-
Thisisfine
After a long period of not posting, I present my latest doodle, just in time to see off 2020. You can try it out on kubernetes: kubectl run -it --rm --image=ghcr.io/pdevine/thisisfine tif or for the docker inclined: docker run -it --rm ghcr.io/pdevine/thisisfine … and it should look something like: This marks a return to using block mode in Go-AsciiSprite, and it’s the first time I’ve ever used one for doing a doodle. The first project I did with block mode was Text Invaders!, and I also put together a demo for something that resembled Super Mario Bros, but I was never really happy with the way either worked. The biggest problem was movement. When I created Go-AsciiSprite originally I had only been thinking of ways to move normal text characters around the screen. That worked great, but with block mode we effectively doubled the resolution of the terminal. If you moved a block mode sprite, it would always move an even number of pixels around the screen. You could never move it by an odd number of pixels. This ended up being fine for Text Invaders!, but I felt like the movement looked really jerky. For a while this seemed like a bit of a dead end.
Read more… -
Mastermind
A friend recently posted this puzzle that I thought was pretty awesome: This is one of those brain teasers that I think looks somewhat daunting at first, but if you have played the game Mastermind before, it’s pretty straightforward to solve. I’ve been giving Mastermind as a software engineering programming interview exercise for more than a decade. What I like about it is that it’s easy to describe to someone who has never played the game before, and also that it has three parts to it which get progressively more difficult. This first starts off with a simple recursive algorithm (or you can solve it with binary math for those inclined) for generating a search space. It then requires you to write a slightly tricky “scoring” function for determining which digits are in the correct or incorrect places. If you’ve made it this far and there’s time left, the third part is about writing an algorithm for “solving” the code. Here’s the code I used to solve this particular puzzle: import itertools combos = itertools.product(range(0, 10), repeat=3) def score(guess, secret): red = 0 g_nums = [0] * 10 s_nums = [0] * 10 for x in range(0, len(guess)): if guess[x] == secret[x]: red += 1 else: g_nums[guess[x]] += 1 s_nums[secret[x]] += 1 white = sum([min(g_nums[x], s_nums[x]) for x in range(0, len(g_nums))]) return red, white def filter(guess, g_score): global combos n_combos = [] for c in combos: if score(c, guess) == g_score: n_combos.
Read more… -
Levenshtein Distance
A few weeks ago I posted about One Way Changes, which was one of the coding challenges in Cracking the Coding Interview. A One Way Change would check to see if two words, such as “flood” and “floor” are one change away from each other by removing, inserting, or substituting one character for another one. I’ve been thinking a lot about search recently, and learning about where the industry is at with NLP. One of the first things I ran in to was an exercise for calculating how many inserted, removed, or substituted characters it takes to get from one word to another. This is the minimum edit distance or the Levenshtein distance between two words, and it seemed strange to me that CtCI didn’t include this problem in the Recursion and Dynamic Programming chapter, given that it superficially feels really close to the One Way Change exercise. Surprisingly though, the easiest way you can calculate the Levenshtein distance is unrelated to actually inserting, removing, or substituting characters into your first string. I guess that shouldn’t be so suprising given how many possible characters there are that you could potentially try, but my first intuition was to try to think about how I could reuse my solution to the One Way Changes problem.
Read more… -
Is Rotation
I’m not certain how practical this next problem is, but it seems to be a staple of interviewing questions. The problem is to write a function to check to see if one string is a rotation of another string. By rotation, they’re asking if the string is offset by some amount of characters, and then has excess characters prepended to the beginning of the string. For example, “erwat” is a rotation of the string “water”. I ended up solving this two different ways, the first was to just brute force the problem by writing a function which would rotate one of the strings until it matched the other string. Here’s the code: def isRotation1(s1, s2): if len(s1) != len(s2): return False def rotateStr(mystr, count): return mystr[count:] + mystr[0:count] for n in range(len(s1)): if s2 == rotateStr(s1, n): return True return False This is pretty ineffecient. The string copy is super expensive, so the runtime of this is O(N2) which is pretty ugly. A smarter way of solving this problem is to concatenate one of the strings against itself and then searching for the other string inside of the larger string. With our “erwater” example, we end up with a larger string which is “erwaterwat” and then we just search in that string for “water”.
Read more… -
Set Matrix Zeros
Much like the Rotation Matrix, the “Set Matrix Zeros” problem involves being careful about not destroying the existing matrix which is being operated on. The idea is that given a cell in the matrix which is set to zero, set all of the other cells in the same row or column to zero. I tackled this in two ways which are almost identical. First up was just making a copy of the initial matrix and working on that instead. Here’s the code: import copy def zeroMatrix1(mtrx): newMtrx = copy.deepcopy(mtrx) def zeroRowCol(r, c): for n in range(len(mtrx)): newMtrx[n][c] = 0 for n in range(len(mtrx[0])): newMtrx[r][n] = 0 for r in range(len(mtrx)): for c in range(len(mtrx[0])): if not mtrx[r][c]: zeroRowCol(r, c) return newMtrx The deepcopy is important here otherwise you end up with a copy of the original matrix and you’ll be operating on that instead. There’s not really a “trick” here per se, but the key is if we hadn’t made the copy and zeroRowCol() operated on the original matrix, it would fill in everything with lots of zeros. Since making a copy of the matrix is expensive, there is a way of doing this by just keeping track of any cells we found that had a zero, and calling zeroRowCol() later.
Read more… -
Rotation Matrix
Next up is “Rotate Matrix” which, unsurprisingly, rotates an X by X matrix by 90 degrees. There are two ways of tackling this problem, the first which is creating a new matrix and copying over each of the cells, and the second is to be able to swap elements in place. The second is harder because it means you have to iterate around the matrix with each of the values because you don’t have a separate space to put them. Let’s go over the solution which copies elements to a new matrix: def rotateMatrix(mtrx): N = len(mtrx) newMtrx = [[0 for x in range(N)] for y in range(N)] for r in range(N): for c in range(N): newMtrx[r][c] = mtrx[N-1-c][r] return newMtrx and let’s say we have a 4x4 matrix which looks like: [['A','B','C','D'], ['E','F','G','H'], ['I','J','K','L'], ['M','N','O','P']] We want to rotate that matrix so that it looks like: [['M','I','E','A'], ['N','J','F','B'], ['O','K','G','C'], ['P','L','H','D']] In rotateMatrix() we create a new blank 4x4 matrix initially filled with zeros. We then walk through each of the cells of the matrix and take each cell in each column from the bottom up. The runtime here is O(N) even though we have the two for loops because we’re only ever touching each cell once.
Read more… -
Run Length Encoding
I was actually somewhat surprised that Run Length Encoding (they call it “String Compression”) was included in Cracking the Coding Interview, because it’s not particularly a difficult algorithm to write. I would have thought that writing Huffman Encoding would have been more interesting in interviews given the entire chapter on graphs and trees in the book. The key to RLE is to remember the last character as you’re iterating through the string. If the next character is different, write out the current character and append a count of the number of times you have seen it. Here’s the code: def runlength(s): counter = 0 lastChar = '' newStr = "" for currChar in s: if currChar == lastChar: counter += 1 else: if lastChar != '': newStr += lastChar + str(counter) counter = 1 lastChar = currChar newStr += lastChar + str(counter) return newStr I didn’t bother with the check for whether the returned string is shorter than the string which was passed in, however, it’s easy enough to do. But, there is a slight problem here, and I’m guessing that they’re expecting interviewers to play this up. The runtime complexity for iterating through the string is going to be O(N), but the string copy, in theory, is going to be O(N2) every time we concatenate the new string.
Read more… -
Happy Halloween!
Happy Halloween everyone! To celebrate, I’ve released a new Docker Doodle! $ docker run -it --rm docker/doodle:halloween2019 A fun fact: I made the ASCII moon follow the actual phases of the moon, so in theory it should change to a “first quarter” moon on November 4th. Halloween this year gets a waxing crescent moon.
-
One Way Changes
Next up is writing a program which can compare two strings to see if they’ve been changed by having had one character removed, one extra character inserted, or one character replaced with a different character. I tackled this by breaking it into three separate problems. I think the point of this question is to see whether you can decompose a problem into smaller steps and then see how you can glue them back together again. First up is writing the function which can remove a character from one string and see if it matches the other string. def removeChar(s1, s2): for n in range(len(s1)): if s2 == s1[:n] + s1[n+1:] return True return False This is just walking through each character of the string and then using slicing techniques to construct new possible strings. If we match our second string, return True, otherwise just return False. Next we need to check if a character was inserted into the first string. We could write a routine which adds each letter of the alphabet into each position of our first string, but that is needlessly fussy and would take a lot of time and complexity when there is a far better option.
Read more… -
Palindrome Permutations
This was kind of a weird problem, but the solution was kind of fun to write. Given a string, determine if it’s a palindrome and then write out all the possible permutations of palindromes that string potentially would have. Here’s my solution: import collections import itertools def palinpermute(s): s = s.replace(" ", "") c = collections.Counter(s) pivot = '' for k, v in c.iteritems(): if v % 2 != 0: if not pivot: pivot = k else: return (False, []) newStr = "" for k, v in c.iteritems(): if k != pivot: newStr += k*(v/2) palins = list() for c in itertools.permutations(newStr): palins.append("".join(c) + pivot + "".join(reversed(c))) return (True, palins) Like a lot of the other solutions to string problems, we’re back to using the Counter again. In this case we use it to make certain that for each character, there has to be a matching one. If there isn’t a matching one, choose that character as a pivot point for our palindrome. Once we’ve selected a pivot point, there can’t be another one, so just return False and an empty list if we find one. This next part is probably not obvious: newStr = "" for k, v in c.
Read more…