Układanka z przodu z przodu to układanka, w której musisz zbudować trójwymiarowy (zwykle sześcienny) blok z trzema prostopadłymi widokami: widokiem z góry, widokiem z przodu i widokiem z boku.

Na przykład, biorąc pod uwagę widok z góry, z przodu i z boku w następujący sposób:

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.

Kostka 2x2x2 (z tomem 8) spełniałaby to rozwiązanie, ale jest wykonalna w tomie 4, jeśli mamy następującą strukturę warstw:

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

Istnieją również pewne nierozwiązywalne ustalenia. Weź na przykład:

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

Jeśli widok z góry mówi, że blok jest drugi od lewej, nie ma sposobu, aby dopasować się do widoku z przodu, który mówi, że blok musi być trzeci od lewej. Więc to ustawienie jest niemożliwe.

Twoim zadaniem jest zbudowanie programu, który, biorąc pod uwagę dowolną układankę 4x4 od góry, próbuje rozwiązać go w jak najmniejszej liczbie kostek lub ogłasza, że ​​jest nierozwiązywalny.

Twój program pobierze jako ciąg 48 bitów reprezentujących widoki z góry, z przodu i z boku. Mogą być w dowolnym formacie (ciąg 6-bajtowy, ciąg zer i jedynek, 12-cyfrowy numer szesnastkowy itp.), Ale kolejność bitów musi być odwzorowana jako taka:

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

Innymi słowy, bity są ułożone od lewej do prawej, od góry do dołu, w widoku od góry, od przodu, a następnie z boku.

Twój program wyświetli wtedy albo serię 64 bitów, wskazując wypełnione kostki w siatce 4x4x4, albo wskaże, że siatka jest nierozwiązywalna.

Twój program zostanie oceniony przez uruchomienie baterii 1 000 000 przypadków testowych.

Dane testowe zostaną wygenerowane przez wzięcie skrótów MD5 liczb całkowitych od „000000” do „999999” jako ciągów, wyodrębnienie pierwszych 48 bitów (12 heksów) każdego z tych skrótów i wykorzystanie ich jako danych wejściowych dla górnego-przedniego- układanka boczna. Oto przykładowe dane wejściowe testowe i generowane przez nich zagadki:

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

Pierwsze dwa są nierozwiązywalne, podczas gdy ostatni ma rozwiązanie z następującymi warstwami, od przodu do tyłu:

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.

Wynik Twojego programu zostanie określony na podstawie następujących kryteriów, w malejącej kolejności priorytetów:

• Największa liczba rozwiązanych przypadków.
• Najmniejsza liczba bloków wymagana do rozwiązania tych przypadków.
• Najkrótszy kod w bajtach.

Musisz przesłać i obliczyć wynik samodzielnie, co wymaga, aby Twój program mógł przejść przez wszystkie 1 000 000 przypadków testowych.

Python: 5360 przypadków testowych rozwiązanych przy użyciu bloków 69519, 594 bajtów

To powinny być wartości optymalne.

Podejście:

Najpierw przetestuję, czy przypadek testowy można rozwiązać. Robię to, inicjując listę długości 64 według nich i ustawiając wszystkie pozycje na zero, jeśli tam piksel trzech widoków wynosi zero. Następnie patrzę prosto na puzzle ze wszystkich 3 kierunków i sprawdzam, czy widoki są takie same jak widoki wejściowe. Jeśli są równe, łamigłówka jest do rozwiązania (znaleźliśmy już najgorsze rozwiązanie), w przeciwnym razie jest nierozwiązywalna.

Następnie stosuję podejście odgałęzione w celu znalezienia optymalnego rozwiązania.

Rozgałęzienie: Mam funkcję rekurencyjną. Głębokość rekurencji informuje, ile wartości jest już ustalonych. W każdym wywołaniu funkcji wywołuję się dwa razy, jeśli wartość przy bieżącym indeksie wynosi 1 (wartość ta może wynosić 0 lub 1 w optymalnym rozwiązaniu), lub jeden raz, jeśli wartość wynosi 0 (musi być zero w optymalne rozwiązanie).

Ograniczanie: używam tutaj dwóch różnych strategii.

1. Obliczam widoki z 3 stron w każdym wywołaniu funkcji i sprawdzam, czy nadal odpowiadają one wartościom wejściowym. Jeśli się nie zgadzają, nie wywołuję funkcji rekurencyjnie.

2. Najlepsze rozwiązanie przechowuję w pamięci. Tam jest już więcej stałych w bieżącej gałęzi niż w najlepszym rozwiązaniu, mogę już zamknąć tę gałąź. Dodatkowo mogę oszacować dolną granicę liczby aktywowanych bloków, które nie są stałe. I stan się staje#number of activated fixed blocks + #lower bound of activated blocks (under the not fixed blocks) < #number of activated blocks in the best solution.

Oto kod Python. Definiuje funkcję, fktóra oczekuje 3 list zawierających 1s i 0s i zwraca 0 (nierozwiązywalne) lub listę 1 i 0 reprezentujących optymalne rozwiązanie.

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]

Długość kodu wynosi 596 bajtów / znaków. A oto ramy testowe:

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

Możesz znaleźć wersję programu bez golfa tutaj . Jest także trochę szybszy.

Wyniki:

5360 ze 1000000 łamigłówek jest do rozwiązania. W sumie potrzebujemy 69519 bloków. Liczba bloków waha się od 6 do 18 bloków. Rozwiązanie najtrudniejszej układanki zajęło około 1 sekundy. To układanka z ziarnem "347177", które wygląda

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

i ma optymalne rozwiązanie z 18 kostkami. Oto kilka z góry dla każdej z warstw:

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

Całkowity czas działania wszystkich przypadków testowych wyniósł około 90 sekund. Użyłem PyPy do uruchomienia mojego programu. CPython (domyślny interpreter języka Python) jest nieco wolniejszy, ale rozwiązuje wszystkie zagadki w zaledwie 7 minut.

Możesz znaleźć pełny wynik tutaj : wynik jest oczywisty. Np. Wynik dla powyższej układanki to:

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 spraw rozwiązanych za pomocą 69519 bloków; 923 bajty

Jest to również optymalne. Zadzwoń z tablicą zer i jedynek. Zgłasza a NullPointerExceptiondla niepoprawnego wejścia. Pewna wydajność poświęcana jest na golfa. Nadal kończy się w rozsądnym czasie dla wszystkich 1000000 wejść testowych.

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

Strategia:

Kiedy miałem 10 lat, grałem w tę zagadkę dość często. To moje podejście.

Krok 1:

Utwórz sześcian z największą liczbą bloków pasujących do podanych widoków.

Krok 2:

Utwórz listę elementów wymiennych. (Każdy element z tym ma inny element w rzędzie jest w środku, kolumna jest w środku, a belka jest w środku.)

Krok 3:

Przetestuj każdy możliwy sposób, aby zachować lub usunąć każdy wyjmowany element. (Poprzez rekurencyjną brutalną siłę z przycinaniem.)

Krok 4:

Zachowaj najlepszą prawidłową kostkę.

Nie golfowany:

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;

    }
}

Pełny program:

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;

        }
    }

}