[QUIZ] Verbal Arithmetic (#128)

Discussion in 'Ruby' started by Ruby Quiz, Jun 15, 2007.

  1. Ruby Quiz

    Ruby Quiz Guest

    The three rules of Ruby Quiz:

    1. Please do not post any solutions or spoiler discussion for this quiz until
    48 hours have passed from the time on this message.

    2. Support Ruby Quiz by submitting ideas as often as you can:

    http://www.rubyquiz.com/

    3. Enjoy!

    Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
    on Ruby Talk follow the discussion. Please reply to the original quiz message,
    if you can.

    -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    A famous set of computer problems involve verbal arithmetic. In these problems,
    you are given equations of words like:

    send
    + more
    ------
    money

    or:

    forty
    ten
    + ten
    -------
    sixty

    The goal is to find a single digit for each letter that makes the equation true.
    Normal rules of number construction apply, so the first digit of a multi-digit
    number should be nonzero and each letter represents a different digit.

    This week's quiz is to build a program that reads in equations and outputs
    solutions. You can decide how complex of an equation you want to support, with
    the examples above being the minimum implementation.

    Here's a solution you can test against:

    $ ruby verbal_arithmetic.rb 'send+more=money'
    s: 9
    e: 5
    n: 6
    d: 7
    m: 1
    o: 0
    r: 8
    y: 2
    Ruby Quiz, Jun 15, 2007
    #1
    1. Advertising

  2. Ruby Quiz

    anansi Guest

    I really don't get it :) How did you figured out that 2 = y in your example?




    > Here's a solution you can test against:
    >
    > $ ruby verbal_arithmetic.rb 'send+more=money'
    > s: 9
    > e: 5
    > n: 6
    > d: 7
    > m: 1
    > o: 0
    > r: 8
    > y: 2
    >



    --
    greets

    one must still have chaos in oneself to be able to
    give birth to a dancing star
    anansi, Jun 15, 2007
    #2
    1. Advertising

  3. On Jun 15, 2007, at 7:55 AM, anansi wrote:

    > I really don't get it :) How did you figured out that 2 = y in your
    > example?


    Well, a non-clever way is to try an exhaustive search of each digit
    for each letter.

    James Edward Gray II
    James Edward Gray II, Jun 15, 2007
    #3
  4. Ruby Quiz

    anansi Guest

    ohh I totally misunderstood the task here.. I thought the input would be
    send+more and my app should give money as answer trough calculation..

    James Edward Gray II wrote:
    > On Jun 15, 2007, at 7:55 AM, anansi wrote:
    >
    >> I really don't get it :) How did you figured out that 2 = y in your
    >> example?

    >
    > Well, a non-clever way is to try an exhaustive search of each digit for
    > each letter.
    >
    > James Edward Gray II
    >



    --
    greets

    one must still have chaos in oneself to be able to
    give birth to a dancing star
    anansi, Jun 15, 2007
    #4
  5. Ruby Quiz

    Sammy Larbi Guest

    anansi wrote, On 6/15/2007 8:10 AM:
    > ohh I totally misunderstood the task here.. I thought the input would
    > be send+more and my app should give money as answer trough calculation..
    >


    For perhaps a reason to change the wording, that's what I thought as
    well until I read the explanation to anansi's question.

    Sam


    > James Edward Gray II wrote:
    >> On Jun 15, 2007, at 7:55 AM, anansi wrote:
    >>
    >>> I really don't get it :) How did you figured out that 2 = y in your
    >>> example?

    >>
    >> Well, a non-clever way is to try an exhaustive search of each digit
    >> for each letter.
    >>
    >> James Edward Gray II
    >>

    >
    >
    Sammy Larbi, Jun 15, 2007
    #5
  6. On Jun 15, 2007, at 8:17 AM, Sammy Larbi wrote:

    > anansi wrote, On 6/15/2007 8:10 AM:
    >> ohh I totally misunderstood the task here.. I thought the input
    >> would be send+more and my app should give money as answer trough
    >> calculation..
    >>

    >
    > For perhaps a reason to change the wording, that's what I thought
    > as well until I read the explanation to anansi's question.


    Sorry for the confusion folks. You get both sides of the equation
    and are expected to fine the digit to represent each letter.

    James Edward Gray II
    James Edward Gray II, Jun 15, 2007
    #6
  7. Ruby Quiz

    Robert Dober Guest

    Hmm maybe this helps to clarify (for emacs users) the problem is like
    mpuzz :) (mpuz?)

    Robert

    --
    You see things; and you say Why?
    But I dream things that never were; and I say Why not?
    -- George Bernard Shaw
    Robert Dober, Jun 15, 2007
    #7
  8. Ruby Quiz

    Warren Brown Guest

    Jason,

    > So your task is to find the key.


    Just think of these as a cryptogram with numbers instead of letters.

    - Warren Brown
    Warren Brown, Jun 15, 2007
    #8
  9. [QUIZ][SOLUTION] Verbal Arithmetic (#128)

    --Boundary-00=_AOWdGcXhV+5KlxB
    Content-Type: Multipart/Mixed;
    boundary="Boundary-00=_AOWdGcXhV+5KlxB"

    --Boundary-00=_AOWdGcXhV+5KlxB
    Content-Type: text/plain;
    charset="utf-8"
    Content-Transfer-Encoding: 7bit
    Content-Disposition: inline

    My solution works with addition and multiplication of any sized list of words,
    and subtraction of a list of exactly two words. Its also a fair bit faster
    than brute force. Unfortunately it got pretty messy, and after some rough
    debugging I'm not in the mood to clean it up just now.

    I came up with the basic idea by noticing that the equations can be built
    up and checked from simpler equations taken from the right-hand side. Er..
    lemme give an example to explain better:

    9567
    + 1085
    ------
    10652

    Start off by looking for ways to satisfy:
    7
    + 5
    ---
    2

    Then move further to the left:

    67
    + 85
    ----
    152

    The 52 is right, but not the 1. For addition and multiplication, we can just
    take it mod 100, and if that works then its a possible partial solution.
    For subtraction of two numbers, though, it doesn't work when it goes negative.
    The trick in that case is to just mod the left-most digit:

    9567
    - 1085
    ------
    8482

    7
    - 5
    ---
    2 OK

    67
    - 85
    ----
    -22 => 82 (-2 mod 10 = 8)

    verbal_arithmetic.rb contains (old, ugly) code for generating permutations
    and combinations. So the program works from right-to-left, finding partial
    solutions that work by going through ways of mapping letters to numbers,
    and for each one trying to move further left. Basically a depth-first search.

    There are a number of other subteties, but like I said, I'm tired of messing
    with this now, so I'll leave it there. Ask if you must.

    Examples:

    $ time ./verbal_arithmetic.rb 'send more' + money
    Found mapping:
    m: 1
    y: 2
    n: 6
    o: 0
    d: 7
    e: 5
    r: 8
    s: 9

    real 0m1.074s
    user 0m0.993s
    sys 0m0.019s

    $ ./verbal_arithmetic.rb 'forty ten ten' + sixty
    Found mapping:
    x: 4
    y: 6
    n: 0
    o: 9
    e: 5
    f: 2
    r: 7
    s: 3
    t: 8
    i: 1

    $ ./verbal_arithmetic.rb 'foo bar' - 'zag'
    Found mapping:
    a: 0
    b: 3
    z: 4
    o: 1
    f: 7
    r: 9
    g: 2

    $ ./verbal_arithmetic.rb 'fo ba' \* 'wag'
    Found mapping:
    w: 4
    a: 2
    b: 1
    o: 5
    f: 3
    g: 0


    --
    Jesse Merriman

    http://www.jessemerriman.com/

    --Boundary-00=_AOWdGcXhV+5KlxB
    Content-Type: application/x-ruby;
    name="perms_and_combs.rb"
    Content-Transfer-Encoding: 7bit
    Content-Disposition: attachment;
    filename="perms_and_combs.rb"

    # Ruby Quiz 128: Verbal Arithmetic
    # perms_and_combs.rb

    # Add methods for generating permutations and combinations of Arrays. There's
    # a lot of ugliness here - its a copy-paste-slightly-modify job of a bunch of
    # old ugly code.
    class Array
    # Get the first r-combination of the elements in this Array.
    def first_combination r
    return nil if r < 1 or size < r
    first_combo = Array.new r
    (0...r).each { |i| first_combo = self }
    first_combo
    end

    # Get the combination after start_combo of the elements in this Array.
    def next_combination start_combo
    # Create the positions array
    positions = Array.new start_combo.size
    (0...positions.size).each do |i|
    positions = self.index(start_combo) + 1
    end

    # bump up to the next position
    r, n = start_combo.size, self.size
    i = r
    i -= 1 while positions[i-1] == n - r + i
    return nil if i.zero?

    positions[i-1] = positions[i-1] + 1
    ((i+1)..r).each do |j|
    positions[j-1] = positions[i-1] + j - i
    end

    # translate the next position back into a combination
    next_combo = Array.new r
    (0...next_combo.size).each do |i|
    next_combo = self[positions - 1]
    end
    next_combo
    end

    # Yields every r-combination of the elements in this Array.
    def each_combination r
    combo = first_combination r
    while not combo.nil?
    yield combo
    combo = next_combination combo
    end
    end

    # Swap the elements at the two given positions.
    def swap! i, j
    self, self[j] = self[j], self
    end

    # Generates all permutations of this Array, yielding each one.
    # Based on: http://www.geocities.com/permute_it/
    # This does not generate them in lexicographic order, but it is fairly quick.
    def each_permutation
    # This is pretty ugly..
    a, p, i = self.clone, (0..self.size).to_a, 0
    while i < self.size
    p -= 1
    (i % 2) == 1 ? j = p : j = 0
    a.swap! i, j
    yield a
    i = 1
    while p.zero?
    p = i
    i += 1
    end
    end
    end
    end

    --Boundary-00=_AOWdGcXhV+5KlxB
    Content-Type: application/x-ruby;
    name="verbal_arithmetic.rb"
    Content-Transfer-Encoding: 7bit
    Content-Disposition: attachment;
    filename="verbal_arithmetic.rb"

    #!/usr/bin/env ruby
    # Ruby Quiz 128: Verbal Arithmetic
    # verbal_arithmetic.rb

    require 'perms_and_combs.rb'
    require 'set'

    class VerbalArithmetic
    # Create a new VerbalArithmetic.
    # - words: an array of words
    # - op: a string representation of an operation ('+', '-', or '*')
    # - result: desired result
    # - base: numeric base
    def initialize words, op, result, base = 10
    @words, @op, @result, @base = words, Ops[op], result, base
    @first_letters = Set[ *(words.map { |w| w[0..0] } + [result[0..0]]) ]
    @max_level = (words + [result]).max { |x,y| x.length <=> y.length}.length
    self
    end

    # Returns a hash of letter => number.
    def decode level = 1, partial_mapping = {}
    words_chunk, result_chunk = right_chunk level

    each_valid_mapping(words_chunk, result_chunk, partial_mapping) do |mapping|
    if level == @max_level
    if operate_on_words(words_chunk, mapping) ==
    translate(@result, mapping) and
    not @first_letters.map{ |c| mapping[c]}.include?(0)
    return mapping
    end
    else
    d = decode(level + 1, mapping)
    return d if not d.nil?
    end
    end
    end

    private

    Ops = { '+' => lambda { |x,y| x+y },
    '-' => lambda { |x,y| x-y },
    '*' => lambda { |x,y| x*y } }

    # Yield each valid mapping.
    def each_valid_mapping words, result, partial_mapping = {}
    level = words.first.size

    each_mapping(words + [result], partial_mapping) do |mapping|
    if adjust(operate_on_words(words, mapping), level) ==
    adjust(translate(result, mapping), level)
    yield mapping
    end
    end
    end

    def operate_on_words words, mapping
    nums = []
    words.each { |word| nums << translate(word, mapping) }
    operate nums
    end

    # Operate on the given numbers.
    def operate nums
    nums.inject { |memo, n| @op[memo, n] }
    end

    # Convert a word to a number using the given mapping of letters => numbers.
    def translate word, mapping
    t = word.split(//).map { |c| mapping[c] }
    t.map { |n| n.nil? ? 0 : n }.join.to_i(@base)
    end

    # Generate possible ways of mapping the letters in words to numbers.
    # - words: an array of words
    # - determined: a previously-determined partial mapping which is to be filled
    # out the rest of the way
    def each_mapping words, determined = {}
    letters = Set[]
    words.each do |word|
    word.each_byte { |b| letters << b.chr if not determined.has_key?(b.chr) }
    end

    # Find all arrangements of letters.size undetermined numbers and for each
    # match them up with letters.
    pool = (0...@base).to_a - determined.values
    if pool.size.zero? or letters.size.zero?
    yield determined.clone
    else
    pool.each_combination(letters.size) do |comb|
    comb.each_permutation do |perm|
    mapping = determined.clone
    letters.each_with_index { |let, i| mapping[let] = perm }
    yield mapping
    end
    end
    end
    end

    # Return the result of cutting off the left-side of each word in @words and
    # @result, leaving level-length right-side strings. '0' is prepended to
    # too-short strings.
    def right_chunk level
    words_chunk = @words.map { |word| chunk(word, level) }
    res_chunk = chunk(@result, level)
    [words_chunk, res_chunk]
    end

    def chunk word, level
    word.length < level ? word : word[(word.length - level)...word.length]
    end

    # Adjust the intermediate number num. If its positive, return num modulus
    # @base ** level. Else, return the first digit of the number mod @base
    # appended to the rest of the number.
    def adjust num, level
    if num >= 0
    num % (@base ** level)
    else
    s = num.to_s
    s[0..1] = (s[0..1].to_i(@base) % @base).to_s
    s.to_i @base
    end
    end
    end

    # Usage:
    # verbal_arithmetic.rb WORDS OP RESULT [BASE]
    #
    # WORDS: a list of words
    # OP: the operation (either +, -, or *)
    # RESULT: the result of applying OP to all WORDS
    # BASE: the number base to use (default: 10)
    #
    # Examples:
    # verbal_arithmetic.rb 'send more' + money
    # verbal_arithmetic.rb 'forty ten ten' + sixty
    if __FILE__ == $0
    words, op, result = ARGV[0].split(' '), ARGV[1], ARGV[2]
    base = (ARGV[3].nil? ? 10 : ARGV[3].to_i)

    if op == '-' and words.size != 2
    $stderr.puts 'Subtraction of anything but 2 words is not supported.'
    exit 1
    elsif ['+', '*', '-'].include? op
    va = VerbalArithmetic.new words, op, result, base
    mapping = va.decode
    if mapping
    puts 'Found mapping:'
    mapping.each { |c,n| puts " #{c}: #{n}" }
    else
    puts 'No mapping could be found.'
    end
    else
    $stderr.puts "#{op} is not a supported operation."
    exit 1
    end
    end

    --Boundary-00=_AOWdGcXhV+5KlxB--
    --Boundary-00=_AOWdGcXhV+5KlxB--
    Jesse Merriman, Jun 17, 2007
    #9
  10. [QUIZ][SOLUTION] Verbal Arithmetic (#128)

    --Boundary-00=_s1WdG2CAmTEGH1s
    Content-Type: Multipart/Mixed;
    boundary="Boundary-00=_s1WdG2CAmTEGH1s"

    --Boundary-00=_s1WdG2CAmTEGH1s
    Content-Type: text/plain;
    charset="utf-8"
    Content-Transfer-Encoding: 7bit
    Content-Disposition: inline

    [Note: this didn't seem to get through the first time. Apologies if it did.]

    My solution works with addition and multiplication of any sized list of words,
    and subtraction of a list of exactly two words. Its also a fair bit faster
    than brute force. Unfortunately it got pretty messy, and after some rough
    debugging I'm not in the mood to clean it up just now.

    I came up with the basic idea by noticing that the equations can be built
    up and checked from simpler equations taken from the right-hand side. Er..
    lemme give an example to explain better:

    9567
    + 1085
    ------
    10652

    Start off by looking for ways to satisfy:
    7
    + 5
    ---
    2

    Then move further to the left:

    67
    + 85
    ----
    152

    The 52 is right, but not the 1. For addition and multiplication, we can just
    take it mod 100, and if that works then its a possible partial solution.
    For subtraction of two numbers, though, it doesn't work when it goes negative.
    The trick in that case is to just mod the left-most digit:

    9567
    - 1085
    ------
    8482

    7
    - 5
    ---
    2 OK

    67
    - 85
    ----
    -22 => 82 (-2 mod 10 = 8)

    verbal_arithmetic.rb contains (old, ugly) code for generating permutations
    and combinations. So the program works from right-to-left, finding partial
    solutions that work by going through ways of mapping letters to numbers,
    and for each one trying to move further left. Basically a depth-first search.

    There are a number of other subteties, but like I said, I'm tired of messing
    with this now, so I'll leave it there. Ask if you must.

    Examples:

    $ time ./verbal_arithmetic.rb 'send more' + money
    Found mapping:
    m: 1
    y: 2
    n: 6
    o: 0
    d: 7
    e: 5
    r: 8
    s: 9

    real 0m1.074s
    user 0m0.993s
    sys 0m0.019s

    $ ./verbal_arithmetic.rb 'forty ten ten' + sixty
    Found mapping:
    x: 4
    y: 6
    n: 0
    o: 9
    e: 5
    f: 2
    r: 7
    s: 3
    t: 8
    i: 1

    $ ./verbal_arithmetic.rb 'foo bar' - 'zag'
    Found mapping:
    a: 0
    b: 3
    z: 4
    o: 1
    f: 7
    r: 9
    g: 2

    $ ./verbal_arithmetic.rb 'fo ba' \* 'wag'
    Found mapping:
    w: 4
    a: 2
    b: 1
    o: 5
    f: 3
    g: 0


    --
    Jesse Merriman

    http://www.jessemerriman.com/

    --Boundary-00=_s1WdG2CAmTEGH1s
    Content-Type: application/x-ruby;
    name="perms_and_combs.rb"
    Content-Transfer-Encoding: 7bit
    Content-Disposition: attachment;
    filename="perms_and_combs.rb"

    # Ruby Quiz 128: Verbal Arithmetic
    # perms_and_combs.rb

    # Add methods for generating permutations and combinations of Arrays. There's
    # a lot of ugliness here - its a copy-paste-slightly-modify job of a bunch of
    # old ugly code.
    class Array
    # Get the first r-combination of the elements in this Array.
    def first_combination r
    return nil if r < 1 or size < r
    first_combo = Array.new r
    (0...r).each { |i| first_combo = self }
    first_combo
    end

    # Get the combination after start_combo of the elements in this Array.
    def next_combination start_combo
    # Create the positions array
    positions = Array.new start_combo.size
    (0...positions.size).each do |i|
    positions = self.index(start_combo) + 1
    end

    # bump up to the next position
    r, n = start_combo.size, self.size
    i = r
    i -= 1 while positions[i-1] == n - r + i
    return nil if i.zero?

    positions[i-1] = positions[i-1] + 1
    ((i+1)..r).each do |j|
    positions[j-1] = positions[i-1] + j - i
    end

    # translate the next position back into a combination
    next_combo = Array.new r
    (0...next_combo.size).each do |i|
    next_combo = self[positions - 1]
    end
    next_combo
    end

    # Yields every r-combination of the elements in this Array.
    def each_combination r
    combo = first_combination r
    while not combo.nil?
    yield combo
    combo = next_combination combo
    end
    end

    # Swap the elements at the two given positions.
    def swap! i, j
    self, self[j] = self[j], self
    end

    # Generates all permutations of this Array, yielding each one.
    # Based on: http://www.geocities.com/permute_it/
    # This does not generate them in lexicographic order, but it is fairly quick.
    def each_permutation
    # This is pretty ugly..
    a, p, i = self.clone, (0..self.size).to_a, 0
    while i < self.size
    p -= 1
    (i % 2) == 1 ? j = p : j = 0
    a.swap! i, j
    yield a
    i = 1
    while p.zero?
    p = i
    i += 1
    end
    end
    end
    end

    --Boundary-00=_s1WdG2CAmTEGH1s
    Content-Type: application/x-ruby;
    name="verbal_arithmetic.rb"
    Content-Transfer-Encoding: 7bit
    Content-Disposition: attachment;
    filename="verbal_arithmetic.rb"

    #!/usr/bin/env ruby
    # Ruby Quiz 128: Verbal Arithmetic
    # verbal_arithmetic.rb

    require 'perms_and_combs.rb'
    require 'set'

    class VerbalArithmetic
    # Create a new VerbalArithmetic.
    # - words: an array of words
    # - op: a string representation of an operation ('+', '-', or '*')
    # - result: desired result
    # - base: numeric base
    def initialize words, op, result, base = 10
    @words, @op, @result, @base = words, Ops[op], result, base
    @first_letters = Set[ *(words.map { |w| w[0..0] } + [result[0..0]]) ]
    @max_level = (words + [result]).max { |x,y| x.length <=> y.length}.length
    self
    end

    # Returns a hash of letter => number.
    def decode level = 1, partial_mapping = {}
    words_chunk, result_chunk = right_chunk level

    each_valid_mapping(words_chunk, result_chunk, partial_mapping) do |mapping|
    if level == @max_level
    if operate_on_words(words_chunk, mapping) ==
    translate(@result, mapping) and
    not @first_letters.map{ |c| mapping[c]}.include?(0)
    return mapping
    end
    else
    d = decode(level + 1, mapping)
    return d if not d.nil?
    end
    end
    end

    private

    Ops = { '+' => lambda { |x,y| x+y },
    '-' => lambda { |x,y| x-y },
    '*' => lambda { |x,y| x*y } }

    # Yield each valid mapping.
    def each_valid_mapping words, result, partial_mapping = {}
    level = words.first.size

    each_mapping(words + [result], partial_mapping) do |mapping|
    if adjust(operate_on_words(words, mapping), level) ==
    adjust(translate(result, mapping), level)
    yield mapping
    end
    end
    end

    def operate_on_words words, mapping
    nums = []
    words.each { |word| nums << translate(word, mapping) }
    operate nums
    end

    # Operate on the given numbers.
    def operate nums
    nums.inject { |memo, n| @op[memo, n] }
    end

    # Convert a word to a number using the given mapping of letters => numbers.
    def translate word, mapping
    t = word.split(//).map { |c| mapping[c] }
    t.map { |n| n.nil? ? 0 : n }.join.to_i(@base)
    end

    # Generate possible ways of mapping the letters in words to numbers.
    # - words: an array of words
    # - determined: a previously-determined partial mapping which is to be filled
    # out the rest of the way
    def each_mapping words, determined = {}
    letters = Set[]
    words.each do |word|
    word.each_byte { |b| letters << b.chr if not determined.has_key?(b.chr) }
    end

    # Find all arrangements of letters.size undetermined numbers and for each
    # match them up with letters.
    pool = (0...@base).to_a - determined.values
    if pool.size.zero? or letters.size.zero?
    yield determined.clone
    else
    pool.each_combination(letters.size) do |comb|
    comb.each_permutation do |perm|
    mapping = determined.clone
    letters.each_with_index { |let, i| mapping[let] = perm }
    yield mapping
    end
    end
    end
    end

    # Return the result of cutting off the left-side of each word in @words and
    # @result, leaving level-length right-side strings. '0' is prepended to
    # too-short strings.
    def right_chunk level
    words_chunk = @words.map { |word| chunk(word, level) }
    res_chunk = chunk(@result, level)
    [words_chunk, res_chunk]
    end

    def chunk word, level
    word.length < level ? word : word[(word.length - level)...word.length]
    end

    # Adjust the intermediate number num. If its positive, return num modulus
    # @base ** level. Else, return the first digit of the number mod @base
    # appended to the rest of the number.
    def adjust num, level
    if num >= 0
    num % (@base ** level)
    else
    s = num.to_s
    s[0..1] = (s[0..1].to_i(@base) % @base).to_s
    s.to_i @base
    end
    end
    end

    # Usage:
    # verbal_arithmetic.rb WORDS OP RESULT [BASE]
    #
    # WORDS: a list of words
    # OP: the operation (either +, -, or *)
    # RESULT: the result of applying OP to all WORDS
    # BASE: the number base to use (default: 10)
    #
    # Examples:
    # verbal_arithmetic.rb 'send more' + money
    # verbal_arithmetic.rb 'forty ten ten' + sixty
    if __FILE__ == $0
    words, op, result = ARGV[0].split(' '), ARGV[1], ARGV[2]
    base = (ARGV[3].nil? ? 10 : ARGV[3].to_i)

    if op == '-' and words.size != 2
    $stderr.puts 'Subtraction of anything but 2 words is not supported.'
    exit 1
    elsif ['+', '*', '-'].include? op
    va = VerbalArithmetic.new words, op, result, base
    mapping = va.decode
    if mapping
    puts 'Found mapping:'
    mapping.each { |c,n| puts " #{c}: #{n}" }
    else
    puts 'No mapping could be found.'
    end
    else
    $stderr.puts "#{op} is not a supported operation."
    exit 1
    end
    end

    --Boundary-00=_s1WdG2CAmTEGH1s--
    --Boundary-00=_s1WdG2CAmTEGH1s--
    Jesse Merriman, Jun 17, 2007
    #10
  11. Ruby Quiz

    Eric I. Guest

    Re: [SOLUTION] Verbal Arithmetic (#128)

    This program solves addition problems with any number of terms. It
    finds and displays all solutions to the problem.

    The solving process is broken up into a sequence of simple steps all
    derived from class Step. A Step can be something such as 1) choosing
    an available digit for a given letter or 2) summing up a column and
    seeing if the result matches an already-assigned letter. As steps
    succeed the process continues with the following steps. But if a step
    fails (i.e., there's a contradiction) then the system backs up to a
    point where another choice can be made. This is handled by recursing
    through the sequence of steps. In fact, even when a solution is
    found, the program still backtracks to find other solutions.

    The expectation is that by testing for contradictions as early as
    possible in the process we'll tend to avoid dead ends and the result
    will be much better than an exhaustive search.

    For example, here are the steps for a sample equation:

    send
    +more
    -----
    money

    1. Choose a digit for "d".
    2. Choose a digit for "e".
    3. Sum the column using letters "d", "e" (and include carry).
    4. Set the digit for "y" based on last column summed.
    5. Choose a digit for "n".
    6. Choose a digit for "r".
    7. Sum the column using letters "n", "r" (and include carry).
    8. Verify that last column summed matches current digit for "e".
    9. Choose a digit for "o".
    10. Sum the column using letters "e", "o" (and include carry).
    11. Verify that last column summed matches current digit for "n".
    12. Choose a digit for "s".
    13. Verify that "s" has not been assigned to zero.
    14. Choose a digit for "m".
    15. Verify that "m" has not been assigned to zero.
    16. Sum the column using letters "s", "m" (and include carry).
    17. Verify that last column summed matches current digit for "o".
    18. Sum the column using letters (and include carry).
    19. Verify that last column summed matches current digit for "m".
    20. Display a solution (provided carry is zero)!

    Eric
    ----
    Are you interested in on-site Ruby training that's been highly
    reviewed by former students? http://LearnRuby.com

    ====

    # This is a solution to Ruby Quiz #128. As input it takes a "word
    # equation" such as "send+more=money" and determines all possible
    # mappings of letters to digits that yield a correct result.
    #
    # The constraints are: 1) a given digit can only be mapped to a single
    # letter, 2) the first digit in any term cannot be zero.
    #
    # The solving process is broken up into a sequence of simple steps all
    # derived from class Step. A Step can be something such as 1)
    # choosing an available digit for a given letter or 2) summing up a
    # column and seeing if the result matches an already-assigned letter.
    # As steps succeed the process continues with the following steps.
    # But if a step fails (i.e., there's a contradiction) then the system
    # backs up to a point where another choice can be made. This is
    # handled by recursing through the sequence of steps. In fact, even
    # when a solution is found, the program still backtracks to find other
    # solutions.


    require 'set'


    # State represents the stage of a partially solved word equation. It
    # keeps track of what digits letters map to, which digits have not yet
    # been assigned to letters, and the results of the last summed column,
    # including the resulting digit and any carry if there is one.
    class State
    attr_accessor :sum, :carry
    attr_reader :letters

    def initialize()
    @available_digits = Set.new(0..9)
    @letters = Hash.new
    @sum, @carry = 0, 0
    end

    # Return digit for letter.
    def [](letter)
    @letters[letter]
    end

    # The the digit for a letter.
    def []=(letter, digit)
    # if the letter is currently assigned, return its digit to the
    # available set
    @available_digits.add @letters[letter] if @letters[letter]

    @letters[letter] = digit
    @available_digits.delete digit
    end

    # Clear the digit for a letter.
    def clear(letter)
    @available_digits.add @letters[letter]
    @letters[letter] = nil
    end

    # Return the available digits as an array copied from the set.
    def available_digits
    @available_digits.to_a
    end

    # Tests whether a given digit is still available.
    def available?(digit)
    @available_digits.member? digit
    end

    # Receives the total for a column and keeps track of it as the
    # summed-to digit and any carry.
    def column_total=(total)
    @sum = total % 10
    @carry = total / 10
    end
    end


    # Step is an "abstract" base level class from which all the "concrete"
    # steps can be deriveds. It simply handles the storage of the next
    # step in the sequence. Subclasses should provide 1) a to_s method to
    # describe the step being performed and 2) a perform method to
    # actually perform the step.
    class Step
    attr_writer :next_step
    end


    # This step tries assigning each available digit to a given letter and
    # continuing from there.
    class ChooseStep < Step
    def initialize(letter)
    @letter = letter
    end

    def to_s
    "Choose a digit for \"#{@letter}\"."
    end

    def perform(state)
    state.available_digits.each do |v|
    state[@letter] = v
    @next_step.perform(state)
    end
    state.clear(@letter)
    end
    end


    # This step sums up the given letters and changes to state to reflect
    # the sum. Because we may have to backtrack, it stores the previous
    # saved sum and carry for later restoration.
    class SumColumnStep < Step
    def initialize(letters)
    @letters = letters
    end

    def to_s
    list = @letters.map { |l| "\"#{l}\"" }.join(', ')
    "Sum the column using letters #{list} (and include carry)."
    end

    def perform(state)
    # save sum and carry
    saved_sum, saved_carry = state.sum, state.carry

    state.column_total =
    state.carry +
    @letters.inject(0) { |sum, letter| sum + state[letter] }
    @next_step.perform(state)

    # restore sum and carry
    state.sum, state.carry = saved_sum, saved_carry
    end
    end


    # This step determines the digit for a letter given the last column
    # summed. If the digit is not available, then we cannot continue.
    class AssignOnSumStep < Step
    def initialize(letter)
    @letter = letter
    end

    def to_s
    "Set the digit for \"#{@letter}\" based on last column summed."
    end

    def perform(state)
    if state.available? state.sum
    state[@letter] = state.sum
    @next_step.perform(state)
    state.clear(@letter)
    end
    end
    end


    # This step will occur after a column is summed, and the result must
    # match a letter that's already been assigned.
    class CheckOnSumStep < Step
    def initialize(letter)
    @letter = letter
    end

    def to_s
    "Verify that last column summed matches current " +
    "digit for \"#{@letter}\"."
    end

    def perform(state)
    @next_step.perform(state) if state[@letter] == state.sum
    end
    end


    # This step will occur after a letter is assigned to a digit if the
    # letter is not allowed to be a zero, because one or more terms begins
    # with that letter.
    class CheckNotZeroStep < Step
    def initialize(letter)
    @letter = letter
    end

    def to_s
    "Verify that \"#{@letter}\" has not been assigned to zero."
    end

    def perform(state)
    @next_step.perform(state) unless state[@letter] == 0
    end
    end


    # This step represents finishing the equation. The carry must be zero
    # for the perform to have found an actual result, so check that and
    # display a digit -> letter conversion table and dispaly the equation
    # with the digits substituted in for the letters.
    class FinishStep < Step
    def initialize(equation)
    @equation = equation
    end

    def to_s
    "Display a solution (provided carry is zero)!"
    end

    def perform(state)
    # we're supposedly done, so there can't be anything left in carry
    return unless state.carry == 0

    # display a letter to digit table on a single line
    table = state.letters.invert
    puts
    puts table.keys.sort.map { |k| "#{table[k]}=#{k}" }.join(' ')

    # display the equation with digits substituted for the letters
    equation = @equation.dup
    state.letters.each { |k, v| equation.gsub!(k, v.to_s) }
    puts
    puts equation
    end
    end


    # Do a basic test for the command-line arguments validity.
    unless ARGV[0] =~ Regexp.new('^[a-z]+(\+[a-z]+)*=[a-z]+$')
    STDERR.puts "invalid argument"
    exit 1
    end


    # Split the command-line argument into terms and figure out how many
    # columns we're dealing with.
    terms = ARGV[0].split(/\+|=/)
    column_count = terms.map { |e| e.size }.max


    # Build the display of the equation a line at a time. The line
    # containing the final term of the sum has to have room for the plus
    # sign.
    display_columns = [column_count, terms[-2].size + 1].max
    display = []
    terms[0..-3].each do |term|
    display << term.rjust(display_columns)
    end
    display << "+" + terms[-2].rjust(display_columns - 1)
    display << "-" * display_columns
    display << terms[-1].rjust(display_columns)
    display = display.join("\n")
    puts display


    # AssignOnSumStep which letters cannot be zero since they're the first
    # letter of a term.
    nonzero_letters = Set.new
    terms.each { |e| nonzero_letters.add(e[0, 1]) }


    # A place to keep track of which letters have so-far been assigned.
    chosen_letters = Set.new


    # Build up the steps needed to solve the equation.
    steps = []
    column_count.times do |column|
    index = -column - 1
    letters = [] # letters for this column to be added

    terms[0..-2].each do |term| # for each term that's being added...
    letter = term[index, 1]
    next if letter.nil? # skip term if no letter in column
    letters << letter # note that this letter is part of sum

    # if the letter does not have a digit, create a ChooseStep
    unless chosen_letters.member? letter
    steps << ChooseStep.new(letter)
    chosen_letters.add(letter)
    steps << CheckNotZeroStep.new(letter) if
    nonzero_letters.member? letter
    end
    end

    # create a SumColumnStep for the column
    steps << SumColumnStep.new(letters)

    summed_letter = terms[-1][index, 1] # the letter being summed to

    # check whether the summed to letter should already have a digit
    if chosen_letters.member? summed_letter
    # should already have a digit, check that summed digit matches it
    steps << CheckOnSumStep.new(summed_letter)
    else
    # doesn't already have digit, so create a AssignOnSumStep for
    # letter
    steps << AssignOnSumStep.new(summed_letter)
    chosen_letters.add(summed_letter)

    # check whether this letter cannot be zero and if so add a
    # CheckNotZeroStep
    steps << CheckNotZeroStep.new(summed_letter) if
    nonzero_letters.member? summed_letter
    end
    end

    # should be done, so add a FinishStep
    steps << FinishStep.new(display)

    # print out all the steps
    # steps.each_with_index { |step, i| puts "#{i + 1}. #{step}" }

    # let each step know about the one that follows it.
    steps.each_with_index { |step, i| step.next_step = steps[i + 1] }

    # start performing with the first step.
    steps.first.perform(State.new)
    Eric I., Jun 17, 2007
    #11
  12. Here is my solution for Ruby Quiz 128. It's a little rough, but I
    can't afford to spend any more time working on it. One thing I didn't
    have time to do was to provide a user interface. Another thing I
    didn't do was proper commenting. I apologize for the latter.

    I thought a Darwinian search (aka genetic algorithm) would be an
    interesting way to tackle this quiz. I have been looking for a excuse
    to write such a search in Ruby for quite awhile and this seemed to be
    it.

    Here are is the output from one run of my quiz solution:

    <result>
    Solution found after 15 steps
    SEND+MORE=MONEY
    9567+1085=10652

    Solution found after 27 steps
    FORTY+TEN+TEN=SIXTY
    29786+850+850=31486
    </result>

    And here is the code:

    <code>
    #! /usr/bin/env ruby -w
    #
    # solution.rb
    # Quiz 128
    #
    # Created by Morton Goldberg on 2007-06-18.

    # Assumption: equations take the form: term + term + ... term = sum

    ROOT_DIR = File.dirname(__FILE__)
    $LOAD_PATH << File.join(ROOT_DIR, "lib")

    require "cryptarithm"
    require "solver"

    EQUATION_1 = "SEND+MORE=MONEY"
    EQUATION_2 = "FORTY+TEN+TEN=SIXTY"
    POP_SIZE = 400
    FECUNDITY = 2
    STEPS = 50

    Cryptarithm.equation(EQUATION_1)
    s = Solver.new(POP_SIZE, FECUNDITY, STEPS)
    s.run
    puts s.show

    Cryptarithm.equation(EQUATION_2)
    s = Solver.new(POP_SIZE, FECUNDITY, STEPS)
    s.run
    puts s.show
    </code>

    And here are the library classes:

    <code>
    # lib/cryptarithm.rb
    # Quiz 128
    #
    # Created by Morton Goldberg on 2007-06-18.

    DIGITS = (0..9).to_a

    class Cryptarithm
    @@equation = ""
    @@max_rank = -1
    def self.equation(str=nil)
    if str
    @@equation = str.upcase
    lhs, rhs = @@equation.gsub(/[A-Z]/, "9").split("=")
    @@max_rank = [eval(lhs), eval(rhs)].max
    else
    @@equation
    end
    end
    attr_accessor :ranking, :solution
    def initialize
    @solution = @@equation.delete("+-=").split("").uniq
    @solution = @solution.zip((DIGITS.sort_by {rand})[0,
    @solution.size])
    rank
    end
    def mutate(where=rand(@solution.size))
    raise RangeError unless ().include?(where)
    digits = @solution.collect { |pair| pair[1] }
    digits = DIGITS - digits
    return if digits.empty?
    @solution[where][1] = digits[rand(digits.size)]
    end
    def swap
    m = rand(@solution.size)
    n = m
    while n == m
    n = rand(@solution.size)
    end
    @solution[m][1], @solution[n][1] = @solution[n][1], @solution
    [m][1]
    end
    def rank
    sum = @@equation.dup
    solution.each { |chr, num| sum.gsub!(chr, num.to_s) }
    lhs, rhs = sum.split("=")
    terms = lhs.split("+") << rhs
    if terms.any? { |t| t[0] == ?0 }
    @ranking = @@max_rank
    else
    @ranking = eval("#{lhs} - #{rhs}").abs
    end
    end
    def initialize_copy(original)
    @solution = original.solution.collect { |pair| pair.dup }
    end
    def inspect
    [@ranking, @solution].inspect
    end
    def to_s
    sum = @@equation.dup
    solution.each { |chr, num| sum.gsub!(chr, num.to_s) }
    "#{@@equation}\n#{sum}"
    end
    end
    </code>

    <code>
    # lib/solver.rb
    # Quiz 128
    #
    # Created by Morton Goldberg on 2007-06-18.
    #
    # Attempts to a solve cryptarithm puzzle by applying a Darwinian search
    # (aka genetic algorithm). It can thought of as a stochastic breadth-
    first
    # search. Although this method doesn't guarantee a solution will be
    # found, it often finds one quite quickly.

    MUTATION = 0.5
    SWAP = 1.0

    class Solver
    attr_reader :best, :population, :step
    def initialize(pop_size, fecundity, steps)
    @pop_size = pop_size
    @fecundity = fecundity
    @steps = steps
    @mid_step = steps / 2
    @step = 1
    @population = []
    @pop_size.times { @population << Cryptarithm.new }
    select
    end
    def run
    @steps.times do
    replicate
    select
    break if @best.rank.zero?
    @step += 1
    end
    @best
    end
    def replicate
    @pop_size.times do |n|
    crypt = @population[n]
    # mate = crypt
    # while mate.equal?(crypt)
    # mate = @population[rand(@pop_size)]
    # end
    @fecundity.times do
    child = crypt.dup
    child.mutate if crypt.solution.size < 10 && rand <=
    MUTATION
    child.swap if rand <= SWAP
    @population << child
    end
    end
    end
    def select
    @population = @population.sort_by { |crypt| crypt.rank }
    @population = @population[0, @pop_size]
    @best = @population.first
    end
    def show
    if @step > @steps
    "No solution found after #{step} steps"
    else
    "Solution found after #{step} steps\n" + @best.to_s
    end
    end
    end
    </code>

    Regards, Morton
    Morton Goldberg, Jun 18, 2007
    #12
  13. Ruby Quiz

    Eric I. Guest

    Re: Verbal Arithmetic (#128)

    If anyone would like more samples to try their code with, I found the
    following on the web:

    * http://www.gtoal.com/wordgames/alphametic/testscript

    * http://www.gtoal.com/wordgames/alphametic/testscript.out

    The first is a script which poses the problems to their own solving-
    program. The second shows the solutions that their program produces.

    Some of the sample equations have multiple solutions, such as 'eins
    +eins=zwei'. 'united+states=america' has no solutions. And of the
    few that I've tested with my own solution, 'saturn+pluto+uranus
    +neptune=planets' takes the longest to solve.

    Eric
    ----
    Interested in hands-on, on-site Ruby training? See http://LearnRuby.com
    for information about a well-reviewed class.
    Eric I., Jun 18, 2007
    #13
  14. On Jun 17, 2007, at 9:03 AM, Raf Coremans wrote:

    > Here's my solution: http://pastie.caboo.se/71188
    >
    > It's of the dumb-brute-force-slow-as-hell variety:


    Mine was too:

    #!/usr/bin/env ruby -wKU

    EQUATION = ARGV.shift.to_s.downcase.sub("=", "==")
    LETTERS = EQUATION.scan(/[a-z]/).uniq
    CHOICES = LETTERS.inject(Hash.new) do |all, letter|
    all.merge(letter => EQUATION =~ /\b#{letter}/ ? 1..9 : 0..9)
    end

    def search(choices, mapping = Hash.new)
    if choices.empty?
    letters, digits = mapping.to_a.flatten.partition { |e| e.is_a?
    String }
    return mapping if eval(EQUATION.tr(letters.join, digits.join))
    else
    new_choices = choices.dup
    letter = new_choices.keys.first
    digits = new_choices.delete(letter).to_a - mapping.values

    digits.each do |choice|
    if result = search(new_choices, mapping.merge(letter => choice))
    return result
    end
    end

    return nil
    end
    end

    if solution = search(CHOICES)
    LETTERS.each { |letter| puts "#{letter}: #{solution[letter]}" }
    else
    puts "No solution found."
    end

    __END__

    James Edward Gray II
    James Edward Gray II, Jun 19, 2007
    #14
  15. Sorry for the second post, but I just noticed that I pasted a wrong
    (earlier) version of solver.rb into my first post. This is what I
    intended to post.

    The difference between the two versions is minor, but this version
    eliminates some commented-out experimental code and corrects a minor
    bug.

    Sample output:

    <result>
    Solution found after 15 steps
    SEND+MORE=MONEY
    9567+1085=10652

    Solution found after 27 steps
    FORTY+TEN+TEN=SIXTY
    29786+850+850=31486
    </result>

    And here is the corrected code:

    <code>
    #! /usr/bin/env ruby -w
    #
    # solution.rb
    # Quiz 128
    #
    # Created by Morton Goldberg on 2007-06-18.

    # Assumption: equations take the form: term + term + ... term = sum

    ROOT_DIR = File.dirname(__FILE__)
    $LOAD_PATH << File.join(ROOT_DIR, "lib")

    require "cryptarithm"
    require "solver"

    EQUATION_1 = "SEND+MORE=MONEY"
    EQUATION_2 = "FORTY+TEN+TEN=SIXTY"
    POP_SIZE = 400
    FECUNDITY = 2
    STEPS = 50

    Cryptarithm.equation(EQUATION_1)
    s = Solver.new(POP_SIZE, FECUNDITY, STEPS)
    s.run
    puts s.show

    Cryptarithm.equation(EQUATION_2)
    s = Solver.new(POP_SIZE, FECUNDITY, STEPS)
    s.run
    puts s.show
    </code>

    And here are the library classes:

    <code>
    # lib/cryptarithm.rb
    # Quiz 128
    #
    # Created by Morton Goldberg on 2007-06-18.

    DIGITS = (0..9).to_a

    class Cryptarithm
    @@equation = ""
    @@max_rank = -1
    def self.equation(str=nil)
    if str
    @@equation = str.upcase
    lhs, rhs = @@equation.gsub(/[A-Z]/, "9").split("=")
    @@max_rank = [eval(lhs), eval(rhs)].max
    else
    @@equation
    end
    end
    attr_accessor :ranking, :solution
    def initialize
    @solution = @@equation.delete("+-=").split("").uniq
    @solution = @solution.zip((DIGITS.sort_by {rand})[0,
    @solution.size])
    rank
    end
    def mutate(where=rand(@solution.size))
    raise RangeError unless ().include?(where)
    digits = @solution.collect { |pair| pair[1] }
    digits = DIGITS - digits
    return if digits.empty?
    @solution[where][1] = digits[rand(digits.size)]
    end
    def swap
    m = rand(@solution.size)
    n = m
    while n == m
    n = rand(@solution.size)
    end
    @solution[m][1], @solution[n][1] = @solution[n][1], @solution
    [m][1]
    end
    def rank
    sum = @@equation.dup
    solution.each { |chr, num| sum.gsub!(chr, num.to_s) }
    lhs, rhs = sum.split("=")
    terms = lhs.split("+") << rhs
    if terms.any? { |t| t[0] == ?0 }
    @ranking = @@max_rank
    else
    @ranking = eval("#{lhs} - #{rhs}").abs
    end
    end
    def initialize_copy(original)
    @solution = original.solution.collect { |pair| pair.dup }
    rank
    end
    def inspect
    [@ranking, @solution].inspect
    end
    def to_s
    sum = @@equation.dup
    solution.each { |chr, num| sum.gsub!(chr, num.to_s) }
    "#{@@equation}\n#{sum}"
    end
    end
    </code>

    <code>
    # lib/solver.rb
    # Quiz 128
    #
    # Created by Morton Goldberg on 2007-06-18.
    #
    # Attempts to a solve cryptarithm puzzle by applying a Darwinian search
    # (aka genetic algorithm). It can thought of as a stochastic breadth-
    first
    # search. Although this method doesn't guarantee a solution will be
    # found, it often finds one quite quickly.

    MUTATION = 0.5
    SWAP = 1.0

    class Solver
    attr_reader :best, :population, :step
    def initialize(pop_size, fecundity, steps)
    @pop_size = pop_size
    @fecundity = fecundity
    @steps = steps
    @mid_step = steps / 2
    @step = 1
    @population = []
    @pop_size.times { @population << Cryptarithm.new }
    select
    end
    def run
    @steps.times do
    replicate
    select
    break if @best.ranking.zero?
    @step += 1
    end
    @best
    end
    def replicate
    @pop_size.times do |n|
    crypt = @population[n]
    @fecundity.times do
    child = crypt.dup
    child.mutate if crypt.solution.size < 10 && rand <=
    MUTATION
    child.swap if rand <= SWAP
    @population << child
    end
    end
    end
    def select
    @population = @population.sort_by { |crypt| crypt.rank }
    @population = @population[0, @pop_size]
    @best = @population.first
    end
    def show
    if @step > @steps
    "No solution found after #{step} steps"
    else
    "Solution found after #{step} steps\n" + @best.to_s
    end
    end
    end
    </code>

    Regards, Morton
    Morton Goldberg, Jun 19, 2007
    #15
  16. On Jun 18, 4:59 pm, James Edward Gray II <>
    wrote:
    >> It's of the dumb-brute-force-slow-as-hell variety:

    > Mine was too:
    > #!/usr/bin/env ruby -wKU
    >
    > EQUATION = ARGV.shift.to_s.downcase.sub("=", "==")
    > LETTERS = EQUATION.scan(/[a-z]/).uniq
    > CHOICES = LETTERS.inject(Hash.new) do |all, letter|
    > all.merge(letter => EQUATION =~ /\b#{letter}/ ? 1..9 : 0..9)
    > end
    >
    > def search(choices, mapping = Hash.new)
    > if choices.empty?
    > letters, digits = mapping.to_a.flatten.partition { |e| e.is_a?
    > String }
    > return mapping if eval(EQUATION.tr(letters.join, digits.join))
    > else
    > new_choices = choices.dup
    > letter = new_choices.keys.first
    > digits = new_choices.delete(letter).to_a - mapping.values
    >
    > digits.each do |choice|
    > if result = search(new_choices, mapping.merge(letter => choice))
    > return result
    > end
    > end
    >
    > return nil
    > end
    > end
    >
    > if solution = search(CHOICES)
    > LETTERS.each { |letter| puts "#{letter}: #{solution[letter]}" }
    > else
    > puts "No solution found."
    > end
    >
    > __END__
    >


    I really like it - your solution covers any type of expression :).
    Perhaps some preprocessing of CHOICES can save the performance....

    The only thing, assuming that all examples are always integers, I'd add

    ..sub(/([a-z])([^a-z])/,'\1.0\2')

    to EQUATION to cover examples with division (to drop the assumption, before
    adding .0 one can regexp it for '.'s)

    for 'boaogr/foo=bar' (arbitrary example) your code gives

    b: 1
    o: 0
    a: 2
    g: 3
    r: 7
    f: 8

    and modified one corrects it to

    b: 1
    o: 0
    a: 2
    g: 3
    r: 7
    f: 8

    I can expect that this modification may break on rounding errors, but in
    this task domain I do not think it will
    Eugene Kalenkovich, Jun 19, 2007
    #16
  17. On Jun 19, 2007, at 9:30 AM, Eugene Kalenkovich wrote:

    > On Jun 18, 4:59 pm, James Edward Gray II <>
    > wrote:
    >>> It's of the dumb-brute-force-slow-as-hell variety:

    >> Mine was too:
    >> #!/usr/bin/env ruby -wKU
    >>
    >> EQUATION = ARGV.shift.to_s.downcase.sub("=", "==")
    >> LETTERS = EQUATION.scan(/[a-z]/).uniq
    >> CHOICES = LETTERS.inject(Hash.new) do |all, letter|
    >> all.merge(letter => EQUATION =~ /\b#{letter}/ ? 1..9 : 0..9)
    >> end
    >>
    >> def search(choices, mapping = Hash.new)
    >> if choices.empty?
    >> letters, digits = mapping.to_a.flatten.partition { |e| e.is_a?
    >> String }
    >> return mapping if eval(EQUATION.tr(letters.join, digits.join))
    >> else
    >> new_choices = choices.dup
    >> letter = new_choices.keys.first
    >> digits = new_choices.delete(letter).to_a - mapping.values
    >>
    >> digits.each do |choice|
    >> if result = search(new_choices, mapping.merge(letter =>
    >> choice))
    >> return result
    >> end
    >> end
    >>
    >> return nil
    >> end
    >> end
    >>
    >> if solution = search(CHOICES)
    >> LETTERS.each { |letter| puts "#{letter}: #{solution[letter]}" }
    >> else
    >> puts "No solution found."
    >> end
    >>
    >> __END__
    >>

    >
    > I really like it - your solution covers any type of expression :).
    > Perhaps some preprocessing of CHOICES can save the performance....


    Thanks. There have been far more clever submissions though.

    > The only thing, assuming that all examples are always integers, I'd
    > add
    >
    > .sub(/([a-z])([^a-z])/,'\1.0\2')
    >
    > to EQUATION to cover examples with division (to drop the
    > assumption, before
    > adding .0 one can regexp it for '.'s)
    >
    > for 'boaogr/foo=bar' (arbitrary example) your code gives
    >
    > b: 1
    > o: 0
    > a: 2
    > g: 3
    > r: 7
    > f: 8
    >
    > and modified one corrects it to
    >
    > b: 1
    > o: 0
    > a: 2
    > g: 3
    > r: 7
    > f: 8
    >
    > I can expect that this modification may break on rounding errors,
    > but in
    > this task domain I do not think it will


    Good points.

    James Edward Gray II
    James Edward Gray II, Jun 19, 2007
    #17
  18. Ruby Quiz wrote:
    > This week's quiz is to build a program that reads in equations and outputs
    > solutions. You can decide how complex of an equation you want to support, with
    > the examples above being the minimum implementation.
    >


    This solution requires Gecode/R[1] 0.2.0 (need to install Gecode[3,4]
    followed by Gecode/R[2]). Gecode does the actual search, so we just
    specify the constraints. Two important aspects that are used to make the
    solution quick to compute are:

    == Propagation rather than branching (deduction rather than exploration)

    Branching (i.e. testing a guess, i.e. exploring the search space) costs
    since we have to save the old state and start a new one. Rather Gecode
    tries to prune as much of the search space as it can before resorting to
    exploration. In the case of linear constraints (e.g. a + 10*b + c= 10*d
    + e, which corresponds to the problem

    a
    + bc
    ----
    de

    ) it takes each variable and considers the smallest and largest values
    it can possibly take. E.g. if we consider a in the above example we can
    rewrite the linear equation to

    a = 10*(d - b) + e - c

    From that equation we can check how large and small the right hand side
    can be and then remove all other possibilities from the domain of a. We
    can end up pruning quite a lot if we do this for each variable until
    there are no more possibilities left to remove (coupled with the
    distinct constraint).

    In fact when we use this for send+more=money, without doing any sort of
    exploration we can directly reduce the domains of the variables down to

    s=9, e=4..7, n=5..8, d=2..8, m=1, o=0, r=2..8, y=2..8

    So without any guessing at all we already know the value of three
    letters and have pruned the domains of the others (i.e. pruned the
    number of possibilities left, i.e. reduced the search space).

    Since we now have to start exploring the search space we make a guess
    that e=4. Propagating the constraints once again with e given the domain
    4 will directly result in a failure, so we backtrack and now know that
    e!=4. With that information we redo the propagation and directly end up
    at the solution with no need to explore any further. So in total we only
    need to explore 4 out of 9^2*10^6 nodes in the search space.

    == Branching with a good heuristic

    We don't randomly select where to go next in the search space, rather we
    use a fail-first heuristic to try to cut down the search space faster.
    The heuristic is to simply try to fixate a value for the variable with
    the smallest domain. The reason that it works well is that we exhaust
    domains quicker, hence forcing failures quicker (hence fail-first)

    == The code

    require 'rubygems'
    require 'gecoder'

    # Solves verbal arithmetic problems
    # ( http://en.wikipedia.org/wiki/Verbal_arithmetic ). Only supports
    # addition.
    class VerbalArithmetic < Gecode::Model
    # Creates a model for the problem where the left and right hand sides
    # are given as an array with one element per term. The terms are given
    # as strings
    def initialize(lhs_terms, rhs_terms)
    super()

    # Set up the variables needed as a hash mapping the letter to its
    # variable.
    lhs_terms.map!{ |term| term.split(//) }
    rhs_terms.map!{ |term| term.split(//) }
    all_terms = (lhs_terms + rhs_terms)
    unique_letters = all_terms.flatten.uniq
    letter_vars = int_var_array(unique_letters.size, 0..9)
    @letters = Hash[*unique_letters.zip(letter_vars).flatten!]

    # Must satisfy the equation.
    sum_terms(lhs_terms).must == sum_terms(rhs_terms)

    # Must be distinct.
    letter_vars.must_be.distinct

    # Must not begin with a 0.
    all_terms.map{ |term| term.first }.uniq.each do |letter|
    @letters[letter].must_not == 0
    end

    # Select a branching, we go for fail first.
    branch_on letter_vars, :variable => :smallest_size, :value => :min
    end

    def to_s
    @letters.map{ |letter, var| "#{letter}: #{var.val}" }.join("\n")
    end

    private

    # A helper to make the linear equation a bit tidier. Takes an array of
    # variables and computes the linear combination as if the variable
    # were digits in a base 10 number. E.g. x,y,z becomes
    # 100*x + 10*y + z .
    def equation_row(variables)
    variables.inject{ |result, variable| variable + result*10 }
    end

    # Computes the sum of the specified terms (given as an array of arrays
    # of characters).
    def sum_terms(terms)
    rows = terms.map{ |term| equation_row(@letters.values_at(*term)) }
    rows.inject{ |sum, term| sum + term }
    end
    end

    if ARGV.empty?
    abort "Usage: #{$0} '<word_1>+<word_2>+...+<word_n>=<word_res>'"
    end
    lhs, rhs = ARGV[0].split('=').map{ |eq_side| eq_side.split('+') }
    solution = VerbalArithmetic.new(lhs, rhs).solve!
    if solution.nil?
    puts 'Failed'
    else
    puts solution.to_s
    end


    [1] http://gecoder.rubyforge.org/
    [2] http://gecoder.rubyforge.org/installation.html
    [3] http://www.gecode.org/download.html
    [4] http://www.gecode.org/gecode-doc-latest/PageComp.html

    --
    Andreas Launila
    Andreas Launila, Jun 19, 2007
    #18
  19. Andreas Launila wrote:
    > Since we now have to start exploring the search space we make a guess
    > that e=4. Propagating the constraints once again with e given the domain
    > 4 will directly result in a failure, so we backtrack and now know that
    > e!=4. With that information we redo the propagation and directly end up
    > at the solution with no need to explore any further. So in total we only
    > need to explore 4 out of 9^2*10^6 nodes in the search space.
    >


    The last part is probably a bit misleading/incorrect. We are not
    directly exploring the space of all possible assignments when we branch,
    so saying that we have explored 4 nodes in that space is incorrect (i.e.
    we have not just explored 4 possible assignments, but we have visited
    just 4 nodes in our search space).

    --
    Andreas Launila
    Andreas Launila, Jun 19, 2007
    #19
  20. On 6/15/07, Ruby Quiz <> wrote:
    >
    > This week's quiz is to build a program that reads in equations and outputs
    > solutions. You can decide how complex of an equation you want to support, with
    > the examples above being the minimum implementation.
    >


    Here's my solution: http://pastie.caboo.se/72030

    It's a brute-force search, but has reasonable speed. +, -, and *
    operators are supported.
    Bob Showalter, Jun 20, 2007
    #20
    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. joshc
    Replies:
    5
    Views:
    536
    Keith Thompson
    Mar 31, 2005
  2. Eric Sosman

    Re: Integer 128 != Integer 128 ??

    Eric Sosman, Oct 12, 2010, in forum: Java
    Replies:
    6
    Views:
    816
    Screamin Lord Byron
    Oct 13, 2010
  3. chankey pathak

    Re: Integer 128 != Integer 128 ??

    chankey pathak, Oct 13, 2010, in forum: Java
    Replies:
    0
    Views:
    827
    chankey pathak
    Oct 13, 2010
  4. Ruby Quiz
    Replies:
    0
    Views:
    226
    Ruby Quiz
    Jun 21, 2007
  5. Matthew Moss

    [QUIZ] Modular Arithmetic (#179)

    Matthew Moss, Oct 10, 2008, in forum: Ruby
    Replies:
    13
    Views:
    221
    Gregory Brown
    Oct 13, 2008
Loading...

Share This Page