Snak
| Paradigm(s) | imperative |
|---|---|
| Designed by | User:Quintopia |
| Appeared in | 2021 |
| Computational class | Unknown |
| Reference implementation | Python |
| Influenced by | Nopfunge,Spiral |
| File extension(s) | .snak |
Snak is an esolang by User:Quintopia in 2021 based on ideas by Esolangs Discord user thejonesymyster. Programs consist of an infinite grid of fruit on which a vast Snake Game is played. In short, it is a language of sneks getting snaks.
Snak program definition
Grid chunks
A Snak program consists of a description of a single chunk in an infinite 2D space. The contents of each cell of the space are defined by the character located in that position in the program. These include
| Symbol | Meaning |
|---|---|
| + | Incrementing Fruit |
| - | Decrementing Fruit |
| > | Snake initially moving east |
| < | Snake initially moving west |
| ^ | Snake initially moving north |
| v | Snake initially moving south |
All other characters (aside from line feeds and carriage returns, which are stripped) have no semantic meaning (but do occupy space). (Thus, Snak programs can contain comments in their unused space. It is recommended to replace the letter v, where needed in such comments, with a u or w.)
The full operating space of a Snak program is created by infinitely tiling the fruits in the single defined chunk in every direction.
The width of the chunks is defined as the maximum length of any line of the program. The height of the chunks is defined as the number of lines in the program.
Snakes
A Snak program may have any number of snakes. A snake has a position, a direction, a length, and a finite queue of cells in the grid (the last of which is always its position). At program start, every snake occupies only a single cell in the prescribed location in the origin chunk (the chunk that contains the location (0,0)), regardless of its initial length.
Fruits
Every + or - in the program definition specifies an infinite number of corresponding fruits, one per chunk. As the program runs, some fruits will be removed from the grid, but, unlike the snake game, no fruits are ever added.
Execution of a Snak program
At the beginning of a Snak program, the length of every snake is initialized to the same value provided as the length parameter to the interpreter. This is the only input method that does not involve altering the program source.
A Snak program proceeds in finite ticks. At each tick, the following occur in sequence:
- Every snake takes one step in its current direction.
- The new position is enqueued in its list of occupied cells.
- The oldest position in the queue is popped and discarded.
- If the snake's position is now a cell it already occupies, the program halts.
- If any snake now occupies a cell occupied by any other snake, the program halts.
- If any snake now occupies the same position as a fruit:
- That fruit is removed from the grid.
- The corresponding incrementing or decrementing of the snake's length is performed.
- If a decrementing brings a snake's length to zero, the program halts with an error condition.
- If a snake now occupies more cells than its length, its queue of occupied positions is popped.
- Every snake's direction is updated.
- Up to three fruits are selected from the grid.
- A fruit is selected if it is the first fruit along the line in the snake's current direction from the snake's current position, or 90 degrees clockwise or counterclockwise from that direction and no snakes (including the snake for whom this computation is being performed) lying between the fruit and the snake's current position. In other words, the first fruit "visible" by the snake in any of the three directions it could take its next step.
- Of these selected fruits, the nearest ones to the snake's current position is selected.
- If more than one fruit are at the nearest distance, the clockwise one is preferred to the one in the same direction which itself is preferred to the counterclockwise one.
- Up to three fruits are selected from the grid.
Note that this order ensures that every snake will attempt to take one step in their initially defined direction before the positions of any fruits have an effect on their movement.
When the program halts, the final length of each snake is printed. This is the only form of output aside from watching the program state as it changes.
Example Programs
Given that a normal halt to a Snak program is for a snake to collide (with itself or another snake), an obvious question is how to ensure a self-collision. The challenge in this question is "what is the smallest program that ensures a snake self-collision on any input size?" Here is the smallest found to date (4x4), but smaller ones could exist:
+++
+++
>++
A curious property (and the main challenge) of Snak programs is that the only way to do computation is to destroy the very code that performs it. In fact, although it is possible to engineer arrangements of fruit such that many of the fruits in each chunk are consumed while many are left behind. In fact, it's likely that most initial patterns behave this way. Is the alternative possible, however? Are there patterns such that, given infinite time, a snake will eat every single fruit? We can even further require that the snake do so without infinite growth. This simple checkerboard pattern results in an infinitely growing snake coiled in a square spiral that clears the plane of fruit in the limit:
>+ +
And this checkerboard has the same clearing pattern, but the snake does not infinitely grow. It merely alternates between two lengths:
+>- - + - + + -
And here is a much more complicated spiraling program with the same property, except that it's no longer a rectangular spiral pattern. Note that the chunk shape is not even a square anymore, and in fact cannot be. If a pattern like this were square, it would eventually result in halting by self-collision:
+
- -<
+
In none of the preceding three examples does it particularly matter the initial position or direction of the snake. (In fact, one can include multiple snakes and still get similar behavior as long as they do not immediately collide.) And just to demonstrate that some kind of computation can be performed, here is an example of a widget that divides a snake's length in half rounded down as long as it is not too long to begin with. (In order to use standalone, the above self-collision widget was used which only works on snakes of length at least 9, so this can only be demonstrated as-is on snakes of initial length at least 18, but it will work on smaller snakes when included in a larger program with the first 3 lines blanked.) Yes, all the surrounding padding is necessary for it to work correctly.
+-+
-+-
+-+
-
- -+-
- +
- -
- +
- -
- +
- -
- +
- -
- +
- -
- +
- -
- +
- -
- +
- -
- +
- -
- +
- -
- +
^
+
Computational Class
It is believed that Snak is Turing-complete. It is probably Turing-complete using only one snake. It is probably even Turing-complete in terms of performing computation using only snake lengths as state and ignoring their positions, though this is a greater challenge. Any input or insight as to how to build a Minsky machine or the like with these tools would be appreciated.
Implementations
There's a reference implementation on Github in Python 3.10 using an ncurses-based visualizer that is pretty buggy.