q.rb

require 'pp'

OPS = [ '+', '-', '*', '/' ]

def generate_combos(n, &block)
  n_len = n.length
  chars = n_to_chars_with_pads(n)

  OPS[0..0].each_index do |ops_i|
    transform(chars, n_len, 0, ops_i, &block)
  end
end

def transform(chars, n_len, i, ops_i, &block)
  tchars = chars.dup
  tchars[(i * 2) + 1] = OPS[ops_i]

  yield(tchars)

  while i < (n_len - 2)
    i += 1
    transform(tchars, n_len, i, ops_i, &block)

    other_ops = OPS - [ OPS[ops_i] ]
    other_ops.each_index do |oops_i|
      transform(tchars, n_len, i, oops_i, &block)
    end
  end
end

def n_to_chars_with_pads(n)
  chars = [ ]

  (0...n.length).each do |i|
    chars << n[i]
    if i < (n.length - 1)
      chars << nil
    end
  end

  chars
end

def group_tchars(tchars)
  tchars = tchars.compact
  grouped = [ ]

  i = 0
  numbers = [ ]
  loop do
    if OPS.include?(tchars[i])
      grouped << '%s.0' % numbers.join
      grouped << tchars[i]
      numbers.clear
    else
      numbers << tchars[i]
    end

    if i < tchars.length
      i += 1
    else
      if numbers.count > 0
        grouped << '%s.0' % numbers.join
      end
      break
    end
  end

  grouped
end

def compute_leaf(grouped)
  return 0 if grouped.empty?

  i = 0
  left = nil

  loop do
    val = nil

    case grouped[i]
    when '*'
      right = grouped[i + 1]
      unless right.nil?
        val = left * right.to_f
      end

      i += 2
    when '/'
      right = grouped[i + 1]
      unless right.nil?
        val = left / right.to_f
      end

      i += 2
    when nil
      val = left
      i += 1
    else
      val = grouped[i].to_f
      i += 1
    end

    left = val unless val.nil?
    break if i >= grouped.count
  end

  #puts '%s: %s' % [ grouped.join, left ]

  left
end

def compute_grouped(grouped)
  return 0 if grouped.empty?

  #puts grouped.join

  i = grouped.count - 1
  right = nil

  loop do
    val = nil

    case grouped[i]
    when '+', '-'
      if i > 0
        sub_g = grouped[0...i]
        comp = compute_grouped(sub_g)

        if grouped[i] == '+'
          #puts '%s + %s' % [ sub_g.join, right ]
          val = comp + right
        elsif grouped[i] == '-'
          #puts '%s - %s' % [ sub_g.join, right ]
          val = comp - right
        end
      end

      i = -1
    when '*', '/'
      n = i

      if i > 0
        while(n > 0)
          if [ '+', '-' ].include?(grouped[n])
            n += 1
            break
          else
            n -= 1
          end
        end

        sub_g = grouped[n...i]
        comp = compute_leaf(sub_g)

        if grouped[i] == '*'
          #puts '%s * %s' % [ sub_g.join, right ]
          val = comp * right
        elsif grouped[i] == '/'
          #puts '%s - %s' % [ sub_g.join, right ]
          val = comp / right
        end
      end

      i = n - 1
    when nil
      val = right
      i -= 1
    else
      val = grouped[i].to_f
      i -= 1
    end

    right = val unless val.nil?
    break if i < 0
  end

  #puts '%s: %s' % [ grouped.join, right ]

  right
end

$match = 27182.0
$input = '314159265358'
$matched = [ ]

wheel = [ "\\", '|', '/', '-' ]

i = 0
generate_combos($input) do |c|
  grouped = group_tchars(c)
  result = compute_grouped(grouped)

  if result == $match
    puts '** %d: %s = %f' % [ i, grouped.join, result ]
    $matched << grouped
  else
    print "\b" if i > 0
    print '%s' % wheel[i % 4]
  end

  i += 1
end

pp $matched