W grze sudoku wielu graczy lubi „rysować” możliwymi liczbami, które można wstawić na każdym polu:
Powyższy wiersz może być reprezentowany jako tablica:
[[1,2,9], [6], [5], [7], [1,2,9], [1,2,9], [3], [1,2,4], [8]]
Teraz zauważ, że jest tylko 1 miejsce, do którego 4
można się udać. Pozwala to skutecznie uprościć powyższą listę do:
[[1,2,9], [6], [5], [7], [1,2,9], [1,2,9], [3], [4], [8]]
Celem tego wyzwania jest sporządzenie listy możliwych liczb w permutacji i ustalenie, które możliwości można wyeliminować .
Jako kolejny przykład załóżmy, że masz następujący wachlarz możliwości:
[[0,1,3], [0,2,3], [1,2], [1,2]]
Ostatnie dwa miejsca muszą być wypełnione 1 i 2. Dlatego możemy usunąć te możliwości z pierwszych dwóch elementów w tablicy:
[[0,3], [0,3], [1,2], [1,2]]
Jako kolejny przykład:
[[0,1,2,3], [0,2], [0,2], [0,2]]
Jego niemożliwe do skonstruowania permutacji z powyższych możliwości, jako że jest tylko 1 miejsce dla obu 1
i 3
, i chcesz powrócić pustą tablicę.
Musisz wprowadzić listę możliwości i wypisać pozostałe możliwości po wyeliminowaniu maksymalnej liczby możliwości.
- Jeśli dana tablica jest niemożliwa, musisz zwrócić pustą tablicę lub tablicę, w której jedna z podtablic jest pusta.
- Możesz założyć, że tablica będzie dobrze uformowana i będzie zawierać co najmniej 1 element.
- Biorąc pod uwagę tablicę rozmiarów
N
, możesz założyć, że liczby w podtablicy będą zawsze w zakresie[0:N)
i toN <= 10
- Nie możesz zakładać, że każda liczba od
0
doN-1
będzie obecna - Możesz założyć, że liczby w jednej podtablicy są unikalne.
- Jeśli podtablica zawiera tylko jedną możliwość, możesz ją przedstawić w tablicy lub samodzielnie.
[[1],[2],[0]]
,[1,2,0]
,[[1,2],0,[1,2]]
Wszystkie są ważne. - Możesz zaakceptować tablicę w rozsądnym formacie łańcuchowym lub w formacie listy / tablicy.
- Podesty mogą być w dowolnej kolejności.
- Zamiast zajmować się obdartymi tablicami, możesz wypełniać puste miejsca
-1
.
Przypadki testowe
[[0]] -> [[0]]
[[1],[0]] -> [[1],[0]]
[[1],[1]] -> []
[[1],[0,1]] -> [[1],[0]]
[[0,1,2],[1,2],[1,2]] -> [[0],[1,2],[1,2]]
[[0,1],[1,2],[0,2]] -> [[0,1],[1,2],[0,2]]
[[2,1],[1,2],[1,2]] -> []
[[0,3],[2,1],[3,0],[3,2]] -> [[0,3],[1],[0,3],[2]]
[[0,1],[0,1],[2,3],[2,3,0]] -> [[0,1],[0,1],[2,3],[2,3]]
[[0,1],[0,3],[3,2],[0]] -> [[1],[3],[2],[0]]
[[3,5,2],[0,2,4],[4,0],[0,1,3,5],[2,1],[2,4]] -> [[3,5],[0,2,4],[4,0],[3,5],[1],[2,4]]
[[6,9,8,4],[4,5],[5,3,6],[3,8,6,1,4],[3,1,9,6],[3,7,0,2,4,5],[9,5,6,8],[6,5,8,1,3,7],[8],[8,0,6,2,5,6,3]] -> [[6,9,4],[4,5],[5,3,6],[3,6,1,4],[3,1,9,6],[0,2],[9,5,6],[7],[8],[0,2]]
[[3,5,0],[5,7],[5,1,2],[1,3,0],[5,3],[5,0],[5,3,7,8,0,6],[7,5,0,1,8],[1,0,8],[0,6]] -> []
[[9,0,2,3,7],[0,7,6,5],[6,9,4,7],[9,1,2,3,0,5],[2,8,5,7,4,6],[6,5,7,1],[5,9,4],[5,9,3,8,1],[5,0,6,4],[0,7,2,1,3,4,8]] -> [[9,0,2,3,7],[0,7,6,5],[6,9,4,7],[9,1,2,3,0,5],[2,8,5,7,4,6],[6,5,7,1],[5,9,4],[5,9,3,8,1],[5,0,6,4],[0,7,2,1,3,4,8]]
[[2,6,0],[0,4,3],[0,6,2],[0,7],[0,9,2,3,6,1,4],[1,7,2],[2,7,8],[8,6,7],[6,5,2,8,0],[5,8,1,4]] -> [[2,6,0],[3],[0,6,2],[0,7],[9],[1],[2,7,8],[8,6,7],[5],[4]]
[[8],[8,0,6,5,7,2,4,1],[8,6,9,3,5,0,7],[3,9,1,0],[9],[9,2,6],[2,8,3],[3,1,6,8,2],[6],[6,4,5,3,0,7]] -> [[8],[5,7,4],[5,7],[0],[9],[2],[3],[1],[6],[4,5,7]]
[[8,1,0],[5,8,7,6,2,0],[6,8,2],[2,4,0,9],[4,1,7,3,6,8],[8,1],[8,0,3],[0,8,2],[0,8,3],[1,8,0]] -> []
To jest gra w golfa, więc udziel odpowiedzi tak krótko, jak to możliwe!
źródło
Odpowiedzi:
Brachylog , 21 bajtów
Wypróbuj online!
Wypróbuj online!
Predykat 0 (główny predykat)
Predykat 1 (pomocniczy predykat 1)
Predykat 2 (pomocniczy predykat 2)
źródło
Galaretka , 10 bajtów
Wypróbuj online!
źródło
Pyth , 11 bajtów
Wypróbuj online!
źródło
Haskell, 100 bajtów
źródło
and.flip(zipWith elem)z
jest krótszyWłaściwie 27 bajtów
Wypróbuj online!
źródło
Python 3,
10199 bajtówDzięki @TLW za -2 bajty
Anonimowa funkcja, która pobiera dane wejściowe za pomocą argumentu listy list i zwraca listę zestawów.
Jak to działa
Wypróbuj na Ideone
źródło
list(map(set,
jest krótszy, jak sądzęMathematica, 46 bajtów
źródło
PHP,
245231 bajtów131117 dla funkcji produktu kartezjańskiego, 114 dla innych rzeczyWystąpiły problemy z pamięcią w niektórych przypadkach testowych z funkcją rekurencyjną dla produktu kartezjańskiego. Działa lepiej z tą klasą generatora i
function c($a){$b=[];foreach($a as$i)$b[]=new \ArrayIterator($i);return new CartesianProductIterator($b);}
.Ale mój generator jest krótszy i wykonuje tę samą pracę.
Większe przykłady powodują jednak błąd wewnętrzny serwera (zarówno z iteratorem, jak i generatorem) po pewnym czasie na moim komputerze. Niestety nie ma czasu na sprawdzenie logów serwera.
źródło