From: Erwin Abbott <erwin.abbott@...>
Date: 2007-04-11T10:55:07+09:00
Subject: [QUIZ] Counting to 100 (#119)

It would be really interesting to write a non-recursive permute
function that could map a number n to each permutation of digits, and
map n+1 to the next permutation.  Then we could just count from 1 to
6561 for 9 digits, 1 to 19683 for 10 digits, etc.  Something like
this:
  permutation(1, 1..9) => [1, 2, 3, 4, 5, 6, 7, 8, 9]
  permutation(6549, 1..9) => [123456, 78, 9]
  permutation(6560, 1..9) => [123456, 789]

This is easy when we're permuting a single number (it's just
converting to another base), but it might not be possible in this
problem.  I guess the recursive method really only goes 9 or 10 level
deep anyway.

#!/usr/bin/env ruby

# return all combinations of numbers using @digits
def permute digits, progress=[], results=[]
  # last used digit
  last = progress.last ? digits.index(progress.last % 10) : -1

  # this permutation is all done
  return results << progress if last+1 == digits.size

  remaining = digits[last+1 .. -1]
  remaining.size.times do |b|
    # if the last digit used was 1, we'll try these as the next number;
    #   2, 23, 234, 2345, ..., 23456789

    num = remaining[0..b].join.to_i
    permute digits, progress+[num], results
  end

  results
end

# all permutations of n operations, ops
def operations ops, n, progress=[], results=[]
  # done when we've got n operation is progress array
  return results << progress if progress.size == n

  ops.each{|o| operations ops, n, progress+[o], results }
  results # modified by method call
end

# return expr string and value, give set of numbers and corresponding ops
def compute numbers, ops
  e = numbers.zip(ops).flatten.map{|n| n.to_s}.join ' ' # make a string
  v = eval(e)                                           # evaluate it
  ["#{e}= #{v}", v]
end

def target value, digits=(1..9).to_a, ops=[:+, :-]
  # note: only digits 0 - 9 work, because of % 10 math in permute method

  stars        = '*'*76 + "\n"
  count        = 0
  cache        = {}
  permutations = permute digits

  permutations.each do |nums|
    # cache permutations of nums.size-1 operations
    opers = cache[nums.size-1] ||
           (cache[nums.size-1] = operations(ops, nums.size-1))

    opers.each do |o|
      count += 1
      expr, val = compute(nums, o)

      if val != value
        puts expr
      else
        puts stars + expr << "\n" << stars
      end

    end
  end

  puts "#{count} possible equations tested"
end

if $0 == __FILE__
    target 100, (1..9).to_a, [:+, :-]
end