[Community Puzzle] Paper-folding curve

Puzzles
#1

I submitted a wrong answer to the paper-folding-curve puzzle but still got 100%.

I found it dubious my code worked so I ran some tests myself and found that my code fails for many situations (the longer the required substring, the more my code fails)

Am I in the right place to ask to increase the amount of test cases for this puzzle to cover my bad solutions so I wont get an undeserved 100% pass?

Here are some examples of start-end indexes where my code would fail

ORDER: 18
254800-254861
377685-377847
172870-172940
505805-505905
ORDER: 19
582259-582399
487349-487503
1015214-1015350
175363-175515
ORDER: 20
221459-221596
1283506-1283704
1998196-1998266
846139-846239
ORDER: 21
2625801-2625965
3626474-3626590
1801701-1801777
2575721-2575777

Let me know if I should share the code here

1 Like
#3

Thanks for reporting. Allow some time to check.

1 Like
#4

Thanks for the quick reply! I look forward to resubmitting and not getting 100% :sweat_smile: :grinning:

1 Like
#5

Have additional test cases added and at the same time updated/expanded some original test cases. Thanks again for reviving this early puzzle.

2 Likes
#6

Many thanks!

#8

what is the mathematic design to understand this puzzle?

#9

My approach in steps:

Step 1
When you know the pattern of Order n, can you write out the pattern of Order (n+1)?

Step 2
If this is successful, can you also write out the pattern of Order (n+2), (n+3)…(n+x) directly, without going through every stages?

Step 3
Rather than writing out the whole string, can you write out a particular selected char in the string?

2 Likes
#10

justily
order 4 is 110110001100100 and i guess that
order 5 is 110110001110010011101100011

initialy i think that orderN+1 begin with order N but it’s not the case.

and on the console the expected is truncated. it’s complicated to analyze th pattern.

#11

actually I don’t understand this problem physically. I mean, when I fold the paper, it is more like I have divided the page into squares. :sweat_smile: :smiling_face_with_tear:

1 Like
#12

Don’t fold it like that. Instead take a thin but long paper, take the end on your right and move it to the end of your left. This way it will be folded once, both ends will be on your left and on your right there will be the folding. Then repeat, moving the end your your right and moving it to the left folding it twice.
If you unfold and put the paper sideways you will get the figure of order-n being n the number of times you fold it.

Does it make sense?

1 Like
#13

I had to write it down and fold many papers irl to figure out an algorithm.
Then I have written 5 different approaches in order to get one more or less correct, elegant and functional.
After completing I have seen simpler and more elegant solutions done by others.
I think the key is to look for patterns to be able to find out what goes into each position.

#14

IMG_0792
After 2 folds

IMG_0793
After 3 folds

IMG_0794
Expanding the 3-folds result

1 Like
#15

I think that your sequences for order 4 and 5 are wrong.

  • the lenght sequence for every order is 2**order-1. Then lenght for order 4 is 15 and lenght for order 5 is 31.
  • the right sequence is for order 4 is 110110011100100; your initial think about the begin of sequence N+1 (same as sequence N) works right in my opinion.

I think that my algorithm is ok, and my solution works with all tests cases except last two, because process has timed out. Now I´m looking for a way to give an answer without calculate all N-1 sequences. This is the very hard problem of this puzzle.

#16

Your order-4 is incorrect. Your order-5 seems to be too short?

The sequence of order-1 curve is: 1
The sequence of order-2 curve is: 110
The sequence of order-3 curve is: 1101100

Note that all “correct” curve representations have a middle fold “1”. There are 4 possible representations because of different ways you look at the paper, but the puzzle fixed on using just one of them.

IMG_0792a

#17

After some paper calculations and one long strip of paper used to check them, I went with the recursive symbol-by-symbol solution. I was a bit worried about the stack overflows (I used Typescript), but even on max depth it performed pretty well.

Overall pretty interesting problem, props to the author.

2 Likes
#18

_ _
||| |_
_| |
||

for order 4. with example if i begin left bottom i find left, left,right, left left, right, right, right, left , left and right not left.
if i begin right bottom i find left,left, right, left, right so not the right bottom but the left bottom.

#19

order-4
Only one way of path-walking is deemed “correct”.

You can fold an order-4 curve back into order-3 by using the circled middle point to collapse the paper (and keeping all other folds at right-angles).

2 Likes
#20

The sequence is encoded by a(n) = (1+K(-1/n))/2, where n is the index in the sequence and K is the Kronecker symbol.

2 Likes
#21

thanks for the explanations. I solved the puzzle. it’s easy in reality but the order 4 can confused if you don’t translate correctly as for me.
maybe add the order 4 number in the list .in the puzzle explaining.

2 Likes