Construa um solucionador de quebra-cabeças na parte superior da frente

15

Um quebra-cabeça da parte superior da frente é um quebra-cabeça em que você é obrigado a construir uma forma tridimensional de blocos (geralmente cúbicos), com três vistas ortogonais: uma vista superior, uma vista frontal e uma vista lateral.

Por exemplo, com uma vista superior, frontal e lateral da seguinte maneira:

Top:        Front:      Side:
. . . .     . . . .     . . . .
. x x .     . x x .     . x x .
. x x .     . x x .     . x x .
. . . .     . . . .     . . . .

In this problem, the side view is taken from the right.

Um cubo 2x2x2 (com volume 8) satisfaria essa solução, mas é factível no volume 4, se tivermos a seguinte estrutura de camada:

. . . .     . . . .
. x . .     . . x .
. . x .     . x . .
. . . .     . . . .

Existem também alguns acordos insolúveis. Considere por exemplo:

Top:        Front:      Side:
. . . .     . . . .     . . . .
. . . .     . . x .     . . . .
. x . .     . . . .     . x . .
. . . .     . . . .     . . . .

Se a vista superior diz que o bloco é o segundo da esquerda, não há como corresponder à vista frontal que diz que o bloco deve ser o terceiro da esquerda. Portanto, esse arranjo é impossível.


Sua tarefa é criar um programa que, dado um quebra-cabeça arbitrário 4x4 na parte superior da frente, tente resolvê-lo no menor número de cubos ou o declare insolúvel.

Seu programa terá como entrada uma série de 48 bits, representando as vistas superior, frontal e lateral. Eles podem estar no formato que você desejar (uma sequência de 6 bytes, uma sequência de 0 e 1, um número hexadecimal de 12 dígitos etc.), mas a ordem dos bits deve ser mapeada da seguinte forma:

Top: 0x00   Front: 0x10 Side: 0x20
0 1 2 3     0 1 2 3     0 1 2 3
4 5 6 7     4 5 6 7     4 5 6 7
8 9 a b     8 9 a b     8 9 a b
c d e f     c d e f     c d e f

Em outras palavras, os bits vão na ordem da esquerda para a direita, de cima para baixo, na vista superior, depois frontal e lateral.

Seu programa produzirá uma série de 64 bits, indicando os cubos na grade 4x4x4 preenchidos ou indicará que a grade é insolúvel.


Seu programa será pontuado executando uma bateria de 1.000.000 de casos de teste.

Os dados de teste serão gerados usando os hashes MD5 dos números inteiros "000000" a "999999" como seqüências de caracteres, extraindo os primeiros 48 bits (12 hexágonos) de cada um desses hashes e usando-os como entrada para a parte superior frontal. quebra-cabeça lateral. Como exemplo, aqui estão algumas das entradas de teste e os quebra-cabeças que elas geram:

Puzzle seed: 000000   hash: 670b14728ad9
Top:        Front:      Side:
. x x .     . . . x     x . . .
x x x x     . x . x     x . x .
. . . .     . x x x     x x . x
x . x x     . . x .     x . . x

Puzzle seed: 000001   hash: 04fc711301f3
Top:        Front:      Side:
. . . .     . x x x     . . . .
. x . .     . . . x     . . . x
x x x x     . . . x     x x x x
x x . .     . . x x     . . x x

Puzzle seed: 000157   hash: fe88e8f9b499
Top:        Front:      Side:
x x x x     x x x .     x . x x
x x x .     x . . .     . x . .
x . . .     x x x x     x . . x
x . . .     x . . x     x . . x

Os dois primeiros são insolúveis, enquanto o último tem uma solução com as seguintes camadas, da frente para trás:

x . . .   . . . .   x x x .   x x x .
. . . .   x . . .   . . . .   . . . .
x . . .   . . . .   . . . .   x x x x
x . . .   . . . .   . . . .   x . . x

There are a total of 16 blocks here, but it can probably be done in less.

A pontuação do seu programa será determinada pelos seguintes critérios, em ordem decrescente de prioridade:

  • O maior número de casos resolvidos.
  • O menor número de blocos necessários para resolver esses casos.
  • O código mais curto em bytes.

Você deve enviar e calcular a pontuação sozinho, o que exige que seu programa seja capaz de executar todos os 1.000.000 de casos de teste.

Joe Z.
fonte
Aprendi ao tentar gerar casos de teste para esse problema que mais casos são insolúveis do que não. Eu me pergunto como isso vai acabar.
Joe Z.
Se for um problema de otimização, deve haver um limite de tempo, para que as pessoas não o forcem.
Isaacg 28/03
O prazo é o tempo que eles levam para testá-lo. Uma solução que leva uma eternidade para ser executada nunca produzirá um resultado que possa ser publicado aqui. É assim que todos os problemas de otimização que escrevo funcionam.
Joe Z.
1
@JoeZ. orlp está certo. Eu tive um erro na minha conversão de MD5 para quebra-cabeça. 551 quebra-cabeças solucionáveis ​​em 00000-99999 e 5360 quebra-cabeças solucionáveis ​​em 000000-999999.
Jakube 28/03

Respostas:

5

Python: 5360 casos de teste resolvidos usando 69519 blocos, 594 bytes

Esses devem ser os valores ideais.

Abordagem:

Primeiro, testarei se o caso de teste é realmente solucionável. Eu faço isso inicializando uma lista de comprimento 64 por unidades e defino todas as posições como zero, se o pixel correspondente das três visualizações for zero. Depois, visualizo o quebra-cabeça de todas as três direções e ver se as visualizações são iguais às visualizações de entrada. Se for igual, o quebra-cabeça é solucionável (já encontramos a pior solução), caso contrário, é insolúvel.

Depois, faço uma abordagem de ramificação e limite para encontrar a solução ideal.

Ramificação: Eu tenho uma função recursiva. A profundidade da recursão informa quantos valores já foram corrigidos. Em cada chamada da função, eu me chamo duas vezes, se o valor no índice atual for 1 (esse valor pode ser 0 ou 1 na solução ideal) ou uma vez, se o valor for 0 (deve ser zero na solução ideal).

Limite: Eu uso duas estratégias diferentes aqui.

  1. Calculo as visualizações dos três lados em cada chamada de função e observo se elas ainda correspondem aos valores de entrada. Se eles não corresponderem, não chamo a função recursivamente.

  2. Eu mantenho a melhor solução na memória. Já existem mais fixos no ramo atual do que na melhor solução, já posso fechar esse ramo. Além disso, posso estimar um limite inferior para o número de blocos ativados, que não são fixos. E a condição se torna#number of activated fixed blocks + #lower bound of activated blocks (under the not fixed blocks) < #number of activated blocks in the best solution.

Aqui está o código Python. Ele define uma função fque espera 3 listas contendo 1s e 0s e retorna 0 (não solucionável) ou uma lista de 1s e 0s representando a solução ideal.

S=sum;r=range
def f(t,f,s):
 for i in r(4):s[4*i:4*i+4]=s[4*i:4*i+4][::-1]
 c=[min(t[i%16],f[(i//16)*4+i%4],s[i//4])for i in r(64)]
 m=lambda:([int(S(c[i::16])>0)for i in r(16)],[int(S(c[i+j:i+j+16:4])>0)for i in r(0,64,16)for j in r(4)],[int(S(c[i+j:i+j+4])>0)for i in r(0,64,16)for j in r(0,16,4)])==(t,f,s)
 Z=[65,0];p=[]
 def g(k):
  if k>63and S(c)<Z[0]:Z[:]=[S(c),c[:]]
  if k>63or S(c[:k])+p[k]>=Z[0]:return
  if c[k]:c[k]=0;m()and g(k+1);c[k]=1
  m()and g(k+1)
 for i in r(64):h,R=(i//16)*4+4,(i//4)%4;p+=[max(S(f[h:]),S(s[h:]))+max((R<1)*S(f[h+i%4-3:h]),S(s[h+R-3:h]))]
 g(0);return Z[1]

O comprimento do código é 596 bytes / caracteres. E aqui está a estrutura de teste:

from hashlib import md5
from time import time

N = 1000000
start=time();count=blocks=0
for n in range(N):
 bits = list(map(int,"{:048b}".format(int(md5("{:06}".format(n).encode("utf-8")).hexdigest()[:12], 16))))
 result = f(bits[:16], bits[16:32], bits[32:])
 if result:
  count += 1
  blocks += sum(result)
  print("Seed: {:06}, blocks: {}, cube: {}".format(n, sum(result), result))
print()
print("{} out of {} puzzles are solvable using {} blocks.".format(count, N, blocks))
print("Total time: {:.2f} seconds".format(time()-start))

Você pode encontrar uma versão não destruída do programa aqui . Também é um pouco mais rápido.

Resultados:

5360 dos 1000000 quebra-cabeças são solucionáveis. No total, precisamos de 69519 blocos. O número de blocos varia de 6 a 18 blocos. O quebra-cabeça mais difícil levou cerca de 1 segundo para resolver. É o quebra-cabeça com a semente "347177", que parece

Top:      Front:    Side:
x x . .   x x x x   x . x .
x x x x   x x x x   x x x x
x x x x   x x x x   x x x x
x x . x   x x x x   x . x x

e tem uma solução ideal com 18 cubos. A seguir, são apresentados alguns de cima para cada uma das camadas:

Top 1:    Top 2:    Top 3:    Top 4:
. . . .   . x . .   . x . .   x . . .
. . x x   . . x .   x . . .   . x x .
. . . .   . . . x   x x x .   . . . .
x x . .   x . . .   . . . x   . . . x

O tempo total de execução para todos os casos de teste foi de aproximadamente 90 segundos. Eu usei o PyPy para executar o meu programa. CPython (o intérprete padrão do Python) é um pouco mais lento, mas também resolve todos os quebra-cabeças em apenas 7 minutos.

Você pode encontrar a saída completa aqui : A saída é auto-explicativa. Por exemplo, a saída do quebra-cabeça acima é:

Seed: 347177, blocks: 18, cube: [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1]
Jakube
fonte
3

5360 caixas resolvidas com 69519 blocos; 923 bytes

Isso também é ótimo. Ligue com uma matriz de uns e zeros. Lança a NullPointerExceptionpara entrada inválida. Alguma eficiência é sacrificada para o golfe. Ele ainda é concluído dentro de um tempo razoável para todas as 1000000 entradas de teste.

import java.util.*;int[]a(int[]a){a b=new a(a);b=b.b(64);return b.d();}class a{List<int[]>a=new ArrayList();List b=new ArrayList();int c;a(int[]d){int e=0,f,g,h,i[]=new int[48];for(;e<64;e++){f=e/16;g=(e%16)/4;h=e%4;if(d[f+12-4*h]+d[16+f+g*4]+d[32+h+g*4]>2){i[f+12-4*h]=i[16+f+g*4]=i[32+h+g*4]=1;a.add(new int[]{f,g,h});c++;}}if(!Arrays.equals(d,i))throw null;b=f();}a(){}a b(int d){if(c-b.size()>d|b.size()<1)return this;a e=c();e.a.remove(b.get(0));e.b.retainAll(e.f());e.c--;e=e.b(d);d=Math.min(e.c,d);a f=c();f=f.b(d);return e.c>f.c?f:e;}a c(){a c=new a();c.a=new ArrayList(a);c.b=new ArrayList(b);c.b.remove(0);c.c=this.c;return c;}int[]d(){int[]d=new int[64];for(int[]e:a)d[e[2]*16+e[1]*4+e[0]]=1;return d;}List f(){List d=new ArrayList();int e,f,g;for(int[]h:a){e=0;f=0;g=0;for(int[]p:a)if(p!=h){e|=h[0]==p[0]&h[1]==p[1]?1:0;f|=h[0]==p[0]&h[2]==p[2]?1:0;g|=h[1]==p[1]&h[2]==p[2]?1:0;}if(e+f+g>2)d.add(h);}return d;}}

Estratégia:

Na verdade, eu costumava jogar esse quebra-cabeça quando tinha 10 anos. Isso usa minha abordagem.

Passo 1:

Forme o cubo com mais blocos que se ajustem às visualizações fornecidas.

Passo 2:

Crie uma lista de peças removíveis. (Qualquer peça que tenha outra peça na linha está dentro, a coluna está dentro e a viga está dentro.)

Etapa 3:

Teste todas as formas possíveis para manter ou remover cada peça removível. (Via força bruta recursiva com poda.)

Passo 4:

Mantenha o melhor cubo válido.

Ungolfed:

int[] main(int[] bits) {
    Cube cube = new Cube(bits);
    cube = cube.optimize(64);
    return cube.bits();
}

class Cube {

    List<int[]> points = new ArrayList();
    List removablePoints = new ArrayList();
    int size;

    Cube(int[] bits) {
        int i = 0,x,y,z,placed[] = new int[48];
        for (; i < 64; i++) {
            x = i / 16;
            y = (i % 16) / 4;
            z = i % 4;
            if (bits[x + 12 - 4 * z] + bits[16 + x + y * 4] + bits[32 + z + y * 4] > 2) {
                placed[x + 12 - 4 * z] = placed[16 + x + y * 4] = placed[32 + z + y * 4] = 1;
                points.add(new int[]{x, y, z});
                size++;
            }
        }

        if (!Arrays.equals(bits, placed))
            throw null;

        removablePoints = computeRemovablePoints();
    }

    Cube() {
    }

    Cube optimize(int smallestFound) {
        if (size - removablePoints.size() > smallestFound | removablePoints.size() < 1)
            return this;

        Cube cube1 = duplicate();
        cube1.points.remove(removablePoints.get(0));

        cube1.removablePoints.retainAll(cube1.computeRemovablePoints());
        cube1.size--;

        cube1 = cube1.optimize(smallestFound);
        smallestFound = Math.min(cube1.size, smallestFound);

        Cube cube2 = duplicate();

        cube2 = cube2.optimize(smallestFound);

        return cube1.size > cube2.size ? cube2 : cube1;

    }

    Cube duplicate() {
        Cube c = new Cube();
        c.points = new ArrayList(points);
        c.removablePoints = new ArrayList(removablePoints);
        c.removablePoints.remove(0);
        c.size = size;
        return c;
    }

    int[] bits() {
        int[] bits = new int[64];
        for (int[] point : points)
            bits[point[2] * 16 + point[1] * 4 + point[0]] = 1;
        return bits;
    }

    List computeRemovablePoints(){
        List removablePoints = new ArrayList();
        int removableFront, removableTop, removableSide;
        for (int[] point : points) {
            removableFront = 0;
            removableTop = 0;
            removableSide = 0;
            for (int[] p : points)
                if (p != point) {
                    removableFront |= point[0] == p[0] & point[1] == p[1] ? 1 : 0;
                    removableTop |= point[0] == p[0] & point[2] == p[2] ? 1 : 0;
                    removableSide |= point[1] == p[1] & point[2] == p[2] ? 1 : 0;
                }
            if (removableFront + removableTop + removableSide > 2)
                removablePoints.add(point);
        }
        return removablePoints;
    }

    public String toString() {

        String result = "";
        int bits[] = bits(),x,y,z;

        for (z = 0; z < 4; z++) {
            for (y = 0; y < 4; y++) {
                for (x = 0; x < 4; x++) {
                    result += bits[x + 4 * y + 16 * z] > 0 ? 'x' : '.';
                }
                result += System.lineSeparator();
            }
            result += System.lineSeparator();
        }

        return result;

    }
}

Programa completo:

import java.security.MessageDigest;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Example cube:
 *
 * origin
 * |   ........
 * |  .      ..
 * | . top  . .
 * v.      .  .
 * ........   .  <- side
 * .      .  .
 * . front. .
 * .      ..
 * ........
 *
 *     / z
 *    /
 *  /
 * .-----> x
 * |
 * |
 * |
 * V y
 */

public class PPCG48247 {

    public static void main(String[] args) throws Exception{
        MessageDigest digest = MessageDigest.getInstance("MD5");
        int totalSolved = 0;
        int totalCubes = 0;

        for (int i = 0; i < 1000000; i++){
            byte[] input = String.format("%06d", i).getBytes();

            byte[] hash = digest.digest(input);
            int[] bits = new int[48];

            for (int j = 0, k = 0; j < 6; j++, k += 8){
                byte b = hash[j];
                bits[k] = (b >> 7) & 1;
                bits[k + 1] = (b >> 6) & 1;
                bits[k + 2] = (b >> 5) & 1;
                bits[k + 3] = (b >> 4) & 1;
                bits[k + 4] = (b >> 3) & 1;
                bits[k + 5] = (b >> 2) & 1;
                bits[k + 6] = (b >> 1) & 1;
                bits[k + 7] = b & 1;
            }

            try {
                int[] solution = new PPCG48247().a(bits);
                totalSolved++;
                for (int b : solution){
                    totalCubes += b;
                }
            } catch (NullPointerException ignored){}

        }
        System.out.println(totalSolved);
        System.out.println(totalCubes);
    }

    int[] main(int[] bits) {
        Cube cube = new Cube(bits);
        cube = cube.optimize(64);
        return cube.bits();
    }

    class Cube {

        List<int[]> points = new ArrayList();
        List removablePoints = new ArrayList();
        int size;

        Cube(int[] bits) {
            int i = 0,x,y,z,placed[] = new int[48];
            for (; i < 64; i++) {
                x = i / 16;
                y = (i % 16) / 4;
                z = i % 4;
                if (bits[x + 12 - 4 * z] + bits[16 + x + y * 4] + bits[32 + z + y * 4] > 2) {
                    placed[x + 12 - 4 * z] = placed[16 + x + y * 4] = placed[32 + z + y * 4] = 1;
                    points.add(new int[]{x, y, z});
                    size++;
                }
            }

            if (!Arrays.equals(bits, placed))
                throw null;

            removablePoints = computeRemovablePoints();
        }

        Cube() {
        }

        Cube optimize(int smallestFound) {
            if (size - removablePoints.size() > smallestFound | removablePoints.size() < 1)
                return this;

            Cube cube1 = duplicate();
            cube1.points.remove(removablePoints.get(0));

            cube1.removablePoints.retainAll(cube1.computeRemovablePoints());
            cube1.size--;

            cube1 = cube1.optimize(smallestFound);
            smallestFound = Math.min(cube1.size, smallestFound);

            Cube cube2 = duplicate();

            cube2 = cube2.optimize(smallestFound);

            return cube1.size > cube2.size ? cube2 : cube1;

        }

        Cube duplicate() {
            Cube c = new Cube();
            c.points = new ArrayList(points);
            c.removablePoints = new ArrayList(removablePoints);
            c.removablePoints.remove(0);
            c.size = size;
            return c;
        }

        int[] bits() {
            int[] bits = new int[64];
            for (int[] point : points)
                bits[point[2] * 16 + point[1] * 4 + point[0]] = 1;
            return bits;
        }

        List computeRemovablePoints(){
            List removablePoints = new ArrayList();
            int removableFront, removableTop, removableSide;
            for (int[] point : points) {
                removableFront = 0;
                removableTop = 0;
                removableSide = 0;
                for (int[] p : points)
                    if (p != point) {
                        removableFront |= point[0] == p[0] & point[1] == p[1] ? 1 : 0;
                        removableTop |= point[0] == p[0] & point[2] == p[2] ? 1 : 0;
                        removableSide |= point[1] == p[1] & point[2] == p[2] ? 1 : 0;
                    }
                if (removableFront + removableTop + removableSide > 2)
                    removablePoints.add(point);
            }
            return removablePoints;
        }

        public String toString() {

            String result = "";
            int bits[] = bits(),x,y,z;

            for (z = 0; z < 4; z++) {
                for (y = 0; y < 4; y++) {
                    for (x = 0; x < 4; x++) {
                        result += bits[x + 4 * y + 16 * z] > 0 ? 'x' : '.';
                    }
                    result += System.lineSeparator();
                }
                result += System.lineSeparator();
            }

            return result;

        }
    }

}
O número um
fonte