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

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

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

Okay