(See the next iteration.) Problem definition We are given an undirected graph \$G = (V, E)\$ and a weight function \$w \colon E \to (0, 1]\$. The weight of the edge \$e \in E\$, \$w(e)\$, describes its reliability, or, in other words, the probability that the edge is available. Given two distinguished nodes \$s, t \in V\$, we wish to compute a most reliable \$s,t\$ - path. There is, however, a catch: the cost of a path \$(v_1, \dots, v_k)\$ is $$\prod_{i = 1}^{k-1} w(v_i, v_{i + 1})$$ and not $$\sum_{i = 1}^{k-1} w(v_i, v_{i + 1}).$$ There is however a trick to remember: Prior to computing the path, set for each edge \$e\$ \$w(e) \leftarrow \log_d w(e)\$, where \$d \in (0, 1)\$. Then, compute the ordinary shortest path in the same graph using the modified weight function. Next, suppose \$P = (v_1, \dots, v_k)\$ is a shortest path in the graph. You return \$P\$ as is, and you return as its cost \$d^{c(P)}\$, where $$ c(P) = \sum_{i = 1}^{k - 1} w(v_i, v_{i + 1}) $$ is the cost of \$P\$ in the modified graph. Solution MostReliablePathFinder.java ``` package net.coderodde; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.PriorityQueue; import java.util.Queue; import java.util.Set; public final class MostReliablePathFinder { Path findLeastReliablePath( UndirectedGraphNode source, UndirectedGraphNode target, UndirectedGraphProbabilisticWeightFunction weightFunction) { weightFunction = weightFunction.normalize(); Queue open = new PriorityQueue<>(); Set closed = new HashSet<>(); Map parents = new HashMap<>(); Map distance = new HashMap<>(); open.add(new NodeHolder(source, 0.0)); parents.put(source, null); distance.put(source, 0.0); while (!open.isEmpty()) { UndirectedGraphNode currentNode = ope

The goal of my code was to find all possible moves from each open position in the maze (`@moves_hash`), assign it a value for how many moves it would take to get to that position (`@distance_hash`), then going backwards from the end_position pick moves that have the lowest distance back to the start point. How can I make my code more readable and better formatted? I'm currently reading through Practical Object Oriented Design in Ruby, but am unsure how to apply certain principles from the book. Should I have created another class or are there other methods I should breakdown to have less dependency? What other types of ways could I make my code easier to understand, be reusable, and have less risk of bugs? ``` class Maze attr_reader :maze def initialize(maze) @maze = maze @current_position = find_start_point @start_position = find_start_point @end_position = find_end_point @moves_hash = Hash.new @distance_hash = Hash.new @moves = [method(:move_up),method(:move_right),method(:move_down),method(:move_left)] @allpossiblemoves = allpossiblemoves end def update_moves_hash(parent) possiblemoves = Array.new @moves.each do |x| nextmove = x.call(parent) possiblemoves << nextmove if possible_move?(nextmove) @moves_hash[parent] = possiblemoves end end def fill_moves_hash count = 0 until @allpossiblemoves.count+1 == @moves_hash.keys.count @moves_hash.values.each do |y| y.each {|x| update_moves_hash(x) if !@moves_hash.keys.include? y} y.each {|x| update_distance(x,count) } end count += 1 end end def update_distance(pos,count) @distance_hash[pos] = count if @distance_hash[pos] == nil end def allpossiblemoves list = Array.new @maze.each_index do |x| @maze[x].each_index { |y| list << [x,y] if @maze[x][y] == " " } end list end def [](pos) row,col = pos @maze[row][col] end def []=(pos,val) row,col = pos

I would like my solution to Google Foobar's `prepare_the_bunnies_escape` checked for readability, maintainability, extensibility, style, design. I am looking forward to reading your suggestions on any of these aspects! Feel free to comment on other aspects as well. Problem Link to full problem statement Summary You are given an HxW matrix of 0's and 1's, m, where 0's indicate traversable cells and 1's indicate nontraversable cells (i.e. walls). start denotes the cell at coordinate (0, 0) and end denotes the cell at coordinate (H-1, W-1). start and end are always traversable. Given that you can remove one wall making it traversable, find the distance of a shortest path from start to end. Test cases Inputs: ``` m = [ [0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0] ] ``` Outputs: ``` 7 ``` Inputs: ``` m = [ [0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0] ] ``` Outputs: ``` 11 ``` Inputs: ``` m = [ [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 1, 0], [1, 1, 1, 1, 1, 0, 1, 1, 0], [1, 1, 1, 1, 1, 0, 1, 1, 1], [0, 0, 0, 0, 0, 0, 1, 1, 0], [0, 1, 1, 1, 1, 1, 1, 1, 0], [0, 1, 1, 1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0] ] ``` Outputs: ``` 16 ``` Inputs: ``` m = [ [0], [1], [0] ] ``` Outputs: ``` 3 ``` Inputs: ``` m = [ [0, 0, 0, 0], [1, 1, 1, 0], [1, 0, 1, 0], [1, 1, 1, 0], [1, 0, 0, 0], [1, 0, 1, 1], [1, 0, 0, 0] ] ``` Outputs: ``` 10 ``` My Algorithm Find and store `start.minDistTo`, the minimum distance from start to each cell. Do likewise for end, that is, find and store `end.minDistTo`, the minimum distance from end to each cell. Now, for each wall in m, use `start.minDistTo` and `end.minDistTo` to see if you can get a shorter path b

I want to assign corresponding variables based on the name to save each directory from a folder, including its subfolders, so I can get access to the file in each folder easily. The code created by myself doesn't look concise. Any suggestions? ``` import os modelFld = r'C:\model' baseInputFld = [os.path.join(modelFld, x) for x in os.listdir(modelFld) if 'base' in x.lower()][0] oilWellFld = [os.path.join(baseInputFld, x) for x in os.listdir(baseInputFld) if 'oilwell' in x.lower()][0] diswaterWellFld = [os.path.join(baseInputFld, x) for x in os.listdir(baseInputFld) if 'waterwell' in x.lower()][0] quarryFld = [os.path.join(baseInputFld, x) for x in os.listdir(baseInputFld) if 'quar' in x.lower()][0] linearRefFld = [os.path.join(baseInputFld, x) for x in os.listdir(baseInputFld) if 'linear' in x.lower()][0] txCountyFld = [os.path.join(baseInputFld, x) for x in os.listdir(baseInputFld) if 'county' in x.lower()][0] tigerFld = [os.path.join(baseInputFld, x) for x in os.listdir(baseInputFld) if 'tiger' in x.lower()][0] step1Fld = [os.path.join(modelFld, x) for x in os.listdir(modelFld) if 'step1' in x.lower()][0] step2Fld = [os.path.join(modelFld, x) for x in os.listdir(modelFld) if 'step2' in x.lower()][0] step3Fld = [os.path.join(modelFld, x) for x in os.listdir(modelFld) if 'step3' in x.lower()][0] step4Fld = [os.path.join(modelFld, x) for x in os.listdir(modelFld) if 'step4' in x.lower()][0] step5Fld = [os.path.join(modelFld, x) for x in os.listdir(modelFld) if 'step5' in x.lower()][0] step6Fld = [os.path.join(modelFld, x) for x in os.listdir(modelFld) if 'step6' in x.lower()][0] step1InputFld = [os.path.join(step1Fld, x) for x in os.listdir(step1Fld) if 'input' in x.lower()][0] step2InputFld = [os.path.join(step2Fld, x) for x in os.listdir(step2Fld) if 'input' in x.lower()][0] step3InputFld = [os.path.join(step3Fld, x) for x in os.listdir(step3Fld) if 'input' in x.lower()][0] step4InputFld = [os.path.join(step4Fld, x) for x in os.listdir(step4Fld) if 'input' in

I have been working on Google Foobar since a few days ago. I am currently in the third level but is stuck in the second challenge of "Prepare the Bunnies' Escape." I have checked this post but it did not fully resolve my problem in Google Foobar as it is still giving me `Time limit exceeded` errors. For reference, here is the challenge. Prepare the Bunnies' Escape You have maps of parts of the space station, each starting at a prison exit and ending at the door to an escape pod. The map is represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls. The door out of the prison is at the top left \$(0,0)\$ and the door into an escape pod is at the bottom right \$(w-1,h-1)\$. Write a function `answer(map)` that generates the length of the shortest path from the prison door to the escape pod, where you are allowed to remove one wall as part of your remodeling plans. The path length is the total number of nodes you pass through, counting both the entrance and exit nodes. The starting and ending positions are always passable (0). The map will always be solvable, though you may or may not need to remove a wall. The height and width of the map can be from 2 to 20. Moves can only be made in cardinal directions; no diagonal moves are allowed. Test cases Input: ``` maze = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]] ``` Output: ``` 7 ``` Input: ``` maze = [[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]] ``` Output: ``` 11 ``` What I have done is create a graph based on the matrix and apply the shortest path algorithm (I am not sure what the algorithm is exactly called). The code I have below runs and gives me the proper length of the shortest path. ``` class Node(object): def __init__(self, identity, x, y): self.neighbours = [] self.identity = identity s

I'm implementing Dijkstra's algorithm with a priority queue for a game I'm developing in Unity with C#. I was a bit disappointed with the performance, so I decided to port the code to C++ and see if the performance was related to the language or the algorithm itself. The path finding searches through a 3D grid and selects certain edges/neighbours based on some extra criteria (cell filter). The problem is that this grid contains only 3000 cells, and the C# algorithm takes 38 ms to find a path. The C++ version takes just 2 ms to do the exact same thing! The two source files of the algorithm are below and I'm wondering if someone experienced with C# can point out if I've done anything horribly inefficient or if C# is just slower here. The C# version stores the grid as a multidimensional array and the C++ version simulates it with an extra `get_index` function that computes an index into a vector using the x, y and z coordinates. I simulate a priority queue in C# by using a `SortedSet` with a special queue node containing both the value and the priority value (`dist`). Both algorithms simulate updating the priority queue by just appending a new value that invalidates the old one. This is done by also storing the priorities in the `dist` hash table. C#: ``` using System; using System.Collections.Generic; using System.IO; namespace PathFinding.NET { struct Vec3 { public int x, y, z; public Vec3(int x, int y, int z) { this.x = x; this.y = y; this.z = z; } public static Vec3 operator +(Vec3 a, Vec3 b) { return new Vec3(a.x + b.x, a.y + b.y, a.z + b.z); } public static bool operator ==(Vec3 a, Vec3 b) { return a.x == b.x && a.y == b.y && a.z == b.z; } public static bool operator !=(Vec3 a, Vec3 b) { return !(a == b); } public static float Dist(Vec3 a, Vec3 b) { int dx = a.x - b.x; int dy

This is my first attempt at writing something useful in F# and in a functional way in general. I would appreciate if you could point out any issue, even details, as I'd like to put all the bad habits aside as soon as possible. I tried to leave my OOP comfort zone when I wrote this but I feel like this is not enough. I would love to hear suggestions about how to make this code more functional. Please consider that the code in Program.fs is for testing only and has a lot of ugly stuffs in it (magic numbers, poor logic). I've put it here so that you can see how the code in Pathfinding.fs is used. The code in `main` creates the following grid with 10 rows and 10 columns and sets which nodes are obstacles: ``` 0 1 . . . 9 10 19 . . . . . . 90 91 . . . 99 ``` Pathfinding.fs ``` module Pathfinding //Classic Vector2 type with distances calculation type Vector2 = { mutable X : float; mutable Y : float; } with member this.EuclideanDistance(otherVector:Vector2) = let distanceX = otherVector.X - this.X let distanceY = otherVector.Y - this.Y sqrt (distanceX * distanceX + distanceY * distanceY) member this.ManhattanDistance(otherVector:Vector2) = let distanceX = abs (otherVector.X - this.X) let distanceY = abs (otherVector.Y - this.Y) distanceX + distanceY // Open = Available to get chosen as the starting point for a new recursion // Closed = Already used during one recursion, not available anymore // NotUsed = Ready to be opened, never used before // Obstacle = Can't be used and won't be reset type NodeState = Open = 0 | Closed = 1 | NotUsed = 2 | Obstacle = 3 //A possible point on paths type Node = { mutable g : float; //Sum of the distances between each nodes from the starting node to this one, following the parents mutable h : float; //Sum of all the manhattan distance of the parents nodes and this node

Background I have decided to use this year's Advent Of Code to learn Haskell. I feel like I vaguely understand the language and can solve most of the problems with relative ease. However, the code I produce is not the most readable and possibly has inefficiencies. Any suggestions on how to improve readability and performance would be much appreciated. Problem The problem is Day 13 of AoC. It consists of a maze where each cell `(x,y)` is either a wall or an empty space, dictated by the population count of the following equation: ``` x*x + 3*x + 2*x*y + y + y*y + key (where key is some arbitrary integer) ``` The cell is a wall if the population count is odd. The problem then comes in two parts: - Find shortest distance between `(1,1)` and `(31,39)`. - Find number of cells that can be visited in 50 or less steps (from `(1,1)`). Code The code uses BFS for both parts. I am aware that A* may quicker for Part1. ``` import Data.Bits (popCount) import qualified Data.Map as Map import Debug.Trace -- Define all types type Index = (Int, Int) -- (x,y) type Edges = [Index] -- list of connecting edges type Prob = (Int, Int, Int) -- (key, width, height) type State = (Index, Int, Map.Map Index Bool) -- (current, steps, visited) -- Determine if a specific cell index represents a wall isWall :: Int -> Index -> Bool isWall key (x,y) = odd $ popCount num where num = x*x+3*x+2*x*y+y+y*y+key -- Generate all edges of a specific cell mkEdges :: Int -> Index -> Edges mkEdges key (x,y) = filter (not.isWall key) adjs where adjs = wB [(x, y-1), (x+1, y), (x,y+1), (x-1,y)] wB = filter (\(a,b) -> not (a Index -> [State] -> Int bfsPathLength key goal t@((curr, steps, visited):rest) | goal==curr = steps | otherwise = bfsPathLength key goal newStates where newStates = (filter (not.isQueued) $ filter (not.isVisited) $

This is the Google Foobar puzzle "Prepare the Bunnies' Escape": You have maps of parts of the space station, each starting at a prison exit and ending at the door to an escape pod. The map is represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls. The door out of the prison is at the top left \$(0,0)\$ and the door into an escape pod is at the bottom right \$(w-1,h-1)\$. Write a function `answer(map)` that generates the length of the shortest path from the prison door to the escape pod, where you are allowed to remove one wall as part of your remodeling plans. The path length is the total number of nodes you pass through, counting both the entrance and exit nodes. The starting and ending positions are always passable (0). The map will always be solvable, though you may or may not need to remove a wall. The height and width of the map can be from 2 to 20. Moves can only be made in cardinal directions; no diagonal moves are allowed. Test cases Input: ``` maze = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]] ``` Output: ``` 7 ``` Input: ``` maze = [[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]] ``` Output: ``` 11 ``` My approach is to make a list of removable walls and then by removing them one at a time in a loop, do a BFS for the shortest path. At the end, I return the shortest path overall. I have the following code that works. However, when I deal with larger matrices, it becomes very slow and I can't get past the test code due to exceeding the time limit. I was wondering if there is a problem in my algorithm or there would be a better approach to this problem. ``` class Queue: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def enqueue(self, item): self.items.insert(0,item) def dequeue(self): return self.items.pop() def size(self): retur

The puzzle goes like this: in a rectangular 2D grid there are empty spaces (`.`), exactly one starting point (`S`, `s`) and obstacles (denoted below by `X`'s). The objective of the puzzle is to find a path starting at the starting point and going through each empty space exactly once (a Hamiltonian path). You can't, of course cross the obstacles. You can move horizontally and vertically. A typical puzzle would look like this: ``` ...... .SX... ...X.. .....X ...... XX.... ...... ``` And its solution: ``` 11 12 13 14 17 18 10 1 X 15 16 19 9 2 3 X 21 20 8 5 4 23 22 X 7 6 25 24 29 30 X X 26 27 28 31 37 36 35 34 33 32 ``` I wrote a solver in Python 3 (I later learned that this algorithm is actually a simple DFS). It solves the puzzle above in ~0.9 s, which is very good, but I was wondering if I can perhaps optimize it somehow. ``` import time EMPTY_SPACE_SYMBOLS = ['.'] STARTING_POINT_SYMBOLS = ['S', 's'] OBSTACLE_SYMBOL = 'X' PUZZLE_PATH = "grid.txt" DIRS = [(-1, 0), (1, 0), (0, 1), (0, -1)] start_time = time.time() grid = open(PUZZLE_PATH).read().splitlines() H = len(grid) W = len(grid[0]) assert all(len(row) == W for row in grid), "Grid not rectangular" def print_solution(coords): result_grid = [[OBSTACLE_SYMBOL for _ in range(W)] for _ in range(H)] for i, (r, c) in enumerate(coords, start=1): result_grid[r][c] = i str_grid = [[str(item).ljust(3) for item in row] for row in result_grid] print('\n'.join(' '.join(row) for row in str_grid)) def extend(path, legal_coords): res = [] lx, ly = path[-1] for dx, dy in DIRS: new_coord = (lx + dx, ly + dy) if new_coord in legal_coords and new_coord not in path: res.append(path + [new_coord]) return res start_pos = None legal = set() for r, row in enumerate(grid): for c, item in enumerate(row): if item in STARTING_POINT_SYMBOLS: assert start_pos is None, "Multiple starting points" start_pos = (r, c)