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

[REBOL] Re: Coffee break problem anyone?

From: joel:neely:fedex at: 5-Nov-2003 13:37

Hi, Sunanda, First, let me offer an improvement and then address some more of the good discussion points you raise. (There's a little challenge at the end for the interested who wade through to that point! ;-) Minor issue first: instead of initializing run length to zero and incrementing for each added element, just directly calculate the length once the run is finished. Now for the more interesting stuff... Instead of saying that: - a block is an iteration of runs, and - a run is an iteration of numbers; block --*-- run --*-- number lets say that: - a block is an iteration of runs, and - a run is a first number, followed by any consecutive numbers. +-- first number | block --*--+ | +--*-- consecutive number This (again) addresses a boundary issue; the first value in a run plays a different role than the other numbers in the run. Tricky setup of initial conditions so that the first value can be treated just like all the others adds more complexity to the code. That said, here's a version that implements that view: where-j: func [ block [block!] /local maxpos maxlen runpos runlen prev curr ][ maxpos: maxlen: 0 ; default empty run while [not empty? block] [ ; more data = more runs runpos: index? block ; start new run here prev: block/1 ; remember first value block: next block ; done with first while [ prev + 1 = curr: block/1 ; extending the run ][ prev: curr ; save comparison value block: next block ; move on ] runlen: (index? block) - runpos ; now compute length if runlen > maxlen [ ; update best run? maxpos: runpos maxlen: runlen ] ] reduce [maxpos maxlen] ; return best run ] [SunandaDH--aol--com] wrote:
> ... 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. >
I'm not clear on what you mean by "both approaches"... I view JSP (Jackson Structured Programming) simply as a specific type of structured programming which has strong heuristics about which structure(s) should drive the design.
> And then there are situations that seem completely off the > deterministic axis. >
??? Do you mean non-deterministic programming, or just programming when the criteria are only vaguely stated?
> Consider this progression: > > -- Find the sum of the numbers (simply almost any way: write a loop; > use a map function, etc) >
Easy. Agreed.
> -- Find the longest run with the highest end value (101--107 in the > original data) >
An easy extension of the above program: - add a local MAXTOP initialized to anything - change the condition at the end from runlen > maxlen to any [runlen > maxlen all [runlen = maxlen prev > maxtop]] - change the "new best run" block to include maxtop: prev (For why this was easy, see below...)
> -- Find the run (as defined in the original problem) whose run length > is the modal length of runs >
First, we have to change "the run" to "a run", since the answer is no longer unique. For the data [10 8 9 6 7 4 5 0 1 2] there are runs of length 1, 2, 2, 2, and 3, so the mode length is 2, and there are three runs that have that length. However, something more significant has happened. The previous change to the problem (longest run with highest upper value) actually had THE SAME STRUCTURE as the original problem: find the "best" run, where we have a simple test for determining whether one run is "better" than another. In other words, we can generate runs one at a time, and test each one against the current "best" to see which one wins. But in this last change, we now are asking for a run based on some property/ies of the entire collection of runs, so we must generate (and retain) all of them. We can (trivially) change the above function to return all runs, then write a separate "pick a median" function to operate on that collection (or we build the additional stuff into the end of the modified function). In either case we now have a two-step approach: 1) transform the offered block into a collection of runs; 2) do something with the collection of runs. That's why the first change was easy and the second one was harder.
> --Find the two runs that are most nearly similar (contain mostly the > same numbers) >
I think I can paraphrase that as "find two runs whose intersection is at least as long as any other intersection of distinct runs", which is easy to solve, still using the two-step approach above. This one is also not uniquely determined without more constraints; to see why, consider [1 2 3 4 5 2 3 4 5 6 3 4 5 6 7]
> -- 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! >
Now we've jumped from a programming problem to a specification problem! The other tasks were well-defined (there could be no argument about whether an answer is correct or not), but not so with this last one. (I recently saw a documentary on TV in which a critical question was whether a certain figure in a Renaissance painting was male or female. The "experts" couldn't agree. ;-)
> 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. >
My complements!!! Sometimes the best way to solve a problem is to redifine the terms of discourse so that the problem simply disappears!
> Finally, this is getting a bit long, but just to stick up for the > "finite machine state" approach I took in the original code... >
I certainly use FSM-inspired design at times myself, but the nasty part (IMHO) is always the transition between states. Not implementing the transition (usually just updating a variable) but making it clear to the eye/mind of the reader the pattern of transitions that will actually occur. In that regard, I suggest that the (improved) JSP-inspired version above can be regarded as a FSM as well. It's just that each "state" corresponds to a region of code, and the state transitions are simply the standard flow-control! In the updated FSM version, State 0 is *always* followed by State 1 (modulo falling off of the end) and a series of occurrences of State 1 are likewise followed by a State 0 (same caveat). The JSP version makes that organization much more obvious (IMHO). Finally, there is still considerable redundancy in the FSM version -- it's just in time rather than in codespace! Notice that the "update largest" test is done *for each element* of each run, and the sets for a maximum-length run will be done for each element after the length of its nearest competitor has been passed. The FSM code contains these expressions only once, but evaluates them *MANY* more times than the equivalent ones in the JSP version. I'm not criticizing here, but pointing out the trade-offs (which just happen to be particularly dramatic in this case! ;-) It is possible to optimize for one measure (in this case, minimizing source code redundancy) in such a way that it pessimizes another measure (the number of times the code is -- redundantly -- evaluated). Note that the JSP design heuristics don't minimize *ALL* aspects of code redundancy; the NOT EMPTY? test is really in there twice!!! Brownie points to anyone who can show why! ;-) -jn-