Wykreślanie linii metodą brute-force

25

tło

Nonogram , znany również jako Picross lub Griddlers, to łamigłówka, której celem jest ustalenie, czy każda komórka na siatce 2D powinna być pokolorowana, czy pozostawiona pusta, przy użyciu liczb kolejnych kolorowych komórek w każdej linii.

Poniżej znajduje się przykład puzzle Nonogram z rozwiązaniem.

Problem polega na tym, że niektóre komercyjne gry / aplikacje mobilne Nonogram mają łamigłówki, których nie można rozwiązać ręcznie (np. Mają wiele rozwiązań lub wymagają głębokiego cofania). Jednak oferują one także życie graczowi, w którym jedno życie zostaje utracone, gdy próbujesz pokolorować komórkę, której poprawna odpowiedź jest pusta . Czas więc brutalnie zmusić te paskudne „łamigłówki”!

Aby uprościć zadanie, wyobraź sobie tylko jedną linię ze wskazówką i niczym więcej:

3 7 | _ _ _ _ _  _ _ _ _ _  _ _ _ _ _

[3,7]to wskazówki, a długość linii wynosi 15 komórek. Ponieważ ma wiele możliwych rozwiązań, musimy zaryzykować życie, aby w pełni rozwiązać tę linię (tj. Określić wszystkie kolorowe komórki).

Wyzwanie

Biorąc pod uwagę linię ze wskazówkami (listę dodatnich liczb całkowitych) i długość linii, znajdź maksymalną liczbę żyć, które stracisz, zakładając, że brutalnie zmusisz linię z optymalną strategią.

Pamiętaj, że zawsze zgadujesz kolorowe komórki . W rzeczywistych grach odgadywanie pustych komórek (dobre lub złe) nie ma wpływu na twoje życie, więc nie możesz w ten sposób „rozwiązać” układanki.

Możesz również założyć, że dane wejściowe zawsze reprezentują prawidłową linię Nonogram, więc nie musisz się martwić o coś takiego [6], 5.

Wyjaśnienie

Najpierw spójrzmy na kilka prostszych przykładów.

[1,2], 5

Istnieją dokładnie trzy możliwości dla tej linii ( Ojest kolorową komórką, .jest pustą):

O . O O .
O . . O O
. O . O O

Jeśli spróbujemy kolorować komórkę 0 (indeks 0 od lewej), nastąpi jedna z następujących czynności:

  • Komórka jest poprawnie pokolorowana. Teraz mamy dwie możliwości i możemy wybrać między komórką 2 a komórką 4, aby w pełni rozwiązać linię. W obu przypadkach stracimy jedno życie w najgorszym przypadku.
  • Komórka jest pusta i tracimy życie. W tym przypadku zidentyfikowaliśmy już unikalne rozwiązanie tej linii, więc skończyliśmy z 1 straconym życiem.

Dlatego odpowiedź [1,2], 5brzmi 1.

[5], 10

Wyszukiwanie binarne? Nie.

Najbardziej oczywistym pierwszym wyborem jest 4 lub 5, które ujawnią jedną możliwość, jeśli jest pusta (kosztem 1 życia). Powiedzmy, że wybraliśmy 4 jako pierwsze. Jeśli komórka 4 rzeczywiście jest zabarwiona, rozciągamy ją w lewo, tj. Próbuj 3, 2, 1 i 0, aż do utraty życia (lub komórka 0 jest zabarwiona, w końcu nie wydajemy wcale życia). Za każdym razem, gdy ginie życie, możemy jednoznacznie ustalić rozwiązanie, np. Jeśli zobaczymy coś takiego:

_ _ X O O _ _ _ _ _

wiemy już, że odpowiedź brzmi:

. . . O O O O O . .

Dlatego odpowiedź na [5], 10to również 1.

[3,7], 15

Zacznij od komórki 11, która, jeśli jest pusta, od razu ujawni następujące rozwiązanie.

O O O . O O O O O O O X . . .

Następnie spróbuj 12, która, jeśli jest pusta, daje dwie możliwości, które można rozwiązać kosztem 1 dodatkowego życia.

O O O . . O O O O O O O X . .
. O O O . O O O O O O O X . .

Teraz spróbuj 2. Jeśli pusty, prowadzi do trzech możliwości, które można rozwiązać podobnie jak w [1,2], 5przykładzie.

. . X O O O . O O O O O O O .
. . X O O O . . O O O O O O O
. . X . O O O . O O O O O O O

Jeśli nadal minimalizujesz ryzyko w ten sposób, możesz osiągnąć dowolne rozwiązanie z maks. 2 życia spędzone.

Przypadki testowe

[1,2] 5 => 1
[2] 5 => 2
[1] 5 => 4
[] 5 => 0
[5] 10 => 1
[2,1,5] 10 => 0
[2,4] 10 => 2
[6] 15 => 2
[5] 15 => 2
[4] 15 => 3
[3,7] 15 => 2
[3,4] 15 => 3
[2,2,4] 15 => 4
[1,1,1,1,1,1,1] 15 => 2

[2,1,1,3,1] 15 => 3
[1,1,1,2,1] 15 => 5

W dwóch ostatnich przypadkach optymalną strategią nie jest przechodzenie przez minimalne odstępy, ale po prostu przechodzenie od lewej do prawej (lub od prawej do lewej). Dzięki @crashoz za wskazanie tego.

Zasady

Obowiązują standardowe zasady . Najkrótsze prawidłowe przesłanie w bajtach wygrywa.

Hojność

Jeśli ktoś wymyśli algorytm wielomianowy (z dowodem poprawności), przyznam +100 nagród za takie rozwiązanie.

Bubbler
źródło
Jaki jest zamierzony wynik [6], 5?
Leaky Nun
Kiedy zgadujesz, czy musisz zgadnąć, że komórka jest czarna, czy potrafisz zgadnąć, czy jest ona czarna, czy biała?
feersum
@LeakyNun To nieprawidłowa linia. Możesz założyć, że wejście jest zawsze prawidłową linią Nonogram.
Bubbler
@feersum Zawsze zgadujesz kolorowe komórki. W rzeczywistych grach odgadnięcie pustej komórki (właściwej lub złej) nie ma wpływu na twoje życie, więc nie możesz uzyskać z nią żadnej informacji zwrotnej.
Bubbler
Fantastyczne wyzwanie
Enrico Borba,

Odpowiedzi:

19

Rubinowy , 85 bajtów

f=->l,n,s=n-l.sum-l.size+1{*a,b=l;b&&s>0?(a[0]?1+f[a,n-b-2,s-1]:(n.to_f/b).ceil-1):0}

Wypróbuj online!

Wyjaśnienie

l=[l1,l2,...,lx]xn

lx
nlx
nlx1+f(l,nlx)
1+f(l~,nlx2)l~l

f(l,n)={0,if 1xli+x1nnlx1if x=11+max{f(l,nlx)f(l~,nlx2),otherwise

Oto przykład _jest nieznany, Xjest znaną przestrzenią, Ojest znaną kolorową komórką i Lginie życie

[2,2,4] 15                  _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
(1) -> [2,2,4] 11           _ _ _ _ _ _ _ _ _ _ _ L X X X
    (1) -> [2,2,4] 7        _ _ _ _ _ _ _ L X X X L X X X
        0                   X X X L X X X L X X X L X X X
    (2) -> [2,2] 5          _ _ _ _ _ X O O O O L L X X X
        0                   O O X O O X O O O O L L X X X 
(2) -> [2,2] 9              _ _ _ _ _ _ _ _ _ X O O O O L
    (1) -> [2,2] 7          _ _ _ _ _ _ _ L X X O O O O L
        (1) -> [2,2] 5      _ _ _ _ _ L X L X X O O O O L
            0               O O X O O L X L X X O O O O L
        (2) -> [2] 3        _ _ _ X O O L L X X O O O O L
            1               O O L X O O L L X X O O O O L               
    (2) -> [2] 5            _ _ _ _ _ X O O L X O O O O L
        2                   O O L L X X O O L X O O O O L

O(2n)

h

h(l,n)=n1xlix+1

h

h

h(l,nlx)=nlx1xlix+1=(n1xlix+1)lx=h(l,n)lx

h(l~,nlx2)=nlx21x1li(x1)+1=(n1xlix+1)1=h(l,n)1

h(l,n)={0,if 1xli+x1nnlx,if x=1max{h(l,nlx)+lxh(l~,nlx2)+1,otherwise

h

[h(l,nlx)+lx][h(l~,nlx2)+1]=nlxn1xlix+1+lx[nlx21x1li(x1)+1+1]=2

[h(l,nlx)+lx][h(l~,nlx2)+1]=2[h(l,nlx)+lx][h(l~,nlx2)+1]<0[h(l,nlx)+lx]<[h(l~,nlx2)+1]

h(l,n)={0,if 1xli+x1nnlx,if x=1h(l~,nlx2)+1otherwise

hfh

f(l,n)={0,if 1xli+x1nnlx1if x=11+f(l~,nlx2),otherwise

nO(n)

crashoz
źródło
2
Witamy w PPCG, niesamowity pierwszy post!
cole
1
@cole To nie jest ich pierwszy post, ale na pewno jest niesamowity! Bardzo sprytne podejście +1
Mr. Xcoder
1
Świetna robota. Przyznam nagrodę 2 dni później, jeśli do tego czasu nikt nie znajdzie poważnej logicznej wady.
Bubbler
2

Python, 303 289 bajtów

Pierwszy golf od dłuższego czasu, więc może być dużo nadmiaru tłuszczu. (Dzięki Jo King za znalezienie 14 bajtów.)

Funkcja f generuje wszystkie możliwe aranżacje (choć zawsze z pustym znakiem jako pierwszym znakiem, ale to w porządku, o ile zwiększamy długość o 1, zanim ją wywołamy). Funkcja g wybiera pozycję z najmniejszą liczbą odstępów i powtarza się. Funkcja h łączy je razem.

f=lambda l,n:["."*i+"X"*l[0]+c for i in range(1,n-l[0]+1)for c in f(l[1:],n-i-l[0])]if l else["."*n]
def g(q,n):O,X=min([[[p[:i]+p[i+1:]for p in q if p[i]==u]for u in".X"]for i in range(n)],key=lambda x:len(x[0]));return(len(q)>1)*1and max(1+g(O,n-1),g(X,n-1))
h=lambda l,n:g(f(l,n+1),n+1)

Wszystkie przykłady działają poprawnie:

>>> h([3,7],15)
2
>>> h([3,4],15)
3
>>> h([1,1,1,2,1],15)
6
Uri Granta
źródło
1
Czy wolno powrócić Falsedo 0? Jeśli tak, możesz zmienić (len(q)>1)*1andna len(q)>1and. Jeśli nie są dozwolone, aby powrócić Falsedo 0, a następnie zrobić to, ale zmiana g(f(l,n+1),n+1)na 1*g(f(l,n+1),n+1)i będzie jeszcze uratować jeden bajt
Zachary
1
Jeszcze lepiej: w przypadku, gdy Falsenie jest dozwolone 0, zamiast zmienić g(f(l,n+1),n+1)na 1*g(f(l,n+1),n+1), zmień na+g(f(l,n+1),n+1)
Zacharý
2
Ponadto nie trzeba liczyć liczby h=bajtów
Zacharý
1
288 bajtów .
Jonathan Frech