[plt-scheme] toy code for doing a ruby-quiz problem (countdown). Also some problems with HASH-TABLE-GET.

From: Danny Yoo (dyoo at hkn.eecs.berkeley.edu)
Date: Mon Jan 29 09:34:53 EST 2007

Hi everyone,

I thought it might be fun to try doing one of the Ruby Quiz problems at:

     http://rubyquiz.com/quiz7.html


I had fun with this and wanted to share my solution here with the plt 
list:

     http://hashcollision.org/svn/repos/projects/plt-misc/countdown.ss

It makes use of structs, hashtables, and Jens's nice 'evector' library 
from PLaneT.


Here's what it does:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> (require "countdown.ss")
> (parameterize ([debug-on? #t])
     (expr->string (gen-expr 42 '(1 2 3 4 5))))
current-best: 1 = 1.0
current-best: 2 = 2.0
current-best: 3 = 3.0
current-best: 4 = 4.0
current-best: 5 = 5.0
current-best: (1 + 5) = 6.0
current-best: (2 * 4) = 8.0
current-best: (2 * 5) = 10.0
current-best: (3 * 4) = 12.0
current-best: (3 * 5) = 15.0
current-best: (4 * 5) = 20.0
current-best: (1 + (4 * 5)) = 21.0
current-best: (2 + (4 * 5)) = 22.0
current-best: (2 * (4 * 5)) = 40.0
current-best: ((3 + 4) * (1 + 5)) = 42.0
"((3 + 4) * (1 + 5))"
>
> (expr->string (gen-expr 43 '(1 2 3 4 5)))
"(((3 * 5) * (4 - 1)) - 2)"
> (expr->string (gen-expr 44 '(1 2 3 4 5)))
"(((4 + 5) * (2 + 3)) - 1)"
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

That's what it does when it behaves.



However, I am seeing some occasional weirdness that I haven't been able to 
trace completely yet.  Concretely, the result here:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
dyoo at dyoo-desktop:~/work/plt-misc$ mzscheme
Welcome to MzScheme v369.6 [3m], Copyright (c) 2004-2007 PLT Scheme Inc.
> (require "countdown.ss")
> (expr->string (gen-expr 42 '(1 2 3 4 5)))
"((3 + 4) * (1 + 5))"
> (expr->string (gen-expr 76 '(1 2 3 4 5)))
"(1 + ((3 * 5) * (1 + 4)))"
> (does-not-reuse-nums? (gen-expr 76 '(1 2 3 4 5)))
#t
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

is wrong: the algorithm should be able to know that it's not supposed to 
reuse the number '4' here.  So the result there is bizarre: somehow, 
another instance of a NUM is being constructed, but I've taken pains to 
only instantiate NUMs in a single place.

I've been staring at my own definitions for a while and see what's flawed; 
whatever it is, it's darn persistent.  *grin*


Anyway, I thought this might be interesting to folks.  Best of wishes!


Posted on the users mailing list.