parker-chainfinder2.rb

# WARNING: VERY UGLY CODE AHEAD
# 
# Documentation of sorts:
# This is a library, so you have to require it eg require 'parker-chainfinder2.rb'
# The functions are:
#
# - translate(number)
#   This translates from an integer to its english representation 
#   translate(5) #=> "Five"
#   translate(5352) #=> "Five Thousand Three Hundred Fifty Two"
#
# - count_digits_in(number)
#   Counts the number of characters in the english representation of the integer "number", not including spaces.
#
# - wrap_nwcl(...)
#   old function I forgot to remove, I don't think it's doing anything anymore
#
# - num_with_char_length(len, less_than: nil)
#   Finds the lowest number which, when converted to an english translation using translate(), has a character length of 'len'
#   optionally takes a 'less_than' argument which only searches for integer results less than it.
#   returns false if no number could be found
#
# - nums_with_char_length(len, less_than: nil, &block) 
#   Finds all numbers with a certain character length, like above. Passes each number as it is found to the block.
#
# - max_length_of_num(n)
#   Meant to be used internally. Returns the maximum converted-to-english-character length 
#   of all numbers less than or equal to n. Is usually but not always accurate
#
# - find_chains_from(n, max = 50) Takes a block
#   Find chains! This iterates through every chain whose elements all are less than or equal to 'max'
#   Only yields the longest chains, not subchains. Eg. if it was going to yield [4,9,26] it would not also yield [4,9]

def e(n)
  10**n
end
$number_names = {
  e(63)=> "Vigintillion", # (|)
  e(60)=> "Novendecillion",
  e(57)=> "Octodecillion",
  e(54)=> "Septendecillion",
  e(51)=> "Sexdecillion", # 8===> ({}) 8===> ({}) 8===> ({}) 8===> ({}) 8===> ({}) 8===> ({}) 8===> ({}) 8===> ({}) 8===> ({}) 8===> ({})
  e(48)=> "Quindecillion",
  e(45)=> "Quattuordecillion",
  e(42)=> "Tredecillion",
  e(39)=> "Duodecillion",
  e(36)=> "Undecillion",
  e(33)=> "Decillion",
  e(30)=> "Nonillion",
  e(27)=> "Octillion",
  e(24)=> "Septillion",
  e(21)=> "Sextillion", # 8===> ({})
  e(18)=> "Quintillion",
  e(15)=> "Quadrillion",
  e(12)=> "Trillion",
  e(9)=>  "Billion",
  e(6)=>  "Million",
  1000 => "Thousand",
  100 =>  "Hundred",
  90 =>   "Ninety",
  80 =>   "Eighty",
  70 =>   "Seventy",
  60 =>   "Sixty",
  50 =>   "Fifty",
  40 =>   "Forty",
  30 =>   "Thirty",
  20 =>   "Twenty",
  19 =>   "Nineteen",
  18 =>   "Eighteen",
  17 =>   "Seventeen",
  16 =>   "Sixteen",
  15 =>   "Fifteen",
  14 =>   "Fourteen",
  13 =>   "Thirteen",
  12 =>   "Twelve",
  11 =>   "Eleven",
  10 =>   "Ten",
  9 =>    "Nine",
  8 =>    "Eight",
  7 =>    "Seven",
  6 =>    "Six",
  5 =>    "Five",
  4 =>    "Four",
  3 =>    "Three",
  2 =>    "Two",
  1 =>    "One"
}

$levels = 0
def translate(number)#, use_and: false, count_spaces: false, long_scale: false)
  #puts "  "*$levels + "Translating #{number}"
  if number.is_a? FalseClass
    return "false"
  elsif number == 0
    return "Zero"
  elsif number < 0
    return "Negative " + translate(number.abs)
  end
  res = ""
  $number_names.each do |amount, name|
    if number >= amount
      #puts "  "*$levels + "Divmodding out #{name}"
      divres,number = number.divmod(amount)
      #puts "  "*$levels + "divres: #{divres}, number: #{number}"
      if amount > 90
        $levels += 1
        res << translate(divres)#, use_and: use_and, count_spaces: count_spaces, long_scale: long_scale)
        $levels -= 1
        res << " "
      end
      res << name
      res << " "
    end
  end
  #puts "  "*$levels + "Result is #{res.inspect}"
  return res.strip
end

def count_digits_in(number)
  translate(number).gsub(" ","").length
end

$nwcl = {}
def wrap_nwcl(len, less_than: nil)
  if $debug
    return num_with_char_length(len, less_than: less_than)
  else
    key = [len, less_than].hash
    return $nwcl[key] if $nwcl.include?(key)
    return $nwcl[key] = num_with_char_length(len, less_than: less_than)
  end
end

def num_with_char_length(len, less_than: nil)
  nums_with_char_length(len, less_than: nil) do |n|
    return n
  end
  return false
end

$threedigitdigits = (1..999).map{|n| count_digits_in(n)}

$twodigitdigits = Hash.new{|h,k| h[k] = []}
(1..99).each do |n|
  $twodigitdigits[count_digits_in(n)] << n
end

def max_length_of_num(n) #this is almost always but not always right
  raise ArgumentError, "n must be positive" if n < 0
  return 0 if n == 0
  if n < 1000
    return $threedigitdigits[0...n].max
  else
    res = 0
    $number_names.each do |big,name|
      next if big < 1000
      if n >= big
        res += max_length_of_num([n/big,999].min)
        res += name.length
        res += max_length_of_num([n-big,big-1].min)
        return res
      end
    end
  end
  raise "This code shouldnt get to this point"
end

$nlevels = 0
def nums_with_char_length(len, less_than: nil, &block)
  return enum_for(:nums_with_char_length, len, less_than: nil) if block.nil?
  puts "  "*$nlevels + "Searching for n of length #{len} less than #{less_than.inspect}" if $debug
=begin
  (1..9).each do |n|
    if less_than.nil? || n < less_than
      if $number_names[n].length == len
        puts "  "*$nlevels + "Found #{n} in 1..9 range" if $debug
        return n
      end
    end
  end
  (1..9).map{|n| n*10}.each do |n|
    if less_than.nil || n < less_than
      if $number_names[n].length == len
        puts "  "*$nlevels + "Found #{n} in 10..90 range" if $debug
        return n
      elsif $number_names[n].length+3 <= len
=end
  #[1,3,4,11,13,15,17,21,23,24,73].each do |n|
  #(1..99).each do |n|
  #  next unless less_than.nil? || n < less_than
  #  block.call n if count_digits_in(n) == len
  #end
  $twodigitdigits[len].each do |n|
    block.call n if less_than.nil? || n < less_than
  end
  [100, *(1..21).map{|n| 1000**n}].each do |n|
    if $number_names[n].length+3 <= len and (less_than.nil? || n < less_than)
      next if max_length_of_num(999*n) < len
      puts "  "*$nlevels + "Searching within #{$number_names[n]}" if $debug
      #all the numbers 1...100 which are the smallest to produce that length
      #ie 1 is the smallest number to produce a 3-character word
      smallest_char = if n == 100 #"seventeen hundred" isnt allowed
                        [1,3,4]
                      else
                        [1,3,4,11,13,15,17,21,23,24,
                         73,101,103,104,111,113,115,
                         117,123,124,173,323,373]
                      end
      range =
        if n == 100
          (1..9)
        else
          (1..999)
        end
      range.each do |multiple|
        next if !less_than.nil? && !((multiple * n) < less_than)
        puts "  "*$nlevels + "Searching within #{translate(multiple * n)}" if $debug
        current_length = count_digits_in(multiple * n)
        remaining = len - current_length
        if remaining == 0
          puts "  "*$nlevels + "None remaining, found #{multiple * n}" if $debug
          block.call multiple * n
        end
        sub_less_than = if less_than.nil?
                          n
                        else
                          [n, less_than - n].min
                        end
        $nlevels += 1
        test = nums_with_char_length(remaining, less_than: sub_less_than) do |sub_n|
          res = (multiple*n) + sub_n
          puts "  "*$nlevels + "Found #{res} as a combination of lots" if $debug
          block.call res
        end
        $nlevels -= 1
=begin
        if test
          res = (multiple*n) + test
          puts "  "*$nlevels + "Found #{res} as a combination of lots" if $debug
          block.call res
        end
=end
      end

=begin      
      remaining = len - (n.to_s.length)
      puts "  "*$nlevels + "Trying #{$number_names[n]}, #{remaining} chars remaining"
      max_less_than = (n == 100 ? 10 : 100)
      if less_than.nil?
        sub_less_than = max_less_than
      else
        sub_less_than = [max_less_than, (less_than/n)].min
      end
      $nlevels += 1
      sub_num = num_with_char_length(remaining, less_than: sub_less_than)
      $nlevels -= 1
      if sub_num
        puts "  "*$nlevels + "Found #{sub_num * n} in high range"
        return sub_num * n
      end
=end
    end
  end
  puts "  "*$nlevels + "Search has ended" if $debug
end

def q(n)
  #found = wrap_nwcl(n)
  #res=translate(found)
  #[res.gsub(" ","").length,found,res]
  nums_with_char_length(n) do |found|
    puts "#{found}: #{translate(found)}"
  end
end

def find_chains_from(n, max = 50)
  return enum_for(:find_chains_from, n, max) unless block_given?
  found = false
  nums_with_char_length(n, less_than: max) do |o|
    next if o == n
    found = true
    find_chains_from(o, max) do |chain|
      yield [n] + chain
    end
  end
  yield [n] unless found
end

=begin
n = 3
while (the_num = num_with_char_length(n))
  puts translate(the_num)
  n+=1
end

loop do
  res = num_with_char_length(gets.chomp.to_i)
  if res
    puts translate(res)
  else
    puts 'false'
  end
end
=end