Flippin 'Squares


34

Utwórz program lub funkcję, aby odłączyć kwadrat cyfr, odwracając (odwracając punkt środkowy) tylko wiersze i kolumny.

Wkład

Dane wejściowe będą siatką cyfr 9 x 9 w postaci ciągu 9 wierszy, jak poniżej:

986553229
264564891
759176443
643982153
567891234
526917874
685328912
891732537
117644378

Ten format wejściowy nie podlega negocjacji - wszelkie rozwiązania, które są „kreatywne” z formatem wejściowym, zostaną uznane za nieprawidłowe.

Wydajność

Wyjściem powinna być lista ruchów odwracających, które zastosowane do danych wejściowych w podanej kolejności powinny odtworzyć siatkę docelową.

Przykładowe dane wyjściowe (nie rozwiązanie poprzedniego przykładu wprowadzania):

28IF5D3EAB9G3

Ten format wyjściowy również nie podlega negocjacji. Wyjście nie powinno zawierać znaków nowej linii ani spacji, a jedynie znaki 1- 9i A- I(małe litery są dopuszczalne zamiast wielkich liter, jeśli wolisz).

Siatka docelowa (stan, który należy odtworzyć) jest następująca:

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

Liczby 1- 9powinny być używane jako instrukcje do odwracania wierszy, a litery A- Ipowinny być używane dla kolumn. Jest to pokazane poniżej z przywróconą siatką.

     ABCDEFGHI
     |||||||||
     vvvvvvvvv
1 -> 123456789
2 -> 234567891
3 -> 345678912
4 -> 456789123
5 -> 567891234
6 -> 678912345
7 -> 789123456
8 -> 891234567
9 -> 912345678

Tak więc 8środek przewraca drugi rząd od dołu, a Fśrodek przewraca szóstą kolumnę.

W przypadku, gdy żadne rozwiązanie nie jest możliwe, program powinien zakończyć się bez wypisywania niczego.

Przykłady

Wkład:

987654321
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

Wydajność:

1

W takim przypadku tylko górny wiersz wymaga przewrócenia, aby powrócić do stanu docelowego.

Wkład:

123456788
234567897
345678916
456789125
567891234
678912343
789123452
891234561
912345679

Wydajność:

I

W takim przypadku tylko ostatnia kolumna (kolumna I) wymaga odwrócenia, aby odtworzyć stan celu.

Wkład:

123456788
798765432
345678916
456789125
567891234
678912343
789123452
891234561
912345679

Wydajność:

2I

W takim przypadku musimy odwrócić wiersz, 2a następnie odwrócić kolumnę, Iaby powrócić do stanu docelowego.

Uwagi:

  • W odpowiedzi podaj przykład użycia.
  • Podane dane wyjściowe nie muszą być najkrótszą sekwencją, która zwróci stan celu - każda sekwencja, która zwróci stan celu, będzie działać tak długo, jak to działa (tj. Tak długo, jak mogę to przetestować)
  • Postaram się przetestować każdą odpowiedź i głosować za tymi wszystkimi, którzy działają i oczywiście próbowali grać w golfa.
  • To są zawody otwarte - zaakceptuję najkrótszą odpowiedź w przyszłym tygodniu, ale jeśli pojawi się nowa, ważniejsza odpowiedź, która będzie krótsza w dowolnym momencie w przyszłości, zmienię zaakceptowaną odpowiedź, aby to odzwierciedlić .
  • Nagroda została ustalona na 200 reputacji za najkrótszą odpowiedź otrzymaną do 23:59:59 (GMT) w dniu 26.01.2014. Nagroda została przyznana Howardowi za jego 268-znakowe rozwiązanie GolfScript .

Testowanie

Podaj odpowiedź swojego programu dla następujących trzech siatek testowych:

986553229
264564891
759176443
643982153
567891234
526917874
685328912
891732537
117644378

927354389
194762537
319673942
351982676
567891234
523719844
755128486
268534198
812546671

813654789
738762162
344871987
341989324
567891234
576217856
619623552
194435598
926543271

Stworzyłem mały program w języku Python do generowania prawidłowych siatek do celów testowych:

import random

def output(array):
  print '\n'.join([''.join(row) for row in array])

def fliprow(rownum, array):
  return [row[::1-2*(rownum==idx)] for idx,row in enumerate(array)]

def flipcol(colnum, array):
  return zip(*fliprow(colnum, zip(*array)))

def randomflip(array):
  op=random.randint(0,1)
  row=random.randint(0,9)
  if(op==1):
    return fliprow(row, array)
  else:
    return flipcol(row, array)

def jumble(array):
  arraycopy=array
  for i in range(10, 1000):
    arraycopy=randomflip(arraycopy)
  return arraycopy

startarray=[
['1','2','3','4','5','6','7','8','9'],
['2','3','4','5','6','7','8','9','1'],
['3','4','5','6','7','8','9','1','2'],
['4','5','6','7','8','9','1','2','3'],
['5','6','7','8','9','1','2','3','4'],
['6','7','8','9','1','2','3','4','5'],
['7','8','9','1','2','3','4','5','6'],
['8','9','1','2','3','4','5','6','7'],
['9','1','2','3','4','5','6','7','8']]

print output(jumble(startarray))

8
Właśnie napisałem krótkie rozwiązanie, które losowo przewracało wiersze / kolumny aż do zakończenia sortowania. Po 500 milionach iteracji wciąż nie rozwiązał pierwszej podanej układanki (w której wystarczy przerzucić wiersz 1). Losowość nie wydaje się użytecznym rozwiązaniem tego problemu!
— Josh

3
@Josh Nic dziwnego. Ten problem wydaje się bardzo podobny do rozwiązania kostki rubika. Uważam, że jakaś brutalna siła byłaby najlepszym przeszukiwaniem w pierwszej kolejności. To powiedziawszy, losowy algorytm teoretycznie musi się ostatecznie skończyć i wydaje się pasować do określonych reguł.
— Cruncher

4
Brutalna siła nie jest potrzebna. Weź pod uwagę fakt, że każdy kafelek siatki może skończyć się tylko w jednej z czterech pozycji: w prawidłowej lokalizacji, odwrócony X, odwrócony Y lub odwrócony XY. Pomoże ci to potraktować w myślach kratkę jako (0,0) będącą środkową płytką. Jeśli rozwiązywania płytki (-2, 4), jedyne lokalizacje numer docelowy może być to (-2, 4), (2, 4), (2, -4), lub (-2, -4).
— Pan Llama,

2
@Cruncher: Użycie całych wierszy / kolumn powoduje, że jest to niemożliwe. Na przykład spróbuj wziąć najwyższą lewą 1 ( A1) i przesuń ją do B1. Możesz dostać 1pozycję B1, ale będzie to płytka z B9, a nie płytka z A1. Ponieważ wolno nam przewracać tylko cały wiersz / kolumnę, najwyższy lewy 1 będzie zawsze w jednym z czterech najbardziej zewnętrznych narożników. Jeśli popełniłem błąd, daj mi znać.
— Pan Llama,

7
Gratulacje, Gareth. To bardzo dobrze zaprojektowany problem. Także dość trudne.
— DavidC

Odpowiedzi:


7

GolfScript, 300 279 268 znaków

n%`{\5,{.9+}%{;.2/\2%},\;''{1${.9/7+7*+}%+:z;}:?~{{.9<77*{\zip\9-}>:Z~{1$!{-1%}*\(\}@%\Z;}/}:E~{:^;{:c;.`{[\E[.^=\8^-=]{.c=\8c-=}%[^c+^8c-+8^-c+16c-^-]{9%49+}%=}+[[]]:K[[8^- 17c-][^9c+]1$]{:s;{[[]s.+.2$+]{1$+}/}%.&}/\,K+0=z?E}5,/}5,/{{+9%)}+9,%''*}9,%={z:u;}*}+1024,/u

Zauważ, że ten kod jest bardzo wolny (również z powodu ciężkich manipulacji blokami kodu) i może działać kilka minut. Kod jest bardzo nieskryptowy z dużą ilością zmiennych i wyraźnych pętli.

Napisałem bardziej analityczne rozwiązanie, które działało krócej niż sekundę. Zepsułem to całkowicie podczas gry w golfa. Niestety nie byłem w stanie przywrócić ani naprawić kodu w ciągu ostatnich dwóch dni. Dlatego stworzyłem tę wersję próbną, która i tak jest krótsza.

Odpowiedzi na puzzle podane powyżej:

1A2C4D9G9G9G9G1C1C1C1C9F9F9F9F1D1D1D1D2A2A2A2A8H8H8H8H2B2B2B2B2C2C8F8F2D2D2D2D3A3A7I7I3B3B7H7H7G7G7G7G3D3D7F7F6I6I6I6I4A4A4A4A6H6H6H6H6G6G4C4C4C4C6F6F4D4D

1AB39I9I1A1A9I9I1B1B9F9F8I8I8I8I2B2B8H8H8G8G8G8G2D2D2D2D3A3A3A3A7H7H7H7H3C3C3C3C3D3D7F7F6I6I4A4A6I6I4B4B4B4B6G6G4C4C4C4C6F6F6F6F4D4D

1A34D9I9I9I9I1A1A1A1A1B1B1B1B9G9G1C1C1C1C9F9F9F9F1D1D9F9F8I8I2A2A2A2A8H8H8H8H2C2C2C2C8F8F2D2D8F8F7I7I7I7I3A3A3B3B7G7G7G7G3C3C3C3C6I6I6I6I6H6H6H6H4B4B4B4B6G6G6G6G4C4C6G6G6F6F4D4D6F6F

Cóż, pokonanie tego będzie ciężką pracą ...
— Gareth

Wygląda na to, że się myliłem ...
— Gareth

@Gareth Wiedziałem, że jest to wyzwanie, które byłoby trudne przy golfa przeciwko np. Matematyce.
— Howard

1
@Howard - jakie podejście zastosowałeś? Czym jest „wersja próbna”, o której wspominałeś?
— SergeyS

24

Mathematica 582 575 503 464 282

Do walki z golfistami muszę używać ciężkiej artylerii!

i = "986553229
264564891
759176443
643982153
567891234
526917874
685328912
891732537
117644378";

a=Array;h@M_:=Join@@a[9(M〚##〛/. 9->9⌈2Random[]⌉)+Abs[{##}-5]&,n={9,9}];
For[i_~t~j_:=i{#2,10-#2}+j#-9&~a~{9,4},!ListQ[e=GroupElementToWord[
PermutationGroup[Cycles/@Join[1~t~9,9~t~1]],
h[ToCharacterCode@StringSplit@i-48]~FindPermutation~h@a[Mod[8+##,9,1]&,n]]],];
e~IntegerString~36<>""

Wydajność:

g69g69g8g8g7g7gd96d96d8d8d7d7dh6h64a6a46d6d4g4g6b6b7h7h7c7c2a8a27b7bd8db8b7f7fg8g82c2c94a4a3a3aigfdc91

Tutaj PermutationGroup[...]ustawia możliwe odwroty i GroupElementToWord[...]rozwiązuje problem (około 0.2sekundy). Głównym problemem jest to, że trudno jest ustalić zgodność między pozycją 9w początkowej i końcowej siatce. Do gry w golfa robię to losowo (zajmuje to kilka sekund). Istnieją pewne ostrzeżenia, ale można je zignorować.

Inne do testowania siatek:

g69g69g8g8g7g7gh89h89h7h7h6h6hf6f6g6g64f4f4h4hg7g73g3g2a8a28d8db8b83d3dg8g82c2c9a3a643a3a2g9f9d9c9ga
h89h89h7h7h6h6h6h6h6f6f6g6g6d6d3a7a37g7g7h7h3c3c2a8a27b7b8d8d2f2f8b8b3f3f2b2ba2a764a8aih9g9c9gb1i

Całkowicie odtwarza przykłady:

1
i
2i

Poprzednie rozwiązanie (464)

bez sprytnych wbudowanych funkcji i przy czasie działania 4 ms:

M=ToCharacterCode@StringSplit@i-48;
S="";s=Signature;H=(S=S<>{#,#2+9}~IntegerString~36)&;
A=(m=M〚##〛)-9Mod[m+##,2]&[s@{2#3,5}#,2#2#3~Mod~2-#2]&~Array~{4,4,4};
u=s/@Join@@A;
H@@({k,l}=#&@@@#~Position~1&/@{v=u〚13;;〛;{h=#2u〚2〛,-#u〚5〛,-#u〚9〛}&@@v,v〚4〛=u〚4〛h;v});
A〚k〛=A〚k,;;,{2,1,3,4}〛;A〚;;,l〛=A〚;;,l,{3,2,1,4}〛;
MapIndexed[4#≠#4&&H@@@If[#2<3,#0[#3,#,#2,#4];k,#0[#,#3,#4,#2];10-k]&@@
If[s@#<0,#〚{1,3,2,4}〛,#]&@Ordering[k={#2,#2};#]&,A,{2}];
M〚5,1〛<5&&5~H~{};M〚1,5〛<5&&{}~H~5;S

Wszystkie nowe linie tutaj nie są konieczne.

Wydajność:

3b9i9i1a1a1a1a9i9i1a1a9h9h1b1b1b1b9h9h9g9g1c1c9g9g9f9f1d1d9f9f8h8h2b2b8f8f8f8f7i7i7h7h3b3b3b3b7h7h3b3b7h7h7g7g3c3c7g7g3c3c7f7f6i6i4a4a6h6h4b4b4b4b6g6g4c4c6g6g4c4c6f6f4d4d4d4d6f6f4d4d6f6f4d4d

Pozostałe dwie siatki testowe:

13ab9i9i1a1a9i9i9h9h1b1b1b1b9h9h9f9f8i8i8i8i8h8h2b2b2b2b8h8h8h8h8g8g8g8g8f8f2d2d2d2d8f8f2d2d7i7i3a3a3a3a7i7i7h7h3b3b7h7h3b3b7g7g3c3c3c3c7g7g3c3c7f7f3d3d3d3d7f7f7f7f6i6i4a4a6i6i6h6h4b4b4b4b6h6h4b4b6g6g4c4c4c4c6f6f4d4d4d4d6f6f4d4d6f6f
2bc9i9i1a1a9i9i9g9g1c1c9g9g1c1c9f9f1d1d1d1d8i8i8i8i8h8h2b2b2b2b8f8f2d2d7i7i7h7h3b3b3b3b7h7h3b3b7g7g3c3c7f7f3d3d3d3d7f7f3d3d6i6i4a4a4a4a6h6h4b4b6g6g6g6g6f6f4d4d

Wyobrażanie sobie:

anim = Reap[Fold[Function[{m, i}, 
 If[i > 9, (Sow@Grid[#, Background -> {i - 9 -> Pink, None}] & /@ {m, #}; #) &@
   Transpose@MapAt[Reverse, Transpose@m, i - 9], (Sow@Grid[#, 
         Background -> {None, i -> Pink}] & /@ {m, #}; #) &@
   MapAt[Reverse, m, i]]], M, IntegerDigits[FromDigits[S, 36], 36]]];

ListAnimate[Join[{#, #} &@Grid@M, anim[[2, 1]], {#, #} &@Grid@anim[[1]]], 5]

wprowadź opis zdjęcia tutaj

Ciąg wejściowy imoże być generowany losowo przez

M = Array[Mod[8 + ##, 9, 1] &, {9, 9}];
(M[[#]] = Reverse@M[[#]]; M[[All, #2]] = Reverse@M[[All, #2]];) & @@@
   RandomInteger[{1, 9}, {10000, 2}];
i = ToString /@ # <> "\n" & /@ M <> ""

Krótka dyskusja

  • Przerzuty mogą zamieniać tylko te elementy („poczwórne”):

    wprowadź opis zdjęcia tutaj

  • Możliwe jest wymienianie tych elementów oddzielnie od innych elementów tylko wtedy, gdy zamówienie początkowe i końcowe ma ten sam podpis.

  • Odwrócenie tych czterech elementów tworzy naprzemienną grupę stopnia 4 (= grupa obrotów czworościennych). Każdy element z tej grupy składa się z 2 elementów generujących. Więc jeśli znamy pozycję początkową i końcową, możemy dekomponować odpowiednią transformację jako kombinację prostych przerzutów.

Detale

Dla sportowców zamieszczam szczegóły przed końcem nagrody!

M=ToCharacterCode@StringSplit@i-48;

Konwertuj ciąg ina macierz M.

S="";s=Signature;H=(S=S<>{#,#2+9}~IntegerString~36)&;

Dodamy znaki do S. Teraz jest to pusty ciąg. H[i,j]doda znak i( 1,2,3,...,9) i znak j( a,b,c,...,iw bazie 36).

A=(m=M〚##〛)-9Mod[m+##,2]&[s@{2#3,5}#,2#2#3~Mod~2-#2]&~Array~{4,4,4};

Konwertuję elementy jako

wprowadź opis zdjęcia tutaj

aby uzyskać macierz docelową w następującej formie

wprowadź opis zdjęcia tutaj

W moim algorytmie są dwa główne etapy

  1. Znajdź flipy, aby uzyskać podpisy jak w macierzy docelowej (np. Podpis {-7,-1,1,7}is 1i podpis {-6,2,-2,6}is -1):

    u=s/@Join@@A;
    H@@({k,l}=#&@@@#~Position~1&/@{v=u〚13;;〛;{h=#2u〚2〛,-#u〚5〛,-#u〚9〛}&@@v,v〚4〛=u〚4〛h;v});
    A〚k〛=A〚k,;;,{2,1,3,4}〛;A〚;;,l〛=A〚;;,l,{3,2,1,4}〛;
    
  2. Obracaj każdy „poczwórny”, aby uzyskać odpowiednią kolejność:

    MapIndexed[4#≠#4&&H@@@If[#2<3,#0[#3,#,#2,#4];k,#0[#,#3,#4,#2];10-k]&@@
    If[s@#<0,#〚{1,3,2,4}〛,#]&@Ordering[k={#2,#2};#]&,A,{2}];
    

    Jest to najbardziej nietrywialna część algorytmu. Na przykład transformacja 1b1bzostanie przekonwertowana {-7,-1,1,7}na {-1,1,-7,7}. Transformacja 9h9hzostanie przekonwertowana {-7,-1,1,7}na {-7,7,-1,1}. Mamy więc dwie mapy

    {1,2,3,4} -> {2,3,1,4}
    {1,2,3,4} -> {1,4,2,3}
    

    i chcemy przekształcić dowolną kolejność {x,y,z,w}do {1,2,3,4}. Prostą metodą jest (z wyjątkiem wyszukiwania losowego)

    repeat   
    {x, y, z, w} -> If[z < 3, {y, z, x, w}, {x, w, y, z}]
    until {1,2,3,4}
    

    Nie mogę tego udowodnić, ale działa!

Ostatnim krokiem jest

M〚5,1〛<5&&5~H~{};M〚1,5〛<5&&{}~H~5;S

Wykonuje trywialne odwrócenie środkowego rzędu i środkowej kolumny i zwraca wynik.


@Gareth Czy mogę używać małych znaków na wyjściu? Oszczędza mi to wielu znaków.
— ybeltukov

Tak, zaakceptuję małe litery w danych wyjściowych (zmienię pytanie, aby to zauważyć). Nie mam Mathematica, więc czy inny użytkownik Mathematica może potwierdzić, że kod faktycznie generuje dane wyjściowe? Zweryfikowałem trzy testowe rozwiązania i wszystkie są poprawne, więc daj +1. Dobra robota!
— Gareth

Ciekawe - jakie jest twoje podejście? Czy testowałeś dane wejściowe generowane przez tysiące przerzutów?
— SergeyS

@SergeyS Tak, zajmuje to około 50 ms :)
— ybeltukov

@Gareth Przepisuję mój program, czy możesz sprawdzić wyniki? Moje testy wykazały, że wszystko jest w porządku.
— ybeltukov

7

jot 487 438

q=:3 :'(>:9|+/~i.9)=/&((,{;/(,.8&-)y){])g'
l=:2 :0
:
o=:o,(m+x){a.
x&(|.@{`[`]})&.v y
)
r=:49 l]
c=:97 l|:
w=:2 :'g=:4 v^:(4=(<m){g)g'
p=:_1=C.!.2@,@:I.@q
t=:2 :'for_i.>:i.3 do.g=:i v^:(p m*i)g end.'
z=:2 :0
'i j I J'=.y,8-y
g=:".'(',(,' ',.,(I.m{q y){,;._1 n),'])^:2 g'
)
d=:3 :0
g=:9 9$".,_ list,' ',.y
o=:''
0 4 w c
4 0 w r
0 1 t c
g=:0 c^:(-.(p 1 0)=p 1 2)g
1 0 t r
for_k.>,{;~i.4 do.0 z';;jcir;irjc;Irjc'k
3 z';;IrJc;JcIr;'k end.o
)

d jest czasownikiem, który pobiera ciąg siatki w określonym formacie i zwraca ciąg rozwiązania w określonym formacie.

Przykładowe zastosowanie:

   d '987654321',LF,'234567891',LF,'345678912',LF,'456789123',LF,'567891234',LF,'678912345',LF,'789123456',LF,'891234567',LF,'912345678'
bcda2341a1a1b1b1c1c1d1da2a2b2b2c2c2d2d2a3a3b3b3c3c3d3d3a4a4b4b4c4c4d4d4

Teraz akceptuje albo nowy typ linii.

Rozwiązania do siatek testowych:

b3a1a11b1bc9c99g9gd9d99f9fb8b8f8f87i7i7h7hc3c3g7g77f7fa6a64b4bh6h6c4c4g6g6d6d6f6f6
cd24a9a91c1c1d1d9f9fa2a2i8i88h8hc2c2g8g82d2d3b3bh7h7d3d37f7fa6a64b4bg6g64d4d6f6f
bc2a9a99i9ic1c1g9g91d1df9f9i8i8b2b2h8h82c2cd8d87i7ib3b3c7c7d3d34a4ai6i6b6b6g6g6d6d6

Jestem dość nowy w J; to może być jeszcze bardziej golfa.


Sprawdzanie, czy siatki są nieprawidłowe / nierozwiązywalne, podlega karze 123 znaków. Nie sądzę, aby inne dotychczasowe odpowiedzi zawierały takie sprawdzanie błędów.

Aby to zrobić, zmień pierwszy wiersz dna:

if.-.+./89 90=#y do.0 return.end.if.-.*./(/:~y)=/:~(#y)$'123456789',LF do.0 return.end.g=:9 9$".,_ list,' ',.y

i ostatnia linia do tego:

3 z';;IrJc;JcIr;'k end.if.*./,g=>:9|+/~i.9 do.o return.end.0

Zdecydowałem się powrócić 0po takich błędach, że zwrócenie pustego łańcucha byłoby nie do odróżnienia od poprawnego rozwiązania w pełni rozwiązanej siatki. Zauważ, że zakłada to nowe wiersze UNIX (ponownie).


Gratulacje, właśnie wyszedłeś na prowadzenie. :-)
— Gareth,

Wygląda na to, że Twój wpis nie jest jednym ciągiem, jak wymagają tego reguły, czy coś mi umknęło?
— SergeyS

@SergeyS: Możesz się mylić. O ile mi wiadomo, J nie ma możliwości umieszczania znaków ucieczki (takich jak nowa linia) w literałach łańcuchowych. Konstrukcja „a”, LF, „b” w J jest podobna do „a” + „\ n” + „b” w językach, w których + działa, aby dodać ciągi znaków.
— AlliedEnvy

Ok, to ma sens niż dzięki.
— SergeyS

Właśnie czytałem sekcję dotyczącą plików z książki APL z 1962 roku i myślę, że @AlliedEnvy ma rację. W ten sposób dane pojawią się w programie, jeśli zostaną odczytane z pliku w formacie pytania. Do LFs reprezentują partycje pliku sekwencyjnego.
— luser droog

5

DO# 540 399

Cóż, poświęcona wydajność (teraz zajmuje to do 30 sekund), wprowadzono zmienne dynamiczne, nieznacznie zmieniono logikę rozwiązania. I tak, teraz oczekuje danych wejściowych jako jednego ciągu z podziałem wierszy (zgodnie z wymaganiami reguł).

Oczywiście C # nie ma predefiniowanych funkcji matematycznych, więc ciężko byłoby walczyć z chłopakami Mathematica. Niemniej jednak było to wielkie wyzwanie, dzięki autorowi!

string S(string _){for(i=0,e=1>0;e;){
for(h=v=j=0;j<89;)m[j/10,j%10+9]=_[j++]-49;a="";
for(j=i++;j>0;v++,j/=2)if(j%2>0)F(v);
for(;h<9&(h<4|!e);h+=j/36,j%=36)if((e=m[h,g=j++%9+9]!=(t=(h+g)%9))|m[v=8-h,g]==t){F(v);F(g);F(v);F(g);}
}return a;}void F(int z){for(f=z<9;++l<9;)m[0,l]=m[f?z:l,f?9+l:z];for(;l-->0;)m[f?z:l,f?9+l:z]=m[0,8-l];a+=(char)(z+=f?49:56);}
dynamic h,v,i,j,e,t,l=-1,g,a,m=new int[9,19],f;

Siatki testowe:

3B9A9A9B9B9C9C9D9D9F9F9G9G9H9H9I9I9B9B9C9C9D9D9F9F9G9G9H9H9C9C9D9D9C9C9D9D8B8B8F8F8H8H8B8B8F8F8B8B8H8H7B7B7C7C7F7F7H7H7I7I7H7H6A6A6B6B6C6C6D6D6F6F6H6H6A6A6B6B6D6D6F6F6D6D6D6D6F6F5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I

13AB9A9A9B9B9F9F9H9H9A9A9B9B9H9H9I9I8B8B8D8D8F8F8G8G8H8H8I8I8B8B8G8G8H8H8I8I8H8H7A7A7B7B7C7C7D7D7F7F7G7G7I7I7A7A7D7D7F7F7I7I7F7F6A6A6B6B6C6C6D6D6F6F6G6G6H6H6I6I6A6A6C6C6F6F6I6I6A6A6A6A5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I

2BC9A9A9C9C9D9D9F9F9A9A9D9D9I9I8B8B8D8D8H8H8I8I8B8B8D8D8I8I7B7B7C7C7D7D7F7F7G7G7H7H7I7I7C7C7C7C7G7G6A6A6B6B6D6D6F6F6G6G6I6I6A6A6B6B6D6D6G6G6D6D6F6F5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I

Stare rozwiązanie (540)

Działa w mniej niż sekundę na dowolnym wejściu (testowane na tysiącach losowo generowanych siatek). Maksymalna długość łańcucha wyjściowego to 165 (początkowo każda siatka została rozwiązana w nie więcej niż 82 rzutach, ale podczas gry w golfa poświęciłem to).

string S(string[]_){for(i=0;i<1<<18;){
for(j=0;j<81;)m[j/9+49,j%9+65]=_[j/9][j++%9]-49;a="";char g,h='1',v='9',b,x=h,y;
for(j=i;j>0;x=x==v?'A':++x,j/=2)if(j%2>0)F(x);j=i+1;
for(i+=1<<19;h<58;h++,v--)for(g='A',b='I';g<74;g++,b--){
t=(h+g-6)%9;e=m[h,g];q=m[v,g];i=h>52&t!=e?j:i;
if(e!=t|q==t){x=q==t?v:g;y=q==t?g:v;
if(m[h,b]==t){x=b;y=h;}
F(x);F(y);F(x);F(y);}}}return a;}
void F(char z){var f=z<65;for(l=0;l<4;l++){n=m[d=f?z:49+l,s=f?65+l:z];m[d,s]=m[o=f?z:57-l,u=f?73-l:z];m[o,u]=n;}a+=z;}
int i,j,q,e,t,l,s,d,n,u,o;int[,]m=new int[99,99];string a;

Odpowiedz na przykład 1:

15A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

Odpowiedz na przykład 2:

19AI1I1H1H1G1G1F1F19F9F9G9G9H9H9I9I8A8AI8I87A7AI7I76A6AI6I65A5A5B5B5C5C5D
5DE5E55F5F5G5G5H5H5I5I

Odpowiedz na przykład 3:

129AI1I1H1H1G1G1F1F19F9F9G9G9H9H9I9I8A8AI8I87A7AI7I76A6AI6I65A5A5B5B5C5C5
D5DE5E55F5F5G5G5H5H5I5I

Odpowiedzi na kwadraty testowe:

346B9A9AH1H1C9C9D9D99F9F9G9GH9H99I9IB8B8F8F87B7B7C7C7F7FH7H77I7I6A6A6B6BC6C66D6DG6G6H6H66I6I5A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

1346ABA9A9H1H19F9FH9H99I9IH2H28D8D8F8FG8G8I8I8I3I37B7B7C7CF3F37G7GI7I7H4H4D6D66F6F5A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

2BCA9A99C9CF1F19F9F9I9IH2H2D8D88H8HI8I87B7BC7C77D7D7F7F7H7H7I7II4I4B6B6D6D6G6G66I6I5A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

Właśnie pobieram teraz Mono na komputer Mac, aby móc przetestować sam program, ale mam już moduł sprawdzania poprawności, który uruchamia dane rozwiązanie na danej siatce i mówi mi, czy rozwiązanie jest prawidłowe dla tej siatki - i jest to mówiąc mi, że trzy przykładowe rozwiązania, które mi podałeś, są nieprawidłowe. Właśnie badam, dlaczego teraz.
— Gareth

Aha! Zrozumiałem, co się tutaj wydarzyło! Podane odpowiedzi wydają się być odpowiedziami na 3 przykłady, a nie na trzy siatki testowe (które znajdują się niżej w pytaniu). Rzeczywiście są one poprawnymi rozwiązaniami dla tych siatek, choć są one nieco dłuższe niż 1, Ai 2Iktóre są najprostszymi rozwiązaniami - ale to nie ma znaczenia, ponieważ nie oceniam długości rozwiązania siatki :-) Jeśli mógłbyś edytować i udzielę odpowiedzi na 3 siatki testowe (zobaczę, czy mogę to teraz uruchomić na moim komputerze Mac). Mogę dać ci +1.
— Gareth

@Gareth - Ups, przegapiłem odpowiedzi na kwadraty testowe, dziękuję za zwrócenie na to uwagi. Dodałem je teraz do mojej odpowiedzi.
— SergeyS

Doskonale, dzięki za to. Wszyscy dobrze się sprawdzili. Xamarin z jakiegoś powodu nie działałby na moim Macu, więc za kilka godzin będę musiał przetestować program w pracy.
— Gareth

@Gareth - Właściwie nie ma nic specyficznego dla C # w tym kodzie, prawdopodobnie można go przekonwertować na Javę, a nawet C ++ bez większego bólu i ... golfować niektóre znaki z niego :) Również możesz przekonwertować go na GolfScript lub coś więcej zwięzłe - może pojawić się dwa lub więcej razy;)
— SergeyS
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.