Tinta hitam gelap telah berhamburan di seluruh lembar kertas printer Anda! Solusi yang jelas adalah melipat kertas sehingga bagian hitam dan putih bertemu dan keduanya menjadi abu-abu saat tinta berdifusi. Kemudian buka dan buka kembali sampai kertas Anda semuanya berwarna abu-abu.

Menemukan cara terbaik untuk membuat lipatan ini adalah tugas Anda dalam tantangan pengkodean ini. Pastebin ini berisi empat ukuran grid satu dan nol. Setiap kotak mewakili selembar kertas berceceran tinta yang harus Anda ubah menjadi abu-abu. Nol adalah kertas dan tinta.

Dalam kisi-kisi ini, hanya lipatan horizontal dan vertikal di sepanjang ruang antara garis dan kolom yang valid. Ketika lipatan dibuat, pasangan nilai yang tumpang tindih dirata-rata. Lipatan dilakukan satu per satu dan selalu dibuka. Lipatan hanya mengubah distribusi tinta, bukan ukuran kertas.

Rn menunjukkan lipat tepi kiri kisi ke kanan, dimulai setelah kolom ke-n. Dn menunjukkan lipat tepi atas grid ke bawah, dimulai setelah baris ke-n. (n diindeks 1)

Contoh

Diberi kisi ini

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

lipatan D1 berarti "lipat seluruh baris atas ke bawah lalu buka".

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

Maka R2 akan menghasilkan

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

dan R2 lain tidak akan mengubah apa pun.

Tujuan

Tujuan Anda adalah untuk menulis algoritma yang menemukan urutan lipat penyebaran tinta terbaik untuk masing-masing dari empat kisi menggunakan tepat 8 lipatan setiap kali. Lipatan dapat berupa kombinasi Rs atau Ds.

Mencetak gol

Skor kiriman Anda adalah jumlah skor Anda untuk setiap kisi. Skor kisi adalah jumlah dari perbedaan absolut antara masing-masing nilainya dan rata-rata (jumlahnya dibagi dengan wilayahnya). Skor yang lebih rendah lebih baik. Skor 0 sempurna, tetapi mungkin tidak mungkin hanya dalam 8 lipatan.

Anda harus melaporkan empat urutan lipat 8 langkah dengan kode Anda dalam jawaban. Ini agar kami dapat memverifikasi algoritma Anda benar-benar berfungsi.

Harap letakkan di formulir ini:

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

Berikut ini adalah skrip Python yang akan menghitung skor Anda mengingat urutan lipat Anda.

Secara alami Anda tidak harus menyalin pengiriman urutan orang lain. Urutan untuk setiap kotak hanya milik orang yang pertama kali membuatnya.

Klarifikasi

• Idealnya, algoritme Anda akan berfungsi dengan baik di kisi apa pun, meskipun Anda dapat menyesuaikannya dengan yang khusus ini.

• Anda harus mengirimkan kode Anda dengan urutan Anda. Untuk menang, Anda membutuhkan set skor terkecil dari urutan lipat 8-langkah yang belum diposting, dan juga algoritma yang berdiri untuk pengawasan publik. Jelaskan kode Anda, jangan mengaburkannya.

• Kotak tidak boleh berisi angka negatif.

• Celah standar berlaku.

Python

Selesaikan mencoba berbagai kombinasi lipatan untuk beberapa lipatan pertama, kemudian lakukan sisa lipatan menggunakan pendekatan serakah.

Pendekatan lengkap dibatasi dalam rentang lipatan yang wajar di tengah, sehingga tidak akan berlangsung selamanya, sementara tidak mengabaikan terlalu banyak lipatan yang mungkin untuk menghasilkan minimum yang baik.

Berlari menggunakan pypy di macbook air saya.

Jawaban:

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

Output:

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 Skor: 7.91125 + 16.34375 + 42.13 + 32.30875 = 98.69375

Kode:

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 menit 33 detik)

Bergerak terbaik yang ditemukan sejauh ini: D6, D13, R19, D9, D11, R21, D10, R20

Menggunakan campuran Monte Carlo dan panjat bukit. Bisa dibuat untuk berlari lebih cepat, saya yakin.

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