Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Dark black ink has splattered all over your white sheet of printer paper! The obvious solution is to fold the paper so black and white parts meet and both become grey as the ink diffuses. Then unfold and refold until your paper is all equally grey.

Finding the best way to make these folds is your task in this coding challenge. This Pastebin contains four different sized grids of ones and zeros. Each grid represents a piece of ink splattered paper that you must turn grey. Zeros are paper and ones are ink.

In these grids, only horizontal and vertical folds along the spaces between lines and columns are valid. When a fold is made the pairs of overlapping values are averaged. Folds are done one at a time and always unfolded. Folds only change the ink distribution, not the size of the paper.

Rn denotes folding the left edge of the grid to the right, starting after the nth column. Dn denotes folding the top edge of the grid downward fold, starting after the nth row. (n is 1-indexed)

Example

Given this grid

0 1 1 1
0 0 0 0
0 0 0 0

a D1 fold means "fold the entire top row down then unfold".

0 0.5 0.5 0.5
0 0.5 0.5 0.5
0   0   0   0

Then an R2 will produce

0.25 0.5 0.5 0.25
0.25 0.5 0.5 0.25
   0   0   0    0

and another R2 will not change anything.

Goal

Your goal is to write an algorithm that finds the best ink-spreading folding sequence for each of the four grids using exactly 8 folds each time. The folds may be any combination of Rs or Ds.

Scoring

The score of your submission is the sum of your scores for each grid. A grid's score is the sum of the absolute differences between each of its values and its average (its sum divided by its area). Lower scores are better. A score of 0 is perfect, but is probably impossible in only 8 folds.

You must report your four 8-step folding sequences with your code in your answer. This is so we can verify your algorithm really works.

Please put them in this form:

20*20R1D2R3D4R5D6R7D8
40*20R1D2R3D4R5D6R7D8
40*40R1D2R3D4R5D6R7D8
20*80R1D2R3D4R5D6R7D8

Here is a Python script that will calculate your scores given your folding sequences.

Naturally you should not copy someone else's sequence submission. Sequences for each grid only belong to the person who first created them.

Clarifications

  • Ideally your algorithm will work well on any grid, though you can tailor it to these specific ones.

  • You must submit your code with your sequence. To win you need the smallest-scoring set of 8-step folding sequences that has not already been posted, and also an algorithm that stands up to public scrutiny. Explain your code, don't obfuscate it.

  • The grid should never contain negative numbers.

  • Standard loopholes apply.

share|improve this question
1  
I think it's better if you have some test cases, and that participants are expected to give code that produces the sequence, instead of just giving the sequence. –  justhalf Jul 10 at 11:20
1  
Another option is to ask people to give the sequence that they got with their code, but ask them to provide a hash (say SHA-256) of their code as proof that they actually produce it using their own work. I remember seeing that kind of mechanism some time ago, but I can't remember. Can anybody point to that challenge? –  justhalf Jul 10 at 12:00
1  
Another way to prohibit hard-coding is to make the challenge open to other test cases as well. –  Howard Jul 10 at 12:00
1  
@Calvin'sHobbies I'd prefer a larger set of test cases, too, to be honest, because some algorithms might fare better on certain grids than others. What you could do is what I did with Vector Racing that each participant may add a test case to the benchmark set. In that case, you'd have to take it on you to test and score all submissions though, because you can't expect early participants to rerun their code with test cases added later. –  Martin Büttner Jul 10 at 12:34
1  
@Calvin'sHobbies Brute force is (19+39)^8 (minus some symmetries) which is much more feasable. –  Howard Jul 10 at 17:15

2 Answers 2

up vote 7 down vote accepted
+250

Python

Exhaustively tries different combinations of folds for the first few folds, then does the rest of the folds using a greedy approach.

The exhaustive approach is bounded within a reasonable range of folds in the center, such that it won't take forever, while not ignoring too many possible folds to yield a good minimum.

Ran using pypy on my macbook air.

Answers:

20*20D9R15R6D11R10R9D10R11
40*20D6D13D9R19R21R20D11D10
40*40D21R21R11D19R23R20D23D15
20*80D33D47D40R10D39D41R9R11

Outputs:

Exhaustive folds levels: 3
Percentage pruned from sides from exhaustive folds: 0.2
Time taken: 4.016076s
Score: 7.91125
20*20D9R15R6D11R10R9D10R11

Exhaustive folds levels: 3
Percentage pruned from sides from exhaustive folds: 0.2
Time taken: 28.529278s
Score: 16.34375
40*20D6D13D9R19R21R20D11D10

Exhaustive folds levels: 3
Percentage pruned from sides from exhaustive folds: 0.25
Time taken: 98.430465s
Score: 42.13
40*40D21R21R11D19R23R20D23D15

Exhaustive folds levels: 3
Percentage pruned from sides from exhaustive folds: 0.25
Time taken: 234.873787s
Score: 32.30875
20*80D33D47D40R10D39D41R9R11

Total Score: 7.91125 + 16.34375 + 42.13 + 32.30875 = 98.69375

Code:

import time, math
from collections import deque

numberOfFolds = 8 # Total number of folds

startTime = time.clock()

exec "grid = ("+"""
1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 0 1 1
1 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 1
0 1 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 0
0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 1 0 0 0 1
0 1 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 0
1 0 1 1 0 1 1 1 1 1 1 0 0 1 0 1 0 1 0 1
0 1 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0
1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1
1 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 0
0 1 1 0 0 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1
0 1 1 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 1 0
0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 1
0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1
1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 0 0 1
0 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 0
0 1 1 0 1 0 0 1 0 0 1 1 1 1 1 0 1 1 0 0
0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 1 1 1 1 1 
""".replace(" ",",").replace("\n","],[")[2:-2]+")"

def getAverage(grid):
    count = total = 0
    for j in grid:
        for i in j:
            count += 1
            total += i
    return total/float(count)

def getScore(grid, average):
    score = 0
    for j in grid:
        for i in j:
            score += abs(average-i)
    return score

def downFoldedGrid(grid, row, width, height, copy=True):
    if copy: grid = [r[:] for r in grid]
    foldRange = min(row, height-row)
    for j in xrange(foldRange):
        rowRef1 = grid[row+j]
        rowRef2 = grid[row-1-j]
        for i in xrange(width):
            rowRef1[i] = rowRef2[i] = (rowRef1[i] + rowRef2[i]) * .5
    return grid

def downFoldedScore(grid, score, average, row, width, height):
    foldRange = min(row, height-row)
    average2  = 2*average
    for j in xrange(foldRange):
        rowRef1 = grid[row+j]
        rowRef2 = grid[row-1-j]
        a = b = c = 0
        for i in xrange(width):
            a = rowRef1[i] 
            b = rowRef2[i]
            c = a+b
            score += abs(average2-c) - abs(average-a) - abs(average-b)
    return score

def rightFoldedGrid(grid, column, width, height, copy=True):
    if copy: grid = [r[:] for r in grid]
    foldRange = min(column, width-column)
    for j in xrange(height):
        rowRef = grid[j]
        for i in xrange(foldRange):
            a = column+i
            b = column-1-i
            rowRef[a] = rowRef[b] = (rowRef[a] + rowRef[b]) * .5
    return grid

def rightFoldedScore(grid, score, average, column, width, height):
    foldRange = min(column, width-column)
    average2 = 2*average
    for j in xrange(height):
        rowRef = grid[j]
        a = b = c = 0
        for i in xrange(foldRange):
            a = rowRef[column+i]
            b = rowRef[column-1-i]
            c = a+b
            score += abs(average2-c) - abs(average-a) - abs(average-b)
    return score

def bestFoldsGreedy(grid, average, maxFolds, width, height):
    score  = getScore(grid, average)
    folds  = []
    append = folds.append
    for z in xrange(maxFolds):
        bestFold      = 0
        bestFoldScore = score
        bestFoldGrid  = grid
        for i in xrange(1, width): #Try all right folds
            foldScore = rightFoldedScore(grid, score, average, i, width, height)
            if foldScore < bestFoldScore:
                bestFold      = i
                bestFoldScore = foldScore
        for i in xrange(1, height): #Try all down folds
            foldScore = downFoldedScore(grid, score, average, i, width, height)
            if foldScore < bestFoldScore:
                bestFold      = -i
                bestFoldScore = foldScore
        if bestFold:
            append(bestFold)
            score = bestFoldScore
            if bestFold > 0: rightFoldedGrid(grid, bestFold, width, height, False)
            else:            downFoldedGrid(grid, -bestFold, width, height, False)
    return score, folds


# Get the height and width
height  = len(grid)
width   = len(grid[0])

# Transpose the grid if height > width for better locality of reference
transposed = False
if height > width:
    grid = [[grid[i][j] for i in range(height)] for j in range(width)]
    transposed = True
    height, width = width, height

# The exhaustive grids and folds attempted
exhaustiveGridsAndFolds = deque([(grid,[])])
popleft = exhaustiveGridsAndFolds.popleft
append  = exhaustiveGridsAndFolds.append

# Set the bounds to exhaustively test for
exhaustiveLevels   = 3
prunePadding       = [0.2, 0.25][width*height > 1000]
leftBound          = int(max(width*prunePadding, 1))
rightBound         = int(width*(1.0-prunePadding))
topBound           = int(max(height*prunePadding, 1))
bottomBound        = int(height*(1.0-prunePadding))

# Populate the exhaustive grids and folds
while 1:
    grid, folds = popleft()
    if len(folds) == exhaustiveLevels:
        append((grid, folds))
        break
    for i in xrange(leftBound, rightBound):
        if i not in folds:
            append((rightFoldedGrid(grid, i, width, height), folds+[i]))
    for i in xrange(topBound, bottomBound):
        if -i not in folds:
            append((downFoldedGrid(grid, i, width, height), folds+[-i]))

# Test all the exhaustive grids and folds greedily
average             = getAverage(grid)
bestFinalScore      = getScore(grid, average)
bestFinalFolds      = []
numberOfGreedyFolds = numberOfFolds-exhaustiveLevels
while exhaustiveGridsAndFolds:
    grid, exhaustiveFolds = popleft()
    finalScore, greedyFolds = bestFoldsGreedy(grid, average, numberOfGreedyFolds, width, height)
    if finalScore <= bestFinalScore:
        bestFinalScore = finalScore
        bestFinalFolds = exhaustiveFolds + greedyFolds


# Repeat the last fold till the total number of folds if needed
if len(bestFinalFolds) < numberOfFolds:
    bestFinalFolds += [bestFinalFolds[-1]]*(numberOfFolds-len(bestFinalFolds))

# Print the best result
foldsString = ""
down  = "D"
right = "R"
if transposed:
    down,  right  = right,  down
    width, height = height, width
for fold in bestFinalFolds:
    if   fold > 0: foldsString += right+str(fold)
    elif fold < 0: foldsString += down+str(-fold)
print "Exhaustive folds levels: " + str(exhaustiveLevels)
print "Percentage pruned from sides from exhaustive folds: " + str(prunePadding)
print "Time taken: " + str(time.clock()-startTime) + "s"
print "Score: " + str(bestFinalScore)
print str(width) + "*" + str(height) + foldsString
share|improve this answer
2  
Okay, I can stop working on this now. This would have been exactly my algorithm. –  Martin Büttner Jul 10 at 13:59
    
@bitpwner You're still using 0.5 as the grid average but it's actually slightly different depending on the grid. With my script at ideone.com/5wbrOQ you are scoring 8.26, 17.71875, 44.61125, and 32.72 for a 103.31 total. –  Calvin's Hobbies Jul 10 at 23:45

C, 16.344 (4 minutes 33 seconds)

Best moves found so far: D6,D13,R19,D9,D11,R21,D10,R20

Uses a mixture of Monte Carlo and hill climbing. Could be made to run much faster, I'm sure.

#include <stdio.h>
#include <stdlib.h>

/*

Best result so far: 16.344
D6,D13,R19,D9,D11,R21,D10,R20

real    4m33.027s
user    4m12.787s
sys 0m1.334s

*/

#define GRID_WIDTH   40
#define GRID_HEIGHT  20
#define GRID_SIZE    (GRID_WIDTH * GRID_HEIGHT)
#define NUM_FOLDS    8
#define MAX_VALUE    (1 << NUM_FOLDS)
#define TARGET_VALUE (MAX_VALUE / 2)

double score_grid(short *g) {
  int i, sum;
  for (i=sum=0; i<GRID_SIZE; i++) sum += abs(*g++ - TARGET_VALUE);
  return sum * 1.0 / MAX_VALUE;
}

void h_fold(short *g, int fold_row) {
  int x, y0, y1;
  if (fold_row<1 || fold_row>=GRID_HEIGHT) return;
  y1 = fold_row * GRID_WIDTH;
  y0 = y1 - GRID_WIDTH;
  while (y0>=0 && y1<GRID_SIZE) {
    for (x=0; x<GRID_WIDTH; x++) {
      g[y0+x] = g[y1+x] = (g[y0+x] + g[y1+x]) >> 1;
    }
    y0 -= GRID_WIDTH;
    y1 += GRID_WIDTH;
  }
}

void v_fold(short *g, int fold_col) {
  int y, x0, x1;
  if (fold_col<1 || fold_col>=GRID_WIDTH) return;
  x1 = fold_col;
  x0 = x1 - 1;
  while (x0>=0 && x1<GRID_WIDTH) {
    for (y=0; y<GRID_SIZE; y+=GRID_WIDTH) {
      g[y+x0] = g[y+x1] = (g[y+x0] + g[y+x1]) >> 1;
    }
    x0--;
    x1++;
  }
}

void print_grid(short *g) {
  int i=0, checksum=0;
  while (i<GRID_SIZE) {
    checksum += *g;
    printf("%3X",*g++);
    if ((++i) % GRID_WIDTH == 0) putchar('\n');
  }
  if (checksum != GRID_SIZE * TARGET_VALUE) printf("Bad total: %d\n",checksum);
}

void init_grid(short *g) {
  int i;
  static short *start_grid=0, *sg;
  if (!start_grid) {
    char *src = "11010110100011100000001000110001001101010111000100100100000101100000101111000010"
                "10110011111011111101101011111001000010101010110111000101000001011111101000011001"
                "10000111111001111011100101101001101100001110001101001011010011011110101000011100"
                "00110010100010100010110101001100110001100100111010000110100110001000110000111101"
                "01000001110000101000110101011011101010111110101010110000001011010010000011101000"
                "11111011111100100100100010111010111111000101011110000100111111111000110101101101"
                "00110100010111101111000011011010000110001001101010010101110010110111101001011111"
                "10110001101100001110010100110100010011011110100110000100100111101101000010011001"
                "00011100110100111101000000001000010100001101001011000101101001000100111100011010"
                "00010110001110011111100011101111011100111001110011111011010010000100101111101001";
    start_grid = malloc(GRID_SIZE * sizeof(short));
    for (i=0; i<GRID_SIZE; i++) start_grid[i] = (src[i]&1)<<NUM_FOLDS;
  }
  sg = start_grid;
  for (i=0; i<GRID_SIZE; i++) *g++ = *sg++;
}

double evaluate(int *moves) {
  short *grid;
  double score;
  int i, f;
  grid = malloc(GRID_SIZE * sizeof(short));
  init_grid(grid);
  for (i=0; i<NUM_FOLDS; i++) {
    f = moves[i];
    if (f>0) v_fold(grid,f);
    else h_fold(grid,-f);
  }
  score = score_grid(grid);
  free(grid);
  return score;
}


double optimize_folding(int *moves, double score) {
  int opt_cycle, i, which_fold, new_move, f1, f2, t;
  double s;

  for (opt_cycle=0; opt_cycle<1000; opt_cycle++) {
    for (i=0; i<NUM_FOLDS; i++) {
      which_fold = random() % NUM_FOLDS;
      do {
        if (random()&1) new_move = random() % (GRID_WIDTH-1) + 1;
        else new_move = -(random() % (GRID_HEIGHT-1) + 1);
      } while (moves[which_fold]==new_move);
      t = moves[which_fold];
      moves[which_fold] = new_move;
      s = evaluate(moves);
      if (s>score) moves[which_fold] = t;
      else score = s;
    }
    for (i=0; i<NUM_FOLDS; i++) {
      f1 = random() % NUM_FOLDS;
      do {
        f2 = random() % NUM_FOLDS;
      } while (f2==f1);
      t = moves[f1];
      moves[f1] = moves[f2];
      moves[f2] = t;
      s = evaluate(moves);
      if (s>score) {
        t = moves[f1];
        moves[f1] = moves[f2];
        moves[f2] = t;
      }
      else score = s;
    }
  }

  return score;
}

void show_moves(int *moves) {
  int i, m;
  for (i=0; i<NUM_FOLDS; i++) {
    m = moves[i];
    printf("%c%d%c",(m>0)?'R':'D',abs(m),((i+1)%NUM_FOLDS)?',':'\n');
  }
}

int main() {
  int i, j, moves[NUM_FOLDS], save_moves[NUM_FOLDS];
  double score, best_score = 1.0E+99;

  srandomdev();
  for (i=0; i<400; i++) {
    for (j=0; j<NUM_FOLDS; j++) {
            if (random()&1) moves[j] = random() % (GRID_WIDTH-1) + 1;
            else moves[j] = -(random() % (GRID_HEIGHT-1) + 1);
        }
        score = optimize_folding(moves, 1.0E+99);
        if (score<best_score) {
            best_score = score;
            for (j=0; j<NUM_FOLDS; j++) save_moves[j]=moves[j];
        }
    }
  printf("%.3lf\n",best_score);
  show_moves(save_moves);
  return 0;
}
share|improve this answer
    
Bah. Just noticed that the question has changed. I'll have to fix this later... –  squeamish ossifrage Jul 10 at 14:12
    
Currently I'm getting a decent score of 16.34375 for your 40*20. –  Calvin's Hobbies Jul 10 at 23:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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