Exact Cover Puzzle
Python 2, 864 bytes
- Thanks to Stephen for finding a bug.
- The string parsing could be golfed significantly, as the input format is stricter than what it can handle.
def V(C,S=0,D=-1,J=0,H=[],E=enumerate,R=range,r=str.replace,s=str.split,e="!"):
if[]<C*0:
J=0;N=[J]*26;K=[]
for c in s(r(r(r(C,"[",""),"]","")," ","*"),2*"\n"):
c=[list(_)for _ in s(c,"\n")]
for x,_ in E(c[0]):
if all(c[y][x]<">"for y,_ in E(c)):
for y,_ in E(c):c[y][x]=e
for j,y in E(c):
y="".join(y)
while"!!"in y:y=r(y,2*e,e)
c[j]=s(y,e)
K+=[],[],[],[];J+=4
for y in c:
while""in y:y.remove("")
for j,x in E(y):K[j+J-4]+=x,
for k in K:
if all(k)and k:N[ord(k[0][0])-97]=[[x>"*"for x in y]for y in k]
while 0in N:N.remove(0)
C=N
if[]>S:S=[0]*36
if-~D>0:
Y=J/6;j=0
for y in C[D]:
X=J%6
for x in y:
if x:
if X>5or Y>5or S[X+Y*6]:return
S[X+Y*6]=x
X+=1
Y+=1
if~-len(C)==D:
if 0in S:return
for h in H[1:]+[J]:print"HAUL %c TO %c %d"%(65+j,65+h%6,h/6+1);j+=1
j/0
for j in R(36):V(C,S[:],-~D,j,H*(D>=0)+[J])
Try it online!
Explanation
A lot of bytes are used to parse the two-dimensional crates inputted through a single string. Crates are represented as a nested list of boolean values.
After the crates are parsed, the function considers all possible positions of all crates. To do so, it iteratively calls itself. When it finds an impossible position (if the crate would be placed outside the deck or on top of another crate), it kills the current recursion tree branch to improve performance.
When it sees that a certain combination of placements resulted in a completely covered deck, it prints the recorded crate placement history and globally exits by attempting a hopeless division. The printed haul instructions are even sorted alphabetically.
Python 2, 812 bytes
def f(C,M=[],d=0,R=range,E=enumerate,L=len):
if C*0=="":
N=[0]*26;K=[];J=0
r=str.replace
for c in r(r(r(C,"[",""),"]","")," ","*").split("\n\n"):
c=[list(_)for _ in c.split("\n")]
for x in R(L(c[0])):
if all(c[y][x]=="*"for y in R(L(c))):
for y in R(L(c)):c[y][x]="!"
for j,y in E(c):
y="".join(y)
while"!!"in y:y=r(y,"!!","!")
c[j]=y.split("!")
for _ in"_"*L(c):K+=[],
for y in c:
for j,x in E(y):K[j+J]+=x,
J+=L(c)
for k in K:
if all(k)and k:N[ord(k[0][0])-97]=[[x!="*"for x in y]for y in k]
while 0in N:N.remove(0)
C=N
if d==L(C):
j=0;S=[j]*36
for c,k in E(C):
Y=M[c]/6
for y in k:
X=M[c]%6
for x in y:
if X<6>Y:S[X+Y*6]|=x
X+=1
Y+=1
if 0in S:return
for m in M:print"HAUL %c TO %c %d"%(65+j,65+m%6,1+m/6);j+=1
j/0
for j in R(36):f(C,M*(d>=0)+[j],d+1)
Try it online!
Explanation
The crate string is parsed and transformed into a listed nest of booleans representing each crate.
An iterative function generates all possible lists of length equal to the amount of crates given containing the integers 0 <= x < 36 (all possible ship deck positions). Every list is interpreted as an instruction to position all crates and tested. If the tested instruction list results in a deck with no empty spaces, the instruction list has to be valid and gets printed.
Being extremely inefficient, I did not test it on the provided test case, though on scenarios with fewer crates (see the TIO link). Because the algorithm searches through every possible arrangement, it tries to look at 36**10 = 3.656e15 of them. Yet in theory it should still work.
Python 3.6, 435 437 385 331 bytes
Call F() with the crate string.
def R(b,d,i=0):
if not d:return 1
(k,x),*d=d
while x:
if x&b<1and R(b|x,d):print(f'HAUL {k.upper()} TO {i%7+65:c} {i//7+1}');return 1
i+=1;x>>=1
def F(t,d={},e={}):
r=c=0
for a in t:
if'`'<a<'{':e[a]=x,y=e.get(a,(r,c));d[a]=d.get(a,0)+(1<<(48-(r-x)*7-(c-y)//3))
elif'\n'==a:r+=1;c=-1
c+=1
R(4432676798719,d.items())
Managed to golf it a lot more:
- Parse the crate string directly instead of using the
relibrary. - Used setdefault to save the first coordinate of a set of crates, so that the bitmask can be created when parsing the crate string. Eliminating a for loop.
import re
def R(b,d,i=0):
if not d:return 1
(k,x),*d=d
while x:
if not x&b and R(b|x,d):print(f'HAUL {k.upper()} TO {i%7+65:c} {i//7+1}');return 1
i+=1;x>>=1
def F(t,d={},n=0):
for r in t.split('\n'):
for m in re.finditer(r'(.)]',r):d[m[1]]=d.get(m[1],[])+[(n,m.start())]
n+=1
R(4432676798719,[(k,sum(1<<(48-(r-v[0][0])*7-(c-v[0][1])//3)for r,c in v))for k,v in d.items()])
Restructured the code to remove redundant loops.
Previous code built a list of all positions of a crate in
F()and then iterated over the list inR(). New code creates one position of a crate inF()andR()tries all possible positions.In previous code,
R()collected a possible solution inaandF()then iterated over the returned solution. In new code,R()prints the HAUL commands directly
import re
def R(b,d,a=[]):
if not d:yield a
for x in d[0]:
if not x&b:yield from R(b|x,d[1:],a+[x])
def F(t,d={},n=0):
for r in t.split('\n'):
for m in re.finditer(r'(.)]',r):d[m[1]]=d.get(m[1],[])+[(n,m.start())]
n+=1
for k,j in enumerate(next(R(4432676798719,[[sum(1<<(48-(r-v[0][0])*7-(c-v[0][1])//3)for r,c in v)>>i for i in range(48)]for k,v in d.items()]))):x=51-len(bin(j));print(f'HAUL {k+65:c} TO {x%7+65:c} {x//7+1}')
Explanation
The basic idea is to represent the ship's deck and the crates as bit maps. By using bitmaps, moving a crate becomes a shift of its bitmap and checking for overlap between crates becomes a bit-wise AND and test for zero.
Ungolfed code:
import re
def F(crate_string): # 3
coords = {}
row_no = 0
for row in crate_string.split('\n'): # 7
for match_obj in re.finditer('(.)]', row): # 9
crate_name = match_obj[1] # 11
col_no = match_obj.start() # 12
coords[crate_name] = coords.get(crate_name, []) + [(row_no, col_no)] # 13
row_no += 1
normed = {k:[(r-v[0][0], (c-v[0][1])//3) for r,c in v] for k,v in coords.items()} # 17
bitmaps = [(k,sum(1<<(48 - r*7 - c) for r,c in v)) for k,v in normed.items()] # 18
R(4432676798719, bitmaps) # 20
def R(used, bitmaps): # 22
if not bitmaps: # 23
return True # 24
shift = 0 # 25
(crate_name, crate_bitmap),*bitmaps = bitmaps # 26
while crate_bitmap: # 28
if not used & crate_bitmap: # 29
if R(used | crate_bitmap, bitmaps): # 30
print(f'HAUL {crate_name.upper()} TO {shift%7 + 65:c} {shift//7 + 1}') # 31
return True # 32
shift += 1 # 34
crate_bitmap >>= 1 # 35
return False # 37
F() parses the crate definition string and builds the bit maps. A regex searches (line 9) each line of the crate definition string for crates (a letter followed by a ']'). When a match is found, the corresponding (row,col) is added to a dictionary keyed by the letter (lines 11-13). For the example crate definition string given in the problem:
coords = {'a': [(0, 5), (0, 8), (0, 11), (1, 5), (1, 8), (1, 11)],
'b': [(0, 29), (1, 29), (2, 29)],
... }
The coordinates of each crate are normalized (line 17), so that each crate starts at (0,0) and each block is one unit wide (instead of 3 a la '[a]').
normed = {'a': [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)],
'b': [(0, 0), (1, 0), (2, 0)],
... }
A bitmap is then created for each crate based on the normalized coordinates (line 18).
The deck is treated as a 7 x 7 grid. Column 'G' and row 7 are used to detect when a shape extends off the board. A bitmap has a 1 if the crates would occupy the corresponding square on the deck. Bits 48 to bit to 42 correspond to squares A1 to A7, bits 41 to 35 correspond to squares B1 to B7, and so on.
bitmaps = [('a', 0b1110000_1110000_0000000_0000000_0000000_0000000_0000000),
('b', 0b1000000_1000000_1000000_0000000_0000000_0000000_0000000),
...
]
R(used, bitmaps) then uses the bitmaps to recursively search for crate placements that don't try to put two crates in the same square. used is a bitmask indicating which squares can't be used because they are already occupied by a crate or because they are off the board (i.e., column G and row 7). bitmaps is a list of crates that still need to be placed.
The base case for the recursion is when there are no more crates left to place, i.e., bitmaps is empty (line 23). In this case True is returned to indicate a solution has been found.
Otherwise, a crate name and its bitmap are popped off the list of bitmaps (line 26). While the crate bitmap is not empty (line 28), check if the current crate placement, represented by the crate bitmap, conflicts with any previously placed crates. At line 29, not used & crate_bitmap is False if used and crate_bitmap both have a 1 in the same bit position, indicating a conflict. If there is not a conflict, R() is called recursively (line 30) to try and place the remaining crates.
If the recursive call to R() returns True, it means that a solution has been found and that the current placement of the crates is part of that solution. So the corresponding command to move the crates is printed and True is propagated up the recursive calls (lines 31-32).
When created in F(), each crate bitmap represents the deck squares that would be occupied by the crates if they are placed at position A1. Shifting a bitmap one bit to the right corresponds to moving the crates to position A2. A seven bit right shift corresponds to moving the crates to B1, etc. For example, the following bitmaps represent crates 'a' at various positions:
0b1110000_1110000_0000000_0000000_0000000_0000000_0000000 represent crates 'a' at A1
0b0111000_0111000_0000000_0000000_0000000_0000000_0000000 represent crates 'a' at A2
0b0011100_0011100_0000000_0000000_0000000_0000000_0000000 represent crates 'a' at A3
...
0b0000000_1110000_1110000_0000000_0000000_0000000_0000000 represent crates 'a' at B1
...
If a possible placement of crates doesn't work because it conflicts with a previously placed crate (line 30) or because there is not a valid placement of the remaining crates (line 31). The crates are moved to a different position by shifting the bitmask right one bit (line 35). Shift keeps track of how many places the bit map has been shifted, which corresponds to the current position of the crates.
If the bitmap is empty (zero), it indicates that all possible placement have been tried. False is returned (line 37) to indicate failure so that a call to R() earlier in the recursion will try another placement for its crates.
To ensure that the crates don't extend off the side of the deck, bits corresponding to column G and row 7 are set in used for the initial call to R() (line 20).
4432676798719 is the empty deck corresponding to 0b0000001000000100000010000001000000100000011111111
JavaScript, 366
k=>(x=y=0,C={},B=[...k].map((c,p)=>(c<' '?(x=0,++y):c<'a'?++x:(c=C[c=parseInt(c,36)]||(C[c]=[[],x,y]))[0].push((y-c[2])*7+(x++-c[1])/3),p<8|p>48|p%7<1)),S=[],R=i=>!C[i]||B.some((v,p)=>v?0:C[i][0].every(q=>B[q+=p]?0:B[q]=i)&&R(i+1,S[i-10]=p)||!C[i][0].map(q=>B[q+=p]==i?B[q]=0:0)),R(10),S.map((v,c)=>`HAUL ${(c+10).toString(36)} TO ${(v%7+9).toString(36)} ${v/7|0}`))
Note: this function can parse a more compact input, as it does not care about spacing by 24 chars, and holes in crates are allowed.
I think it could be golfed a little more, but now it's short and not too much slow, so I like it as is
Less golfed
k=>(
// input parsing
var x = 0, y = 0, // current position
C = []; // crates
[...k].forEach( c =>
c < ' '
? (x = 0, ++y) // found a newline, increment y, reset x
: c < 'a'
? ++x // not a letter, increment x
: ( // found a letter, update the crate
c = parseInt(c,36), // letter to number (10..35)
c = C[c], // current crate in c
c || (C[c]=[[], x, y]), // if new crate, initialize it setting base position
c[0].push((y - c[2])*7 + (x-c[1])/3) // add current position
++x // increment x also
)
);
var B = [...Array(7*8)] // empty board. in golfed code I reuse k to build B. k is big enough
B = B.map( (_, p) => // set borders
p < 8 | p > 48 | p%7<1
)
var S = [] // output steps
// recursive function to fill board
var R = i =>
! C[i] // if crate at position i exists (else, we have found a solution and return true)
||
B.some( (v,p) => // try to put crate at each position in B
v // current cell is used already ?
? 0 // used, return false
: C[i][0].every( q => // try this position, must place every part
B[q+=p] // current position in B is used ?
? 0 // used, stop, return false
: B[q]=i // mark as used
)
&& R(i+1,S[i-10]=p) // ok for current crate, try next, mark step
|| // else, fail for current crate, clear position marked
!C[i][0].map(q =>
B[q+=p]==i ? B[q]=0:0 // clear if it was set to 'i'
)
),
R(10) // start recursive fill at position 10 (that is 'a')
// it returns true if ok, but we don't care as we are assured a solution exists
// now just format output
return S.map((v,c)=>`HAUL ${(c+10).toString(36)} TO ${(v%7+9).toString(36)} ${v/7|0}`)
)
Test cases lots of them
var F=
k=>(x=y=0,C={},B=[...k].map((c,p)=>(c<' '?(x=0,++y):c<'a'?++x:(c=C[c=parseInt(c,36)]||(C[c]=[[],x,y]))[0].push((y-c[2])*7+(x++-c[1])/3),p<8|p>48|p%7<1)),S=[],R=i=>!C[i]||B.some((v,p)=>v?0:C[i][0].every(q=>B[q+=p]?0:B[q]=i)&&R(i+1,S[i-10]=p)||!C[i][0].map(q=>B[q+=p]==i?B[q]=0:0)),R(10),
// Just for debug: return the fill in addition to the steps
[B.slice(7,50).map((c,i)=>i%7?c.toString(36):'\n'),
S.map((v,c)=>`HAUL ${(c+10).toString(36)} TO ${(v%7+9).toString(36)} ${v/7|0}`)])
var Test = [
"[a][a][a] [b] [c][c]\n [a] [b][b][b] [c]\n [a] [b][b]\n\n[d] [e] [f][f][f][f][f]\n[d][d] [e]\n[d][d] [e]\n [e]\n [e][e]\n\n[g] [h] [i]\n[g] [i]\n [i]"
,"[a][a][a] [b] [c][c][c]\n [a][a] [b]\n [a] [b][b]\n [b][b]\n\n[d] [e] [f]\n[d] [f]\n[d] [f]\n[d]\n[d]\n\n[g][g] [h] [i]\n [i][i]\n [i]\n [i][i]\n\n[j][j][j]"
,"[a] [b][b][b] [c]\n[a] [b]\n[d] [e] [f][f]\n[d] [e]\n[d][d][d]\n[g] [h] [i]\n[g] [h][h][h] [i]\n [h] [i][i]\n [h] [i]\n [i]\n[j] [k][k][k]\n[j]\n[j]"
,"[a][a][a][a] [b][b][b] [c]\n [b] [c]\n [b] [c][c]\n [c][c]\n[d] [e] [f]\n[d] [f][f][f]\n[g] [h] [i][i]\n [h][h][h] [i][i]\n [h][h]\n[j]\n[j]\n[j]"
,"[a] [b] [c][c]\n[a] [b]\n[a]\n[d][d] [e] [f][f][f]\n[d][d][d]\n[g] [h] [i]\n [h]\n [h]\n [h][h]\n [h]\n[j] [k][k][k]\n[j][j] [k][k]\n[j][j][j] [k]"
,"[a] [b][b][b] [c]\n[a] [c]\n [c]\n[d][d] [e] [f]\n[d][d][d][d] [e] [f]\n [e][e][e][e] [f]\n[g] [h][h][h] [i][i][i]\n [h] [i][i][i]\n[j][j]"
,"[a] [b] [c][c][c]\n [b]\n[d] [e][e] [f][f]\n[d][d][d] [f][f]\n[d][d]\n[g] [h][h][h] [i]\n[g] [h] [i][i]\n[g] [h] [i][i]\n[g]\n[g]\n[j]\n[j]\n[j]"
,"[a][a] [b] [c]\n [a][a] [b][b] [c]\n [b][b][b] [c]\n[d] [e][e][e] [f][f][f]\n[d] [e][e][e]\n[g][g] [h] [i]\n [i]\n [i][i]\n[j][j]\n [j]\n [j]\n [j]"
,"[a][a] [b] [c]\n[a][a] [b][b] [c]\n [b][b][b]\n[d][d] [e] [f][f][f]\n[g] [h] [i][i]\n[g] [h] [i]\n[g] [h]\n[g]\n[g][g]\n[j]\n[j]\n[j]\n[j][j]\n [j]"
,"[a] [b] [c][c][c][c][c]\n [b]\n [b][b][b]\n [b]\n[d] [e] [f][f][f]\n [e]\n [e]\n [e][e][e]\n[g] [h] [i]\n[g] [h]\n[g] [h]\n [h]\n[j][j] [k]\n[j][j] [k]"
,"[a] [b] [c]\n [c]\n [c]\n[d][d][d] [e] [f]\n [e][e][e] [f]\n [f][f][f]\n [f]\n[g][g][g] [h][h] [i]\n[g][g][g] [i][i]\n [i][i]\n[j] [k]\n[j] [k]\n[j]"
,"[a][a] [b] [c]\n [b] [c][c][c]\n [b] [c]\n [b][b] [c]\n [b]\n[d] [e] [f]\n[d]\n[g] [h] [i]\n[g][g][g] [h] [i]\n [h][h][h] [i]\n [h]\n[j][j][j] [k][k]"
,"[a][a] [b][b][b] [c]\n [b][b][b]\n[d] [e] [f]\n[d] [e] [f]\n [e] [f]\n [e][e]\n [e]\n[g][g][g] [h][h] [i]\n [h][h] [i]\n [h][h] [i][i]\n [i]\n [i]\n[j]"
,"[a][a][a] [b][b] [c][c]\n [b][b] [c][c]\n [b][b] [c][c]\n[d][d] [e] [f][f]\n [d] [e]\n [e]\n [e]\n [e]\n[g] [h] [i][i]\n[g] [i][i]\n[g]\n[g]\n[g][g]"
,"[a][a][a] [b] [c]\n [a] [c]\n [a]\n[d] [e][e][e] [f][f]\n[d]\n[g] [h][h] [i]\n[g][g][g] [h][h] [i]\n [g][g] [i]\n[j] [k]\n[j] [k]\n[j][j]\n [j]\n [j]"
,"[a][a] [b] [c][c]\n [b][b]\n [b][b][b]\n[d] [e][e][e] [f][f]\n [e][e][e] [f][f][f]\n[g] [h] [i][i]\n[g] [h] [i][i]\n[g] [i][i]\n[j][j][j]"
,"[a][a] [b][b][b] [c]\n [a] [b][b]\n [a][a][a]\n[d][d] [e] [f]\n[d][d] [e][e] [f][f][f]\n [e][e]\n [e]\n[g][g][g] [h] [i]\n [i]\n [i]\n [i]\n[j][j]"
,"[a] [b][b] [c]\n[a] [c]\n[a]\n[a][a][a]\n[d] [e][e][e][e] [f]\n[d] [f]\n [f]\n[g] [h] [i]\n[g] [h][h]\n[g] [h][h][h]\n[g]\n[g][g]\n[j] [k][k]\n [k]"
,"[a] [b][b] [c]\n[a] [b][b][b] [c]\n[a][a][a][a] [c]\n[d][d][d] [e] [f]\n [d][d] [e]\n[g] [h] [i]\n [h] [i]\n [h]\n [h]\n [h][h]\n[j][j][j][j][j]"
,"[a][a] [b][b] [c]\n [a][a][a]\n [a]\n[d] [e][e][e] [f][f]\n[d]\n[g] [h][h] [i]\n[g] [h][h]\n[g] [h][h]\n[g]\n[j] [k]\n[j][j] [k][k]\n [k][k]\n [k]"
,"[a][a][a] [b] [c]\n [c]\n [c][c][c][c]\n[d] [e][e][e] [f][f][f]\n[d] [e][e][e] [f][f][f]\n[d]\n[g] [h][h] [i][i]\n[g] [i][i]\n[j]\n[j]\n[j]"
,"[a] [b] [c][c]\n [b] [c][c]\n [b]\n[d][d][d] [e] [f]\n [d] [f]\n [f]\n[g] [h] [i]\n[g] [h][h][h] [i][i]\n [h][h] [i][i][i]\n[j] [k] [l][l][l][l]"
,"[a] [b] [c]\n[a][a] [b]\n[a][a]\n[d] [e] [f]\n[d] [e]\n[d] [e][e][e]\n[d] [e]\n[g] [h][h][h] [i][i]\n[g][g]\n[j][j][j] [k]\n[j][j][j] [k]\n [k]"
,"[a] [b] [c][c]\n[a][a][a] [b] [c][c]\n [a][a] [b]\n [b]\n [b][b]\n[d] [e] [f]\n[d] [e]\n[d]\n[g] [h][h][h][h] [i]\n[j][j] [k]\n [k]\n [k][k]\n [k]\n [k]"
,"[a] [b][b][b] [c]\n[a] [b][b][b] [c][c][c]\n[a]\n[d] [e] [f][f][f][f]\n [e]\n [e]\n [e]\n [e]\n[g] [h] [i]\n [h][h] [i]\n [h][h] [i][i][i]\n [i]\n[j]"
,"[a][a][a] [b] [c]\n [b] [c]\n [b][b][b]\n [b]\n[d][d][d] [e][e] [f]\n [e][e] [f]\n [f]\n [f][f][f]\n[g] [h] [i]\n[g] [i]\n[g] [i]\n [i]\n [i][i]\n[j][j]"
,"[a] [b] [c]\n[a] [b]\n[a][a] [b]\n[d] [e][e][e] [f]\n[d] [e] [f]\n [e] [f]\n [e] [f][f]\n [f]\n[g][g] [h] [i]\n [i]\n[j][j][j] [k]\n [k][k][k]\n [k][k]"
,"[a][a][a] [b][b] [c]\n [b] [c]\n[d] [e][e] [f]\n[d] [f]\n[d][d]\n [d][d]\n[g] [h] [i]\n [h]\n [h]\n[j][j] [k] [l]\n[j][j][j] [k] [l][l][l]\n [j] [k]"
,"[a][a] [b] [c][c][c]\n[d] [e][e] [f][f]\n[d] [e][e] [f][f]\n[d]\n[d]\n[g] [h][h][h] [i]\n[g] [i]\n[g]\n[g][g][g]\n[j] [k]\n[j]\n[j][j][j][j]"
,"[a][a][a] [b][b] [c]\n[d] [e] [f]\n[d][d][d] [f][f][f][f]\n[d][d] [f]\n[g][g] [h][h][h] [i]\n [i]\n [i]\n[j] [k] [l]\n[j] [l]\n [l][l]\n [l][l]"
,"[a][a][a] [b] [c]\n [b] [c]\n [c]\n[d][d] [e][e] [f]\n [d]\n [d]\n [d]\n[g] [h] [i][i]\n[g][g] [h] [i][i][i]\n [h][h][h] [i]\n [h]\n[j][j] [k]\n[j][j]"
,"[a] [b][b][b] [c]\n[a] [b] [c]\n[a][a] [b] [c]\n [a][a]\n[d] [e][e][e] [f][f]\n[d][d][d] [f][f]\n [d][d]\n[g] [h] [i][i]\n[j] [k]\n[j] [k][k]"
,"[a] [b] [c]\n [c]\n [c][c]\n [c][c]\n[d][d][d][d][d] [e] [f][f]\n [f][f]\n[g] [h] [i][i]\n[g] [h][h] [i][i]\n[g] [i][i]\n[g]\n[g]\n[j][j]\n[j][j]"
,"[a] [b][b] [c][c]\n [b] [c][c]\n [b]\n[d][d] [e][e] [f]\n[d][d][d] [e][e][e]\n[g] [h] [i]\n[g] [h]\n[g][g][g][g] [h]\n [h]\n [h]\n[j][j][j][j]"
,"[a] [b][b][b] [c][c][c]\n[a] [b][b]\n[a]\n[a][a]\n [a]\n[d] [e] [f]\n[d] [f]\n[d] [f]\n[g] [h] [i][i]\n[g][g] [h] [i][i]\n[g][g][g]\n[j] [k][k]"
,"[a] [b][b] [c]\n[a] [b][b]\n [b][b]\n[d] [e] [f][f][f]\n[d][d][d]\n[d][d]\n[g] [h] [i][i]\n[g] [h]\n[g]\n[j][j][j] [k]\n [j] [k]\n [k]\n [k][k]\n [k]"
,"[a][a][a] [b] [c]\n [a][a]\n[d][d][d] [e] [f][f]\n [e]\n[g] [h] [i]\n[g][g] [h] [i]\n[g][g][g] [h] [i]\n[j] [k][k]\n[j][j] [k][k][k]\n[j][j]"
,"[a][a][a] [b] [c][c][c][c][c]\n [a][a] [b]\n [a] [b]\n [b]\n[d] [e] [f]\n[d][d] [f]\n[d][d][d] [f]\n[g] [h][h] [i][i][i]\n [h][h] [i][i][i]"
,"[a][a] [b] [c]\n [b]\n [b]\n[d][d][d] [e] [f]\n [f]\n [f]\n [f]\n[g][g][g] [h][h] [i]\n[g][g][g] [h][h] [i][i]\n [i][i][i]\n[j][j][j]\n [j][j]\n [j]"
,"[a] [b] [c]\n[a] [c]\n[a] [c]\n[a] [c][c][c]\n[a][a]\n[d] [e] [f]\n [e]\n [e]\n[g][g] [h][h] [i][i][i]\n[g][g]\n[g][g]\n[j] [k][k][k]\n[j]\n[j]\n[j]"
,"[a][a][a] [b] [c]\n [a][a] [b][b] [c]\n [a] [b][b][b] [c]\n [c]\n[d] [e][e][e] [f]\n[d][d][d]\n[d][d]\n[g] [h] [i][i]\n [i][i]\n[j] [k][k]\n[j]"
,"[a] [b][b] [c]\n [c]\n [c][c]\n [c][c]\n[d] [e][e][e] [f][f]\n[d][d][d] [f][f]\n [f]\n[g] [h] [i]\n [i][i]\n [i][i]\n [i]\n[j] [k] [l][l]\n[j]\n[j]\n[j]"
,"[a] [b] [c][c][c]\n[a] [b] [c][c]\n[a] [b]\n[a]\n[a][a]\n[d] [e] [f][f]\n [e][e]\n [e][e]\n [e]\n[g] [h] [i][i]\n [i][i]\n [i][i]\n[j] [k][k][k]\n[j]"
,"[a][a][a] [b] [c]\n [c]\n [c]\n [c][c]\n [c]\n[d][d][d] [e] [f]\n [d] [f]\n [f]\n[g][g] [h] [i]\n [h] [i][i][i]\n [i][i]\n[j][j] [k]\n[j][j] [k]\n[j][j]"
,"[a][a] [b][b] [c][c]\n [b][b]\n [b]\n[d] [e][e][e] [f]\n[d] [e][e][e] [f]\n[d][d]\n [d][d]\n[g][g][g] [h] [i]\n [h] [i][i]\n [h]\n[j] [k]\n [k]\n [k]"
,"[a][a][a] [b][b] [c]\n [a] [c][c][c]\n [c][c]\n[d] [e] [f]\n [f]\n [f]\n [f]\n[g] [h][h] [i][i][i]\n[g] [h][h]\n[g] [h][h]\n[g][g][g]\n[j][j][j]"
,"[a][a] [b][b] [c][c][c][c][c]\n[a][a][a] [b]\n[d] [e][e][e] [f]\n[d] [e][e][e] [f]\n[d][d][d][d] [f]\n [f]\n [f]\n[g] [h]\n [h]\n [h]\n [h]\n [h]"
,"[a] [b][b] [c]\n[a] [c]\n[a] [c]\n[a] [c]\n[a]\n[d] [e] [f]\n[g] [h][h][h][h] [i][i][i]\n[g] [i][i][i]\n[g][g][g][g]\n[j][j]\n[j][j][j][j]"
,"[a] [b] [c]\n [b][b]\n [b][b][b]\n[d][d][d] [e] [f][f]\n [d][d] [e] [f][f]\n [d] [e]\n [e]\n[g][g] [h] [i][i][i]\n [h] [i][i][i]\n [h]\n[j][j][j]"
,"[a][a] [b][b] [c]\n [c]\n [c]\n [c]\n [c][c]\n[d] [e] [f][f][f]\n [e]\n [e]\n [e][e][e]\n[g][g] [h] [i]\n [h][h][h] [i]\n [h][h] [i]\n[j] [k]\n [k]\n [k]\n [k]"
,"[a] [b] [c][c][c][c][c]\n[a]\n[a][a][a][a]\n[d][d] [e] [f]\n[d][d]\n[g] [h][h] [i]\n[g] [h][h][h] [i]\n[j] [k]\n[j] [k]\n[j] [k]\n [k][k]\n [k]"
,"[a] [b] [c]\n[a][a] [b]\n [b]\n [b][b]\n [b]\n[d] [e] [f][f][f]\n[d] [e] [f][f][f]\n [e]\n[g] [h] [i]\n [h] [i]\n [h] [i][i][i]\n [i]\n[j][j][j][j][j]"
,"[a] [b] [c][c]\n [b] [c][c]\n [b]\n [b]\n[d][d] [e][e][e] [f][f]\n[d][d]\n[g] [h][h] [i][i]\n [h][h] [i][i]\n [h][h]\n[j] [k]\n [k]\n [k][k][k]\n [k]"
,"[a][a] [b][b] [c]\n [a][a] [b] [c]\n [a] [b] [c]\n [b] [c]\n[d] [e] [f]\n [f][f]\n [f][f][f]\n[g][g] [h][h][h] [i]\n[j][j] [k][k]\n [k][k][k][k]"
,"[a] [b] [c]\n [c]\n [c]\n [c][c]\n [c]\n[d] [e][e] [f][f]\n [e][e][e]\n [e]\n[g] [h] [i][i][i]\n [h]\n [h]\n [h]\n [h]\n[j][j] [k] [l]\n [k] [l]\n [l][l]\n [l][l]"
,"[a][a] [b] [c]\n [a] [c][c]\n [a] [c]\n [a] [c]\n [a] [c]\n[d] [e] [f]\n[d] [f]\n[d][d] [f]\n [d] [f]\n [d]\n[g][g][g] [h][h] [i]\n [i]\n [i]\n [i]\n [i][i]\n[j]"
,"[a] [b] [c][c]\n [b]\n [b]\n[d] [e][e] [f]\n[d][d][d] [e] [f][f]\n[d][d] [f][f][f]\n[g][g][g] [h][h][h] [i][i]\n [h][h] [i][i]\n[j] [k]\n[j]"
,"[a][a][a] [b][b] [c]\n [b] [c][c][c]\n [c][c]\n[d] [e][e] [f][f]\n[d] [f][f]\n[g] [h] [i][i][i][i]\n[g][g] [h] [i][i]\n[g][g][g] [h]\n[j]"
,"[a][a][a] [b] [c]\n [c]\n [c][c]\n [c][c]\n[d] [e] [f]\n[d][d][d] [e] [f]\n [f][f]\n [f][f]\n[g] [h] [i][i]\n[g] [h]\n[g] [h]\n[j][j][j]\n[j][j]\n [j]"
,"[a] [b] [c]\n [b] [c][c][c][c]\n [b] [c]\n[d][d] [e][e][e] [f]\n[d][d][d][d]\n[g] [h] [i][i][i]\n[g] [h]\n[g]\n[j][j] [k]\n [k]\n [k][k][k]\n [k]"
,"[a] [b] [c]\n[a] [c]\n[a] [c]\n[a][a]\n [a]\n[d] [e][e] [f][f]\n[g][g] [h][h][h] [i]\n[g][g] [i]\n [g]\n[j] [k] [l]\n[j] [k] [l]\n[j][j] [k]\n [j][j]"
,"[a] [b] [c][c]\n [b] [c][c]\n [b] [c][c]\n [b]\n [b][b]\n[d][d][d][d] [e] [f]\n [e][e]\n [e][e]\n [e]\n[g] [h] [i]\n [h]\n [h]\n [h]\n[j] [k] [l][l]\n [l][l]"
,"[a] [b][b][b] [c]\n[a][a] [b] [c]\n[a][a] [b] [c]\n [c][c][c]\n[d][d] [e] [f]\n [e] [f][f][f]\n [f][f]\n[g] [h][h][h] [i]\n[g]\n[g]\n[j][j][j]"
,"[a][a] [b][b][b] [c]\n [b] [c]\n[d] [e] [f][f][f][f]\n[d][d][d][d][d]\n[g] [h] [i]\n[g] [h][h][h] [i]\n[g][g][g] [h][h] [i]\n [g]\n[j] [k]"
,"[a] [b][b][b][b] [c]\n[a][a][a] [c]\n [a][a] [c]\n[d] [e] [f]\n[d] [f]\n[g][g][g] [h] [i][i]\n [g] [i][i]\n[j] [k]\n[j] [k]\n[j][j] [k]\n [j]\n [j]"
,"[a][a][a] [b] [c][c][c]\n [a][a] [b] [c][c][c]\n [a] [b]\n[d] [e][e][e][e] [f]\n[d]\n[d]\n[d][d]\n [d]\n[g] [h] [i]\n[g]\n[j]\n[j][j]\n[j][j][j]"
,"[a][a][a] [b] [c]\n [b]\n [b]\n[d] [e] [f]\n[d] [e] [f][f]\n[d]\n[d][d][d]\n[g] [h] [i][i][i][i]\n[j] [k][k]\n[j][j] [k][k]\n[j][j][j] [k]\n [k]"
,"[a][a] [b][b][b] [c]\n[a][a] [c][c]\n [c][c][c]\n[d] [e][e] [f]\n [f]\n [f]\n [f]\n[g] [h] [i][i]\n[g][g] [h] [i]\n [h]\n[j][j] [k]\n [j][j]\n [j]\n [j]"
,"[a] [b] [c][c][c][c][c]\n[a] [b]\n[a]\n[d][d][d] [e] [f]\n[d][d][d] [e] [f]\n [e][e] [f]\n [e][e] [f]\n [f][f]\n[g] [h] [i][i]\n [i][i]\n [i][i]"
,"[a] [b] [c]\n[a] [b]\n[a] [b][b]\n[a] [b][b]\n[d][d][d][d] [e] [f][f]\n [f][f]\n[g][g] [h] [i][i]\n[g][g] [h][h][h] [i][i]\n [g][g] [i]\n[j]"
,"[a] [b][b][b] [c]\n[a][a][a] [b]\n[a][a] [b]\n[d][d][d] [e] [f]\n [e][e][e]\n [e][e]\n[g][g] [h] [i]\n [h] [i]\n [h]\n[j] [k][k]\n[j] [k][k]\n[j]"
,"[a][a] [b][b][b][b] [c]\n [a][a] [c]\n [a][a]\n[d] [e] [f]\n[d]\n[d][d]\n [d]\n [d]\n[g][g] [h] [i]\n[g][g] [i]\n[j] [k]\n[j] [k][k]\n[j] [k]\n [k]\n [k]"
,"[a][a] [b] [c]\n [b] [c]\n [b]\n[d][d][d] [e] [f]\n[d][d][d] [e] [f][f]\n [e] [f][f][f]\n[g] [h] [i]\n [h] [i]\n [i][i]\n [i]\n [i]\n[j] [k] [l][l][l]"
,"[a] [b] [c]\n [c]\n [c]\n[d] [e][e][e] [f]\n [f]\n [f]\n [f][f][f]\n[g] [h][h][h][h] [i]\n[g] [i][i]\n [i][i][i]\n[j][j] [k][k]\n[j][j] [k][k]\n [k]"
,"[a][a][a] [b] [c]\n [b][b][b][b] [c]\n [b] [c]\n[d] [e][e][e] [f][f]\n[d] [e][e][e]\n[d][d][d][d]\n[g][g] [h] [i]\n[g][g] [h]\n[j][j][j]"
,"[a] [b][b][b] [c]\n[a] [b] [c]\n[a] [c][c][c]\n [c]\n[d][d] [e][e][e][e] [f]\n[d][d]\n[g] [h] [i]\n [h][h][h] [i]\n [h][h]\n[j] [k][k]\n [k][k]"
,"[a][a][a] [b] [c][c][c]\n [c]\n[d] [e] [f]\n[d] [f][f][f]\n[d] [f][f]\n[g] [h][h] [i]\n [h][h] [i]\n [i]\n[j] [k] [l][l]\n[j] [k][k][k]\n [k][k]"
,"[a] [b] [c]\n[a] [b][b]\n[a] [b][b][b]\n[a]\n[d] [e] [f][f][f]\n[d][d] [e] [f][f]\n[d][d] [e]\n [d] [e]\n[g][g] [h] [i]\n[j] [k][k][k]\n[j][j]"
,"[a][a][a][a][a] [b] [c][c]\n [c][c]\n[d][d][d] [e] [f][f]\n[d][d][d] [f]\n [f]\n[g] [h][h] [i]\n[g] [h][h][h] [i]\n[g][g][g][g] [i]\n [i]"
,"[a][a] [b] [c][c][c]\n [b]\n [b]\n [b][b]\n [b]\n[d] [e][e] [f]\n[d]\n[d]\n[d]\n[g][g] [h] [i]\n [g] [i]\n [g] [i][i]\n [i]\n [i]\n[j] [k]\n [k][k]\n [k]\n [k][k]"
,"[a][a] [b] [c][c]\n[a][a][a] [b][b]\n [a]\n[d] [e] [f]\n[d] [e] [f]\n[d][d][d] [e]\n [d]\n[g] [h][h][h] [i][i][i]\n [i][i][i]\n[j][j]\n [j]\n [j]"
,"[a][a][a][a] [b] [c]\n [c][c]\n [c][c][c]\n[d][d][d] [e][e][e] [f]\n [e][e] [f]\n [f]\n[g] [h] [i]\n[g] [h] [i]\n [h] [i]\n [h] [i][i][i]\n [h]\n[j]"
,"[a] [b] [c][c][c]\n[a] [b]\n[a][a] [b][b]\n [b][b]\n[d][d] [e] [f]\n [d][d] [e][e]\n [d] [e]\n [d] [e]\n [e]\n[g][g] [h] [i]\n [h]\n [h]\n [h]\n [h]\n[j][j]"
,"[a] [b][b][b][b] [c]\n[a]\n[a][a][a][a]\n[d] [e] [f]\n[d] [e] [f]\n [e] [f]\n[g][g][g] [h][h][h] [i][i]\n[g][g][g] [h][h][h] [i][i]\n[j]"
,"[a] [b][b][b][b] [c]\n[a][a] [b][b]\n[a][a][a]\n[d] [e][e] [f][f]\n[d] [e][e] [f]\n[d]\n[d]\n[g][g][g] [h] [i]\n [h][h][h]\n [h][h]\n[j][j]"
,"[a][a] [b] [c][c][c][c][c]\n[a][a][a]\n[d][d][d] [e] [f][f]\n [d]\n [d]\n[g] [h] [i]\n[g][g][g] [h] [i]\n [g][g] [i]\n[j]\n[j]\n[j][j]\n[j][j]"
,"[a][a][a] [b] [c]\n [b][b][b] [c]\n [b][b] [c]\n [c]\n [c]\n[d][d] [e] [f][f]\n [f][f]\n[g][g][g] [h] [i]\n [g] [i][i]\n [g][g] [i][i][i]\n[j]\n[j]"
,"[a] [b][b] [c]\n[d] [e] [f]\n[d]\n[g][g] [h][h] [i]\n[g][g][g] [i]\n [g] [i][i]\n [i][i]\n[j][j][j] [k] [l]\n [k] [l]\n [k] [l]\n [l][l]\n [l]\n[m]\n[m]"
,"[a] [b] [c]\n [b] [c]\n [b][b]\n [b][b]\n[d][d][d][d][d] [e] [f][f][f]\n [f][f][f]\n[g] [h] [i][i]\n[g] [h][h] [i][i]\n[g] [i][i]\n[j]\n[j]\n[j]"
,"[a] [b][b][b] [c]\n[a][a] [b] [c]\n[a][a][a] [b][b] [c]\n[d][d] [e] [f]\n [f][f][f]\n [f][f]\n[g][g][g] [h] [i]\n [h] [i]\n[j][j] [k]\n[j][j]"
,"[a][a][a] [b][b][b] [c]\n [a] [b][b][b] [c]\n [a]\n[d] [e] [f]\n[d] [e][e][e] [f]\n[d] [e][e]\n[g] [h] [i][i][i]\n[g]\n[g][g]\n [g]\n [g]\n[j][j]"
,"[a] [b] [c][c][c][c]\n[a][a] [b]\n [a] [b]\n [a][a]\n[d] [e] [f]\n [e]\n [e][e]\n [e]\n [e]\n[g][g] [h] [i]\n [h] [i]\n[j] [k] [l][l]\n [k] [l][l]\n [l][l]"
,"[a] [b] [c]\n[d] [e] [f]\n[d][d] [e] [f]\n [d][d] [e][e] [f]\n [d] [e][e]\n[g] [h] [i][i][i][i]\n[g] [h]\n[j][j][j] [k]\n [j][j] [k][k][k]\n [j]"
,"[a] [b] [c]\n[a]\n[a]\n[a]\n[d] [e][e][e][e] [f][f]\n [f][f]\n[g][g][g] [h] [i][i][i]\n [h] [i][i][i]\n [h][h][h][h]\n[j]\n[j]\n[j]\n[j][j][j]"
,"[a][a] [b] [c]\n[a][a]\n[d][d][d][d][d] [e] [f]\n [e][e][e] [f]\n [e][e] [f]\n [f]\n [f]\n[g] [h] [i]\n[g] [h][h]\n[g][g]\n [g][g]\n[j][j][j]\n [j]"
,"[a] [b][b][b] [c]\n[a] [b] [c]\n[a][a][a] [b] [c]\n [b]\n[d] [e][e] [f][f]\n [f][f]\n[g] [h] [i]\n[g] [h][h][h] [i]\n [h][h] [i]\n[j] [k][k][k]"
,"[a] [b] [c]\n [b] [c]\n [b][b]\n [b][b]\n[d] [e] [f]\n[d] [e]\n[d] [e]\n[d]\n[d][d]\n[g] [h] [i][i]\n[g][g] [h][h] [i]\n [h][h]\n [h]\n[j] [k][k][k][k]"
,"[a][a] [b] [c][c][c][c][c]\n [b]\n [b]\n[d] [e] [f][f][f]\n [e] [f][f][f]\n[g] [h][h] [i]\n [h] [i]\n [h] [i][i]\n [i][i]\n[j]\n[j]\n[j]\n[j]\n[j][j]"
,"[a][a][a] [b][b] [c][c]\n [b][b]\n[d] [e] [f][f]\n[d] [e] [f][f]\n[d]\n[g] [h] [i]\n [h] [i][i]\n [h] [i][i][i]\n [h]\n [h]\n[j][j][j]\n [j][j]\n [j]"
,"[a][a] [b][b] [c]\n[a][a] [c][c]\n[a][a] [c]\n [c]\n [c]\n[d] [e][e][e] [f]\n [f]\n [f]\n[g] [h][h][h] [i]\n[g] [h][h] [i]\n[j]\n[j]\n[j][j]\n [j]\n [j]"
,"[a][a] [b] [c]\n[a][a] [b] [c]\n [b][b][b] [c]\n [b] [c][c][c]\n[d] [e] [f][f]\n[d]\n[g][g][g] [h][h][h] [i]\n [i]\n [i]\n[j]\n[j]\n[j]\n[j]\n[j][j]"
]
to=0
function update() {
var nt=+I.value
var test = Test[nt-1]
if (test) {
O.textContent = test
clearTimeout(to)
to = setTimeout(_=>{
I.disabled = true
var t = + new Date()
var [d,r]=F(test)
O.textContent = 'Time '+(new Date-t)/1000+' sec'+d+r.join`\n`+'\n'+test
I.disabled = false
}, 800)
}
}
update()Test # <input id=I value=1 type=number oninput='update()' max=101 min=1> (1 to 101, be patient: some testcase is slow to solve)
<pre id=O></pre>