Czy potrafisz pokonać brytyjski wywiad? (Nonogram Solver)

20

Czas podjąć niebezpieczną misję pokonania brytyjskiego wywiadu. Celem tego wyzwania jest napisanie najkrótszego kodu, który rozwiąże Nonogram.

Co to jest nonogram?

Puzzle Nonogram

Zasady są proste. Masz siatkę kwadratów, które muszą być wypełnione na czarno lub pozostawione puste. Obok każdego rzędu siatki są wymienione długości serii czarnych kwadratów w tym rzędzie. Nad każdą kolumną są wymienione długości serii czarnych kwadratów w tej kolumnie. Twoim celem jest znalezienie wszystkich czarnych kwadratów. W tym typie puzzli liczby są formą dyskretnej tomografii, która mierzy, ile nieprzerwanych linii wypełnionych kwadratów znajduje się w danym wierszu lub kolumnie. Na przykład wskazówka „4 8 3” oznacza, że ​​istnieją zestawy czterech, ośmiu i trzech wypełnionych kwadratów, w tej kolejności, z co najmniej jednym pustym kwadratem między kolejnymi grupami. [ 1 ] [ 2 ]

Rozwiązaniem powyższego Nonogramu byłoby:

Rozwiązany nonogram

Szczegóły dotyczące wdrożenia

Możesz wybrać reprezentowanie Nonograma w dowolny sposób i brać go jako dane wejściowe w dowolny sposób, który uznasz za odpowiedni dla twojego języka. To samo dotyczy wyników. Celem tego wyzwania jest dosłownie wykonanie pracy; jeśli możesz rozwiązać nonogram za pomocą danych wyjściowych programu, jest to poprawne. Jednym zastrzeżeniem jest to, że nie możesz użyć solvera online :)

Ten problem jest bardzo trudny algorytmicznie (np. Kompletny), ponieważ nie ma całkowicie skutecznego rozwiązania i jako taki, nie zostaniesz ukarany za to, że nie jesteś w stanie rozwiązać większych, chociaż twoja odpowiedź będzie silnie wynagrodzona, jeśli jest w stanie obsługiwać duże skrzynki (patrz bonus). Jako punkt odniesienia moje rozwiązanie działa w przybliżeniu na 25 x 25 w ciągu 5-10 sekund. Aby zapewnić elastyczność między różnymi językami, wystarczające są rozwiązania, które zajmują mniej niż 5 minut dla nonogramu 25x25.

Możesz założyć układankę w zawsze kwadratowym nonogramie NxN.

Możesz użyć tego internetowego łamigłówki nonogramowej do przetestowania swoich rozwiązań.

Punktacja

Oczywiście możesz swobodnie używać dowolnego języka, a ponieważ jest to kod do golfa, wpisy zostaną posortowane w kolejności: accuracy -> length of code -> speed.jednak nie zniechęcaj się kodami języków golfowych, odpowiedzi we wszystkich językach, które pokazują próby gry w golfa w ciekawy sposób zostaną ocenione!

Premia

I rzeczywiście dowiedział się o Nonograms z kryptograficznego kartki świąteczne wydany przez brytyjskiego wywiadu tutaj . Pierwsza część była w zasadzie ogromnym Nonogramem 25x25. Jeśli twoje rozwiązanie jest w stanie rozwiązać ten problem, otrzymasz odznaczenia :)

Aby ułatwić Ci życie w zakresie wprowadzania danych, przedstawiłem sposób, w jaki przedstawiłem dane dla tej konkretnej układanki do bezpłatnego użytku. Pierwsze 25 wierszy to wskazówki wierszy, następnie linia separatora „-”, następnie 25 linii wskazówek col, następnie linia separatora „#”, a następnie reprezentacja siatki z wypełnionymi kwadratowymi wskazówkami.

7 3 1 1 7
1 1 2 2 1 1
1 3 1 3 1 1 3 1
1 3 1 1 6 1 3 1
1 3 1 5 2 1 3 1
1 1 2 1 1
7 1 1 1 1 1 7
3 3
1 2 3 1 1 3 1 1 2
1 1 3 2 1 1
4 1 4 2 1 2
1 1 1 1 1 4 1 3
2 1 1 1 2 5
3 2 2 6 3 1
1 9 1 1 2 1
2 1 2 2 3 1
3 1 1 1 1 5 1
1 2 2 5
7 1 2 1 1 1 3
1 1 2 1 2 2 1
1 3 1 4 5 1
1 3 1 3 10 2
1 3 1 1 6 6
1 1 2 1 1 2
7 2 1 2 5
-
7 2 1 1 7
1 1 2 2 1 1
1 3 1 3 1 3 1 3 1
1 3 1 1 5 1 3 1
1 3 1 1 4 1 3 1
1 1 1 2 1 1
7 1 1 1 1 1 7
1 1 3
2 1 2 1 8 2 1
2 2 1 2 1 1 1 2
1 7 3 2 1
1 2 3 1 1 1 1 1
4 1 1 2 6
3 3 1 1 1 3 1
1 2 5 2 2
2 2 1 1 1 1 1 2 1
1 3 3 2 1 8 1
6 2 1
7 1 4 1 1 3
1 1 1 1 4
1 3 1 3 7 1
1 3 1 1 1 2 1 1 4
1 3 1 4 3 3
1 1 2 2 2 6 1
7 1 3 2 1 1
#
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

A oto nieco inna wersja dla twojej wygody; krotka oddzielona przecinkami (wiersz, kolumna), gdzie każdy element jest listą list.

([[7, 3, 1, 1, 7],
  [1, 1, 2, 2, 1, 1],
  [1, 3, 1, 3, 1, 1, 3, 1],
  [1, 3, 1, 1, 6, 1, 3, 1],
  [1, 3, 1, 5, 2, 1, 3, 1],
  [1, 1, 2, 1, 1],
  [7, 1, 1, 1, 1, 1, 7],
  [3, 3],
  [1, 2, 3, 1, 1, 3, 1, 1, 2],
  [1, 1, 3, 2, 1, 1],
  [4, 1, 4, 2, 1, 2],
  [1, 1, 1, 1, 1, 4, 1, 3],
  [2, 1, 1, 1, 2, 5],
  [3, 2, 2, 6, 3, 1],
  [1, 9, 1, 1, 2, 1],
  [2, 1, 2, 2, 3, 1],
  [3, 1, 1, 1, 1, 5, 1],
  [1, 2, 2, 5],
  [7, 1, 2, 1, 1, 1, 3],
  [1, 1, 2, 1, 2, 2, 1],
  [1, 3, 1, 4, 5, 1],
  [1, 3, 1, 3, 10, 2],
  [1, 3, 1, 1, 6, 6],
  [1, 1, 2, 1, 1, 2],
  [7, 2, 1, 2, 5]],
 [[7, 2, 1, 1, 7],
  [1, 1, 2, 2, 1, 1],
  [1, 3, 1, 3, 1, 3, 1, 3, 1],
  [1, 3, 1, 1, 5, 1, 3, 1],
  [1, 3, 1, 1, 4, 1, 3, 1],
  [1, 1, 1, 2, 1, 1],
  [7, 1, 1, 1, 1, 1, 7],
  [1, 1, 3],
  [2, 1, 2, 1, 8, 2, 1],
  [2, 2, 1, 2, 1, 1, 1, 2],
  [1, 7, 3, 2, 1],
  [1, 2, 3, 1, 1, 1, 1, 1],
  [4, 1, 1, 2, 6],
  [3, 3, 1, 1, 1, 3, 1],
  [1, 2, 5, 2, 2],
  [2, 2, 1, 1, 1, 1, 1, 2, 1],
  [1, 3, 3, 2, 1, 8, 1],
  [6, 2, 1],
  [7, 1, 4, 1, 1, 3],
  [1, 1, 1, 1, 4],
  [1, 3, 1, 3, 7, 1],
  [1, 3, 1, 1, 1, 2, 1, 1, 4],
  [1, 3, 1, 4, 3, 3],
  [1, 1, 2, 2, 2, 6, 1],
  [7, 1, 3, 2, 1, 1]])
code-golf  puzzle-solver 
— gowrath
źródło
Niestety moja strona internetowa nie działa, ale miała dość szybki solver Nonogram; 5-10 minut brzmi zbyt długo.
— Neil
1
— edc65
1
@dwana Nie musisz się martwić nierozwiązywalnymi sprawami. Jeśli chodzi o losową odpowiedź, na nonogramie 25x25 masz 2 ^ 625 możliwych konfiguracji. W kontekście jest to ponad dwukrotność liczby atomów w znanym wszechświecie (tj. Jeśli użyjesz każdego atomu we wszechświecie trochę, nadal nie będziesz miał wystarczająco dużo miejsca, aby przechowywać możliwości). Jeśli chodzi o czas, jeśli zajęło ci drugą nano (obfite), aby sprawdzić ważność każdej konfiguracji, zajęłoby 7 wcieleń wszechświata kodu do końca działa :)
— gowrath
1
Ty za wyjaśnienie nierozwiązywalnych spraw. (+ Mam magiczny komputer, który potwierdza odpowiedź w ~ 2.1546362E-186 sekund)
— dwana
1
Twój plik CSV nie ma kwadratowych wskazówek. Oto kilka JS do ich wygenerowania:s=[].fill([].fill(0,0,25),0,25);s[3][3]=s[3][4]=s3[3][12]=s3[3][13]=s3[3][21]=s[8][6]=s[8][7]=s[8][10]=s[8][14]=s[8][15]=s[8][18]=s[16][6]=s[16][11]=s[16][16]=s[16][20]=s[21][3]=s[21][4]=s[21][9]=s[21][10]=s[21][15]=s[21][20]=s[21][21]=1;
— Tytus

Odpowiedzi:

5

Brachylog , 70 69 bajtów

[R:C]hlL~l:L:1f=.:3aR,.z:3aC,
tL,?he##ElL,E:2a
.<2,_1<
@b:4f:la
e.h1,

Pobiera to listę dwóch list (najpierw wskaźniki wierszy, a następnie kolumny). Każdy wskaźnik sam w sobie jest listą (dla pozycji jak [3,1]w jednym rzędzie).

Ta wersja zajmuje około 3 minut, aby rozwiązać przykładowe wyzwanie 5 na 5.

Znacznie bardziej wydajna wersja, 91 bajtów

[R:C]hlL~l:L:1f:Cz:3az:Rz:3a=.:4aR,.z:4aC,
tL,?he##ElL,E:2a
.<2,_1<
:+a#=,?h
@b:5f:la
e.h1,

Wypróbuj online!

Ten nie jest całkowitą brutalną siłą: jedyną różnicą jest to, że nakłada ograniczenia na wartości komórek, tak że liczba 1s w każdym rzędzie i kolumnie odpowiada liczbom podanym jako wskaźniki na wejściu. Jedyną częścią siły brutalnej jest wówczas znalezienie jednej siatki z tymi ograniczeniami, dla których „bloki” 1s odpowiadają temu, co podano jako wskazanie.

To trwa około 0,05 sekundy na przykładzie wyzwania 5 na 5. Jest to wciąż zbyt wolne w przypadku premii, ponieważ nie mam pojęcia, jak wyrazić bloki zer oddzielone jednym lub więcej zerami w kategoriach ograniczeń.

Wyjaśnienie

Wyjaśnię poniżej wersję 93 bajtów. Jedyną różnicą między nimi jest wywołanie predykatu 3, które nie istnieje w wersji 70-bajtowej, i numeracja predykatów (ponieważ jest jeden mniej).

  • Główny predykat:

    [R:C]     Input = [R, C]
hlL       The length of R is L
~l        Create a list of length L
:L:1f     Each element of that list is a sublist of length L with cells 0 or 1 (Pred 1)
          %%% Part unique to the 93 bytes version
:Cz       Zip the rows of the list of lists with C
:3a       The sum of 1s in each row is equal to the sum of the indicators (Pred 3)
z         Transpose
:Rz       Zip the columns of the list of lists with R
:3a       The sum of 1s in each column is equal to the sum of the indicators (Pred 3)
          %%%
=.        Assign values to the cells of the list of lists which satisfy the constraints
:4aR,     The blocks of 1s must match the indicators on rows
.z        Transpose
:4aC,     The blocks of 1s must match the indicators on columns

  • Predykat 1: Wymusza, aby wiersze miały określoną długość, a każda komórka ma wartość 0 lub 1.

    tL,       L is the length given as second element of the input
?he       Take an element from the list
##ElL,    That element E is itself a list of length L
E:2a      The elements of E are 0s and 1s (Pred 2)

  • Predykat 2: Ogranicz zmienną do wartości 0 lub 1

    .<2,      Input = Output < 2
_1<       Output > -1

  • Predykat 3: Suma 1s na liście musi być równa sumie wskaźników (np. Jeśli wskaźnikiem jest [3: 1], wówczas lista musi mieć sumę 4)

    :+a       Sum the elements of the list and sum the indicator
#=,       Both sums must be equal
?h        Output is the list

  • Predykat 4: Sprawdź, czy bloki 1s pasują do wskaźnika

    @b        Split the list in blocks of the same value
:5f       Find all blocks of 1s (Pred 5)
:la       The list of lengths of the blocks results in the indicator (given as output)

  • Predykat 5: Prawda dla bloków 1s, w przeciwnym razie fałsz

    e.        Output is an element of the input
  h1,     Its first value is 1
— Fatalizować
źródło
Czuje się idealnym narzędziem do pracy. Czekamy na wyjaśnienia.
— Emigna
@Fatalize To fantastyczne, czekałem na kogoś, kto użyje do tego prologicznego języka. Czy próbowałeś już tego z obudową 25x25? Wprowadziłem już
— gowrath
@gowrath Uruchomię to na swoim komputerze tego popołudnia, zobaczymy, co się stanie.
— Fatalize
@Fatalize Wydaje się, że upłynął limit czasu, ale może robię to źle. Nie polegałbym też całkowicie na moich umiejętnościach wprowadzania danych: D
— gowrath,
@gowrath Upłynął limit czasu na TIO, ale uruchomię go w tłumaczu offline bezpośrednio na moim komputerze.
— Fatalize
9

Haskell, 242 230 201 199 177 163 160 149 131 bajtów

import Data.Lists
m=map
a#b=[x|x<-m(chunk$length b).mapM id$[0,1]<$(a>>b),g x==a,g(transpose x)==b]
g=m$list[0]id.m sum.wordsBy(<1)

Wreszcie poniżej 200 bajtów, kredyt @Bergi. Ogromne podziękowania dla @nimi za pomoc prawie o połowę mniejszą.

Łał. Prawie w połowie wielkości teraz, częściowo przeze mnie, ale głównie przez @nimi.

Magiczną funkcją jest (#). Znajduje wszystkie rozwiązania danego nonogramu.

Jest to w stanie rozwiązać wszystkie przypadki, ale może być bardzo wolne, ponieważ chodzi o jego złożoność O(2^(len a * len b)). Szybki test porównawczy ujawnił 86 GB przydzielonych dla nonogramu 5x5.

Ciekawostka: działa na wszystkie nonogramy, nie tylko kwadratowe.

Jak to działa:

  • a#b: Biorąc pod uwagę listy liczb całkowitych reprezentujących liczbę kwadratów, generuj wszystkie siatki ( map(chunk$length b).mapM id$a>>b>>[[0,1]]) i filtruj wyniki, aby zachować tylko te prawidłowe.
  • g: Biorąc pod uwagę potencjalny nonogram, sumuje biegi 1 w poziomie.
— ThreeFx
źródło
Masz na myśli O (2 ^ (len a * len b)), a nie O ((len a * len b) ^ 2).
— Anders Kaseorg,
@AndersKaseorg Right. Zatrzymaj milion, który przypadkowo tam zasugerowałem. : D
— ThreeFx
1
Kolejne kilka bajtów: m(chunk$l b)ireplicate(l$a>>b)
— Bergi,
@ThreeFx 86GB: O ... Czy mógłbyś krótko wyjaśnić, jak to skompilować? Dopiero zacząłem uczyć się haskell i to daje błędy w ghc. Chcę to przetestować :)
— gowrath
1
import Data.Listswystarczy, ponieważ ponownie eksportuje zarówno Data.Listi Data.List.Split.
— nimi
4

Pyth, 91 72 71 bajtów

D:GHdRq@@QdG.nCf.)TrH8V^,01^hQ2=TcNhQ=Y1VhQ=*Y*:H@TH1:H@CTH2)IYjbmjkdTb

Program, który pobiera listę postaci, w [size, [horizontal clues], [vertical clues]]której każda wskazówka jest listą liczb całkowitych (puste wskazówki są pustą listą []), i drukuje każde rozwiązanie, oddzielone znakiem nowej linii, w postaci siatki binarnej, w której 1jest zacieniowany i nie 0jest zacieniowany .

To brutalna siła, więc z grubsza O(2^n^2). Zaczyna się zajmować dużo czasu dla większych łamigłówek, ale rozwiąże każdy rozmiar arbitrary, mając wystarczającą ilość czasu.

Wypróbuj online

Jak to działa

Program generuje każdy możliwy układ, biorąc powtarzalny iloczyn kartezjański o [0, 1]długości równej size^2. Jest to następnie dzielone na części, dając listę dla każdej linii poziomej. Każda linia jest kodowana na całej długości, filtrowana przez obecność 1i spłaszczana, pozostawiając wskazówkę dla tej linii. Jest to następnie porównywane z danymi wejściowymi. Powyższy proces powtarza się dla transpozycji fragmentów, sprawdzając linie pionowe. W przypadku trafienia każdy fragment jest konkatenowany, a konkatenowane fragmenty są łączone na znakach nowej linii i domyślnie drukowane, z końcowym znakiem nowego wiersza.

D:GHdRq@@QdG.nCf.)TrH8V^,01^hQ2=TcNhQ=Y1VhQ=*Y*:H@TH1:H@CTH2)IYjbmjkdTb  Program. Input: Q
                            hQ                                           Q[0], size
                           ^  2                                          Square
                        ,01                                              [0, 1]
                       ^                                                 Cartesian product
                      V                                     )            For N in the Cartesian product:
                                 cNhQ                                    Split N into Q[0] chunks
                               =T                                        Assign that to T
                                     =Y1                                 Y=1
                                        VhQ                              For H in range [0, Q[0]-1]:
D:GHd                                                                     def :(G, H, d)
                   rH8                                                     Run-length-encode(H)
               f.)T                                                        Filter by presence of 1 in character part
            .nC                                                            Transpose and flatten, giving the clue
       @@QdG                                                               Q[d][G], the relevant input clue
     Rq                                                                    Return clue==input clue
                                               :H@TH1                     :(H, T, 1)
                                                     :H@CTH2              :(H, transpose(T), 2)
                                           =*Y*                           Y=Y*product of above two
                                                             IY           If Y:
                                                                 mjkdT     Conacatenate each element of T
                                                               jb          Join on newlines
                                                                      b    Add a newline and implicitly print

Dzięki @ Pietu1998 za kilka wskazówek

— TheBikingViking
źródło
To może być najdłuższy program Pyth, jaki kiedykolwiek widziałem
— Business Cat
=ZhZjest równy =hZi FNrówny V.
— PurkkaKoodari
@TheBikingViking Co dokładnie masz na myśli mając wystarczającą ilość czasu? Jestem całkiem pewien, że nie rozwiązałoby to do tej pory 25x25, gdybyś zaczął od koncepcji wszechświata.
— gowrath
1
@gowrath Jestem tego całkiem pewien! Jestem nowy w Pyth i po tym czasie mi to zajęło, nawet nie chcę rozważać próby wprowadzenia lepszego algorytmu
— TheBikingViking
2

JavaScript (ES6), 401 386 333 bajtów

To wczesna próba. Nie jest to zbyt wydajne, ale byłem ciekawy przetestowania rozwiązania przy użyciu wyrażeń regularnych na binarnej reprezentacji wierszy i kolumn.

Na przykład przetłumaczy wskazówkę [3,1]na następujące wyrażenie regularne:

/^0*1{3}0+1{1}0*$/

W tej chwili ta wersja nie uwzględnia kwadratowych wskazówek. Prawdopodobnie dodam to później.

Kod

(c,r)=>{W=c.length;w=[];S=0;M=(n,p)=>eval(`/^0*${p.map(v=>`1{${v}}`).join`0+`}0*$/`).exec(n);R=(y,i=0)=>S||(w[y]=r[y][i],y+1<W?R(y+1):c.every((c,y)=>(n=0,w.map((_,x)=>n+=w[W-1-x][y]),M(n,c)))&&(S=w.join`
`),r[y][i+1]&&R(y,i+1));r=r.map(r=>[...Array(1<<W)].map((_,n)=>((1<<30)|n).toString(2).slice(-W)).filter(n=>M(n,r)));return R(0)}

Wynik

Rozwiązanie jest wyświetlane w formacie binarnym. Jak na przykład:

00110
01110
11100
11101
00001

Test

Jest to prosty test na przykładowej siatce.

let f =
(c,r)=>{W=c.length;w=[];S=0;M=(n,p)=>eval(`/^0*${p.map(v=>`1{${v}}`).join`0+`}0*$/`).exec(n);R=(y,i=0)=>S||(w[y]=r[y][i],y+1<W?R(y+1):c.every((c,y)=>(n=0,w.map((_,x)=>n+=w[W-1-x][y]),M(n,c)))&&(S=w.join`
`),r[y][i+1]&&R(y,i+1));r=r.map(r=>[...Array(1<<W)].map((_,n)=>((1<<30)|n).toString(2).slice(-W)).filter(n=>M(n,r)));return R(0)}

console.log(f(
  [[2],[3],[4],[2],[2]],
  [[2],[3],[3],[3,1],[1]]
));
Rozwiń fragment kodu

— Arnauld
źródło
dobry pomysł. jednak zabija moje przeglądarki przy świątecznej układance.
— Tytus
2

Haskell, 109 bajtów

Oświadczenie: pochodzi z odpowiedzi @ ThreeFx . Pomogłem mu odrzucić odpowiedź, ale wydaje się, że stracił zainteresowanie dołączeniem moich ostatnich znacznych ulepszeń, więc opublikowałem je jako nową odpowiedź.

import Data.List
n=mapM id
a#b=[x|x<-n$(n$" #"<$a)<$b,g x==a,g(transpose x)==b]
g=map$max[0].map length.words

Przykład użycia: [[2],[3],[3],[3,1],[1]] # [[2],[3],[4],[2],[2]]-> [[" ## "," ### ","### ","### #"," #"]].

Brutalna siła. Wypróbuj wszystkie kombinacje i #, podziel int części #, policz długości i porównaj z danymi wejściowymi.

— nimi
źródło
1

PHP, 751 833 (720) 753 724 726 710 691 680 682 bajtów

Bardzo chciałem zbudować specjalną sekwencję i spróbować jeszcze raz mojego kartezjańskiego generatora;
ale zrezygnował z kartezjan na rzecz wycofania się, aby szybciej rozwiązać dużą zagadkę.

$p=[];foreach($r as$y=>$h){for($d=[2-($n=count($h)+1)+$u=-array_sum($h)+$w=count($r)]+array_fill($i=0,$n,1),$d[$n-1]=0;$i<1;$d[0]+=$u-array_sum($d)){$o=$x=0;foreach($d as$i=>$v)for($x+=$v,$k=$h[$i];$k--;)$o+=1<<$x++;if(($s[$y]|$o)==$o){$p[$y][]=$o;$q[$y]++;}for($i=0;$i<$n-1&$d[$i]==($i?1:0);$i++);if(++$i<$n)for($d[$i]++;$i--;)$d[$i]=1;}}
function s($i,$m){global$c,$w,$p;for(;!$k&&$i[$m]--;$k=$k&$m<$w-1?s($i,$m+1):$k){for($k=1,$x=$w;$k&&$x--;){$h=$c[$x];for($v=$n=$z=$y=0;$k&&$y<=$m;$y++)$n=$n*($f=($p[$y][$i[$y]]>>$x&1)==$v)+$k=$f?:($v=!$v)||$n==$h[$z++];if($k&$v)$k=$n<=$h[$z];}}return$k?is_array($k)?$k:$i:0;}
foreach(s($q,0)as$y=>$o)echo strrev(sprintf("\n%0{$w}b",$p[$y][$o]));
  • oczekuje podpowiedzi w tablicach podpowiedzi $rdo wierszy, podpowiedzi $cdo kolumn i $spodpowiedzi kwadratowych.
  • rzuca, invalid argument supplied for foreachjeśli nie znajdzie rozwiązania.
  • aby uzyskać prawidłową liczbę bajtów, użyj wartości fizycznej \ni usuń pozostałe dwa podziały wiersza.

opis

1) z podpowiedzi wierszy
wygeneruj możliwe wiersze, które spełniają podpowiedzi kwadratowe
i zapamiętaj ich liczby dla każdego indeksu wiersza.

2) cofnij się nad kombinacjami wierszy:
jeśli kombinacja spełnia podpowiedzi kolumny, szukaj głębiej lub zwróć udaną kombinację, w przeciwnym razie
spróbuj następnej możliwości dla tego wiersza

3) rozwiązanie drukowania

Ostatni golf miał poważny wpływ na wyniki;
ale usunąłem zadania profilowania dla końcowych testów porównawczych.

Wymień $n=$n*($f=($p[$y][$i[$y]]>>$x&1)==$v)+$k=$f?:($v=!$v)||$n==$h[$z++];
się if(($p[$y][$i[$y]]>>$x&1)-$v){$k=($v=!$v)||$n==$h[$z++];$n=1;}else$n++;
cofnąć ostatni krok w golfa.

przykłady

Dla małego przykładu (od 17 do 21 około 12 8 7 6,7 5,3 ms), użyj

$r=[[2],[3],[3],[3,1],[1]];$c=[[2],[3],[4],[2],[2]];$s=[0,0,0,0,0];

dla świątecznej układanki:

  • zabiłem mój mały serwer domowy starym rozwiązaniem
  • zabił przeglądarkę wynikami testowymi
  • teraz rozwiązany w 50 37,8 45,5 w około 36 sekund

umieść dane z pytania w pliku christmas.nonogrami użyj tego kodu, aby zaimportować:

$t=r;foreach(file('christmas.nonogram')as$h)if('-'==$h=trim($h))$t=c;elseif('#'==$h){$t=s;$f=count($h).b;}else
{$v=explode(' ',$h);if(s==$t)for($h=$v,$v=0,$b=1;count($h);$b*=2)$v+=$b*array_shift($h);${$t}[]=$v;}

awaria

$p=[];  // must init $p to array or `$p[$y][]=$o;` will fail
foreach($r as$y=>$h)
{
    // walk $d through all combinations of $n=`hint count+1` numbers that sum up to $u=`width-hint sum`
    // (possible `0` hints for $h) - first and last number can be 0, all others are >0
    for(
        $d=[2-
            ($n=count($h)+1)+               // count(0 hint)=count(1 hint)+1
            $u=-array_sum($h)+$w=count($r)  // sum(0 hint) = width-sum(1 hint)
        ]                           // index 0 to max value $u-$n+2
        +array_fill($i=0,$n,1)      // other indexes to 1
        ,$d[$n-1]=0;                // last index to 0
                                    // --> first combination (little endian)
        $i<1;   // $i:0 before loop; -1 after increment; >=$n after the last combination
        $d[0]+=$u-array_sum($d) // (see below)
    )
    {
        // A: create row (binary value) from 1-hints $h and 0-hints $d
        $o=$x=0;
        foreach($d as$i=>$v)
            for($x+=$v,$k=$h[$i];$k--;)
                $o+=1<<$x++;
        // B: if $o satisfies the square hints
        if(($s[$y]|$o)==$o)
        {
            $p[$y][]=$o;    // add to possible combinations
            $q[$y]++;       // increase possibility counter
        }
        // C: increase $d
            // find lowest index with a value>min
                // this loop doesn´t need to go to the last index:
                // if all previous values are min, there is nothing left to increase
        for($i=0;$i<$n-1&$d[$i]==($i?1:0);$i++);
        if(++$i<$n)             // index one up; increase $d if possible
            for($d[$i]++        // increase this value
            ;$i--;)$d[$i]=1;    // reset everything below to 1
            // adjust $d[0] to have the correct sum (loop post condition)
    }
}

// search solution: with backtracking on the row combinations ...
function s($i,$m)
{
    global $c,$w,$p;
    for(;
        !$k // solution not yet found
        &&$i[$m]    // if $i[$m]==0, the previous iteration was the last one on this row: no solution
            --;     // decrease possibility index for row $m
        $k=$k&$m<$w-1? s($i,$m+1) : $k      // if ok, seek deeper while last row not reached ($m<$w-1)
    )
    {
        // test if the field so far satisfies the column hints: loop $x through columns
        for($k=1,$x=$w;$k&&$x--;)   // ok while $k is true
        {
            $h=$c[$x];
            // test column hints on the current combination: loop $y through rows up to $m
            for($v=$n=$z=   // $v=temporary value, $n=temporary hint, $z=hint index
                $y=0;$k&&$y<=$m;$y++)
                // if value has not changed, increase $n. if not, reset $n to 1
                // (or 0 for $k=false; in that case $n is irrelevant)
                $n=$n*  
                    // $f=false (int 0) when value has changed, true (1) if not
                    ($f=($p[$y][$i[$y]]>>$x&1)==$v)
                    +$k=$f?:    // ok if value has NOT changed, else
                        ($v=!$v)        // invert value. ok if value was 0
                        || $n==$h[$z    // value was 1: ok if temp hint equals current sub-hint
                        ++]             // next sub-hint
                ;
            // if there is a possibly incomplete hint ($v==1)
            // the incomplete hint ($n) must be <= the next sub-hint ($c[x][$z])
            // if $n was <$h[$z] in the last row, the previous column hints would not have matched
            if($k&$v)$k=$n<=$h[$z];
        }
        // ok: seek deeper (loop post condition)
        // not ok: try next possibility (loop pre condition)
    }
    return$k?is_array($k)?$k:$i:0;  // return solution if solved, 0 if not
}

// print solution
foreach(s($q,0)as$y=>$o)echo strrev(sprintf("\n%0{$w}b",$p[$y][$o]));
— Tytus
źródło
1
Duży przykład zabija mój mały serwer domowy (500 - wewnętrzny błąd serwera). Kombinacje są gotowe po 15 sekundach, ale produkt kartezjański ma 1.823E + 61 członków. (Siódmy i 22-ty wiersz mają tylko jedno rozwiązanie między.) Algorytm musi zostać ulepszony.
— Tytus
Myślę, że można to przyspieszyć, jeśli użyjesz rekurencyjnego cofania. Niemniej świetna robota!
— gowrath
@gowrath: backtracking daje trochę, a nawet oszczędza bajty ... liczba całkowita z arytmetyką bitów daje około 50% prędkości, ale zwiększa rozmiar (muszę jeszcze dowiedzieć się, ile to dokładnie kosztuje) ... Nadal jestem na tym.
— Tytus
@gowrath: Goniłem mój błąd; było w przyrostach (gdzie indziej?): $dmusi być w odpowiedniej kolejnościforeach
— Tytus
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.