1346 Puzzle Solution with Amb

1346.coffee

# Puzzle solution
# Using the numbers [1, 3, 4, 6] and operations [+, -, *, /],
# find an expression that equals 24.
# Use each number exactly once.
# The puzzle is fun! Don't read this until you've solved it.
# Uses amb, the (super cool) ambiguity operator. (Explained below)

# Print in continuation passing style.
# A continuation (k) is basically a word a callback.
# It's the function that represents what to do next.
# In languages that really support continuations,
# control never returns from a continuation.
print = (msg, k) ->
  console.log msg
  k()

panic = (msg) ->
  if msg == undefined
    console.log "panic"
  else
    console.log "panic #{msg}"
  return

# Dump the stack.
# Gotta do this once in a while to not overrun the stack.
breathe = (k) -> setTimeout k, 0

rest = (xs) -> xs[1..]

# ambiguity operator
# "Takes on the value" of any of the choices.
# choices - Values to try.
# bail    - Function to call when all choices are exhausted.
# k       - Computation to run. Passed (value, fail)
#           Where `fail` is a function to call to backtrack.
#           Backtracking means calling `k` again with the next choice.
amb = (choices, bail, k) ->
  # set bail to default panic function
  unless bail
    bail = -> panic "amb ran out of choices #{choices}"

  # bail up and out when exhausted choices
  unless choices.length
    bail()
    return

  k choices[0], ->
    # what to do if that didn't work out
    amb (rest choices), bail, k

# Check that each number appears only once
check_nums = (nums, fail, k) ->
  if (new Set(nums)).size == 4
    k()
  else
    fail()

# Get all combos of 4 numbers and 3 ops.
# Ambiguously.
# Cals (k nums4, ops3, fail)
get_setup = (nums, ops, fail, k) ->
  amb nums, fail, (x, fail) ->
    amb nums, fail, (y, fail) ->
      amb nums, fail, (z, fail) ->
        amb nums, fail, (w, fail) ->
          amb ops, fail, (op1, fail) ->
            amb ops, fail, (op2, fail) ->
              amb ops, fail, (op3, fail) ->
                check_nums [x, y, z, w], fail, ->
                  k [x, y, z, w], [op1, op2, op3], fail

# Check that the expression evaluates to 24
check_expr = (expr, fail, k) ->
  sum = eval(expr)
  console.log "#{sum} = #{expr}"
  if sum == 24
    k expr, sum
  else
    fail()

# Check an ordering of numbers and ops.
# Tries both tree structures.
check = (nums4, ops3, fail, k) ->
  amb ['left', 'right'], fail, (swi, fail) ->
    if swi == 'left'
      expr = "(#{nums4[0]} #{ops3[0]} #{nums4[1]}) #{ops3[1]} (#{nums4[2]} #{ops3[2]} #{nums4[3]})"
      check_expr expr, fail, k
    else if swi == 'right'
      expr = "#{nums4[0]} #{ops3[0]} (#{nums4[1]} #{ops3[1]} (#{nums4[2]} #{ops3[2]} #{nums4[3]}))"
      check_expr expr, fail, k
    else
      panic "impossible"

solve_problem = (k) ->
  nums = [1,3,4,6]
  ops = ['+', '-', '*', '/']
  get_setup nums, ops, null, (nums4, ops3, fail) ->
    # now we're ready to make one attempt
    breathe ->
      check nums4, ops3, fail, k

main = ->
  solve_problem (expr, sum) ->
    print "GOT IT: #{sum} = #{expr}", ->

do main