「オフラインリアルタイムどう書く第27回(分岐と行き止まり)」の問題を解いてみた


[横浜へなちょこプログラミング勉強会](https://yhpg.doorkeeper.jp/)にて過去に出題された[分岐と行き止まり](http://nabetani.sakura.ne.jp/hena/ord27raswi/)を解いてみた。
回答にかかった時間は15分程度。
時間配分としては全ルートを書き出すのに10分、コードを書くのに5分。

スタートからゴールまでに通る部分さえ分かってしまえば、通行禁止の線路が含まれていないルートを抽出するだけの力業である。
今回はルート数が少ないので特に工夫もしていないが、これがルート数が膨大な数になるならばもっと工夫しなけれならないだろう。

```ruby
class Rail
  def initialize
    @routes = {
      1 => [
        {route: [?a, ?b, ?c],     goal: 4},
        {route: [?g, ?c],         goal: 4},
        {route: [?g, ?h],         goal: 4},
        {route: [?a, ?b],         goal: 5},
        {route: [?g, ?e],         goal: 5},
        {route: [?a, ?b, ?c],     goal: 6},
        {route: [?g, ?c],         goal: 6},
        {route: [?g, ?h, ?i],     goal: 6}
      ],
      2 => [
        {route: [?d, ?c],         goal: 4},
        {route: [?h],             goal: 4},
        {route: [?d, ?e],         goal: 5},
        {route: [?d, ?c],         goal: 6},
        {route: [?h, ?i],         goal: 6}
      ],
      3 => [
        {route: [?b, ?c],         goal: 4},
        {route: [?f, ?g, ?c],     goal: 4},
        {route: [?f, ?g, ?h],     goal: 4},
        {route: [?b],             goal: 5},
        {route: [?f, ?g, ?e],     goal: 5},
        {route: [?b, ?c],         goal: 6},
        {route: [?f, ?g, ?c],     goal: 6},
        {route: [?f, ?g, ?h, ?i], goal: 6}
      ]
    }
  end

  def go input
    chars = input.chars
    can = @routes.each_with_object([]){|(start, routes), r|
      routes.each{|route|
        r << "#{start}#{route[:goal]}" unless chars.any?{|c| route[:route].include?(c)}
      }
    }.uniq.sort
    can.empty? ? "-" : can.join(",")
  end
end
test = <<_TEST
/*0*/ test( "befi", "14,16,24,26" );    
/*1*/ test( "abc", "14,15,16,24,25,26,34,35,36" );    
/*2*/ test( "de", "14,15,16,24,26,34,35,36" );    
/*3*/ test( "fghi", "14,15,16,24,25,26,34,35,36" );    
/*4*/ test( "abcdefghi", "-" );    
/*5*/ test( "ag", "24,25,26,34,35,36" );    
/*6*/ test( "dh", "14,15,16,34,35,36" );    
/*7*/ test( "bf", "14,15,16,24,25,26" );    
/*8*/ test( "ch", "15,25,35" );    
/*9*/ test( "be", "14,16,24,26,34,36" );    
/*10*/ test( "ci", "14,15,24,25,34,35" );    
/*11*/ test( "cgi", "15,24,25,35" );    
/*12*/ test( "acgi", "24,25,35" );    
/*13*/ test( "cdefghi", "15,35" );    
/*14*/ test( "acdefghi", "35" );    
/*15*/ test( "cdegi", "15,24,35" );    
/*16*/ test( "bcdegi", "24" );    
/*17*/ test( "afh", "14,15,16,24,25,26,34,35,36" );    
/*18*/ test( "abfh", "14,15,16,24,25,26" );    
/*19*/ test( "dfh", "14,15,16,34,35,36" );    
/*20*/ test( "cdfh", "15,35" );    
/*21*/ test( "deh", "14,15,16,34,35,36" );    
/*22*/ test( "cdeh", "15,35" );    
/*23*/ test( "abefgh", "24,26" );    
/*24*/ test( "abdefgh", "-" );    
/*25*/ test( "acfghi", "25,35" );    
/*26*/ test( "acdfghi", "35" );    
/*27*/ test( "cegi", "15,24,35" );    
/*28*/ test( "abcfhi", "15,25" );    
/*29*/ test( "abcefhi", "-" );    
/*30*/ test( "abdi", "14,15,16,24,34,35,36" );    
/*31*/ test( "abdfi", "14,15,16,24" );    
/*32*/ test( "bdi", "14,15,16,24,34,35,36" );    
/*33*/ test( "bdfi", "14,15,16,24" );    
/*34*/ test( "adfh", "14,15,16,34,35,36" );    
/*35*/ test( "adfgh", "34,35,36" );    
/*36*/ test( "acdfhi", "15,35" );    
/*37*/ test( "bcdfgi", "24" );    
/*38*/ test( "bcdfghi", "-" );    
/*39*/ test( "defi", "14,15,16,24,34,35,36" );    
/*40*/ test( "defhi", "14,15,16,34,35,36" );    
/*41*/ test( "cdefg", "15,24,26,35" );    
/*42*/ test( "cdefgi", "15,24,35" );    
/*43*/ test( "bdefg", "24,26" );    
/*44*/ test( "bdefgi", "24" );
_TEST

require 'minitest/autorun'

describe 'Rail' do
  rail = Rail.new
  test.split("\n").each do |line|
    t, n, input, expect = line.match(/^\/\*(\d+)\*\/\s*test\(\s*"([^"]+)",\s*"([^"]+)"\s*\);*\s*$/).to_a
    it input do
      assert_equal expect, rail.go(input)
    end
  end
end
```