[plt-scheme] Re: HtDP Exercise 43.3.3

From: Gadfly (dyrueta at gmail.com)
Date: Sat Mar 6 16:25:47 EST 2010

Solved!

On Mar 6, 10:35 am, Gadfly <dyru... at gmail.com> wrote:
> I think I found the problem....
>
> On Mar 5, 8:32 pm, Gadfly <dyru... at gmail.com> wrote:
>
> > I just realized that even interested parties might hesitate to
> > download two random ss files, so I've cut-and-pasted the contents of
> > both into Google docs:
>
> > placement-with-local available here
>
> >http://docs.google.com/Doc?docid=0AfZKElmhzsp-ZGhkcWgzamZfMzZkcnR4dmh...
>
> > and TestingFunctions available here
>
> >http://docs.google.com/Doc?docid=0AfZKElmhzsp-ZGhkcWgzamZfMzlmZDduN3p...
>
> > On Mar 5, 8:09 pm, David Yrueta <dyru... at gmail.com> wrote:
>
> > > Am hoping to prevail upon a fellow Schemer for help debugging my solution to
> > > one of the final HtDP exercises.  So close, yet so far!
>
> > > The exercise adapts the checking-queens algorithm from Chapter 28 to state
> > > variables.  It asks the student to do two things: 1) design two new
> > > functions, place-queen and unplace-queen, which serve to "set!" the
> > > chessboard as the algorithm backtracks into a solution, and; 2)  implement
> > > those functions into a new version of 'placement.'
>
> > > Here's a link:
>
> > >http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-53.html#node_sec_43.3
>
> > > I've done all that, but my solution fails in a very strange way.
> > > Specifically, it generates the correct solution to for all boards up to 5 x
> > > 5:
>
> > > ;(check-expect (placement 1) (vector (vector true)))  ;; passes
> > > ;(check-expect (placement 2) false) ;; passes
> > > ;(check-expect (placement 3) false) ;; passes
> > > ;(check-expect (placement 4) (vector (vector false false true false) (vector
> > > true false false false) (vector false false false true) (vector false true
> > > false false))) ;; passes
> > > ;
> > > ;(check-expect (placement 5) (vector  ;; passes
> > > ;                             (vector false false true false false)
> > > ;                             (vector true false false false false)
> > > ;                             (vector false false false true false)
> > > ;                             (vector false true false false false)
> > > ;                             (vector false false false false true)))
>
> > > On a 6 x 6 board, things start to get weird --
>
> > > ;(check-expect (placement 6) (vector        ;; fails
> > > ;                             (vector false false false true false false)
> > > ;                             (vector true false false false false false)
> > > ;                             (vector false false false false true false)
> > > ;                             (vector false true false false false false)
> > > ;                             (vector false false false false false true)
> > > ;                             (vector false false true false false false)))
>
> > > Here's what I get instead ---
>
> > > (vector
> > >  (vector false false false true false false)
> > >  (vector true false false false false false)
> > >  (vector false false false false true false)
> > >  (vector false true false false false false)
> > >  (vector false false false false true true)
> > >  (vector false false true false false false))
>
> > > Compared to the correct solution, this result is off by one vector value, or
> > > "queen-position": "true" in 5th column, 5th row.   That should be false --
> > > the queen in column 6 should have "flipped" it after being placed.
>
> > > I tested extensively the place and unplace functions, and they seem to work
> > > fine.  Looking for patterns, I found that if you trace the trajectories of
> > > the queens positioned in *only* vector-column-indexes 0-3, the resulting
> > > board is exactly the one I'm left with. As if the queens in
> > > vector-column-indexes  4 and 5 haven't been placed, even though the queen
> > > positions selected in columns 0-3 are made *as though* they had!
>
> > > Needless to say, things get progressively worse as the board dimension
> > > inputs get larger.
>
> > > All my efforts to debug have been fruitless.  I've sat with the Stepper
> > > literally for hours trying to trace the origins of this result, but to no
> > > avail.  I don't understand how I could get the correct solution for 5, but
> > > have it blow up at 6, get worse at 7, etc.  I also don't understand why the
> > > backtracking strategy which succeeded in all cases in Chapter 28 is not
> > > working here.  I know there are subtle differences, especially in the base
> > > case, but it seems the backtracking approach which worked in the first
> > > should translate to the second.  It's making me a little crazy.
>
> > > I've posted two public ss files to Google docs for anyone who wants to take
> > > a look --
>
> > > "placement-with-local" which is available here --
>
> > >https://docs.google.com/leaf?id=0B_ZKElmhzsp-YzY2YzgxOTctYWFjOC00MDUw...
>
> > > and "TestingFunctions" available here --
>
> > >https://docs.google.com/leaf?id=0B_ZKElmhzsp-NDZiZWJiNzgtNjJhZC00NGRj...
>
> > > Placement-with-local contains the complete algorithm, while TestingFunctions
> > > contains all my tests for the auxiliary functions.  Data definitions,
> > > written arguments for the algorithm (and a second alternative), function
> > > contracts, purpose statements, etc. are all included.
>
> > > This is a function with a lot of moving parts, so anyone who dives into with
> > > me to try and help would be doing me an enormous favor.  The only thing I
> > > can offer in return is lots of gratitude.... and maybe my grandmother's
> > > not-really-secret-but-totally-yummie recipe for Spanish "tortilla patata."
>
> > > As always, any and all suggestions are welcome and appreciated.
>
> > > Many thanks!
>
> > > Dave Yrueta
>
> > > _________________________________________________
> > >   For list-related administrative tasks:
> > >  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
> > _________________________________________________
> >   For list-related administrative tasks:
> >  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
> _________________________________________________
>   For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme


Posted on the users mailing list.