Rozwiąż grę na akordeonie

13

Akordeon to gra w pasjansa, którą ostatnio spotkałem, w której prawie każdy układ jest do rozwiązania, ale niezwykle trudny. Możesz zagrać tutaj .

Zasady

52 odkryte karty są umieszczane odkryte w losowej kolejności. W każdej turze zamieniasz kartę na późniejszą, w której dwie karty :

  • Udostępnij garnitur lub numer i
  • Są w odległości 1 (sąsiadujące) lub 3 (dwie karty pomiędzy nimi).

Gra zostaje wygrana, gdy pozostała tylko 1 karta . Możesz założyć, że każde wejście można rozwiązać. Wymieniona karta musi zawsze poprzedzać kartę zastępującą.

Przykład

Jako przykład rozważ następujący układ:

2H,2S,1S,2D  (H: Hearts, S: Spades, D: Diamonds)

Istnieją tutaj 3 możliwe ruchy:

  1. Zamień na 2Hsąsiednie 2S, więc skończymy z2S,1S,2D
  2. Zamień na 2Ssąsiednie 1S, więc skończymy z2H,1S,2D
  3. Wymienić 2Hz 2D(w odległości 3), tak, że kończy się z2D,2S,1S

Z tych 3 ruchów tylko ostatni ma możliwość wygranej (wygrywasz 2D <- 2Swtedy, zastępując 2S <- 1S).

Wejście wyjście

Twoim zadaniem jest napisanie solwera do akordeonu . Otrzymałeś listę kart i musisz zwrócić listę ruchów, aby rozwiązać grę.

Otrzymujesz listę kart jako ciąg rozdzielany przecinkami, gdzie każda karta jest przekazywana jako liczba całkowita reprezentująca ich wartość liczbową, a następnie znak reprezentujący ich kolor.

Musisz zwrócić listę zamienników jako ciąg rozdzielany przecinkami, gdzie każda zamiana ma format Card <- Card(zgodny z formatem karty opisanym powyżej). Pierwsza karta w każdej parze to karta zastępowana.

Przypadki testowe:

5H,1C,12S,9C,9H,2C,12C,11H,10C,13S,3D,8H,1H,12H,4S,1D,7H,1S,13D,13C,7D,12D,6H,10H,4H,8S,3H,5D,2D,11C,10S,7S,4C,2H,3C,11S,13H,3S,6C,6S,4D,11D,8D,8C,6D,5C,7C,5S,9D,10D,2S,9S
5H,9C,11H,7S,7D,12D,6H,10S,3H,4D,12C,2S,3C,5C,7H,6S,1H,8S,2H,11S,4C,10D,12H,9H,2D,4H,6C,13H,11C,2C,10H,8C,1S,11D,3S,12S,7C,5D,13S,8D,4S,6D,13C,3D,8H,13D,1D,9D,9S,1C,5S,10C
7H,11C,8C,7S,10D,13H,4S,10C,4D,2C,4H,13D,3C,2H,12C,6C,9H,4C,12H,11H,9S,5H,8S,13S,8H,6D,2S,5D,11D,10S,1H,2D,5C,1C,1S,5S,3H,6S,7C,11S,9C,6H,8D,12S,1D,13C,9D,12D,3D,7D,10H,3S

Podczas gdy te zawody to gra w , jestem szczególnie zainteresowany rozwiązaniami oszczędzającymi czas i prawdopodobnie nagrodzę pomysłowe rozwiązania nagrodami. To powiedziawszy, rozwiązania wymagające astronomicznej ilości czasu są nadal akceptowalne (zalecałbym testowanie z mniejszą talią, taką jak talia 16 kart, 4 kolory).

Nathan Merrill
źródło
Czy twoje zasady wspominają, że ruchy można wykonywać tylko w jednym kierunku?
feersum
6
Każda karta na stole ma średnio około 0,25 + 0,25 = 0,5 legalnego ruchu. Dlatego przestrzeń wyszukiwania wynosi około 52! * 0,5 = 4E67. Wywołane wyzwanie (z kodem golfowym) można interpretować jedynie jako przeszukiwanie całej przestrzeni i zgłaszanie dowolnego rozwiązania (lub „brak”, jeśli się wyczerpuje), co pozostawia niewiele miejsca na pomysłowość i wymaga astronomicznych ram czasowych. Sugeruję, aby uczynić to wyzwaniem dla kodu, biorąc pod uwagę wskaźnik sukcesu i czas, i albo zmniejszyć wpływ długości kodu na wynik, albo całkowicie go wyeliminować.
Level River St
1
@ Pietu1998 i na tym polega problem. Zakładam, że pamięć kosztuje Cię bajtów, więc powinieneś przesłać wersję bez pamięci jako wersję golfową, ale wtedy testowanie na talii 52 kart staje się niemożliwe. Codegolf nie działa dobrze jako system oceniania problemów z dużymi przestrzeniami wyszukiwania.
Level River St
3
Nie przeszkadzają mi astronomiczne środowiska wykonawcze dla tych, którzy chcą grać w golfa. Jednak ludzie z pewnością są w stanie (i zachęcani) do publikowania odpowiedzi, które nie są konkurencyjne i dotyczą czasu wykonywania.
Nathan Merrill
4
Ponadto, jeśli chcesz przetestować grę w golfa kodowego, talia 52 kart nie jest potrzebna. Talia 16 kart (4 kolory) powinna zapewniać krótkie czasy działania i sprawdzać poprawność.
Nathan Merrill

Odpowiedzi:

5

Python 3, 274 272 271 bajtów

2 bajty zapisane dzięki @orlp .

def g(p):
 q=lambda a:[[i,a]for i in range(len(p)-a)if p[i][:-1]==p[i+a][:-1]or p[i][-1]in p[i+a]]
 for n in q(1)+q(3):
  s=sum(n);c=p[:s]+p[s+1:];c[n[0]]=p[s]
  if g(c):return p[n[0]]+' <- '+p[s]+','+g(c)
 return' 'if len(p)<2else[]
print(g(input().split(','))[:-2]or'')

To jest bardzo wolne. Możesz jednak spróbować z notatką . To ma kilka dodatkowych list- tuplekonwersje, ale jest inaczej równoważne.

import functools
@functools.lru_cache(maxsize=None)
def g(p):
 q=lambda a:[[i,a]for i in range(len(p)-a)if p[i][:-1]==p[i+a][:-1]or p[i][-1]in p[i+a]]
 for n in q(1)+q(3):
  s=sum(n);c=list(p[:s]+p[s+1:]);c[n[0]]=p[s]
  if g(tuple(c)):return p[n[0]]+' <- '+p[s]+','+g(tuple(c))
 return' 'if len(p)<2else[]
print(g(tuple(input().split(',')))[:-2]or'')

Nawet ten jest astronomicznie wolny z pewnymi wejściami.

Kod używa ciągów, a nie liczb, więc obsługuje również notację typu KHzamiast 13H.

Przykład:

$ python accordion.py
5H,9C,11H,7S,7D,12D,6H,10S,3H,4D,12C,2S,3C,5C,7H,6S,1H,8S,2H,11S,4C,10D,12H,9H,2D,4H,6C,13H,11C,2C,10H,8C,1S,11D,3S,12S,7C,5D,13S,8D,4S,6D,13C,3D,8H,13D,1D,9D,9S,1C,5S,10C
7S <- 7D,7D <- 12D,3C <- 5C,12H <- 9H,11C <- 2C,3S <- 12S,13D <- 1D,1D <- 9D,9D <- 9S,2S <- 6S,7H <- 1H,6S <- 8S,1H <- 2H,8S <- 11S,2H <- 9H,10D <- 2D,9H <- 4H,4H <- 4C,5C <- 4C,4D <- 4C,4C <- 12C,10S <- 11S,11H <- 11S,6H <- 3H,12D <- 2D,12C <- 2C,2C <- 6C,6C <- 8C,12S <- 13S,5D <- 6D,6D <- 8D,8D <- 3D,4S <- 9S,13S <- 9S,11D <- 3D,7C <- 1C,1S <- 1C,1C <- 13C,8C <- 13C,13C <- 13H,13H <- 10H,2D <- 3D,3D <- 3H,3H <- 8H,8H <- 10H,11S <- 5S,5H <- 10H,5S <- 9S,10H <- 10C,10C <- 9C,9C <- 9S
PurkkaKoodari
źródło
Użyj functools.lru_cachezamiast pisać własne.
orlp
@orlp Chciałbym, ale ponieważ listjest nie do powstrzymania, to nie działa.
PurkkaKoodari
Następnie użyj krotek.
orlp
@orlp OK, ale wymagałoby to zmian w kodzie (np. str.splitzwrotów list). Wolałbym, żeby te dwa programy były funkcjonalnie równoważne.
PurkkaKoodari
Można to zrobić h=lambda p:lru_cache(None)(g)(''.join(p)).
orlp