### B. Tidy Numbers

*d*we're happy. If

_{i}≤d_{i+1}*d*we need to "fix it up". Fixing it up means usually means changing

_{i}>d_{i+1},*d*to

_{i}*d*and replacing everything to the right with nines. We cannot run into

_{i}-1*d*, because there are no leading zeroes and we have already checked that the prefix of the number up to and including digit

_{i}=0*i*is Tidy, so the digits cannot become lower. The local fixup may result in the overall number not being Tidy anymore, i.e. we may have made d

_{i}<d

_{i-1}. So we need to recurse (or reiterate, but hey we're thinking in Lisp, right?) on the result. We also may have introduced a leading zero that should be removed. So we remove those. The resulting code is in B.lisp. The code is recursive but not purely functional, because it munches the array using

`(setf (aref ...) ...)`. That's ugly and might have made debugging harder, but then the code should be easy enough to not need debugging. And probably this (half-) destructive approach saves a few cycles...

### C. Bathroom Stalls

*general*pattern.

Pretty quickly, I had a complete understanding of the case where

*N=2*The first person (K=1=2

^{i}-1:^{0}) has

*2*space to the left and to the right, the next two (

^{i-1}-1*2*) persons each have

^{1}*2*space to the left and right, and so on. But how to generalize this to

^{i-2}-1*N*s that do not have this form?

At any "round of the game" (K), there is a set of "extents" of free space. In each round, the largest of the current extents is "split": If the size of this largest extent is odd and larger than one, that is, of the form

*2x+1,*then it will be split into two extents of size

*x.*That was the "easy" case that covers the problem completely when

*N=2*

^{i}-1.But for other kinds of

*N,*I still had no good idea of the pattern how the overall set of extents develops. In a desperate attempt, I tried to draw this up as a tree for

*N=6.*That looked somewhat promising, but I still couldn't figure out the general pattern. At least it shows the special case of the size-2 extent, which doesn't really get split into two extents but degenerates into a single size-1 extent. Hm, this seems complicated.

In an even more desperate attempt, I decided that I needed to look at a bigger example and started drawing up the tree for

*N=230.*Nothing very particular about that number, except that I wanted to start with an even number because that seems to be the more complicated case.

Now that led to the breakthrough. In this non-trivial example, I saw that each level of the tree only contained (a maximum of) two different values with a difference of one.

So a complete and useful description of a given level of the tree is the distribution between these two different values. This is what I wrote up in the right-hand column: On level 1 (after the first split) we have extents of 1x114 and 1x115, on level 2, 1x56 and 3x57, on level 3, 1x27 and 7x28, on level 4, 9x13 and 7x14, and so on. Generalizing to level 0, we can say that we start with 1x230 (1x

*N*) and 0x231.

But how does one get from level

*j*to level

*j+1?*Well, each odd extent splits into two equal extents, and each even one splits into one that's half the original number and one that's one lower. That leads to the two cases below the large (partially written-out) tree. (I started writing the cases with

*m*and

*n*and then replaced that with

*a*and

*b,*respectively, but didn't do so all the way because I had enough to write the code.) The code is in C.lisp, and I'm quite happy with it. Initially I had switched the even and odd cases, which led to wrong results on the tiny example under the problem description. First I panicked, but by simply running a few examples under

`(trace minmax-1)`I could locate the error. I knew the code was O(log(N)) efficient, so I fed it the small, still-small, and large cases with confidence, and each was processed in less than 10 milliseconds.

### A. Oversized Pancake Flipper

*K*places before the end because of the flipper restriction), we're done. The last pancakes must then all be + or we lose.

`reverse`(or

`nreverse`) step because it really doesn't matter whether we operate on a mirror image.