問題と他者の回答はこちら
http://qiita.com/mtsmfm/items/6d9112fcc568908caaba
path は登山道。["A"~"H"] 毎の [頂上~麓の階段(横道の数+1)] の2次元配列。
path の内容は、真っすぐ上る階段は 0
、右の登山道に移動する階段は +1
、左の登山道に移動する階段は -1
、落石で通れない階段は None
。
step は階段の位置。頂上は [0]
、麓は [-1]
(最後の要素)。
direction は横道の方角。1~8。
across は横道の順序および方角を表す文字列。
place および rock は登山道の位置。"A"~"H"。
index は登る/降りる位置。0~7 ("A"~"H"に対応するインデックス番号)。
# -*- coding:utf-8 -*-
PATH = "ABCDEFGH"
def make_path(across):
path = [[0] * (len(across) + 1) for i in xrange(len(PATH))]
for step, direction in enumerate(across):
index = int(direction) % len(PATH)
path[index+0][step] = -1
path[index-1][step] = +1
return path
def fall_rock(path, index):
for step in xrange(len(path[0])):
next_index = (index + path[index][step]) % len(PATH)
path[index][step] = None
index = next_index
def climb(path, index):
for step in xrange(len(path[0]) - 1, -1, -1):
if path[index][step] is None:
return False
index = (index + path[index][step]) % len(PATH)
return True
def solve(data):
across, rock = data.split(':')
path = make_path(across)
fall_rock(path, PATH.index(rock))
climbable_places = [place
for index, place in enumerate(PATH)
if climb(path, index)]
return ''.join(climbable_places)
if __name__ == '__main__':
testdata = (
(0, "2512:C", "DEFGH"),
(1, "1:A", "CDEFGH"),
(2, ":C", "ABDEFGH"),
(3, "2345:B", "AGH"),
(4, "1256:E", "ABCDH"),
(5, "1228:A", "ADEFG"),
(6, "5623:B", "AEFGH"),
(7, "8157:C", "ABDEFGH"),
(8, "74767:E", "ABCFGH"),
(9, "88717:D", "ABCEFGH"),
(10, "148647:A", "ACDEFH"),
(11, "374258:H", "BCDEFH"),
(12, "6647768:F", "ABCDEH"),
(13, "4786317:E", "ABFGH"),
(14, "3456781:C", ""),
(15, "225721686547123:C", "CEF"),
(16, "2765356148824666:F", "ABCDEH"),
(17, "42318287535641783:F", "BDE"),
(18, "584423584751745261:D", "FGH"),
(19, "8811873415472513884:D", "CFG"),
(20, "74817442725737422451:H", "BCDEF"),
(21, "223188865746766511566:C", "ABGH"),
(22, "2763666483242552567747:F", "ABCG"),
(23, "76724442325377753577138:E", "EG"),
(24, "327328486656448784712618:B", ""),
(25, "4884637666662548114774288:D", "DGH"),
(26, "84226765313786654637511248:H", "DEF"),
(27, "486142154163288126476238756:A", "CDF"),
(28, "1836275732415226326155464567:F", "BCD"),
(29, "62544434452376661746517374245:G", "G"),
(30, "381352782758218463842725673473:B", "A"),
)
def test():
for no, data, correct in testdata:
answer = solve(data)
print '%s #%d "%s" "%s" -> "%s"' % (('NG!!','OK ')[answer == correct], no, data, correct, answer)
test()
横道設定が "2512"
、落石位置が C
の場合の解説
path は登山道。["A"~"H"] 毎の [頂上~麓の階段(横道の数+1)] の2次元配列。
真っすぐ上る場合は +0 、右にずれる場合は +1、左にずれる場合は -1、落石で通行できない場合は None。
初期状態の登山道。すべて真っすぐ上る道。
横道の設定が 2512