LoginSignup
0
0

More than 5 years have passed since last update.

@Nabetani(鍋谷 武典)

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

Posted at

問題 : 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 までしか解けない当日の実装。
ちょっと手直ししたけど。

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 さんによって明かされた想定アルゴリズムの、拙実装

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分ぐらいかかる。何が無駄かなぁ。

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

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0