DEV Community

Stanislav Berkov
Stanislav Berkov

Posted on

Denver Dev Day snake puzzle solver

At https://www.meetup.com/DenverDevDay/ 2023 Fall I get the following puzzle.

Solved puzzle

When disassembled it looks this way

Disassembled puzzle

Quite hard puzzle I would say. I decided to write a C# program to solve it.

const int dim = 3;
int[] snake = { 3, 3, 3, 3, 2, 2, 2, 3, 3, 2, 2, 3, 2, 3, 2, 2, 3 };

bool[,,] used = new bool[dim, dim, dim];

Stack<Point> path = new();
used[0, 0, 0] = true;

if (DFS((0, 0, 0), 0, (0, 0, 0))) {
    foreach (var m in path.Reverse()) {
        Console.WriteLine(m);
    }
};

bool DFS(Point p, int idx, Point m) {
    if (idx >= snake.Length) {
        return false;
    }

    if (p == (dim - 1, dim - 1, dim - 1) && idx == snake.Length - 1) {
        Console.WriteLine("done!");
        return true;
    }

    foreach (var move in Point.Moves) {
        if (move == m) { continue; }
        var len = (snake[idx] - 1);
        var nextLen1Or2 = p + (move * len);
        var nextLen1 = p + move;
        if (!nextLen1Or2.InCube(dim)) { continue; }
        if (used[nextLen1Or2.X, nextLen1Or2.Y, nextLen1Or2.Z]) { continue; }
        if (used[nextLen1.X, nextLen1.Y, nextLen1.Z]) { continue; }
        path.Push(move);
        used[nextLen1Or2.X, nextLen1Or2.Y, nextLen1Or2.Z] = true;
        used[nextLen1.X, nextLen1.Y, nextLen1.Z] = true;
        if (DFS(nextLen1Or2, idx + 1, move)) {
            return true;
        }
        path.Pop();
        used[nextLen1Or2.X, nextLen1Or2.Y, nextLen1Or2.Z] = false;
        used[nextLen1.X, nextLen1.Y, nextLen1.Z] = false;
    }

    return false;
}

public record struct Point(int X, int Y, int Z) {
    public static readonly Point[] Moves = { (-1, 0, 0), (0, -1, 0), (0, 0, -1), (1, 0, 0), (0, 1, 0), (0, 0, 1) };
    public static Point operator +(Point a, Point b) => new(a.X + b.X, a.Y + b.Y, a.Z + b.Z);
    public static Point operator *(Point a, int f) => new(a.X * f, a.Y * f, a.Z * f);
    public static implicit operator Point((int X, int Y, int Z) p) => new(p.X, p.Y, p.Z);
    public readonly bool InCube(int size) => X >= 0 && X < size && Y >= 0 && Y < size && Z >= 0 && Z < size;
}
Enter fullscreen mode Exit fullscreen mode

So the solution is:

Point { X = 1, Y = 0, Z = 0 }
Point { X = 0, Y = 1, Z = 0 }
Point { X = -1, Y = 0, Z = 0 }
Point { X = 0, Y = 0, Z = 1 }
Point { X = 1, Y = 0, Z = 0 }
Point { X = 0, Y = 0, Z = -1 }
Point { X = 1, Y = 0, Z = 0 }
Point { X = 0, Y = -1, Z = 0 }
Point { X = -1, Y = 0, Z = 0 }
Point { X = 0, Y = 0, Z = 1 }
Point { X = 0, Y = 1, Z = 0 }
Point { X = 0, Y = 0, Z = -1 }
Point { X = 1, Y = 0, Z = 0 }
Point { X = 0, Y = 0, Z = 1 }
Point { X = 1, Y = 0, Z = 0 }
Point { X = 0, Y = 1, Z = 0 }
Enter fullscreen mode Exit fullscreen mode

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

Top comments (0)

Heroku

This site is powered by Heroku

Heroku was created by developers, for developers. Get started today and find out why Heroku has been the platform of choice for brands like DEV for over a decade.

Sign Up

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay