25
\$\begingroup\$

In the game of sudoku, many players like to "pencil in" possible numbers that can go in each square:

Sudoku row

The above row can be represented as an array:

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

Now, notice that there is only 1 place where a 4 can go. This effectively lets us simplify the above list to:

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

The goal of this challenge is to take a list of possible numbers in a permutation, and deduce which possibilities can be eliminated.

As another example, lets say you have the following array of possibilities:

[[0,1,3], [0,2,3], [1,2], [1,2]]

The last two places must be filled with 1 and 2. Therefore, we can remove those possibilities from the first two elements in the array:

[[0,3], [0,3], [1,2], [1,2]]

As another example:

[[0,1,2,3], [0,2], [0,2], [0,2]]

Its impossible to construct a permutation from the above possibilities, as there's only 1 location for both 1 and 3, and you would want to return an empty array.

You need to input a list of possibilities and output the remaining possibilities after the maximum number of possibilities have been eliminated.

  • If a particular array is impossible, you either need to return an empty array, or an array where one of the subarrays is empty.
  • You may assume that the array will be well-formed, and have at least 1 element.
  • Given an array of size N, you can assume the numbers in the subarray will always be in the range [0:N), and that N <= 10
  • You may not assume that every number from 0 to N-1 will be present
  • You may assume that numbers within a single subarray are unique.
  • If a subarray contains only a single possibility, you can either represent the possibility in an array or by itself. [[1],[2],[0]], [1,2,0], [[1,2],0,[1,2]] are all valid.
  • You may accept the array either in a reasonable string format or in list/array format.
  • Subarrays can be in any order.
  • Instead of dealing with ragged arrays, you can pad empty places with -1.

Test cases

[[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]] -> []

This is a so make your answers as short as possible!

\$\endgroup\$
  • \$\begingroup\$ Any number greater than 9? \$\endgroup\$ – Leaky Nun Aug 23 '16 at 14:57
  • \$\begingroup\$ You don't need to support numbers greater than 9. \$\endgroup\$ – Nathan Merrill Aug 23 '16 at 15:00
  • \$\begingroup\$ Can I return with duplicates in subarrays? \$\endgroup\$ – Leaky Nun Aug 23 '16 at 15:03
  • \$\begingroup\$ @LeakyNun no. Subarrays can only contain unique elements. \$\endgroup\$ – Nathan Merrill Aug 23 '16 at 15:04
  • \$\begingroup\$ I think you've got some mistakes in your fourth test case; one of the sublists is double-bracketed. \$\endgroup\$ – TheBikingViking Aug 23 '16 at 21:00
17
\$\begingroup\$

Brachylog, 21 bytes

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

Try it online!

Try it online!

Predicate 0 (main predicate)

: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.

Predicate 1 (auxiliary predicate 1)

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

Predicate 2 (auxiliary predicate 2)

:Am     Output is member of Input
\$\endgroup\$
8
\$\begingroup\$

Jelly, 10 bytes

Œp⁼Q$ÐfZQ€

Try it 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
\$\endgroup\$
  • \$\begingroup\$ It seems a bit disingenuous to claim 10 bytes when Jelly uses characters outside of latin1. Represented as UTF-8 the above sequence requires 16 bytes. \$\endgroup\$ – Chris Becke Aug 24 '16 at 7:03
  • 1
    \$\begingroup\$ @ChrisBecke Jelly has its own charset \$\endgroup\$ – Robin Gertenbach Aug 24 '16 at 8:06
  • \$\begingroup\$ And yet - if I try it online! - I need to send 16 bytes. \$\endgroup\$ – Chris Becke Aug 25 '16 at 5:30
  • \$\begingroup\$ @ChrisBecke Yes but if you download Jelly you would only have to write a 10-byte program. \$\endgroup\$ – Leaky Nun Aug 25 '16 at 6:21
  • \$\begingroup\$ And save it in a text file I cannot edit with anything other than Jelly? By that argument if Jelly compressed its program we should only count the compressed bytes? \$\endgroup\$ – Chris Becke Aug 25 '16 at 8:10
7
\$\begingroup\$

Pyth, 11 bytes

{MC{I#.nM*F

Try it 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
\$\endgroup\$
6
\$\begingroup\$

Haskell, 100 bytes

import Data.List
p z=map nub$transpose$filter(and.(flip$zipWith elem)z)$permutations[0..length z-1]
\$\endgroup\$
  • \$\begingroup\$ Nice solution! and.flip(zipWith elem)z is shorter \$\endgroup\$ – Damien Aug 26 '16 at 16:27
2
\$\begingroup\$

Actually, 27 bytes

Rd╗R`╜∙"♂i"£M╗`MX╜`;╔=`░┬♂╔

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 3, 101 99 bytes

Thanks to @TLW for -2 bytes

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

An anonymous function that takes input via argument of a list of lists and returns a list of sets.

How it works

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

Try it on Ideone

\$\endgroup\$
  • \$\begingroup\$ list(map(set, is shorter, I think \$\endgroup\$ – TLW Aug 23 '16 at 23:07
2
\$\begingroup\$

Mathematica, 46 bytes

Union/@Thread@Select[Tuples@#,DuplicateFreeQ]&
\$\endgroup\$
0
\$\begingroup\$

PHP, 245 231 bytes

131 117 for the cartesian product function, 114 for the other stuff

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?:[];}

I ran into memory issues on some of the test cases, with a recursive function for the cartesian product. Worked better with this generator class and function c($a){$b=[];foreach($a as$i)$b[]=new \ArrayIterator($i);return new CartesianProductIterator($b);}.
But my generator is shorter and does the same job.

The larger examples, however, result in an Internal Server Error (both with the iterator and the generator) after a while on my machine. Currently no time to check the server logs, unfortunately.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.