「第28回オフラインリアルタイムどう書く」のへなちょこ解答(Ruby)

土曜日は久しぶりにどう書くに行ってきました。

オフラインリアルタイムどう書くとは
皆で共通のお題を好きなプログラミング言語で解いて、結果を見せ合う会です。

今回の問題はこちら。

鍋谷さんの中二センスに完敗です。z軸の移動がないから螺旋ではないのでは?と思ったけど、本当に螺旋の問題を出されても困るので黙っておこうと思います。

自分の解答

初めてRubyで参戦しました。

時間内にデバッグが終わらず悔しい思いをしましたが、翌日1行足したらテストが通りました。

#!/usr/bin/ruby
# http://nabetani.sakura.ne.jp/hena/ord28spirwa/
 
def parse(input)
    wall, day = input.split(":")
    n, e, s, w = wall.split(",")
    rs = [0,0]
    1.upto(n.to_i) { |y| rs << [0, y] }
    1.upto(e.to_i) { |x| rs << [x, 0] }
    1.upto(s.to_i) { |y| rs << [0, -y] }
    1.upto(w.to_i) { |x| rs << [-x, 0] }
    return rs, day
end
 
def check(wall, n, e, s, w)
    if wall.include?(e) && wall.include?(w) && wall.include?(n)
        return s, "S"
    elsif wall.include?(n) && wall.include?(e) && wall.include?(s)
        return w, "W"
    elsif wall.include?(e) && wall.include?(s) && wall.include?(w)
        return n, "N"
    elsif wall.include?(n) && wall.include?(s) && wall.include?(w)
        return e, "E"
    elsif wall.include?(s) && wall.include?(w)
        return e, "E"
    elsif wall.include?(n) && wall.include?(w)
        return s, "S"
    elsif wall.include?(n) && wall.include?(e)
        return w, "W"
    elsif wall.include?(e) && wall.include?(s)
        return n, "N"
    elsif wall.include?(n)
        return w, "W"
    elsif wall.include?(e)
        return n, "N"
    elsif wall.include?(s)
        return e, "E"
    elsif wall.include?(w)
        return s, "S"
    end
    return nill
end
 
def walk(wall, posi)
    x, y = posi[0], posi[1]
    n, e, s, w = [x, y+1], [x+1, y], [x, y-1], [x-1, y]
    nxt, ch = check(wall, n, e, s, w)
    wall << nxt
    return wall, nxt, ch
end
 
def solve(wall, day)
    posi = [1, 1]
    wall << posi
    ch = ""
    0.upto(day) {|d|
        wall, posi, ch = walk(wall, posi)
    }
    return ch
end
 
DATA.each{|line|
    num, input, expected = line.split( /\s+/ )
    
    wall, day = parse(input)
    actual = solve(wall, day.to_i)
    
    error = (actual == expected) ? "" : " ** expected is : #{expected} **"
    puts "%s -> %s %s" % [input, actual, error]
}
__END__
#0 2,3,5,4:85 S
#1 1,2,3,4:1 E
#2 1,2,3,4:2 S

考え方

まず、入力値をx座標とy座標で表現される壁に変換します。中央が(0, 0)です。

次に、現在地に隣接する東西南北のマス目が「壁かどうか」をチェックします。どの方角が壁であるかによって、進める方向が一意に定まることを利用します。

たとえば、0日目。南と西が壁のときは、東に進みます。

1日目。0日目にいた場所はもう通れないので、以後は壁とみなします。進行方向のルールは0日目と同じ。南と西が壁のときは、東に進みます。

2日目。1日目にいた場所は、以後壁とみなします。西が壁のときは、南に進みます。

3日目。2日目にいた場所は、以後壁とみなします。北と西が壁のときは、南に進みます。

……といったルールを表現したのが、上のひどいif文です。ローテートすれば4分の1で済む気もしますが、全部書いてしまいました。

最後に、上記を旅の日数分だけ繰り返します。

「どこから移動してきたか」という状態を持たず、今いる場所の隣接マスだけを見て判定しているのがポイントです。鍋谷さんから指摘があったとおり、壁の形が凸型だから使える戦略でした。

他の人の解答

他の人の解答では、3方向の移動をまとめて1組と考える戦略や、「どこから移動してきたか」という状態を持つ戦略がありました。

詳しくは、Qiitaのコメント欄からお楽しみください。

第28回オフラインリアルタイムどう書くの問題 - Qiita

どう書くはRubyで解く人が多いので、いざ自分がRubyを書こうとした時に勉強になるのでありがたいですね。今回は、tap breakってなんやねんと思いました。

いつも通り楽しかったです。鍋谷さん、皆さん、ありがとうございました。