Click here for the problem http://nabetani.sakura.ne.jp/hena/ord17foldcut/
Click here for other sample answers http://qiita.com/Nabetani/items/ebd9d7deb30c57447806
In the method I first thought about later, the amount of array data increases as the number of folds increases, so I always tried to process with a 3x3 array. It feels like folding and reducing the array data, stretching the data c in the center and pushing it to the end like a rice cake to return it to 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)
Commentary:
def solve(data): #Input data example:'LRTB-br'
fold, (cut_y, cut_x) = data.split('-')
#Input data split.'-'The left side divided by is the folding instruction, and the right side is the vertical and horizontal positions of the cutting corner.
paper = reduce(lambda p,f: eval(f+'(p)'), fold, [[0,0,0],[0,1,0],[0,0,0]])
#Initial array p corresponding to folding paper:Even if the circumference is cut, no holes will be opened, so 0, and the number of paper folds in the center is 1.
# [ [ 0, 0, 0 ],Upper row: [upper left,Nakagami,Upper right]
# [ 0, 1, 0 ],Middle row: [Middle left,Middle middle,Middle right]
# [ 0, 0, 0 ] ]Lower row: [Lower left,Nakashita,Lower right]
#Folding function L for each folding instruction character with reduce(p)Or R(p)Or T(p)Or B(p)To make a paper
return str(paper[{'t':0,'b':-1}[cut_y]][{'l':0,'r':-1}[cut_x]]/4)
# paper[{'t':0,'b':-1}{cut_y]]On the top of the paper(0 is the first element)Or lower row(-1 is the final element)choose
# {'l':0,'r':-1}{cut_y]On the left(0 is the first element)Or right(-1 is the final element)choose
#The number of holes, str, is the number of folds of the specified corners of the folded paper divided by 4.()Stringized with
L = lambda p: [[c+c, c+c, l+r] for l,c,r in p] #Fold the left side to the right
#Example:Initial state Left is added to right, middle is doubled, left is the same as middle
# p l, c, r c+c,c+c,l+r
# [[0, 0, 0] [[0, 0, 0]
# [0, 1, 0] -> [2, 2, 0]No hole will be opened no matter where you cut the square
# [0, 0, 0]] [0, 0, 0]]
R = lambda p: [[l+r, c+c, c+c] for l,c,r in p] #Fold the right side to the left
#Example:Above state Add right to left, medium double, right same as middle
# p l, c, r l+r,c+c,c+c
# [[0, 0, 0] [[0, 0, 0]
# [2, 2, 0] -> [2, 4, 4]No hole will be opened no matter where you cut the square
# [0, 0, 0]] [0, 0, 0]]
T = lambda p: zip(*[[c+c, c+c, t+b] for t,c,b in zip(*p)]) #Fold the top down
#Example:Vertical and horizontal swap with the above state zip, left(Up)Right(under)Add to, double the middle, the left is the same as the middle, zip back
# p zip(*p) t, c, b c+c,c+c,t+b zip(*[...])zip*Takes the array contents as an argument
# t [[0, 0, 0] [[0, 2, 0] [[4, 4, 0] [[4, 8, 8]If you cut the upper left, the hole is 1
# c [2, 4, 4] -> [0, 4, 0] -> [8, 8, 0] -> [4, 8, 8]If you cut the upper right, the hole is 2
# b [0, 0, 0]] [0, 4, 0]] [8, 8, 0]] [0, 0, 0]]If you cut the bottom, the hole is 0
B = lambda p: zip(*[[t+b, c+c, c+c] for t,c,b in zip(*p)]) #Fold the bottom up
#Example:Vertical and horizontal swap with the above state zip, right(under)Left(Up)に加算、中2倍、underは中と同じ、zipで戻す
# p zip(*p) t, c, b t+b,c+c,c+c zip(*[...])zip*Takes the array contents as an argument
# t [[4, 8, 8] [[4, 4, 0] [[4, 8, 8] [[4, 8, 8]If you cut the upper left, the hole is 1
# c [4, 8, 8] -> [8, 8, 0] -> [8,16,16] -> [8,16,16]If you cut the upper right, the hole is 2
# b [0, 0, 0]] [8, 8, 0]] [8,16,16]] [8,16,16]]Lower left is 2, lower right is 4
The first method I thought of was to prepare array data of sufficient size to look like paper, fold it, and count the number of folds. Folding instruction Prepare a square array paper with a side length size according to the length of the fold (number of times of folding), and initialize the initial value with the number of folds of 1. However, the initial value (number of folds) is 0 because no holes can be made even if the outer circumference is cut. Each time it is folded, the values of the overlapping positions are added to halve the size of the array paper. The number of holes is the number of folds of the cut corner cut divided by 4 because the hole is made by cutting the corner.
#!/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" );
Recommended Posts