Skip to content
PodSubs
ShowsPeopleGuestsJobsNewsEvents
More
BlogPodCred
Menu
ShowsPeopleGuestsJobsNewsEventsBlogPodCredNetworksSign in
Join nowSign in
  • Shows
  • People
  • Jobs
  • News
  • More
    • Guests
    • Events
    • Blog
    • PodCred
    • Networks
    Join nowSign in

ADSP: Algorithms + Data Structures = Programs

ADSP: Algorithms + Data Structures = Programs artwork

Episode 271: Mastermind Algorithms

Jan 30, 202619 minAudio
  • Apple Podcasts

In this episode, Conor talks about algorithms used to solve the Mastermind game and specifically a beautiful use of an inverse algorithm. Link to Episode 271 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Show Notes Date Recorded: 2026-01-29 Date Released: 2026-01-30 "Point-Free or Die: Tacit Programming in Haskell and Beyond" by Amar Shah C++98 std::transform C++23 std::views::zip_transform zip_transform Hoogle Translate C++98 std::accumulate C++23 std::ranges::fold_left_first The Twin Algorithms - Conor Hoekstra - CppNorth 2022 frequencies Hoogle Translate outerProduct Hoogle Translate C++23 std::views::adjacent_transform Hoogle Translate adjacent_transform Hoogle Translate scan ADSP Episode 146: 🇸🇮 SRT23 - Algorithms, BQN's Superpowers & More! Combinatory Logic Intro Song Info Miss You by Sarah Jansen https://soundcloud.com/sarahjansenmusic Creative Commons - Attribution 3.0 Unported - CC BY 3.0 Free Download / Stream: http://bit.ly/l-miss-you Music promoted by Audio Library https://youtu.be/iYYxnasvfx8

Audio and video play straight from the show's own hosting. PodSubs stores and serves no media.

Transcript

From the show. Tap a time to play from there.

ConorThe 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. And the inverse operation that we want here is an inverse plus scan.

ConorAnd 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. It is currently January twenty-ninth at just after five PM Eastern Standard Time.

ConorAnd 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.

ConorThere 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.

ConorWe're going to record that later. And maybe we won't even record it. 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.

ConorIf 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. 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.

ConorThere 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. 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.

ConorAnd 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. 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.

ConorAnd the information that you get with each guess is the exact same information you get with Wordle. 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.

ConorI 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.

ConorAnd if we're staying in C land, a binary operation would be a two-range std transform if you're in pre-range land. 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.

ConorSo 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. 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?

ConorI 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. 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.

ConorClojure calls it frequencies. Pandas and libraries, similar to pandas, call it value counts. 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.

ConorOr 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.

ConorAnd 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.

ConorSo 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.

ConorAnd 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.

ConorAnd 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.

ConorSo 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. 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.

ConorBut 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. 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.

ConorThe 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. 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.

ConorThe 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. 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.

ConorAnyways, there's there's different camps on what's the correct behavior. 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.

ConorAnd 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. So if you want to do something two, three times, you just put it to the power of two or three.

ConorBut 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. 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.

ConorSo 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. 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.

ConorSo 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.

ConorAnd 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.

ConorIt 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. Go check out Amar Shaw's point free or die talk if you haven't.

ConorYou 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. 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.

ConorThanks 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. Our tagline is chaos with sprinkles of information.

Open the transcript file

Hosts and Guests

Nobody is credited on this episode yet.

Credit the people on this episode

Be the first to rate this episode

More episodes

All episodes
  1. Episode 313: C++26 Reflection vs CRTP, AI, Kids & More with Zach Laine

    Nov 20, 202647 minAudio

    In this episode, Conor and Bryce chat with Zach Laine about C++26 Reflection vs CRTP, AI, kids & more. Link to Episode 313 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP:...

    • Apple Podcasts

    Credit the people on this episode

  2. Episode 312: The C++26 Contracts Fiasco

    Nov 13, 202652 minAudio

    In this episode, Conor and Bryce chat with Zach Laine about the C++26 contracts fiasco. Link to Episode 312 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The Podcast:...

    • Apple Podcasts

    Credit the people on this episode

  3. Episode 311: Career Changes, GPUs & More with Zach Laine

    Nov 6, 202628 minAudio

    In this episode, Conor and Bryce talk with Zach Laine about his career and the career changes he has made. Link to Episode 311 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials...

    • Apple Podcasts

    Credit the people on this episode

  4. Episode 310: Leaving NVIDIA for... ?

    Oct 30, 202624 minAudio

    In this episode, Conor and Bryce talk about Bryce's next chapter and where he is leaving NVIDIA for. Link to Episode 310 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The...

    • Apple Podcasts

    Credit the people on this episode

  5. Episode 309: Default Construction & CppCon 2026 with Jason Turner

    Oct 23, 202629 minAudio

    In this episode, Conor and Ben chat with Jason Turner about default construction in C++. Link to Episode 309 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The Podcast:...

    • Apple Podcasts

    Credit the people on this episode