Edited at

第18回オフラインリアルタイムどう書くの参考問題をPythonで

More than 5 years have passed since last update.

問題はこちら

http://nabetani.sakura.ne.jp/hena/ord18mafovafo/

実行結果はこちら

http://ideone.com/ZSJEH2

他の方々の解答例はこちら

http://qiita.com/Nabetani/items/373105e7fafd12f5e9fd

「第18回オフラインリアルタイムどう書く」横浜へなちょこプログラミング勉強会のイベント告知はこちら

http://atnd.org/events/47025 (2014/02/01(土曜日)開催)

#!/usr/bin/env python


# FOLD = { operation:(front side fold, back side fold), ... }
# '0':front side paper, '1':back side paper, 'm':mountain fold, 'V':valley fold
FOLD = {'L':('1V0','1m0'), 'J':('0V1','0m1'), 'Z':('0m1V0','1m0V1'), 'U':('1V0V1','0m1m0'), 'S':('0V1m0','1V0m1'), '':('','')}

solve = lambda operation, side=0: ''.join(solve(operation[1:], int(f)) if f in '01' else f for f in FOLD[operation[:1]][side])

def test(data, correct):
answer = solve(data)
print 'xo'[answer==correct], data, correct, answer

0, test( "JZ", "mVVmV" );
1, test( "J", "V" );
2, test( "L", "V" );
3, test( "Z", "mV" );
4, test( "U", "VV" );
5, test( "S", "Vm" );
6, test( "JL", "VVm" );
7, test( "JS", "VmVVm" );
8, test( "JU", "VVVmm" );
9, test( "LU", "mmVVV" );
10, test( "SL", "VVmmV" );
11, test( "SS", "VmVVmmVm" );
12, test( "SU", "VVVmmmVV" );
13, test( "SZ", "mVVmVmmV" );
14, test( "UL", "mVVVm" );
15, test( "UU", "mmVVVVmm" );
16, test( "UZ", "mVVmVVmV" );
17, test( "ZJ", "VmmVV" );
18, test( "ZS", "VmmVmVVm" );
19, test( "ZZ", "mVmmVVmV" );
20, test( "JJJ", "VVmVVmm" );
21, test( "JJZ", "mVVmVVmVmmV" );
22, test( "JSJ", "VVmmVVmVVmm" );
23, test( "JSS", "VmVVmmVmVVmVVmmVm" );
24, test( "JUS", "VmVVmVVmVVmmVmmVm" );
25, test( "JUU", "mmVVVVmmVVVmmmmVV" );
26, test( "JUZ", "mVVmVVmVVmVmmVmmV" );
27, test( "LJJ", "VmmVVVm" );
28, test( "LLS", "VmmVmVVmVVm" );
29, test( "LLU", "mmmVVVmmVVV" );
30, test( "LLZ", "mVmmVVmVVmV" );
31, test( "LSU", "mmVVVmmmVVVVmmmVV" );
32, test( "LSZ", "mVVmVmmVVmVVmVmmV" );
33, test( "LZL", "mmVVmVVmmVV" );
34, test( "LZS", "VmmVmVVmVVmmVmVVm" );
35, test( "LZU", "mmmVVVmmVVVmmmVVV" );
36, test( "SJL", "VVmVVmmmVVm" );
37, test( "SLU", "mmVVVVmmmVVmmmVVV" );
38, test( "SLZ", "mVVmVVmVmmVmmVVmV" );
39, test( "SSU", "VVVmmmVVVmmVVVmmmmVVVmmmVV" );
40, test( "SUJ", "mVVVmVVmmmVmmVVVm" );
41, test( "SUS", "VmVVmVVmVVmmVmmVmmVmVVmVVm" );
42, test( "SZZ", "mVmmVVmVVmVmmVVmVmmVmmVVmV" );
43, test( "UJJ", "VmmVVVmVVmm" );
44, test( "ULU", "mmmVVVmmVVVVmmmVV" );
45, test( "ULZ", "mVmmVVmVVmVVmVmmV" );
46, test( "UUU", "VVmmmmVVVmmVVVVmmVVVmmmmVV" );
47, test( "ZJU", "VVVmmmVVmmmVVVVmm" );
48, test( "ZLS", "VmVVmmVmmVmVVmVVm" );
49, test( "ZSJ", "VVmmVmmVVmmVVVmmV" );
50, test( "ZUJ", "mVVVmmVmmmVVmVVVm" );
51, test( "JJLJ", "mVVVmmVVmVVmmmV" );
52, test( "JLJJ", "VmmVVVmVVmmmVVm" );
53, test( "JLJL", "VmmVVVmVVmmmVVm" );
54, test( "LJJL", "VVmmVmmVVVmVVmm" );
55, test( "LLJJ", "VmmmVVmVVmmVVVm" );
56, test( "SZUS", "VmVVmVVmmVmmVmmVmVVmVVmVVmVVmmVmmVmmVmVVmVVmVVmmVmmVmmVmVVmVVmmVmmVmmVmVVmVVmVVm" );
57, test( "ULLS", "VmmVmmVmVVmVVmmVmVVmVVmVVmmVmmVmVVm" );
58, test( "JJJJZJ", "VmmVVVmmVVmVVmmVVmmmVVmVVmmVVVmmVVmmVmmVVmmmVVmVVmmVVVmmVVmVVmmVVmmmVVmmVmmVVVmmVVmmVmmVVmmmVVm" );
59, test( "JULLLJ", "mmVmmVVmmmVVmVVVmmVmmVVVmmVVmVVVmmVmmVVmmmVVmVVVmmVmmVVVmmVVmVVmmmVmmVVmmmVVmVVmmmVmmVVVmmVVmVV" );
60, test( "LJJJUL", "mVVVmVVmmmVVmVVVmmVmmmVmmVVVmVVmmmVmmVVVmmVmmmVVmVVVmVVmmmVVmVVVmmVmmmVVmVVVmVVmmmVmmVVVmmVmmmV" );
61, test( "LJSJJL", "VVmVVmmVVVmmVmmmVVmVVmmmVVmmVmmVVVmVVmmmVVmmVmmVVVmVVmmVVVmmVmmmVVmVVmmVVVmmVmmVVVmVVmmmVVmmVmm" );
62, test( "LZLLLJ", "mmVmmVVmmmVVmVVmmmVmmVVVmmVVmVVVmmVmmVVmmmVVmVVVmmVmmVVVmmVVmVVmmmVmmVVmmmVVmVVVmmVmmVVVmmVVmVV" );
63, test( "SJJJJL", "VVmVVmmVVVmmVmmVVVmVVmmmVVmmVmmVVVmVVmmVVVmmVmmmVVmVVmmmVVmmVmmmVVmVVmmVVVmmVmmVVVmVVmmmVVmmVmm" );
64, test( "ZLJLJL", "VmmVVVmmVmmmVVmVVmmVVVmVVmmmVVmmVmmVVVmmVmmmVVmmVmmVVVmVVmmmVVmVVmmVVVmmVmmmVVmVVmmVVVmVVmmmVVm" );

解説

doukaku_18.png

紙の表側を'0'、裏側を'1'、山折を'm'。谷折りを'V'とする。

表側のL折り結果は (裏, 谷, 表) なので '1V0'。

裏側のL折り結果は (裏, 山, 表) なので '1m0'。

L折りから折り畳み結果への変換を FOLD = {'L':('1V0','1m0')} という辞書データにしておく。

表側のL折り結果は FOLD['L'][0] で '1V0' が取り出せる。

裏側のL折り結果は FOLD['L'][1] で '1m0' が取り出せる。

L折り1回だけであれば、'1V0' の折り目データの 'V' だけを取り出したのが答になる。

LL折りの場合、'1V0' の紙部分を表す 1 と 0 をそれぞれ L折りした結果に置き換えればよいので、

LL折り結果 = 表側のL折り結果に対してさらにL折り操作

→ FOLD['L'][0] をさらにL折り操作

→ '1V0' をさらにL折り操作 (1と0に対してL折り操作)

→ FOLD['L'][1]+'V'+FOLD['L'][0]

→ '1m0'+'V'+'1V0'

→ '1m0V1V0'

となり、折り目文字だけを集めて 'mVV' が答えとなる。

これをプログラムにすると以下のようになる。


  1. 操作文字列から最初の操作文字を取り出す

  2. 操作文字に対する変換辞書をひいて折畳み結果に変換する

  3. 続く操作があれば、折畳み結果の 0 および 1 に対して、2番目以降の操作を再帰的に行う

  4. 最後に 0 および 1 を取り除く作業は、最後に空操作として''に置き換えることにする。
    これは、操作文字を operation[0] で取り出すと操作文字がなくなったときにエラーになってしまうが、operation[:1] と書くことで操作がなくなったときは空文字になり、空文字に対する折畳み結果を '':('','') として変換辞書に登録しておけば、操作文字がなくなったときに'0'と'1'が空文字に置き換わる。

solve = lambda operation, side=0: ...

# solve関数定義。以下に示すdefを使った関数と同じ
# def solve(operation, side=0):
# return ...
operation[:1]
# 操作文字列の最初の操作文字を取り出す
# operationが空文字列だった場合には '' になる
FOLD[operation[:1]][side]
# 操作文字列の最初の操作文字に対する折畳み文字列を取り出す
# operationが空文字列だと '' になる
for f in FOLD[operation[:1]][side]
# 折畳み文字列のそれぞれの文字に対して
operation[1:]
# 2番目以降の操作文字列
solve(operation[1:], int(f)) if f in '01' else f
# '0' か '1' なら2番目以降の操作を再帰的に行う、'm' か 'V' ならその文字
# 最後の操作で残った '0' と '1' は solve('', side) を呼び出して '' になる
''.join(...)
# 部分部分の折り畳み文字列を隙間なく結合して文字列にする