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.