# Matrix Jigsaw Puzzle Pieces

(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 so all usual golfing rules apply, and the shortest code (in bytes) wins.
• Can the output actually be a list of the pieces? Or I/O not be done with strings but with matrices and integers (with -1 or a space representing an empty space, or absence of an element if possible)? – Erik the Outgolfer Jan 11 at 19:03
• Is it acceptable if the input is 1-based (doesn't contain zeros) and the output uses 0 as filler value? So each piece would be output with the rest of the values in the matrix set to 0 – Luis Mendo Jan 11 at 19:15
• Independent of my previous question: no other whitespace is permitted: not even trailing spaces to make all lines equal length? – Luis Mendo Jan 11 at 19:17
• @EriktheOutgolfer Absence of an element would be OK, since that's outputting just the "piece" itself. Outputting an entire matrix for each piece with -1 or some other value instead of nothing/whitespace wouldn't be OK, though. – AdmBorkBork Jan 11 at 19:18
• @AdmBorkBork Oh, so should the space (' ') be used in that case? – Erik the Outgolfer Jan 11 at 19:18

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

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

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

Ẏ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. • ẎQ=€ should do, although we need the pieces in ascending order, so 9Ż=€ (unless we must not include "non-existent pieces" in which case ẎQṢ=€) – Jonathan Allan Jan 12 at 20:20 • @JonathanAllan Fixed the issue, although I'm pretty sure 9Ż=€ won't work (I think "extraneous whitespace [...] are not allowed" extends to arrays as well, that's why I'm trimming). – Erik the Outgolfer Jan 12 at 21:24 • Yeah, that makes sense. – Jonathan Allan Jan 12 at 21:30 # Python 3, 271209206183176172 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 # Python 2, 173172 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. • @AdmBorkBork - Right, missed that criteria. Fixed now. – Chas Brown Jan 14 at 20:25 # 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! # 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' • You're allowed to specify the input format (e.g., as a list of lists, or as a space-separated paragraph) if it makes your code golfier. – AdmBorkBork Jan 14 at 13:46 # Retina, 75 bytes$
¶9
.-10{T9dd.$*;(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.

T9dd.$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.) • There is guaranteed to never be a "missing digit" if that makes your code shorter. – AdmBorkBork Jan 14 at 13:43 • @AdmBorkBork I don't think that would help. What would be more likely to help is not having to output the pieces in numerical order. Is that allowed? – Neil Jan 14 at 14:07 • No, that's half the challenge, otherwise it'd be too easy. ;-) – AdmBorkBork Jan 14 at 15:50 # 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. # 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}]])& # 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

# APL (Dyalog Unicode), 38 bytesSBCS

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

# 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

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. • @AdmBorkBork Overlooked that rule, fixed – Black Owl Kai Jan 15 at 18:30 # 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.