Tuesday: Let's talk about topology again, in another post I should stick on my science blog.

Alternate title: God damn it, Julie, I can't play games at work!

Julie sent me a link to this game, and said I should play it, as it supports Techtonica, which does great things (copying from their webpage): "Free tech training with living and childcare stipends and job placement for low-income women and non-binary adults. #BridgeTheTechGap".  Great, I'm all on board with that.

The game is essentially a more complicated version of the Bridges of Koningsberg problem.  There are nodes you need to pass through, and you can't retrace steps.  I did the first 17 levels before realizing I should get back to work, so I waited until I got home to finish all the levels (and bring Techtonica above 50000 stars.  I assume everybody gets some money, and that it's not some sort of monstrous three charities enter, one charity leaves thing).  It wasn't until level 29/30 that I realized that there had to be some sort of algorithm to solve these, and not just "magical topology powers."  So I sat down to write out what I was doing with diagrams and words, to make sense of it.

Here's the board.

Nodes with only two edges must be traveled through both, obviously.

So, we can block off any route that the two-edge nodes force us to exclude.

 I ended up largely solving this from the end, because I know a path must go to the terminal node, and that immediately forces the route into the two nodes in the bottom right corner.  Knowing that the intermediate node already had two edges on the path excludes any other path from using the other two edges.

And this provides the next big hint to how the algorithm works:  Once you've blocked edges from being part of the path, you turn some nodes that were previously connected to 3+ nodes into 2-edge nodes, so you can iterate the process again.  I've labeled the first node that is downgraded like this with a star.

Another round of marking and blocking gets the pseudo-path near the start point, but there aren't any clear ways to continue at that end.

Which is good that I noticed that in the upper right, the one edge I crossed off in stage 1a is connected to another edge that is also forbidden.  This makes the one node a 2-edge.  The square path at the top is redundant, so I chose one to exclude.  This connects those two corner nodes to the straight 2-edge in the middle.

I'm not 100% sure that my solution here is unique, but I'm not redrawing my diagrams again.  In any case, my logic here says that the start can't continue straight past that first target node, as it would then either need to go down (which leads to the end), or straight (back through that 2-edge), which isn't value.  I already excluded the bottom route, so it will need to turn up.  Blocking that route forces the empty node to have 2-edges, which connects the "to-the-end" path with the "back through the straight 2-edge" path.  This blocks the down edge out of the top-center node, forcing it to be a turn.

That forces the empty node above it to have one exit blocked, and then things fall into place. 

See, 50008.

And I think that this algorithm solves any similar game, although there are two edge cases.  The first is when the grid is over connected with edges.  This should always have trivial solutions that are obvious (and the early stages have extra connectivity, and that simply means that there are multiple paths that are valid.  Path length was not a constraint).  The second problem case is when the objective is not possible because it's a true Bridges of Koningsberg problem with no solution.

And then I drank this cider I got at Shirokiya.  It is tasty sweet cider.

• Joy indeed.
• Wow.  Maybe we should just get Tumblr to do punch up work on all stories.  That Passengers movie didn't seem that interesting, and reading the ending put it pretty clearly on my "nope" list, but this version would have been super cool.
• Fuck you, Glenn Beck.  You were there, breaking shit, making stupid people crazy, generally being an asshole.  Fuck you in your stupid ugly face.  Now fucking start fixing shit, jackass.  We need to not fucking break everything.
• Also Tracer from hit video game Overwatch isn't straight, and the internet can't deal with it.  She wasn't who I was guessing would come out, but hey.  Good for her.
• I guess when you don't already have history to warn you, and the gods are murdering people warning you of the trick, it can be pretty surprising.
• Canned food.  Including pastry dough.
• Uber.
• Twenty-four hour gyoza restaurant.  It is in Kabukicho, which isn't the best neighborhood, but still.
• This is an important read.  Even when told explicitly that they would be harmed, they assumed it wouldn't happen.  Now that it might happen, they're starting to worry.
• Also an important read.  "433 pain pills for every man, woman and child in West Virginia."  That's over six years, but still.  Everyone in the state could take one every five days.  Everyone.  I would assume if we still lived in a sane world, there would be proper investigations and jail time for the companies involved.
• Finally, "Duterte on Monday revealed that he used to take fentanyl, often prescribed for cancer pain and other chronic ailments, because of a spinal injury from previous motorcycle accidents.  He however said his doctor made him stop using it on learning he was "abusing the drug" by using more than the prescribed patches."  This is the guy who has bragged about murdering drug users, and is leading a violent purge against drugs.