Paper Folding for the win

Question

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 code-golf, 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.

Answer 1

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
}