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