オフラインリアルタイムどう書く E26 の実装例(ruby)

問題 : https://cedretaber.github.io/doukaku/e26/
実装リンク集 : https://qiita.com/Nabetani/items/0bcabb80bdcbc9b2ff52

で。

当日は完全に敗北。
惜しいところまでも行けなかった。

入力は 2×2 から 9×9 まである（なぜか 5×5 がない）。
当日書けたのは、 3×3 が解けるところまで。
3×3 なら、盤面の状態が高々 4の9乗 = 26万通り しかないので、全探索できる。
4×4 だと 4の16乗 なので 43億通り。終わらない。9×9 は夢のまた夢。

というわけで、まずは 3×3 までしか解けない当日の実装。
ちょっと手直ししたけど。

```ruby:ruby2.5
# frozen_string_literal: true

require "json"

class Solver
  def initialize( sz )
    @size = sz
  end

  attr_reader( :size )

  NEIS = [ [-1, 0], [1, 0], [0, -1], [0, 1] ].freeze

  # 地図 m0 の pos を90度回す
  def rotate( m0, pos )
    m = m0.dup
    y, x = pos.divmod(size)
    m[pos] = ( m[pos]+1 ) %4
    NEIS.each do |dx, dy|
      y1, x1 = dy+y, dx+x
      next unless 0<=y1 && y1<size && 0<=x1 && x1<size
      p = y1*size+x1
      m[p] = ( m[p] + 3 ) % 4
    end
    m
  end

  def solved?( map )
    map.all?(&:zero?)
  end

  def solve( map )
    q=[[map, []]]
    done = {}
    loop do
      m0, h = q.shift
      (size*size).times do |pos|
        next if 3<=h.count(pos)
        m1=rotate(m0, pos)
        return h+[pos] if solved?(m1)
        key = m1.join
        q.push( [m1, h+[pos]] ) unless done[key]
        done[key]=true
      end
    end
  end
end

if $PROGRAM_NAME==__FILE__
  JSON.parse( DATA.read )["test_data"].each do |e|
    q = e["number"]
    src = e["src"]
    size  = src.to_i
    d = e["src"].split("|").last.scan( /\d/ ).map{ |e| e.to_i - 1 }
    solver = Solver.new(size)
    hands = solver.solve(d.flatten).map{ |x|
      x.divmod(size).map{ |xy| xy+1 }.reverse.join(",")
    }.join("|")
    puts [q, hands].join( " " )
  end
end

__END__
{
  "event_id":"E26",
  "event_url":"https://cedretaber.github.io/doukaku/e26",
  "test_data":[
    {"number":0,"src":"2|23,14"},
    {"number":1,"src":"2|13,43"},
    {"number":2,"src":"2|43,13"},
    {"number":3,"src":"2|12,34"},
    {"number":4,"src":"2|23,34"},
    {"number":5,"src":"2|23,13"},
    {"number":6,"src":"2|21,21"},
    {"number":7,"src":"2|22,22"},
    {"number":8,"src":"3|423,124,242"},
    {"number":9,"src":"3|343,334,211"},
    {"number":10,"src":"3|313,231,423"},
    {"number":11,"src":"3|241,321,343"},
    {"number":12,"src":"3|142,241,121"},
    {"number":13,"src":"3|333,443,411"},
    {"number":14,"src":"3|142,321,424"},
    {"number":15,"src":"3|313,342,211"}
  ]
}
```

そして。
以下は出題者である @cedretaber さんによって明かされた想定アルゴリズムの、拙実装

```ruby:ruby2.5
# frozen_string_literal: true

require "json"

class Solver
  def initialize( sz )
    @size = sz
  end

  attr_reader( :size )

  NEIS = [ [-1, 0], [1, 0], [0, -1], [0, 1] ].freeze

  # 地図 m0 の pos を90度回す
  def rotate( m0, pos )
    m = m0.dup
    y, x = pos.divmod(size)
    m[pos] = ( m[pos]+1 ) %4
    NEIS.each do |dx, dy|
      y1, x1 = dy+y, dx+x
      next unless 0<=y1 && y1<size && 0<=x1 && x1<size
      p = y1*size+x1
      m[p] = ( m[p] + 3 ) % 4
    end
    m
  end

  # 解けていたら true。
  # ※ 本当は最下段だけチェックすればいいけど、全部チェックしている
  def solved?( map )
    map.all?(&:zero?)
  end

  # 最下段以外を揃える手順と、その結果
  def solve_uppers( map0, hands0 )
    map = map0.dup
    hands=hands0.dup
    (1...size).each do |y|
      (0...size).each do |x|
        pos0 = (y-1)*size + x
        pos1 = pos0+size
        hands += [pos1]*map[pos0]
        map[pos0].times{ map = rotate( map, pos1 ) }
      end
    end
    [map, hands]
  end

  # 解く
  def solve( map0 )
    (4**size).times do |num|
      map = map0.dup
      # 最上段を適当に回す
      hands = num.digits(4).flat_map.with_index{ |d, ix| [ix]*d }
      hands.each do |h|
        map = rotate( map, h )
      end

      # 最下段以外を揃える
      map, hands = solve_uppers( map, hands)

      # 偶然(?)全部揃ったら正解
      return hands if solved?(map)
    end
  end
end

if $PROGRAM_NAME==__FILE__
  JSON.parse( DATA.read )["test_data"].each do |e|
    q = e["number"]
    src = e["src"]
    size  = src.to_i
    d = e["src"].split("|").last.scan( /\d/ ).map{ |e| e.to_i - 1 }
    solver = Solver.new(size)
    hands = solver.solve(d.flatten).map{ |x|
      x.divmod(size).map{ |xy| xy+1 }.reverse.join(",")
    }.join("|")
    puts [q, hands].join( " " )
  end
end

__END__
{ "event_id":"E26",
  "event_url":"https://cedretaber.github.io/doukaku/e26",
  "test_data":[{"number":0,"src":"2|23,14"},
  {"number":1,"src":"2|13,43"},
  {"number":2,"src":"2|43,13"},
  {"number":3,"src":"2|12,34"},
  {"number":4,"src":"2|23,34"},
  {"number":5,"src":"2|23,13"},
  {"number":6,"src":"2|21,21"},
  {"number":7,"src":"2|22,22"},
  {"number":8,"src":"3|423,124,242"},
  {"number":9,"src":"3|343,334,211"},
  {"number":10,"src":"3|313,231,423"},
  {"number":11,"src":"3|241,321,343"},
  {"number":12,"src":"3|142,241,121"},
  {"number":13,"src":"3|333,443,411"},
  {"number":14,"src":"3|142,321,424"},
  {"number":15,"src":"3|313,342,211"},
  {"number":16,"src":"4|2233,3421,2423,3443"},
  {"number":17,"src":"4|4241,1131,1122,3212"},
  {"number":18,"src":"4|1341,3244,1241,2243"},
  {"number":19,"src":"4|1322,2313,2123,1231"},
  {"number":20,"src":"4|3334,4321,4413,2421"},
  {"number":21,"src":"4|4341,2411,2212,3441"},
  {"number":22,"src":"4|2332,3344,4143,4442"},
  {"number":23,"src":"4|1132,1323,1431,4113"},
  {"number":24,"src":"4|1143,4311,4431,3322"},
  {"number":25,"src":"4|3414,3423,1131,4343"},
  {"number":26,"src":"6|221111,241234,233313,341121,113324,221212"},
  {"number":27,"src":"6|424311,113322,433243,243412,324413,244132"},
  {"number":28,"src":"6|321321,434431,414411,431421,223143,431421"},
  {"number":29,"src":"6|131331,442434,142241,441143,121414,211221"},
  {"number":30,"src":"6|413344,424331,213114,214432,431113,432331"},
  {"number":31,"src":"6|124131,412132,321411,433223,332244,334111"},
  {"number":32,"src":"6|244312,111214,241421,314233,322112,114242"},
  {"number":33,"src":"6|143311,111242,222221,323122,333131,421243"},
  {"number":34,"src":"6|424422,341234,441343,432431,122331,121323"},
  {"number":35,"src":"6|431434,424333,134444,331131,141123,324121"},
  {"number":36,"src":"7|3241411,4441442,4212413,2121134,1422324,1434322,4343413"},
  {"number":37,"src":"7|1243111,1113111,3341414,2344223,3142231,1112142,1231222"},
  {"number":38,"src":"7|4242242,3221412,2431231,2331143,1334211,1243413,4114112"},
  {"number":39,"src":"7|1411343,3221433,4121144,1243421,3231444,1334413,2243213"},
  {"number":40,"src":"7|3444121,1221223,2123443,3233414,4342412,4344431,2232444"},
  {"number":41,"src":"7|2144234,1233134,3431431,2334434,1334413,3133341,2424131"},
  {"number":42,"src":"8|31323114,31212114,32412112,12433332,31413231,14244134,32342222,23244112"},
  {"number":43,"src":"8|11413121,12421412,32332241,33113131,41341424,24241433,34222233,41411122"},
  {"number":44,"src":"8|33241213,32441332,12123424,12132412,13141333,13411112,13321421,23341333"},
  {"number":45,"src":"8|42443342,11244323,14412212,32132443,22143221,11143134,12423311,44432244"},
  {"number":46,"src":"8|44322211,33243223,23423332,12134113,44221134,11141323,43443344,23411244"},
  {"number":47,"src":"8|34434142,11124143,44312124,13321412,14431321,42412314,41432121,13122423"},
  {"number":48,"src":"9|242314234,431314323,324242223,243133311,342411343,422111322,444421344,113442233,113221224"},
  {"number":49,"src":"9|133412414,244411421,421323313,221432342,113123313,112413334,343423111,232423133,321143143"}
]}
```

* 最下段以外を揃えるのは簡単
* 最下段以外を揃える際には、最上段を回す必要がない
* 最上段を予め回してから最下段以外を揃えると、最下段の状態が変わる

という辺りを理解しておくとソースコードの意図が読めるかもしれない。

現実的な時間で 9×9 も終わるものの、割と遅くて、全部回すと手元のマシンで 1分ぐらいかかる。何が無駄かなぁ。

というわけで、敗北の記録なのでした。ぐぬぬ。