From: "Glen F. Pankow" <Glen.F.Pankow@...>
Date: 2007-06-18T20:33:03+09:00
Subject: Re: [QUIZ] Verbal Arithmetic (#128)

#! /usr/bin/env ruby
#
#  quiz-128  --  Ruby Quiz #128  --  Verbal Arithmetic.
#
#  Usage:  quiz-128 [ -v ] '<equation string>'
#     or:  quiz-128 [ -v ] <addend> <addend> [ <addend> ... ] <sum>
#
#  See the Ruby Quiz #128 documentation for more information
#  (http://www.rubyquiz.com/quiz128.html).
#
#  Glen Pankow      06/17/07        Original version.
#
#  Licensed under the Ruby License.
#
#-----------------------------------------------------------------------------
#
#  I take a slightly different approach to this quiz:  I build up code that
#  kinda-sorta models addition as taught in U.S. elementary schools (taking
#  into account the various constraints of the problem), then eval it.
#
#  And instead of generating permutations of unassigned digits and using
#  recursion for backtracking, I have a single array of digits that is used
#  sort of as a mask (nil entries mark assigned digits) and use Ruby's
#  wonderful magic iterator facility to scan through it.
#
#  $ uname -srmpio
#  Linux 2.6.9-55.ELsmp i686 i686 i386 GNU/Linux
#
#  $ time ./quiz-128 'send + more = money'
#  d = 7, e = 5, y = 2, n = 6, r = 8, o = 0, s = 9, m = 1
#      1   0   1   1
#        s:9 e:5 n:6 d:7
#  +     m:1 o:0 r:8 e:5
#  ---------------------
#    m:1 o:0 n:6 e:5 y:2
#  0.065u 0.003s 0:00.07 85.7%     0+0k 0+0io 0pf+0w
#
#  $ time ./quiz-128 forty ten ten sixty
#  y = 6, n = 0, t = 8, e = 5, r = 7, x = 4, o = 9, i = 1, f = 2, s = 3
#      1   2   1   0
#    f:2 o:9 r:7 t:8 y:6
#            t:8 e:5 n:0
#  +         t:8 e:5 n:0
#  ---------------------
#    s:3 i:1 x:4 t:8 y:6
#  0.029u 0.002s 0:00.03 66.6%     0+0k 0+0io 0pf+0w
#
#  $ time ./quiz-128 eat+that=apple
#  t = 9, e = 8, a = 1, l = 3, h = 2, p = 0
#      1   1   0   1
#            e:8 a:1 t:9
#  +     t:9 h:2 a:1 t:9
#  ---------------------
#    a:1 p:0 p:0 l:3 e:8
#  0.008u 0.002s 0:00.01 0.0%      0+0k 0+0io 0pf+0w
#
#  $ time ./quiz-128 ruby rubber baby buggy bumper
#  y = 0, r = 7, b = 8, e = 1, g = 4, u = 2, a = 3, p = 9, m = 6
#  ...
#  y = 0, r = 7, b = 8, e = 5, g = 4, u = 2, a = 3, p = 9, m = 6
#      1   2   1   2   0
#            r:7 u:2 b:8 y:0
#    r:7 u:2 b:8 b:8 e:5 r:7
#            b:8 a:3 b:8 y:0
#  +     b:8 u:2 g:4 g:4 y:0
#  -------------------------
#    b:8 u:2 m:6 p:9 e:5 r:7
#  0.120u 0.002s 0:00.13 92.3%     0+0k 0+0io 0pf+0w
#


class Array

    #
    # For each non-nil element of the current array, (destructively) set it to
    # nil (i.e., 'marking' it), yield the original value (to the assumed block),
    # and restore it back to what it originally was (i.e., 'unmarking' it).
    #
    # For example, the code:
    #    array = [ 0, nil, 2, 3 ]
    #    p "before: array = #{array.inspect}"
    #    array.unmarkeds { |elem| p "elem = #{elem}, array = #{array.inspect}" }
    #    p "after: array = #{array.inspect}"
    # would print:
    #    before: array = [0, nil, 2, 3]
    #    elem = 0, array = [nil, nil, 2, 3]
    #    elem = 2, array = [0, nil, nil, 3]
    #    elem = 3, array = [0, nil, 2, nil]
    #    after: array = [0, nil, 2, 3]
    #
    def unmarkeds
        (0...size).each do |i|
            next if (at(i).nil?)
            elem = at(i)  ;  self[i] = nil
            yield elem
            self[i] = elem
        end
    end

    #
    # If the <i>-th element of the current array is nil, do nothing.  Otherwise
    # (destructively) set it to nil (i.e., 'marking' it), yield (to the assumed
    # block), and restore it back to what it originally was (i.e., 'unmarking'
    # it).  This is basically the guts of unmarkeds(), and is provided for safe
    # manual element marking.
    #
    def if_unmarked(i)
        return if (at(i).nil?)
        elem = at(i)  ;  self[i] = nil
        yield
        self[i] = elem
    end

    #
    # Note:  typically one might say 'yield elem, self' in these methods, but
    # I don't need them for this application due to Ruby's scoping mechanism.
    #
end


#
# Process the command-line arguments of addend strings and the sum string.
#
verbose = false
addend_strs = [ ]
ARGV.each do |arg|
    if (arg == '-v')
        verbose = true
    else
        arg.split(/[\s+=]+/).each { |term| addend_strs << term }
    end
end
addend_strs = [ 'send', 'more', 'money' ] if (addend_strs.empty?)
sum_str = addend_strs.pop

#
# Split the strings up into their component letters; create some (ugly) code to
# eventually print out a nice table of the addition.
#
table_print_code = 'print " '
(sum_str.length - 1).downto(1) do |i|
    table_print_code << "   \#{carry#{i}}"
end
table_print_code << "\\n\"\n"
addends = [ ]
first_letters = { }
(0...addend_strs.size).each do |i|
    addend_str = addend_strs[i]
    addend_chars = addend_str.split(//).reverse
    addends << addend_chars
    first_letters[addend_chars[-1]] = 1
    table_print_code \
      << 'print "' << ((i < addend_strs.size - 1)? ' ' : '+') \
      << '    ' * (sum_str.length - addend_str.length) \
      << addend_str.gsub(/([a-z])/, ' \1:#{\1}') << "\\n\"\n"
end
table_print_code \
  << 'print "-' << ('----' * sum_str.length) << "\\n\"\n" \
  << 'print " ' << sum_str.gsub(/([a-z])/, ' \1:#{\1}') << "\\n\"\n"
sum_chars = sum_str.split(//).reverse
first_letters[sum_chars[-1]] = 1

#
# Build the addition code.
#
# This, too, is quite ugly and I don't bother to document it, as printing out
# the generated code will probably give one a better idea of how it works than
# my usual verbose documentation (i.e., run this script with -v).
#
seen_chars = { }
code_head = "rem_digs = (0..9).to_a\n"
code_tail = ''
answer_print_code = 'print "'
indent = ''
(0...sum_chars.size).each do |col|
    sum_char = sum_chars[col]
    col_sum_code = "#{indent}carry#{col+1}, #{sum_char} = (carry#{col}"
    addends.inject([ ]) { |dc, addend| dc << addend[col] }.each do |dig_char|
        next if (dig_char.nil?)
        if (seen_chars[dig_char].nil?)
            code_head << "#{indent}rem_digs.unmarkeds do |#{dig_char}|\n"
            code_tail[0,0] = "#{indent}end\n"
            indent << '   '
            seen_chars[dig_char] = 1
            code_head << "#{indent}next if (#{dig_char} == 0)  # leading 0?\n" \
              if (first_letters.has_key?(dig_char))
            col_sum_code[0,0] = '   '   # fix indentation
            answer_print_code << ", #{dig_char} = \#{#{dig_char}}"
        end
        col_sum_code << " + #{dig_char}"
    end
    col_sum_code << ").divmod(10)\n"
    col_sum_code.sub!(/\(carry0 \+ /, '(')
    if (seen_chars[sum_char].nil?)
        code_head << col_sum_code
        code_head << "#{indent}next if (#{sum_char} == 0)  # leading 0?\n" \
          if (first_letters.has_key?(sum_char))
        code_head << "#{indent}rem_digs.if_unmarked(#{sum_char}) do\n"
        code_tail[0,0] = "#{indent}end\n"
        indent << '   '
        seen_chars[sum_char] = 1
        answer_print_code << ", #{sum_char} = \#{#{sum_char}}"
    else
        col_sum_code.sub!(/ = /, '2 = ')
        code_head \
          << col_sum_code \
          << "#{indent}next unless (#{sum_char}2 == #{sum_char})  # inconsistent?\n"
    end
end
answer_print_code.sub!(/\", /, '"\n')
answer_print_code << "\\n\"\n"

#
# And print out the code (if verbose) and run it!
#
code = code_head + answer_print_code + table_print_code + code_tail
print code, "\n" if (verbose)
eval(code)