オフラインリアルタイムどう書くE27の参考問題「灯りと鏡」の実装例を、まずは ruby で。
問題 : http://nabetani.sakura.ne.jp/hena/orde27ligmir/
実装リンク集 : https://qiita.com/Nabetani/items/0b2f459ec128c89948f4
10/6 のイベント : https://yhpg.doorkeeper.jp/events/79705
ruby2.5
require "json"
def reflect(x)
case x
when 0+1i; 1+0i
when 0-1i; -1+0i
when 1+0i; 0+1i
when -1+0i; 0-1i
end
end
def solve(map)
you = Complex(*map.index("Y").divmod(5+1)) # +1 は「/」の分
light = [you, -1+0i] # 位置と方向のペア
visited = []
(5*5*2).times do # 高々 5×5×2 しか進まない
visited << light[0]
newpos = light[0]+light[1]
break unless (0...5)===newpos.real && (0...5)===newpos.imag
cell = map[newpos.real*(5+1)+newpos.imag]
case cell
when ".", "Y"
light=[newpos, light[1]]
when "0"
light=[newpos, reflect(light[1])]
when "1"
light=[newpos, -reflect(light[1])]
when "x"
break
end
end
visited.map{ |c|
((c.real*5+c.imag)+?a.ord).chr
}.sort.uniq.join
end
if $0==__FILE__
data = JSON.parse(DATA.read, symbolize_names:true)
data[:test_data].map{ | number:, src:, expected: |
actual = solve( src )
okay = actual == expected
puts [ number, (okay ? "ok" : "**NG**"), actual, expected ].join(" ")
okay
}.all?.yield_self{ |x| puts( x ? "okay" : "SOMETHING WRONG" ) }
end
__END__
{"event_id":"E27","event_url":"https://yhpg.doorkeeper.jp/events/79705","test_data":[
{"number":0,"src":"x...x/.1.0./..0../.Y.../0..x.","expected":"ghilnqs"},
{"number":1,"src":"..Y../...../...../...../.....","expected":"c"},
{"number":2,"src":"..x../..Y../...../...../.....","expected":"h"},
{"number":3,"src":"..Y.x/..1x0/11.../....0/1..1.","expected":"c"},
{"number":4,"src":"....1/....Y/...../...../.....","expected":"ej"},
{"number":5,"src":".10../x.1../x.1x./.Y.1./...0.","expected":"bcghlq"},
{"number":6,"src":"0.x10/00..x/x0x.0/....0/...Y1","expected":"deinsx"},
{"number":7,"src":"1.01./01Y.1/..1.1/..10./0.0..","expected":"abcfgh"},
{"number":8,"src":"x..../x1x../0...0/....Y/.1..0","expected":"klmnot"},
{"number":9,"src":"...../..10./.1Y1./.01../.....","expected":"hilmnqr"},
{"number":10,"src":"...../..10./x.11./...../..Y..","expected":"hilmnrw"},
{"number":11,"src":"...../x.10x/...../x.Y1x/.....","expected":"himnqrs"},
{"number":12,"src":"..010/...Y1/..0../0.x../.....","expected":"defghij"},
{"number":13,"src":"1.0../...../.0x../Y.1x./..1..","expected":"abcfhkp"},
{"number":14,"src":"...../101../0.0../..Y../.....","expected":"fgklmqrv"},
{"number":15,"src":"1.0../00.../.x..0/0.Y1./...10","expected":"abcfghmr"},
{"number":16,"src":"x101./1..../.Y.x./..01./.00.1","expected":"bcghlmrs"},
{"number":17,"src":"x11../x.x../.0.01/..x../...Y.","expected":"bcglmnsx"},
{"number":18,"src":"..1.0/x0.x./0.0../x...Y/.10.1","expected":"cdehjmnot"},
{"number":19,"src":"..x.0/.0.../1..0x/1..1./Y.00.","expected":"klmnpqrsu"},
{"number":20,"src":"0.1.0/.0.xY/0...0/01..1/x00.x","expected":"cdehjmrwx"},
{"number":21,"src":"...0./.0.0./..101/...10/..01Y","expected":"mnpqrstwxy"},
{"number":22,"src":"10..0/.Y.0./0..1./....x/000..","expected":"abfghiklmn"},
{"number":23,"src":"10..1/...../.1010/110.1/x..Yx","expected":"lmnopqrstx"},
{"number":24,"src":"110../....1/x1..x/0.0.0/....Y","expected":"bcghlmrsty"},
{"number":25,"src":"x.101/1..../..001/010Yx/..1.1","expected":"cdehijmnos"},
{"number":26,"src":"x.111/x10../...0./00.1x/x.Y.1","expected":"ghklmnqrsw"},
{"number":27,"src":"11.../....0/11..1/1.1../.Y..1","expected":"fghijlmnoqv"},
{"number":28,"src":"...x1/.1.0./11.1./.01../Y..x.","expected":"cghiklmnpqru"},
{"number":29,"src":".0.../110x./11..0/01.x./..Y.x","expected":"ghklmnopqrtw"},
{"number":30,"src":".01.0/.110x/0...0/.01Y./x.1x.","expected":"cdeghilmnqrs"},
{"number":31,"src":".1100/..1.0/1.11Y/0..1./.0..0","expected":"hijklmnopqrs"},
{"number":32,"src":"1..00/..11./.100./1..Y1/.....","expected":"abcdfhikmnps"},
{"number":33,"src":"1.0../.11x0/.00.x/Y.10./.10x0","expected":"abcfghklmpqr"},
{"number":34,"src":"11110/11.../.x.../.0111/0.Y0.","expected":"deijnorstwxy"},
{"number":35,"src":"...1./.1.0x/10..0/0Y.11/.0.x0","expected":"ghiklmnopqrst"},
{"number":36,"src":"...10/x111./0x.11/.0.../0.0Y.","expected":"dehijmnorswxy"},
{"number":37,"src":".1x../.x1.0/0x.x./x11.1/x0Y.1","expected":"hijmoqrstvwxy"},
{"number":38,"src":"x.x../x110./1.1.0/0.Y.1/0.00x","expected":"hiklmnopqrstx"},
{"number":39,"src":"...0./11.00/10..x/..0.1/Y0.10","expected":"ghiklmnpqsuvwx"},
{"number":40,"src":".110./....0/x..../.0001/11.Y.","expected":"cdfghijmnorstx"},
{"number":41,"src":"1.00./....1/.1.../0...0/0..1Y","expected":"abcfhkmpqrstwy"},
{"number":42,"src":".1.01/..x../..100/..Y../...01","expected":"bcdgilmnoqrstvxy"},
{"number":43,"src":"1...0/Y..../...../...../0...1","expected":"abcdefjkoptuvwxy"},
{"number":44,"src":"x1..0/1..0./.Yx../0...1/.0.1.","expected":"bcdefghijklnopqrstvwx"},
{"number":45,"src":"1...0/.1.0./..1../..01./Y0..1","expected":"abcdefghijklmnopqrstuvwxy"}
]}
たぶん方針は光の流れを素直にシミュレートするしかないと思う。
この実装では、地図の持ち方は文字列のまま。自分の位置は複素数で持つという方針にした。
悩みどころは終了条件をどうするか。
この実装の選択は、光は高々 2×5×5 マスしか進まないということを利用して、50.times で済ませた。
9番のケースなんかでだいぶ無駄な処理が進むことになるけど、気にしない方向で。
reflect メソッドをもう少し簡単にしたいところだけど、いい方法が思いつかなかった。
共役とか使えばシンプルになりそうな気もする。
テストを走らせるコードで
ruby2.5
data[:test_data].map{ | number:, src:, expected: |
#略
}
とかけるのがちょっと嬉しかった。（シンタックスハイライト...）
@yancya さんありがとう( see https://qiita.com/yancya/items/c557864f307d429bbde4 )