A tinta preta escura espalhou-se por toda a folha de papel da impressora! A solução óbvia é dobrar o papel para que as partes em preto e branco se encontrem e ambas se tornem cinza à medida que a tinta se difunde. Depois, desdobre e desdobre até o papel ficar igualmente cinza.

Encontrar a melhor maneira de fazer essas dobras é sua tarefa neste desafio de codificação. Este Pastebin contém quatro grades de tamanhos diferentes de uns e zeros. Cada grade representa um pedaço de papel espalhado por tinta que você deve ficar cinza. Zeros são papel e outros são tinta.

Nestas grades, apenas dobras horizontais e verticais ao longo dos espaços entre linhas e colunas são válidas. Quando uma dobra é feita, os pares de valores sobrepostos são calculados como média. As dobras são feitas uma de cada vez e sempre se desdobram. As dobras alteram apenas a distribuição da tinta, não o tamanho do papel.

Rn denota dobrar a borda esquerda da grade para a direita, começando após a enésima coluna. Dn denota dobrar a borda superior da grade para baixo, começando após a enésima linha. (n é indexado 1)

Exemplo

Dada esta grade

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

uma dobra D1 significa "dobre toda a linha superior para baixo e desdobre".

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

Então um R2 produzirá

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

e outro R2 não vai mudar nada.

Objetivo

Seu objetivo é escrever um algoritmo que encontre a melhor sequência de dobras de espalhamento de tinta para cada uma das quatro grades, usando exatamente 8 dobras de cada vez. As dobras podem ser qualquer combinação de Rs ou Ds.

Pontuação

A pontuação do seu envio é a soma das suas pontuações para cada grade. A pontuação de uma grade é a soma das diferenças absolutas entre cada um de seus valores e sua média (sua soma dividida por sua área). Pontuações mais baixas são melhores. Uma pontuação 0 é perfeita, mas provavelmente é impossível em apenas 8 dobras.

Você deve relatar suas quatro seqüências de dobramento de 8 etapas com seu código em sua resposta. Isso é para que possamos verificar se seu algoritmo realmente funciona.

Coloque-os neste formulário:

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

Aqui está um script Python que calculará sua pontuação de acordo com suas seqüências dobráveis.

Naturalmente, você não deve copiar o envio da sequência de outra pessoa. As seqüências para cada grade pertencem apenas à pessoa que as criou pela primeira vez.

Esclarecimentos

• Idealmente, seu algoritmo funcionará bem em qualquer grade, embora você possa adaptá-lo a esses específicos.

• Você deve enviar seu código com sua sequência. Para vencer, você precisa do conjunto de menor pontuação de sequências dobráveis ​​de 8 etapas que ainda não foram publicadas e também de um algoritmo que resiste ao escrutínio público. Explique seu código, não ofusque-o.

• A grade nunca deve conter números negativos.

• Aplicam-se brechas padrão.

Pitão

Tenta exaustivamente diferentes combinações de dobras para as primeiras dobras, depois faz o resto das dobras usando uma abordagem gananciosa.

A abordagem exaustiva é limitada a uma faixa razoável de dobras no centro, de modo que não demore uma eternidade, sem ignorar muitas dobras possíveis para produzir um bom mínimo.

Corri usando pypy no meu macbook air.

Respostas:

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

Saídas:

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

Pontuação total: 7.91125 + 16.34375 + 42.13 + 32.30875 = 98.69375

Código:

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 minutos e 33 segundos)

Melhores movimentos encontrados até agora: D6, D13, R19, D9, D11, R21, D10, R20

Usa uma mistura de Monte Carlo e escalada. Pode ser feito para correr muito mais rápido, tenho certeza.

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