先日のSECCON 2014 quals OnlineのProgramming 300 あみだくじを試合終了後にときましたので、置いておきます。
二時間程度かかりました。もうちょっと早く綺麗に解けるようにならないとな・・・。
Prog300 あみだくじ
問題ファイル:amida
実行ファイルが渡されるので、解いてねと言う問題。
書いたプログラムが以下。(python3)
# -*- coding: utf-8 -*- import sys from subprocess import Popen, PIPE # 元の文章を渡すとhead(数字行), mondai(あみだ本体), tail(*行) のリストを返す def transform(original): # 最初のNo~と最後の空白行を削除 # top => 最初の行, bottom => 最後の行 original = original[1:-1] top = list(original[0]) bottom = list(original[-1]) # あみだが横に倒れている場合 if "".join(top).find('--') != -1: trans = [] for m in original: t = m.replace('-', '#') t = t.replace('|', '-') t = t.replace('#', '|') trans.append(t) trans = list(map(list, zip(*trans))) # 転置 original = ["".join(tr) for tr in trans] top = list(original[0]) bottom = list(original[-1]) # 最終行が数字で始まっていたら上下を反転 if bottom[0] == '1' or bottom[0] == '8': trans = [] for m in original: trans.insert(0, m) original = trans top = list(original[0]) bottom = list(original[-1]) # 1 2 3 4 5 6 7 8 のように空白が開いている場合は、各行から冗長部分を削除 if (top[0] == '1' or top[0] == '8') and "".join(top).find(' ') != -1: i = 0 j = 0 while i < len(top) - 1: while top[j:j + 2] == [' ', ' ']: for k in range(len(original)): tmp = list(original[k]) del tmp[j + 1] original[k] = "".join(tmp) del top[j + 1] i += 1 j += 1 head = list(original[0]) body = original[1:-1] # headとtailを除いた部分 tail = list(original[-1]) return (head, body, tail) def main(): p = Popen(["./amida"], stdout=PIPE, stdin=PIPE, shell=True) while True: print('=' * 50) # 標準出力から問題を取得する msg = "" while True: c = p.stdout.read(1) if not c or c == b'?': break msg += c.decode('utf-8') print(msg) original = ["".join(list(m.replace('\x00', ''))) for m in msg.split('\n')] # 整形処理 head, body, tail = transform(original) print("#" * 30) print("".join(head)) print("\n".join(body)) print("".join(tail)) print("#" * 30) # solve for i in range(len(body)): for j in range(len(body[0])): if body[i][j] == '-': # swap tmp = head[j - 1] head[j - 1] = head[j + 1] head[j + 1] = tmp answer = head[tail.index('*')] print("Answer:", answer) # 答えを投げる p.stdin.write((answer + '\n').encode()) p.stdin.flush() if __name__ == '__main__': sys.exit(main())
渡された問題を標準出力から読み取り、整形して、解いて、標準入力から渡しています。
結局あみだくじは橋が出てきたら数字を入れ替えて行って、入れ替え終わったら*の位置と照合するだけでいいので、整形のほうがメインになってきます。
この問題、問題が進んでいくたびに上下が逆になったり、橋の間隔が大きくなったり、横になったりするので、それぞれに応じて整形してあげなければいけませんでした(ここが一番つらかった)
問題の出現順序が変わらなかったので、「一問あたりの制限時間あるけどどうせ100くらいなら手作業でいけるっしょ〜w」と思い、競技中は順番に入力して解いてたんですが、100問超えくらいから徐々に怪しくなって、160問くらいでつらくなったのでやめました。
その後、やっぱスクリプト書こう!!ってことで書き始めたんですが、もう考える気力と集中力は残ってなかった。結局解けず・・・(あたがわさんに任せとけばよかったなぁ・・・)
実はPythonのsubprocess.Popen使って標準入出力を制御する方法がわからず、ぐぐっても見つけきれなかったので始めは
$ netcat -l -p 40000 -e ./amida
して、それに対してTelnetlibから入出力を受け取って解いてました w
メンバーさんに聞いたらやっぱりPopenでできるみたいだよ!とURL付きで教えてくれたので、それを参考に組みました。勉強が足りないな・・・・。