「オフラインリアルタイムどう書く第23回(くねくね増加列)」の問題を解いてみた


[横浜へなちょこプログラミング勉強会](https://yhpg.doorkeeper.jp/)にて過去に出題された[くねくね増加列](http://nabetani.sakura.ne.jp/hena/ord23snakemoinc/)を解いてみた。
回答にかかった時間は50分程度。

多分解法としてはすごく愚直だと思われる。
`SnakeLine#longest`の中で`break`を使うか使わないかは悩んだのだが、無駄に計算することもないなと思って`break`するようにした。

```ruby
class SnakeLine
  def initialize input
    @field = input.split("/").map{|line|
      line.chars.map &:to_i
    }
  end

  def longest
    (0..9).inject(0){|max, i|
      break max if max > (10 - i)
      detect_axis(i).each_with_object([max]){|(x, y), r|
        r << longest_route_size(x, y)
      }.max
    }
  end

  private

  def detect_axis i
    @field.each_with_object([]).with_index{|(line, r), y|
      line.each.with_index{|v, x|
        r << [x, y] if v === i
      }
    }
  end

  def longest_route_size x, y
    (move(x, y).map{|(xx, yy)|
      longest_route_size(xx, yy)
    }.max || 0) + 1
  end

  def move x, y
    [
      [x - 1, y],
      [x + 1, y],
      [x, y - 1],
      [x, y + 1]
    ].select{|(xx, yy)|
      xx.between?(0, 4) and yy.between?(0, 4) and @field[yy][xx] > @field[y][x]
    }
  end
end

test = <<_TEST
/*0*/ test( "01224/82925/69076/32298/21065", "6" );    
/*1*/ test( "03478/12569/03478/12569/03478", "10" );    
/*2*/ test( "09900/28127/87036/76545/87650", "10" );    
/*3*/ test( "77777/77777/77777/77777/77777", "1" );    
/*4*/ test( "00000/11111/22222/33333/44444", "5" );    
/*5*/ test( "01234/12345/23456/34567/45678", "9" );    
/*6*/ test( "10135/21245/43456/55567/77789", "8" );    
/*7*/ test( "33333/33333/55555/55555/77777", "2" );    
/*8*/ test( "01234/11234/22234/33334/44444", "5" );    
/*9*/ test( "98765/88765/77765/66665/55555", "5" );    
/*10*/ test( "01234/10325/23016/32107/45670", "8" );    
/*11*/ test( "34343/43434/34343/43434/34343", "2" );    
/*12*/ test( "14714/41177/71141/17414/47141", "3" );    
/*13*/ test( "13891/31983/89138/98319/13891", "4" );    
/*14*/ test( "01369/36901/90136/13690/69013", "5" );    
/*15*/ test( "02468/24689/46898/68986/89864", "6" );    
/*16*/ test( "86420/68642/46864/24686/02468", "5" );    
/*17*/ test( "77777/75557/75357/75557/77777", "3" );    
/*18*/ test( "53135/33133/11111/33133/53135", "3" );    
/*19*/ test( "01356/23501/45024/61246/13461", "5" );    
/*20*/ test( "46803/68025/91358/34792/78136", "4" );    
/*21*/ test( "66788/56789/55799/43210/33211", "9" );    
/*22*/ test( "40000/94321/96433/97644/98654", "9" );    
/*23*/ test( "58950/01769/24524/24779/17069", "6" );    
/*24*/ test( "97691/01883/98736/51934/81403", "4" );    
/*25*/ test( "92049/27798/69377/45936/80277", "5" );    
/*26*/ test( "97308/77113/08645/62578/44774", "5" );    
/*27*/ test( "90207/17984/01982/31272/60926", "6" );    
/*28*/ test( "62770/65146/06512/15407/89570", "4" );    
/*29*/ test( "93914/46889/27554/58581/18703", "5" );    
/*30*/ test( "42035/12430/60728/30842/90381", "5" );    
/*31*/ test( "90347/53880/67954/95256/68777", "6" );    
/*32*/ test( "05986/60473/01606/16425/46292", "5" );    
/*33*/ test( "18053/90486/24320/04250/03853", "5" );    
/*34*/ test( "36865/13263/67280/18600/12774", "5" );    
/*35*/ test( "72456/72052/79971/14656/41151", "5" );    
/*36*/ test( "94888/28649/05561/76571/97567", "5" );    
/*37*/ test( "50214/94693/88718/78922/55359", "5" );    
/*38*/ test( "76502/99325/17987/31737/93874", "7" );    
/*39*/ test( "87142/14764/13014/00248/73105", "6" );    
/*40*/ test( "24573/71679/48704/19786/91834", "7" );    
/*41*/ test( "20347/61889/06074/61263/20519", "7" );    
/*42*/ test( "74344/97459/97302/14439/35689", "6" );    
/*43*/ test( "04794/52198/50294/09340/24160", "5" );    
/*44*/ test( "41065/69344/64698/54167/43348", "7" );    
/*45*/ test( "39947/15696/03482/19574/70235", "7" );    
/*46*/ test( "92767/16790/84897/69765/75734", "7" );    
/*47*/ test( "09654/79610/05070/23456/74687", "8" );    
/*48*/ test( "73998/98799/98707/05633/23915", "8" );    
/*49*/ test( "35661/17480/89723/64335/27217", "7" );    
/*50*/ test( "02489/77571/84873/03879/84460", "7" );
_TEST

require 'minitest/autorun'

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