Ciemny czarny atrament rozpryskiwał się na białej kartce papieru do drukarki! Oczywistym rozwiązaniem jest złożenie papieru w taki sposób, aby czarno-białe części stykały się i obie stały się szare w miarę rozpraszania atramentu. Następnie rozłóż i zwiń, aż papier będzie równie szary.

Znalezienie najlepszego sposobu na wykonanie tych fałd jest Twoim zadaniem w tym wyzwaniu kodowania. Ten Pastebin zawiera cztery różnej wielkości siatki zer i jedynek. Każda siatka przedstawia kawałek poplamionego atramentem papieru, który należy zmienić na szary. Zera to papier, a te to atrament.

W tych siatkach obowiązują tylko poziome i pionowe fałdy wzdłuż przestrzeni między liniami i kolumnami. Po złożeniu pary uśpionych wartości uśrednia się. Fałdy są wykonywane pojedynczo i zawsze rozkładane. Fałdy zmieniają tylko rozkład atramentu, a nie rozmiar papieru.

Rn oznacza złożenie lewej krawędzi siatki w prawo, zaczynając od n-tej kolumny. Dn oznacza złożenie górnej krawędzi siatki w dół, zaczynając od n-tego rzędu. (n ma indeks 1)

Przykład

Biorąc pod uwagę tę siatkę

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

składanie D1 oznacza „złóż cały górny rząd w dół, a następnie rozłóż”.

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

Wtedy R2 wyprodukuje

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

a inny R2 nic nie zmieni.

Cel

Twoim celem jest napisanie algorytmu, który znajdzie najlepszą sekwencję rozkładania atramentu dla każdej z czterech siatek, używając dokładnie 8 fałd za każdym razem. Fałdy mogą być dowolną kombinacją Rs lub Ds.

Punktacja

Wynik twojego zgłoszenia jest sumą twoich wyników dla każdej siatki. Wynik siatki jest sumą bezwzględnych różnic między każdą z jej wartości a jej średnią (jej suma podzielona przez powierzchnię). Niższe wyniki są lepsze. Wynik 0 jest idealny, ale prawdopodobnie jest niemożliwy tylko w 8 fałdach.

Musisz podać swoje cztery 8-etapowe sekwencje składania ze swoim kodem w swojej odpowiedzi. Dzięki temu możemy zweryfikować, czy Twój algorytm naprawdę działa.

Proszę umieścić je w tej formie:

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

Oto skrypt w języku Python, który obliczy Twoje wyniki na podstawie sekwencji składania.

Oczywiście nie powinieneś kopiować przesyłania sekwencji przez inną osobę. Sekwencje dla każdej siatki należą tylko do osoby, która je utworzyła.

Wyjaśnienia

• Idealnie twój algorytm będzie działał dobrze na każdej siatce, chociaż możesz go dostosować do tych konkretnych.

• Musisz przesłać kod wraz z sekwencją. Aby wygrać, potrzebujesz najmniejszego zestawu 8-krokowych sekwencji składania, który nie został jeszcze opublikowany, a także algorytmu, który jest do publicznej kontroli. Wyjaśnij swój kod, nie zaciemniaj go.

• Siatka nigdy nie powinna zawierać liczb ujemnych.

• Obowiązują standardowe luki.

Pyton

Wyczerpująco wypróbowuje różne kombinacje foldów dla pierwszych kilku foldów, a następnie robi resztę foldów, stosując zachłanne podejście.

Wyczerpujące podejście jest ograniczone do rozsądnego zakresu fałd na środku, tak że nie zajmie to wieczności, nie ignorując zbyt wielu możliwych fałd, aby uzyskać dobre minimum.

Ran używając pypy na moim MacBook Air.

Odpowiedzi:

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

Wyjścia:

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

Łączny wynik: 7,91125 + 16,33375 + 42,13 + 32,30875 = 98,69375

Kod:

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

C, 16,344 (4 minuty 33 sekundy)

Najlepsze znalezione ruchy: D6, D13, R19, D9, D11, R21, D10, R20

Wykorzystuje mieszankę Monte Carlo i wspinaczki górskiej. Jestem pewien, że można by go uruchomić znacznie szybciej.

#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;
}