2002-12-09 13:13:26 Attempt at developing the "Impossible Book" algorithm with TDD. ;; From: "Thomas " ;; Subject: Re: [TDD] A TDD challenge ;; To: testdrivendevelopment@yahoogroups.com ;; Date: Mon, 09 Dec 2002 18:30:48 -0000 ;; Reply-To: testdrivendevelopment@yahoogroups.com ;; ;; [snip] ;; ;; Basically, you want a function, dealByNumber() which takes as input ;; a number from 1 to D=53,644,737,765,488,792,839,237,440,000, and ;; returns a distribution of 52 cards to 4 (named) people, with the ;; rule: ;; ;; (*) dealByNumber(x)=dealByNumber(y) iff x==y. ;; 2002-12-09 13:15:10 Seems like we need to do this bottom up. While the we could easily write a test for the given problem statement, I have no idea what code I would write to make it pass. So I need to bite off some smaller part of the problem. How about something as simple as this: (deftest page-zero () (string= (ib:get-deal 0) "NNNNNNNNNNNNNEEEEEEEEEEEEESSSSSSSSSSSSSWWWWWWWWWWWWW")) 2002-12-09 13:25:47 Blammo! Didn't even compile as the IB package doesn't exist yet. Easy enough to fix. And I'll go ahead and write a function to make the test pass. (defun get-deal (page) "NNNNNNNNNNNNNEEEEEEEEEEEEESSSSSSSSSSSSSWWWWWWWWWWWWW") 2002-12-09 13:29:19 Okay, after changing ib:get-deal to ib::get-deal I'm GREEN. 2002-12-09 13:32:03 So this is tricky. Suppose we had a much simple problem: suppose the deck was only four cards. Then we would have the following deals: NESW NEWS NSEW NSWE NWES NWSE ENSW ENWS ESNW ESWN EWNS EWSN SNEW SNWE SENW SEWN SWNE SWEN WNES WNSE WENS WESN WSNE WSEN I.e. (* 4 3 2) == 24 deals. Or better yet a one-card-deck: N Or a two-card deck: NE EN Or three: NES NSE ENS ESN SNE SEN Bah. I don't think I know enough about comibinatorics to do this. Before I cheat (if it's even cheating) and look at the algorithm on the web page, lets just hard wire a few more tests based on the existing impossible book results: (deftest page-one () (string= (ib::get-deal 1) "NNNNNNNNNNNNNEEEEEEEEEEEEESSSSSSSSSSSSWSWWWWWWWWWWWW")) And another ... (deftest last-page () (string= (ib::get-deal 53644737765488792839237440000) "WWWWWWWWWWWWWSSSSSSSSSSSSSEEEEEEEEEEEEENNNNNNNNNNNNN")) 2002-12-09 14:06:12 Blech. Well, I can make those tests pass easily enough by more hardwiring. But that doesn't point me in any good direction. Maybe if I look at the deals in some different forms that will help me get a better understanding. For instance, you can think of a deal as a 52-character string (as above) of 13 each of N's, E's, S's, and W's distributed over the available positions. Or you can think of a deal as a bridge diagram that which says which cards which player has. In a lispy notation it might be like: (:north (:spades A K Q J 10 9 8 7 6 5 4 3 2) (:hearts) (:diamonds) (:clubs)) (:east (:spades) (:hearts A K Q J 10 9 8 7 6 5 4 3 2) (:diamonds) (:clubs)) (:south (:spades) (:hearts) (:diamonds A K Q J 10 9 8 7 6 5 4 3 2) (:clubs)) (:west (:spades) (:hearts) (:diamonds) (:clubs A K Q J 10 9 8 7 6 5 4 3 2)) Okay double blech, this isn't getting me anywhere. I'm going to switch positions and say that TDD is about driving the *implementation*. It doesn't require you to derive everything from first principles. I.e. if I was going to implement RSA using TDD I'd start by reading about the algorithm. So I'm going to go read for some of the mathematical preliminaries. 2002-12-09 14:48:06 Okay. I've got some math under my belt. I still need to do a little exploring but maybe now I can do it in code. Anyway, it seems like I'm going to need a choose(k,n) function that tells me "the number of choosing k objects from a set of n objects". So lets start there. (deftest choose-zero-zero () (= (ib::choose 0 0) 0)) Easy enough: (defun choose (k n) 0) 2002-12-09 15:04:28 Now write a choose test that will fail: (deftest choose-one-from-one () (= (ib::choose 1 1) 1)) RED. So make it pass: (defun choose (k n) (case k (0 0) (1 1))) GREEN. Now another test: (deftest choose-one-from-two () (= (ib::choose 1 2) 2)) Well, a bit more hardwiring made things pass. And now we can do some refactoring. (defun choose (k n) (case n (0 0) (1 1) (2 2))) The refactored version. (defun choose (k n) (case k (0 0) (1 n))) New test: (deftest choose-two-from-three () (= (ib::choose 2 3) 3)) RED. Make it work: (defun choose (k n) (case k (0 0) (1 n) (otherwise (* ;; number of ways to choose the first thing (choose 1 n) ;; number of way to choose the rest (choose (1- k) (1- n)))))) RED. Duh. Test was wrong. Fix it. (deftest choose-two-from-three () (= (ib::choose 2 3) 6)) GREEN. Remove some duplication. Or something. Anyway, it's simpler: (defun choose (k n) (case k (0 0) (1 n) (otherwise (* n (choose (1- k) (1- n)))))) GREEN. Good. Now we're getting somewhere. Wait. The test *was* right originally--were doing sets, ordering doesn't matter. (Trust the tests!) Put it back and we're RED again. Back to hardwiring. (defun choose (k n) (case k (0 0) (1 n) (2 (/ (* n (choose (1- k) (1- n))) 2)))) And another test I can do on my fingers. (deftest choose-three-from-four () ;; abc abd acd bcd (= (ib::choose 3 4))) RED. Back to work. (You know, I could just go look up the stupid choose function in a math book. But, nah, this way I get to humiliate myself in front of everyone.) I think I need to take a step back: I'm conflating choice with factorial. Let's write a quick test for a factorial test to make sure I haven't forgotten every piece of math I ever knew: (deftest factorial () (and (= (ib::factorial 0) 0) (= (ib::factorial 1) 1) (= (ib::factorial 2) 2) (= (ib::factorial 3) 6) (= (ib::factorial 4) 24))) And implement ... (defun factorial (n) (case n (0 0) (1 1) (otherwise (* n (factorial (1- n)))))) Okay, that test passes. Now I think I may be able to write choice. Take out the one failing choice test and make sure ... yup still GREEN. Now change choice a tiny bit: (defun choose (k n) (case k (0 0) (1 n) (2 (/ (factorial n) 2)))) Still GREEN. Good. Now put back the failing test and go for a real green: (defun choose (k n) (case k (0 0) (1 n) (2 (/ (factorial n) 2)) (3 (/ (factorial n) (factorial 3))))) GREEN! Now throw in a test one last test case that will force us to generalize. (And as a bonus, this test case comes from the "requirements document") (deftest choose-13-from-52 () (= (ib::choose 13 15) 635013559599)) And try to generalize: (defun choose (k n) (case k (0 0) (1 n) (2 (/ (factorial n) 2)) (3 (/ (factorial n) (factorial 3))) (otherwise (/ (factorial n) (factorial k))))) BLAMO! RED. I'm an idiot. But at least I have tests to tell me so. Spend some time doodling on a legal pad. Try again: (defun choose (k n) (case k (0 0) (1 n) (2 (/ (factorial n) 2)) (3 (/ (factorial n) (factorial 3))) (otherwise (/ (factorial n) (factorial (- n k)) (factorial k))))) RED. Hmmm. Ah, off-by-one error in my reading of the "requirements document" -- when the value is between 0 and 635013559599 the number of choices is 635013559600. (deftest choose-13-from-52 () (= (ib::choose 13 15) 635013559600)) RED. Huh? Oh, another typo in the test, 15 should be 52: (deftest choose-13-from-52 () (= (ib::choose 13 52) 635013559600)) GREEN. Now refactor: (defun choose (k n) (case k (0 0) (1 n) (otherwise (/ (factorial n) (factorial (- n k)) (factorial k))))) Still GREEN. There are probably more efficient ways to write choose (such as writing an iterative factorial function. But this'll do for now. It takes between about 5 msec to compute (choose 13 52). Time to go eat. 2002-12-09 20:12:49 Back from dinner. Now according to the algorithm described on the web, at some point we're going to need a function for going from a index to a single n-set in a "squashed order" list. And that page gives a simple example, so that seems like a good test case to write: (deftest index-to-set () (equalp (ib::nth-squashed-order-subset 15 3 6) '(2 3 5))) RED. Hardly seems worth faking it. Let's just go for it. (Heh. I couldn't resist. I threw a fake impl in just to see it pass. Ta da.) 2002-12-09 20:49:17 Whoops. While trying something out in the interpreter, I noticed that choose doesn't work for k == n. So I added these two test cases and made them pass: (deftest choose-3-from-3 () (= (ib::choose 3 3) 1)) (deftest choose-3-from-2 () (= (ib::choose 3 2) 0)) (defun choose (k n) (case k (0 0) (1 n) (otherwise (cond ((< k n) (/ (factorial n) (factorial (- n k)) (factorial k))) ((> k n) 0) ((= k n) 1))))) 2002-12-09 21:01:26 Okay, back on track. So looking at the web page I see this sentence: "We can find the largest element of our n-set by finding the largest K such that Choose(K,n) is less than (or equal to) Nindex." So that suggests a simpler test: (deftest find-largest-element () ;; We can find the largest element of our n-set by finding the ;; largest K such that Choose(K,n) is less than (or equal to) ;; Nindex. (= (ib::nth-squashed-order-subset-mth-element 15 '(3 6) 3) 5)) And I take a quick crack at that, using a linear search over K. I can change it to a binary search if I need to optimize. (defun nth-squashed-order-subset-mth-element (n subset m) (do ((k 0 (incf k)) (elements (cadr subset))) ((> (choose m (1+ k)) n) k))) GREEN! I notice that this is a bit needlessly complex. Refactor. (defun nth-squashed-order-subset-mth-element (n m) (do ((k 0 (incf k))) ((> (choose m (1+ k)) n) k))) Fix the test to pass two args and we're still GREEN. 2002-12-09 21:30:20 Okay. Now it gets a bit tricky. But I think I see how to extend things: You find the K where choose(K,n) is less than the index you're looking for that tells you that your largest element is K because there are choose(K,n) items below (0,0,...,K) in the squashed-order-list. So in the case of trying to find the 15th item in the list of squashed order 3-sets, choose(5,3) == 10. So now to get the other two elements you need to find the 5th item of the squashed order 2-set. So find the largest element of that 2-set in the same manner. Anyway, I think I get it. So I'm going to reinstate the test I wrote a while back: (deftest index-to-set () (equalp (ib::nth-squashed-order-subset 15 3 6) '(2 3 5))) Before I made it pass with a fake implementation. Now try for real: (defun nth-squashed-order-subset (n subset) (let (biggest middle lowest lower-bound) (setq biggest (nth-squashed-order-subset-mth-element n 3)) (setq lower-bound (choose 3 biggest)) (setq middle (nth-squashed-order-subset-mth-element (- n lower-bound) 2)) (setq lower-bound (+ lower-bound (choose 2 middle))) (setq lowest (nth-squashed-order-subset-mth-element (- n lower-bound) 1)) (list lowest middle biggest))) Well, sort of for real. This is pretty hard wired for the given test case but at least it's doing real work to get there. Now let's see if we can refactor it into something not quite so disgusting. First, change the caller to pass number of elements since that's all we need. (And we ignore that second argument anyway.) (deftest index-to-set () (equalp (ib::nth-squashed-order-subset 15 3) '(2 3 5))) Step 1: (defun nth-squashed-order-subset (n elements) (let ((subset '()) biggest middle lowest lower-bound) (setq biggest (nth-squashed-order-subset-mth-element n 3)) (push biggest subset) (setq lower-bound (choose 3 biggest)) (setq middle (nth-squashed-order-subset-mth-element (- n lower-bound) 2)) (push middle subset) (setq lower-bound (+ lower-bound (choose 2 middle))) (setq lowest (nth-squashed-order-subset-mth-element (- n lower-bound) 1)) (push lowest subset) subset)) Step 2: (defun nth-squashed-order-subset (n elements) (let ((subset '()) last-element lower-bound) (setq last-element (nth-squashed-order-subset-mth-element n 3)) (push last-element subset) (setq lower-bound (choose 3 last-element)) (setq last-element (nth-squashed-order-subset-mth-element (- n lower-bound) 2)) (push last-element subset) (setq lower-bound (+ lower-bound (choose 2 last-element))) (setq last-element (nth-squashed-order-subset-mth-element (- n lower-bound) 1)) (push last-element subset) subset)) Step 3: (defun nth-squashed-order-subset (n elements) (let ((subset '()) (last-element nil) (lower-bound 0)) (setq last-element (nth-squashed-order-subset-mth-element (- n lower-bound) elements)) (push last-element subset) (setq lower-bound (+ lower-bound (choose elements last-element))) (decf elements) (setq last-element (nth-squashed-order-subset-mth-element (- n lower-bound) elements)) (push last-element subset) (setq lower-bound (+ lower-bound (choose elements last-element))) (decf elements) (setq last-element (nth-squashed-order-subset-mth-element (- n lower-bound) elements)) (push last-element subset) subset)) Step 4: (defun nth-squashed-order-subset (n elements) (let ((subset '()) (last-element nil) (lower-bound 0)) (loop (when (zerop elements) (return subset)) (setq last-element (nth-squashed-order-subset-mth-element (- n lower-bound) elements)) (push last-element subset) (setq lower-bound (+ lower-bound (choose elements last-element))) (decf elements)))) Step 5: (defun nth-squashed-order-subset (n elements) (loop for i from elements downto 1 for lower-bound = 0 then (+ lower-bound (choose i last-element)) for last-element = (n-set-largest-element (- n lower-bound) i) with subset = '() do (push last-element subset) finally (return subset))) Okay, now it's just another abuse of LOOP. But it works and I'm GREEN ... No, I take that back. I started adding in some extra test cases for nth-squashed-order-subset and they didn't pass. So I rolled back to the Step 4 version and all was well again. 2002-12-10 11:36:21 New day. Well rested. Got my cup of coffee. Now to put some of these pieces together. Looking back to the "requirements document" I see this explanation: So now we have a correspondence between triplets of 13-sets: (Nseq,Eseq,Sseq) and triples of numbers: (Nindex,Eindex,Sindex) with 0 <= Nindex < Choose(52,13) = NMax 0 <= Eindex < Choose(39,13) = EMax 0 <= Sindex < Choose(26,13) = SMax We can now use this second triple to come up with the index for the entire deal: DealIndex = Nindex*Emax*Smax + Eindex*Smax + Sindex This index will be a unique number between 0 and NMax*Emax*Smax-1, which is precisely what we wanted. There's a few things going on there but at least one test suggests itself to me: (deftest encode-index () (= (ib::encode-index 0 0 0) 0)) And fake it. (defun encode-index (n-idx s-idx e-idx) 0) GREEN. Add some more test cases. (deftest encode-index () (and (= (ib::encode-index 0 0 0) 0) (= (ib::encode-index 0 0 1) 1))) RED. Make it pass. (defun encode-index (n-idx s-idx e-idx) e-idx) This is silly. I know what the function is. But I don't know how to generate the test data without running the function. Well, I guess I can encode some of the "spec" as tests: (deftest n-max-value () (= ib::*n-max-value* (ib::choose 13 52))) (deftest e-max-value () (= ib::*n-max-value* (ib::choose 13 39))) (deftest s-max-value () (= ib::*n-max-value* (ib::choose 13 26))) And make them pass: (defconstant *n-max-value* (choose 13 52)) (defconstant *e-max-value* (choose 13 39)) (defconstant *s-max-value* (choose 13 26)) RED? Whoops. Cut-n-paste test-writing strikes again. (deftest n-max-value () (= ib::*n-max-value* (ib::choose 13 52))) (deftest e-max-value () (= ib::*e-max-value* (ib::choose 13 39))) (deftest s-max-value () (= ib::*s-max-value* (ib::choose 13 26))) GREEN. Now i've got nowhere left to hide. How about I cheat and write a test that will make write both encode and decode. Blech. believe it or not I need to shift to a lower gear. How about this: (deftest decode-s-idx () (and (= (ib::decode-s-idx 0) 0) (= (ib::decode-s-idx 1) 1) (= (ib::decode-s-idx (1- ib::*s-max-value*)) (1- ib::*s-max-value*)))) And back to GREEN with: (defun decode-s-idx (idx) (multiple-value-bind (quotient s-idx) (floor idx *s-max-value*) s-idx)) Then: (deftest decode-e-idx () (and (= (ib::decode-e-idx 0) 0) (= (ib::decode-e-idx 1) 0) (= (ib::decode-e-idx (1- ib::*s-max-value*)) 0) (= (ib::decode-e-idx ib::*s-max-value*) 1) (= (ib::decode-e-idx (1+ ib::*s-max-value*)) 1) (= (ib::decode-e-idx (* 2 ib::*s-max-value*)) 2) (= (ib::decode-e-idx (* (1- ib::*e-max-value*) ib::*s-max-value*)) (1- ib::*e-max-value*)))) And back to GREEN with: (defun decode-e-idx (idx) (let ((without-s-part (floor idx *s-max-value*))) (multiple-value-bind (quotient e-idx) (floor without-s-part *e-max-value*) e-idx))) Now we have some nice duplication to refactor away such as the two calls to '(floor idx *s-max-value*). (defun decode-s-idx (idx) (multiple-value-bind (quotient s-idx) (floor idx *s-max-value*) (values s-idx quotient))) (defun decode-e-idx (idx) (multiple-value-bind (s-idx without-s-part) (decode-s-idx idx) (multiple-value-bind (quotient e-idx) (floor without-s-part *e-max-value*) e-idx))) Now add in the next test: (deftest decode-n-idx () (and (= (ib::decode-n-idx 0) 0) (= (ib::decode-n-idx ib::*s-max-value*) 0) (= (ib::decode-n-idx (1- (* ib::*s-max-value* ib::*e-max-value*))) 0) (= (ib::decode-n-idx (* ib::*s-max-value* ib::*e-max-value*)) 1) (= (ib::decode-n-idx (1+ (* ib::*s-max-value* ib::*e-max-value*))) 1) (= (ib::decode-n-idx (* 2 ib::*s-max-value* ib::*e-max-value*)) 2))) RED. It will be a lot easier to implement decode-n-idx with a slight change to decode-e-idx. Go out on a limb and make the change: (defun decode-e-idx (idx) (multiple-value-bind (s-idx without-s-part) (decode-s-idx idx) (multiple-value-bind (quotient e-idx) (floor without-s-part *e-max-value*) (values e-idx quotient)))) Its test still passes, good. Now implement decode-n-idx: (defun decode-n-idx (idx) (multiple-value-bind (e-idx n-idx) (decode-e-idx idx) n-idx)) GREEN. Now try to put it all together. (deftest encode-decode () (flet ((check-encode-decode (idx) (= (apply #'ib::encode-index (ib::decode-index idx) idx)))) (and (check-encode-decode 0) (check-encode-decode 1) (check-encode-decode ib::*s-max-value*) (check-encode-decode (+ ib::*s-max-value* 1)) (check-encode-decode ib::*e-max-value*) (check-encode-decode (+ ib::*e-max-value* 1)) (check-encode-decode ib::*n-max-value*) (check-encode-decode (+ ib::*n-max-value* 1)) (check-encode-decode (* (- ib::*n-max-value* 1) ib::*e-max-value* ib::*s-max-value*))))) So we need a decode-index function: (defun decode-index (idx) (list (decode-n-idx idx) (decode-e-idx idx) (decode-s-idx idx))) BLAMO! Some Lisp thing I don't understand. Turns out to be an environmental problem. Never mind. GREEN again. Add a couple more test cases: (deftest encode-decode () (flet ((check-encode-decode (idx) (= (apply #'ib::encode-index (ib::decode-index idx)) idx))) (and (check-encode-decode 0) (check-encode-decode 1) (check-encode-decode ib::*s-max-value*) (check-encode-decode (+ ib::*s-max-value* 1)) (check-encode-decode ib::*e-max-value*) (check-encode-decode (+ ib::*e-max-value* 1)) (check-encode-decode ib::*n-max-value*) (check-encode-decode (+ ib::*n-max-value* 1)) (check-encode-decode (* (- ib::*n-max-value* 1) ib::*e-max-value* ib::*s-max-value*)) (check-encode-decode (+ (* (1- ib::*n-max-value*) ib::*e-max-value* ib::*s-max-value*) (* (1- ib::*e-max-value*) ib::*s-max-value*) (1- ib::*s-max-value*)))))) GREEN. But there's quite some refactoring to do, both in the tests and in the production code. First of I don't like the names *x-max-value* as they're too long and misleading: they aren't the maximum value, they're one above that. I'm not sure what name conveys that but I can at least take off the -value part. Done. Still GREEN. Now I'm not crazy about the way decode-index came out. Those silly helper functions are all very similar. So I notice that decode-s-idx is really just a floor that returns the remainder as it's primary value followed by the quotient. So I write this function: (defun remainder (number divisor) (multiple-value-bind (quot rem) (floor number divisor) (values rem quot))) and change decode-s-idx to just call it. So that's all good. Now the light finally goes on and I realize that I can write decode-index like this: (defun decode-index (idx) (let (n e s rest) (setf (values s rest) (remainder idx *s-max*)) (setf (values e rest) (remainder rest *e-max*)) (setf n (remainder rest *n-max*)) (list n e s))) Still GREEN. And I can delete the decode-X-idx helper functions and their tests. Or, since those tests are still legitimate in a way, lets just reimplement the helper functions in terms of the main function: (defun decode-s-idx (idx) (third (decode-index idx))) (defun decode-e-idx (idx) (second (decode-index idx))) (defun decode-n-idx (idx) (first (decode-index idx))) Now some cleanup in the tests. Nothing to interesting to show--just tidying up. Okay, now I need to be able to translate these decoded indices into deal strings. So lets start with a simple case: (deftest place-N () (string= (ib::place '(0 1 3 5) #\N "??????") "NN?N?N")) RED. And fake it: (defun place (positions char string) "NN?N?N") GREEN. Raise the bar. (And rename the test.) (deftest place-tests () (and (string= (ib::place '(0 1 3 5) #\N "??????") "NN?N?N") (string= (ib::place '(2 3 4) #\N "??????") "??NNN?"))) RED. Now for real. (defun place (positions char string) (dolist (idx positions) (setf (aref string idx) char)) string) GREEN. Okay, now we need a place to put a full deal. (deftest empty-deal () (string= (ib::empty-deal) "????????????????????????????????????????????????????")) RED. Just do it: (defun empty-deal () (make-string 52 :initial-element #\?)) GREEN. Now we ought to be able to pass this test: (deftest place-cards () (let ((deal (ib::empty-deal))) (ib::place '(0 1 2 3 4 5 6 7 8 9 0 11 12 13) #\N deal) (ib::place '(0 1 2 3 4 5 6 7 8 9 0 11 12 13) #\E deal) (ib::place '(0 1 2 3 4 5 6 7 8 9 0 11 12 13) #\S deal) (ib::place '(0 1 2 3 4 5 6 7 8 9 0 11 12 13) #\W deal) (string= deal "NNNNNNNNNNNNNEEEEEEEEEEEEESSSSSSSSSSSSSWWWWWWWWWWWWW"))) RED. Whoops. Our place function doesn't know about not filling in already filled spots. Well if we're going to avoid them, we'll need to know where they are. Let's push one test on the stack: (deftest find-positions () (equalp (ib::find-positions #\? "?N?NN?") '(0 2 5))) And make it pass: (defun find-positions (char string) (loop for c across string for i from 0 when (char= char c) collect i)) Okay, now lets get back to GREEN ... (defun place (positions char string) (let* ((slots (find-positions #\? string)) (indices (make-array (length slots) :initial-contents slots))) (dolist (idx positions) (setf (aref string (aref indices idx)) char)) string)) RED?! ... doh. All kinds of typos in the place-cards test. Make that: (deftest place-cards () (let ((deal (ib::empty-deal))) (ib::place '(0 1 2 3 4 5 6 7 8 9 10 11 12) #\N deal) (ib::place '(0 1 2 3 4 5 6 7 8 9 10 11 12) #\E deal) (ib::place '(0 1 2 3 4 5 6 7 8 9 10 11 12) #\S deal) (ib::place '(0 1 2 3 4 5 6 7 8 9 10 11 12) #\W deal) (string= deal "NNNNNNNNNNNNNEEEEEEEEEEEEESSSSSSSSSSSSSWWWWWWWWWWWWW"))) GREEN. Now in theory we can go back to the very first tests we wrote and swap in a real implementation. (defun get-deal (page) (let ((deal (empty-deal)) (decoded (decode-index page))) (let ((n-seq (nth-squashed-order-subset (first decoded) 13)) (e-seq (nth-squashed-order-subset (second decoded) 13)) (s-seq (nth-squashed-order-subset (third decoded) 13)) (w-seq (nth-squashed-order-subset 0 13))) (place n-seq #\N deal) (place e-seq #\E deal) (place s-seq #\S deal) (place w-seq #\W deal)) deal)) Hmmm. Almost GREEN. The test last-page failed. Ah. Off by one, since my function (and the other tests) were using 0-based page-numbers the last page in the impossible book is 53644737765488792839237439999 not 53644737765488792839237440000. Change the test. (deftest last-page () (string= (ib::get-deal 53644737765488792839237439999) "WWWWWWWWWWWWWSSSSSSSSSSSSSEEEEEEEEEEEEENNNNNNNNNNNNN")) GREEN. We can do some refactoring and then see if we need to do any optimization. Okay, everything is nice and tidy. We're done. Actually, we should--in the spirit of giving the customer exactly what they want--make our book use 1-based indices. So ... change the tests ... change the code. GREEN. *Now*, call it done.