And yes, n/2 splitting (for this modified problem) _should_ be optimal as it transmits maximum information. And I think the _proof_ should be obvious from some information theoretic point-of-view.

So, I think this modified optic-fiber problem turns out to be easy after all; compared to the original copper-wire problem that involved more interesting math. And that deeper problem always (when n != 2,5,9) has a 2-step solution compared to the best Log[2,n]-step solution of the simpler problem!

I think your Ceiling[Log[2,n]]-step assertion is correct, but I’m confused about your method. For eight wires are you saying you should light in the following pattern?
00000001
00000010
00000011
00000100
00000101
00000110
00000111
00001000

Most of those are redundant and you still wouldn’t know four of them. I’m either misunderstanding you and/or you meant something like this:
11110000
11001100
10101010

This is such a simple method, I wonder if there isn’t some more complexity lying within this problem once n gets bigger…

I’m starting to be convinced that there is not. Any initial n-splitting with k “on” wires, no matter how complex, is essentially “isomorphic” to an (n-k)k split, that is, 11001100 ~= 11110000 ~= 10101010. Then it essentially becomes two problems – (n-k) and k. Just judging from our small samples clearly it is better when k = n/2, or as close as possible if n is odd. If k = n/2 is the ideal split, then Ceiling[Log[2,n]] should be correct, no?

For example if instead of splitting 8 into 4-4 we split into 6-2 we’d end up taking four steps instead of three, since we have the initial split and 6 takes three steps.

hmm…

For 5 wires, by working out all possible two-step solutions, it looks clear to me that a three-step solution is the best possible.

In general, a Ceiling[Log[2,n]]-step solution is easy: Number the wires {0,1,…,n-1}. In the kth step, turn on the lights of wires the binary representation of which have kth bit ON. On the other end, keep building the IDs of each wire, a bit at each step.

Now the question is: Could some clever scheme do better than Ceiling[Log[2,n]]-steps?

The two-wire situation is now obvious. Besides that I’ve only looked at the five wore situation which can be solved in three steps as follows:

For wires A,B,C,D, and E, light up A, B, and C and mark that group somehow. Then light up A, and D. This will give you A (lit up both times), D (lit up once), and E (never lit up). Now you have the two wire situation (B and C) and so one more step will do it.

Not sure if it can be done in two steps, nor do I have an inkling towards the general solution.

Is anyone aware if this is a solved problem? Please don’t tell me Erdös solved it :).

While the book doesn’t ever mention “functional programming”, many of K&P’s suggestions, as you said, work nicely with FP:

Functions in FP tend to be naturally small: It is interesting to ponder what makes programming with FP-flavor lead naturally to smaller, shorter, more concise functions. It could well be that this is my personal feeling because I’ve never really programmed “real-world” programs to solve “real” problems. But I suspect it is more generally true: Functions in imperative languages tend to be longer.

Functions in FP are more loosely coupled. Again, this is arguable. But I think using lists or property-bags as common data-structures leads to looser coupling.

And of course, FP eliminates a whole variety of errors related to order of assignment, uninitialized variables, using evil control structures… FP is good.

As for top-down design, “successive refinement” does seem to be a good way to understand a solution, if not necessarily design one — it helps understand the interactions between the players before delving in details on how each one does its job.

Perhaps top-down vs. bottom-up is like this: Which do you do first when coding or defining a recursive function — code the “recursion part” first, or, code the base case first? Most times, I think, it is more natural do the “recursion part” first, if only because it helps clarify what the base cases should be — precisely the cases for which it makes no further sense to subdivide the problem to conquer it!

But Top-down vs. Bottom-up is surely controversial, so I will not speak more ;-)

I remember, Alex Stepanov once gave a lecture here at our Adobe office, and there was a fair bit of discussion around this point. I actually cannot remember which, if any, side he spoke for. However, see page 5 of his notes on programming. There, he tries to be promoting a view alternative to top-down design, perhaps mostly to encourage the reader to appreciate the “bottom” of software — data-structures, algorithms and complexity — stuff which too many “pattern-oriented” designs consider secondary. When phrased like that, I personally, am all for the bottom of it!

Most points sound pretty decent and uncontroversial. I’m not sure about the top-down one though! This kind of approach works a lot of time, but not all the time. Sometimes it’s actually better to build things bottom up, or do a mix of both. I think it depends more on what the problem is.

Thanks,
Sam

Yes, I remember flipping through that book some years ago — it did have a similar flavor.

Kernighan’s books are still awesome if only because they are short, sweet, to the point, and, of course, still relevant — one small reason I prefer them over, say, Code Complete.

Code Complete too, is highly acclaimed, on similar lines, and more current. But it’s a much larger work (~250 vs. ~1000 pages), and studying it would take much more than a week (roughly the time I took to finish Programming Style).