[racket] Request feedback on a boggle solver

Hi Carl,

Thank you very much for your kind feedback. I agree with you that having a
single data structure will make the solution simpler. Let me ponder over
that and see what I can come up with.


Thanks,
Jingjing


On Tue, Sep 24, 2013 at 9:10 AM, Carl Eastlund <cce at ccs.neu.edu> wrote:

> Jingjing,
>
> The new code you've written only follows the HtDP design recipe
> superficially.
>
> First of all, none of your contracts actually tell me what the valid
> inputs and outputs of each function are.  For instance, the contract for
> build-position-to-neighbor is:
>
>   (listof lists) -> (hashof position to neighbors)
>
> But this suggests to me that I could call it like this:
>
>   (build-position-to-neighbor (list (list "the" 'first "list") (list
> "list" 'number 2) (list (list (list)))))
>
> After all, that argument is a list of lists.  Nevertheless, that doesn't
> seem like what build-position-to-neighbor should actually accept.  Your
> contracts need to be based on explicit data definitions.  Descriptive
> phrases like "list of lists" or "hash of position to neighbors" are not
> precise enough.
>
> Second, I think if you write data definitions for this program, you'll
> find something surprising: there are at least two different data
> definitions for a boggle board hidden in your functions.  For a program
> that's all about processing a boggle board, you in fact manipulate many
> different kinds of lists and hash tables.  It would be simpler, and more in
> the style of HtDP, to write a single data definition for a boggle board,
> and use that data definition for every function that operates on a boggle
> board.
>
> Finally, your test cases are not particularly exhaustive.  When testing a
> function, you should start with the smallest possible example.  Write at
> least one base case test, at least one test for a single step beyond the
> base case, and at least one test larger than that.  That way, when a test
> goes wrong, you don't just know that the function is broken, you have some
> idea how and why it is broken.
>
> Carl Eastlund
>
> On Tue, Sep 24, 2013 at 11:18 AM, Jingjing Duan <duanjingjing at gmail.com>wrote:
>
>> Hi Carl,
>>
>> I've cleaned up the code a bit and added tests to all the functions. Do
>> you mind taking another look? Don't hesitate to give comments even if they
>> are trivial. The more the better. I'm a total scheme/racket beginner.
>> Thanks.
>>
>> https://github.com/jduan/boggle_scheme/blob/master/boggle.rkt
>>
>> In the mean time, I'm going to take a look at Jay McCarthy's solution. I
>> didn't want to look at his code before because I didn't want his code to
>> affect my refactoring.
>>
>>
>> Thanks,
>> Jingjing
>>
>>
>> On Sat, Sep 21, 2013 at 9:14 PM, Carl Eastlund <cce at ccs.neu.edu> wrote:
>>
>>> Looking forward to to your followup!
>>>
>>> Carl Eastlund
>>>
>>> P.S. copying to the mailing list so everyone's in the loop.
>>>
>>> On Sat, Sep 21, 2013 at 8:25 PM, Jingjing Duan <duanjingjing at gmail.com>wrote:
>>>
>>>> Hi Carl,
>>>>
>>>> Thanks for your great feedback. Let me try to rewrite the code, this
>>>> time by following the recipes from HTDP. Will send out another email once
>>>> I'm ready!
>>>>
>>>> Thanks,
>>>> Jingjing
>>>>
>>>>
>>>> On Sat, Sep 21, 2013 at 10:25 AM, Carl Eastlund <cce at ccs.neu.edu>wrote:
>>>>
>>>>> On Sat, Sep 21, 2013 at 12:09 PM, Jingjing Duan <
>>>>> duanjingjing at gmail.com> wrote:
>>>>>
>>>>>> Hi,
>>>>>>
>>>>>> I've been reading HTDP and I'm about half way through. To apply what
>>>>>> I've learned in the book to a bigger exercise, I decided to write a boggle
>>>>>> solver.
>>>>>>
>>>>>> You can find the code here:
>>>>>> https://github.com/jduan/boggle_scheme/blob/master/boggle.rkt
>>>>>>
>>>>>> Any feedback is greatly appreciated. I'm specifically looking for
>>>>>> feedback on:
>>>>>>
>>>>>> 1. Did I break the problem into right components?
>>>>>> 2. How can I make the code more idiomatic?
>>>>>>
>>>>>
>>>>> If you're halfway through HtDP, you should know the value of data
>>>>> definitions, contracts, and test cases.  I don't see any of those in your
>>>>> program.  That makes it very hard to tell what's going on in the code, and
>>>>> whether it's doing the right thing.  Adding them after the fact should
>>>>> improve your code's readability.  Adding them earlier -- during the design
>>>>> process of the code itself -- helps break things down into components in a
>>>>> natural way.
>>>>>
>>>>>
>>>>>> 3. Why is code so slow? It can take minutes to solve a 4 by 4 board.
>>>>>> The same board can be solved by a ruby program I wrote in much less time,
>>>>>> like a few seconds. I know recursive functions are a big reason but is
>>>>>> there anything?
>>>>>>
>>>>>
>>>>> "Recursive functions" have nothing to do with the kind of slowdown
>>>>> you're seeing.  Your program is simply doing too much work.  Start adding
>>>>> simple test cases for your functions and you may start to get a clearer
>>>>> idea of where a lot of the work is being done.  The process of adding test
>>>>> cases may also suggest simpler ways to structure your program, both in
>>>>> terms of making it more idiomatic and in terms of doing less work.
>>>>>
>>>>> You might get a lot out of restarting this boggle exercise from the
>>>>> top down, starting with the function find-all-words and going through the
>>>>> design recipe step by step.  You may be surprised how different the result
>>>>> is from what you've written, and how much more natural the solution you get
>>>>> is.  In my own experience, it is also a much quicker process than taking
>>>>> something written as a whole without the design steps, and trying to add
>>>>> them in after the fact.
>>>>>
>>>>> However you proceed, please feel free to share your results and any
>>>>> other questions you have with the list.  We love hearing about stuff like
>>>>> this!
>>>>>
>>>>>  Thanks,
>>>>>> Jingjing
>>>>>>
>>>>>
>>>>> No problem.  Glad to see you're interested in HtDP and Racket!  Good
>>>>> luck!
>>>>>
>>>>> --Carl
>>>>>
>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130924/2965e194/attachment-0001.html>