Painting with Line Filler

Question

Given a matrix of positive integers, output whether it's possible to generate it by starting with an empty¹ matrix of the same dimensions and repeatedly filling a whole row or a whole column with the same value, overwriting any values already written.

Example

The following matrix:

$$\begin{pmatrix}1&1&1\\2&3&4\\2&3&4\end{pmatrix}$$

Can be obtained with the following steps:

$$ \begin{pmatrix}2&0&0\\2&0&0\\2&0&0\end{pmatrix}\rightarrow \begin{pmatrix}2&3&0\\2&3&0\\2&3&0\end{pmatrix}\rightarrow \begin{pmatrix}2&3&4\\2&3&4\\2&3&4\end{pmatrix}\rightarrow \begin{pmatrix}1&1&1\\2&3&4\\2&3&4\end{pmatrix} $$

Test cases

[[1,1,1,1,1],
 [2,3,4,5,6],
 [2,3,4,5,6]] => true

[[1,1,1,1,1],
 [2,3,4,1,6],
 [2,3,4,1,6]] => true

[[1,1,1,1,6],
 [2,3,4,1,6],
 [2,3,4,1,6]] => true

[[1,1],
 [1,1]] => true

[[1,2],
 [2,1]] => false

[[1,2],
 [3,4]] => false

[[1,1,2],
 [4,5,2],
 [4,3,3]] => false

[[1,2,4],
 [2,1,4],
 [3,3,3]] => false

Shortest code in each languages win.

^{1 You can assume it is initially filled with zeros}

Answer 1

Haskell + hgl, 21 bytes

ø<<yyc$jn m$tx<fn lq

Attempt This Online!

Explanation

The algorithm employed here repeatedly removes all rows of equal elements, removes all columns of equal elements, until we reach a fixed point where additional operations stop changing things.

If that fixed point is the empty list we return True otherwise False.

• lq determines if all elements of a list are equal.
• fn lq takes a list of lists and filters out all rows of equal elements.
• tx transposes a list.
• jn m takes a function and composes it with itself.
• jn m$tx<fn lq takes a list of lists removes all constant rows, transposes it to remove all constant columns and transposes back.
• yyc repeats an operation until it reaches a fixed point
• ø determines if a list is empty

Alternate version, 21 bytes

ø<<yyc$tx<fn lq<.<tx

Reflection

It's really nice to see yyc paying off already. The weak point in this answer is really with the glue. We have all the right components, but we waste a couple bytes putting it together.

• jn could use an infix. We already have fjn, so I don't know why there isn't an infix. Even if it's 3 bytes it would save here if it had the right precedence.
• jn m is a really expensive way to compose a function with itself. This should be a built in operator, probably 2 bytes long. It would save 2 bytes here.
• The composition operator we really want is something like f<|<g=f<g<f<g, which alternates two functions back and forth. We have the similar "sandwich compose" <.< which is useful in the alternate answer, but this other operator is probably worth having. With this we would save 3 bytes.
• It might be worth having a stronger version of yyc which stops when there is any repeated value. With this we could do away with the whole double compose and just write ø<<yyC$tx<fn lq.
• We have column map with mC it might be worthwhile implementing a column filter.
• tx could be an Iso.

Answer 2

Nibbles, 6.5 bytes (13 nibbles)

/\`.$|`'$>>=~

Returns truthy (nonempty list) if the matrix cannot be 'painted with lines', falsy (empty list) if it can.

/\`.$|`'$>>=~
  `.            # iterate while unique
    $           # (starting with input):
     |          #   filter 
      `'        #   the transpose of
        $       #   the result so far
           =~   #     by groups of its identical elements 
         >>     #     without the first group
                #     (so: all elements equal => empty list = falsy
                #          different elements => nonempty list = truthy)
 \              # reverse the list of results
/               # and return the first element
                # (which will be an empty list if the matrix 
                # can be 'painted with lines', or nonempty list
                # if it cannot).      

Answer 3

Rust, 436 280 bytes

|a:&[&[u8]]|f(&|c,d|a[c][d],a.len(),a[0].len());fn f(a:&dyn Fn(usize,usize)->u8,b:usize,c:usize)->bool{b<1||c<1||h(a,b,c)||h(&|e,f|a(f,e),c,b)}fn h(a:&dyn Fn(usize,usize)->u8,b:usize,c:usize)->bool{(0..b).any(|x|(0..c).all(|y|a(x,y)==a(x,0))&&f(&|d,e|a(d-(d>x)as usize,e),b-1,c))}

Attempt This Online!

Explanation

The basic idea is we check if there is at least one row or column with all elements the same, then recurse over the remaining rows and columns.

Since transposing and editing arrays is a bit tricky in rust instead we pass callback functions that can represent transformations on the original matrix.

// This function wraps the main program, converting our array into a function that will return the array position from a coordinate postion
let g = |a: &[&[u8]]| f(&|c, d| a[c][d], a.len(), a[0].len());
// f performs the transposition. Returns true if the array is empty, or if h(a), or h(a) transposed. b and c are the size of the array.
fn f(a: &dyn Fn(usize, usize) -> u8, b: usize, c: usize) -> bool {
    b < 1 || c < 1 || h(a, b, c) || h(&|e, f| a(f, e), c, b)
}
// h is the core of the function. Check if there is at least one row that is all equal and that f(the remaining matrix)
fn h(a: &dyn Fn(usize, usize) -> u8, b: usize, c: usize) -> bool {
    (0..b).any(|x| {
    (0..c).all(|y| a(x, y) == a(x, 0)) && f(&|d, e| a(d - (d > x) as usize, e), b - 1, c)
})

Answer 4

R, 71 bytes

f=\(m,n=o,o=sum(m|1))`if`(n,f(t(m[,apply(m,2,\(l)any(l-l[1]))]),n-1),o)

Attempt This Online!

Returns truthy (nonzero value) if the matrix cannot be 'painted with lines', falsy (zero) if it can.

Performs n (=number of elements of matrix) iterations of removing all-the-same columns and transposing, and outputs the number of elements remaining at the end.
Since at least one row or column of a paintable-with-lines matrix must be all-the-same at the start, this number of iterations is always enough to check paintability.

Answer 5

Python + NumPy, 64 bytes

f=lambda A,c=2:f(A[x].T,c-all(x))if c*any(x:=A.ptp(1)>0)else c>0

Attempt This Online!

As @TheThonnu points out per meta consensus (thanks @pxeger for sharing the exact link in the comments) this can be 62 bytes: simply drop the last two characters.

Answer 6

Jelly, 7 bytes

EÐḟZ$ÐL

A monadic Link that accepts a matrix and yields an empty list if possible (falsey) or a non-empty list if not (truthy).

Try it online!

How?

EÐḟZ$ÐL - Link: matrix, M
     ÐL - loop while distinct, applying:
    $   -   last two links as a monad - f(current):
 Ðḟ     -     filter discard those for which:
E       -       all equal?
   Z    -     transpose

Answer 7

Vyxal, 7 bytes

≬~≈F∩İ÷

Try it Online!

-1 byte: changed output method (thanks to @emanresuA)

Outputs an empty list if it's possible or a non-empty list if not.

≬        # three element lambda:
 ~≈      #   filter by: are all elements equal
   F     #   remove elements of a that are in b
    ∩    #   transpose
     İ   # apply function while results are unique, collecting results
      ÷  # push each item to stack

Answer 8

PARI/GP, 55 bytes

f(a)=g(a)||g(a~)
g(a,i)=!a||[#Set(c)<=f(a[,^i++])|c<-a]

Attempt This Online!

---

PARI/GP, 59 bytes

f(a)=if(a!=b=g(g(a)),f(b),!a)
g(a)=Mat([c|c<-a~,#Set(c)>1])

Attempt This Online!

Answer 9

JavaScript (Node.js), 89 84 bytes

f=m=>m<(m=m.map(u=x=>x.map((y,j)=>x.some(v=>v-y)&m.some(v=>v[j]-y)?u=y:f)))?f(m):u>f

Try it online!

Notice that only change is (number) => m=>m<m.ma..., so the first change makes string larger

Answer 10

Haskell, 94 bytes

e=[]:e
s(a:b)=all(==a)b
g m=m==[]||any s m&&p(filter(not.s)m)
p m=g m||g(foldr(zipWith(:))e m)

Try it online!

Haskell, 98 bytes

import Data.List
s=(<2).length.nub
g m=all s m||any s m&&p(filter(not.s)m)
p m=g m||g(transpose m)

Try it online!

Answer 11

05AB1E, 10 (or 7) bytes

Δ2FøʒË≠]˜P

Outputs a 05AB1E truthy/falsey result (1 if truthy; any other positive integer if falsey).

Try it online or verify all test cases.

Could be 7 bytes by outputting an empty list for truthy and non-empty matrix for falsey, even though both are considered falsey in terms of 05AB1E booleans, by removing the final three bytes:

Δ2FøʒË≠

Try it online or verify all test cases.

Explanation:

Δ        # Loop until the result no longer changes:
 2F      #  Inner loop 2 times:
   ø     #   Zip/transpose the matrix; swapping rows/columns
         #   (which will use the implicit input-matrix in the very first iteration)
    ʒ    #   Filter this matrix of rows by:
     Ë≠  #    Check that all values in the row-list are NOT equal
]        # Close the filter, loop, and changes-loop
 ˜       # Flatten the remaining list
  P      # Take the product (1 for an empty list; or a positive integer if not empty†)
         # (after which the result is output implicitly)

† Note that the matrix can never contain just 1s at this point, since it would have been reduced further.

Answer 12

Charcoal, 38 bytes

⊞υθＦυＦ²«≔Ｅ⌊ιＥι§νμι≔Φι⁻⌈λ⌊λκ¿⁻ικ¿κ⊞υκＰ¹

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean i.e. - if the array can be painted, nothing if not. Explanation:

⊞υθＦυ

Start a breadth-first search with the original array.

Ｆ²«

Loop over the transpose as well as the array.

≔Ｅ⌊ιＥι§νμι

Transpose the array.

≔Φι⁻⌈λ⌊λκ

Remove rows of identical elements.

¿⁻ικ

If this results in a smaller array, then:

¿κ⊞υκ

If this array is not empty then add it to the list of arrays to search.

Ｐ¹

But if it is empty then output that it can be painted.

Answer 13

JavaScript (ES6),  112  95 bytes

Returns a Boolean value.

f=m=>m+''==(m=(g=a=>a.filter((v,x)=>new Set(v.at?v:m.map(r=>r[x])).size>1))(m.map(g)))?m<1:f(m)

Attempt This Online!

Commented

f = m =>               // f is a recursive function taking the input matrix m[]
m + '' == (            // compare the current version of m[] with ...
  m = (                // ... the updated one
    g = a =>           // g is a helper function taking an array a[]:
    a.filter((v, x) => //   for each entry v at position x in a[]:
      new Set(         //     turn into a set:
        v.at ?         //       if v is an array:
          v            //         use v directly
        :              //       else:
          m.map(r =>   //         extract the x-th column from m[]
            r[x]       //   
          )            //   
      ).size > 1       //     remove if there's less than 2 distinct values
    )                  //   end of filter()
  )(m.map(g))          // invoke g on each row of m[] and then on the result
) ?                    // if m[] was not updated:
  m < 1                //   return true if m[] is empty, false otherwise
:                      // else:
  f(m)                 //   try to remove more rows or columns

Answer 14

Factor + combinators.extras, 62 bytes

[ [ [ [ all-eq? ] reject flip ] twice ] to-fixed-point { } = ]

Attempt This Online!

• [ ... ] to-fixed-point Call [ ... ] on the input until it stops changing
• [ ... ] twice Call [ ... ] twice
• [ all-eq? ] reject Remove the rows with numbers that are all equal
• flip Transpose
• { } = Is it empty?