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

Są [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 gry w golfa . 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.

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=[l_1,l_2,...,l_x]$$x$$n$

$l_x$
$n-l_x$
$n-l_x$$1+f(l,n-l_x)$
$1+f(\tilde{l},n-l_x-2)$$\tilde{l}$$l$

$$f(l,n)=\begin{cases} 0, & \text{if } \sum_1^xl_i+x-1 \geq n\\ \lceil \frac{n}{l_x} \rceil - 1 & \text{if } x= 1\\ 1+\max\begin{cases} f(l,n-l_x)\\ f(\tilde{l},n-l_x-2) \end{cases}, & \text{otherwise} \end{cases}$$

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

$\mathcal{O}(2^n)$

$h$

$$h(l,n)=n - \sum_1^xl_i-x+1$$

$h$

$h$

$$\begin{align} h(l,n-l_x) &= n - l_x - \sum_1^xl_i-x+1\\ & =(n - \sum_1^xl_i-x+1) - l_x\\ & = h(l,n) - l_x \end{align}$$

$$\begin{align} h(\tilde{l},n-l_x-2) &= n - l_x - 2 - \sum_1^{x-1}l_i-(x-1)+1\\ & =(n - \sum_1^xl_i-x+1) - 1\\ & = h(l,n) - 1 \end{align}$$

$$h(l,n)=\begin{cases} \leq 0, & \text{if } \sum_1^xl_i+x-1 \geq n\\ n - l_x, & \text{if } x=1\\ \max\begin{cases} h(l,n-l_x)+l_x\\ h(\tilde{l},n-l_x-2)+1 \end{cases}, & \text{otherwise} \end{cases}$$

$h$

$$[h(l,n-l_x)+l_x] - [h(\tilde{l},n-l_x-2)+1]\\ \begin{align} &= n-l_x-n - \sum_1^xl_i-x+1 + l_x - [n-l_x-2 -\sum_1^{x-1}l_i-(x-1)+1+1]\\ &=-2 \end{align}$$

$$\begin{align} [h(l,n-l_x)+l_x] - [h(\tilde{l},n-l_x-2)+1] &=-2\\ [h(l,n-l_x)+l_x] - [h(\tilde{l},n-l_x-2)+1] &< 0\\ [h(l,n-l_x)+l_x] &< [h(\tilde{l},n-l_x-2)+1] \end{align}$$

$$h(l,n)=\begin{cases} \leq 0, & \text{if } \sum_1^xl_i+x-1 \geq n\\ n - l_x, & \text{if } x=1\\ h(\tilde{l},n-l_x-2)+1 & \text{otherwise} \end{cases}$$

$h$$f$$h$

$$f(l,n)=\begin{cases} 0, & \text{if } \sum_1^xl_i+x-1 \geq n\\ \lceil \frac{n}{l_x} \rceil - 1 & \text{if } x= 1\\ 1+ f(\tilde{l},n-l_x-2), & \text{otherwise} \end{cases}$$

$n$$\mathcal{O}(n)$

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