問題はこちら
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" );