Calculating single-digit summands

Ruby
1

I have tried to make an algorithm that finds all possible combinations
of single-digit summands for a number. After an afternoon of hard and
desperate work I got something inefficient (although it works). Maybe
someone has a better idea. The link to the algorithm:
http://secam.blogspot.com/2005/12/solving-kakuro-part-i.html

2

On 11 Dec 2005 13:53:28 -0800, “draq” [email protected] wrote:

I have tried to make an algorithm that finds all possible combinations
of single-digit summands for a number. After an afternoon of hard and
desperate work I got something inefficient (although it works). Maybe
someone has a better idea. The link to the algorithm:
http://secam.blogspot.com/2005/12/solving-kakuro-part-i.html

I don’t understand the rules of the game from your writeup.

3

On Dec 11, 2005, at 3:57 PM, draq wrote:

I have tried to make an algorithm that finds all possible combinations
of single-digit summands for a number. After an afternoon of hard and
desperate work I got something inefficient (although it works). Maybe
someone has a better idea. The link to the algorithm:
http://secam.blogspot.com/2005/12/solving-kakuro-part-i.html

One thing that your code could really use is better names. Variables
like “arr”, “t”, and even “calc” tell me very little, as I’m trying
to read you code.

Next, there’s a lot more iterators than just each() and using them
can make your code more expressive. Some examples:

def sum (arr)
i = 0
arr.each do |k| i += k end
i
end

… or …

def sum( enum )
inject { |sum, n| sum + n }
end

arrj.each do |a|
arri.delete(a) if sum(a) != number
end

… or …

arrj.delete_if { |a| sum(a) != number }

You can also simplify lines like the following by using destructive
method calls:

arri = arri.uniq

… or …

arri.uniq!

Hope that gives you some ideas.

James Edward G. II

4

Would you like to add some asserts, so I can figure out the
specification?

How is the data entered?

Christer

5

http://www.kakuro.net/

6

Since only single digit summands are under consideration, I don’t think
optimizations are important for this. Here’s a simple brute force
approach that performs reasonably well. It considers all possible
subsets of [1,2,3,4,5,6,7,8,9] and rejects any with the wrong depth or
sum. For this solution I reused the powerset method I wrote for a recent
Ruby Q…

class Array

def sum
inject { |sum,x| sum += x }
end

def powerset
for element_map in 0…(1 << self.length) do
subset = []
each_with_index do |element, index|
subset << element if element_map[index] == 1
end
yield subset
end
end

end

def calc(number, depth)
puts “number = #{number}, depth = #{depth}”
candidates = (1…9).inject([]) { |a,x| a << x }
candidates.powerset { |subset|
next unless subset.length == depth
next unless subset.sum == number
p subset
}
end

examples

(3…5).each { |depth|
(10…20).each { |target| calc(target, depth) }
}

7

draq,

Array mixes in Enumerable, so inject works.

I added some asserts to be able to understand what your code does.
As I can see, this solves only a partial problem: generating all
combinations, given a sum and number of squares. This is calc(sum,
count).
Next step would probably be intersection(sum1, count1, sum2, count2)
between a row and a column, listing the possible combinations.

Curiousity: The list for arr(2) below, was too long. So I decided to cut
it by writing a method for Array. Then I found it’s already defined!
First accepts zero or one argument.

Defining a kakuro, so a program can solve it, seems to be a lot more
hassle than defining a sudoku.

Christer

def sum (arr) arr.inject { |sum,i| sum += i } end

def arr (depth, min=1, max=10-depth,t=[], arr=[])
(min…max).each do |i|
t[depth-1] = i if depth > 0
arr(depth-1, i+1, max+1, t, arr) if depth > 1
arr << t.reverse.clone if depth == 1
end
arr
end

def calc (number, depth)
arri = arr(depth)
arri.each do |a|
arri.delete_if { |a| sum(a) != number }
end
arri
end

require ‘test/unit’
class TestKakuro < Test::Unit::TestCase
def test_all
assert_equal 12, sum([3,4,5])
assert_equal [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6],
[1, 7], [1, 8], [1, 9], [2, 3], [2, 4]],
arr(2).first(10)
assert_equal 9, arr(1).size
assert_equal 36, arr(2).size
assert_equal 84, arr(3).size
assert_equal 126, arr(4).size
assert_equal 126, arr(5).size
assert_equal 84, arr(6).size
assert_equal 36, arr(7).size
assert_equal 9, arr(8).size
assert_equal 1, arr(9).size

assert_equal [[7, 8, 9]], calc(24,3)
assert_equal [[1, 6, 8, 9],[2, 5, 8, 9],
              [2, 6, 7, 9],[3, 4, 8, 9],
              [3, 5, 7, 9],[3, 6, 7, 8],
              [4, 5, 6, 9],[4, 5, 7, 8]], calc(24, 4)
assert_equal [[1, 2, 3, 4, 5, 6, 7, 8, 9]], calc(45, 9)

end
end

8

I see, there is much to learn. ;-))

draq

9

draq wrote:

Hello Christer,

I don’t see the problem. The list of arr(2) seems to be right. The
numbers are [1,2] - [1,3] - [1,4] - [1,5] - [1,6] - [1,7] - [1,8] -
[1,9] - [2,3] - [2,4] - [2,5] - [2,6] - [2,7] - [2,8] - [2,9] - [3,4] -
[3,5] - [3,6] - [3,7] - [3,8] - [3,9] - [4,5] - [4,6] - [4,7] - [4,8] -
[4,9] - [5,6] - [5,7] - [5,8] - [5,9] - [6,7] - [6,8] - [6,9] - [7,8] -
[7,9] - [8,9].

I beg pardon for my lousy comments. I’ve tried to improve. You’ll find
the newest code at
http://secam.blogspot.com/2005/12/solving-kakuro-part-iii.html
Hopefully it’s now better understandable.

draq,

I was using first(10) to keep the output short.
Your code is working. Sorry about being unclear.

christer

10

… or …

def sum( enum )
inject { |sum, n| sum + n }
end

Don’t you need enum. ?

def sum(enum)
enum.inject {|sum,n| sum+n}
end

11

This is a newer algorithm which works much more faster.

def sum (arr)

sorry James Edward G. II, but I’m not using an enum.

i = 0
arr.each do |k| i += k end
i
end

def arr (depth, min=1, max=10-depth,t=[], arr=[])
(min…max).each do |i|
t[depth-1] = i if depth > 0
arr(depth-1, i+1, max+1, t, arr) if depth > 1
arr << t.reverse.clone if depth == 1
end

arr
end

def calc (number, depth)
arri = arr(depth)

arri.each do |a|
arri.delete_if { |a| sum(a) != number }
end

arri
end

examples

calc(24, 3).each do |a| print "#{a} - " end puts
calc(24, 4).each do |a| print "#{a} - " end puts

even summands of 45 can be calculated now. It was impossible with the

older algorithm.
calc(45, 9).each do |a| print "#{a} - " end puts

12

Hello Christer,

I don’t see the problem. The list of arr(2) seems to be right. The
numbers are [1,2] - [1,3] - [1,4] - [1,5] - [1,6] - [1,7] - [1,8] -
[1,9] - [2,3] - [2,4] - [2,5] - [2,6] - [2,7] - [2,8] - [2,9] - [3,4] -
[3,5] - [3,6] - [3,7] - [3,8] - [3,9] - [4,5] - [4,6] - [4,7] - [4,8] -
[4,9] - [5,6] - [5,7] - [5,8] - [5,9] - [6,7] - [6,8] - [6,9] - [7,8] -
[7,9] - [8,9].

I beg pardon for my lousy comments. I’ve tried to improve. You’ll find
the newest code at
http://secam.blogspot.com/2005/12/solving-kakuro-part-iii.html
Hopefully it’s now better understandable.

13

On Dec 12, 2005, at 11:02 AM, draq wrote:

This is a newer algorithm which works much more faster.

def sum (arr)

sorry James Edward G. II, but I’m not using an enum.

You don’t think so? Let’s ask Ruby…

Array.ancestors.find { |par| par.to_s =~ /enum/i }
=> Enumerable

arr = Array.new
=> []

arr.is_a? Enumerable
=> true

arr.respond_to? :inject
=> true

Ruby thinks so. Let’s try a sum:

arr = (1…10).to_a
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

arr.inject { |sum, n| sum + n }
=> 55

Looks good to me.

arri.each do |a|
arri.delete_if { |a| sum(a) != number }
end

The whole point of delete_if() is that you don’t need the each().
Try taking it out. :wink:

James Edward G. II

14

Hi –

On Tue, 13 Dec 2005, draq wrote:

arr << t.reverse.clone if depth == 1

I haven’t been following this thread closely but just an observation:
Array#reverse gives you a new array, so you don’t need to clone it.

David

–
David A. Black
[email protected]

“Ruby for Rails”, forthcoming from Manning Publications, April 2006!