Verifying a horizontal ASCII pet snake

Recently there have been a couple of ASCII pet snake challenges (e.g. here)

            0 0
0        0 0 000
00 0     00       000 0      0
000 0            0 0   00
0                000


This challenge is to take a randomly generated horizontal pet snake (height of five lines, length of 30), and verify that :

• Each column has only one 0
• Each 0 is "connected" to the 0 before and after it (vertically spaced by 0 or 1 line only)

Final output can be true or 1 if the snake is valid, or false or 0 if the snake is invalid

Edit—Clarification

Assume the input:

• Is a string
• Contains only ' ', '0', and '\n'
• Has exactly 30 characters each line
• Has exactly 5 lines

I.e. verify whether the snake is connected, and that there are no stray chars. No need to validate the "canvas" that the snake is printed on.

• Hi and welcome to PPCG :) This is a good challenge for a first post, but you probably want to add some more test cases that catch exceptional snakes. You also will probably want to decide if the snake has to be represented by zeros or can be any character. In the future, please consider using the sandbox. Good luck :) – FryAmTheEggman Feb 22 '18 at 1:52
• Is this taken as a Sting? Or can it be input as a 2d array? – JSchiff Feb 22 '18 at 1:56
• Are we guaranteed that the input consists of 0's and spaces? That every line has a length of 30? That there are 5 lines? – xnor Feb 22 '18 at 4:57
• Since this is a decision-problem how about truthy/falsey rather than true/false? – Jonathan Allan Feb 22 '18 at 8:15
• @JSchiff I'm sure a snake Bytes? – MarioDS Feb 22 '18 at 8:41

JavaScript (ES2018), 62 54 bytes

s=>!/0(.{30}|.{60,62}(.{31})*)0|( .{30}){4} /s.test(s)


Input is a single string:

• without trailing new line
• contain only space, '0', and '\n'
• 30 characters each line, 5 lines, 154 character in total

Flag s means a dot match anything (including '\n'). This feature currently supported by Chrome 63+, Opera 50+, Safari 11.1+, based on compat-table. You may test this function with these supported browser. You will get an exception when loading the page if your browser do not support this feature.

How it works:

• No column with no 0:
• do not match /( .{30}){4} /
• No two 0s in one column:
• do not match /0.{30}(.{31})*0/
• No 0 not connect to its neighbors:
• do not match /0.{60}(.{31})*0/, /0.{62}(.{31})*0/

Merge all these regex, and you will finally got this one.

f =

s=>!/0(.{30}|.{60,62}(.{31})*)0|( .{30}){4} /s.test(s)
<textarea id=i style="width:100%;height:100px">            0 0
0        0 0 000
00 0     00       000 0      0
000 0            0 0   00
0                000   </textarea>
<button onclick="o.value=f(i.value.slice(0,154))">Validate</button>
Result: <output id=o></output>

Thanks to Martin Ender point out that do a single ! operator may save 8 bytes.

SnakeEx, 51 bytes

This is obviously the right language for the task. :^D

s:({c<L>}{c<R>}0[(<R> <L>)(<L> <R>)_?])%{30}
c:0 *$ Matches the entire input if it is a valid snake; fails to match if it's not. Try it here! Explanation SnakeEx is a 2-D pattern matching language. A program consists of a list of definitions for "snakes," which crawl around the input matching characters, changing directions, and spawning other snakes. In our program, we define two snakes, s and c. We'll start with c because it's simpler. Its definition is 0 *$, which should be quite readable if you know regex: match 0, followed by zero or more spaces, followed by the edge of the grid. The main catch here: this matching can proceed in any direction. We're going to use c both upward and downward from the snake, to verify that there are no extra 0s in each column.

Now for the main snake, s. It takes the form (...)%{30}, which means "match the contents of the parentheses 30 times"--once for each 0 in the snake. So far, so good. What goes inside the parentheses?

{c<L>}


This spawns a new c snake, turned left 90 degrees. The direction is relative to the s snake's direction, so the new snake moves toward the top of the grid (the main snake is moving toward the right). The c snake checks that the current grid cell is a 0 and that every cell above it is a space. If it fails, the whole match fails. If it succeeds, we continue with

{c<R>}


which does the same thing, only turned right (toward the bottom of the grid).

Note that these spawns don't affect the position of the match pointer in the main snake. They're a bit like lookaheads in regex. (Maybe here we could call them "lookbesides"?) So after verifying that we're pointing to a 0 and the rest of the column contains only spaces, we need to actually match the 0:

0


Now the match pointer is on the character to the right of the 0. We need to check three different options: the snake angles down, the snake angles up, or the snake goes straight. For this, we can use an OR expression:

[...]


Inside our OR, we have three possibilities:

(<R> <L>)


Turn right, match a space, and turn left again (snake angles down).

(<L> <R>)


Turn left, match a space, and turn right again (snake angles up).

_?


Match zero or one underscores. Since there are no underscores in the input, this will always be an empty match (snake goes straight).

After matching one of the above three options, the match pointer should be pointing to the 0 in the next column, ready to match the parenthesized expression again.

CJam, 35 34 bytes

{z_{'0e=1=}%:*\'0f#2ew::-[W0X]-!*}


Try it online! Input is a rectangular array of arrays of characters. Assumes input only contains   and 0.

Explanation:

{z_{'0e=1=}%:*\'0f#2ew::-[W0X]-!*}   Function taking a character matrix:
z                                      Transpose.
{      }%                            Consider whether each row
e=                                  contains
1=                                exactly one
'0                                    of the character '0'.
:*                            This must be true for every row.
#                     Next, find the position
'0                         of the character '0'
f                        at every row
_           \                           in the original input.
:-               Find the differences between
:                   each
2                      pair
ew                    of adjacent elements (in other words, compute
the increments).
For the snake to be valid, this array of increments
must only contain {0, 1, -1}, so
-         Remove from this list
[   ]            the elements
W                 -1,
0                0,
X               and 1,
!          and then check whether the array is empty.
*       The previous code tested two different properties
of the matrix; they both must be true for a
valid snake.


05AB1E, 18 bytes

ζDε0k}¥Ä2‹sεþg}ìPΘ


Try it online!

Explanation

ζ                    # transpose
D                   # duplicate
ε  }               # for each row in the first copy (column of input)
0k                # get the index of the first 0
¥Ä             # calculate absolute delta's
2‹           # check that each is less than 2
sε  }      # for each row in the second copy (column of input)
þg       # calculate the length of the string with non-digits removed
ì     # concatenate the lists
P    # calculate product
Θ   # truthify (turn false values to 0)


Husk, 12 bytes

Depending on rule clarifications, may be 11 bytes or 13 bytes.

±Λ=;1Ẋ×≈mηfT


Try it online!

Input is a list of lines containing only spaces and 0s; if a single string is required, prepend ¶ to the program to split into lines. The TIO link already does this for clarity. Output is 0 or 1; if any falsy and truthy values are fine, the ± can be removed.

Explanation

±Λ=;1Ẋ×≈mηfT  Implicit input: a list of lines.
T  Transpose into list of columns.
m     For each column,
ηf   get list of indices of truthy elements.
In Husk, whitespace characters are falsy and other are truthy,
so this gets us the indices of 0s on each column.
Ẋ        For each adjacent pair of these index lists,
×       for all pairs drawn from the two lists,
≈      give 1 if they differ by at most 1, otherwise 0.
For each adjacent pair, this produces a list of 1s and 0s.
Λ            Do all of these lists
=;1         equal [1]? Return either 0 or 30 (length of the outer list + 1).
±             Signum; convert to 0 or 1.


The idea is to use ×≈ to guarantee that (a) all columns contain precisely one 0, and (b) their positions differ by at most one. As an example, consider the 8-column input

0  0  0
000 0
00   0


First, mηfT transforms it to the list of index lists

[[1],[2],[2,3],[1,2,3],[],[2],[1],[3]]


Then Ẋ×≈ gives

[[1],[1,1],[1,1,0,1,1,1],[],[],[1],[0]]


Each 1 corresponds to a pair of indices that differ by at most 1, and each 0 corresponds to a pair that doesn't. Each result equals [1] precisely when both lists have one index, and the indices differ by at most 1.

Python 2, 71 bytes

f=lambda s:s[1]<' 'or'0'in s[::31]in' %s '%s[1::31]in'%6s'%0*2*f(s[1:])


Try it online!

Takes input as a multiline string. Tests case from Bubbler.

The first column is extracted as s[::31] and the second as s[1::31], and they are checked for validity. We recurse on s removing the first character, causing successive pairs of columns to be checked.

The check for two columns uses Python's comparison chaining for in combine multiple checks:

• '0'in s[::31] checks that the first column has at least one 0
• s[::31]in' %s '%s[1::31] checks that the first column is a substring of the second column sandwiches between two spaces, which ensures the position of the 0 has shifted at most one space
• ' %s '%s[1::31]in'%6s'%0*2 checks that the second column contains at most one 0.

The ending *f(s[1:]) also forces the recursive case to be true.

• Now that I think about it, Python is an awesome language for these "snake" challenges. :P – MustacheMoses Feb 23 '18 at 19:51

C (gcc), 246245232215 212 bytes

#define F)exit(1);
#define L for(i=l=0;i<30;i++)
#define X b[7][i]
char b[8][31];k,j,l;main(i){for(;j++<5;){gets(b);L{if(i[*b]>47){if(X++F memset(b[j+1]+i-1,l=1,3);}else if(!X&b[j][i]F}k+=!!l;}if(k<5 F L if(!X F}


Try it online!

Figured I'd take my favorite language to this (even though as I can see from the many other, smaller entries it's probably far from ideal for this sort of challenge) and C what I could manage. The program's approach to the problem is relatively straightforward, just with a lot of byte penny-pinching; it takes the snake on stdin and gives its result in the return value of main (thus the exit code; as requested in the problem 0 indicates an invalid snake and 1 valid even though for an exit code that's weird as typical for exit codes 0 is a valid snake and 1 is an invalid snake). With the macros expanded and some nice whitespace it looks more like the following:

char b[8][31];l,j,k;                           //Declares a buffer to work in, initialized all to 0; l j and k default to int and as globals are init to 0
main(i) {                                      //This is run no-args, so argc is 1 and the undeclared type defaults to int.
for (; j++ < 5;) {                           //Iterating over each row, 1-indexed for convenience accessing the buffer
gets(b);                                   //Reads into b[0] because of stack array decl layout
for (i = l = 0; i < 30; i++) {             //j and l both init each time we begin this overall loop
if (i[*b] > 47) {                        //Did we read a zero?
if(b[7][i]++) exit(1);                 //If the snake already had a zero in this column, fail out
memset(b[j+1] + i-1, l = 1, 3);        //Expect them on the next row in the columns left and right of this one (also set l)
} else if (!b[7][i] & b[j][i]) exit(1);  //If we didn't read a zero, and we had reason to expect one this row, and there wasn't already a zero in this column, fail out
}
k+=!!l;                                    //Adds 1 to k iff l is nonzero
} if (k < 5) exit(1);                        //If less than 5 rows had zeroes in them, fail out
for(i = l = 0 ; i < 30; i++) {               //l isn't relevant in this loop but saves some bytes when sharing a macro with the other horizontal loop
if(!b[7][i]) exit(1);                      //If any columns didn't have zeroes, fail out
}                                            //Else, snake is valid. main default returns 0.
}


Lines of input are read into the first row of the buffer, the next five are for tracking what places are expected to (read: must) have zeroes in the row after each current one, and the last is for tracking whether a zero has already been read in a given column, in any row. The program processes each row in turn.

It's not at all robust (gets() is only the beginning) and the input must contain all the relevant spaces (no left-off trailing whitespace for instance), and gcc spews warnings and notes about stdlib functionality left implicitly declared and so on, but, C la vie.

It also assumes that the snake head need not be in the center row, and that a valid snake must have at least one zero in every row (i.e. no rows of all spaces in the 5 input rows). If the latter's not a requirement it can be made a bit shorter - everything to do with k and l in the program can be pared out or replaced with fewer bytes of code in that case.

Thanks to user202729 for approx. 26 bytes saved.

• Welcome to PPCG! And, don't worry about shorter programs in other languages. – user202729 Feb 23 '18 at 5:00
• You can left out the space between #define F and ) for -1 byte. – user202729 Feb 23 '18 at 5:01
• Also, because the input only have \n (10), <space> (32) and 0 (48) you can check for ==48 with >47 (-1 byte). / You can remove the ={0} when initialize b if the variable is global. Similarly make k global and i a (untyped -> int) parameter of main (in place of argc which is 1). – user202729 Feb 23 '18 at 5:03
• Thank you! Edited before I saw the latter suggestions; I'll tick my way through them (that i as argc is genius). First drafts of this were well over 400 bytes; took me long enough just to drag it down to my personal goals of 300 and then 256 so there may well be more ways to slim it down I've missed. – SevenStarConstellation Feb 23 '18 at 5:10
• Decided to make k, j, and l all globals to save on having separate int declarations, then realized the defaults would let me get away with leaving the type off entirely. Thanks again! – SevenStarConstellation Feb 23 '18 at 5:31

MATL, 18 17 bytes

32>&fun30=wd|2<vA


Input is a 2D char array. Any non-space character can be used for the snake.

Try it online!

Explanation

32>      % Implicit input. Transform non-space into 1, space into 0
&f       % Push vector of row indices and vector of column indices of nonzeros
u        % Unique: vector of deduplicated entries
n        % Length
30=      % Does it equal 30? (*)
w        % Swap. Moves vector of row indices to top
d|       % Absolute consecutive differences
2<       % Is each value less than 2? (**)
v        % Concatenate results (*) and (**) vertically
A        % All: true if all entries are nonzero. Implicit display

• The spec implies the line lengths being 30 is guaranteed, so I think you can save a few. – Jonathan Allan Feb 22 '18 at 8:48
• @JonathanAllan Thanks! I'm using un30= to check that all column indices are different, and none of the 30 columns is empty. Maybe I can test that more directly, but I don't see how – Luis Mendo Feb 22 '18 at 11:23

((\|/)?0(<(?| *$^)<){2}){30}  Test it here. Jelly, 19 bytes Zn⁶T€L€=1$$;FIỊ$$$Ạ


Try it online!

-2 bytes thanks to Mr. Xcoder

Explanation

Zn⁶T€L€=1$$;FIỊ$$$Ạ Main Link Z Transpose the matrix of characters (string -> list of chars in Jelly) n⁶ != " " (vectorizing) T€ For each column, get (row) indices of snake parts L€=1$$For each index list, is its length 1? (that is, exactly one snake part per column) ; Append (helper part) FIỊ$$ helper part: F flatten index list I get increments/forward differences Ị are the values insignificant? (|z| <= 1) Ạ Are these all true?  Input is as a list of strings • @Mr.Xcoder Huh fail, Jelly string representation issues lol. fixed by ungolfing the 1 byte – HyperNeutrino Feb 22 '18 at 13:22 Jelly, (14?*) 13 bytes Zn⁶T€z-IỊ0-¦Ȧ  A monadic link taking a list of five strings*, each of length 30 consisting of spaces and any other characters (e.g. 0s), and returning an integer (1 if a snake as defined, 0 otherwise) * If input must be a single string (list of characters) then prepend a Ỵ to split the string at line feeds. Try it online! How? Zn⁶T€z-IỊ0-¦Ȧ - Link: list of lists of characters, Lines Z - transpose the lines -> columns ⁶ - literal space character n - not equal? -> 0 where there were spaces and 1 where there were "0"s T€ - truthy indices for each -> e.g. [0,0,1,0,0] -> [3] or [0,1,1,0,0] -> [2,3] - note: [0,0,0,0,0] -> [] - - literal minus one z - transpose with filler (-1) -> {valid: a single list of heights {top:1,...,bottom:5} - invalid: list of >1 lists, some of which contain -1 - ...OR an empty list (no 0s in the input at all)} I - differences -> {up:-1; down:1; flat:0; invalid:-6,-5,...,-2,2,...4} Ị - insignificant (abs(z)<=1) -? {up/down/flat:1; invalid:0} ¦ - sparse application/// 0 - ...action: literal zero - - ...to indices: [-1] -> make penultimate list into a zero (when one exists) Ȧ - any & all -> when flattened:{empty or contains a 0:0; otherwise:1}  • Ah thought I'd tried all edge cases, thanks for the heads-up; will have to address later. – Jonathan Allan Feb 22 '18 at 13:22 • @LuisMendo heh and in fixing that I saved three, so thanks again! – Jonathan Allan Feb 22 '18 at 19:44 • ... uh, but I introduced another. Fixed up for another 3 :( – Jonathan Allan Feb 22 '18 at 20:09 • Not a bad byte-count though :-) – Luis Mendo Feb 22 '18 at 21:58 Stax, 20 bytesCP437 Å┴m▐◘5)ît╢V¼≥+╝╜►º½ê  24 bytes when unpacked, LM{'0|Ic%vChm:-{Jh!f%29=  Run and debug online! May not be the best golfed one but I think the method is novel and interesting. Explanation LM Load the input string as a 2d array of characters, and transpose it { m Map array with block '0|I Get all indices of substring "0" c%vC Map to nothing if the indices are not unique h Otherwise map to the unique index :- Take pairwise difference { f Filter array with block Jh! Only keep 0, 1 and -1 %29= Check whether the final array has exactly 29 elements  J, 38, 37 30 bytes -8 bytes thanks to FrownyFrog [:($e.~[:(-:*)2-/\])@:I.'0'=|:


Try it online!

• How about [:(-:*)2-/\, check if all differences are −1, 0 or 1. – FrownyFrog Feb 23 '18 at 1:55
• @FrownyFrog Yes, it's much beteter! Thank you! – Galen Ivanov Feb 23 '18 at 7:23
• @ FrownyFrog Hmm, I didn't realize that. I'll try to fix it. Thank you for pointing that out. – Galen Ivanov Feb 23 '18 at 11:56
• [:(#@{.=[:(-:*)2-/\])@:I.'0'=|: – FrownyFrog Feb 23 '18 at 14:05
• Oh, this also works [:($e.~[:(-:*)2-/\])@:I.'0'=|: – FrownyFrog Feb 23 '18 at 15:32 Jelly, 16 bytes Zµi€”0IỊ;ċ€⁶=4ƊẠ  Try it online! Assumes that the input string will always only contain only spaces and zeros. Takes input as a list of strings (each representing a line), and outputs 1 if truthy, 0 otherwise. Explanation Zµi€”0IỊ;ċ€⁶=4ƊẠ | Monadic full program. Z | Transpose. µ | Start a new monadic chain. i€”0 | Retrieve the first index of 0 in each column. IỊ | Check whether their increments are insignificant (element-wise). ; Ɗ | Append the result of the following: ċ€⁶ | In each list of characters, count the occurrences of a space. =4 | Check whether they equal 4 (returns a boolean array). Ạ | All. Check whether all the elements are truthy.  Python 2, 141 bytes lambda g:(lambda a:all(map(len,a)+[-2<x-y<2 for b in[sum(a,[])]for x,y in zip(b,b[1:])]))([[i for i in range(5)if"0"==r[i]]for r in zip(*g)])  Try it online! Input is a grid of characters. Python 2 and Python 3, 122120 119 bytes lambda s:s.count('0')<31and all(s[i-31*(i>30):31*(i<124)-~i:31].strip(' ')for i,x in enumerate(s,1)if' '<x)and' '<s[62]  Try it online! Input format is one string of length 154 (5 x 30 chars, 4 newlines): ''' 0 0 0 0 0 000 00 0 00 000 0 0 000 0 0 0 00 0 000 '''[1:] # to exclude starting newline  If the head doesn't have to be the center row The center-row-head requirement was in the original challenge, but I found that it's not the case here (at least it's not explicitly mentioned). Python 2 and Python 3, 124 123 bytes lambda s:s.count('0')<31and all(s[i-31*(i>30):31*(i<124)-~i:31].strip(' ')for i,x in enumerate(s,1)if' '<x)and'0'in s[::31]  Try it online! Edit: • Reduced 2 bytes by changing equals(==) into inequalities for each code. • Found mistakes in the less limiting version, and revised it. (Fortunately it's not too terrible, so I could keep all versions similar in length.) You can see additional test cases in the latter two TIO links. • Found a dangling byte in Py2 solutions, making the all() trick meaningless in Py3, so merged both versions. Excel (VBA), 68 bytes Using Immediate Window, Cell[A6] as output. [A1:AD5]="=CHOOSE(ROUND(RAND()+1,),0,"""")":[A6]="=COUNT(A1:AD5)=30"  Snails, 18 bytes \0!(ud.,\0)raa7)30  Try it online! Grime, 3026 23 bytes Thanks to Zgarb for saving 7 bytes and pointing out a bug. e" 0/0 "oO|#29ddv&d#1+  Try it online! Ruby, 93 bytes ->x{x.transpose.map{|x|x.count(?0)<2&&x.index(?0)}.each_cons(2).all?{|x,y|x&&y&&(x-y).abs<2}}  Try it online! JavaScript (Node.js), 128 126 bytes Edited after input clarification stating that the input is "a string". F=(a,l=29,r=0,t=/^( *)0 *$/.exec(a.split
.map(p=>p[l]).join),q=t&&~t[1].length)=>q&&(s=q-(r=r||q))>-2&s<2?l?F(a,l-1,q):1:0


Try it online!

Python 3, 197 185 bytes

In command prompt do verify.py<snake.txt or in bash do cat snake.txt | python verify.py. Where snake.txt is a file containing a snake to verify.

If the snake is correct nothing will be output. If it isn't correct Python will raise an index error.

import sys
`