Penguin Coding 7: Walk to the Corner Mystery Cache

Penguin Pablo has recently been really honing his programming skills, and is here pushing his new series, the Penguin Coding series. His puzzle inspiration is varied, but he was recently seen struggling through another polar-themed puzzle event, the yearly Advent of Code challenge, though studying those is not at all required.

Unlike the Penguencoding series, there is no D1, but the series should roughly start easier, and progressively get tougher, with some of the early ones as practice for future ones. But fear not! Pablo is a generous sort, and is very free with hints - or at least after the FTF!

No particular language is required! Only the answer is needed. Typically once you've completed the coding the coordinates should be obvious, but perhaps you'll have to do a little lateral thinking to see them.

Given the nature of coding puzzles - where true coders will consider a puzzle "too easy" that is opaque to non-coders - Pablo has decided to provide help in the form of algorithms, pseudocode, or code snippets, but only after 24 hours of release. That way the coders can have their try for FTS, and non-coders can get assistance to start. The updates will be given at the bottom of the text page sometime on or after the second day.

Pablo's son Pippin was a curious sort, and he secretly admired his dad and his curious way of looking at the world (and other problems in general), though he would never admit it out loud. He was a visual penguin, and had yet to (externally) show interest in his father's love of computers and programming. But he enjoyed posing problems to himself and see if he could solve them. Every day on his walk to school, he would enter a section that was an array of tiles, each with a numerical value on it. His goal was to walk from one corner to the opposing corner, adding up the values along the way, and trying to minimize the total value. At first he would just look at the two options and take the smaller of the two, but he had a feeling this wasn't the best algorithm. For instance, if he wanted to go from the NW corner to the SE corner, if he only considered a step to the south or a step to the east, he might encounter the "local minimum" but not the global minimum. Sure enough, he looked farther afield one time and found a longer path (by step count) with a lower value. "Oh boy!" he thought, "how big is this problem?"

Eventually Pippin broke down and talked to his dad. "Wow, you've stumbled upon a very well known but fun problem!" His dad beamed with excitement at his son's numerical interests. "You'll find that ..." Three words into the lecture Pippin began to regret his oversharing as his father droned on about some Dutch penguin he had once met, something about dikes or something. Eventually his dad finished his speech, so Pippin returned to listening. "Let's go to your grid and see if we can solve it!" he said, and they walked towards Pippin's school.

"See here" he lectured, as his son resisted rolling his eyes, "starting in the north-west, if you use the brute-force method, you would certainly choose to start south, since 4 is smaller than 7. "And you certainly wouldn't attempt to backtrack like I did there!" "Wow", Pippin had to admit eventually, "a score of 50 is pretty impressive. I don't think I ever got under 60." Reluctantly he added "Can you show me how you found that path?" Pablo put his arms around his son, sensing a rare teaching moment. Later, after things were explained, Pablo walked his son to an even bigger field. "Wow!!" Pippin exclaimed. "That's right" Pablo grinned, "let's see if you can solve this one. The best I've ever gotten is 487, and I'm pretty sure it can't be beat." "But ... these are not all numbers" said a confused Pippin. And after Pablo explained hexadecimal to Pippin, he was off to the races.

OK, here is the puzzle: given the following array of hexidecimal values (where A=10, B=11, ... F=15), what is the path from the NW corner to the SE corner that has the lowest sum value?

You can validate your puzzle solution with certitude.

Congratulations to KendraH for the First to Find, and to pfalstad for the First to Solve!

Post-24h help update: Dijkstra's Algorithm (Pablo's reference to the "Dutch Penguin", perhaps?) is a famously simple and elegant way to solve this and other shortest-path challenges. It is used for things like best-route searches for route planning, and puzzles like this one. In its basic form, for this problem, pseudocode for it looks roughly like this:

This starts the "heap" (a random "pile of work" to churn through) with the NW corner and a total sum value of zero, and a null path. It then keeps adding all four possible directions from each location (x,y), adding in their numerical value, until eventually it reaches the final destination corner. The first key is popping the member of the heap with the lowest value of any heap member, thereby ensuring you're trying the most efficient step. The second key is keeping track of where you've visited, and skipping it if you've already been there. There is no reason to re-visit (x,y) if you've already visited it with a lower cost path on the heap! This guarantees at worst you visit each of the x*y locations at most once.