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

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

More than 5 years have passed since last update.

問題はこちら
http://nabetani.sakura.ne.jp/hena/ord17foldcut/

他の解答例はこちら
http://qiita.com/Nabetani/items/ebd9d7deb30c57447806

後述の最初に考えた方法では、折り畳み回数が多くなると配列データ量が膨大になるため、常に3x3の配列で処理するようにしてみました。
折りたたんで小さくなった配列データを、中央のデータcを伸し餅のように端まで押し伸ばして3x3に戻す感じです。

L = lambda p: [[c+c, c+c, l+r] for l,c,r in p]
R = lambda p: [[l+r, c+c, c+c] for l,c,r in p]
T = lambda p: zip(*[[c+c, c+c, t+b] for t,c,b in zip(*p)])
B = lambda p: zip(*[[t+b, c+c, c+c] for t,c,b in zip(*p)])

def solve(data):
    fold, (cut_y, cut_x) = data.split('-')
    paper = reduce(lambda p,f: eval(f+'(p)'), fold, [[0,0,0],[0,1,0],[0,0,0]])
    return str(paper[{'t':0,'b':-1}[cut_y]][{'l':0,'r':-1}[cut_x]]/4)

解説:

def solve(data):             # 入力data例:'LRTB-br'
    fold, (cut_y, cut_x) = data.split('-')
    # 入力データ分割。'-'で分割した左側は折畳み指示、右側は切る角の上下位置と左右位置

    paper = reduce(lambda p,f: eval(f+'(p)'), fold, [[0,0,0],[0,1,0],[0,0,0]])
    # 折り畳む紙に相当する初期配列p: 周囲は切っても穴が開かないので0、中央は紙の折重なり数1
    #   [ [ 0, 0, 0 ],       上段: [左上, 中上, 右上]
    #     [ 0, 1, 0 ],       中段: [左中, 中中, 右中]
    #     [ 0, 0, 0 ] ]      下段: [左下, 中下, 右下]
    # reduceで折畳み指示文字毎に 折畳み関数L(p)かR(p)かT(p)かB(p)を呼び出してpaperを作る

    return str(paper[{'t':0,'b':-1}[cut_y]][{'l':0,'r':-1}[cut_x]]/4)
    # paper[{'t':0,'b':-1}{cut_y]]で紙の上段(0は先頭要素)か下段(-1は最終要素)を選択
    # {'l':0,'r':-1}{cut_y]で左(0は先頭要素)か右(-1は最終要素)を選択
    # 折り畳んだ紙の指定された角の折重なり数を4で割った値が穴の数、str()で文字列化

L = lambda p: [[c+c, c+c, l+r] for l,c,r in p]   # 左側を右側に折り畳む
    # 例:初期状態  左を右に加算、中は2倍、左は中と同じに
    # p l, c, r    c+c,c+c,l+r
    # [[0, 0, 0]   [[0, 0, 0]
    #  [0, 1, 0] -> [2, 2, 0]    四角のどこを切っても穴は開かない
    #  [0, 0, 0]]   [0, 0, 0]]

R = lambda p: [[l+r, c+c, c+c] for l,c,r in p]   # 右側を左側に折り畳む
    # 例:上記状態  右を左に加算、中は2倍、右は中と同じに
    # p l, c, r    l+r,c+c,c+c
    # [[0, 0, 0]   [[0, 0, 0]
    #  [2, 2, 0] -> [2, 4, 4]    四角のどこを切っても穴は開かない
    #  [0, 0, 0]]   [0, 0, 0]]

T = lambda p: zip(*[[c+c, c+c, t+b] for t,c,b in zip(*p)]) # 上側を下側に折り畳む
    # 例:上記状態  zipで縦横入替、左(上)を右(下)に加算、中2倍、左は中と同じ、zipで戻す
    #   p      zip(*p) t, c, b    c+c,c+c,t+b  zip(*[...]) zipの*は配列内容を引数に
    # t [[0, 0, 0]   [[0, 2, 0]   [[4, 4, 0]   [[4, 8, 8]  左上を切ると穴は1
    # c  [2, 4, 4] -> [0, 4, 0] -> [8, 8, 0] -> [4, 8, 8]  右上を切ると穴は2
    # b  [0, 0, 0]]   [0, 4, 0]]   [8, 8, 0]]   [0, 0, 0]] 下を切ると穴は0

B = lambda p: zip(*[[t+b, c+c, c+c] for t,c,b in zip(*p)]) # 下側を上側に折り畳む
    # 例:上記状態  zipで縦横入替、右(下)を左(上)に加算、中2倍、下は中と同じ、zipで戻す
    #   p      zip(*p) t, c, b    t+b,c+c,c+c  zip(*[...]) zipの*は配列内容を引数に
    # t [[4, 8, 8]   [[4, 4, 0]   [[4, 8, 8]   [[4, 8, 8]  左上を切ると穴は1
    # c  [4, 8, 8] -> [8, 8, 0] -> [8,16,16] -> [8,16,16]  右上を切ると穴は2
    # b  [0, 0, 0]]   [8, 8, 0]]   [8,16,16]]   [8,16,16]] 左下は2、右下は4

最初に考えた方法は、紙に見立てた十分な大きさの配列データを用意して実際に折り畳んで折重なり数を数える方法。
折畳み指示foldの長さ(折り畳み回数)に応じて1辺の長さsizeの正方形配列paperを用意し、折り重なり数1で初期値初期化しておく。ただし、外周部は切っても穴ができないので初期値(折重なり数)は0。
折り畳む度に折り重なる位置同士の値を加算して配列paperの大きさを半分ずつにしていく。
角を切って穴ができるのは4枚折り重なった場所なので、切る角cutの折重なり数を4で割った値が穴の数。

#!/usr/bin/env python
#-*- coding:utf8 -*-

L = lambda p: [[l+r for l,r in zip(y[:len(y)/2][::-1], y[len(y)/2:])] for y in p]
R = lambda p: [[l+r for l,r in zip(y[:len(y)/2], y[len(y)/2:][::-1])] for y in p]
T = lambda p: [[t+b for t,b in zip(*y)] for y in zip(p[:len(p)/2][::-1], p[len(p)/2:])]
B = lambda p: [[t+b for t,b in zip(*y)] for y in zip(p[:len(p)/2], p[len(p)/2:][::-1])]

def solve(data):
    fold, (cut_y, cut_x) = data.split('-')
    size = 2<<len(fold)
    paper = [[0]*size] + [[0]+[1]*(size-2)+[0] for y in xrange(size-2)] + [[0]*size]
    paper = reduce(lambda p,f: eval(f+'(p)'), fold, paper)
    return str(paper[{'t':0,'b':-1}[cut_y]][{'l':0,'r':-1}[cut_x]]/4)

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

0, test( "RRTRB-bl", "6" );
1, test( "R-tr", "0" );
2, test( "L-br", "0" );
3, test( "T-tl", "0" );
4, test( "B-tl", "0" );
5, test( "BL-br", "0" );
6, test( "LB-tl", "0" );
7, test( "RL-tl", "0" );
8, test( "BL-tl", "0" );
9, test( "TL-bl", "0" );
10, test( "RT-tr", "1" );
11, test( "TRB-tl", "0" );
12, test( "TRL-bl", "0" );
13, test( "TRB-br", "2" );
14, test( "LLB-bl", "2" );
15, test( "RTL-tr", "1" );
16, test( "LBB-tr", "0" );
17, test( "TLL-tl", "2" );
18, test( "RLRR-tr", "0" );
19, test( "BBTL-tl", "4" );
20, test( "TBBT-tr", "0" );
21, test( "LLBR-tl", "0" );
22, test( "LBRT-tl", "2" );
23, test( "RLBL-bl", "4" );
24, test( "BRRL-br", "3" );
25, test( "TBBTL-tl", "8" );
26, test( "TLBBT-br", "0" );
27, test( "LRBLL-br", "7" );
28, test( "TRRTT-br", "6" );
29, test( "BBBLB-br", "0" );
30, test( "RTTTR-tl", "4" );
31, test( "BBLLL-br", "6" );
32, test( "RRLLTR-tr", "16" );
33, test( "TTRBLB-br", "8" );
34, test( "LRBRBR-bl", "14" );
35, test( "RBBLRL-tl", "8" );
36, test( "RTRLTB-tl", "12" );
37, test( "LBLRTR-tl", "14" );
38, test( "RRLTRL-tl", "16" );
39, test( "TBLTRR-br", "12" );
40, test( "TTTRLTT-bl", "30" );
41, test( "TBBRTBL-tr", "15" );
42, test( "TRTRTLL-tr", "28" );
43, test( "TLLRTRB-tr", "24" );
44, test( "RLLBRLB-tr", "15" );
45, test( "LTLRRBT-tr", "32" );
46, test( "RBBRBLT-br", "21" );
47, test( "LLRLRLR-tr", "0" );
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