[Community puzzle] Folding Paper

Puzzles
#21

Thank you for your answer and all the details, I got mistaken by the fact that the program expected “1”, when it actually expected 12.

1 Like
#22

Thank you very much! I was getting mad soon ;d

#23

This puzzle is very useful to experiment on lazy evaluation. In a lazy implementation for example with the test 8 fold easy, you doesn’t need any calculation.

This old puzzle can be a very good sandbox for optimizing drastically. article on lazy eval.

1 Like
#24

I find your comment about lazy eval to be very interesting.
In this puzzle case, the example of “8 easy” is indeed trivial, but it’s a special case (last fold is done on the viewed side).

In a more general view, the nature of the problem leads to the fact that when calculating a folding sequence you only need to keep track of the final side and it’s opposite, and you don’t need to calculate the other two sides specifically.

Is this what you meant when you said “easy eval optimization”, or can you see here additional areas for optimization?

#25

When you use lazy evaluation, all this kind of optimization is done automatically. The special case you mention can happen many times during the fold. You avoid sometimes 60% of the processing with lazy evaluation. This is the first time I find a puzzle offering an interesting use case for lazy evaluation.

1 Like
#26

Thank you. This is most interesting.

Can you please be more specific - not in a general case but specifically for this puzzle.

There is one edge case here: having the “viewed side” appear at the end. It’s a simple check that can save computation on these specific cases (and it will depend on the nature of the problem to clearly state if it’s beneficial or not to do this test).

There is one general optimization that takes advantage of the fact that the “viewed side” is known prior to the computation, which then allows the algorithm to compute only the viewed side and its opposite (DOWN <-> UP , LEFT <-> RIGHT). Again, not exactly “lazy” but simply a reduction of the problem that can be done in advance.

I’m very interested to hear your meaning in “implementing lazy eval” in this specific puzzle, and how it can bring 60% performance boost.

#27

In this puzzle you have 4 counters :

  • up
  • down
  • left
  • right

each motion update the four counters. At the end you have 4 values which needed some calculation, and you display only one of them : this is a perfect use case for lazy evaluation.

With lazy evaluation you do the calculation strictly needed only for the counter you want to display, not the others.

With the input :
UL
D

Here the progress of my counters step by step.

initial state :

  • Up : 1 layer
  • Down : 1 layer
  • Left : 1 layer
  • Right : 1 layer

after Up motion

  • Up : 1 layer (Affect 1)
  • Down : 2 layers (1 + 1)
  • Left : 2 layers (1*2)
  • Right : 2 layer (1*2)

after left motion :

  • Up : 2 layers (1*2)
  • Down : 4 layers (2*2)
  • Left : 1 layer (Affect 1)
  • Right : 4 layers (2*2)

With lazy evaluation only this 2 calculations are done :
1 + 1
2 * 2

result : 4
I put in bold police the calculation really needed in the step by step description.

If you do all calculations in a lazy way, all kind of optimizations are done automatically.

#28

Hi. I am new here and trying now to learn Java from scratch. I have maded a solution but after submission most tests fail. And now I am not able to find the problem in the code. I it ok to list it here for someone to comment?

#29

Probably not a good idea to post the code right at the beginning. Perhaps you could let us know whether you passed all the test cases and failed most of the validators upon submission? Which ones are you failing? And also, what is the current logic of your code?

1 Like
#30

Test cases failed: 4 ply (expected 12 found 10) and 6 ply (expected 26 found 24). After submitting the solution only 6 ply is OK. Solution is based on the above post regarding lazy evaluation. Is here a way to see the test logic so I could try it hard in IDE? I see 2 options - bug in code or wrong calcualtion idea:)

#31

Understood. Can you show the calculations involved to reach 10 and 24?

#32

I use this scheme:
case ‘U’:
d = d + u;
l = l * 2;
r = r *2;
u = 1;

But I do not know what is the input data for each test scenario. Knowing that I could check step by step the code to verify it.
I use same calculation idea for each folding directon. Forlding direction variable always last to make it 1. Opposite side always calculated as sum.

#33

You always start with r, l, u and d as 1, because before folding the paper, the number of layers is 1.
You could try adding some debug code in your code and compare, at each step, my values below with those produced by your code, so that you may detect where the bug in your code may be:
For 4 ply:

 r  l  u  d
 2  2  2  1
 1  4  4  2
 2  8  1  6
10  1  2 12

For 6 ply:

 r  l  u  d
 2  2  2  1
 1  4  4  2
 1  5  8  4
 2 10  1 12
12  1  2 24
24  2 26  1
1 Like
#34

My code shows the same numbers - for each step. Is it 4 ply (DRUL with check side D)? Shows 12. 6 ply (DRRULD with check side U)? Shows 26 (on IDE). I have checked if the code on webside is the same I have in IDE and it is.

#35

In that case, it looks like your code always output the value of r instead of the asked value.

#36

Hey - you gave me good direction. There was a problem with “IF ELSE” part to decide which result to return. Strange as in IDE it was working fine. Changed to “switch” and works perfectly. Many thanks for help!

1 Like
#37

Wonder why is it medium with only 75% success rate. Nice for beginners.

#38

Hello !
I’m a begginer, and i find it really hard. Sorry it’s gonna be ugly be here’s my code in python…

I pass the first 2 tests, the other no. I understand why because i fold the paper, but in code i really don’t know how.

def count_visible_layers(order, side):
n = len(order)

flips = order.count(side) 
layers = 1
s = 0
for i in range(n):
    if order[i] == side:
        layers = 1
    elif (order[i] == 'L' or order[i] == 'R') and (side == 'D' or side == 'U') or (order[i] == 'D' or order[i] == 'U') and (side == 'L' or side == 'R'):
        layers *= 2
    elif (order[i] == 'U' or order[i] == 'L') and (side == 'D' or side == 'R') or (order[i] == 'D' or order[i] == 'R') and (side == 'U' or side == 'L') or (order[i] == 'U' or order[i] == 'R') and (side == 'D' or side == 'L') or (order[i] == 'D' or order[i] == 'L') and (side == 'U' or side == 'R'):
        if i <= 1:
            layers = 2 ** (i+1)
        else:
            layers = 2 ** (i+1) - layers 
return layers

order = input()
side = input()

n = count_visible_layers(order, side)

print(n)

#39

You may format your code properly on this forum by using the </> button in the formatting toolbar.

Also, please try describing your approach instead of posting full codes on the forum next time.

Regarding your code, your calculation is wrong. Try getting a piece of paper, fold it once at a time, note down the layer numbers from all sides, and observe how the numbers change with each fold. Then you can convert the pattern to code.

In my solution code, I keep track of the numbers on all the sides as I proceed with each fold. You may also refer to the earlier discussion in this post for some inspiration.

#40

Hi, I’m having a hard time to understand this puzzle, especially the sentence

the number of layers of paper visible from side

What does it mean ?
If you fold a sheet of paper 2 times, there will be 2^2 = 4 layers, whatever “side” we look at, right ?
I just tried to fold a real sheet of paper following the example inputs, but I don’t get it all, so if anyone can explain me I’ll be very grateful.