[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]