level5-death.rb

level5-death.rb

INF = 2 ** 20
def turn(k, counter = 0)
  @dp ||= {}
  return nil if k < 1 || k > 255 || counter > 100
  return @dp[k] if @dp[k]
  return @dp[k] = {count: 1, prev: k, action: :D, current: k} if (k % 5) === 0
  t1 = nil
  t2 = turn(k/2, counter + 1)
  t3 = turn(k + 10, counter + 1)
  t4 = turn(k + 20, counter + 1)
  t1 = turn(k - 1, counter + 1) if (k % 2) == 0
  cond = {
    't1' => {
      node: t1, prev: k-1, action: :O
    },
    't2' => {
      node: t2, prev: k/2, action: :K
    },
    't3' => {
      node: t3, prev: k + 10, action: :R
    },
    't4' => {
      node: t4, prev: k + 20, action: :S
    },
  }
  return nil if cond.map {|_, c| c[:node]}.all?(&:nil?)
  c = cond.sort_by {|k, v| v&.[](:node)&.[](:count) || INF}[0][1]
  node = c[:node]
  return @dp[k] = {prev: c[:prev], action: c[:action], count: node[:count] + 1, current: k}
end

def solve(k)
  trace = []
  n = k
  loop do
    v = turn(k)
    break if v.nil?
    trace << v
    break if k == v[:prev]
    k = v[:prev]
  end
  return "#{n}:: > fail" if trace.empty?
  size = trace.size
  return "#{n}:#{size} > " + trace.map.with_index {|t, i| "#{t[:current]}:#{t[:action]}#{i == size-1 ? '' : '>'}"}.join
end

def main(n)
  for k in 1..n
    puts solve(k)
  end
end

# main(150)
main(150)
# p solve(1)