Paper Folding for the win

"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).
• Unlike real paper, each spot (pixel) of the paper has its own thickness.

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. Area with no paper is the cell with the number 0.

Paper representation example:

     Option 1                        Option 2

2 1 1 1 1 1 1 1 2              [[2,1,1,1,1,1,1,1,2],
1 1 1 1 2 1 1 1 1              [1,1,1,1,2,1,1,1,1],
1 1 1 2 3 2 1 1 1              [1,1,1,2,3,2,1,1,1],
1 1 1 1 2 1 1 1 1              [1,1,1,1,2,1,1,1,1],
2 1 1 1 1 1 1 1 2              [2,1,1,1,1,1,1,1,2]]


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:

            ___
/   \
\/<-- |
2 1 1 1 1 1 1|1 2            2 1 1 1 1 3 2
1 1 1 1 2 1 1|1 1            1 1 1 1 2 2 2
1 1 1 2 3 2 1|1 1    ===>    1 1 1 2 3 3 2
1 1 1 1 2 1 1|1 1            1 1 1 1 2 2 2
2 1 1 1 1 1 1|1 2            2 1 1 1 1 3 2


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 in each case, 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:

• A paper (represented as described before)
• 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:

The goal is writing a program that will output a set of folds that result in the minimum possible number of remaining pixels for any input.

Since this is a , the shortest code wins.

Examples:

Example:

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---------


Some Test cases:

Case 1:

N = 17 , M = 11 , Threshold =  16
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 2 1 1 0 0 0 0 0 0
0 0 0 0 0 1 1 2 3 2 1 1 0 0 0 0 0
0 0 0 0 1 1 1 1 2 1 1 1 1 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 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 1 2
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2


Case 2:

N = 20 , M = 9 , Threshold =  32
1 1 1 1 1 1 1 1 1 8 8 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 8 1 1 8 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 8 1 1 1 1 8 1 1 1 1 1 1 1
1 1 1 1 1 1 8 1 1 1 1 1 1 8 1 1 1 1 1 1
1 1 1 1 1 8 1 1 1 1 1 1 1 1 8 1 1 1 1 1
1 1 1 1 1 1 8 1 1 1 1 1 1 8 1 1 1 1 1 1
1 1 1 1 1 1 1 8 1 1 1 1 8 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 8 1 1 8 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 8 8 1 1 1 1 1 1 1 1 1


Case 3:

N = 10 , M = 10 , Threshold =  29
1 1 1 1 1 1 1 1 1 1
1 1 9 1 1 1 1 9 1 1
1 9 9 9 1 1 9 9 9 1
1 1 9 1 1 1 1 9 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 9 1 1 1 1 9 1 1
1 9 9 9 1 1 9 9 9 1
1 1 9 1 1 1 1 9 1 1
1 1 1 1 1 1 1 1 1 1


Case 4:

N = 20 , M = 12 , Threshold =  23
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 4 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 4
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3
1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4
1 1 1 3 4 3 1 1 1 1 1 1 1 1 1 1 2 3 4 4
1 1 1 1 3 1 1 1 1 1 1 1 1 1 2 2 3 4 4 4
1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 3 4 4 4 3
1 1 1 1 1 1 1 1 2 2 2 2 2 3 4 4 4 3 3 2
2 2 1 1 1 1 1 1 1 1 2 2 2 2 2 3 3 2 1 1
4 3 2 1 1 1 1 1 2 2 3 3 2 2 1 1 1 1 1 1
5 4 3 2 1 1 1 3 3 2 2 1 1 1 1 1 1 1 1 1


Check validity

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.

• As for the first question, P/S will be 0 and then we can kind of say something/0 is "Inf" which is the highest score and the bottom of the leaderboard. But I got the point in the example Dominic gave. I will go back to my original scoring plan, and consider only the amount of pixels removed. I am editing with the new scoring now. Thanks :) Aug 1, 2020 at 11:36
• I also added this: "Papers with no reduced pixels are also considered not valid". So making no folds at all or making folds that are all 0-pixels sized - yields an invalid paper result, which is not eligible for scoring. Aug 1, 2020 at 12:36
• Would it be unreasonable to insist that every program removes the maximum possible number of pixels? Then one could remove 'remaining pixels' from the score altogether, and it'd just be code-golf... Aug 1, 2020 at 13:19
• In my opinion this challenge is very interesting but I think you can mostly only solve this using brute force. Also the modification makes it absolutely more clear but it isn't enough to suit code golf. My suggestion is to have only a thickness of 1. This may make it a lot simpler, opens the door for non brute force solutions and last but not least makes the solutions more.. "Validable".. I really think this can gain a great consensus with this little modification. Aug 1, 2020 at 20:17
• I might do so... I'll keep it for a couple of days, if it gains no interest and no entries, I'll modify it. (If there will be entries I can open a new question with the new less complicated version as well, just to keep both alive) Aug 2, 2020 at 5:48

R, 425 bytes

p=function(m,t){
d=dim(m);r=d[1];c=d[2]
l=apply(matrix(c(seq(l=r-1),rep(0,r+c-2),seq(l=c-1)),,2),1,function(f){n=array(0,pmax(g<-(f-1)%%d+1,h<-(d-f-1)%%d+1))
if(f,n[1:g[1],]<-m[g[1]:1,],n[,1:g[2]]<-m[,g[2]:1])
n[1:h[1],1:h[2]]=n[1:h[1],1:h[2]]+m[(i=g%%d+1)[1]:r,i[2]:c]
if(max(n)<=t)cbind(c(T=f[1],L=f[2]),p(n,t))})
if(!is.null(l))l[[order(sapply(l,function(f){for(x in seq(ncol(f))){d=pmax(f[,x],d-f[,x])};prod(d)}))[1]]]}


Try it online!

This came out much longer than I expected, and also slows-down a lot for big sheets of paper with large thresholds (which could be foreseen from the approach).

Recursively tries each possible fold, keeping only results that don't exceed the threshold at any pixel, and choosing the series of folds that gives the smallest folded size.

Output is 2d list of folds, with 'T' row indicating position of horizontal folds from top, and 'L' row indicating position of vertical folds from left.

Ungolfed version:

fold_paper=p=function(m,t){             # m=matrix of paper thicknesses; t=threshold thickness;
d=dim(m);r=d[1];c=d[2]              # get paper dimensions;
fold_list=apply(                    # iterate over list of possible folds to this paper...
matrix(c(seq(l=r-1),rep(0,r+c-2),seq(l=c-1)),,2),1,
# as a matrix: each row is a possible fold, and the 2
# columns represent positions vertical & horizontal folds;
function(f){
new_m=array(0,pmax(g<-(f-1)%%d+1,h<-(d-f-1)%%d+1))
# make a new matrix for each trial fold, then...
if(f)                       # if it's a horizontal fold...
new_m[1:g[1],]<-m[g[1]:1,]
# add the relevant rows of m, reversed,
else new_m[,1:g[2]]<-m[,g[2]:1])
# otherwise add the relevant cols of m, reversed;
new_m[1:h[1],1:h[2]]=new_m[1:h[1],1:h[2]]+m[(i=g%%d+1)[1]:r,i[2]:c]
# and now add all the unfolded elements of m
if(max(new_m)<=t)               # now, if we didn't exceed the paper thickness threshold...
cbind(c(T=f[1],L=f[2]),p(new_m,t))
# add this fold to the list (labelled with 'T' and 'L',
# and recursively call function with newly_folded paper;
}
)
if(!is.null(fold_list))             # if we ended-up with a list containing any valid folds,
fold_list[[                     # return the element containing the set of folds with...
which.min(                  # the lowest value of...
sapply(fold_list,function(folds){
for(x in seq(ncol(folds))){d=max(folds[,x],d-folds[,x])};prod(d)}))]]
# the number of remaining pixels, calculated from the product
# of the remaining cols & rows after applying all the folds
}

• @SomoKRoceS - The output from test case 3 is: 1T 1T 4T 1T 1L 3L 5L. I tried to use the 'validator' to verify this, but it fails at the last step (link is too long for comments). But without the last step, it's obvious from the final result that the last step would be Ok. Aug 3, 2020 at 14:06
• @SomoKRoceS - The paper size before the last step is 3 high x 6 wide, and the validator gives it a '*** PAPER IS VALID ***' using 1T 1T 4T 1T 1L 3L 1R (which is equivalent to the output above, just doing the last fold the other way...) Aug 3, 2020 at 14:09
• That's a great answer :) About that last step.. yes, my intention (as noted in the challenge) is that a fold can't exceed the original "box" of the paper, so you can use the equivalent opposite fold. The Validator follows that as well. However It can be accepted. Aug 3, 2020 at 20:36
• Ah! I did not understand that constraint from the way it was written, but I now see what you intended... Aug 3, 2020 at 20:46