Author: Cameron Swartzell

July 19th, 2023: Carpenters Tricks and Edge Cases

Cameron SwartzellLeave a comment

Recently doing a spate of coding challenges I came upon a question I rather liked:

Given the coordinates of four points in 2D space p1, p2, p3 and p4, return true if the four points construct a square.

Simple enough, right? In particular, with my background in Carpentry I thought I immediately had the solution. There is a great construction trick when building rectangular frame to check if they are true; Do not fiddle with a carpenters square, trying to check each corner. For anything larger than a small frame you may not be able to see the difference. Being just half a degree off of 90 over the course of 16 feet and you’d be off by more than an inch and a half. Instead, simply measure the length of the two diagonals: If they are equal then you know you have a rectangle*. Or so I thought.

The two diagonals above give different measurements, so you’d know you have a parallelogram instead of a rectangle.

Of course you also want to check that the other 4 sides are the same length right? Actually this may not be necessary if none of the points are coincidental. But, with just 4 arbitrary points we don’t have a way of measuring just the diagonals anyhow since we do not yet know which is which. “Easy enough”, I thought, “Ill simply compute the lengths for all 6 lines and add them to a set. If there are exactly two length measurements it must be a square right? Easy Peasy”

We start by making a function (d) to calculate the distance between two points using the quadratic formula. Here we can use a little shortcut by omitting taking the square root: we actually don’t care about the lengths, just a “class of lengths”. Then, simply check if there are two different lengths out of all six possible lines between the points.

Oh right. Those pesky coincidental points. Imagine you have 3 points that form an equilateral triangle, and a 4th point that coincides with one of the above. The distance between the three points is the same, and the distance from the null point to its partner is a second length (0). Ok, well we should just check for coincidental points before bothering to compute distance anyhow:

That should be all the edge cases right? “The 4 points are distinct and we know how to check if we have a rectangle using our diagonal trick and that the remaining sides are equal. I think that’s it.”

Aaaaand wrong. There is exactly one edge case that breaks the above method:

Two adjoined equilateral triangles clearly have 2 sets of measurements: five equal lines and one distinct longer diagonal. It was not enough to just count that we had 2 differing lengths. The fix is trivial, instead of checking we have 2 total lengths we instead actually bother to count them. We should have 4 equal sides and 2 equal, but distinct, diagonals to ensure we have a square.

A good reminder to consider all the possible edge cases and to not assume a simple solution necessarily covers all of them.

Corrected, and all together:

(input points are passed as lists of floats: [float, float])

July 12th, 2023: Blackjack

Cameron SwartzellLeave a comment

Today I challenged myself to write a simple console based game of Blackjack “In One Hour”. Several hours later and I’m done! It wasn’t so much that it was a tricky feat, rather I got hung up on a few areas of interest.

First, I discovered that the console (Windows in this case) supports UTF-8 by default, and all 52 standard cards actually do have their own printable character, neat! So I started playing with that for a while. First issue is the Unicode characters for cards look like this:

🂷🂬

So… quite unreadable. Ah well, at least I can just use the characters for suits (â™ , ♥, ♦, ♣) and draw my own old school ASCII art to display them. Oh wait, the “10” card is the only one to use two characters for its rank. Hmm, is there another character I could use? I could use the “enclosed numbers” block so it would be â‘©, but that looks weird if I don’t do them all and they are pretty hard to read too. Then I looked into combining characters which is a standard way of using Unicode and went down a few rabbit holes before deciding, as I’m sure many frustrated fussy hobbyist programmers before me have, that “T” is good enough to mean ten and move on having wasted a bunch of time.

When playing with the Unicode cards, I also noted that I was never seeing kings come up and couldn’t figure out why. It looked like an Off By One type error, but the rest of the program worked as expected. Turns out, Unicode includes an “alternate” rank called a “knight” that was used in France and Spain in times of yore. Now, obnoxiously dropped in the middle of the Unicode ordering. Fine, we can just add an offset to ignore this issue.

I also spent some time refamiliarizing myself with methods of randomizing and distributing elements from a collection and looked through the documentation of the random package in Python. I ended up writing my class for creating a deck, shuffling, dealing, and storing card information as I can reuse parts for future projects, but it was still informative learning some existing options.

Lastly, I spent a while just playing with timing and “animating” the game, such that it can be in console. Just blanking the console and reprinting various states. I could have been a bit more clever and stored sections in some sort of display buffer, only then editing the changing parts, but instead just wrote a few multipurpose, hard coded display sections which work well enough for a silly task like this.

Overall a fun little short project. Pretty simple, but not trivially so. Upon completing the base game, I decided to add doubling down on your bet as an option, which was simple enough. Now it all functions as intended, looks “good”, and is fun. Yet to tackle is Splitting as it’s a whole other display rigmarole I’ll have to deal with. It’ll bother me if I leave it unfinished though, so surely I’ll go back to it.

See Source Code on Github: https://github.com/cswartzell/SpeedRound.git

Hooray! It works!

Code Snippet

       def print_hand(hand, hide_first):
            for _ in range(len(hand)):
                print("╭――╮", end="  ")
            print()
            
            for crd in hand:
                if hide_first:
                    print(f"│🜲\u2009│", end=" ")
                    hide_first = False
                else:
                    print(f"│{crd.unicode_suit}{crd.unicode_rank}│", end="  ")
            print()
            
            for _ in range(len(hand)):
                print("╰――╯", end="  ")
            print("\n")
            

        def print_state(player_cash, dealer_hand, player_hand, player_total, hide_dealer, won=0, msg="", d_total=0):
            system('cls')
            print(f"                                             Cash: ${player_cash}")
            if won > 0:
                print(f"                                                  +${won}")
            elif won < 0:
                print(f"                                                  -${won}")
            else:
                print()
            print("Dealer: ", end="")
            if d_total:
                print(d_total)
            else:
                print()
            print_hand(dealer_hand, hide_dealer)
            print(f"Player: {player_total}")
            print_hand(player_hand, False)
            if msg:
                print(msg)
            if won != 0:
                sleep(.5)
                print_state(player_cash + won, dealer_hand, player_hand, player_total, hide_dealer, d_total=d_total, won=0, msg=msg)

Dec 4, Leetcode 2256. Minimum Average Difference- Adding Complexity

Cameron SwartzellLeave a comment

https://leetcode.com/problems/minimum-average-difference/
Language: Python — Time: 35 minutes
Full Code on Gitfront.io — https://github.com/cswartzell

Oddly phrased, but fairly simple challenge. Mostly, this just comes down to recognizing you need to create a prefix sum in order to efficiently generate averages of sub-sums as we iterate through the array. I had a vague memory of learning a data structure that did this implicitly and so challenged myself to use a more advanced DS rather than the obvious solution. After a bit of research I rediscovered the “Fenwick Tree” (wikipedia), a Binary Insertion Tree that stores a prefix array in tree form. This allows a trade off where lookups are O(log n), so quite a bit slower than a prefix sum array, but insertions are also O(log n), where they would be O(n).

I found some example code for implementing a Fenwick Tree (geeksforgeeks) and set to work, knowing full well that this was rather a silly solution: Our given array is static, we will not be performing any future insertions. The benefits of a Fenwick Tree in this scenario is entirely moot. I went this way specifically for the added challenge of implementing a more complicated structure and testing the result. I was quite pleased that it worked exactly as intended, and just squeaked by the minimum requirements for acceptance, being in the bottom 5% for performance.

Another reason I decided to make this harder than it needed to be was to interrupt a habit I’ve noticed I am forming; With the majority of my recent exercises being shortform challenges like Leetcode problem I have fallen into writing in simple block form. I find I opt for iterative solutions instead of writing recursive functions, and I almost never create whole alternate “helper classes” extraneous to the solution. This was a good opportunity to implement the tree structure as its own class, and use that to solve the problem at hand.

Other than this bit of added complication, the solution is a pretty standard “iterate through and note the min” algorithm, using the FenwickTree.getsum() method to calculate the average difference for each index position of our original loop.

I’m glad I took the extra time to further challenge myself on this one. The opportunities to research how more complicated structures work, and how to implement them offer a real chance for growth, and its solutions like this that afford me the best opportunities to grow as a coder.

Dec 3, LeetCode 451. Sort Characters By Frequency: Sometimes Python Is Magic

Cameron SwartzellLeave a comment

https://leetcode.com/problems/sort-characters-by-frequency/
Language: Python — Time: 2 minutes
Full Code on Gitfront.io — https://github.com/cswartzell

I’ve been exploring development with Python for much of a year, and recently I feel like its really beginning to click. I’m falling in with the fanatics, Python is magic. Simple, powerful, readable, and intuitive. The standard and common libraries are amazing for just getting things done. Most of the times I wonder if there is an existing method for doing this or manipulating that, and after just a little googling… there just is, and not in some obscure package nobody has ever heard of, but often a core feature of standard types.

Case in point, todays Leetcode exercise (seemingly erroneously marked as a Medium difficulty), asks to simply return a string of characters, sorted by the frequency of the characters themselves. Built in sorting methods assume character sorting by alphabetic order.

Dead easy:
1. Create a frequency hashmap of the letters: This is the Python Counter() type
2. Sort this frequency map: Yep. As of Python 3.10 dicts, counters, sets etc (hashed types) now retain their ordering, so can indeed be sorted. Furthermore, Counter has a method that sorts by most common frequency already.
3. Iterate our Counter. We can use a list comprehension to recreate our string. By unpacking the Counter as a Tuple we get the character (key), and its frequency (value) in a single handy package we can simultaneously assign to two variables. Simultaneous assignment and automatic unpacking makes so much sense and eliminates a lot of clutter.
4. Generate the list of chars. In list comprehensions, the “*” operator means “repeat the previos value” as in [“X”*Y] would make a list “X” characters repeated Y times. This creates the list, in order, for the correct number of each character
5. Convert this back to a string. ****

**** Ok… here I sympathize with those that disparage Python. The “”.join(str) method seems… rather clunky. Why lead with the literal to be used as the separator and not treat it as an argument? It feels very odd, and doesn’t match almost any other syntax I know in the language. str.join(iterable, “seperator”) seems to make a lot more sense. Otherwise it feels like I’m operating on the object “”

Anyhow, all of this is simple, intuitive, and built in standard functions. This can elegantly be combined into a single line, and not a hacky “technically its one line” mess. It is completely logical, readable, efficient. As we are sorting the hashmap it is presumably O(n log n).

        return “”.join([x*y for (x, y) in Counter(s).most_common()])

Sometimes Python is magic. Relevant XKCD

Dec 1, Leetcode 1657. Determine if Two Strings Are Close- A great logic puzzle

Cameron SwartzellLeave a comment

https://leetcode.com/problems/determine-if-two-strings-are-close/
Language: Python — Time: 10 minutes
Full Code on Gitfront.io — https://github.com/cswartzell

This was hands down one of my favorite problems so far. Ill list it in full here:

Two strings are considered close if you can attain one from the other using the following operations:

  • Operation 1: Swap any two existing characters.
    • For example, abcde -> aecdb
  • Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
    • For example, aacabb -> bbcbaa (all a‘s turn into b‘s, and all b‘s turn into a‘s)

You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

The reason I loved this is… its a trick. Rather than a wrote exercise in coding existing patterns, or a brain bender of a challenge requiring arcane wizardry, this problem just asks you to think.

The first clue is in the description of the first operation. If you can swap any two letters in a word, and you can perform that operation any number of times then you can create whatever arrangement you want from the word. The mechanics of the operation are meaningless: the letters can be arranged however you’d like. We will never need to perform a swap operation on one of the words to “test” its ability to become the other. If we can ensure the two words have the right number of letters, we can ignore their arrangement and this rule.

But how do we know if we have the right letters? Well first we note we can only swap between existing letters. 5 letter “A”s can swap with 3 letter “B”s such that we have 3 “A”s and 5 “B”s. That means if one word has a letter the other doesnt then we can terminate as False. We cannot generate a missing letter nor lose an existing letter. We merely need to make a hashset out of each word and ensure the two words contain exactly the same letters.

But how many of each letter? Back to the example of our 5 “A”s and 3 “B”s, we see after swapping them we still have 5 of one letter and 3 of another. We can never affect the total count of the various letter groupings, merely what letter happens to be assigned to them. We have thus far determined that our two words have the same sets of letters. If the two words have the same grouping sizes (say, 5 of letter #1, 3 of letter #2, and 1 of letter #3), then we can swap the labels on these groups such that the two word sets will have the same frequencies per letter. This catches the trivial case that the words need to be of equal length.

We can use a basic hashmap to simply check these two conditions. The Python Counter() collection can be used to automatically create an unordered hash with the letters of our strings as the keys, and their frequency within a word as the values. We then check the lists of keys for both words are the same (affirming the two words have the same and only the same letters), and then compare their values lists (affirming they have similar “letter frequency groups”, regardless of what letter is attached to them).

We don’t need to perform any swaps. We don’t need to implement either operation. We don’t simulate the transformation of one word to the other. Using just logic we can extend the existing rules to think about what they ultimately mean, and reduce the problem to a much simpler one. Rather than math trickery or hacky shenanigans (which, to be fair, I also love) this can be solved in just a few lines with basic reasoning:

I love it.

Accounting Mystery: Yep, 2^n gets really big

Cameron SwartzellLeave a comment

Language: Python — Time: 10 minutes
Full Code on Gitfront.io — https://github.com/cswartzell

A colleague of mine received a check today for some receipts they had turned in for reimbursement. They were surprised to find the total was quite a bit less than they were expecting. Specifically, according to their tracking sheet, they had turned in 20 receipts totaling $475.98 but received only $304.22: a difference of $171.76. They asked if me if I thought maybe a section of receipts had perhaps fallen out and weren’t added by the Accountant. Aha! We can solve this in just a few lines! Surely there can’t be that many combinations that add up to a specific value from a subset of values that are within two orders of magnitude from each other and the target sum right? And there are only 20 receipts to deal with, this should be simple.

Well… the Power Set of a given set of length n is 2^n so… there are a lot of combinations. 2^20 = 1,048,576 combinations of receipts to be exact. Still, pretty manageable. “I could probably write a 2d DP solution for this” I thought to myself as I instead lazily abused itertools to simply generate all the the sets of iteratively. It ran in under a second. Good enough, you know what they say:

“Premature optimization is the root of all evil”- Knuth

And the result?

Twelve! Twelve combinations of possibly missing receipts that might explain the discrepancy. Sure, out of over a million possibilities it seems small, but I was quite surprised. Thinking on it further, the individual prices are conveniently clustered in a range around 10% of the target total, so it makes sense that the overwhelming majority of the sums of around 10 of these receipts might be at least within the ballpark of the target after all.

We concluded that it didn’t really seem likely that most of the receipts went missing from the stack, but the mystery remains. The accountant swears they added up what was presented to them correctly. The obvious question (as yet unanswered) is “yes, but how many receipts were there?”

Dungeons and Dice: Is +1d4 or Advantage Better?

Cameron SwartzellLeave a comment

Language: Python — Time: 90 minutes with research
Full Code on Gitfront.io — https://github.com/cswartzell

Another problem inspired by a Reddit thread: In Dungeons and Dragons nearly all actions are assigned a “DC” (Difficulty Class), which is a target number you want to meet or exceed when rolling a single 20 sided die (1d20) to succeed. For instance, “roll better than 15 to climb this wall”. There are certain actions players can take can aid their fellow party members, giving them assistance for these rolls. The Cleric spell Guidance, for instance, adds an additional 1d4 to a players next d20 roll while Enhance Ability grants “Advantage” on a roll which allows a player to roll two d20 and keep the higher result. Both of these options give a player a minor edge, but in different ways. Given the choice, which is statistically superior?

A pretty simple probability problem, and a good chance to play around with the matplotlib library in Python. We can simply generate all outcomes (1d20+1d4, and max(2d20)), calculate the probabilities of each combination, create a running total for each result showing “chance of rolling at least X”, and graph the result. Matplotlib allows us to create a clean, simple graph in just a few lines of code:

The answer ends up being quite surprising: It depends on the “DC” of the roll we are intending!

Adding 1d4 mostly just adds a simple offset to a linear probability, while advantage changes the probability to being nonlinear. Graphing the two, we see the lines cross each other multiple times, though just barely on the left.

On the low end, if we must avoid rolling a one to succeed in some challenge, then obviously we should take the added die as the lowest roll for 1d20+1d4 is 2, while there is still a slim possibility of 2d20 each showing a 1 (a 1 in 400 chance). Above this minimum, rolling 2d20 with Advantage gains an edge for some time, and results in the range 3-17 are significantly more likely.

For middle values we see that the Advantaged roll is significantly more likely to roll “at least” those targets. At its peak, rolling with Advantage gives us a 75% chance of getting at least 11, while 1d20+1d4 has only a 62.5% chance to be at least as much.

At 18 the lines very nearly cross again, though Advantage retains an edge, there being 27.75% chance of rolling at least 18 with Advantage compared with 27.50% if rolling 1d20+1d4. After a DC target of 18 the added 1d4 takes the lead again, and is more likely to give you a higher total. Significantly, the added d4 allows a player to roll above 20 as the combined results go up to 24. We now see this is actually the reason why the added die is less favorable for most middle target numbers: there are more total results so the probability of any specific result is commensurately reduced.

So, which to use? We see now this is dependent on the target DC— a value known only to the Dungeon Master. Players don’t have perfect information when playing and can only make an informed guess. Experienced players may have a sense (10 is pretty standard, 15 is a hard task, 20 is quite a challenge), and can perhaps game the system by estimating what the DM has in mind, but the difference is fairly slight either way.

More Math:
2d20 with advantage:
Mean: 13.82
Deviation: 4.71

1d20+1d4:
Mean: 13 (simply: mean 1d20 + mean 1d4 = 10.5 + 2.5)
Deviation: 5.87

Nov 19-21st, Leetcode 224, 1926, 279- A Difficult Series

Cameron SwartzellLeave a comment

A frustrating set of difficult problems. While I’ve learned a lot, its been a few days since I’ve been able to jump to a solution without quite a bit of additional hints.

11-19-2022 Leetcode 224. Basic Calculator
https://leetcode.com/problems/basic-calculator/
Language: Python — Time: 60 minutes
Full Code on Gitfront.io — https://github.com/cswartzell

I should really learn to use Regex better. Converting strings into numbers is simple enough though. Some obvious math pitfalls here: Addition is associative, so we can just ignore repeated addition. My first instict was to create a function that takes the innards of a set of parens, and parses it: adding numbers and operators to a stack. I thought I was being clever and converting leading minus signs to a -1 and * number and operator, maintaining the invariant of our stack always being computed, left to right, Num Operator Num… It actually worked quite well, recursing to process any number of complicated nesting, but unfortunately timed out. I could have adapted it to do all the additions as we scanned, rather than creating such a large stack. I actually think its unfortunate this was a TLE as I thought the solution should have been considered good enough. I also considered a method using regex to reformat the string in the first place to take care of leading muinus signs. If we could flatten the expression to just a series of +/- it would be trivial to compute (once converting the numbers). This would be mean negating everything within a neseted paren using regex iteratively. Should be doable, but was beyond my scope at the time

11-20-2022 Leetcode 1926. Nearest Exit from Entrance in Maze
https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/
Language: Python — Time: 40 minutes
Full Code on Gitfront.io — https://github.com/cswartzell

I did much better with this. It can be done iteratively or recursively, and I went with an iterative, stack based approach. A simple “take a step, if valid, and add new positions to the LIST. Repeat til we reach a condition, or there are no more steps to take”. Unfortunately my solution timed out, again. Why? We are just trying to reach the end of the grid. What I failed to do was to recognize the clear importance of a BFS method: there is no reason to chase down a long and windy path using a depth first approach if that path wont lead to an exit faster than a BFS method would. A BFS is guarantied to find it quicker as it is “blobbing out” from our starting point, and the very first exit space reached will be guarantied to at least be in the same class (number of steps from start) as any other solution. This was actually why I avoided a recursive approach. All I had to make was a simple change to use a DeQue and popleft() so I was processing it from LEAST steps to greatest. Obvious.

11-21-2022 Leetcode 279. Perfect Squares
https://leetcode.com/problems/perfect-squares/
Language: Python — Time: 60+ minutes- Needed to Peek at Answer
Full Code on Gitfront.io — https://github.com/cswartzell

A mathy one, I should have been on top of this. I was even aware of the Four Square theorem, and thought it might be the case inre the three square solution. I should have been able to recognize this as a DP problem, nearly identical to “make X change with coins of varying sized”: In this case, the “coins” are just the perfect squares less than our input, N. We start by generating these squares (x**2 for x less than sqrt(n)+1 is a clever method), and build up a DP array for i in n. Either a new “coin” will reduce the number of total coins needed so far, or its just the last sum + 1. As 1**2 is one, we can always get the next sum by adding an additional 1 “coin”. Again, a concept I understand, but not a tool I reach for immediately. I should consider some additional practice using Bottom Up DP as it is a powerful pattern that can be used to solve many problems.

Nov 10, Leetcode 223. Rectangle Area- Beware Pitfalls

Cameron SwartzellLeave a comment

https://leetcode.com/problems/rectangle-area/
Language: Python — Time: 15 minutes
Full Code on Gitfront.io — https://github.com/cswartzell

Deceptive in its simplicity. As presented, sum the area of two rectangles given coordinates. So simple that it should clue an interviewee in that there must be a trick; otherwise this is a trivial one line question. The problem is presented on Leetcode with the trap shown clearly: the rectangles can overlap.

I’d like to think I’d spot this case in an interview even if not so obviously presented. It’s a good lesson in the absolute importance to really consider the problem before jumping straight to coding. Without the clue, one might be tempted to “show off” by simply returning the area of the two rectangles without considering the obvious edge case.

The actual solution is nearly as trivial, we must simply check if there is an overlap, and if so subtract it so it’s area is not counted twice. I started with a series of symmetric if blocks to determine if one rectangle started after the other but before it’s end, for each of the two dimensions, and if so calculate this overlap. While only a few lines, knew there must be a far simpler way to do it in one go.

The neat answer is indeed pretty elegant;

“`overlap_X = max(min(ax2,bx2)-max(ax1,bx1), 0)“`

We simply determine the distance between the right most starting point, and left most end point, regardless of which rectangle either point comes from. However, we must catch that this would return a negative result for rectangles that do not overlap. We fix this by maxing this with zero, so we only retain positive overlaps. We do this for each axis. From there, we can compute this in a single line (if we are playing golf instead of writing clean code; more on this later):

“`return (ax2-ax1)*(ay2-ay1) + (bx2-bx1)*(by2-by1) – ( (max(min(ax2,bx2)-max(ax1,bx1), 0)) * ((max(min(ay2,by2)-max(ay1,by1), 0)) )“`

Dungeons & Dragons & Diagonal Movement

Cameron SwartzellLeave a comment

Language: Python —
Full Code on Gitfront.io — https://github.com/cswartzell

A friend of mine is working on a Unity project based on faithfully recreating tabletop RPG rules, and asked for a hand coding the rules for movement. In Dungeons and Dragons character movement is done on a grid of squares where each square represents 5’ x 5’ of space. Traveling orthogonally from one square to another simply takes 5’ of movement. However, the rule for diagonal movements are… unusual.

A character taking their first diagonal step in a turn is charged as having moved 5’. This makes all 8 squares surrounding the starting position an equal 5’ away. Afterwards, any second diagonal move during a turn takes 10’ of movement even if not contiguous or in the same direction as the first diagonal step. The pattern then repeats; 5’, 10’, 5’, 10’… simple enough and a good compromise for efficient movement on a grid. Plotting say 30’ of movement using this system starts to roughly approximates a circle.

As a coding challenge, how do we plot a characters movement? How do we draw a movement “circle” indicating grid spaces they can reach within their movement distance? How far away is a target from a character, assuming the most direct route using these movement rules?

As this project is Unity based, some simple solutions come to mind. My friend easily created a coordinate based grid system, and can arbitrarily assign scales to the world. We could simply take an actual measurement from the center of one grid position to another to determine their distance by rounding to the nearest 5’. Will this accurately model the rules though? Hard to say, but my intuition is it will accumulate errors, or rather “corrections” that deviate from the more approximate game rules vs real measure. Similarly, we could treat each diagonal move as 7.5’ and, again with rounding, come up with a decent approximation. While fine choices for a game these methods may not exactly match the game rules.

Instead, we need to come with an algorithm for determining optimum grid movement given the movement rules as written. The most efficient movement is orthogonal; moving in a straight path along a row or column always costs us 5’ per square. We want to travel in an orthogonal path toward our target for as much distance as possible. For any square not in our current row or column we will have to alter our direction at some point. However, unlike in real life, the straight line from the origin to the target may not be the shortest route if it costs an extra 10’ diagonal step we could have avoided.

The least efficient movement would be L shaped, barring intentionally indirect paths. Using this method moving 4 squares North followed by 4 squares East would be 8 steps. Let’s start using coordinates to notate this; (0,0)->(4,4) at 5’ step size would be a “Manhattan Distance” of 40’. We could instead make just 4 diagonal movements NE to go directly toward the target. At a cost of 5’, then 10’, 5’ and 10’ again, we would arrive at the same square using only 30’ of movement. Diagonal movement is the more efficient than L shaped movement.

So, we want to travel in a straight line as much as possible yet may need to get over a few rows or columns first in order to do this. Combining these two ideas we see that we should move directly diagonally, along the shorter leg of the L, toward either the row or column that lets us make the rest of our movement in a straight line.

After some thinking and tinkering I hit upon the algorithm that solves this. Let’s call East-West movement row based and North-South column based. To go from our characters origin (0,0) to our target (tgt_row, tgt_col), we could travel the L shaped Manhattan Distance of (5’ * tgt_row) + (5’ * tgt_col) less some savings by moving diagonally. Specifically, we save 5’ of movement on the Manhattan route per odd diagonal step we take. We need to take diagonal steps for the minimum between tgt_row and tgt_col to get into a lane where the remainder of our movement is straight. Putting it all together, the most efficient route from one space to another using these rules is given by:

#Our target (x,y) is the absolute value of the offset from the characters position to the target’s step_size = 5 tgt_x = abs(char_row - tgt_row) tgt_y = abs(char_col - tgt_col) distance = step_size * (tgt_x + tgt_y - ceil(min(tgt_x, tgt_y)/2))

Using this as our basis, we can draw out a grid for movement costs on an arbitrary grid:

Limiting the output to our characters movement speed, we can correctly highlight the spaces our character can reach in a single move. We can also assign a target to a grid position (noted here by being underlined, and use the same formula to calculate the distance to a target:

Neat.