If you have not played OneShot yet, go do that RIGHT NOW. It's available on Steam and itch.io, and it's one of my favorite games of all time.
This puzzle appears in the Factory in the Refuge, and is a variant of the game Mastermind. You have 5 lights that you can toggle to either orange, blue, green or red. There's a correct pattern of 5 colors that you're supposed to guess. After you set each light, you can pull a lever, and it will tell you how many lights you got correct. You get 10 attempts before the puzzle resets itself. Depending on the pattern, it can be quite easy or fairly tricky to guess the right pattern.
I was super intrigued if I can come up with a way to solve this puzzle 100% of the time regardless of what the pattern is, so I wrote two solvers for this puzzle around a year and a half ago. The human logic solver is also available in JavaScript, hosted at https://osmmsolver.rkevin.dev with the help of @Fayti1703, who did all the JS and frontend work. I recently revisited this after watching a friend play OneShot to see if I can come up with something better.
The first idea I had was to find the number of lights for each color, then dealing with the possibilities on a case-by-case basis. Some cases are pretty complicated, and I had to use some fancy partitioning to find whether a color is on the left or right side. Overall, this worked pretty well, and I was able to guarantee the algorithm can guess any solution within 10 tries. It takes 7.6 tries on average, and the guess count distribution is [0, 1, 1, 3, 15, 38, 136, 254, 308, 196, 72]. An explanation on my thought process for this is at the end of this document, and there are some comments in the code you can follow.
I then tried a more AI-ish solution of trying to use maximin and eliminate as many guesses as possible. For every turn, I go through all solutions that are still possible based on prior guesses, and I try all 4**5 possible guesses on them. I find the guess that will, in the worst case, eliminate the most number of solutions that are still possible. This didn't work very well, and sometimes needed 12 tries to fully solve a puzzle. I left this in as a historical curiosity and a demonstration of how horribly I write code one and a half years ago (not that I've improved much tbh).
The best solver I found was to maximize the amount of entropy I get from a single guess. For every turn, I go through all solutions that are still possible, and I try all 4**5 possible guesses on them. I calculate the amount of expected entropy I'll get from each guess and try to maximize that. This is by far the best solution I've found, guessing the solution in only 5.8 tries on average, and guarantees finding a solution in at most 8 tries. The guess count distribution is [0, 1, 3, 10, 55, 243, 505, 201, 6, 0, 0]. It is a lot less efficient than the human logic solver, and some precomputation is used to speed it up (you can technically precompute everything, and then solving any puzzle is just a lookup, but I felt it was unnecessary).
BTW, this is inspired by the super cool 3blue1brown video on information theory and Wordle. It's a super good primer on entropy in the information theory context.
The first thing I do is to determine how many of each color there are. I do 3 queries on all orange, all blue, and all green. The number of reds should be 5 minus the sum of the other colors. Sometimes you can get away with just doing 2 queries (if there's only orange and blue switches, you will notice they sum to 5), or even just one (if it's all orange to begin with). Using this, I split the solution into 6 types and I'm dealing with them separately.
We should've gotten rid of the possibility of all orange, blue, and green from the first 3 queries, so if we see there are 5 red switches then we're done! Just try 5 reds.
From now on, I'll use c1, c2, c3 and c4 to refer to the 4 colors. It doesn't matter what their names are, only their frequency matters. In this case, there are 4 c1s and 1 c2 in total. This is also easy to deal with, since there are only 5 possibilities ([c2, c1, c1, c1, c1] to [c1, c1, c1, c1, c2]), so just try them all.
We need to find two c2s, so we can do it one at a time. We make every switch c1 and just vary where c2 is in the first 3 spots. If we find the first c2 in the first 3 spots, we can fix that in place and start searching for the second c2 from that point on. Here's an example:
attempt(c2, c1, c1, c1, c1) == 3 # If the `c2` is right, the three `c1`s must also match, so the result should be 4. If it's 3, we haven't found it.
attempt(c1, c2, c1, c1, c1) == 3 # still nope
attempt(c1, c1, c2, c1, c1) == 4 # found first c2! fix that in place and look for the second one
attempt(c1, c1, c2, c2, c1) == 3 # nope
attempt(c1, c1, c2, c1, c2) == 5 # jackpot!
If there are no c2s in the first 3 spots, then the solution has to be [c1, c1, c1, c2, c2].
Finding the first c2 can take a maximum of 3 tries, and finding the second takes at most 2. That, plus the original 3 to determine which type of solution, brings us up to at most 8 tries.
This is where things get tricky. My thought process is we can try to pin down the two c1s first. If we know their positions for sure, there's 3 spots left for two c2s and one c3, so there's 3 possibilities and you can just use 3 attempts on that. That means we get 10(total)-3(used to figure out type)-3(used to bruteforce c2 and c3)=4 attempts to figure out where the two c1s are exactly.
I'm going to split the 5 positions into two "partitions". The first partition is the first 2 spots and the second partition is the last 3 spots. We know c4 is guaranteed to not exist, so we can use it to probe how many c1s are in each partition. We ask [c1, c1, c4, c4, c4], and the result should tell us how many c1s are in the first partition.
That's nice! There's only two spots in the first partition, so we know c1 must be in the first two spots. We can then start bruteforcing c2 and c3 given c1's positions (implemented by try221withknown2 in my code) using at most 3 attempts.
We know that both c1s must be in the second partition. You have 3 attempts (ignoring the try221withknown2 step) left to find where they are, which should be easy. You can implement it however (such as using [c4, c4, c1, c4, c4], [c4, c4, c4, c1, c4], [c4, c4, c4, c4, c1] to try one at a time). My solution is a bit convoluted and it doesn't have to be. After you pin down c1s, use try221withknown2.
This means that there's also another c1 in the second partition. Knowing that one out of two spots in the first partition is c1 helps us pin down where it is in one try (if [c1, c4, c4, c4, c4] == 1 then it's the first spot, otherwise the second). This leaves us 2 tries to know where the other c1 is. Since we know it has to be in the last 3 spots, we can just try [c4, c4, c1, c4, c4] and [c4, c4, c4, c1, c4], and if it's not in either of those places we know it has to be in the last spot. Therefore, we pinned down where c1 is and we can let try221withknown2 do the rest.
We also use partitions for this type of solution, but instead of finding two of the same color, we're trying to find c2 and c3. I'm using [c2, c2, c3, c3, c3] to figure this out.
Awesome! This means c2 is in the first partition and c3 is in the second, guaranteed. Similar to the fourth type case where there's one c1 in each partition, we can use 1 attempt to find where c2 is in the first partition, and 2 attempts to find where c3 is in the second partition. This means we used 3(type discovery)+1(find this case)+1(find c2)+2(find c3)=7 attempts and we know where c2 and c3 is. The rest 3 spots are all c1.
This is the exact opposite of the first case, since we know c3 is in the first partition and c2 is in the second. We can use the exact same method (just with c2 and c3 flipped) to find the solution.
This is more complicated than the other case. We know we got 1 correct, so c2 and c3 must be in the same partition, but we don't know which one. We can find out by using c4 (guaranteed incorrect) and asking if [c2, c2, c4, c4, c4] has any correct.
If you have 1 correct, that means c2 and c3 are both in the first partition. You can find out which is which using 1 query, and you know the entire solution.
If you have 0 correct, that means c2 and c3 are both in the second partition. We've used 5 queries so far, so we need to find their locations in another 5. We can find out where c2 is in 2 queries(ask [c4, c4, c2, c4, c4] and [c4, c4, c4, c2, c4]. If neither of those have hits, c2 must be in the last spot), and where c3 is in another query (we have 2 choices for c3 left, choose between them). Afterwards, we know where c2 and c3 is, and we fill the rest with c1s. Done!
This is by far the worst type to deal with, since we don't have a nice dummy color that's guaranteed to fail a match. Oh well, we might as well find out how to do this.
I start off by doing a similar thing with type 5, where I find out which partition the two least common colors are in using [c3, c3, c4, c4, c4].
c3 must be in the first partition and c4 must be in the second. Moreover, since c4 is in the second partition, it's definitely not in the first (since there's only one c4). This is nice because we can use one query ([c3, c4, c4, c4, c4]) to find exactly which spot in the first partition is c3.
Once we fix c3's position, we can use it as a guaranteed fail to find further colors. We've used 5 queries so far, so we use another 2 to find where c4 is (fix the first two spots as one c3 and one c4 such that you know there's exactly 1 match in the first partition, then vary the last three spots like [c4, c3, c3] and [c3, c4, c3]). We now know where c3 and c4 is, and we need to fit two c1s and one c2 into the remaining 3 spots. There's only three possibilities, so try them all and it should work in exactly 10 tries.
This is the exact opposite of the case above, and you can use the exact same procedure with c3 and c4 flipped. The logic is exactly the same.
F in the chat. We know c3 and c4 are in the same partition, but we don't know which one. This is a bit of a brainmeld, but we'll get through this last case between us and victory. We can actually use 1 query to figure out which partition they're both in: [c3, c3, c1, c1, c1].
Assuming both c3 and c4 are in the first partition, the first partition will have 1 match with the above pattern. Also, both c1s have to be in the second partition because there's no space in the first one, so we know we will get exactly 3 matches.
Assuming both c3 and c4 are in the second partition, things are a bit tricky. We know two out of the three spaces in the second partition is occupied, but we don't know if the third spot is a c1 or c2. If it's a c1, we would have one match in the second partition (the single c1), and no matches in the first partition. If it's a c2, we would have no matches in the first or second partition.
Using this reasoning, we can split our searching into three final cases. We have used 5 queries so far, including the [c3, c3, c1, c1, c1].
We know both c3 and c4 are in the first partition, and also both c1s are in the second partition. This means we can determine where c3 and c4 are using one query ([c3, c1, c1, c1, c1]). We know the c1 in the second spot is guaranteed not to match, and the second partition is guaranteed to match exactly 2, so looking at the result (2 or 3) we can tell where c3 is, and c4 must be in the other spot. Fixing down c3 and c4, we just have 3 possibilities of where to put c2 (and fill the last two spots with c1), and we win!
We know both c3 and c4 are in the second partition, but we also know both c1s are in the first partition. This is pretty cool, since we know exactly where the c1s are. We can use 2 attempts to find what the color at the middle spot is ([c1, c1, c?, c1, c1] and vary c? to be c2 or c3. If c? is right, then 3 lights match, otherwise 2. If neither c2 and c3 are right, it's c4). The last two spots are for the two unused colors, so there's only 2 possibilities. Try them both, and we got it in 9 attempts.
This means both c3 and c4 are in the second prtition, and there's one c1 in each partition. The second partition has one c1, one c3 and one c4, which means c2 can only be in the first partition. We can find where c2 is using [c2, c1, c1, c1, c1], because we know the second partition has one and only one match, and the first partition is 0 matches if it's [c1, c2] and 2 matches if it's [c2, c1].
We have 4 tries left, but we know the entire first partition. Similar to the above case, we use 2 tries to find what the color of the middle spot, then there's only 2 possibilities left and we try them both. Done! That was a journey.