[QUIZ][SOLUTION] Grid Folding (#63)

[David Tran]

I wonder for 4x4 the total solution is 16 * 4! =3D 384

My solution about check_fold is try to find all combinations possible.

Below is modified version of my check_fold, it will print out all
possible combinations and total count number.
However I found for 4x4 there is only 96 possible not 384.
Can someone tell me that I am wrong ( missing some combination ) or
the previous math formula is not correct ?

Thanks,

def check_fold(row, col, result)

# find all combinations with binary 0 for row and 1 for column operation
def all_orders(r, c) #
return [2**c - 1] if (r <=3D 0) # c bits of 1 is 2**c-1
return [0] if (c <=3D 0) # r bits of 0 is 0
table =3D []
all_orders(r-1,c).each { |t| table << ((t << 1) + 0) }
all_orders(r,c-1).each { |t| table << ((t << 1) + 1) }
table
end
=3Dbegin
if row <=3D 0 ||
col <=3D 0 ||
row * col !=3D result.size ||
2 ** (Math.log(row)/Math.log(2)).to_i !=3D row ||
2 ** (Math.log(col)/Math.log(2)).to_i !=3D col
raise "Error: Parameters are not correct."
end
=3Dend
r =3D Integer(Math.log(row) / Math.log(2))
c =3D Integer(Math.log(col) / Math.log(2))
all_rc_orders =3D all_orders(r,c)
count =3D 0

row.times do |tb_operation|
col.times do |lr_operation|
all_rc_orders.each do |order|
operations =3D ''
tb_op =3D tb_operation
lr_op =3D lr_operation
(r+c).times do
if (order & 1 =3D=3D 0)
operations +=3D (tb_op & 1 =3D=3D 0) ? 'T' : 'B'
tb_op >>=3D 1
else
operations +=3D (lr_op & 1 =3D=3D 0) ? 'L' : 'R'
lr_op >>=3D 1
end
order >>=3D 1
end
puts operations
count +=3D 1
# return operations if fold(row, col, operations) =3D=3D result
end
end
end
p count
end

check_fold(4,4, nil)

#=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D#
The output:

TTLL
TLTL
TLLT
LTTL
LTLT
LLTT
TTRL
TRTL
TRLT
RTTL
RTLT
RLTT
TTLR
TLTR
TLRT
LTTR
LTRT
LRTT
TTRR
TRTR
TRRT
RTTR
RTRT
RRTT
BTLL
BLTL
BLLT
LBTL
LBLT
LLBT
BTRL
BRTL
BRLT
RBTL
RBLT
RLBT
BTLR
BLTR
BLRT
LBTR
LBRT
LRBT
BTRR
BRTR
BRRT
RBTR
RBRT
RRBT
TBLL
TLBL
TLLB
LTBL
LTLB
LLTB
TBRL
TRBL
TRLB
RTBL
RTLB
RLTB
TBLR
TLBR
TLRB
LTBR
LTRB
LRTB
TBRR
TRBR
TRRB
RTBR
RTRB
RRTB
BBLL
BLBL
BLLB
LBBL
LBLB
LLBB
BBRL
BRBL
BRLB
RBBL
RBLB
RLBB
BBLR
BLBR
BLRB
LBBR
LBRB
LRBB
BBRR
BRBR
BRRB
RBBR
RBRB
RRBB
96

 

[Morus Walter]

I wonder for 4x4 the total solution is 16 * 4! = 384
My solution about check_fold is try to find all combinations possible.
Below is modified version of my check_fold, it will print out all
possible combinations and total count number.
However I found for 4x4 there is only 96 possible not 384.
Can someone tell me that I am wrong ( missing some combination ) or
the previous math formula is not correct ?

96 is correct.
I'm not sure how the 16 * 4! formula was created but you can easily
see that it must be wrong since the total number of 4 letter strings
constisting of R/L/T/B is 4**4 = 256 (each of the 4 characters can take
one of 4 values; for n characters that would be 4**n) and that includes
invalid combinations such as TTTT.
So the right answer must be smaller than 256.
As already noted in a comment on Matthews summary post, I think the
correct number is
sum_i=0^n/2 sum_j=0^n/2 n! / i! / (n/2-i)! / j! / (n/2-j)!
for a 2^(n/2) x 2^(n/2) size grid.
This is a bit hard to read in ascii but the basic thought is, that there
must be n/2 letters R or L and n/2 letters T or B.
Now the number of R characters can be 0 up to n/2. Same for T.
For a given number i of Rs and j of Ts the number of permutations is
the number of permutations of n items divided by the number of permutations
of Rs, Ls, Ts and Bs. The total number of possibilites is the sum over
all possibilities for i and j.
Probably this can be rewritten to a simpler form.
I checked the calculation using the following ruby program (up to n=8).
The first part creates and counts all valid folding strings, the second
one calculates the above expression.

---
#! /usr/bin/ruby

n=8
n2=n/2

strs = [ "" ]
n.times do
strs = strs.collect do | str | [ str+'R', str+'L', str+'T', str+'B' ] end.flatten
end

strs.reject! do | str | str.count("RT") != n2 end

#puts strs
puts strs.size

def fak(n)
return 1 if n <= 1
return n*fak(n-1)
end

sum = 0
(0..n2).each do | i |
(0..n2).each do | j |
sum+= fak(n)/fak(i)/fak(n2-i)/fak(j)/fak(n2-j)
end
end
puts sum

 

[Morus Walter]

As already noted in a comment on Matthews summary post, I think the
correct number is
sum_i=0^n/2 sum_j=0^n/2 n! / i! / (n/2-i)! / j! / (n/2-j)!
for a 2^(n/2) x 2^(n/2) size grid. ....
Probably this can be rewritten to a simpler form.

It can:
Its n!/(n/2)!**2 * 2^n
(using 2^n = sum_i=0^n n! / i! / (n-i)!)

Now the remaining challenge is, if that can be seen directly without
calculation.
I guess one could argue:
The number of choices which positions will be used for vertical
folds (leaving the others for horizontal folds) is n over n/2 (n!/(n/2)**2).
And for each position there remain two possiblities (L/R or T/B) which
gives 2^n.
Strange that I didn't see that before doing the calculation...

Morus