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 0
s 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.
4
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 – 2018-02-22T01:52:11.1535Is this taken as a Sting? Or can it be input as a 2d array? – JSchiff – 2018-02-22T01:56:11.943
6Are 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 – 2018-02-22T04:57:26.443
Waiting for the inevitable diagonal snake challenge... – Luis Mendo – 2018-02-22T07:34:27.577
Hmm, what about the polar snake? Or Ouroboros? :) – Galen Ivanov – 2018-02-22T07:36:10.727
Can we choose a different character instead of
0
? – Luis Mendo – 2018-02-22T08:08:32.0809
Since this is a decision-problem how about
– Jonathan Allan – 2018-02-22T08:15:52.903truthy/falsey
rather thantrue/false
?3@JSchiff I'm sure a snake Bytes? – MarioDS – 2018-02-22T08:41:09.483
@MarioDS Except if it constraints then maybe it's a python? – Unlambder – 2018-02-22T14:14:03.510
I'm not really sure how a question that has 19 upvotes and 20 answers (at the time of commenting) can justifiably be put on hold as unclear particularly when many of the answers are from pretty high rep members who obviously have a lot of experience of these things. Maybe there is a justification for it being closed. In my (humble) opinion, "unclear" is not it. Just a bit surprised, that's all. – ElPedro – 2018-02-22T23:04:00.080
Sorry for the ambiguity—I've edited for clarification, can this be taken off hold? – Mirror318 – 2018-02-22T23:59:59.387
@ElPedro Yes, it was unclear. There are 5~6 answers taking an array/list of strings as input, or assumes that input may be taken as a 2D array and provide multiple alternatives, or edit after the clarification.
– user202729 – 2018-02-23T04:50:07.640