Tuesday, January 13, 2009

Computational Mind Teaser

Via GoogleReader and DZone ... I came across this post yesterday: http://blogs.digitss.com/programming/a-mind-teaser-good-one/

Of course I couldn't pass up the challenge and spent all of my free random moments yesterday afternoon trying things out. I was able to see how the subtract function was easily related to decrement and had several promising ideas on how decrement could work but nothing right. This morning a coworker and I sat down and finished all three in under 30 minutes. I post my solutions here b/c I feel the need to justify the time wasted ;-)


DEC(b) :=
a = 0
loop(b)
b = a++

SUB(a,b) :=
loop(b)
DEC(a)

DIV(a,b) :=
q = 0
loop(a)
SUB(a,b)
c = a
DEC(c)
loop(a)
q++
SUB(q,c)
a = q

* all functions leave the result in the first variable and assume the operator presents itself between the two parameters (e.g. SUB(a,b) == (a=a-b) ... prefix notation)

** I like my DIV better than those posted as of the writing of this article but still feel like it could be shortened / cleaner. I am happy to say that the hack of reducing the second loop to only a single increment while using the loop(0) as the "conditional" to stop working was my idea :-)

The coworker I figured this out with then tried to explain y-combinators in lambda calculus and how they might relate to functional technique he was trying in JavaScript ..... my head hurts ... in a good way.

No comments: