オフラインリアルタイムどう書くE20 への yancya の解答 https://yhpg.doorkeeper.jp/events/67049

1_main.rb

require 'pg'

def main(str)
  start, goal = str.chars
  PG.connect.exec_params(<<~SQL, [start, goal]).first['cnt']
  WITH RECURSIVE patterns("from", "to") AS (
VALUES ('0', '1'), ('0', '6'), ('1', '0'), ('1', '7'), ('2', '3'),
       ('3', '2'), ('3', '4'), ('3', '9'), ('4', '3'), ('4', '5'),
       ('5', '4'), ('5', 'B'), ('6', '0'), ('6', 'C'), ('7', '1'),
       ('7', '8'), ('8', '7'), ('8', '9'), ('9', '8'), ('9', '3'),
       ('9', 'A'), ('9', 'F'), ('A', '9'), ('B', '5'), ('C', '6'),
       ('C', 'D'), ('C', 'I'), ('D', 'C'), ('E', 'K'), ('F', '9'),
       ('F', 'G'), ('G', 'F'), ('G', 'M'), ('H', 'N'), ('I', 'C'),
       ('I', 'O'), ('J', 'K'), ('J', 'P'), ('K', 'J'), ('K', 'E'),
       ('K', 'L'), ('L', 'K'), ('L', 'M'), ('M', 'L'), ('M', 'G'),
       ('M', 'S'), ('N', 'H'), ('N', 'T'), ('O', 'I'), ('P', 'J'),
       ('P', 'Q'), ('P', 'V'), ('Q', 'P'), ('Q', 'R'), ('R', 'Q'),
       ('R', 'X'), ('S', 'M'), ('S', 'T'), ('S', 'Y'), ('T', 'S'),
       ('T', 'N'), ('U', 'V'), ('V', 'U'), ('V', 'P'), ('V', 'W'),
       ('W', 'V'), ('X', 'R'), ('Y', 'S'), ('Y', 'Z'), ('Z', 'Y'))

     , routes AS (
SELECT 0 AS "cnt"
     , ARRAY[]::TEXT[] AS "visited" -- 閉路に対応
     , "from" AS "cur"
  FROM patterns
 WHERE "from" = $1::TEXT

 UNION ALL

SELECT "cnt" + 1 AS "cnt"
     , ARRAY_APPEND("visited", routes."cur") AS "visited"
     , patterns."to" AS "cur"
  FROM routes
  JOIN patterns
    ON routes."cur" = patterns."from"
   AND NOT ARRAY[patterns."to"] <@ routes."visited")

SELECT MIN("cnt") AS "cnt"
  FROM routes
 WHERE "cur" = $2::TEXT;
  SQL
end

require 'test-unit'

class HogeTest < Test::Unit::TestCase
  TEST_CASES = DATA.each_line.map { |line|
    %r[^/\*(?<id>\d+)\*/.*test\((?<act_exp>.*)\)] =~ line
    act, exp = act_exp.scan(%r["(.+?)"]).flatten
    [id, [act, exp]]
  }.to_h

  data(TEST_CASES)
  test "hoge" do |(input, expected)|
    assert { main(input) == expected }
  end
end

__END__
/*0*/ test( "DE", "13" );
/*1*/ test( "EK", "1" );
/*2*/ test( "01", "1" );
/*3*/ test( "LG", "2" );
/*4*/ test( "A1", "4" );
/*5*/ test( "GJ", "4" );
/*6*/ test( "FK", "4" );
/*7*/ test( "LV", "4" );
/*8*/ test( "27", "4" );
/*9*/ test( "0O", "4" );
/*10*/ test( "G1", "5" );
/*11*/ test( "ZH", "5" );
/*12*/ test( "AB", "5" );
/*13*/ test( "KX", "5" );
/*14*/ test( "1G", "5" );
/*15*/ test( "WX", "5" );
/*16*/ test( "3L", "5" );
/*17*/ test( "9Y", "5" );
/*18*/ test( "EX", "6" );
/*19*/ test( "BG", "6" );
/*20*/ test( "7K", "7" );
/*21*/ test( "E3", "7" );
/*22*/ test( "SW", "7" );
/*23*/ test( "BM", "7" );
/*24*/ test( "3C", "7" );
/*25*/ test( "H9", "7" );
/*26*/ test( "J3", "7" );
/*27*/ test( "GX", "8" );
/*28*/ test( "2Z", "8" );
/*29*/ test( "8H", "8" );
/*30*/ test( "Z7", "8" );
/*31*/ test( "0B", "8" );
/*32*/ test( "U9", "9" );
/*33*/ test( "Z0", "10" );
/*34*/ test( "0N", "10" );
/*35*/ test( "U8", "10" );
/*36*/ test( "XZ", "10" );
/*37*/ test( "H0", "11" );
/*38*/ test( "CH", "13" );
/*39*/ test( "WB", "13" );
/*40*/ test( "0R", "13" );
/*41*/ test( "DZ", "13" );
/*42*/ test( "NI", "13" );
/*43*/ test( "QC", "14" );
/*44*/ test( "6U", "14" );
/*45*/ test( "PO", "15" );
/*46*/ test( "RI", "16" );
/*47*/ test( "UO", "17" );
/*48*/ test( "WO", "17" );
/*49*/ test( "OX", "18" );