Zasada Permutation Pigeon-hole

25

W grze sudoku wielu graczy lubi „rysować” możliwymi liczbami, które można wstawić na każdym polu:

Wiersz Sudoku

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 4moż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 1i 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 0do N-1bę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 więc udziel odpowiedzi tak krótko, jak to możliwe!

Nathan Merrill
źródło
Dowolna liczba większa niż 9?
Leaky Nun
Nie musisz obsługiwać numerów większych niż 9.
Nathan Merrill
Czy mogę powrócić z duplikatami w subarrays?
Leaky Nun
@LeakyNun no. Podcienie mogą zawierać tylko unikalne elementy.
Nathan Merrill
Myślę, że masz błędy w czwartym przypadku testowym; jedna z list podrzędnych ma podwójne nawiasy kwadratowe.
TheBikingViking

Odpowiedzi:

17

Brachylog , 21 bajtów

:1fz:da|,[]
:2a#d
:Am

Wypróbuj online!

Wypróbuj online!

Predykat 0 (główny predykat)

:1fz:da|,[]
:1f            Find all solutions of Predicate 1 using Input as Input.
   z           Transpose
    :da        Deduplicate each.
       |,[]    If there is no solution, return [] instead.

Predykat 1 (pomocniczy predykat 1)

:2a#d
:2a     Each element of Output satisfies Predicate 2 with each element of Input as Input
   #d   Each element is different

Predykat 2 (pomocniczy predykat 2)

:Am     Output is member of Input
Leaky Nun
źródło
8

Galaretka , 10 bajtów

Œp⁼Q$ÐfZQ€

Wypróbuj online!

Œp⁼Q$ÐfZQ€   Main chain, argument: z

Œp           Cartesian product
  ⁼Q$Ðf      Filter for those that remain unchanged when uniquified
       Z     Transpose
        Q€   Uniquify each subarray
Leaky Nun
źródło
Wydaje się nieco nieuczciwe zajmowanie 10 bajtów, gdy Jelly używa znaków spoza Latin1. Powyższa sekwencja, reprezentowana jako UTF-8, wymaga 16 bajtów.
Chris Becke
1
@ChrisBecke Jelly ma własny
zestaw
A jednak - jeśli spróbuję online! - Muszę wysłać 16 bajtów.
Chris Becke,
@ChrisBecke Tak, ale jeśli pobierzesz Jelly, wystarczy napisać 10-bajtowy program.
Leaky Nun
I zapisać go w pliku tekstowym, którego nie mogę edytować za pomocą niczego innego niż Jelly? Przez ten argument, gdyby Jelly skompresował swój program, powinniśmy liczyć tylko skompresowane bajty?
Chris Becke,
7

Pyth , 11 bajtów

{MC{I#.nM*F

Wypróbuj online!

{MC{I#.nM*F
         *F  reduce by Cartesian product
             produces nested arrays
      .nM    flatten each
   {I#       filter for invariant under deduplication
  C          transpose
{M           deduplicate each
Leaky Nun
źródło
6

Haskell, 100 bajtów

import Data.List
p z=map nub$transpose$filter(and.(flip$zipWith elem)z)$permutations[0..length z-1]
Geoff Reedy
źródło
Fajne rozwiązanie! and.flip(zipWith elem)zjest krótszy
Damien
2

Python 3, 101 99 bajtów

Dzięki @TLW za -2 bajty

from itertools import*
lambda x:list(map(set,zip(*[i for i in product(*x)if len(i)==len(set(i))])))

Anonimowa funkcja, która pobiera dane wejściowe za pomocą argumentu listy list i zwraca listę zestawów.

Jak to działa

from itertools import*        Import Python's library for iterator generation
lambda x                      Anonymous function with input possibilities x as a
                              list of lists
...for i in product(*x)...    For i in the Cartesian product of x, ie all candidate
                              arrangements:
[...if len(i)==len(set(i))]    Filter into list by non-duplicity (set removes
                               duplicates, so there are no duplicates if the length
                               of i is the same as the length of the set of
                               the elements of i)
zip(*...)                     Unpack and take the transpose, leaving the modified
                              possibilities with duplicates
map(set,...)                  Remove duplicates
:list(...)                    Return the modified possibilities as a list of sets

Wypróbuj na Ideone

TheBikingViking
źródło
list(map(set,jest krótszy, jak sądzę
TLW
2

Mathematica, 46 bajtów

Union/@Thread@Select[Tuples@#,DuplicateFreeQ]&
alephalpha
źródło
0

PHP, 245 231 bajtów

131 117 dla funkcji produktu kartezjańskiego, 114 dla innych rzeczy

function c($a){if ($a){if($u=array_pop($a))foreach(c($a)as$p)foreach($u as$v)yield $p+[count($p)=>$v];}else yield[];}
function p($a){foreach(c($a)as$i)if(max(array_count_values($i))<2)foreach($i as$k=>$v)$r[$k][$v]=$v;return$r?:[];}

Wystą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.

Tytus
źródło