\nToday’s Little Program solves the following problem:\n<\/p>\n
\nConsider a two-dimensional board, tall and narrow.\nInto the board are nailed a number of horizontal obstacles.\nPlace a water faucet at the top of the board and turn it on.\nThe water will dribble down, and when it hits an obstacle,\nsome of the water will go left and some will go right.\nThe goal is to find the shortest path to the ground from a given\nstarting position,\ncounting both horizontal and vertical distance traveled.\n<\/p><\/blockquote>\n
\n⬤<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n•<\/div>\n<\/div>\n\nIn the above diagram,\nthe water falls three units of distance\nuntil it encounters Obstacle 1,\nat which some goes to the left and some goes to the right.\nThe water that goes to the left travels three units of distance\nbefore it reaches the\nend of the obstacle,\nthen falls three units and encounters\nObstacle 2.\nUpon reaching Obstable 2,\nthe water can again choose to flow either left or right.\nThe water that flows to the left falls to the ground;\nthe water that flows to the right falls and encounters\na third obstacle.\nFrom the third obstacle,\nthe water can flow left or right, and either way it goes,\nit falls to the ground.\nOn the other hand, the water that chose to flow to the right\nwhen it encountered Obstable 1 iwould fall past Obstacle 2\n(which is not in a position to intercept the water)\nand land directly on Obstacle 3.\n<\/p>\n
\nIn the above scenario, there are five paths to the ground.\n<\/p>\n
\n
- From Obstacle 1, flow left, then from Obstacle 2,\n flow left again.\n Total distance traveled: 17 units.<\/p>\n
- From Obstacle 1, flow left, then from Obstacle 2,\n flow right,\n then from Obstacle 3, flow left.\n Total distance traveled: 18 units.<\/p>\n
- From Obstacle 1, flow left, then from Obstacle 2,\n flow right,\n then from Obstacle 3, flow right.\n Total distance traveled: 20 units.<\/p>\n
- From Obstacle 1, flow right, then from Obstacle 3,\n flow left.\n Total distance traveled: 16 units.<\/p>\n
- From Obstacle 1, flow right, then from Obstacle 3,\n flow right.\n Total distance traveled: 14 units.\n<\/ul>\n
\nIn this case, the shortest path to the ground\nis the last path.\n<\/p>\n
\nThere are many ways to attack this problem.\nThe brute force solution would be to enumerate all the possible\npaths to the ground, then pick the shortest one.\n<\/p>\n
\nA more clever solution would use a path-finding algorithm\nlike A*,\nwhere the altitude above the ground is the heuristic.\n<\/p>\n
\nIn both cases, you can add an optimization where once you\ndiscover two paths to the same point, you throw out the longer one.\nThis may short-circuit future computations.\n<\/p>\n
\nBut I’m going to use an incremental solution, since it\nhas the advantage of incorporating the optimization as\na convenient side-effect.\nInstead of studying individual drops of water,\nI’m going to study all of them at once.\nAt each step in the algorithm,\nthe data structures represent a horizontal cross-section\nof the above diagram,\nrepresenting all possible droplet positions at a fixed\naltitude.\n<\/p>\n
\nIn addition to collapsing redundant paths automatically,\nthis algorithm has the nice property that it can be done\nas an on-line algorithm:\nYou don’t need to provide all the obstacles in advance,\nas long as the obstacles are provided in order of decreasing altitude.\n<\/p>\n
\nInstead of presenting the raw code and discussing it later\n(as is my wont),\nI’ll explain the code as we go via code comments.\nWe’ll see how well that works.\n<\/p>\n
\nI originally wrote the program in C# because\nI thought I would need\none of the fancy collection classes provided by the BCL,\nbut it turns out that I didn’t need anything fancier than a hash table.\nAfter I wrote the original C# version, I translated it to JavaScript,\nwhich is what I present here.\n<\/p>\n
<!–<\/p>\n
\n\/\/ Oh you're so clever - you are doing a view.source to see the C# version.\n\/\/ You can put your finger by the side of your nose as a signal.\n\/\/ http:\/\/ask.metafilter.com\/4447\/\nusing System;\nusing System.Collections.Generic;\nusing System.Linq;\n\/\/ An Obstacle describes the position of a single obstacle\nclass Obstacle\n{\n public double Left { get; set; }\n public double Right { get; set; }\n public double Y { get; set; }\n}\n\/\/ A Step describes the last point in a path,\n\/\/ the cost to get there, and\n\/\/ a reference to the rest of the path.\nclass Step\n{\n public double X { get; set; }\n public double Y { get; set; }\n public double Cost { get; set; }\n public Step Previous { get; set; }\n \/\/ Add a step to an existing step\n public Step To(double x, double y, double incrementalCost)\n {\n return new Step { Previous = this, X = x, Y = y,\n Cost = Cost + incrementalCost };\n }\n}\n\/\/ Locations tracks all the possible droplet locations at a particular\n\/\/ altitude. The positions are indexed by X-coordinate for easy look-up.\nclass Locations : SortedList<double, Step>\n{\n \/\/ Record a droplet position\n public void Add(Step step)\n {\n \/\/ If no previous droplet at this position or the new droplet\n \/\/ has a cheaper path, then remember this droplet.\n if (!this.ContainsKey(step.X) || step.Cost < this[step.X].Cost)\n {\n this[step.X] = step;\n }\n }\n}\nstatic class Extensions\n{\n \/\/ Like Min, but returns the item with the minimum value rather than the\n \/\/ minimum value itself.\n public static T MinIndirect<T, V>(\n this IEnumerable<T> source,\n Func<T, V> func) where V : IComparable\n {\n return source.Aggregate(default(T), (sofar, next) =>\n (sofar == null || func(next).CompareTo(func(sofar)) < 0 ?\n next : sofar));\n }\n}\nclass Program\n{\n \/\/ Take an existing collection of locations and updates them to account\n \/\/ for a new obstacle. Obstacles must be added in decreasing altitude.\n \/\/ (Consecutive duplicate altitudes allowed.)\n static Locations FallTo(Locations oldLocations, Obstacle obstacle)\n {\n Locations newLocations = {};\n foreach (var pair in oldLocations)\n {\n var step = pair.Value;\n var dy = step.Y - obstacle.Y; \/\/ distance fallen\n if (dy > 0)\n {\n \/\/ fall to the obstacle's altitude\n step = step.To(step.X, obstacle.Y, dy);\n }\n \/\/ If the falling object does not hit the obstacle,\n \/\/ then there is no horizontal displacement.\n if (step.X <= obstacle.Left || step.X >= obstacle.Right)\n {\n newLocations.Add(step);\n }\n else\n {\n \/\/ The falling object hit the obstacle.\n \/\/ Split into two droplets, one that goes left\n \/\/ and one that goes right.\n newLocations.Add(step.To(obstacle.Left, obstacle.Y,\n step.X - obstacle.Left));\n newLocations.Add(step.To(obstacle.Right, obstacle.Y,\n obstacle.Right - step.X));\n }\n }\n return newLocations;\n }\n static void PrintPath(Step firstStep)\n {\n System.Console.Write(\"Cost = {0}: \", firstStep.Cost);\n \/\/ Walk the path backwards, then reverse it so we can print\n \/\/ the results forward.\n var path = new List<Step>();\n for (var step = firstStep; step != null; step = step.Previous)\n {\n path.Add(step);\n }\n path.Reverse();\n foreach (var step in path)\n {\n System.Console.Write(\"({0},{1}) \", step.X, step.Y);\n }\n System.Console.WriteLine();\n }\n \/\/ Debugging function\n static void PrintLocations(Locations l)\n {\n foreach (var pair in l)\n {\n PrintPath(pair.Value);\n }\n }\n static void Main()\n {\n var l = {};\n System.Console.Write(\"Initial X position: \");\n var x = double.Parse(System.Console.ReadLine());\n System.Console.Write(\"Initial Y position: \");\n var y = double.Parse(System.Console.ReadLine());\n l[x] = new Step { X = x, Y = y };\n for (;;)\n {\n PrintLocations(l);\n System.Console.Write(\"Obstacle height (0 = floor): \");\n y = double.Parse(System.Console.ReadLine());\n if (y == 0) break;\n System.Console.Write(\"Obstacle Left edge: \");\n var left = double.Parse(System.Console.ReadLine());\n System.Console.Write(\"Obstacle Right edge: \");\n var right = double.Parse(System.Console.ReadLine());\n l = FallTo(l, new Obstacle { Left = left, Right = right, Y = y });\n }\n \/\/ Find the cheapest step.\n var best = l.Values.MinIndirect(s => s.Cost);\n \/\/ Add a segment from the last obstacle to the floor and print it.\n PrintPath(best.To(best.X, 0, best.Y));\n }\n}\n<\/pre>\n–><\/p>\n
\nThe inputs which correspond to the diagram above are\n<\/p>\n
\n
- Initial X position = 6, Initial Y position = 12\n
- Obstacle: Left = 3, Right = 7, height = 9\n
- Obstacle: Left = 1, Right = 5, height = 6\n
- Obstacle: Left = 4, Right = 8, height = 3\n<\/ul>\n
\nAnd here’s the program.\n<\/p>\n
\nfunction Obstacle(left, right, y) {\n this.left = left;\n this.right = right;\n this.y = y;\n}\n\/\/ A single step in a path, representing the cost to reach that point.\nfunction Step(x, y, cost) {\n this.x = x;\n this.y = y;\n this.cost = cost;\n}\n \/\/ Add a step to an existing step\nStep.prototype.to = function to(x, y) {\n var dx = Math.abs(this.x - x);\n var dy = Math.abs(this.y - y);\n return new Step(x, y, this.cost + dx + dy);\n}\n\/\/ Record a droplet position\nfunction addDroplet(l, step) {\n \/\/ If no previous droplet at this position or the new droplet\n \/\/ has a cheaper path, then remember this droplet.\n var existingStep = l[step.x];\n if (!existingStep || step.cost < existingStep.cost) {\n l[step.x] = step;\n }\n}\n\/\/ Take an existing collection of locations and updates them to account\n\/\/ for a new obstacle. Obstacles must be added in decreasing altitude.\n\/\/ (Consecutive duplicate altitudes allowed.)\nfunction fallTo(oldLocations, obstacle) {\n var newLocations = {};\n for (var x in oldLocations) {\n var step = oldLocations[x];\n \/\/ fall to the obstacle's altitude\n step = step.to(step.x, obstacle.y);\n \/\/ If the falling object does not hit the obstacle,\n \/\/ then there is no horizontal displacement.\n if (step.x <= obstacle.left || step.x >= obstacle.right) {\n addDroplet(newLocations, step);\n } else {\n \/\/ The falling object hit the obstacle.\n \/\/ Split into two droplets, one that goes left\n \/\/ and one that goes right.\n addDroplet(newLocations, step.to(obstacle.left, obstacle.y));\n addDroplet(newLocations, step.to(obstacle.right, obstacle.y));\n }\n }\n return newLocations;\n}\nfunction printStep(step) {\n console.log(\"Cost = \" + step.cost + \": \" + step.x + \",\" + step.y);\n}\n\/\/ Debugging function\nfunction printLocations(l) {\n for (var x in l) printStep(l[x]);\n}\nfunction shortestPath(x, y, obstacles) {\n var l = {};\n l[x] = new Step(x, y, 0);\n printLocations(l);\n obstacles.forEach(function (obstacle) {\n l = fallTo(l, obstacle);\n console.log([\"after\", obstacle.left, obstacle.right, obstacle.y].join(\" \"));\n printLocations(l);\n console.log(\"===\");\n });\n \/\/ Find the cheapest step.\n var best;\n for (x in l) {\n if (!best || l[x].cost < best.cost) best = l[x];\n }\n \/\/ Fall to the floor and print the result.\n printStep(best.to(best.x, 0));\n}\nshortestPath(6,12,[new Obstacle(3,7,9),\n new Obstacle(1,5,6),\n new Obstacle(4,8,3)]);\n<\/pre>\n\nThis program finds the cost of the cheapest path to the floor,\nbut it merely tells you the cost and not how the cost was\ndetermined.\nTo include the winning path,\nwe need to record the history of how the cost was determined.\nThis is a standard technique in dynamic programming:\nIn addition to remembering the best solution so far,\nyou also remember how that solution was arrived at\nby remembering the previous step in the solution.\nYou can then walk backward through all the previous steps\nto recover the full path.\n<\/p>\n
\n\/\/ A single step in a path, representing the cost to reach that point\n\/\/ and the previous step in the path<\/font>.\nfunction Step(x, y, cost, previous) {\n this.x = x;\n this.y = y;\n this.cost = cost;\n this.previous = previous;\n}\n \/\/ Add a step to an existing step\nStep.prototype.to = function to(x, y) {\n var dx = Math.abs(this.x - x);\n var dy = Math.abs(this.y - y);\n \/\/ These next two test are not strictly necessary. They are for style points.\n if (dx == 0 && dy == 0) {\n \/\/ no movement\n return this;\n } else if (dx == 0 && this.previous && this.previous.x == x) {\n \/\/ collapse consecutive vertical movements into one\n return new Step(x, y, this.cost + dx + dy, this.previous);\n } else {<\/font>\n return new Step(x, y, this.cost + dx + dy, this<\/font>);\n }<\/font>\n}\nfunction printStep(firstStep) {\n \/\/ Walk the path backwards, then reverse it so we can print\n \/\/ the results forward.\n var path = [];\n for (var step = firstStep; step; step = step.previous) {\n path.push(\"(\" + step.x + \",\" + step.y + \")\");\n }\n path.reverse();\n console.log(\"Cost = \" + firstStep.cost + \": \" + path.join(\" \"));\n}<\/font>\n<\/pre>\n\nNotice that we didn’t change any of the program logic.\nAll we did was improve our record-keeping\nso that the final result prints the full path from the starting\npoint to the ending point.<\/p>\n","protected":false},"excerpt":{"rendered":"
Today’s Little Program solves the following problem: Consider a two-dimensional board, tall and narrow. Into the board are nailed a number of horizontal obstacles. Place a water faucet at the top of the board and turn it on. The water will dribble down, and when it hits an obstacle, some of the water will go […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-393","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Today’s Little Program solves the following problem: Consider a two-dimensional board, tall and narrow. Into the board are nailed a number of horizontal obstacles. Place a water faucet at the top of the board and turn it on. The water will dribble down, and when it hits an obstacle, some of the water will go […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/393","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=393"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/393\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=393"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=393"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=393"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}