Ein Top-Front-Side-Puzzle ist ein Puzzle, bei dem Sie eine 3D-Form von (normalerweise kubischen) Blöcken mit drei orthogonalen Ansichten konstruieren müssen: einer Draufsicht, einer Vorderansicht und einer Seitenansicht.

Beispiel für eine Draufsicht, eine Vorderansicht und eine Seitenansicht:

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.

Ein 2x2x2 Würfel (mit Volumen 8) würde diese Lösung erfüllen, aber es ist in Volumen 4 machbar, wenn wir die folgende Schichtstruktur haben:

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

Es gibt auch einige unlösbare Vereinbarungen. Nehmen Sie zum Beispiel:

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

Wenn in der Draufsicht angegeben ist, dass der Block an zweiter Stelle von links liegt, kann die Vorderansicht nicht mit der Angabe übereinstimmen, dass der Block an dritter Stelle von links liegen muss. Diese Anordnung ist also unmöglich.

Ihre Aufgabe ist es, ein Programm zu erstellen, das bei einem beliebigen 4x4-Puzzle von oben nach vorne versucht, es in der geringsten Anzahl von Würfeln zu lösen, oder es für unlösbar erklärt.

Ihr Programm nimmt eine Reihe von 48 Bits als Eingabe, die die Draufsicht, die Vorderansicht und die Seitenansicht darstellen. Sie können in einem beliebigen Format vorliegen (eine 6-Byte-Zeichenfolge, eine Zeichenfolge aus 0en und 1en, eine 12-stellige Hex-Zahl usw.), die Reihenfolge der Bits muss jedoch wie folgt lauten:

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

Mit anderen Worten, die Bits werden von links nach rechts, von oben nach unten, von oben nach vorne und dann von der Seite betrachtet.

Ihr Programm gibt dann entweder eine Reihe von 64 Bit aus, die die ausgefüllten Würfel im 4x4x4-Raster anzeigen, oder Sie geben an, dass das Raster nicht lösbar ist.

Ihr Programm wird mit einer Batterie von 1.000.000 Testfällen bewertet.

Die Testdaten werden generiert, indem die MD5-Hashes der Ganzzahlen "000000" bis "999999" als Zeichenfolgen verwendet werden, die ersten 48 Bits (12 Hexits) jeder dieser Hashes extrahiert werden und als Eingabe für die Top-Front-Front-Funktion verwendet werden. Seitenrätsel. Als Beispiel hier sind einige der Testeingaben und die Rätsel, die sie erzeugen:

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

Die ersten beiden sind unlösbar, während die letzte Lösung von vorne nach hinten die folgenden Ebenen enthält:

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.

Die Punktzahl Ihres Programms wird anhand der folgenden Kriterien in absteigender Reihenfolge der Priorität bestimmt:

• Die höchste Anzahl gelöster Fälle.
• Die niedrigste Anzahl von Blöcken, die zur Lösung dieser Fälle erforderlich sind.
• Der kürzeste Code in Bytes.

Sie müssen die Punktzahl selbst einreichen und berechnen. Dies setzt voraus, dass Ihr Programm alle 1.000.000 Testfälle durchlaufen kann.

Python: 5360 Testfälle mit 69519 Blöcken, 594 Bytes gelöst

Dies sollten die optimalen Werte sein.

Ansatz:

Zuerst werde ich testen, ob der Testfall tatsächlich lösbar ist. Dazu initialisiere ich eine Liste der Länge 64 nach Einsen und setze alle Positionen auf Null, wenn dort das entsprechende Pixel der drei Ansichten Null ist. Dann betrachte ich das Puzzle einfach aus allen drei Richtungen und überprüfe, ob die Ansichten mit den Eingabeansichten übereinstimmen. Wenn es gleich ist, ist das Rätsel lösbar (wir haben bereits die schlechteste Lösung gefunden), andernfalls ist es nicht lösbar.

Dann mache ich einen branch-and-bound Ansatz, um die optimale Lösung zu finden.

Verzweigung: Ich habe eine rekursive Funktion. Die Rekursionstiefe gibt an, wie viele Werte bereits festgelegt sind. Bei jedem Aufruf der Funktion rufe ich sich zweimal auf, wenn der Wert am aktuellen Index 1 ist (dieser Wert kann in der optimalen Lösung 0 oder 1 sein), oder einmal, wenn der Wert 0 ist (er muss in der Funktion Null sein) optimale Lösung).

Bounding: Ich benutze hier zwei verschiedene Strategien.

1. Ich berechne die Ansichten von den 3 Seiten in jedem Funktionsaufruf und schaue, ob sie noch mit den Eingabewerten übereinstimmen. Wenn sie nicht übereinstimmen, rufe ich die Funktion nicht rekursiv auf.

2. Ich behalte die beste Lösung im Gedächtnis. Wenn es in der aktuellen Filiale bereits mehr feste gibt als in der besten Lösung, kann ich diese Filiale bereits schließen. Zusätzlich kann ich eine Untergrenze für die Anzahl der aktivierten Blöcke schätzen, die nicht festgelegt sind. Und der Zustand wird#number of activated fixed blocks + #lower bound of activated blocks (under the not fixed blocks) < #number of activated blocks in the best solution.

Hier ist der Python-Code. Es definiert eine Funktion, fdie 3 Listen mit 1 und 0 erwartet und entweder 0 (nicht lösbar) oder eine Liste mit 1 und 0 zurückgibt, die die optimale Lösung darstellt.

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]

Die Codelänge beträgt 596 Bytes / Zeichen. Und hier ist das Test-Framework:

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))

Sie können eine ungolfed Version des Programms finden hier . Es ist auch ein bisschen schneller.

Ergebnisse:

5360 von 1000000 Puzzles sind lösbar. Insgesamt benötigen wir 69519 Blöcke. Die Anzahl der Blöcke variiert zwischen 6 und 18 Blöcken. Die Lösung des schwierigsten Rätsels dauerte ungefähr 1 Sekunde. Es ist das Puzzle mit dem Samen "347177", wie es aussieht

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

und hat mit 18 würfel eine optimale lösung. Das Folgende ist ein paar von oben für jede der Schichten:

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

Die Gesamtlaufzeit für alle Testfälle betrug ca. 90 Sekunden. Ich habe PyPy benutzt, um mein Programm auszuführen. CPython (der Standard-Python-Interpreter) ist etwas langsamer, löst aber auch alle Rätsel in nur 7 Minuten.

Die vollständige Ausgabe finden Sie hier : Die Ausgabe ist selbsterklärend. ZB ist die Ausgabe für das obige Puzzle:

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]

5360 Fälle mit 69519 Blöcken gelöst; 923 Bytes

Das ist auch optimal. Rufen Sie mit einer Reihe von Einsen und Nullen auf. Löst ein NullPointerExceptionfür ungültige Eingaben aus. Ein gewisser Wirkungsgrad wird geopfert, um Golf zu spielen. Es ist immer noch innerhalb einer angemessenen Zeit für alle 1000000 Testeingaben abgeschlossen.

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

Strategie:

Eigentlich habe ich dieses Puzzle ziemlich oft gespielt, als ich 10 Jahre alt war. Dies verwendet meinen Ansatz.

Schritt 1:

Bilden Sie den Würfel mit den meisten Blöcken, die den angegebenen Ansichten entsprechen.

Schritt 2:

Erstellen Sie eine Liste mit entfernbaren Teilen. (Jedes Stück mit diesem hat ein anderes Stück in der Reihe, in der Spalte und im Balken.)

Schritt 3:

Testen Sie alle Möglichkeiten, um jedes herausnehmbare Teil aufzubewahren oder zu entfernen. (Über rekursive Brute-Force mit Beschneiden.)

Schritt 4:

Behalte den besten gültigen Würfel.

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;

    }
}

Volles Programm:

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;

        }
    }

}