A bit ago I wrote about writing a generic brute force solver (wow, was that really two months ago?). It got … complicate. Mostly, because every time I wrote a step function, I had to be careful to undo the same. Wouldn’t it be nice if we could just write a step function and get backtracking for ‘free’?
Well, with immutability you can!
Part 1: Given a map of the form:
########### #0.1…..2# #.#######.# #4…….3# ###########
> Find the shortest route to visit each of the points, starting at `0`.
First, we want to take the map that we were given and simplify it. We know that we want to visit all of the points, so lets take the original map and turn it just into a map of distances between any two named points.
```python
walls = set()
name_to_point = {}
point_to_name = {}
# Load the input file into a set of walls and the location of points of interest
for y, line in enumerate(fileinput.input(args.files)):
for x, c in enumerate(line.strip()):
if c.isdigit():
name_to_point[int(c)] = (x, y)
point_to_name[(x, y)] = int(c)
elif c == '#':
walls.add((x, y))
# Dynamically fill a distance map to a given point
def distances_to(name):
to_scan = queue.Queue()
to_scan.put((name_to_point[name], 0))
scanned = set()
result = {}
while not to_scan.empty():
point, distance = to_scan.get()
if point in point_to_name:
name = point_to_name[point]
if name not in result:
result[name] = distance
if point in scanned:
continue
else:
scanned.add(point)
x, y = point
for xd, yd in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
neighbor = (x + xd, y + yd)
if neighbor not in walls:
to_scan.put((neighbor, distance + 1))
return result
distances = {
name: distances_to(name)
for name in name_to_point
}
names = list(sorted(name_to_point.keys()))
The first part loads the map and the second part will flood fill out from each point. This will find the minimum distance from each named point to the given one, somewhat simplifying the problem.
Part 1: Create a 4x4 grid of rooms with doors
Up,Down,Left, andRight from each location. To determine if a door is currently open:
- Calculate
MD5(salt + sequence)where sequence is a string containing any combination ofUDLRdepending on how you got to this room- The first four hex values represent the doors
Up,Down,Left, andRight respectively:bcdefmeans open; anything else is closed
Find the shortest path from
(0, 0)to(3, 3).
Part 1: Input will be a list of the following form:
- The first floor contains a hydrogen-compatible microchip and a lithium-compatible microchip.
- The second floor contains a hydrogen generator.
- The third floor contains a lithium generator.
- The fourth floor contains nothing relevant.
You have an elevator that can move exactly 1 or 2 items. You can only leave a microchip on a floor with a non-matching generator if a matching generator is also present.
Move all items to the top (4th) floor.
Based on a /r/dailyprogrammer puzzle: Takuzu solver.
Basically, Takuzu is a logic puzzle similar to Sudoku. You are given a grid partially filled with 0s and 1s. You have to fill in the rest of the grid according to three simple rules:
Thus, if you have a puzzle like this:
0.01.1
0....1
..00..
..00..
1....0
10.0.0
One valid solution (most puzzles should have only a single valid answer, but that doesn’t always seem to be the case):
010101
001101
110010
010011
101100
101010
Let’s do it!
It’s been a while1, but I’m back. Today’s post is inspired by a post from /r/dailyprogrammer almost a month ago now: Challenge #183 [Intermediate] Edge Matching Tile Puzzle. Basically, we’re going to solve puzzles like this:
If you look carefully, the tiles are the same between the two, although they might be rotated.
Onwards and upwards! For today’s chess puzzle, let’s take a first crack at the Knight’s Tour1
After two weeks, it seems only right that we actually get around to a real chess puzzle. First on the list: Eight queens puzzle.
Specifically, how do you place n queens on an n by n chess board such that no pair of queens can attack one another?
Ever been to Cracker Barrel? Remember that peg game? It seems that rather a few people are interested in how to solve it: Google. Let’s do that.
Yesterday’s post at /r/dailyprogrammer managed to pique my interest1:
A triangle on a flat plane is described by its angles and side lengths, and you don’t need all of the angles and side lengths to work out everything about the triangle. (This is the same as last time.) However, this time, the triangle will not necessarily have a right angle. This is where more trigonometry comes in. Break out your trig again, people.