Thin Paper Folding
This is a "lighter" version of the challenge Paper Folding for the win. This challenge is being posted as a different challenge with many modifications in order to try and get wider range of interesting answers.
For anyone who is answering the first challenge, I marked the changes with bold
(also note that the examples and the cases are different).
"How many times can you fold a paper?" - This well known question led to many arguments, competition, myths and theories.
Well, the answer to that question depends on many properties of the paper (length, strength, thickness, etc...).
In this challenge we will try to fold a piece of paper as much as we can, however, there will be some constraints and assumptions.
Assumptions:
- The paper will be represented in pixel-sized cells. The length and width of the paper is
N x M
respectively (which means you can not fold a pixel/cell in the middle). - Each spot (pixel) of the paper has its own thickness (as a result of a fold).
A paper:
A paper will be represented as a 2D M x N
Matrix as the top-view of the paper. Each cell of the matrix will contain a number that will represent the thickness of the paper's pixel. The initial thickness of all pixels is 1.
Paper representation example:
Option 1 Option 2
1 1 1 1 1 1 1 1 1 [[1,1,1,1,1,1,1,1,1],
1 1 1 1 1 1 1 1 1 [1,1,1,1,1,1,1,1,1],
1 1 1 1 1 1 1 1 1 [1,1,1,1,1,1,1,1,1],
1 1 1 1 1 1 1 1 1 [1,1,1,1,1,1,1,1,1],
1 1 1 1 1 1 1 1 1 [1,1,1,1,1,1,1,1,1]]
A fold:
A fold is a manipulation on the matrix defined as follows:
Assuming there is a 2 pixels fold from the right side of the paper in the example above, the size of the paper will now be N-2 x M
and the new thickness of the pixels will be the summation of the previous thickness of the cell + the thickness of the mirrored cell relative to the fold cut:
___
/ \
\/<-- |
1 1 1 1 1 1 1|1 1 1 1 1 1 1 2 2
1 1 1 1 1 1 1|1 1 1 1 1 1 1 2 2
1 1 1 1 1 1 1|1 1 ===> 1 1 1 1 1 2 2
1 1 1 1 1 1 1|1 1 1 1 1 1 1 2 2
1 1 1 1 1 1 1|1 1 1 1 1 1 1 2 2
Goal:
The goal is to write a program that will output a set of folds that result in the minimum possible number of remaining pixels for any given input (size of paper and threshold).
Constraints:
- You can fold a paper from 4 directions only: Top, Left, Right, Bottom.
- The fold will be symmetric, which means, if you fold 2 pixels of the paper from the left, all of the cells in the first and second columns will be folded 2 pixels "mirrorly".
- A thickness threshold of a paper cell will be given as an input, a cell can not exceed that threshold at any time, which means, you will not be able to fold the paper, if that specific fold will result exceeding the thickness threshold.
- Number of pixels being fold must be between 0 and the length/width of the paper.
- Do not exceed with your folding the initial dimensions and position of the paper. ( there is no pixel -1 )
Input:
- Two integers
N
andM
for the size of the paper - Thickness threshold
Output:
- A list of folds that yields a valid paper (with no pixels exceeding the thickness threshold) folded in any way you want (using any heuristic or algorithm you've implemented).
Scoring:
Since this is a code-golf, the shortest code wins.
Examples:
Example 1:
Input: N=6 , M=4, Threshold=9
1 1 1 1 1 1
1 1 1 1 1 1 fold 2 pixels from top 2 2 2 2 2 2 fold 3 pixels from right 4 4 4 fold 1 pixel from top
1 1 1 1 1 1 ======================> 2 2 2 2 2 2 =======================> 4 4 4 =====================> 8 8 8 No more fold possible
1 1 1 1 1 1
Optional outputs:
[2T,3R,1T]
------------or----------
[[2,top],[3,right],[1,top]]
------------or----------
Top 2
Right 3
Top 1
------or any other sensible readable way------
--------notice the order is inportant---------
Example 2:
Input: N=6 , M=4, Threshold=16
1 1 1 1 1 1
1 1 1 1 1 1 fold 2 pixels from top 2 2 2 2 2 2 fold 3 pixels from right 4 4 4 fold 1 pixel from top fold 1 pixel from left
1 1 1 1 1 1 ======================> 2 2 2 2 2 2 =======================> 4 4 4 =====================> 8 8 8 =====================> 16 8 No more fold possible
1 1 1 1 1 1
Optional outputs:
[2T,3R,1T,1L]
------------or----------
[[2,top],[3,right],[1,top],[1,left]]
------------or----------
Top 2
Right 3
Top 1
Left 1
------or any other sensible readable way------
--------notice the order is inportant---------
Some Test cases:
Case 1:
Input: N = 16 , M = 6 , Threshold = 3
Output: [2, top], [2, top]
(This fold will result 32 remaining pixels)
(Example for bad output will be splitting in half, yields 48 remaining pixels)
Case 2:
Input: N = 16 , M = 6 , Threshold = 24
Output:
8 RIGHT
4 RIGHT
3 BOTTOM
1 TOP
1 TOP
(This fold will result 4 remaining pixels)
Case 3:
Input: N=6 , M=4, Threshold=9
Output: [2T,3R,1T]
Case 4:
Input: N=6 , M=4, Threshold=16
Output: [2T,3R,1T,1L]
Check validity
In the previous challenge I wrote a program that checks the validity of foldings and the validity of the resulted paper after folding (no exceeding threshold). You can use the same program, but you need to generate the paper itself as a matrix as an input to the function:
This nodejs program will:
- Check if your folded papers are valid
- Check if your steps are valid
How to use:
Call the desired function in the footer.
Call validator with threshold, initial paper, and a list of steps with the format [x,d]
for folding x
pixels from d
direction. d
is one of the following strings: "RIGHT","LEFT","TOP","BOTTOM".
This function will print if the final paper as a matrix and the amount of pixels reduced.
Output will look like this:
*** PAPER IS VALID ***
Init length: 240, New length: 180, Pixels removed (score): 60
Or, if the paper isn't valid:
*** PAPER UNVALID ***
NO SCORE :(
You can see call examples commented in the code.
You can also remove the comment in the line // console.log(paper); // If you want to print the paper after each step
to "debug" and print the folded paper after each fold.
2T 2T
give 32 remaining pixels? \$\endgroup\$