16
\$\begingroup\$

Given a matrix of positive integers, output whether it's possible to generate it by starting with an empty1 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

\$\endgroup\$
1
  • \$\begingroup\$ Recommend adding a false test case that has an entire row or column of the same number. Right now a program that just tests for that property satisfies all the test cases. \$\endgroup\$ Jan 24 at 2:41

14 Answers 14

6
\$\begingroup\$

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.
\$\endgroup\$
0
5
\$\begingroup\$

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

enter image description here

\$\endgroup\$
4
\$\begingroup\$

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)
})
\$\endgroup\$
0
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ Note: I've seen the close votes but since they were not explained I chose to ignore them. \$\endgroup\$
    – loopy walt
    Jan 22 at 12:01
  • \$\begingroup\$ Since this is [decision-problem], would it be possible to leave out the >0 at the end (Attempt This Online!) \$\endgroup\$
    – The Thonnu
    Jan 22 at 13:11
  • \$\begingroup\$ @TheThonnu I'm not sure, actually. Many askers ask for two consistent values. There may, however, be an exception if the inconsistent values are all truthy and all falsy.. \$\endgroup\$
    – loopy walt
    Jan 22 at 13:55
  • \$\begingroup\$ Here is our meta consensus about decision-problem output \$\endgroup\$
    – pxeger
    Jan 22 at 16:53
  • \$\begingroup\$ Should one count the additional bytes to import the NumPy library? \$\endgroup\$ Jan 22 at 22:29
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ 7 \$\endgroup\$
    – emanresu A
    Jan 22 at 18:32
  • \$\begingroup\$ Actually 6 with the Jelly answer's I/O method. \$\endgroup\$
    – emanresu A
    Jan 22 at 18:33
  • \$\begingroup\$ @emanresuA It doesn't terminate for [[1,2],[3,4]] \$\endgroup\$
    – AndrovT
    Jan 22 at 18:47
  • \$\begingroup\$ Ah, because of the transpose :| You can still get 7 using the Jelly answer's I/O method of empty/nonempty list \$\endgroup\$
    – emanresu A
    Jan 22 at 18:53
3
\$\begingroup\$

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!

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

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

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

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 3 small golfs bring this down to 95 bytes \$\endgroup\$
    – Wheat Wizard
    Jan 22 at 14:20
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I've often been jealous of 05AB1E's 'only 1 is truthy', which seems to frequently save bytes compared to other languages... so it's somehow darkly satisfying to see that it can also be a disadvantage here... \$\endgroup\$ Jan 23 at 11:16
1
\$\begingroup\$

Charcoal, 38 bytes

⊞υθFυF²«≔E⌊ιEι§νμι≔Φι⁻⌈λ⌊λκ¿⁻ικ¿κ⊞υκP¹

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:

⊞υθFυ

Start a breadth-first search with the original array.

F²«

Loop over the transpose as well as the array.

≔E⌊ιEι§νμι

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.

P¹

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

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ My solution is 98 bytes \$\endgroup\$
    – l4m2
    Jan 22 at 14:31
  • \$\begingroup\$ @l4m2 Looks better now. \$\endgroup\$
    – Arnauld
    Jan 22 at 17:17
  • \$\begingroup\$ My solution revealed \$\endgroup\$
    – l4m2
    Jan 22 at 17:23
  • \$\begingroup\$ Ugh. I just stopped golfing below 98 bytes, not 89! ;-) \$\endgroup\$
    – Arnauld
    Jan 22 at 17:25
  • \$\begingroup\$ It was 98 and I later do extra golf \$\endgroup\$
    – l4m2
    Jan 22 at 17:28
1
\$\begingroup\$

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?
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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