平成変換を解いてみました #codeiq 2014から26に至る変換を見つけるという問題でした。 問題の解説はこちら http://antimon2.hatenablog.jp/entry/2013/08/07/231634

answer.txt

[2]014->[4]014->[16014]->(256)448196->1(64)4(81)(9)6->(1849)(36)->(4)(36)->26

(7ステップ)
別解
7: [2014]->4056[196]->40563(841)6->(4)0[5]63[2]96->(2025)6[3](49)6->(456976)->(676)->26
8: [201]4->(4)0[4]014->(201601)4->4[4][9][4]->4(1681)16->(441)16->(2116)->(4)6->26
8: 20[14]->20[19]6->[2]0[3]616->(4096)16->6[41]6->6(16)(81)6->6(49)6->(676)->26

言語: Ruby

解法:
 - 数をノードとし、変換をエッジとしてDijkstra法で到達可能な範囲を求める
 - 幅n桁までの数に制限する。例えばn=5なら6桁以上の数を通る解は考えない
 - n-1桁までの最短解より長くなりそうな探索枝は刈る
 - ゴールまで4ステップ以内で到達可能なノードをあらかじめ計算しておき、
   現在の最短ステップ以内にその範囲に到達できないことが明らかなノードは刈る

感想:
 - 桁数が増えると可能な変換が3^nオーダで増えるので、
   とにかく桁数を増やさないことが先決
 - 計算対象となる桁数を増やしても、行って帰ってこないといけないので、
   結局それでもうかるかどうかはわからない
   - 例: 別解として提示した(201601)->449を含む解は探索範囲を
     7桁まで広げなければ見つからないが、同じステップ数の解「(4096)->64」もまた
     8ステップである

力技でCPUをぶん回してしまいましたが、1ステップではひとつの変換しかしないような
制限で解いてから、並列実行できる変換を畳むほうが、探索の幅が広がらない分、
楽だったのかもしれません。実際、得られた解も並列に変換している部分は少ししか
ありません。

heisei.rb

require 'pry'

STDOUT.sync = true

# Bidrectional search from two ends: goal and start.
# Here we complete the backend tree at a fixed depth before expanding frontend.
# We loop over the number of digits that restrict intermediate nodes.
# At Each loop the search aims to solutions shorter than
#  already-found shortest one.

# Represent a node in the search tree
class Node
  attr_reader :number
  attr_accessor :depth, :edge
  attr_accessor :goal, :steps # node in the back tree if solution reached

  def initialize(num, depth = 0, edge = nil)
    @number = num.to_i
    @depth = depth
    @edge = edge
    @goal = nil
    @steps = 9999
  end

  def to_s
    "Node<#{@number}: depth(#{@depth}: #{@edge})>"
  end
end

# Solver
#  Perform the bidirectional search
#  digits limit the intermediate nodes being too big
class Solver
  attr_reader :nodes, :start
  attr_reader :digits, :max_steps, :depth, :max
  attr_reader :goals
  attr_reader :answer

  # Solver.new
  #  start: the number to start from
  #  digits: at most this many number of digits
  #  goals: another Solver that represents our goal nodes
  def initialize(start, digits, max_steps, goals = nil)
    @start = start
    @start_node = Node.new(start, 0)
    @goals = goals
    @max_steps = max_steps
    @digits = digits
    @max = 10**digits
    @report_step = 1000
  end

  # Expand the graph
  def solve
    puts (goals ? "Solving upto" : "Generating goals to") + " #{@digits} digits... [#{Time.now}]"
    @nodes = {
      @start => @start_node.dup,
    }
    togo = @nodes.values # fringe nodes
    @depth = 0
    @next_report = 1000
    solutions = {}
    max_edges = 0
    goals_depth = goals ? goals.depth : 0
    until togo.empty? || @depth + goals_depth >= @max_steps - 1
      print "+(#{max_edges}*#{togo.size})"
      @depth += 1
      dirty = []
      togo.each do |n|
        next if n.number >= @max

        # For each possible edge, populate the search tree.
        edges = Translation.translations(n.number).find_all{|t|t.to != n.number}
        max_edges = [edges.size, max_edges].max
        edges.each do |e|
          next if e.to >= @max
          if to = @nodes[e.to]
            if to.depth > @depth
              to.depth = @depth
              to.edge = e
            end
          else
            # Add the new node to fringe for the next round
            to = Node.new(e.to, @depth, e)
            @nodes[e.to] = to
            dirty << to
            if @nodes.size > @next_report
              print @depth
              @next_report += @report_step
            end
          end
          if n.depth != @depth - 1
            binding.pry # Shouldn't happen
          end
          # Did we hit the back wavefront?
          if goals && goal = goals.nodes[to.number]
            unless solutions[to]
              solutions[to] = true
              steps = @depth + goal.depth
              if steps < to.steps
                to.goal = goal
                to.steps = steps
              end
              if steps < @max_steps
                puts "\n   Solution: #{steps} steps: #{path(to)}   [#{Time.now}]"
                @max_steps = steps
              end
            end
          end
        end
      end
      togo = dirty
    end
    # Report the shortest solutions so far
    solution = solutions.keys.sort_by {|n| n.steps}.first
    if solution
      @max_steps = [@max_steps, solution.steps].min
      answer = path(solution)
    end
    puts ""
    solution
  end
  # Give the answer in the answer.txt format
  def path(node)
    res = []
    p = node
    while p.depth > 0
      res.unshift(p.edge.translation)
      p = @nodes[p.edge.from]
    end
    p = node.goal
    while p.depth > 0
      res << p.edge.inverse
      p = goals.nodes[p.edge.from]
    end
    res << goals.start
    res.join('->')
  end
end

# Translation is an edge in the search tree.
# Implements the Heisei translation.
class Translation
  @@translations = [] # Memoize translations upto 9999
  attr_reader :from, :to, :translation
  def initialize(trans)
    @from = trans.gsub(/\D/, '').to_i
    @translation = trans
    @to = value
  end
  def to_s
    "Edge<#{@translation}>"
  end

  # Compute the destination number
  #  [d] -> d^2
  #  (d) -> d.sqrt
  def value
    x = translation.dup
    x.gsub!(/\[(\d+)\]/) do
      ($1.to_i ** 2).to_s
    end
    x.gsub!(/\((\d+)\)/) do
      sqr = $1.to_i
      sqrt = Math.sqrt(sqr).floor
      sqr == sqrt * sqrt or raise "invalid sqrt translation"
      sqrt.to_s
    end
    x.to_i
  end

  # Express inverse translation in answer.txt format.
  def inverse
    x = translation.dup
    x.gsub!(/\[(\d+)\]/) do
      "<" + ($1.to_i ** 2).to_s + ">" # avoid confusion with input ()
    end
    x.gsub!(/\((\d+)\)/) do
      sqr = $1.to_i
      sqrt = Math.sqrt(sqr).floor
      sqr == sqrt * sqrt or raise "invalid sqrt translation"
      "[" + sqrt.to_s + "]"
    end
    x.tr('<>', '()')
  end

  # Populate the cache table
  (0..1).each {|n| @@translations[n] = [Translation.new(n.to_s)]}
  (2..9).each do |n|
    @@translations[n] = [Translation.new(n.to_s),
                         Translation.new("[#{n}]")]
    if n == 4 || n == 9
      @@translations[n] << Translation.new("(#{n})")
    end
  end

  # Return all possible translations that can be applied to num
  def self.translations(num)
    trans1(num.to_s)
  end

  # Recursively compute translations
  # (Identitiy translation is included)
  #
  #  Let
  #    r: Num's rightmost digit
  #    l: Left substring
  #  and corresponding translation sets rtr and ltr,
  #  the translations are the union of
  #    l x r (product and concat)
  #    open-paren in left side and close-paren at the end
  def self.trans1(num)
    res = @@translations[num.to_i] and return res
    l, r = num[0...-1], num[-1]
    ltr = trans1(l)
    rtr = trans1(r)
    res = ltr.product(rtr).map{|a,b| self.new(a.translation+b.translation)}
    l.size.times do |p|
      # Place []
      #   Can't place open left to a zero
      l[p] == '0' and next
      res << self.new(l[0...p] + "[" + l[p..-1] + r + "]")

      # Place ()
      #   n^2 mod 10 cannot be 2,3,7,8
      #   n^2 mod 10 == 0 only if n^2 mod 100 == 0
      if "14569".include?(r) || l[-1] == '0' && r == '0'
        # OK, just try.  "rescue nil" rejects a non-square number case
        res << self.new(l[0...p] + "(" + l[p..-1] + r + ")") rescue nil
      end
    end
    # Memoize upto 9999
    num.size <= 4 and @@translations[num.to_i] = res
    res
  end
end

# main
AD = 2014
HEISEI = 26

answers = []
goal_depth = 4 # Decided by cut-and-try.
max_steps = 15 # I know there is an answer with 15 steps (I did it by hand)
# Loop over the number of digits we consider
#  27 is number of digits in 2014**2**backend_depth (3 when we reach there)
(4..27).each do |limit|
  puts "\n------ Limit = #{limit}; Showing answers shorter than #{max_steps} steps ------\n"
  g = Solver.new(HEISEI, limit, [goal_depth, (max_steps+1)/2].min)
  g.solve # Get backend wavefront
  sv = Solver.new(AD, limit, max_steps, g)
  sv.solve # Search frontend
  sv.answer and answers << [sv.answer, Time.now]
  max_steps = sv.max_steps
end
puts "\n------ Finished ------\n"
puts answers.each {|a| puts a.join("  ")}

heisei_out.txt

maeda@mandel 6977% time ruby heisei4.rb|tee h4-4.out

------ Limit = 4; Showing answers shorter than 15 steps ------
Generating goals to 4 digits... [2013-10-06 22:18:11 +0900]
+(0*1)+(4*4)+(16*14)
Solving upto 4 digits... [2013-10-06 22:18:11 +0900]
+(0*1)+(13*3)

------ Limit = 5; Showing answers shorter than 15 steps ------
Generating goals to 5 digits... [2013-10-06 22:18:11 +0900]
+(0*1)+(4*4)+(16*26)
Solving upto 5 digits... [2013-10-06 22:18:11 +0900]
+(0*1)+(13*8)+(31*9)+(54*8)+(54*6)+(54*18)+(58*34)+(111*105)
   Solution: 11 steps: 20[14]->201(9)6->201(36)->20[16]->(2025)6->4[5]6->4(256)->[41]6->(16)(81)6->(4)(9)6->2(36)->26   [2013-10-06 22:18:11 +0900]


------ Limit = 6; Showing answers shorter than 11 steps ------
Generating goals to 6 digits... [2013-10-06 22:18:12 +0900]
+(0*1)+(4*4)+(16*31)
Solving upto 6 digits... [2013-10-06 22:18:12 +0900]
+(0*1)+(13*11)+(56*35)+(79*64)+(118*143)
   Solution: 8 steps: 20[14]->20[19]6->[2]0[3]616->(4096)16->6[41]6->6(16)(81)6->6(49)6->(676)->26   [2013-10-06 22:18:12 +0900]


------ Limit = 7; Showing answers shorter than 8 steps ------
Generating goals to 7 digits... [2013-10-06 22:18:12 +0900]
+(0*1)+(4*4)+(16*31)
Solving upto 7 digits... [2013-10-06 22:18:13 +0900]
+(0*1)+(13*13)+(152*76)+(306*293)4

------ Limit = 8; Showing answers shorter than 8 steps ------
Generating goals to 8 digits... [2013-10-06 22:18:14 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 8 digits... [2013-10-06 22:18:15 +0900]
+(0*1)+(13*13)+(152*126)3+(454*929)4444

------ Limit = 9; Showing answers shorter than 8 steps ------
Generating goals to 9 digits... [2013-10-06 22:18:25 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 9 digits... [2013-10-06 22:18:26 +0900]
+(0*1)+(13*13)+(152*187)33+(1503*2225)4444
   Solution: 7 steps: [2]014->[4]014->[16014]->(256)448196->1(64)4(81)(9)6->(1849)(36)->(4)(36)->26   [2013-10-06 22:18:39 +0900]
44444444444444

------ Limit = 10; Showing answers shorter than 7 steps ------
Generating goals to 10 digits... [2013-10-06 22:19:15 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 10 digits... [2013-10-06 22:19:15 +0900]
+(0*1)+(13*13)+(152*241)33333

------ Limit = 11; Showing answers shorter than 7 steps ------
Generating goals to 11 digits... [2013-10-06 22:19:19 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 11 digits... [2013-10-06 22:19:19 +0900]
+(0*1)+(13*13)+(152*281)333333333

------ Limit = 12; Showing answers shorter than 7 steps ------
Generating goals to 12 digits... [2013-10-06 22:19:25 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 12 digits... [2013-10-06 22:19:25 +0900]
+(0*1)+(13*13)+(152*307)333333333333333333

------ Limit = 13; Showing answers shorter than 7 steps ------
Generating goals to 13 digits... [2013-10-06 22:19:37 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 13 digits... [2013-10-06 22:19:37 +0900]
+(0*1)+(13*13)+(152*316)3333333333333333333333333333333

------ Limit = 14; Showing answers shorter than 7 steps ------
Generating goals to 14 digits... [2013-10-06 22:19:54 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 14 digits... [2013-10-06 22:19:54 +0900]
+(0*1)+(13*13)+(152*321)3333333333333333333333333333333333333333333333333333

------ Limit = 15; Showing answers shorter than 7 steps ------
Generating goals to 15 digits... [2013-10-06 22:20:21 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 15 digits... [2013-10-06 22:20:21 +0900]
+(0*1)+(13*13)+(152*321)3333333333333333333333333333333333333333333333333333333333333333333333333333333

------ Limit = 16; Showing answers shorter than 7 steps ------
Generating goals to 16 digits... [2013-10-06 22:20:50 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 16 digits... [2013-10-06 22:20:50 +0900]
+(0*1)+(13*13)+(152*321)333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

------ Limit = 17; Showing answers shorter than 7 steps ------
Generating goals to 17 digits... [2013-10-06 22:21:20 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 17 digits... [2013-10-06 22:21:21 +0900]
+(0*1)+(13*13)+(152*321)33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

------ Limit = 18; Showing answers shorter than 7 steps ------
Generating goals to 18 digits... [2013-10-06 22:21:52 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 18 digits... [2013-10-06 22:21:52 +0900]
+(0*1)+(13*13)+(152*321)33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

------ Limit = 19; Showing answers shorter than 7 steps ------
Generating goals to 19 digits... [2013-10-06 22:22:24 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 19 digits... [2013-10-06 22:22:24 +0900]
+(0*1)+(13*13)+(152*321)33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

------ Limit = 20; Showing answers shorter than 7 steps ------
Generating goals to 20 digits... [2013-10-06 22:22:58 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 20 digits... [2013-10-06 22:22:58 +0900]
+(0*1)+(13*13)+(152*321)333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

------ Limit = 21; Showing answers shorter than 7 steps ------
Generating goals to 21 digits... [2013-10-06 22:23:32 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 21 digits... [2013-10-06 22:23:33 +0900]
+(0*1)+(13*13)+(152*321)33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

------ Limit = 22; Showing answers shorter than 7 steps ------
Generating goals to 22 digits... [2013-10-06 22:24:21 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 22 digits... [2013-10-06 22:24:21 +0900]
+(0*1)+(13*13)+(152*321)33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

------ Limit = 23; Showing answers shorter than 7 steps ------
Generating goals to 23 digits... [2013-10-06 22:25:05 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 23 digits... [2013-10-06 22:25:05 +0900]
+(0*1)+(13*13)+(152*321)333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

------ Limit = 24; Showing answers shorter than 7 steps ------
Generating goals to 24 digits... [2013-10-06 22:25:46 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 24 digits... [2013-10-06 22:25:46 +0900]
+(0*1)+(13*13)+(152*321)3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

------ Limit = 25; Showing answers shorter than 7 steps ------
Generating goals to 25 digits... [2013-10-06 22:26:20 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 25 digits... [2013-10-06 22:26:20 +0900]
+(0*1)+(13*13)+(152*321)3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

------ Limit = 26; Showing answers shorter than 7 steps ------
Generating goals to 26 digits... [2013-10-06 22:26:52 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 26 digits... [2013-10-06 22:26:52 +0900]
+(0*1)+(13*13)+(152*321)3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

------ Limit = 27; Showing answers shorter than 7 steps ------
Generating goals to 27 digits... [2013-10-06 22:27:24 +0900]
+(0*1)+(4*4)+(16*31)3
Solving upto 27 digits... [2013-10-06 22:27:24 +0900]
+(0*1)+(13*13)+(152*321)3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

------ Finished ------
ruby heisei4.rb  520.70s user 4.64s system 89% cpu 9:46.52 total
tee h4-4.out  0.01s user 0.11s system 0% cpu 9:46.53 total