Calculating single-digit summands

Discussion in 'Ruby' started by draq, Dec 11, 2005.

  1. draq

    draq Guest

    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
     
    draq, Dec 11, 2005
    #1
    1. Advertising

  2. 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, Dec 12, 2005
    #2
    1. Advertising

  3. Christer Nilsson, Dec 12, 2005
    #3
  4. draq

    draq Guest

    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, Dec 12, 2005
    #4
  5. draq

    draq Guest

    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
     
    draq, Dec 12, 2005
    #5
  6. 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
     
    James Edward Gray II, Dec 12, 2005
    #6
  7. 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/.
     
    Kenneth Collins, Dec 12, 2005
    #7
  8. 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


    --
    Posted via http://www.ruby-forum.com/.
     
    Christer Nilsson, Dec 12, 2005
    #8
  9. draq

    draq Guest

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

    draq
     
    draq, Dec 13, 2005
    #9
  10. draq

    draq Guest

    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, Dec 13, 2005
    #10
  11. 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

    --
    Posted via http://www.ruby-forum.com/.
     
    Christer Nilsson, Dec 13, 2005
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Fangs
    Replies:
    3
    Views:
    9,801
    darshana
    Oct 26, 2008
  2. Replies:
    2
    Views:
    958
    Martin Honnen
    Apr 12, 2008
  3. draq
    Replies:
    3
    Views:
    96
    James Edward Gray II
    Dec 12, 2005
  4. April
    Replies:
    16
    Views:
    201
    Ted Zlatanov
    Jul 7, 2008
  5. Thomas Andersson
    Replies:
    2
    Views:
    110
    Dr.Ruud
    Aug 14, 2010
Loading...

Share This Page