Questions tagged [taxicab-geometry]

The taxicab metric is also known as rectilinear distance, L1 distance or L1 norm (see Lp space), city block distance, Manhattan distance, or Manhattan length

Filter by
Sorted by
Tagged with
5
votes
2answers
101 views

Compute Manhattan distance from origin given a set of left-right-step directions

I am solving the problems for Advent of Code 2016 to learn Rust programming. The prompt for the first problem can be summarized: I start at position 0,0 on a regular grid. I am given a set of ...
5
votes
2answers
574 views

Optimized board representation for the 4x4 sliding puzzle

Inspired by this question and my answer to it I told myself I could try an optimized version for a 4x4 puzzle. There are only \$16!\$ possible states, so the state fits into a single ...
7
votes
3answers
11k views

Optimizing Manhattan-distance method for N-by-N puzzles

By N-by-N puzzles I mean f.e. a 3x3 sliding puzzle with one blank space (so a 8-puzzle) or a 4x4 sliding puzzle (so a 15-puzzle). When I try to solve certain puzzles some take no time but others take ...
3
votes
1answer
3k views

N-puzzle program solved using A* search

I coded the following program to solve the n-puzzle problem with n = 3. Are there any suggestions regarding readability and variable names? ...
3
votes
2answers
5k views

Calculating sum of manhattan distances in a sliding puzzle

I would like some feed back on a method which calculates the sum of Manhattan distances for each tile in a sliding puzzle to its goal position in the goal puzzle. Here is the code: ...
2
votes
2answers
2k views

A* shortest path algorithm optimization

I had this programming exercise of mine where I had to find the shortest path to an exit in an NxM -grid maze in under a second (both N and M would be anywhere between 3 and 1000). The program would ...