[REBOL] Coffee break problem anyone?
From: SunandaDH::aol::com at: 4-Nov-2003 7:02
Here's a little problem I needed an answer to yesterday.
As I needed the answer yesterday, I hacked together some code. But there has
got to be a more elegant way, surely. Maybe using parse on a block?
The problem is this......You have a block containing integers, like this:
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
]
They are not in ascending order, and there are some numbers duplicated. But
there are runs of consecutive, ascending integers: 12--17, 7--8 etc. We want
to find the location in the block of the first longest, such sequence.
The answer for this dataset is 20--26. 101--107 is as long, but isn't the
first. 59--52 is longer, but it is descending.
My solution is below. Someone can do better, surely!
Thanks,
Sunanda
;;=============================
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: 0
largest-run-start: data-array ;; in case there are zero data items
Forever
[if tail? current-location
[if run-size > largest-run-size
[largest-run-size: run-size
largest-run-start: run-start
]
break ;; we're done
]
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 (1 + first back current-location) = current-location/1
[
;; The run continues
;; -----------------
run-size: run-size + 1
current-location: next current-location
]
[
;; Run's ended: check if it was the largest so far
;; -----------------------------------------------
if run-size > largest-run-size
[largest-run-size: run-size
largest-run-start: run-start
]
current-state: 0
]
] ;; 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]
