Verifying a horizontal ASCII pet snake

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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)

Answer 7

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.

Answer 8

C (gcc), 246 245 232 215 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.

Answer 9

Python 2 and Python 3, 122 120 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.

Answer 10

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

Answer 11

Grime, 30 26 23 bytes

Thanks to Zgarb for saving 7 bytes and pointing out a bug.

e`" 0/0 "oO|#29ddv&d#1+

Try it online!

Answer 12

Slip, 28 bytes

((\|/)?0(<(?| *$^)<){2}){30}

Test it here.

Answer 13

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

Answer 14

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}

Answer 15

Stax, 20 bytes^CP437

Å┴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

Answer 16

J, 38, 37 30 bytes

-8 bytes thanks to FrownyFrog

[:($e.~[:(-:*)2-/\])@:I.'0'=|:

Try it online!

Answer 17

Vyxal, 14 bytes

∩ȧvT:v₃$¯ȧ2<JA

Try it Online!

Takes input as a list of char lists.

∩              # Transpose the input
 ȧ             # Remove whitespace (since this is a char list list, spaces become empty)
  vT           # Truthy indices (indices of 0) of each
            JA # Are both...
    :v₃        # All elements are length 3
       $¯ȧ     # And all elements have absolute differences
          2<   # Less than 2.

Answer 18

Pip -r, 26 24 bytes

$&ZgM{0Na<2>yAD#y*Ya@?0}

Takes the snake from stdin and outputs 0 for invalid or 1 for valid. Attempt This Online!

Explanation

This was fun. I went through several different versions, finally ending up with a solution that abuses the y variable delightfully and also shows off Pip's chaining comparison operators.

$&ZgM{0Na<2>yAD#y*Ya@?0}
                          g is list of lines of stdin (-r flag); y is "" (implicit)
  Zg                      Zip g, transposing rows and columns
    M{                 }  To each sublist (column of the original input), map this function:
      0Na                  The number of 0s in this column
         <2                 is less than 2
           >                and 2 is greater than the following quantity:
            y                The index of the 0 in the previous column, or "" if this is
                              the first column
             AD              Absolute difference with
               #y*            len(y) times
                   a@?0       the index of 0 in this column
                  Y           which we also store in y
$&                        Fold the resulting list on logical AND

The expression yAD#y*Ya@?0 warrants further explanation. We want to calculate the difference between the indices of 0s in consecutive columns. We calculate the index of 0 in the current column (a@?0) and store it in y by using the Yank operator (Ya@?0).

But then how can we access the previous column's index, which was stored in y? We'll have to access it before overwriting y with the new value. Since Pip expressions are always evaluated left-to-right, we can use the old value of y on the left side of the expression and update to the new value on the right.

The first column presents another wrinkle. Here, when we access the old value of y, we haven't had a chance to set it to anything yet, and it still has its initial value of "". We want the first column to succeed no matter what its 0 index is, which means we need the difference to be between -1 and 1. So we multiply the new value by the length of the old value (#y). If y hasn't been set yet, this multiplies the new value by 0, making the difference 0. If y has been set, it will be a single-digit number (since there are only 5 rows in the input), and so multiplying by its length will leave the new value unchanged.

Answer 19

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.

Answer 20

Excel (VBA), 68 bytes

Using Immediate Window, Cell[A6] as output.

[A1:AD5]="=CHOOSE(ROUND(RAND()+1,),0,"""")":[A6]="=COUNT(A1:AD5)=30"

Answer 21

Snails, 18 bytes

\0!(ud.,\0)raa7)30

Try it online!

Answer 22

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!

Answer 23

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!

Answer 24

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
s=sys.stdin.read().split("\n")
x=0
exec('t,y="",0\nwhile y<5:t+=s[y][x];y+=1\ns+=[t];x+=1;'*30)
s=list(map(lambda l:len(l.rstrip()),s))
while y<35:"ee"[abs(s[y]-s[y+1])];y+=2