Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search

[REBOL] Re: Coffee break problem anyone?

From: SunandaDH:aol at: 5-Nov-2003 2:28

Thanks to (in order of message receipt at my end) Gabriele, Gabriele, Romano, Ladislav, and Joel for showing me better approaches. Parse is so powerful, I should try to learn to use it for more things that just breaking strings apart. Joel:
> This is a great little problem for comparing two approaches that handle > state differently: classic stateful structured programming massages > variables to maintain state, while the Jackson Structured Methodology > maps data structure to algorithm structure as much as possible.
Interesting discussion! I suspect most of us start out "procedural" -- trying to apply processes to what we see as static data structures. I admit I never was a great fan of JSP, but the insight that (in effect) the procedures can fall naturally out of an analysis of the data structures can lead to some very elegant solutions. Of course there are situations where neither approach works, and then you need other approaches too. Object-orientation is one claim to the next step as it merges both approaches. I never quite saw the point there, either, but it does work in some areas. And then there are situations that seem completely off the deterministic axis. Consider this progression: -- Find the sum of the numbers (simply almost any way: write a loop; use a map function, etc) -- Find the longest run with the highest end value (101--107 in the original data) -- Find the run (as defined in the original problem) whose run length is the modal length of runs --Find the two runs that are most nearly similar (contain mostly the same numbers) -- The numbers are RGB values from a JPG. Find the average color tone of the object the female nearest the camera is looking at. Break out the neural networks for this one! In my actual case, the patterns I was looking for grew more complex, so I reasoned that the requirement was becoming unreasonable as the preceding data structures weren't designed for easy sifting. Luckily, I could rewrite history (not always a luxury in this industry) and simplified the problem almost out of existence. Finally, this is getting a bit long, but just to stick up for the "finite machine state" approach I took in the original code. It isn't necessary to duplicate tests as my hacked-out original did -- see new improved (but already redundant) model below. But it is, as Joel notes, tricky to handle boundary conditions -- note the non-obvious way that largest-run-size is initialised. Thanks again everyone, Sunanda sparse-array: [ 12 13 14 15 16 17 7 8 20 21 22 23 24 25 26 19 59 58 57 56 55 54 53 52 20 21 22 23 101 102 103 104 105 106 107 ] ;;============================= find-longest-run: func [data-array [block!] /local current-state current-location run-size largest-run-size largest-run-start ] [ current-state: 0 current-location: data-array run-size: 0 largest-run-size: minimum 1 length? data-array ;; in case there is exactly one element largest-run-start: data-array ;; in case there are zero data items while [not tail? current-location] [ switch current-state [ ;; State 0: start of a new run ;; --------------------------- 0 [ run-start: current-location run-size: 1 current-location: next current-location current-state: 1 ] ;; end state 0 ;; State 1: next item ;; ------------------ 1 [ either run-start/1 + run-size = current-location/1 [ ;; The run continues ;; ----------------- run-size: run-size + 1 current-location: next current-location ;; Update largest, if it's biggest so far ;; -------------------------------------- if run-size > largest-run-size [largest-run-size: run-size largest-run-start: run-start ] ] [ current-state: 0 ;; the run has ended -- go start another one ] ] ;; end state 1 ] ;; switch ] ;; forever return reduce [largest-run-size largest-run-start] ] ;; func ;; Run some tests ;; -------------- set [run-size run-start] find-longest-run sparse-array print ["Length:" run-size "Looks like:" copy/part run-start run-size] set [run-size run-start] find-longest-run [1 2 3 4 5 ] ;; just one run print ["Length:" run-size "Looks like:" copy/part run-start run-size] set [run-size run-start] find-longest-run [999] ;; just one data point print ["Length:" run-size "Looks like:" copy/part run-start run-size] set [run-size run-start] find-longest-run [] ;; empty dataset print ["Length:" run-size "Looks like:" copy/part run-start run-size]