Forum: Ruby Calculating single-digit summands

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
D5f8e0711f7a954e2ff14cb11a452aab?d=identicon&s=25 draq (Guest)
on 2005-12-11 23:00
(Received via mailing list)
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
Af95bdaf87958c40150b813e94381bfd?d=identicon&s=25 Christer Nilsson (christer)
on 2005-12-12 01:54
Would you like to add some asserts, so I can figure out the
specification?

How is the data entered?

Christer
Af95bdaf87958c40150b813e94381bfd?d=identicon&s=25 Christer Nilsson (christer)
on 2005-12-12 01:59
D5f8e0711f7a954e2ff14cb11a452aab?d=identicon&s=25 draq (Guest)
on 2005-12-12 18:06
(Received via mailing list)
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
1fba4539b6cafe2e60a2916fa184fc2f?d=identicon&s=25 unknown (Guest)
on 2005-12-12 18:12
(Received via mailing list)
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
dblack@wobblini.net

"Ruby for Rails", forthcoming from Manning Publications, April 2006!
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2005-12-12 19:46
(Received via mailing list)
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
Ce1f4ad22c0f38122258eb8f4c1cd5a5?d=identicon&s=25 Kenneth Collins (kcollins)
on 2005-12-12 20:08
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) }
}
Af95bdaf87958c40150b813e94381bfd?d=identicon&s=25 Christer Nilsson (christer)
on 2005-12-12 20:22
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
D5f8e0711f7a954e2ff14cb11a452aab?d=identicon&s=25 draq (Guest)
on 2005-12-13 17:23
(Received via mailing list)
I see, there is much to learn. ;-))

draq
D5f8e0711f7a954e2ff14cb11a452aab?d=identicon&s=25 draq (Guest)
on 2005-12-13 18:24
(Received via mailing list)
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-p...
Hopefully it's now better understandable.
Af95bdaf87958c40150b813e94381bfd?d=identicon&s=25 Christer Nilsson (christer)
on 2005-12-13 18:27
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-p...
> 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
This topic is locked and can not be replied to.