`yen()`'s result is not always ordered
epidemian opened this issue · 3 comments
epidemian commented
Hey, thanks for making this great library! It's been a blessing on for last year's Advent of Code :)
I've found what might be a bug on Yen's algorithm implementation. The docs say:
The returned paths include both the start and the end node and are ordered by their costs starting with the lowest cost
But this doesn't seem to be guaranteed.
Here's an example program —a terribly inefficient solution for AoC 2023 day 23 part 1— that showcases this:
use pathfinding::directed::yen::yen;
fn main() {
let grid: &Vec<Vec<char>> = &INPUT.lines().map(|l| l.chars().collect()).collect();
let start = (1_usize, 0_usize);
let end = (grid[0].len() - 2, grid.len() - 1);
let k = 1000;
let k_shortest_paths = yen(
&start,
|&(x, y)| {
let dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)];
dirs.into_iter().filter_map(move |(dx, dy)| {
let (nx, ny) = (x.wrapping_add_signed(dx), y.wrapping_add_signed(dy));
let tile = *grid.get(ny)?.get(nx)?;
match tile {
'v' if dy == -1 => None,
'>' if dx == -1 => None,
'#' => None,
_ => Some(((nx, ny), 1)),
}
})
},
|&pos| pos == end,
k,
);
let path_lengths: Vec<_> = k_shortest_paths.iter().map(|(_, l)| l).collect();
println!("found {} paths", k_shortest_paths.len());
println!("lengths: {path_lengths:?}");
println!("last: {}", path_lengths.last().unwrap());
println!("max: {}", path_lengths.iter().max().unwrap());
}
const INPUT: &str = "#.###########################################################################################################################################
#.#.....#...###.......#.....#.......#.......###...#...#.........#...#...###...###...###...#####...#...###...###...#.....#.....#...#...###...#
#.#.###.#.#.###.#####.#.###.#.#####.#.#####.###.#.#.#.#.#######.#.#.#.#.###.#.###.#.###.#.#####.#.#.#.###.#.###.#.#.###.#.###.#.#.#.#.###.#.#
#.#...#...#...#.....#.#...#.#.#.....#.#.....#...#.#.#.#.#.......#.#.#.#.#...#...#.#...#.#.....#.#.#.#.#...#...#.#.#...#.#...#...#...#.#...#.#
#.###.#######.#####.#.###.#.#.#.#####.#.#####.###.#.#.#.#.#######.#.#.#.#.#####.#.###.#.#####.#.#.#.#.#.#####.#.#.###.#.###.#########.#.###.#
#.#...#.......#.....#...#.#.#.#.....#.#.#...#...#...#...#...#...#.#.#.#.#.....#.#...#.#.#.....#.#.#.#...#.....#.#.#...#...#.....#.....#...#.#
#.#.###.#######.#######.#.#.#.#####.#.#.#.#.###.###########.#.#.#.#.#.#.#####.#.###.#.#.#.#####.#.#.#####.#####.#.#.#####.#####.#.#######.#.#
#.#.###...#...#.....#...#.#.#.#.....#.#.#.#.###.......#.....#.#.#.#.#.#.......#.>.>.#.#.#.#.....#.#.....#.###...#.#.....#.#.....#...#...#.#.#
#.#.#####.#.#.#####.#.###.#.#.#.#####.#.#.#.#########.#.#####.#.#.#.#.###########v###.#.#.#.#####.#####.#.###.###.#####.#.#.#######.#.#.#.#.#
#.#.#.....#.#...###.#...#.#.#.#...>.>.#...#.#...#.....#.#...#.#.#.#.#...#...#...#...#.#.#...#.....#.....#.#...#...#...#.#.#.#.....#.#.#...#.#
#.#.#.#####.###.###.###.#.#.#.#####v#######.#.#.#.#####.#.#.#.#.#.#.###.#.#.#.#.###.#.#.#####.#####.#####.#.###.###.#.#.#.#.#.###.#.#.#####.#
#.#.#.#...#...#.#...###.#.#.#.#.....#.......#.#.#.....#.#.#.#.#...#.###...#...#.#...#...#.....#...#.....#.#...#.###.#.#.#.#.#...#...#.#.....#
#.#.#.#.#.###.#v#.#####.#.#.#.#.#####.#######.#.#####.#.#.#.#.#####.###########.#.#######.#####.#.#####.#.###.#.###.#.#.#.#.###.#####.#.#####
#.#.#...#.....#.>.#.....#.#...#.#...#...#...#.#.#...#.#.#.#.#...#...#...#...#...#.......#.#...#.#...#...#.#...#...#.#.#.#.#.#...#...#.#.#...#
#.#.###########v###.#####.#####.#.#.###.#.#.#.#.#.#.#.#.#.#.###.#.###.#.#.#.#.#########.#.#.#.#.###.#.###.#.#####.#.#.#.#.#.#.###.#.#.#.#.#.#
#.#.#.....#.....###.#...#.#.....#.#...#...#.#.#.#.#.#.#.#.#.#...#.>.>.#.#.#...#...#...#.#.#.#.#.#...#...#.#.....#.#.#.#.#.#.#...#.#.#.#.#.#.#
#.#.#.###.#.#######.#.#.#.#.#####.###.#####.#.#.#.#.#.#.#.#.#.#####v###.#.#####.#.#.#.#.#.#.#.#.#.#####.#.#####.#.#.#.#.#.#.###.#.#.#.#.#.#.#
#...#.#...#.......#...#.#.#.......#...#...#...#...#.#.#.#.#.#...###...#.#.#.....#...#.#.#.#.#.#.#.#.>.>.#...#...#.#.#.#.#.#.#...#.#...#...#.#
#####.#.#########.#####.#.#########.###.#.#########.#.#.#.#.###.#####.#.#.#.#########.#.#.#.#.#.#.#.#v#####.#.###.#.#.#.#.#.#.###.#########.#
#...#.#...###.....#.....#.#.....###.#...#...#.....#.#.#...#.#...#.....#...#.........#.#.#.#.#...#...#.....#...###...#...#.#.#.#...#.........#
#.#.#.###.###.#####.#####.#.###.###.#.#####.#.###.#.#.#####.#.###.#################.#.#.#.#.#############.###############.#.#.#.###.#########
#.#...#...#...#####.......#...#.....#...###...#...#...#...#...#...#.....#...#.......#...#.#.#.............#...#.....#.....#.#.#.###.........#
#.#####.###.#################.#########.#######.#######.#.#####.###.###.#.#.#.###########.#.#.#############.#.#.###.#.#####.#.#.###########.#
#.....#.....#...###.........#.......#...#.......#####...#...#...###...#...#...#####.....#...#...#.....#.....#...#...#.....#.#...#.........#.#
#####.#######.#.###.#######.#######.#.###.###########.#####.#.#######.#############.###.#######.#.###.#.#########.#######.#.#####.#######.#.#
#.....#.......#.....#.......#.......#.###.........#...#...#...#...#...#.............#...#.......#...#.#...###.....#...###...#...#.......#.#.#
#.#####.#############.#######.#######.###########.#.###.#.#####.#.#.###.#############.###.#########.#.###.###.#####.#.#######.#.#######.#.#.#
#.......#.......#.....###...#.........#...........#...#.#.......#.#.#...###.........#...#...........#...#.#...#...#.#.###...#.#.#...#...#.#.#
#########.#####.#.#######.#.###########.#############.#.#########.#.#.#####.#######.###.###############.#.#.###.#.#.#.###.#.#.#.#.#.#v###.#.#
#...#...#.....#...#...###.#.###...###...#...........#...#.......#.#...#...#.......#.....###...#...#...#...#...#.#.#.#.#...#...#...#.>.###.#.#
#.#.#.#.#####.#####.#.###.#.###.#.###.###.#########.#####v#####.#.#####.#.#######.#########.#.#.#.#.#.#######.#.#.#.#.#.#############v###.#.#
#.#...#.......#...#.#.#...#.#...#...#.....#.........#...>.>...#...###...#.........#...###...#.#.#...#...#...#.#.#.#.#.#.#...#.....#...###.#.#
#.#############.#.#.#.#.###.#.#####.#######.#########.###v###.#######.#############.#.###.###.#.#######.#.#.#.#.#.#.#.#.#.#.#.###.#.#####.#.#
#.#.............#...#.#...#.#...#...###.....###...#...#...###...###...#...........#.#...#...#.#.....#...#.#.#.#.#.#.#...#.#...###...#...#...#
#.#.#################.###.#.###.#.#####.#######.#.#.###.#######.###.###.#########.#.###.###.#.#####.#.###.#.#v#.#.#.#####.###########.#.#####
#...#...###...........#...#...#.#.....#.....###.#.#.#...#...###...#...#.#.........#...#...#.#.#...#.#.#...#.>.>.#.#.....#.............#.....#
#####.#.###v###########.#####.#.#####.#####.###.#.#.#.###.#.#####.###.#.#.###########.###.#.#.#.#.#.#.#.#####v###.#####.###################.#
#.....#...#.>...###...#.....#.#.#.....#...#.#...#...#...#.#.....#.###...#.....###...#...#.#.#.#.#.#.#...#...#.###...#...#...........#.......#
#.#######.#v###.###.#.#####.#.#.#.#####.#.#v#.#########.#.#####.#.###########.###.#.###.#.#.#.#.#.#.#####.#.#.#####.#.###.#########.#.#######
#.#.....#.#...#.#...#.#...#.#.#.#.#...#.#.>.>.#.....#...#.#.....#.....#.....#.#...#.....#.#.#.#.#.#.#.....#...#...#...#...#.......#...#...###
#.#.###.#.###.#.#.###.#.#.#.#.#.#.#.#.#.###v###.###.#.###.#.#########.#.###.#.#.#########.#.#.#.#.#.#.#########.#.#####.###.#####.#####.#.###
#...###.#.....#...#...#.#.#.#.#.#.#.#...###.###.#...#...#.#...#...#...#...#.#.#...###...#...#...#...#...........#...###.....#.....#...#.#...#
#######.###########.###.#.#.#.#.#.#.#######.###.#.#####.#.###.#.#.#.#####.#.#v###.###.#.###########################.#########.#####.#.#.###.#
#.......#...#...###...#.#.#.#.#.#.#.###...#.....#.#...#.#.###...#.#...#...#.>.>...#...#.#.......###...###...#.....#.#.........###...#...#...#
#.#######.#.#.#.#####.#.#.#.#.#.#.#.###.#.#######.#.#.#.#.#######.###.#.#####v#####.###.#.#####.###.#.###.#.#.###.#.#.###########.#######.###
#.........#...#...###...#...#...#...#...#...#...#...#.#...#.......###.#.....#...###.#...#.#.....#...#.....#...###...#.............#.......###
#################.###################.#####.#.#.#####.#####.#########.#####.###.###.#.###.#.#####.#################################.#########
#.......#...#.....#...#...###...#...#.....#...#.#...#.....#.........#.#.....###...#.#.###.#.#...#...#.....#.......#...#...#.........#...#####
#.#####.#.#.#.#####.#.#.#.###.#.#.#.#####.#####.#.#.#####.#########.#.#.#########.#.#.###.#.#.#.###.#.###.#.#####.#.#.#.#.#.#########.#.#####
#.#...#...#.#.#...#.#.#.#...#.#.#.#.#.....#...#...#.....#.#.........#...###...###...#.....#...#.###...###...#.....#.#.#.#.#...........#.....#
#.#.#.#####.#.#.#.#.#.#.###.#.#.#.#.#.#####.#.#########.#.#.###############.#.#################.#############.#####.#.#.#.#################.#
#...#.....#...#.#.#.#.#.#...#.#.#.#.#...#...#.......###...#...............#.#.#.........#...#...#.....#.....#...#...#.#.#.###...#...#.......#
#########.#####.#.#.#.#.#.###.#.#.#.###.#.#########.#####################.#.#.#.#######.#.#.#.###.###.#.###.###.#.###.#.#.###v#.#.#.#.#######
#.........#...#.#.#.#.#.#.###.#.#.#.###.#...#.......#...#...........#...#...#.#.......#...#.#.###...#.#...#.#...#...#.#.#.#.>.#...#...#...###
#.#########.#.#.#.#.#.#.#.###.#.#.#.###v###.#.#######.#.#.#########.#.#.#####.#######.#####.#.#####.#.###.#.#.#####.#.#.#.#.#v#########.#.###
#.#.....#...#...#...#.#.#.#...#.#.#...>.>...#.......#.#.#.........#...#.......#...#...#...#...#...#.#.....#...#...#.#.#.#...#...........#...#
#.#.###v#.###########.#.#.#.###.#.#####v###########.#.#.#########.#############.#.#.###.#.#####.#.#.###########.#.#.#.#.###################.#
#.#.###.>.#...#...###...#.#.#...#.#.....###.....#...#.#.#.......#...#...#.....#.#.#.....#.......#.#.........#...#...#.#.#...........#.......#
#.#.###v###.#.#.#.#######.#.#.###.#.#######.###.#.###.#.#.#####.###.#.#.#.###.#.#.###############.#########.#.#######.#.#.#########.#.#######
#...#...#...#.#.#.......#...#.....#.#.....#...#...###.#.#.....#.#...#.#.#.#...#.#.###.............#...#.....#.......#.#.#.........#.#.....###
#####.###.###.#.#######.###########.#.###.###.#######.#.#####.#.#.###.#.#.#.###.#.###v#############.#.#.###########.#.#.#########.#.#####.###
#...#.....###.#.#.......#.........#...#...###...#...#.#.#...#.#.#...#.#.#.#...#.#...>.>.###...#...#.#.#...#...#...#.#...###.......#.....#...#
#.#.#########.#.#.#######.#######.#####.#######.#.#.#.#.#.#.#.#.###v#.#.#.###.#.#####v#.###.#.#.#.#.#.###v#.#.#.#.#.#######.###########.###.#
#.#...........#.#...###...#...#...#.....#...###.#.#.#.#.#.#...#...>.>.#.#.###.#.#.....#.....#.#.#...#.#.>.>.#...#.#...#.....#...#...###...#.#
#.#############.###.###.###.#.#.###.#####.#.###.#.#.#.#.#.#########v###.#.###.#.#.###########.#.#####.#.#v#######.###.#.#####.#.#.#.#####.#.#
#.#...#.....#...###.....#...#...###.......#...#.#.#.#.#...###...#...###.#.#...#.#.........#...#...#...#.#.#...###.....#.......#...#.....#.#.#
#.#.#.#.###.#.###########.###################.#.#.#.#.#######.#.#.#####.#.#.###.#########.#.#####.#.###.#.#.#.#########################.#.#.#
#...#.#.#...#.#.........#.###...#.............#.#.#.#...#.....#.#.....#...#.....#.......#.#...#...#...#.#.#.#...###.....#...............#.#.#
#####.#.#.###.#.#######.#.###.#.#.#############.#.#.###.#.#####.#####.###########.#####.#.###.#.#####.#.#.#.###.###.###.#.###############.#.#
#.....#.#.....#.......#.#...#.#.#.............#...#.....#.....#.#...#.#...#####...#...#...###.#.#...#...#...###.....#...#...............#...#
#.#####.#############.#.###.#.#.#############.###############.#.#.#.#.#.#.#####.###.#.#######.#.#.#.#################.#################.#####
#.......###...#...#...#.....#.#.....#.........#...###.........#...#...#.#.###...#...#...#...#...#.#...#.....#.......#.#...#.......#...#.....#
###########.#.#.#.#.#########.#####.#.#########.#.###.#################.#.###.###.#####.#.#.#####.###.#.###.#.#####.#.#.#.#.#####.#.#.#####.#
#...........#.#.#...#.....#...#.....#...........#...#.......###.....#...#...#...#.....#.#.#.#...#.#...#...#.#.....#...#.#.#.....#.#.#...#...#
#.###########.#.#####.###.#.###.###################.#######.###.###.#.#####.###.#####.#.#.#.#.#.#.#.#####.#.#####v#####.#.#####v#.#.###.#.###
#...........#.#.......#...#...#.###...#.......#.....#.......#...#...#...#...#...#.....#...#.#.#...#.#.....#.....>.>.#...#.#...>.#.#...#...###
###########.#.#########.#####.#.###.#.#v#####.#.#####.#######.###.#####.#.###v###.#########.#.#####.#.###########v#.#.###.#.###v#.###.#######
#...........#...........#.....#...#.#.>.>.###.#.#...#.......#...#.#.....#...>.>.#.....#.....#.....#...#...###...#.#.#...#...#...#...#.......#
#.#######################.#######.#.###v#.###.#.#.#.#######.###.#.#.#########v#.#####.#.#########.#####.#.###.#.#.#.###.#####.#####.#######.#
#...........#.......#...#.......#.#.#...#...#...#.#.#...###.#...#.#.#.........#.#...#.#.#...#...#.#.....#.....#...#...#.#.....#####.#.......#
###########.#.#####.#.#.#######.#.#.#.#####.#####.#.#.#.###v#.###.#.#.#########.#.#.#.#.#.#.#.#.#.#.#################.#.#.#########.#.#######
#...###...#.#.#.....#.#.#.....#.#.#.#.#...#...#...#.#.#.#.>.>.###...#.........#...#...#...#.#.#...#.................#...#.......###...#...###
#.#.###.#.#.#.#.#####.#.#.###.#.#.#.#.#.#.###.#.###.#.#.#.#v#################.#############.#.#####################.###########.#######.#.###
#.#.....#.#...#.#...#.#...###.#.#.#.#.#.#...#...#...#.#.#.#...#.......#.......#...###...###...###...#...............#.....#...#.....#...#...#
#.#######.#####.#.#.#.#######.#.#.#.#.#.###.#####.###.#.#.###.#.#####.#.#######.#.###.#.#########.#.#.###############.###.#.#.#####.#.#####.#
#.......#.....#.#.#.#.......#...#.#.#.#.###.....#...#.#.#.#...#.#.....#.....###.#.#...#...###.....#.#...............#...#...#.......#.#.....#
#######.#####.#.#.#v#######.#####.#.#.#.#######.###.#.#.#.#.###.#.#########.###.#.#.#####.###.#####.###############.###.#############.#.#####
#.......#.....#.#.#.>.....#.....#...#...###.....###.#.#...#...#.#.....#.....#...#...#...#...#.....#.............#...###...............#.....#
#.#######.#####.#.#v#####.#####.###########.#######.#.#######.#.#####.#.#####.#######.#.###.#####.#############.#.#########################.#
#.......#.#...#...#.....#.#...#...#.........###.....#.....#...#.#.....#.......#...#...#.....#.....#...#.....###...#.........................#
#######.#.#.#.#########.#.#.#.###.#.###########.#########.#.###.#.#############.#.#.#########.#####.#.#.###.#######.#########################
#.......#...#.###...#...#.#.#.#...#...........#.#...#...#.#.....#.......#.....#.#.#.........#.#.....#...###.....###...............#.........#
#.###########.###.#.#.###.#.#.#.#############.#.#.#.#.#.#.#############.#.###.#.#.#########.#.#.###############.#################.#.#######.#
#.#.........#...#.#...###...#...#...#.........#...#.#.#...#...........#.#...#...#...........#...#.............#.....#.............#.#.......#
#.#.#######.###.#.###############.#.#.#############.#.#####.#########.#.###.#####################.###########.#####.#.#############.#.#######
#.#.#.......###.#.#.....#...#...#.#.#...#.....#...#.#.#...#.........#.#.###.................#...#...........#.#.....#.#.....#...#...#.......#
#.#.#.#########.#.#.###.#.#.#.#.#.#.###.#.###.#.#.#.#.#.#.#########.#.#.###################.#.#.###########.#.#.#####.#.###.#.#.#.#########.#
#.#.#.......###.#.#.#...#.#.#.#.#.#.###...#...#.#.#...#.#.#...#.....#.#.#.........#.........#.#.....#.......#...#...#...###...#...#.....#...#
#.#.#######.###.#.#.#.###.#.#.#.#.#.#######.###.#.#####.#.#.#.#.#####.#.#.#######.#.#########.#####.#.###########.#.###############.###.#.###
#.#.#.......#...#.#.#.#...#.#.#.#.#.#.....#.....#...###.#.#.#...#...#...#...#...#...#...#...#.#.....#.......#...#.#.###.......#...#...#.#...#
#.#.#.#######.###.#.#.#.###.#.#.#.#.#.###.#########.###.#.#.#####.#.#######.#.#.#####.#.#.#.#.#.###########.#.#.#.#.###.#####.#.#.###.#.###.#
#.#.#.....###.....#.#.#...#.#.#.#.#.#.#...#.........#...#.#.......#...#...#...#.....#.#.#.#.#.#.#...###...#.#.#.#.#.#...#...#...#.#...#.....#
#.#.#####.#########.#.###.#.#.#.#.#.#.#.###v#########.###.###########.#.#.#########.#.#.#.#.#.#.#.#.###.#.#v#.#.#.#.#.###.#.#####.#.#########
#...#####...#...###.#.#...#.#.#.#.#.#.#...>.>...#...#.#...#...#...#...#.#.#.........#.#.#.#.#.#...#...#.#.>.>.#...#.#.....#.....#...###...###
###########.#.#.###.#.#.###.#.#.#.#.#.#####v###.#.#.#.#.###.#.#.#.#v###.#.#.#########.#.#.#.#.#######.#.###v#######.###########.#######.#.###
#...###.....#.#.#...#.#.###.#.#...#...###...#...#.#.#.#...#.#...#.>.>...#.#...#.....#.#.#.#...###...#...#...#.......#...........###...#.#.###
#.#.###v#####.#.#.###.#.###.#.###########.###.###.#.#.###.#.#######v#####.###.#.###.#.#.#.#######.#.#####.###.#######.#############.#.#.#.###
#.#.###.>.....#.#...#.#.#...#...#.........###...#.#.#...#...#...#...#.....#...#...#.#.#.#.....#...#...#...#...###...#.......#.....#.#.#.#.###
#.#.###v#######.###.#.#.#.#####.#.#############.#.#.###.#####.#.#.###.#####v#####.#.#.#.#####.#.#####.#.###.#####.#.#######v#.###.#.#.#.#.###
#.#.###.......#.....#.#.#.#.....#...........#...#.#.....###...#.#...#...#.>.>.#...#...#.....#.#.....#.#...#.#...#.#...#...>.#.#...#.#...#...#
#.#.#########.#######.#.#.#.###############.#.###.#########.###.###.###.#.#v#.#.###########.#.#####.#.###.#.#.#.#.###.#.###v#.#.###.#######.#
#.#...........###...#.#.#...#...###...#.....#...#.#.........###.#...#...#.#.#.#.#.........#.#...#...#...#.#...#.#...#.#.#...#.#.....#.....#.#
#.###############.#.#.#.#####.#.###.#.#.#######.#.#.###########.#.###.###.#.#.#.#.#######.#.###.#.#####.#.#####.###.#.#.#.###.#######.###.#.#
#.................#.#.#...#...#.#...#...#.....#...#...........#...###.....#.#...#.......#.#.....#.....#.#.#...#.#...#.#.#...#.###...#...#.#.#
###################.#.###.#.###.#.#######.###.###############.#############.###########.#.###########.#.#.#.#.#.#.###.#.###.#.###.#.###.#.#.#
#...................#.....#...#.#.........#...###...#.......#...#...#.......#...###.....#...###...#...#...#.#.#.#.#...#.#...#.#...#.....#.#.#
#.###########################.#.###########.#####.#.#.#####.###.#.#.#.#######.#.###.#######.###.#.#.#######.#.#.#.#.###.#.###.#.#########.#.#
#...#.......###.........#.....#...........#.#...#.#.#.....#.....#.#.#...#...#.#...#.....#...#...#...#...#...#.#.#.#.....#...#.#...#...###...#
###.#.#####.###.#######.#.###############.#.#.#.#.#.#####.#######.#.###.#.#.#.###.#####.#.###.#######.#.#.###.#.#.#########.#.###.#.#.#######
#...#.#.....#...#.......#...............#...#.#.#.#.#####.#.....#.#...#...#.#.#...#.....#...#.......#.#.#...#.#...#...#...#.#.###...#.......#
#.###.#.#####.###.#####################.#####.#.#.#.#####.#.###.#.###.#####.#.#.###.#######.#######.#.#.###.#.#####.#.#.#.#.#.#############.#
#.....#.....#...#.#.....#.......#.....#.#...#.#.#.#.......#.#...#.#...#...#...#...#.#.......#...###.#.#.###.#.###...#...#.#...#.............#
###########.###.#.#.###.#.#####.#.###.#.#.#.#.#.#.#########.#.###.#.###.#.#######.#.#.#######.#.###v#.#.###.#.###.#######.#####.#############
#.....#.....###.#.#.#...#.....#.#...#...#.#.#.#.#...........#...#.#.###.#.###...#.#.#.#...#...#.#.>.>.#.....#.....#.......#.....#...#...#...#
#.###.#.#######.#.#.#.#######.#.###v#####.#.#.#.###############.#.#.###.#.###.#.#.#.#.#.#.#.###.#.#################.#######.#####.#.#.#.#.#.#
#...#.#...#...#.#.#.#.#.....#.#.#.>.>.#...#.#.#...#...#.........#.#.#...#.#...#.#...#...#.#.###.#.#.............#...#.....#.......#...#...#.#
###.#.###.#.#.#.#.#.#.#.###.#.#.#.###.#.###.#.###.#.#.#.#########.#.#.###.#.###.#########.#.###.#.#.###########.#.###.###.#################.#
#...#.....#.#...#...#.#...#.#.#.#...#.#.###.#.#...#.#.#...###...#.#.#.#...#...#.#...#...#.#...#.#.#...........#...###.#...#...###...........#
#.#########.#########.###.#.#.#.###.#.#.###.#.#.###.#.###v###.#.#.#.#.#.#####.#.#.#.#.#.#v###.#.#.###########.#######.#.###.#.###.###########
#...#.....#.###...#...#...#...#...#.#.#.#...#.#...#.#.#.>.>.#.#.#.#...#.#...#.#.#.#.#.#.>.>.#.#...#...........###.....#.#...#...#...........#
###.#.###.#.###.#.#.###.#########.#.#.#.#.###.###.#.#.#.###.#.#.#.#####.#.#.#.#.#.#.#.#####.#.#####.#############.#####.#.#####.###########.#
#...#.#...#.....#.#...#.......#...#.#.#.#...#...#...#.#...#.#.#...#.....#.#.#.#.#.#.#.###...#.....#...............#.....#.....#.###...#.....#
#.###.#.#########.###.#######.#.###.#.#.###.###.#####.###.#.#.#####.#####.#.#.#.#.#.#.###.#######.#################.#########.#.###.#.#.#####
#.#...#.#...#...#.###.....#...#...#.#.#.###...#.#.....#...#.#.....#.#...#.#.#.#...#.#...#...#...#.###...#...........#...#####.#.###.#.#.#...#
#.#.###.#.#.#.#.#.#######.#.#####.#.#.#.#####.#.#.#####.###.#####.#.#.#.#.#.#.#####.###.###.#.#.#.###.#.#.###########.#.#####.#.###.#.#v#.#.#
#.#...#.#.#.#.#.#.......#.#...#...#.#.#.#.....#.#.....#.###.#...#.#...#.#.#.#.....#.#...#...#.#.#.#...#...#.....#...#.#...#...#...#.#.>.#.#.#
#.###.#.#.#.#.#.#######.#.###.#.###.#.#.#.#####.#####.#.###.#.#.#.#####.#.#.#####.#.#.###.###.#.#.#.#######.###.#.#.#.###.#.#####.#.###v#.#.#
#...#.#.#.#.#.#.#.....#.#.#...#...#.#.#.#.#...#.#.....#...#.#.#.#.#.....#.#.#...#.#.#...#.#...#.#.#...#...#.#...#.#.#.#...#.....#.#.###.#.#.#
###.#.#.#.#.#.#.#.###.#.#.#.#####.#.#.#.#.#.#.#.#.#######.#.#.#.#.#.#####.#.#.#.#.#.###.#.#.###.#.###.#.#.#.#.###.#.#.#.#######.#.#.###.#.#.#
###...#...#...#...###...#...#####...#...#...#...#.........#...#...#.......#...#...#.....#...###...###...#...#.....#...#.........#...###...#.#
###########################################################################################################################################.#
";The output after ~20 seconds of crunching is:
found 252 paths
lengths: [1418, 1426, 1430, 1450, 1450, 1454, 1458, 1462, 1466, 1478, 1478, 1482, 1486, 1486, 1486, 1490, 1494, 1498, 1498, 1498, 1510, 1510, 1510, 1514, 1514, 1514, 1506, 1518, 1518, 1522, 1522, 1526, 1526, 1530, 1534, 1526, 1526, 1530, 1526, 1538, 1538, 1538, 1542, 1546, 1546, 1546, 1546, 1550, 1550, 1554, 1558, 1558, 1558, 1566, 1570, 1570, 1570, 1570, 1570, 1562, 1538, 1574, 1574, 1542, 1578, 1582, 1582, 1586, 1586, 1586, 1586, 1554, 1590, 1590, 1594, 1558, 1558, 1562, 1598, 1598, 1598, 1598, 1602, 1606, 1606, 1606, 1610, 1618, 1618, 1618, 1622, 1630, 1638, 1586, 1578, 1582, 1630, 1630, 1574, 1622, 1634, 1590, 1634, 1642, 1642, 1646, 1646, 1666, 1674, 1706, 1710, 1714, 1566, 1626, 1606, 1650, 1662, 1722, 1722, 1574, 1634, 1614, 1658, 1670, 1738, 1742, 1746, 1622, 1666, 1678, 1766, 1770, 1770, 1770, 1638, 1646, 1654, 1598, 1606, 1638, 1650, 1646, 1658, 1638, 1682, 1682, 1602, 1662, 1690, 1690, 1690, 1694, 1694, 1662, 1698, 1678, 1702, 1702, 1706, 1710, 1718, 1738, 1774, 1618, 1678, 1786, 1734, 1738, 1750, 1782, 1626, 1686, 1794, 1794, 1798, 1798, 1802, 1802, 1806, 1634, 1694, 1814, 1818, 1818, 1822, 1826, 1830, 1650, 1658, 1666, 1710, 1618, 1666, 1678, 1658, 1718, 1718, 1650, 1710, 1726, 1842, 1850, 1706, 1750, 1762, 1862, 1866, 1866, 1674, 1734, 1922, 1950, 1978, 2006, 2010, 2090, 2274, 1750, 1798, 1810, 1810, 1822, 1834, 1862, 1994, 2038, 1682, 1726, 1738, 1902, 1914, 1718, 1778, 2130, 2210, 2330, 1814, 1858, 1870, 1846, 1878, 1906, 1922, 1694, 1754, 1934, 2090, 2118, 1826, 1886, 1890, 1950]
last: 1950
max: 2330
Which, as you can see, does not have the maximum length of 2330 at the end of the returned paths.
(Sorry for the terrible example. I couldn't reproduce this with the sample input on that puzzle, and couldn't figure out a shorter or faster example... besides this being a terrible solution for this puzzle 😅)
I think this specific example would be fixed by adding a routes.sort_by_key(|path| path.cost) here. But i don't know if a naive fix like that would still guarantee that algorithm is returning the k-shortest paths in the case of k < total possible paths.
samueltardieu commented
The optimization made in 2ac3972 was wrong and was not caught by the existing tests. I will try to produce a shorter test which exhibits this bogus behavior to illustrate this.
Thanks for the report!
samueltardieu commented
Fixed in pathfinding 4.8.1. Thanks!
epidemian commented
Wow that was too fast of a fix! Thanks!
Oh gods, now my dog-slow and ugly code lives in this repo 🙈