At https://www.meetup.com/DenverDevDay/ 2023 Fall I get the following puzzle.
When disassembled it looks this way
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;
}
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 }
Top comments (0)