Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > Calculating single-digit summands

Reply
Thread Tools

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

 
Reply With Quote
 
 
 
 
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/.


 
Reply With Quote
 
 
 
 
Christer Nilsson
Guest
Posts: n/a
 
      12-12-2005
http://www.kakuro.net/

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


 
Reply With Quote
 
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

 
Reply With Quote
 
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

 
Reply With Quote
 
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


 
Reply With Quote
 
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/.


 
Reply With Quote
 
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/.


 
Reply With Quote
 
draq
Guest
Posts: n/a
 
      12-13-2005
I see, there is much to learn. )

draq

 
Reply With Quote
 
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.

 
Reply With Quote
 
 
 
Reply

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 Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Calculating single-digit summands draq Ruby 3 12-12-2005 03:18 AM
Calculating subnet hosts BagelBoy MCSE 4 11-04-2005 04:35 PM
Calculating a Subtotal for Shopping Cart Sparky Arbuckle ASP .Net 6 03-06-2005 11:27 PM
Calculating number of seconds given two times Asad ASP .Net 2 04-27-2004 06:20 AM
Calculating max. number of subnets RFC950 or RFC1878 Jeffrey Kusters MCSE 2 10-05-2003 01:47 PM



Advertisments