Help us understand the problem. What is going on with this article?

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

問題はこちら
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(...)
    # 部分部分の折り畳み文字列を隙間なく結合して文字列にする
shiracamus
元、低レイヤーエンジニア。 現、サイバーセキュリティ研究者。 使用言語は、C, Lisp, Java, Python, C#, JavaScript/Node.js。 経験アセンブリ言語は Z80, 6502, 6809, 68000, SPARC, PowerPC, ARM, x86/x64。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away