Velocity Reviews > Ruby > Calculating single-digit summands

# Calculating single-digit summands

draq
Guest
Posts: n/a

 12-11-2005
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/so...ro-part-i.html

Christer Nilsson
Guest
Posts: n/a

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

How is the data entered?

Christer

--
Posted via http://www.ruby-forum.com/.

Christer Nilsson
Guest
Posts: n/a

 12-12-2005
http://www.kakuro.net/

--
Posted via http://www.ruby-forum.com/.

draq
Guest
Posts: n/a

 12-12-2005
This is a newer algorithm which works much more faster.

def sum (arr)
# sorry James Edward Gray 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

draq
Guest
Posts: n/a

 12-12-2005
Corrections:

# 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

draq

James Edward Gray II
Guest
Posts: n/a

 12-12-2005
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 Gray 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.

James Edward Gray II

Kenneth Collins
Guest
Posts: n/a

 12-12-2005
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 Quiz.

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) }
}

--
Posted via http://www.ruby-forum.com/.

Christer Nilsson
Guest
Posts: n/a

 12-12-2005
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(.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

--
Posted via http://www.ruby-forum.com/.

draq
Guest
Posts: n/a

 12-13-2005
I see, there is much to learn. )

draq

draq
Guest
Posts: n/a

 12-13-2005
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/so...-part-iii.html
Hopefully it's now better understandable.

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post draq Ruby 3 12-12-2005 03:18 AM BagelBoy MCSE 4 11-04-2005 04:35 PM Sparky Arbuckle ASP .Net 6 03-06-2005 11:27 PM Asad ASP .Net 2 04-27-2004 06:20 AM Jeffrey Kusters MCSE 2 10-05-2003 01:47 PM

Advertisments