Solver for the "Find odd-ball from a group of balls using a balance" problem

gistfile1.coffee

_ = require("underscore")

# State represents aggregate information we've learned about the set of balls.
# in the beginning, all of them are unknown. if they are on the heavier side of
# the balance, they become heavier or lighter if they're on the lighter side.
# if we've ruled them out as not the odd-ball, they become regular.
class State
  constructor: (@unknown = 0, @heavier = 0, @lighter = 0, @regular = 0) ->
  toString: -> [@unknown, @heavier, @lighter, @regular].toString()
  size: -> @unknown + @heavier + @lighter + @regular
  dup: -> new State(@unknown, @heavier, @lighter, @regular)

# eachGroup generates every possible two group combination where the groups are
# of equal size. these are the groups we put on the balance to see if we learn
# something.
#
# it's a simple twist on the basic combination generating recursive funtion.
# callback is called with the resulting groups on every other pick so that the
# groups are always the same size.
eachGroup = (initial, callback) ->
  fn = (left, right, rest, picked = 0) ->
    if picked % 2 == 0
      # if the callback returns true, we return early to skip further checks
      if callback(left, right, rest)
        return true

    for key, count of rest
      if count > 0

        left[key] += 1
        rest[key] -= 1

        # recurse and switch out the sides so that the other one gets a ball added next
        if fn(right, left, rest, picked + 1)
          return true

        left[key] -= 1
        rest[key] += 1

    return false

  fn(new State(), new State(), _.clone(initial))

# test the selections of balls by returning three new possible states
balance = (left, right, rest) ->
  states = []

  if left.size() != right.size() or left.size() == 0
    return states

  left_heavier_than_right = (left, right, rest) ->
    state = new State()
    state.regular += rest.size() # all rest balls become regular
    state.regular += left.regular + right.regular # regulars don't change
    state.regular += right.heavier # heavier on the right side become regular
    state.heavier += left.heavier # heavier on the left just stay as heavier
    state.regular += left.lighter # lighter on the left become regular
    state.lighter += right.lighter # lighter on the right stay lighter
    state.heavier += left.unknown # unknowns on the left become heavier
    state.lighter += right.unknown # unknowns on the right become lighter
    return state

  both_sides_balanced = (left, right, rest) ->
    state = rest.dup()
    state.regular += left.size() # both sides on the scale are regular balls
    state.regular += right.size()
    return state

  # 1. left is heavier than right
  states.push(left_heavier_than_right(left, right, rest))
  # 2. right is heavier than left
  states.push(left_heavier_than_right(right, left, rest))

  # 3. both sides are balanced - only possible if there are unknowns in the rest
  if rest.unknown > 0 or rest.heavier > 0 or rest.lighter > 0
    states.push(both_sides_balanced(left, right, rest))

  return states

# check if we can tell which one is the odd ball. we're basically done when all
# but one are known to be regular.
checkFinal = (state) ->
  state.regular == state.size() - 1 or state.regular == state.size()

checks = 0
# the main recursive function that starts out with a state and puts every possible
# group combination on the balance to see if it solves the puzzle.
solve = (state = new State(10), tries_remaining = 3) ->
  if tries_remaining > 0
    tries_remaining -= 1
  else
    return false

  eachGroup state, (left, right, rest) ->
    checks += 1
    states = balance(left, right, rest)

    if states.length > 0
      # return true if all of the states we got from the balance function above are
      # known to be final.
      if _.every states, checkFinal
        return true
      # othersise, return true if all of the states themselves can be solved using
      # this same function. this is where we recurse however many times necessary.
      else if _.every(states, (state) -> solve(state, tries_remaining))
        # this can sometimes prematurely print that it was solved if the program gets
        # lucky with one of the child states when the others would fail. ultimately,
        # we can learn the first correct move by looking at this output where
        # tries_remaining is the largest value.
        console.log "solved in child state (#{tries_remaining})", left.toString(), right.toString(), "rest", rest.toString(), "state", state.toString()
        return true

# run the solve function and print the total number of groups tested. a lot of them
# will actually be similar, so this can be sped up using some sort of caching mechanism.
console.log "final", solve(), "tried", checks