9
\$\begingroup\$

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 and M 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 , 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:

  1. Check if your folded papers are valid
  2. 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.

\$\endgroup\$
  • \$\begingroup\$ I think you've got some of the critical program information hidden down in the scoring section. The whole time I was reading, I was wondering what the point of folding is. That information should be either in the "criteria" or "output" sections. I.e., specify that the output should be the folds needed to reach a piece of paper with the minimum top surface area, given the constraints. \$\endgroup\$ – Xcali Aug 4 at 22:50
  • \$\begingroup\$ You're right it comes a little late in the post... I will put it before the input/output as a "goal". \$\endgroup\$ – SomoKRoceS Aug 4 at 22:54
  • \$\begingroup\$ Shouldn't case 1 2T 2T give 32 remaining pixels? \$\endgroup\$ – Dominic van Essen Aug 5 at 8:08
  • \$\begingroup\$ Yes. Edited. Thanks \$\endgroup\$ – SomoKRoceS Aug 5 at 8:12
2
\$\begingroup\$

R, 179 bytes

(or 175 bytes without labelling 'T' and 'L')

function(m,n,t,z=function(l,t){while(t>1){F=c(F,g<-l%/%t);l=l-g;t=t-1};list(l=l,f=F[F>0])})
list(T=z(m,b<-order(sapply(1:t,function(f)z(m,f)$l*z(n,t%/%f)$l))[1])$f,L=z(n,t%/%b)$f)

Try it online!

Outputs a list of ['T' = horizontal folds from top, 'L' = vertical folds from left].

How does it work?

First, note that the final maximal thickness after a combination of horizontal & vertical folds is simply the product of the maximal thicknesses that would be obtained using the horizontal or only the vertical folds. So we can separate the problem into (1) finding the folds in one-dimension (either horizontal or vertical) that minimize the final length for a target thickness, and (2) choosing the best combination of target thicknesses for horizontal & vertical folds that yields the smallest product of lengths.

Now, to find the best set of folds in one-dimension, we note that since the number of folds isn't limited, so it's just as effective to 'roll-up' as to repeatedly fold in half.
Rolling-up has the advantage that if the length isn't perfectly divisible by the target thickness, we can do 'loose' rolls, and minimize the final length by doing the tighter rolls before the 'loose' rolls.

Final algorithm:

  • test all combinations of t1, t2, where t1 x t2 <= target thickness
  • for each t1, find the smallest length l1 achievable by rolling-up the paper along dimension m, starting at the top
  • for each t2, find the smallest length l2 achievable by rolling-up the paper along dimension n, starting on the left
  • choose the combination of t1,t2 that gives the smallest final paper size = l1 x l2

Readable code:

fold_paper=function(m,n,t){                 # m=height, n=width, t=thickness threshold
    min_length=function(l,t){               # min_length=local function that calculates the best
                                            #   way to roll-up a strip of length l up to a 
                                            #   thickness threshold of t
        while(t>1){                         # try to use-up all of the thickness t:
            F=c(F,g<-l%/%t)                 #   each fold g is the current length l integer-divided by the 
                                            #   remaining thickness that we need to use-up
                                            #   (save the list of folds in F)
            l=l-g                           #   reduce the current length after each fold
            t=t-1                           #   and reduce the remaining thickness to use-up
        }
        list(l=l,f=F[F>0])                  #   return l = the final length, f = the list of folds
    }
    best_combo<-order(                      # now pick the best combination of t1,t2
        sapply(1:t,function(f)              # cycle through f=1..t for t1, and inteter(t/f) for t2
            min_length(m,f)$l * min_length(n,t%/%f)$l)
                                            # find the product of lengths for each combination
        )[1]                                # and choose the first one from the list sorted by increasing size
    list( T=min_length(m,best_combo)$f, L=min_length(n,t%/%best_combo)$f )
}                                           # finally, use the best combination to re-calculate
                                            # the best set of horizontal & vertical folds
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.