21
\$\begingroup\$

Write a program or function that takes in a multiline string of 0's and 1's. No other characters will be in the string and the string will always be rectangular (all lines will have same number of characters), with dimensions as small as 1×1, but otherwise the 0's and 1's may be arranged arbitrarily.

You may assume the string has an optional trailing newline, and if desired you may use any two distinct printable ASCII characters in place of 0 and 1.

Print or return a truthy value if all of the path connected regions of both 0's and 1's in the string are solid rectangles, else output a falsy value.

A path connected region of 0's means that from any one 0 in the region, all the other 0's can be reached by only moving up, down, left and right to other 0's (and not moving diagonally, not moving to any 1, and not moving outside the string bounds). The same idea applies to 1 path connected regions.

A solid rectangle of 0's means the entire area of the rectangle is filled with 0's and no 1's. The same idea applies to 1 solid rectangles.

The shortest code in bytes wins. Tiebreaker is earlier answer.

(Note that the string does not wrap around with toroidal boundary conditions.)

Examples

1) This input string has 3 path connected regions (2 for 0 and 1 for 1). Only the bottom right 00 region is a solid rectangle though, so the output would be falsy.

0011 0111 0100

2) This input string has 4 path connected regions (2 for both 0 and 1). All of them are solid rectangles so the output would be truthy.

0011 0011 1100

3) This input has 2 path connected regions, but only one of them is a solid rectangle, so the output would be falsy.

00000000 01111110 00000000

4) This input has only 1 path connected region and is trivially a solid rectangle, so the output is truthy.

11111111 11111111 11111111

Test Cases

A T just below the input string means truthy, F means falsy.

0 T 1 T 00 T 01 T 10 T 11 T 0000000 T 1111111 T 011100100100101100110100100100101010100011100101 T 00 11 T 01 10 T 01 11 F 00 01 F 11 11 T 110 100 F 111 000 T 111 101 111 F 101 010 101 T 1101 0010 1101 0010 T 1101 0010 1111 0010 F 0011 0111 0100 F 0011 0011 1100 T 00000000 01111110 00000000 F 11111111 11111111 11111111 T 0000001111 0000001111 T 0000001111 0000011111 F 0000001111 1000001111 F 1000001111 1000001111 T 1110100110101010110100010111011101000101111 1010100100101010100100010101010101100101000 1110100110010010110101010111010101010101011 1010100100101010010101010110010101001101001 1010110110101010110111110101011101000101111 F
Improve this question
\$\endgroup\$
0

9 Answers 9

Reset to default
16
\$\begingroup\$

Jelly, 11 10 bytes

ṣ⁷^2\⁺€FS¬

Massive thanks to @Dennis for golfing this one down to half its original size (via undocumented features).

Try it online! Note that the triple quotes are for a multiline string.

Explanation

The basic algorithm is: return true iff every 2x2 subgrid has an even number of 1s (or, equivalently, 0s).

It's clear why an odd number of 1s can't work, since we would have one of the following:

10 01 00 00 01 10 11 11 00 00 01 10 11 11 10 01

Note that the first 4 are rotations of the same thing, and ditto for the last 4. The reflex angle can't be part of a rectangle, hence why it would be invalid.

In other words, all 2x2 subgrids must be one of the following:

00 00 11 01 10 01 10 11 00 11 00 01 10 10 01 11

which, if we look at the boundaries, can be imagined as the following "puzzle pieces":

 ___ ___ ___ ___ | | | | | | | | | | | | | | | |---| |-|-| |___| |_|_| |___| |_|_|

And try forming a non-rectangle with those puzzle pieces :) (whilst having the ends match up)

The actual implementation is thus:

ṣ⁷ Split input by newlines to give rows ^2\ Taking overlapping sets of 2 rows at a time: accumulate rows by XOR Note that strings cast to integers automatically for bitwise operators ⁺€ Repeat the previous link (⁺), on each (€) element in the resulting array F Flatten the array S Sum (effectively reducing by OR) ¬ Logical negation of the result

For example, for the input

100 010 000 101

we have:

 ṣ⁷: ["100", "010", "000", "101"] ^2\: [[1, 1, 0], [0, 1, 0], [1, 0, 1]] (e.g. first entry is "100" ^ "010") ^2\€: [[0, 1], [1, 1], [1, 1]] (e.g. the first entry is [1^1, 1^0] - this gives the counts of 1s in each subgrid, mod 2) F: [0, 1, 1, 1, 1, 1] S: 5 (this gives the number of invalid 2x2 subgrids, which is indeed all but the top left) ¬: 0
Improve this answer
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Can you please go document the features you used? If people do that then documentation will happen! \$\endgroup\$ Commented Apr 5, 2016 at 6:52
  • \$\begingroup\$ Do you need to flatten? \$\endgroup\$ Commented Apr 5, 2016 at 6:54
  • \$\begingroup\$ @CatsAreFluffy If you don't flatten, Jelly tries to sum a list of vectors and you get a vector as a result \$\endgroup\$ Commented Apr 5, 2016 at 6:55
  • \$\begingroup\$ Just sum and sum-it's better! \$\endgroup\$ Commented Apr 5, 2016 at 6:59
  • 4
    \$\begingroup\$ "Undocumented features" -- aha! So that's how Dennis outgolfs everyone! :D \$\endgroup\$ Commented Apr 5, 2016 at 12:54
12
\$\begingroup\$

Ruby, 76

->s{j=!r=1 s.lines{|t|i=t.to_i(2) j&&r&&=(j^i)%t.tr(?0,?1).to_i(2)<1 j=i} r}

In any grid composed entirely of rectangles, each line must be identical to the line before, or have all bits flipped from 0 to 1 and vice versa.

This is easy to prove. Take a piece of paper and draw arbitrary vertical and horizontal lines all the way across it. Now colour the rectangles using only 2 colours. You will end up with a distorted checkerboard, where all the colours flip at each line.

Want to draw rectangles with lines only part way across? try deleting a segment of any of your lines. You will now need more than 2 colours to colour your design, because you will have points where 3 rectangles meet (2 corners and an edge.) Such designs are therefore irrelevant to this question.

I'm surprised answers so far haven't noticed this.

I think this algorithm should be a lot shorter in some other language.

Ungolfed in test program

f=->s{ j=!r=1 #r = truthy, j=falsy s.lines{|t| #for each line i=t.to_i(2) #i = value of current line, converted to a number in base 2 (binary) j&& #if j is truthy (i.e this is not the first line) r&&=(j^i)%t.tr(?0,?1).to_i(2)<1 #XOR i with the previous line. Take the result modulo (current line with all 0 replaced by 1) #if the result of the XOR was all 0 or all 1, the modulo == zero (<1). Otherwise, it will be a positive number. j=i} #j = value of current line (always truthy in ruby, even if zero) r} #return 1 or true if all the modulo calculations were zero, else false. #text to print after test case to check answer is as desired T='T ' F='F ' #test cases puts f['0'],T puts f['1'],T puts f['00 '],T puts f['01'],T puts f['10'],T puts f['11 '],T puts f['0000000'],T puts f['1111111'],T puts f['011100100100101100110100100100101010100011100101'],T puts f['00 11'],T puts f['01 10'],T puts f['01 11'],F puts f['00 01'],F puts f['11 11 '],T puts f['110 100'],F puts f['111 000'],T puts f['111 101 111'],F puts f['101 010 101 '],T puts f['1101 0010 1101 0010'],T puts f['1101 0010 1111 0010'],F puts f['0011 0111 0100 '],F puts f['0011 0011 1100'],T puts f['00000000 01111110 00000000'],F puts f['11111111 11111111 11111111'],T puts f['0000001111 0000001111'],T puts f['0000001111 0000011111'],F puts f['0000001111 1000001111'],F puts f['1000001111 1000001111'],T puts f['1110100110101010110100010111011101000101111 1010100100101010100100010101010101100101000 1110100110010010110101010111010101010101011 1010100100101010010101010110010101001101001 1010110110101010110111110101011101000101111'],F
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I bet using s.scan(/^?.*\n/) would help save bytes. \$\endgroup\$ Commented Apr 5, 2016 at 17:37
5
\$\begingroup\$

Jelly, 7 bytes

ṣ⁷µ=ḢZE

This uses the same algorithm as @LevelRiverSt's Ruby answer. The actual algorithm fits in the last 4 bytes; the first 3 bytes are required to parse the input format.

Try it online!

How it works

ṣ⁷µ=ḢZE Main link. Argument: t (string) ṣ⁷ Split t at linefeeds.. µ Begin a new, monadic link. Argument: A (list of strings) Ḣ Pop the first string of A. = Compare all other strings in A with the first. = compares characters, so this yields a list of Booleans for each string. For a truthy input, all pairs of lines now have been transformed in lists of only 1's or only 0's. That means all columns must be equal. Z Zip; transpose rows with columns. E Check if all rows (former columns) are equal to each other.
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Snails, 20 bytes

!{to{\0w`3\1|\1w`3\0

Prints the area of the grid if there isn't a 2x2 square with 3 zeroes and a one or 3 ones and a zero, or 0 if such a 2x2 square exists.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

MATL, 12 bytes

Ybc2thYCs2\~

Same algorithm as @sp3000's great answer.

To allow multiline input, MATL needs the row char array (string) to be explicitly built using character 10 for newline. So the input of the four examples are (note that [] is concatenation, so each of these is a row array of chars):

['0011' 10 '0111' 10 '0100'] ['0011' 10 '0011' 10 '1100'] ['00000000' 10 '01111110' 10 '00000000'] ['11111111' 10 '11111111' 10 '11111111']

and the last three test cases are

['0000001111' 10 '1000001111'] ['1000001111' 10 '1000001111'] ['1110100110101010110100010111011101000101111' 10 '1010100100101010100100010101010101100101000' 10 '1110100110010010110101010111010101010101011' 10 '1010100100101010010101010110010101001101001' 10 '1010110110101010110111110101011101000101111']

Truthy output is an array containing only ones.

Try it online!

Explanation

This uses the fact that the parity of chars '0' and '1' is the same as that of numbers 0 and 1, so there's not need to convert from char to the digit it represents,

Yb % split implicit input by whitespace. Gives a cell array c % concatenate cell contents into 2D char array 2th % push array [2 2] YC % get 2×2 sliding blocks and arrange as columns s % sum of each column 2\ % modulo 2 of each sum ~ % negate. Implicit display
Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Input needs to be a string \$\endgroup\$ Commented Apr 5, 2016 at 12:25
  • \$\begingroup\$ @HelkaHomba MATL doesn't allow multiline string input... The input would have to be a row array of the form ['first line' 10 'second llne'], where 10 is ASCII for newline. Is that acceptable? \$\endgroup\$ Commented Apr 5, 2016 at 12:31
  • \$\begingroup\$ @HelkaHomba I've used that in the updated answer. Alternatively, can space be used instead of newline? First example would be string '0011 0111 0100' \$\endgroup\$ Commented Apr 5, 2016 at 12:40
  • \$\begingroup\$ @LuisMendo I appreciate the thought, but I think the Ruby answer might actually be golfier in general here :) \$\endgroup\$ Commented Apr 5, 2016 at 13:01
  • \$\begingroup\$ @Sp3000 Oh, I hadn't seen that one. Very clever too \$\endgroup\$ Commented Apr 5, 2016 at 14:16
2
\$\begingroup\$

JavaScript (ES6), 69 bytes

s=>!s.split` `.some((t,i,u)=>[...t].some((v,j)=>v^t[0]^u[0][j]^s[0]))

I believe that the path connectedness rectangle criterion is equivalent to requiring that given any four points that form the corners of an arbitrary rectangle that there is an even number of 1s. Note that the parity of the rectangle (0, b), (x, y) is the same as (0, b), (a, y) ^ (a, b), (x, y) so I only have to check those rectangles whose top left corner is at (0, 0). Also by De Morgan's laws, !.some() is the same as .every(!) which saves me a couple of bytes.

Edit: I notice that the Jelly solution checks the parity of the corners of all 2×2 rectangles, which can be shown to be equivalent.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ almost 7 times, but +1 \$\endgroup\$ Commented Apr 5, 2016 at 9:59
2
\$\begingroup\$

JavaScript (ES6), 79

Same algorithm of Jelly answer from @Sp3000 (and happy not having to prove it works). Just 8 times longer

s=>[...s].every((x,i)=>[++i,i+=s.search` `,i+1].some(p=>!(x^=p=s[p],p>` `))|!x)

Less golfed

s=>[...s].every((x,i)=> // repeat check for every sub square [++i, // array of position for next char in row i+=s.search`\n`, i+1] // and 2 chars at same column in next row .some(p=> // for each position !( x^=s[p], // xor current value with value at position p s[p]>`\n` // true if value at position p is valid ) // the condition is negated ) // if any value scanned is not valid, .some return true // else, we must consider the check for current square | !x // x can be 0 or 1, to be valid must be 0 )

Test suite

f=s=>[...s].every((x,i)=>[++i,i+=s.search` `,i+1].some(p=>!(x^=p=s[p],p>` `))|!x) testData=` 0 T 1 T 00 T 01 T 10 T 11 T 0000000 T 1111111 T 011100100100101100110100100100101010100011100101 T 00 11 T 01 10 T 01 11 F 00 01 F 11 11 T 110 100 F 111 000 T 111 101 111 F 101 010 101 T 1101 0010 1101 0010 T 1101 0010 1111 0010 F 0011 0111 0100 F 0011 0011 1100 T 00000000 01111110 00000000 F 11111111 11111111 11111111 T 0000001111 0000001111 T 0000001111 0000011111 F 0000001111 1000001111 F 1000001111 1000001111 T 1110100110101010110100010111011101000101111 1010100100101010100100010101010101100101000 1110100110010010110101010111010101010101011 1010100100101010010101010110010101001101001 1010110110101010110111110101011101000101111 F` console.log=x=>O.textContent+=x+'\n' testData.split('\n\n').forEach(t=>{ var k=t.slice(-1)=='T', r=f(t.slice(0,-1)) console.log(t+' '+r+ (k==r?' OK\n':' KO\n')) }) 
<pre id=O></pre>

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Now 8 times longer! \$\endgroup\$ Commented Apr 5, 2016 at 9:15
1
\$\begingroup\$

Grime v0.1, 31 bytes

E=\0+|\1+ N=.+&E! e`(E/N|N/E)#!

Prints 1 for match and 0 for no match. Try it online!

Explanation

Grime is my 2D pattern matching language. I did modify it today, but only to change the character of a syntax element (` instead of ,), so it doesn't affect my score.

I'm using a similar approach to that of Sp3000: an input is falsy if it contains a 2×N rectangle whose one row contains both 0 and 1, and the other row does not.

E= Define a nonterminal E, which matches \0+| a horizontal run of one or more 0s, OR \1+ a horizontal run of one or more 1s. N= Define a nonterminal N, which matches .+ a horizontal run of one or more characters, &E! which is NOT matched by E (so contains both 0 and 1). e` Match entire input to this pattern: ! not # contains (E/N|N/E) E on top of N, or N on top of E
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 64 bytes

s=>(a=s.split` `).every(l=>l==a[0]|l==a[0].replace(/./g,n=>n^1))

Based on @LevelRiverSt's observation that each line must either be the same or the opposite of the first.

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.