Kompulsje krzyżowe!

14

Chris, tajemniczy uzależniony od krzyżówek, ma ustalony algorytm, według którego je rozwiązuje.

wprowadź opis zdjęcia tutaj

Użyjemy powyższego obrazu jako przewodnika.

  1. Chris zawsze zaczyna od pierwszej wskazówki, w tym przypadku 1 Across. Chris jest zdolnym entuzjastą krzyżówki, więc zakłada się, że zawsze pozna odpowiedź na wskazówkę, nad którą pracuje.
  2. Gdy Chris ukończy wskazówkę, sprawdzi wszystkie wskazówki sąsiadujące z tymi, które ukończył (w pierwszym przypadku 1 w dół, 2 w dół i 3 w dół), a następnie ukończy wskazówkę o najniższym numerze. Jeśli nie ma żadnych sąsiednich wskazówek, przejdzie do kroku 3.
  3. Jeśli wskazówka jest taka, że ​​następny numer (jak opisano w kroku 3) zawiera zarówno wskazówkę przekreśloną, jak i wskazówkę dolną, najpierw ukończy wskazówkę przekreśloną (100% pewności, to graniczy z OCD!)
  4. Jeśli nie ma żadnych sąsiadujących wskazówek, przejdzie do następnej dostępnej wskazówki, która będzie następna pod względem liczby (w poprzek lub w dół)
  5. Powtarzaj od kroku 2, aż wszystkie wskazówki zostaną ukończone.

I tu sprowadza się do was, drodzy koderzy. Masz za zadanie stworzyć kod, który po otrzymaniu szablonu krzyżówki może dostarczyć wyniki opisujące kolejność wskazówek opartych na algorytmie Chrisa do jego rozwiązania.

Kod zaakceptuje wprowadzenie szablonu krzyżówki w postaci .białego kwadratu i #czarnego kwadratu.

Przykład :

.....#.........
.#.#.#.#.#.#.#.
...#...#.......
.#.#.#.#.#.#.#.
....#..........
##.#.#.#.#.#.#.
......#........
.###.#####.###.
........#......
.#.#.#.#.#.#.##
..........#....
.#.#.#.#.#.#.#.
.......#...#...
.#.#.#.#.#.#.#.
.........#.....

Dane wejściowe mogą odbywać się poprzez: a) odczyt pliku reprezentacji krzyżówki, lub b) wprowadzanie linii każdego wiersza krzyżówki, a następnie \ndrugie \nwskazanie EOF.

A następnie określi metodę, według której Chris rozwiąże go zgodnie z powyższym algorytmem, który opisał.

Dane wyjściowe muszą być w formacie szeregu instrukcji oddzielonych przecinkami w postaci n(A|D), gdzie njest numer wskazówki, po której następuje znak „ Aza” lub „ Dza”.

Tak więc w powyższym przykładzie (zarówno z obrazu, jak i przykładowego szablonu, które są jednym i tym samym), dane wyjściowe byłyby następujące:

1A,1D,2D,3D,9A,10A,4D,5D,6D,7D,8D,11A,12A,13A,15A,14D,15D,16A,17A,18D,19D,20A,21D,23A,22D,24A,25D,27A,28A,26D,29A,30A,31A

Najkrótszy kod wygrywa ...

Testowanie

Musisz podać swój kod, liczbę bajtów, a także jeden z czterech przypadków testowych reprezentowanych w formacie .i #, a także dane wyjściowe wygenerowane z tego wejścia. Istnieją cztery przypadki testowe, trzy poniżej oraz powyższy przykładowy szablon.

Przykładowe przypadki testowe:

Przypadek testowy 1

.....#
.#.#.#
...#..
.#.#.#
.....#
##.#..

Wynik: 1A,1D,2D,3D,4A,5A,6A,7A

Przypadek testowy 2

.....#..
.#.##..#
.#....#.
...##.#.
.####...
......##

Wynik: 1A,1D,2D,5A,4D,4A,3D,3A,7A,8A,6D,9A

Przypadek testowy 3 

.........#
#.#.#.#.#.
....#...#.
#...#.#.#.
..###.#.#.
.#....#...
.#####...#
.....###..

Wynik: 1A,2D,3D,4D,5D,7A,8A,9A,10A,11A,11D,12A,13A,6D,14D,15A,16A,17A

Przypadek testowy 4

.....#.........
.#.#.#.#.#.#.#.
...#...#.......
.#.#.#.#.#.#.#.
....#..........
##.#.#.#.#.#.#.
......#........
.###.#####.###.
........#......
.#.#.#.#.#.#.##
..........#....
.#.#.#.#.#.#.#.
.......#...#...
.#.#.#.#.#.#.#.
.........#.....

Wynik: 1A,1D,2D,3D,9A,10A,4D,4A,5D,6D,7D,8D,11A,12A,13A,15A,14D,15D,16A,17A,18D,19D,20A,21D,23A,22D,24A,25D,27A,28A,26D,29A,30A,31A

Powodzenia!

code-golf  crossword 
— WallyWest
źródło
Dla pewności: na przykładowym obrazie, która liczba jest piątą wskazówką, którą należy wypełnić kompulsywnie? (po 1H, 1V, 2V, 3V)
— Dr Belisarius
@belisarius Zdjęcie odpowiada czwartemu przypadkowi testowemu. Tak więc piąta wskazówka do wypełnienia to 9 Across, lub, jak to ująłbyś, 9H :) Ponieważ jedynymi sąsiadującymi wskazówkami po ukończeniu czwartej wskazówki są 9 i 10 Across, Chris będzie zmuszony do wypełnienia najniższej wskazówki jako pierwszej ...
— WallyWest
Są bajty brane pod uwagę tylko na podstawie kodu, który daje prawidłowe dane wyjściowe. IOW, czy jesteś karany za włączanie, przestrzeń nazw C # + klasa + Main i tym podobne, aby uzyskać możliwość kompilacji, czy uzasadnione jest założenie, że jeśli napiszę w języku C # lub podobnym, to wymagana będzie minimalna ilość kodu?
— ChiefTwoPencils
1
@BobbyDigital Cóż, to jest golf golfowy ... Mam nadzieję, że jeśli planujesz napisać go w C #, spróbujesz nie używać zbyt wielu zewnętrznych elementów ... Musisz je policzyć, obawiam się ... ,
— WallyWest
1
@WallyWest Myślę, że twój trzeci przykład pomija 17Ana końcu. Również czwarty 4Azaraz po 4D.
— Howard

Odpowiedzi:

5

GolfScript, 154 znaków

:^,,{.^=46<{;-1}*)}%[.^n?)/zip[0]*]{1,%{,1>},}%:H"AD"1/]zip{~`{1$0=H{{0=}/}%.&$?)\+[\]}+/}%(2/\{0=)[\~\]}$+[]{1${1=1$&},.!{;1$1<}*1<:F~~@|@F-\1$}do;;]','*

Dane wejściowe należy podać na STDIN. Przykłady dają następujące wyniki (sprawdź online ):

1A,1D,2D,3D,4A,5A,6A,7A

1A,1D,2D,5A,4D,4A,3D,3A,7A,8A,6D,9A

1A,2D,3D,4D,5D,7A,8D,9A,10A,11A,11D,12A,13A,6D,14D,15A,16A,17A

1A,1D,2D,3D,9A,10A,4D,4A,5D,6D,7D,8D,11A,12A,13A,15A,14D,15D,16A,17A,18D,19D,20A,21D,23A,22D,24A,25D,27A,28A,26D,29A,30A,31A
— Howard
źródło
+1 Niezwykle zwięzły. Jak to działa?
— DavidC
Wow, dzięki za wyjaśnienie, że nie powinienem nawet marnować czasu. Najwyraźniej trzeba będzie opanować bardziej odpowiedni język. votes++
— ChiefTwoPencils
@BobbyDigital Miałem na myśli brak szacunku. C # jest bardzo pełnym językiem ... prawdopodobnie nie jest najlepszy do golfa kodowego. Kręgielnia kodów lub konkursy popularności tutaj ... ale Code Golf to zupełnie nowy czajnik ryb.
— WallyWest
Tutaj też +1 ... Prawdopodobnie jeden z dłuższych wpisów w GolfScript, które widziałem ... Świetnie zrobione.
— WallyWest,
1
@BobbyDigital: Samo zadanie jest dość interesujące. Spróbuj w języku, który znasz. Myślę, że spodoba ci się ta łamigłówka tak samo jak ja - zbadaj różne podejścia do rozwiązania zagadki. To sama w sobie zabawa, nawet jeśli nie osiągniesz liczby tak niskich jak ta odpowiedź.
— Howard
3

Mathematica 806 477

(Wygląda na to, że wystąpiła usterka w porządku kroków rozwiązania. Patrzę na to.)

Grał w golfa

Funkcja qznajduje kolejność rozwiązań krzyżówek.

i = Dimensions; v = MemberQ; u = Position; y = ToString; k = Select;
q@t_ :=
 (g@p_ := Characters@StringSplit[p, "\n"];
  w = g@t;
  a[{r_, c_}, z_] := (c != i[z][[2]]) \[And] 
    v[u[z, "."], {r, c + 1}] \[And] ((c == 1) \[Or] 
      v[u[z, "#"], {r, c - 1}]);
  b@z_ := k[u[z, "."], a[#, z] &];
  d[{r_, c_}, z_] := (r != i[z][[2]]) \[And] 
    v[u[z, "."], {r + 1, c}] \[And] ((r == 1) \[Or] 
      v[u[z, "#"], {r - 1, c}]);
  e@z_ := k[u[z, "."], d[#, z] &];
  Cases[Flatten[{
       If[v[b[w], #[[1]]], y[#[[2]]] <> "A"],
       If[v[e[w], #[[1]]], y[#[[2]]] <> "D"]} & /@ (MapIndexed[List, 
        b[w] \[Union] e[w]] /. {{r_, c_}, {i_}} :> ({r, c} -> i))], 
   Except[Null]])

Nie golfił

q[t7_]:=
Module[{d,acrossSquareQ,acrossSquares,downSquareQ,downSquares,m,numberedCells},
(*w=g[t7];*)
g[p2_]:=Characters@StringSplit[p2,"\n"];
w=g[t7];
acrossSquareQ[{r_,c_},z_]:=(c!=Dimensions[z][[2]])\[And]MemberQ[Position[z,"."],{r,c+1}] \[And]((c==1)\[Or]MemberQ[Position[z,"#"],{r,c-1}]);
acrossSquares[z_]:=Select[Position[z,"."],acrossSquareQ[#,z]&];
downSquareQ[{r_,c_},z_]:=(r!=Dimensions[z][[2]])\[And]MemberQ[Position[z,"."],{r+1,c}] \[And]((r==1)\[Or]MemberQ[Position[z,"#"],{r-1,c}]);
downSquares[z_]:=Select[Position[z,"."],downSquareQ[#,z]&];
numberedCells[z_]:=acrossSquares[z]\[Union]downSquares[z];
m=MapIndexed[List,numberedCells[w]]/.{{r_?IntegerQ,c_?IntegerQ},{i_?IntegerQ}}:> ({r,c}-> i);
Cases[Flatten[{
If[MemberQ[acrossSquares[w],#[[1]]],ToString[#[[2]]]<>"A"],
If[MemberQ[downSquares[w],#[[1]]],ToString[#[[2]]]<>"D"]}&/@m],Except[Null]]]

boardwyświetla krzyżówkę. Kod nie jest uwzględniany w liczbie znaków. qWypożyczono tutaj kilka podfunkcji .

board[p_]:=
Module[{q,g,w,downSquareQ,downSquares,acrossSquareQ,acrossSquares,numberedCells,m},
downSquareQ[{r_,c_},z_]:=(r!=Dimensions[z][[2]])\[And]MemberQ[Position[z,"."],{r+1,c}] \[And]((r==1)\[Or]MemberQ[Position[z,"#"],{r-1,c}]);
downSquares[z_]:=Select[Position[z,"."],downSquareQ[#,z]&];
acrossSquareQ[{r_,c_},z_]:=(c!=Dimensions[z][[2]])\[And]MemberQ[Position[z,"."],{r,c+1}] \[And]((c==1)\[Or]MemberQ[Position[z,"#"],{r,c-1}]);
acrossSquares[z_]:=Select[Position[z,"."],acrossSquareQ[#,z]&];
numberedCells[z_]:=acrossSquares[z]\[Union]downSquares[z];
g[p2_]:=Characters@StringSplit[p2,"\n"];
w=g[p];
m=MapIndexed[List,numberedCells[w]]/.{{r_?IntegerQ,c_?IntegerQ},{i_?IntegerQ}}:> ({r,c}-> i);
Grid[ReplacePart[w,m],Dividers->All,Background->{None,None,(#-> Black)&/@Position[w,"#"]}]]

Przypadki testowe

1

t1=".....#
.#.#.#
...#..
.#.#.#
.....#
##.#..";
board[t1]
q[t1]

t1

{„1A”, „1D”, „2D”, „3D”, „4A”, „5A”, „6A”, „7A”}

2)

t2=".....#..
.#.##..#
.#....#.
...##.#.
.####...
......##";

board[t2]
q[t2]

t2

{„1A”, „1D”, „2D”, „3A”, „3D”, „4A”, „4D”, „5A”, „6D”, „7A”, „8A”, „9A”}

3)

t3=".........#
#.#.#.#.#.
....#...#.
#...#.#.#.
..###.#.#.
.#....#...
.#####...#
.....###..";

board[t3]

q[t3]

t3

{„1A”, „2D”, „3D”, „4D”, „5D”, „6D”, „7A”, „8D”, „9A”, „10A”, „11A”, „11D”, „ 12A ”,„ 13A ”,„ 14D ”,„ 15A ”,„ 16A ”,„ 17A ”}

4

t4=".....#.........
.#.#.#.#.#.#.#.
...#...#.......
.#.#.#.#.#.#.#.
....#..........
##.#.#.#.#.#.#.
......#........
.###.#####.###.
........#......
.#.#.#.#.#.#.##
..........#....
.#.#.#.#.#.#.#.
.......#...#...
.#.#.#.#.#.#.#.
.........#.....";

board[t4]


q[t4]

t4

{„1A”, „1D”, „2D”, „3D”, „4A”, „4D”, „5D”, „6D”, „7D”, „8D”, „9A”, „10A”, „ 11A ”,„ 12A ”,„ 13A ”,„ 14D ”,„ 15A ”,„ 15D ”,„ 16A ”,„ 17A ”,„ 18D ”,„ 19D ”,„ 20A ”,„ 21D ”,„ 22D ” , „23A”, „24A”, „25D”, „26D”, „27A”, „28A”, „29A”, „30A”, „31A”}

— DavidC
źródło
Myślę, że masz problem ze swoim kodem. Np. W przykładzie 2 3Anie powinno być zaraz po, 2Dponieważ nie ma jeszcze wskazówki. Także inne rozwiązania wykazują ten efekt.
— Howard
Howard, nie rozumiem twojego punktu widzenia. Od „4. Jeśli nie ma żadnych sąsiednich wskazówek, przejdzie do następnej dostępnej wskazówki, która będzie następna pod względem liczby (w poprzek lub w dół)”, wygląda na to, że 3A może być po 2D.
— DavidC
Ale np. 5AMa wskazówkę i dlatego należy ją faworyzować 3A.
— Howard
Zdefiniowałeś stenografię ToStringdwa razy
— dr belizariusz
Howard, teraz rozumiem twój punkt widzenia. Dzięki. Poprawi się później.
— DavidC
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.