From: Krishna Dole <dontfall@...>
Date: 2007-01-28T23:46:32+09:00
Subject: Re: [QUIZ] Counting Toothpicks (#111)

Well, here's my solution. (http://pastie.caboo.se/36233)

I leaned heavily on #prime_division, so my solution can be a little
slow for numbers larger than 10^5. I'm not confident that I have a
globally optimal algorithm.

This quiz was quite hard for me, and I spent an unseemly amount of time on it.

Krishna

----------------------------------------------

require 'mathn'

# Combines 2s and 3s into 4s and 6s, which are more toothpick-efficient.
# Takes a 'prime division' argument such as [[2,3], [3,2]], which it
# would return as [[3,1], [4,1], [6,1]]. The primes must be in order.
def merge_primes(pd)
  if pd[0] && pd[0][0] == 2
    if pd[0][1] > 1
      pd << [4, (pd[0][1] / 2).to_i] # for some bizarre reason i have
to call to_i here to avoid a fraction
      pd[0][1] = pd[0][1] % 2
    end
    if pd[1] && pd[1][0] == 3 && pd[0][1] == 1
      pd << [6, 1]
      pd[1][1] -= 1
      pd[0][1] -= 1
    end
  end
  pd.reject{|e| e[1] == 0}
end

# Expects an array of 'prime division'-like objects
def to_toothpicks(ar)
  ar.map { |pd|
    pd.map {|e| Array.new(e[1]){|i| "|" * e[0]}}.join("x")
  }.join "+"
end


# Expects an array of 'prime division'-like objects
def cost(ar)
  c = 0
  for pd in ar
    for i, n in pd
      c += i*n + n*2
    end
  end
  c -= 2
end

# Returns an array of 'prime division'-like objects
def best_toothpicks(i)
  options = []
  rem = 0

  if i < 8 || i == 11
    options <<  [[[i, 1]]]
  else
    while true
      ar = i.prime_division
      option = [merge_primes(ar)]
      option += best_toothpicks(rem) if rem > 0
      options << option

      # this is something i'm not happy about. larger numbers (7)
improve performance,
      # but i'm afraid smaller ones (3) may find better solutions
      if ar.detect {|e| e.first > 5 }
        i -= 1
        rem += 1
      else
        break
      end
    end
  end
  return options.min {|a, b| cost(a) <=> cost(b) }
end

i = ARGV[0].to_i
puts to_toothpicks(best_toothpicks(i))

----------------------------------------------

On 1/26/07, Ruby Quiz <james@grayproductions.net> wrote:
> 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.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>
> This quiz was adapted from an ACM programming challenge at the suggestion of
> Gavin Kistner.
>
> Simple math can be done with toothpicks alone.  Positive integers are just a
> count of toothpicks so three becomes |||.  We can use two toothpicks together to
> build a plus sign (+) or even tilt those slightly to get a multiplication
> operator (x).  Putting all of that together, the expression ||x||||+| is another
> way to express the number nine.
>
> This weeks quiz is to write a program that takes a single command-line argument
> which will be a positive integer.  Your code should build a toothpick expression
> to calculate the number using as few toothpicks as possible.  For example:
>
>         $ruby toothpick.rb 9
>         |||x||| = 9 (8 toothpicks)
>
> Don't forget to count those operators!
>
> Posting toothpick expressions and/or counts for a given number is not spoiler
> material.
>
>