Matrix Jigsaw Puzzle Pieces

Question

(Randomly inspired by https://codegolf.meta.stackexchange.com/a/17272/42963)

Given a rectangular matrix of digits (i.e., 0 - 9), output the "pieces" of the matrix as if the digits are connected together forming a single piece, in ascending order by the digits. The pieces are guaranteed to connect only orthongonally -- no piece will connect diagonally. There will only ever be a maximum of 10 pieces (i.e., a 3 piece won't appear twice in the same matrix).

For example, given the matrix

0 1 1 1
0 0 1 2
3 3 2 2

the following are the pieces, and an example output:

0
0 0

1 1 1
  1

  2
2 2

3 3

Spacing is important to keep the shape of the pieces, but the pieces do not necessarily need interior spacing. The pieces themselves should somehow be made distinct in a consistent manner (e.g., a newline between pieces, making sure each is a different character, etc.). Additionally, extraneous whitespace (for example, trailing newlines or leading columns) are not allowed. For example, the following would also be valid:

0
00
111
 1
 2
22
33

or

#
##

###
 #

 #
##

##

But the following would not be (note the trailing spaces behind the 0s):

0      
0 0    

Rotations or reflections are also not allowed. For example, outputting

 1
111

for the above matrix is also invalid.

The matrix pieces may have holes, or be only a single element:

0 0 0 1
0 2 0 1
0 0 0 3

Or, the piece may be the whole matrix:

0 0 0
0 0 0

Here's a larger, more complicated test case:

1 1 1 1 1 2 2
3 4 4 4 2 2 2
5 5 4 4 2 0 0
5 6 6 6 6 7 7
5 6 8 8 6 6 7
9 6 6 6 7 7 7

And an example output:

00

11111

 22
222
2

3

444
 44

55
5
5

6666
6  66
666

 77
  7
777

88

9

Rules and I/O

• Input and output can be given by any convenient method.
• You can print it to STDOUT or return it as a function result.
• Either a full program or a function are acceptable.
• Leading whitespace to keep the shape (e.g., the "T" shape of the 1 in the example) is required, consistent whitespace to make the pieces distinct, and a single trailing newline at the end is allowed, but no other whitespace is permitted.
• You can safely assume that the pieces are numbered 0 to N contiguously, meaning that (for example) 3 wouldn't be skipped in a six-piece matrix.
• Standard loopholes are forbidden.
• This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Answer 1

05AB1E, 20 19 bytes

ZƒNQ2Fζʒà}}ε0Ü}0ð:,

-1 byte thanks to @Mr.Xcoder.

Outputs 2D lists of pieces (with 1 and space characters " ") per newline.

Try it online or verify all test cases or pretty-print all test cases.

Explanation:

Z              # Get the maximum digit of the (implicit) matrix-input (implicitly flattens)
 ƒ             # Loop in the range [0, max]:
  NQ           #  Check for each digit in the (implicit) matrix if it's equal to the index
    2F    }    #  Inner loop two times:
      ζ        #   Zip/transpose; swapping rows/columns
       ʒ }     #   Filter the inner lists by:
        à      #    Get the max of the list
               #  (so all rows/columns containing only 0s are removed)
  ε  }         #  Map the remaining rows:
   0Ü          #   Remove all trailing 0s
  0ð:          #  Then replace any remaining 0 with a space " "
     ,         #  And output the piece-matrix with a trailing newline

Answer 2

Haskell, 133 132 129 bytes

f x=[until(any(>"!"))(tail<$>)m|m<-[[until((>'!').last)init r|r<-[[last$' ':[s|s==n]|s<-z]|z<-x],any(>'!')r]|n<-['0'..'9']],m>[]]

Takes the matrix as a list of strings and returns a list of list of strings.

Try it online!

                                    -- example matrix: ["0111","0012","3322"] 
                                    --
[          |n<-[0..9]]              -- for each digit 'n' from '0' .. '9'
  [  |z<-x]                         --   for each line 'z' of the input matrix 'x'
   [      |s<-z]                    --     for each digit 's' of line 'z'
      last$' ':[s|s==n]             --       take 's' if 's'=='n', else a space
                                    --       now we have a list of 10 matrices where
                                    --       each matrix contains only the
                                    --       corresponding digit 'n' at it's original
                                    --       position and spaces for all other digits
                                    --       -> [["0   ","00  ","    "],[" 111","  1 ","    "],["    ","   2","  22"],["    ","    ","33  "],["    ","    ","    "],["    ","    ","    "],["    ","    ","    "],["    ","    ","    "],["    ","    ","    "],["    ","    ","    "]]
   [     |r<-[    ],any(>'!')r]     --     loop through rows 'r' and keep those with
                                    --     at least one non-space element
    until((>'!').last)init r        --     and remove trailing spaces
                                    --     -> [["0","00"],[" 111","  1"],["   2","  22"],["33"],[],[],[],[],[],[]]
   [     |m<-[   ],m>[]]            --   loop through matrices 'm' and keep only
                                    --   non-empty
    until(any(>"!"))(tail<$>)m      --   and remove common leading spaces
                                    --   -> [["0","00"],["111"," 1"],[" 2","22"],["33"]]

Answer 3

Jelly, 18 bytes

ẎQṢ=€ẸƇZ$⁺œr€ɗ€0o⁶

Try it online!

Returns a list of pieces, where 1 represents a part of a piece, and ' ' is padding. Trailing ' 's are removed.

Answer 4

Python 3, 271 209 206 183 176 172 191 bytes

lambda t:[[[*"".join(' #'[i==d]for i in r).rstrip()]for r in[w[min(r.index(d)for r in t if d in r):max(len(R)-R[::-1].index(d)for R in t if d in R)]for w in t if d in w]]for d in{*sum(t,[])}]

Try it online!

Edit: Some cleanup and -5 thanks to @Jonathan Frech.

Edit: -3 -26 once again thanks to @Jonathan Frech.

Edit: -7 again thanks to @Jonathan Frech.

Edit: +19: As noted by @nimi previously output had incorrect format.

---

Input is matrix as list of lists:

Input =  [[0, 1, 1, 1],
          [0, 0, 1, 2],
          [3, 3, 2, 2]]

Output is list of matricies:

Output = [[['#'],
           ['#', '#']],
          [['#', '#', '#'],
           [' ', '#']],
          [[' ', '#'],
           ['#', '#']],
          [['#', '#']]],

---

Ungolfed:

O = ' '
X = '#'

def digits(t):
    return {d for r in t for d in r}

def rows_with_digit(table, digit):
    return [row for row in table if digit in row]

def table_with_digit(table, digit):
    subtable = rows_with_digit(table, digit)
    left_most_column = min([row.index(digit) for row in subtable])
    right_most_column = max([len(row) - row[::-1].index(digit) for row in subtable])
    return [row[left_most_column:right_most_column] for row in subtable]

def format_table(table, digit):
    return [[X if i==digit else O for i in row] for row in table]

def f(table):
    D = digits(table)
    R = []
    for d in D:
        digit_table = table_with_digit(table, d)
        R.append(format_table(digit_table, d))    
    return R

Answer 5

Python 2, 173 172 165 bytes

s=input()
for i in sorted(set(sum(s,[]))):R=[''.join([' ',i][c==i]for c in r)for r in s if i in r];print'\n'.join(t[min(r.find(i)for r in R):t.rfind(i)+1]for t in R)

Try it online!

-15 bytes from an observation by nimi.

In program form, takes as input a list of lists of single characters; outputs by printing the pieces found using their character.

Answer 6

APL (Dyalog Unicode), 38 bytes^SBCS

Anonymous tacit prefix function. Takes a numeric matrix as argument and returns a list of lists strings. Each list of strings represents a piece with space-separated 1s. Leading and internal (but not trailing) spaces are spaces.

⊂{' +$'⎕R''↓⍕' '@~{⍉⍵⌿⍨∨/⍵}⍣2⊢⍺=⍵}¨∪∘,

Try it online!

∪∘, the unique elements of the ravel (flattened) matrix

⊂{…}¨ for each of those as ⍵, call the following function with the entire matrix as ⍺:

 ⍺=⍵ indicate where that piece's number is in the matrix

 ⊢ yield that (separates 2 from ⍺)

 {…}⍣2 apply the following function twice (⍵ is the Boolean matrix):

  ∨/ mask for rows with at least one 1 (lit. row-wise OR-reduction)

  ⍵⌿⍨ use that to filter the rows

  ⍉ transpose (so we do this on the columns too, then transpose back)

 ' '@~ replace with spaces at positions where not (i.e. where 0)

 ⍕ format as character matrix

 ↓ split into list of strings

 ' +$'⎕R'' PCRE replace trailing spaces (any number of spaces followed by a line-end) with nothing

Answer 7

C# (.NET Core), 258, 238 bytes

Without LINQ.

EDIT: Embodiment Of Ignorance pointing out better var declarations! Ty ty.

p=>{int j=0,o=0,l=0,x=p.GetLength(1),d=p.Length;while(j<d){int t=j/x,u=j++%x,z=p[t,u];o=z>o?z:o;l=z<l?z:l;}var s="";for(var m=l;m<=o;m++){j=0;while(j<d){int t=j/x,u=j++%x;s+=(p[t,u]==m?p[t,u]+"":" ")+(u==x-1?"\n":"");}s+="\n";}return s;};

Try it online!

Answer 8

Python 2, 291 bytes

import re
t=input()
a,b=t.split(),{c for c in t if' '<c}
for c in sorted((b,a)[int(max(a))==len(a)],key=int):s=re.sub(r'[^%s\s]'%c,' ',t).split('\n');print"\n".join(''.join(l[i]for i in sorted({i for l in s for i,j in enumerate(l)if j in c})if i<len(l)).rstrip()for l in s if l.strip())+'\n'

Try it online!

Expects a quote-delimited sting as input. A semi-ludicrous percentage of the code is dedicated to handling non-space-separated/non-space-padded input.

Un-golfed Explanation:

# built-in python regex handling.
import re
# get argument from STDIN
t=input()
# get elements which are whitespace separated, and all distinct non-whitespace characters
a,b=set(t.split()),{c for c in t if' '<c}
                # choose whichever set has the appropriate number of values based on its max element
                # for non-space separated inputs, this prevents values like '333' for 4-piece sets
                (b,a)[int(max(a))==len(a)]
# get elements in order by their integer value
# this will force the items to print in order, since sets are unordered
for c in sorted(..........................,key=int):
      # using regex substitute, replace any instance that DOESN'T match the current value or a whitespace with a space
      re.sub(r'[^%s\s]'%c,' ',t)
    # split replaced string into lines on line breaks
    s=...........................split('\n')
                # for each line in replaced input
                for l in s
                           # get the index and value of each item in line
                           for i,j in enumerate(l)
             # get distinct indexes which have a value that appears in the current piece
             {i ..................................if j in c}
    # get ordered list of distinct indexes
    a=sorted(...............................................)
                                                               # for each line in the replaced input
                                                               # only return values where line has non-whitespace values
                                                               for l in s if l.strip()
                           # get the value for each index that has a non-space value on other lines
                           # as long as that index exists (for non-space-padded inputs)
                           # this ensures that the spaces between values, if any, are removed
                           # there may still be trailing spaces
                           l[i]for i in a if i<len(l)
                   # join characters back into one string, and remove trailing whitespace
                   ''.join(..........................).rstrip()
    # join the lines back together with line breaks, and terminate with an extra line break
    # print output to screen
    print"\n".join(...................................................................)+'\n'

Answer 9

Retina, 75 bytes

$
¶9
.-10{T`9d`d`.$
*;(s`(\d)(?!.*\1$)
 
 +¶
¶
G`\d
/^\d|^$/m^+m`^.

.$
$&¶

Try it online! Explanation:

$
¶9

Append a digit to the input. This represents the loop counter. The newline simplifies the trailing whitespace removal.

.-10{

Inhibit default output and repeat exactly 10 times.

T`9d`d`.$

Advance the loop digit.

*;(

Output the result of the rest of the script but then restore the buffer.

s`(\d)(?!.*\1$)
 

Replace all digits that don't match the loop digit with spaces. (Because this uses a lookahead and there's nothing to look ahead at this point this also replaces the loop digit.)

 +¶
¶

Remove all trailing whitespace.

G`\d

Remove all blank lines.

/^\d|^$/m^+

Repeat as long as no line begins with a digit...

m`^.

... delete the first character on each line.

.$
$&¶

If there is anything left then append a newline to separate each shape from the next. (This is done to avoid stray newlines for missing digits.)

Answer 10

Charcoal, 43 bytes

ＷＳ⊞υιＦχ«≔Φυ№κＩιθ¿θ«ＵＴＦθ«Ｆκ«¿⁼λＩιλ→»Ｍ±Ｌκ¹»Ｄ⎚

Try it online! Link is to verbose version of code. Explanation:

ＷＳ⊞υι

Read the input into an array. (This could be removed if I used an ugly input format.)

Ｆχ«

Loop over the 10 digits.

≔Φυ№κＩιθ

Get the rows which contain those digits.

¿θ«

Check that the digit was in fact found (to prevent outputting spurious newlines).

ＵＴ

Turn off automatic padding.

Ｆθ«

Loop over the found rows.

Ｆκ«

Loop over each column...

¿⁼λＩιλ→»

... if the current input character equals the current loop digit then print it otherwise move the cursor right.

Ｍ±Ｌκ¹»

Move to the start of the next row. Using movement commands like this allows Charcoal to trim the output on both sides.

Ｄ⎚

Dump and clear the canvas ready for the next digit. This allows the different digits to have different amounts of trimming.

I tried a programmatic approach but that weighed in at 47 bytes, although it would also have been 43 bytes for a brief amount of time when Equals vectorised:

ＵＴＷＳ⊞υιＦχ«≔ΦＥυＥκ⁼μＩιΣκθＥθ⭆✂κ⌊Ｅθ⌕μ¹⁻Ｌκ⌕⮌κ¹¦¹⎇μι 

Try it online! Link is to verbose version of code. Explanation:

ＵＴ

Turn off automatic padding.

ＷＳ⊞υι

Read the input into an array.

Ｆχ«

Loop over the 10 digits.

≔ΦＥυＥκ⁼μＩιΣκθ

Compare each character with the input and build up a boolean array, but then filter out the rows with no matches.

Ｅθ⭆✂κ⌊Ｅθ⌕μ¹⁻Ｌκ⌕⮌κ¹¦¹⎇μι 

Loop over the remaining rows and slice from the earliest match in any row to the latest match in the current row, then mapping the boolean array back to digits or spaces, which are then implicitly printed as an array of strings.

Answer 11

Wolfram Language 101 bytes

There has got to be a much more efficient way to accomplish this.

(g=#;Column[Table[Grid@Map[Replace[#,Thread[Complement[u=Union@Flatten@g,{n}]->""]]&/@#&,g],{n,u}]])&

Answer 12

Perl 5, 97 bytes

$x=$_;for$i(0..9){$_=$x;y/ //d;s/(?!$i)./ /g;s/ *$//gm;s/^
//gm;s/^ //gm until/^(?! )/m;$\.=$_}}{

TIO

Explanation

-p0777                       # options to read whole intput and print special var by default

$x=$_;                       # save default var (input) into $x
for$i(0..9){                 # for $i in 0..9
    $_=$x;                   #   restore default var 
    y/ //d;                  #   remove all space char
    s/(?!$i)./ /g;           #   replace all char except $i by a space
    s/ *$//gm;               #   remove trailing space
    s/^\n//gm;               #   remove empty lines
    s/^ //gm until/^(?! )/m; #   remove leading space until there is no more
    $\.=$_                   #   append default var to output record separator
}
}{                           # trick with -p to output only reacord separator

Answer 13

Japt, 29 bytes

AÆ®®¥X ÑÃÃÕfx Õfx ®¬r0S x1
fl

Try it online!

Updated to comply with stricter output formatting.

Outputs as a list of pieces with each piece represented by a list of lines, using 2 as the filler character.

Explanation:

AÆ                            #For the numbers 0-9:
  ®®    ÃÃ                    # Map over each digit in the input:
    ¥X                        #  True if it equals the current number, false otherwise
       Ñ                      #  Multiply by 2 to turn the bool into a number
          Õfx                 # Remove columns that are all 0
              Õfx             # Remove rows that are all 0
                  ®           # For each remaining row:
                   ¬          #  Turn it into a string
                    r0S       #  Replace "0" with " "
                        x1    #  Trim spaces from the right
fl                            #Remove unused pieces

Answer 14

Python 3, 133 bytes

lambda s:[dedent(re.sub(" *$","",re.sub(f"[^{c}\\n]"," ",s),0,8)).strip("\n")for c in sorted(*s)[1:]]
from textwrap import*
import re

Try it online!

Takes a newline-seperated string, returns a list of newline-seperated strings. Uses textwrap.dedent to get rid of leading spaces.

Answer 15

Jelly, 19 bytes

ŒĠµŒṬZSƇ$⁺ị⁾# œr€⁶)

Try it online!

A monadic link taking the matrix as input and returning a list of one ragged list per piece. Footer displays this prettily, but I think output without that is consistent with rules of question.