Episode 271: Mastermind Algorithms

0:00Conor:The first thing that should come to mind is an algorithm called adjacent transform, or at least that's what comes to mind for me, because this is one of the most fundamental algorithms for performing transforms. That's not a basic transform. Your basic transform or map is applying a unary operation to a single element at a time. And then you have your binary transforms where you're performing binary operations on two different sequences of the same length, but that was our two-range std transform or zip transform that we talked about when calculating exact matches.

0:29Conor:And the inverse operation that we want here is an inverse plus scan. And your plus scan is your partial sum. And so you're getting the inverse of that, which is adjacent difference. So we have the correct algorithm in my opinion, stencil, adjacent transform, or adjacent map if you're in Haskell. But we also have access to the adjacent difference, which is what we actually want in this case, but we get access to that by inverting a plus scan, which is the whole reason behind adjacent difference in the first place.

1:00Conor:It is currently January twenty-ninth at just after five PM Eastern Standard Time. And was it four hours ago? I was outside in minus twelve feels like minus twenty degrees Celsius weather, which in Fahrenheit for our American listeners is ten Fahrenheit feels like minus four Fahrenheit. I was outside running, freezing, my hands off, and I was listening to a couple podcasts, and I realized that I did not have any recorded conversations for tomorrow's episode because I've been so busy.

2:26Conor:There was an internal conference at NVIDIA this week, and there's been a lot on the go. It slipped my mind. I was supposed to organize a recording with Ben. That did not happen. And we've only got a couple hours left. So we're back with another solo recording. I mentioned in the last couple episodes that there was going to be a podcast called The Podcast Purge. But we're going to do that. We're going to record that later. And maybe we won't even record it.

3:01Conor:But uh I I have something else I want to talk about, which I can't remember if it was with Bryce or with Ben. That in the last month I was programming the solution to the mastermind game. And I came across a beautiful, beautiful application of an inverse algorithm. And so this episode will be entitled Mastermind Algorithms. And I'll explain the game. If you've seen one of my talks or Amar Shaw's talk, you'll already know this game, or potentially, I'm assuming, I don't know, in how many countries this game exists.

3:40Conor:But probably 50% of folks have played this game at some point. But, anyways, that's what today's solo episode is going to be about. We'll see how long this runs for. It'll probably be a shorter episode, but I think it's it's pretty fantastic when I realized you could use an inverse algorithm to solve this problem a little bit more beautifully. So Mastermind is a game that is played by two people. There is a code maker and a code breaker. And you have eight colors typically to choose from, but for the purposes of programming this problem, I use the numbers one to eight.

4:15Conor:Usually it's like red, orange, yellow, blue, whatever, eight colors. But numbers, colors, they work just as well. And in the physical game, you choose a four-color code. Now you can use duplicate colors, so your code can be four reds in a row. You can use all unique colors. It can be red, orange, yellow, green. You can use two reds, two oranges, etc. And the goal is that I think there's like 10 or so guesses, and the code breaker has to guess the code within that number of guesses.

4:44Conor:So not dissimilar. Honestly, I'm pretty sure Wordle was inspired by Mastermind. So instead of having uh random colors and a random sequence, you have a set of 2,000 plus or minus words and only a certain uh, it has to be a valid word in order for it to be a Wordle possibility. Whereas in Mastermind, it can be any combination, permutation of those eight colors, including duplicate colors. And the information that you get with each guess is the exact same information you get with Wordle.

5:16Conor:Instead of having green and yellow to indicate uh correct letters in the correct spot and wrong letters in the wrong spot, you usually have a red and white pin that goes beside your clue. So honestly, yeah, Wordle. I did not think about Wordle when I started talking about this, but Wordle clearly is a you know hybrid version of Scrabble and Mastermind. And in the 2014 Strange Loop talk, which I have referenced in many of my talks and many of my podcast episodes, Amar Shaw gave a talk called Point Free or Die.

5:52Conor:I think it this the sub tagline is Tacit Programming and Beyond. And in this talk, he solves the solution to exact matches using the Blackbird combinator, which is composing a unary function after a binary function. So unary and binary meaning a function that takes one argument and a function that takes two arguments. So the and the two inputs to this algorithm for exact matches are your code and your guess. And if we're staying in C land, a binary operation would be a two-range std transform if you're in pre-range land.

6:36Conor:Or if you are in rangeland post-c plus plus 20, you have access to something called zip transform. It was called zip width in range v3, I believe. And this takes two ranges in a binary operation and does an element-wise computation of whether or not your elements are equal to each other. So the binary operation is equal. And then once you have this sequence of Booleans, your unary operation that follows is a summation. So you could do that with a std accumulate, or I believe there's a st, you know, std ranges fold left first that you can use.

7:12Conor:So this is the solution to exact matches. It's pretty straightforward. You do an element-wise comparison to see if elements are equal to each other, and then a summation after that. In array languages, this is just three characters. I covered this in my twin algorithms talk from I believe it was CPP North 2022? I can't remember. Sounds about right though, plus or minus a year. And I didn't cover the algorithm or solution for solving what is called near matches.

7:46Conor:So this is the equivalent of the yellow. So the exact matches is the equivalent of the green in Wordle, and the near matches is the equivalent of the yellow. And the naive way to solve near matches is to just remove the letters or numbers that correspond to your exact matches, and then do an algorithm that amounts to a frequencies or value counts, depending on your language. Clojure calls it frequencies. Pandas and libraries, similar to pandas, call it value counts.

8:19Conor:In Python, there's a collection called counter, which returns you a hash map where the keys are the unique values, and the values attached to those keys are the counts, hence why some languages call this value counts. And this is also referred to as a frequency map. Anyways, there's a bunch of different ways in different languages to kind of get the counts. And then once you have a quote unquote frequency map or counter collection, you just do an intersection of the key value pairs.

8:50Conor:Or if you're in an array language, the way that I have solved this is you do a table or an outer product with the values one to eight, and you do this with both your code and your guess, and then that's gonna give you an array of eight elements. And if you do a row-wise reduction on the outer product of this, you end up with the counts corresponding to each of the values one through eight. And then if you do an element-wise min across the eight element frequency array for both the code and the guess, you're gonna end up with the number of elements that are in the wrong location after you've removed the exact matches.

9:29Conor:And so this is it's not trivial, but it's not super complicated. And after that, you have your exact matches, your near matches, and you're good to go. You basically just return whatever format the problem requires, you can return these two values. And at some point when I was solving this in the last month, I realized having to do this filtering or removal of the exact matches before we do this kind of frequency map or outer product frequency array on the remaining letters or characters is a little bit irritating.

10:04Conor:So what if you instead of calculating exact and near, you calculate exact and all, meaning both exact and near. And that's just basically a simplified version of the near matches, because if you don't remove the exact matches when you do this frequency map, the exact matches are going to be included in the total of the frequency map or frequency array. And so then you have exact, all, and you can back out the near by subtracting from four the count that you got from your all calculation.

10:40Conor:And this is where the beauty of this inverse operation that I'm about to talk about comes in. Because at the end of the day, what you what you need is the exact matches, the near matches, and then the misses, because the information that you want to convey is basically a red or a green for an exact match, a white or a yellow for a near match, and then nothing or x's for no matches. So you don't actually need the all number, but it's easier to calculate the all number, and then we can back out the near number from the all number.

11:13Conor:And I think the f the way that I initially thought about this is that you just subtract all from four, and then that gives you near. But that's not nice. That's not nice, folks. So what I ended up doing is if you put the values for, all, and exact in a three-element array. So say we have one exact match, two near matches, so three matches over all for all, you're gonna end up with an array that is four, three, and one. But the array that we want backed out of that is we want one miss, two near matches, and one exact match.

11:52Conor:So you're starting off with the array four, three, one, and you want the array one, two, one for one miss, two near matches, and one exact match. And the first thing that should come to mind is an algorithm called adjacent transform, or at least that's what comes to mind for me, because this is one of the most fundamental algorithms for performing transforms. That's not a basic transform. Your basic transform or map is applying a unary operation to a single element at a time.

12:19Conor:And then you have your binary transforms where you're performing binary operations on two different sequences of the same length, but that was our two-range std transform or zip transform that we talked about when calculating exact matches. But then after that, there's a third type of transform that people don't well, some people know about it, but not enough people know about it. It's the adjacent transform. It was initially called adjacent difference in C 98, but that's a terrible name.

12:46Conor:We've covered that before. Don't encode the name of your binary operation into the name of your algorithm because you can do lots of things with adjacent difference that have nothing to do with subtraction, the default binary operation. The problem with adjacent difference is there's a bunch of problems. The name we just talked about. But on top of that, the output type, the type of your output sequence, is limited to be the type of your input sequence because they copy the first value of your input sequence to be the first value of the output sequence.

13:16Conor:So you're type constrained. And so really the first value of the output sequence isn't a isn't the application of a binary operation to any two elements. It's just it's just the first value of your input sequence. And then after that, they apply the binary operations. And I talked with Chris Tabella a while ago about this, because he studied Stepanov's algorithms, and apparently the motivation for it was round tripping. The relationship between adjacent difference and partial sum, the scan algorithm in C 98, was that you were supposed to be able to go back and forth between them.

13:49Conor:And I never thought that was a good argument because of the fact that you're, you know, type constraining yourself. And also, too, I think in general, when you are doing an adjacent transform or an adjacent map, you it just by definition you end up with one less element. I've talked to Phineas Porter about this, and that's how the prior algorithm works in Q, same as adjacent difference. Anyways, there's there's different camps on what's the correct behavior.

14:18Conor:But this is all to say that the first algorithm that came to mind was adjacent transform. But adjacent transform returns you n minus one elements. And if you remember the problem, you want to go from 4, 3, 1 to 1, 2, 1. And therefore, you don't actually want adjacent transform here. Otherwise, you have to kind of append some value. So in this case, you actually want adjacent difference. However, in the language I was solving this in Weewa, you have the adjacent transform in the form of an algorithm called stencil.

14:45Conor:And when you provide stencil with a binary operation, it is exactly the adjacent transform in C23. So it's returning you n minus 1 elements. However, they have something in Weewa, and a lot of array languages have this. We talked about it, I believe, on the way to Venice. It was part of the three amazing things about array languages that you should check out. And one of them was inverse operations. And so typically in array languages, there's something called the power operator where you can raise an algorithm or a primitive to the power.

15:15Conor:So if you want to do something two, three times, you just put it to the power of two or three. But you can also put it to the power of negative one, which then turns that operation into an inverse operation. And the inverse operation that we want here is an inverse plus scan. And your plus scan is your partial sum. And so you're getting the inverse of that, which is adjacent difference. So we have the correct algorithm, in my opinion, stencil, adjacent transform, or adjacent map if you're in Haskell.

15:43Conor:But we also have access to the adjacent difference, which is what we actually want in this case, but we get access to that by inverting a plus scan, which is the whole reason behind adjacent difference in the first place, because we wanted to be able to round trip. So round tripping, the motivation for designing, in my opinion, a flawed algorithm, adjacent difference, we get access to that via the inverse plus scan. You've got an inverse modifier.

16:11Conor:It's absolutely beautiful, folks. So we're not in Weewa, you don't actually have to put something to the power of negative one. They just have an inverse operation that they call un. So it reads unpluscan, which is basically adjacent difference. Now you might be thinking, how does doing an unpluscan on 431 get you one, two, one? You have to reverse the 431 to be one three four, and then you're going to copy one to be your first element, then three minus one is two, then four minus three is one, and you end up with one, two, one.

16:39Conor:So the code actually reads unpluscan reverse of your three-element array, which you form by coupling four, and the result of all and exact applied to your code and your guess, and you're having to use the fork. The phi one combinator in this case because you are applying all and exact dyadically. A rare use of the phi one dyadic fork. A little bit of combinatory logic there for you, folks. So we've got the B1 combinator and exact. We've got both, which is the Psi combinator, aka over in all, because you're doing your frequency map on both of your arrays, your code and your guess.

17:17Conor:And then we've got the dyadic fork, the phi one combinator. Fantastic, folks. An unplus scan, which it just brought joy. It brought joy to me, folks, because I always in the back of my mind think about how I look up to Stepanov so much, and I understand the motivation of wanting to round trip. There's a nice kind of symmetry there. But I just fundamentally disagree that the ultimate generic version of a binary operation applied to adjacent elements, you shouldn't be copying that first element to the output sequence.

17:49Conor:It should be returning you n minus one elements, but you can get access to that round tripping with an inverse modifier. Call it whatever you want. It's called undo in BQN, it's called un in WeWa. It's called nothing in APL because they just do power. Negative one. Fantastic, folks. Absolutely fantastic. We went 20 minutes. We'll see how I edit this down. Hope that gave you something to think about. We got the combinators. Check out combinatoriologic.com.

18:16Conor:Go check out Amar Shaw's point free or die talk if you haven't. You can also check out the twin algorithms talk. Talks about how I fell in love with array languages. Lots to think about, folks. Unplus scan is a better version of adjacent difference. And we've got everything we want. We got everything we want. We got the generic adjacent transform in the form of stencil, and we've got adjacent difference in the form of an unplus scan. Whew. All right, folks.

18:40Conor:Next week you'll hear from Ben and I together. Until then, have a good one. Be sure to check these show notes either in your podcast app or at adspthepodcast.com for links to anything we mentioned in today's episode, as well as a link to a GitHub discussion where you can leave thoughts, comments, and questions. Thanks for listening. We hope you enjoyed and have a great day. Low quality, high quality. That is the tagline of our podcast. That's not the tagline.

19:04Conor:Our tagline is chaos with sprinkles of information.