bilbo.rb

STDOUT.sync = true # DO NOT REMOVE
# Auto-generated code below aims at helping you parse
# the standard input according to the problem statement.

class String
  def next_chunk
      /^(.+)\1/.match self do |m|
        whole = m[0]
        part = m[0].scan(/^(.+?)\1/).first.first
        nb = whole.length / part.length
        self.slice!(0..(part.length * nb - 1))
        return { value: part, occurs: nb }
      end
      s = self.slice!(0)
      return nil if s.nil?
      return { value: s, occurs: 1 }
  end
end

module Utils
  def letter_for(n)
    return ' ' if n == 0
    ('A'.ord + n - 1).chr
  end
  def number_for(v)
    return 0 if v == ' '
    v = v.upcase.chars.collect{|l| l.ord - 'A'.ord + 1}
    return v.first if v.length == 1
    v
  end
  def compute_distance(a, b, max)
    delta = (b - a) % max
    sign = delta<=>0
    return 0 if delta == 0
    delta -= (sign * max) unless (0..max/2).cover? delta.abs
    delta
  end
end

class Machine
  include Utils

  MEMORY_SIZE = 30
  VALUES_SIZE = 27

  attr_reader :output
  attr_reader :pointer
  attr_reader :memory

  def program
    @program.join
  end

  def matching_opening_bracket
    seek_cursor = @cursor
    brackets = 0
    while seek_cursor >= 0
      current_token = @program[seek_cursor]
      brackets -= 1 if current_token == '['
      brackets += 1 if current_token == ']'
      return seek_cursor if brackets == 0
      seek_cursor -= 1
    end
  end

  def save(&block)
    token = [
        @memory.collect{|m|m.to_s}.join('|'),
        @pointer, @cursor, @program.join('|'),
        @output.join('|'), @ignore, @brackets,
        @i_nb, @allocated.collect{|a|a.to_s}.join('|')
    ]
    return token unless block_given?
    yield
    restore token
  end

  def restore(save)
    @memory = save[0].split('|').collect{|a| a.to_i}
    @pointer = save[1].to_i
    @cursor = save[2].to_i
    @program = save[3].split('|')
    @output = save[4].split('|')
    @ignore = save[5]
    @brackets = save[6].to_i
    @i_nb = save[7].to_i
    @allocated = save[8].split('|').collect{|a| a.to_i}
  end

  def initialize
    @memory = Array.new(MEMORY_SIZE, 0)
    @pointer = 0
    @cursor = 0
    @i_nb = 0
    @program = []
    @output = []
    @ignore = false
    @brackets = 0
    @allocated = []
  end

  def is_alloc?(slot)
    @allocated.include? slot
  end

  def alloc(ptr, size)
    to_alloc = (ptr..(ptr + size - 1)).to_a
    raise 'Allocation error' unless (to_alloc & @allocated).empty?
    @allocated.concat to_alloc
    ptr
  end

  def find(v)
    return find_word(letter_for v) if (v.is_a? Fixnum)
    return find_word(v) if v.is_a?(String)
  end

  def best_place_for(v, options = {})
    v = number_for v if v.is_a? String
    m = @memory
    results = []
    m.each_with_index do |mi, i|
      unless is_alloc? i
        to_reach = compute_distance(self.current_pointer, i, Machine::MEMORY_SIZE).abs
        to_change = compute_distance(mi, v, Machine::VALUES_SIZE).abs
        results << {score: to_reach + to_change, loc: i}
      end
    end
    results.min{|a,b| a[:score]<=>b[:score]}[:loc]
  end

  def current_value
    @memory[pointer]
  end
  def current_value=(value)
    return if @ignore
    @memory[pointer] = (value % VALUES_SIZE)
  end
  def current_pointer=(v)
    return if @ignore
    @pointer = (v % MEMORY_SIZE)
  end
  def current_pointer
    @pointer
  end
  def plus
    self.current_value += 1
  end
  def minus
    self.current_value -= 1
  end
  def loop_start
    @brackets += 1
    if self.current_value == 0
      @ignore = true
    end
  end
  def loop_end
    @brackets -= 1
    if @ignore == true && @brackets == 0
      @ignore = false
    end
    if self.current_value != 0
      loc = matching_opening_bracket
      @cursor = loc
    end
  end
  def left
    self.current_pointer -= 1
  end
  def right
    self.current_pointer += 1
  end
  def validate
    @output << (letter_for current_value)
  end
  def execute(byte_code)
    raise 'need string' unless byte_code.is_a? String
    @program.concat byte_code.split(//)
    while @cursor < @program.length
      case @program[@cursor]
        when '+' then plus
        when '-' then minus
        when '>' then right
        when '<' then left
        when '.' then validate
        when '[' then loop_start
        when ']' then loop_end
      end
      @i_nb += 1
      @cursor += 1
    end
  end

  private

  def find_word(word)
    @memory.collect{|e|letter_for e}.join.index(word)
  end
end

class Compiler < Machine
  alias_method :eat, :execute

  def move(addr)
    delta = compute_distance(current_pointer, addr, MEMORY_SIZE)
    eat delta.abs.times.collect{((delta<=>0) > 0) ? '>' : '<'}.join
  end

  def start_loop
    eat '['
  end

  def flush
    eat '.'
  end

  def count_up
    eat '+'
  end

  def count_down
    eat '-'
  end

  def end_loop
    eat ']'
  end

  def repeat(word, n)
    repeat_whole(word, n)
    return
    whole, distinct = 0
    save do
      repeat_distinct word, n
      distinct = program.length
    end
    save do
      repeat_whole word, n
      whole = program.length
    end
    whole < distinct ? repeat_whole(word, n) : repeat_distinct(word, n)
  end

  def repeat_distinct(word, n)
    if n == 1
      store word
    else
      n_ptr = current_pointer - 1
      word_ptr = current_pointer
      store word.chars.to_a.uniq.join, at: word_ptr
      store n, at: n_ptr
      start_loop
      word.chars.to_a.each do |c|
        move find(c)
        flush
      end
      move n_ptr
      count_down
      end_loop
    end
  end

  def repeat_whole(word, n)
    if n == 1
      store word
    else
      n_ptr = current_pointer - 1
      word_ptr = current_pointer
      store word, at: word_ptr, validate: true
      store (n - 1), at: n_ptr
      start_loop
      move (find(word) || store(word, at: word_ptr))
      (word.length - 1).times { eat '.>' }
      eat '.'
      move n_ptr
      count_down
      end_loop
    end
  end

  def store(values, options = {})
    ptr = current_pointer
    if values.is_a? String
      values = values.chars.collect{|letter| number_for letter}
    elsif values.is_a? Fixnum
      values = [values]
    elsif values.is_a? Array
      values = values.collect{|v| v.is_a?(String) ? number_for(v) : v}
    else
      raise "Argument not ok #{values.inspect}"
    end
    start_ptr = options[:at] || current_pointer
    if options[:alloc]
      alloc start_ptr, values.length
    end
    values.each_with_index do |value, i|
      if start_ptr == :best
        move best_place_for value
      elsif start_ptr.is_a? Fixnum
        move start_ptr + i
      end
      raise "Cannot store this value #{value}, overflow." unless (0..VALUES_SIZE-1).cover? value
      delta = compute_distance(current_value, value, VALUES_SIZE)
      eat delta.abs.times.collect{((delta<=>0) > 0) ? '+' : '-'}.join
      eat '.' if options[:validate]
      #eat '>' if i < (values.length - 1) && !options[:in_place]
    end
    ptr
  end
end

phrase = gets.chomp
#phrase = 'FIFOFIFOFIFOFIFOFIFOFIFOFIFOFIFOFIFOFIFOFIFOFIFO FUM FUM FUM FUM FUM FUM FUM FUM FUM FUM FUM FUM FUM FUM FUM'
c = Compiler.new

until phrase.empty?
  chunk = phrase.next_chunk
  if chunk[:occurs] == 1
    c.store chunk[:value], at: :best, validate: true
  else
    c.repeat chunk[:value], chunk[:occurs]
  end
end

puts c.program

#m = Machine.new
#m.execute '++++>->-------.>+.>-------.>+.<<<<[[>.>.>.>.<<<<-]<[->+<]>]'
#puts m.output.join