July 12th, 2023: Blackjack

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 3, LeetCode 451. Sort Characters By Frequency: Sometimes Python Is Magic

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

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

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?”

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

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

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

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.

Nov 12, Leetcode 295. Find Median From Data String- Tricky

https://leetcode.com/problems/find-median-from-data-stream/
Language: Python — Time: 90 minutes
Full Code on Gitfront.io — https://github.com/cswartzell

Todays challenge was deceptively difficult, and fun. It seems simple enough, but extremely tight timing constraints required some advanced thinking to solve this one.

The goal is to setup a data structure such that the median of all as-yet stored values could be quickly retrieved. Clearly we’d need to store these in an ordered list to grab the median. Note the median of a set with an odd number of elements is the middle value, but if there are an even number of elements we need the mean of the central two.

My instinct was to use a heap as I knew maintaining the sorted order as we collect new elements needed to be quick. While it works well for this, unfortunately retrieving a list in sorted order from a heap is an additional O(nlogn). A heap does a great job of input, and retrieval of the top (minimum value), but we pay the price on the backend if we need the heap sorted in list form.

Can we cheat and just add the elements to an unsorted list, then sort and return the median only when called for? Alas, Time Limit Exceeded, as it probably should. It seems there is a Python library called “sortedList” that has optimized functions for doing this more directly, but I wasn’t aware of those while solving this.

Ok, what else? Insertion Sort is pretty fast, can we implement that? My first attempt was a flop as the selection sort algorithm I know appends to the rear of a list, then swaps it’s way forward through most other elements; almost bubble sort. I’ll need to review improved/correct versions of Insertion Sort as it’s quick and easy to code.

Still not quick enough. Well, why start by appending a value to the end an linearly scanning to find its intended position, we can do much better with a Binary Search. After a bit of fumbling with the usual uncertainties about the exact formatting of a Binary Search, I managed to write a method that quickly finds our intended position.

Another user on Leetcode has written an awesome template for quickly writing a binary search, and handling the little details so you dont end up with off by one errors. Seen Here.

Inserting our value using this index and string slicing and concatenation… is too slow. Wow, this is a strict challenge. Hard to beat Binary Search (impossible actually, right?). Well, we know concatenation is slow. Turns out list.insert(position, X) is quicker, and manages to pass!

But wait! After solving the problem I had an epiphany. I was thinking about using a Two Pointer solution, needing one pointer to keep the Maximum Value of all items to the left of the center, and another for the Minimum Value for all items the right. Hey, that’s just the tops of a minHeap and a maxHeap! We can use a heap structure to solve this after all, if we use two heaps. To deal with even/odd number of elements we can store a separate Middle variable. We need to keep the two heaps equally sized, so will be rotating values through this middle variable as we add new elements to one heap or the other.

After quite a bit of tinkering, I hit upon a solution requiring five distinct cases. I suspect with some refactoring I could clean this up a bit, but I’m satisfied with how it worked:

0: Initialize the structure (twice) with the first two elements

1: If there is no middle, should the new element be the middle?

2: If not, it should go on one heap or the other. pop an element from that heap to make room for the new element, retaining both heaps as equally sized. Popping from a heap is guaranteed to give us the element closest to the center so it can be the new middle.

3: If there is a middle, and the new element is equal to it, move middle into one heap, and the new element into the other. Doesn’t matter which, they are equal. Note we are setting Middle to “None” not 0

4: There is a middle, and the new element is larger than it. Add the new element to the “right”, which is our minHeap. Move the middle to the “left”, our max heap, and set middle to “None”.

5: Else (we have a middle value, and the new element is smaller) Simple reverse of step 4. Add to the maxHeap on the left, and moving the middle to the right heap, setting it to “None”

It turns out in Python there isn’t a built in maxHeap. Instead, this is accomplished by simply flipping the sign for all inputs and treating it as a “reverse minHeap”. With the sign flipped the “largest” input value will be at the top of the minHeap as the most negative number. We just need to remember to flip the sign again whenever we retrieve values from our improvised maxHeap. Python also suggests some combined operations that push and pop simultaneously, and apparently more efficient.

Using these two heaps, we can instantly return the median as either the Middle if not “None” or the mean of the tops of the heaps. A very satisfying answer, though it took quite a bit to get there.