rkevin-arch/README.md

## README.md

      
    Raw
  

              README.md
            
          
    OneShot Refuge Factory Puzzle Writeup

The problem

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.


Solutions

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.
Human logic solver

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.
Minimax solver

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).
Max entropy solver

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.
Ranty explanation on the human logic solver

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.
First type: all red

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.
Second type: 4 of one color, 1 of another

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.
Third type: 3 of c1, 2 of c2, no c3 or c4

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.
Fourth type: 2 of c1, 2 of c2, 1 of c3, no c4

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.
Case: 2 c1s in 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.
Case: 0 c1s in the first partition

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.
Case: 1 c1s in the first partition

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.
Fifth type: 3 of c1, 1 of c2, 1 of c3, no c4

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.
Case: [c2, c2, c3, c3, c3] says 2 correct

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.
Case: [c2, c2, c3, c3, c3] says 0 correct

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.
Case: [c2, c2, c3, c3, c3] says 1 correct

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!
Sixth type: 2 of c1, 1 of c2, 1 of c3, 1 of c4

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].
Case: [c3, c3, c4, c4, c4] says 2 right

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.
Case: [c3, c3, c4, c4, c4] says 0 right

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.
Case: [c3, c3, c4, c4, c4] says 1 right

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].
Case: [c3, c3, c1, c1, c1] has 3 matches

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!
Case: [c3, c3, c1, c1, c1] has 0 matches

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.
Case: [c3, c3, c1, c1, c1] has 1 match

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.

  
## mastermind.py
from enum import IntEnum
import math

class Color(IntEnum):
    ORANGE = 0
    BLUE = 1
    GREEN = 2
    RED = 3
    def __repr__(self):
        return self.name

class SolveSuccess(RuntimeError):
    pass

class Oracle:
    def __init__(self, soln):
        self.soln = soln
        self.attempts = 0

    def attempt(self, attempt):
        result = sum(1 if a==b else 0 for a,b in zip(self.soln, attempt))
        self.attempts += 1
        print('ORACLE ATTEMPT', self.attempts, attempt, result, 'CORRECT')
        if result == 5:
            raise SolveSuccess
        if self.attempts == 10:
            raise Exception("Solve attempts exceeded on pattern", self.soln)
        return result

def int2pattern(i):
    p = []
    for _ in range(5):
        p.append(Color(i%4))
        i //= 4
    return p

def str2pattern(s):
    mapping = {
        'O': Color.ORANGE,
        'B': Color.BLUE,
        'G': Color.GREEN,
        'R': Color.RED,
    }
    return [mapping[c] for c in s]

class HumanLogicSolver:
    # this solver can solve all possible puzzles in 10 attempts
    # it takes 7.62109375 tries on average
    # guess count distribution is: [0, 1, 1, 3, 15, 38, 136, 254, 308, 196, 72]
    # an explanation is in the attached markdown document
    def __init__(self, oracle):
        self.oracle = oracle

    @classmethod
    def solve(cls, oracle):
        cls(oracle).startsolve()
        # we should never get here
        raise Exception("Algorithm freaked out on pattern", oracle.soln)

    def startsolve(self):
        # first step, determine how many of each color there are, then dispatch it to a subsolver
        ocount = self.oracle.attempt([Color.ORANGE]*5)
        bcount = self.oracle.attempt([Color.BLUE]*5)
        if ocount + bcount == 5:
            # we know there are no green or red ones left
            gcount = 0
            rcount = 0
        else:
            # try all greens
            gcount = self.oracle.attempt([Color.GREEN]*5)
            # red would just be the rest
            rcount = 5 - ocount - bcount - gcount

        counts = [(ocount, Color.ORANGE), (bcount, Color.BLUE), (gcount, Color.GREEN), (rcount, Color.RED)]
        counts.sort(reverse=True)
        # 1st case, only one color, then rcount is 5 (ocount bcount and gcount cant be 5 since their attempt would succeed already
        if counts[1][0] == 0:
            # we're done!
            self.oracle.attempt([Color.RED]*5)
            return
        # 2nd/3rd case, only 2 colors, which could have counts 4-1 or 3-2
        elif counts[2][0] == 0:
            if counts[0][0] == 4:
                solver = self.solve41
            else:
                solver = self.solve32
        # 4th/5th case, 3 colors, which could be 2-2-1 or 3-1-1
        elif counts[3][0] == 0:
            if counts[0][0] == 2:
                solver = self.solve221
            else:
                solver = self.solve311
        # 6th case, all 4 colors, which has to be 2-1-1-1
        else:
            solver = self.solve2111
        # give it the colors and start solving!
        solver(*[i[1] for i in counts])

    def solve41(self, c1, c2, c3, c4):
        # 4 c1s, 1 c2
        # should be really easy, just vary where c2 is
        for i in range(5):
            self.oracle.attempt([c2 if i == j else c1 for j in range(5)])

    def solve32(self, c1, c2, c3, c4):
        # 3 c1s, 2 c2
        # find the first c2 in the first 3 spots
        for i in range(3):
            if self.oracle.attempt([c2 if i == j else c1 for j in range(5)]) == 4:
                # found it! find the next one in the next range
                for j in range(i+1, 5):
                    self.oracle.attempt([c2 if i == k or j == k else c1 for k in range(5)])
        # if c2 isn't in the first 3 spots, the last two spots must be c2
        self.oracle.attempt([c1, c1, c1, c2, c2])

    def solve221(self, c1, c2, c3, c4):
        # 2 of c1, 2 of c2, 1 of c3
        # i never claimed this is an elegant solution, im just writing down my thought process in code
        # so this is not cleaned up, eh
        # lets find where the two c1s are, then we need max 3 attempts to get the right soln
        # we have 4 tries to do this, which should be plenty
        # also, we know c4 is gonna fail, which helps the binsearch quite a bit
        r = self.oracle.attempt([c1, c1, c4, c4, c4])
        if r == 2:
            # that was lucky!
            self.try221withknown2(c1, 0, 1, c2, c3)
        elif r == 0:
            # still fine, this means c1 must be in the last 3
            r = self.oracle.attempt([c4, c4, c1, c1, c4])
            if r == 2:
                # easy game
                self.try221withknown2(c1, 2, 3, c2, c3)
            else:
                # r had to be 1, so we know 4 must be c1
                if self.oracle.attempt([c4, c4, c1, c4, c4]) == 1:
                    # c1 is at 2 and 4
                    self.try221withknown2(c1, 2, 4, c2, c3)
                else:
                    # c1 is at 3 and 4
                    self.try221withknown2(c1, 3, 4, c2, c3)
        else:
            # r is 1, this is kinda unfortunate but still doable in the 3 attempts we have left
            r = self.oracle.attempt([c4, c1, c1, c4, c4])
            if r == 2:
                # we're done!
                self.try221withknown2(c1, 1, 2, c2, c3)
            if r == 0:
                # spot 0 had to have a c1, and spots 1 and 2 have no c1
                if self.oracle.attempt([c4, c4, c4, c1, c4]) == 1:
                    # its 0 and 3
                    self.try221withknown2(c1, 0, 3, c2, c3)
                else:
                    # its 0 and 4
                    self.try221withknown2(c1, 0, 4, c2, c3)
            else:
                # this is truly unfortunate since we cant tell if its 0 and 2, or if its 1 and 3/4.
                # we can still find this out in the last 2 attempts tho
                if self.oracle.attempt([c4, c4, c4, c1, c1]) == 0:
                    # its 0 and 2, since 3 and 4 do not have c1s
                    self.try221withknown2(c1, 0, 2, c2, c3)
                else:
                    if self.oracle.attempt([c4, c4, c4, c1, c4]) == 1:
                        # 1 and 3
                        self.try221withknown2(c1, 1, 3, c2, c3)
                    else:
                        # 1 and 4
                        self.try221withknown2(c1, 1, 4, c2, c3)

    def try221withknown2(self, c1, p1, p2, c2, c3):
        # we know p1 and p2 both have c1, and there are 2 c2s and 1 c3 left
        # bruteforce last 3 possibilities
        c3pos = list(range(5))
        c3pos.remove(p1)
        c3pos.remove(p2)
        for p in c3pos:
            self.oracle.attempt([
                c1 if i == p1 or i == p2 else
                c3 if i == p else
                c2 for i in range(5)
            ])

    def solve311(self, c1, c2, c3, c4):
        # we cant just use 4 tries to find c2 and 4 tries to find c3
        # it will fail on occasion
        # therefore, we have to use a fancier method
        # a similar method is also later used in solve2111
        r = self.oracle.attempt([c2, c2, c3, c3, c3])
        if r == 2:
            # this is neat, we can use 1 attempt to find c2, and up to 3 attempts for c3, easy
            c2loc = self.oracle.attempt([c4, c2, c4, c4, c4])
            for c3loc in range(2, 5):
                self.oracle.attempt([
                    c2 if i == c2loc else
                    c3 if i == c3loc else
                    c1 for i in range(5)
                ])
        elif r == 0:
            # this is just r==2 in reverse
            c3loc = self.oracle.attempt([c4, c3, c4, c4, c4])
            for c2loc in range(2, 5):
                self.oracle.attempt([
                    c2 if i == c2loc else
                    c3 if i == c3loc else
                    c1 for i in range(5)
                ])
        elif r == 1:
            # this is a problem
            # however, this means c2 and c3 are in the same partition
            # keep in mind we have 6 attempts left
            # first, are they both in the first partition?
            r = self.oracle.attempt([c2, c2, c4, c4, c4])
            if r == 1:
                # yes! this should be easy, only 2 choices available
                self.oracle.attempt([c2, c3, c1, c1, c1])
                self.oracle.attempt([c3, c2, c1, c1, c1])
            else:
                # time to do some further digging in the 2nd partition
                # fortunately we have 5 attempts left
                # which should be enough for a simple bruteforce
                c2loc = 4
                for c2loca in range(2, 4):
                    if self.oracle.attempt([c2 if i == c2loca else c4 for i in range(5)]) == 1:
                        c2loc = c2loca
                        break
                for c3loc in range(2, 5):
                    if c3loc == c2loc:
                        continue
                    self.oracle.attempt([
                        c2 if i == c2loc else
                        c3 if i == c3loc else
                        c1 for i in range(5)
                    ])

    def solve2111(self, c1, c2, c3, c4):
        # okay, we're in a bit of a pickle here
        # this is gonna be hell
        # lets try to identify the position of the two least common colors
        r = self.oracle.attempt([c3, c3, c4, c4, c4])
        if r == 2:
            # this means we know c3 is in the 1st partition, and c4 is in the 2nd
            # we can use 1 attempt to find c3, 2 attempts to find c4
            # which leaves us 3 attempts to find c2, which is all we need
            if self.oracle.attempt([c3, c4, c4, c4, c4]) == 2:
                c3loc = 0
            else:
                c3loc = 1
            c4loc = 4
            for c4loca in range(2,4):
                if self.oracle.attempt([c4 if i == c4loca else c3 for i in range(5)]) == 2:
                    c4loc = c4loca
                    break
            # we now have 3 attempts to find c2
            for c2loc in range(5):
                if c2loc == c3loc or c2loc == c4loc:
                    continue
                self.oracle.attempt([
                    c2 if i == c2loc else
                    c3 if i == c3loc else
                    c4 if i == c4loc else
                    c1 for i in range(5)])
        elif r == 0:
            # this is the exact opposite of r==2, use same strat
            if self.oracle.attempt([c4, c3, c3, c3, c3]) == 2:
                c4loc = 0
            else:
                c4loc = 1
            c3loc = 4
            for c3loca in range(2,4):
                if self.oracle.attempt([c3 if i == c3loca else c4 for i in range(5)]) == 2:
                    c3loc = c3loca
                    break
            for c2loc in range(5):
                if c2loc == c3loc or c2loc == c4loc:
                    continue
                self.oracle.attempt([
                    c2 if i == c2loc else
                    c3 if i == c3loc else
                    c4 if i == c4loc else
                    c1 for i in range(5)])
        else:
            # r==1, this is kinda bad
            # we do know that c3 and c4 are in the same partition
            # but we only have 6 tries left
            # spend 1 try trying to figure out which partition they're both in
            # we use c3 c3 c1 c1 c1 to figure this out
            # if c3 and c4 are both in the first partition, the c3 would match, and the two c1s must match the three we have
            # therefore, result is 3 lights right
            # if c3 and c4 are both in the second partition, the first two are incorrect, and at most one c1 would be correct
            # therefore, results can be 0 lights right (if c2 c3 c4 are all in the 2nd partition)
            # or 1 light correct (c2 is in the first partition, c3 and c4 in the second)
            r = self.oracle.attempt([c3, c3, c1, c1, c1])
            if r == 3:
                # nice, we have 5 tries left, and we can spend 1 on finding c3 and c4, and 3 on finding c2, and we're done
                r = self.oracle.attempt([c3, c1, c1, c1, c1])
                if r == 3:
                    # c3 is right
                    c3loc = 0
                    c4loc = 1
                elif r == 2:
                    # c3 is wrong, so must be at 1
                    c3loc = 1
                    c4loc = 0
                else:
                    # we should never get here
                    # using elif earlier cuz im not 100% sure my logic is right
                    # so adding this here as a sanity check
                    raise Exception
                for c2loc in range(2,5):
                    self.oracle.attempt([
                        c2 if i == c2loc else
                        c3 if i == c3loc else
                        c4 if i == c4loc else
                        c1 for i in range(5)])
            elif r == 0:
                # c2 c3 c4 are all in the 2nd partition
                # this means we know both c1s must be in the first
                # 5 attempts left, use 2 to find color at spot 2, then 2 for spots 3/4, then we're done
                if self.oracle.attempt([c1, c1, c2, c1, c1]) == 3:
                    coloratspot2 = c2
                    remainingcolor1 = c3
                    remainingcolor2 = c4
                elif self.oracle.attempt([c1, c1, c3, c1, c1]) == 3:
                    coloratspot2 = c3
                    remainingcolor1 = c2
                    remainingcolor2 = c4
                else:
                    coloratspot2 = c4
                    remainingcolor1 = c2
                    remainingcolor2 = c3
                self.oracle.attempt([c1, c1, coloratspot2, remainingcolor1, remainingcolor2])
                self.oracle.attempt([c1, c1, coloratspot2, remainingcolor2, remainingcolor1])
            elif r == 1:
                # c2 in first partition, c3 and c4 in second
                # 5 attempts left, use 1 attempt to locate c2, then use the last 4 to pin the second partition
                r = self.oracle.attempt([c2, c1, c1, c1, c1])
                if r == 3:
                    # c2 is right
                    ca0 = c2
                    ca1 = c1
                else:
                    assert r == 1 # sanity check cuz im questioning mine atm
                    ca0 = c1
                    ca1 = c2
                # cool, we have pinned down the first two spots
                # 4 tries left to find one of c1, c3 and c4 in the second partition
                # 2 tries to pin down what spot 2 is
                # and 2 to vary spots 3 and 4
                # we win! hooray!
                if self.oracle.attempt([ca0, ca1, c1, c2, c2]) == 3:
                    ca2 = c1
                    rc1 = c3
                    rc2 = c4
                elif self.oracle.attempt([ca0, ca1, c3, c2, c2]) == 3:
                    ca2 = c3
                    rc1 = c1
                    rc2 = c4
                else:
                    ca2 = c4
                    rc1 = c1
                    rc2 = c3
                self.oracle.attempt([ca0, ca1, ca2, rc1, rc2])
                self.oracle.attempt([ca0, ca1, ca2, rc2, rc1])

class NaiveMinMaxSolver:
    # first iteration of the minmax solver
    # was kind of a failure, there are 16 cases that needs 12 guesses and 88 cases that needs 11 guesses
    # i tried some rudimentary steps to fix it but they all failed
    # this is kept here for historical curiosity
    totalpossiblepatterns = [int2pattern(i) for i in range(4**5)]
    def __init__(self, oracle):
        self.oracle = oracle
        self.possiblepatterns = self.totalpossiblepatterns[:] # copy array

    @classmethod
    def solve(cls, oracle):
        self = cls(oracle)
        self.step()
        # to save some computing time, the first attempt should be all orange
        initpattern = [Color.ORANGE]*5
        oracleresult = self.oracle.attempt(initpattern)
        # simulate an oracle to see how the oracle would respond if a pattern is the right pattern
        def simoracle(soln, attempt):
            return sum(1 if a==b else 0 for a,b in zip(soln, attempt))
        self.possiblepatterns = [p for p in self.possiblepatterns if simoracle(p, initpattern) == oracleresult]
        self.step()
        raise Exception("Algorithm freaked out on pattern", oracle.soln)

    def step(self):
        # deal with edge case: if only one possible pattern left, try it
        if len(self.possiblepatterns) == 1:
            self.oracle.attempt(self.possiblepatterns[0])
            return
        # simulate an oracle to see how the oracle would respond if a pattern is the right pattern
        def simoracle(soln, attempt):
            return sum(1 if a==b else 0 for a,b in zip(soln, attempt))
        # find the pattern to test that eliminates max number of possible patterns
        bestpattern = -1
        bestpatternminelimcount = -1
        for p in range(4**5):
            attemptpattern = int2pattern(p)
            counter = [0]*6
            for a in self.possiblepatterns:
                counter[simoracle(a, attemptpattern)] += 1
            # we need to deal with the edge case that if we dont have many patterns left, we're gonna get stuck
            # if we simply use min(counter) as patternminelimcount, we will get 0 most of the time
            # in this case, it's necessary to remove the 0s that won't tell us any info
            # this is a horrifying hack
            counter = [i for i in counter if i != 0]
            if len(counter) == 1:
                # using this would give us no info
                continue
            patternminelimcount = min(counter)
            if (patternminelimcount > bestpatternminelimcount and patternminelimcount != len(self.possiblepatterns)) or (patternminelimcount == bestpatternminelimcount and attemptpattern in self.possiblepatterns):
                # the or is necessary because in e.g. a situation with 2 possibilities left, we'd rather try an option that's one of the two possibilities
                # as opposed to some third pattern that can pin down which possibiligy is left
                # this also helps find solutions a bit quicker, as without that "or" we sometimes (very rarely) exceed 10 tries
                bestpatternminelimcount = patternminelimcount
                bestpattern = p
        # now that we have the best pattern, let's actually try it and eliminate the rest
        bestpattern = int2pattern(bestpattern)
        oracleresult = self.oracle.attempt(bestpattern)
        self.possiblepatterns = [p for p in self.possiblepatterns if simoracle(p, bestpattern) == oracleresult]
        print(self.possiblepatterns)
        # try again
        self.step()

class MaxEntropySolver:
    # second attempt at a non-handcrafted algorithm that tries to minimize the number of possible solutions
    # instead of optimizing for worst case performance (maximizing the number of eliminated patterns in the worst case)
    # this algorithm calculates the average amount of entropy we can gather from each guess and maximizes that
    # this solver can solve all possible puzzles in 8 attempts and takes 5.8173828125 tries on average
    # guess count distribution is: [0, 1, 3, 10, 55, 243, 505, 201, 6, 0, 0]
    # if you can beat this, please let me know! would be interested what kind of optimizations you can make
    # maybe some sort of lookahead to maximize the average entropy from 2 guesses into the future?
    totalPossiblePatterns = [int2pattern(i) for i in range(4**5)]
    def __init__(self, oracle):
        self.oracle = oracle
        self.possiblePatterns = self.totalPossiblePatterns[:] # copy array

    @classmethod
    def solve(cls, oracle):
        self = cls(oracle)
        # to save some computing time, first guess is always all oranges (tbh all first guesses are exactly equal)
        firstGuessResult = self.executeGuess([Color.ORANGE]*5)
        # and the second guess has been precomputed as well
        secondGuesses = [
            [Color.RED, Color.RED, Color.RED, Color.RED, Color.RED], # 0 correct
            [Color.ORANGE, Color.RED, Color.RED, Color.RED, Color.RED], # 1 correct
            [Color.ORANGE, Color.ORANGE, Color.RED, Color.RED, Color.RED], # 2 correct
            [Color.BLUE, Color.BLUE, Color.BLUE, Color.ORANGE, Color.ORANGE], # 3 correct
            [Color.BLUE, Color.BLUE, Color.BLUE, Color.ORANGE, Color.ORANGE], # 4 correct
        ]
        self.executeGuess(secondGuesses[firstGuessResult])
        while True:
            guess = self.findBestGuess()
            self.executeGuess(guess)

    @staticmethod
    def simOracle(solution, pattern):
        # simulates an oracle result
        return sum(1 if a == b else 0 for a,b in zip(solution, pattern))

    def executeGuess(self, pattern):
        # actually asks the oracle for a pattern, then reduce total possible patterns to what's possible
        result = self.oracle.attempt(pattern)
        newPossiblePatterns = [p for p in self.possiblePatterns if self.simOracle(p, pattern) == result]
        self.possiblePatterns = newPossiblePatterns
        return result

    def findBestGuess(self):
        totalPatterns = len(self.possiblePatterns)
        if totalPatterns <= 2:
            return self.possiblePatterns[0] # short circuit, if we have only one or two possible solutions, might as well guess
        # otherwise, for all 4**5 possible guesses, which one gives us the most amount of information?
        maxEntropy = 0
        for p in range(4**5):
            attemptPattern = int2pattern(p)
            counter = [0]*6
            for soln in self.possiblePatterns:
                counter[self.simOracle(soln, attemptPattern)] += 1
            entropy = -sum(c/totalPatterns * math.log(c/totalPatterns) for c in counter if c != 0)
            #print(attemptPattern, counter, entropy)
            if entropy > maxEntropy:
                maxEntropy = entropy
                bestguess = attemptPattern
            elif entropy == maxEntropy and attemptPattern in self.possiblePatterns:
                # given the same amount of entropy, always prioritize a solution that's possible
                # just for that small chance of actually hitting it
                bestguess = attemptPattern
        return bestguess

def verify():
    guessFreq = [0] * 11
    for pattern in range(4**5):
        soln = int2pattern(pattern)
        print('Now testing:', soln, "%d/%d"%(pattern, 4**5))
        oracle = Oracle(soln)
        try:
            #HumanLogicSolver.solve(oracle)
            MaxEntropySolver.solve(oracle)
        except SolveSuccess:
            guessFreq[oracle.attempts] += 1
        else:
            raise Exception("Solver returned without finding correct solution, this should never happen")
    print("Algorithm verification success")
    print("Average number of tries is", sum(c*f for c,f in enumerate(guessFreq)) / (4**5))
    print("Guess count distribution is", guessFreq)

if __name__ == "__main__":
    #HumanLogicSolver.solve(Oracle([Color.BLUE, Color.GREEN, Color.BLUE, Color.RED, Color.ORANGE]))
    #MaxEntropySolver.solve(Oracle([Color.GREEN, Color.GREEN, Color.GREEN, Color.GREEN, Color.ORANGE]))
    #MaxEntropySolver.solve(Oracle([Color.GREEN, Color.GREEN, Color.GREEN, Color.GREEN, Color.GREEN]))
    verify()
	from enum import IntEnum
	import math

	class Color(IntEnum):
	ORANGE = 0
	BLUE = 1
	GREEN = 2
	RED = 3
	def __repr__(self):
	return self.name

	class SolveSuccess(RuntimeError):
	pass

	class Oracle:
	def __init__(self, soln):
	self.soln = soln
	self.attempts = 0

	def attempt(self, attempt):
	result = sum(1 if a==b else 0 for a,b in zip(self.soln, attempt))
	self.attempts += 1
	print('ORACLE ATTEMPT', self.attempts, attempt, result, 'CORRECT')
	if result == 5:
	raise SolveSuccess
	if self.attempts == 10:
	raise Exception("Solve attempts exceeded on pattern", self.soln)
	return result

	def int2pattern(i):
	p = []
	for _ in range(5):
	p.append(Color(i%4))
	i //= 4
	return p

	def str2pattern(s):
	mapping = {
	'O': Color.ORANGE,
	'B': Color.BLUE,
	'G': Color.GREEN,
	'R': Color.RED,
	}
	return [mapping[c] for c in s]

	class HumanLogicSolver:
	# this solver can solve all possible puzzles in 10 attempts
	# it takes 7.62109375 tries on average
	# guess count distribution is: [0, 1, 1, 3, 15, 38, 136, 254, 308, 196, 72]
	# an explanation is in the attached markdown document
	def __init__(self, oracle):
	self.oracle = oracle

	@classmethod
	def solve(cls, oracle):
	cls(oracle).startsolve()
	# we should never get here
	raise Exception("Algorithm freaked out on pattern", oracle.soln)

	def startsolve(self):
	# first step, determine how many of each color there are, then dispatch it to a subsolver
	ocount = self.oracle.attempt([Color.ORANGE]*5)
	bcount = self.oracle.attempt([Color.BLUE]*5)
	if ocount + bcount == 5:
	# we know there are no green or red ones left
	gcount = 0
	rcount = 0
	else:
	# try all greens
	gcount = self.oracle.attempt([Color.GREEN]*5)
	# red would just be the rest
	rcount = 5 - ocount - bcount - gcount

	counts = [(ocount, Color.ORANGE), (bcount, Color.BLUE), (gcount, Color.GREEN), (rcount, Color.RED)]
	counts.sort(reverse=True)
	# 1st case, only one color, then rcount is 5 (ocount bcount and gcount cant be 5 since their attempt would succeed already
	if counts[1][0] == 0:
	# we're done!
	self.oracle.attempt([Color.RED]*5)
	return
	# 2nd/3rd case, only 2 colors, which could have counts 4-1 or 3-2
	elif counts[2][0] == 0:
	if counts[0][0] == 4:
	solver = self.solve41
	else:
	solver = self.solve32
	# 4th/5th case, 3 colors, which could be 2-2-1 or 3-1-1
	elif counts[3][0] == 0:
	if counts[0][0] == 2:
	solver = self.solve221
	else:
	solver = self.solve311
	# 6th case, all 4 colors, which has to be 2-1-1-1
	else:
	solver = self.solve2111
	# give it the colors and start solving!
	solver(*[i[1] for i in counts])

	def solve41(self, c1, c2, c3, c4):
	# 4 c1s, 1 c2
	# should be really easy, just vary where c2 is
	for i in range(5):
	self.oracle.attempt([c2 if i == j else c1 for j in range(5)])

	def solve32(self, c1, c2, c3, c4):
	# 3 c1s, 2 c2
	# find the first c2 in the first 3 spots
	for i in range(3):
	if self.oracle.attempt([c2 if i == j else c1 for j in range(5)]) == 4:
	# found it! find the next one in the next range
	for j in range(i+1, 5):
	self.oracle.attempt([c2 if i == k or j == k else c1 for k in range(5)])
	# if c2 isn't in the first 3 spots, the last two spots must be c2
	self.oracle.attempt([c1, c1, c1, c2, c2])

	def solve221(self, c1, c2, c3, c4):
	# 2 of c1, 2 of c2, 1 of c3
	# i never claimed this is an elegant solution, im just writing down my thought process in code
	# so this is not cleaned up, eh
	# lets find where the two c1s are, then we need max 3 attempts to get the right soln
	# we have 4 tries to do this, which should be plenty
	# also, we know c4 is gonna fail, which helps the binsearch quite a bit
	r = self.oracle.attempt([c1, c1, c4, c4, c4])
	if r == 2:
	# that was lucky!
	self.try221withknown2(c1, 0, 1, c2, c3)
	elif r == 0:
	# still fine, this means c1 must be in the last 3
	r = self.oracle.attempt([c4, c4, c1, c1, c4])
	if r == 2:
	# easy game
	self.try221withknown2(c1, 2, 3, c2, c3)
	else:
	# r had to be 1, so we know 4 must be c1
	if self.oracle.attempt([c4, c4, c1, c4, c4]) == 1:
	# c1 is at 2 and 4
	self.try221withknown2(c1, 2, 4, c2, c3)
	else:
	# c1 is at 3 and 4
	self.try221withknown2(c1, 3, 4, c2, c3)
	else:
	# r is 1, this is kinda unfortunate but still doable in the 3 attempts we have left
	r = self.oracle.attempt([c4, c1, c1, c4, c4])
	if r == 2:
	# we're done!
	self.try221withknown2(c1, 1, 2, c2, c3)
	if r == 0:
	# spot 0 had to have a c1, and spots 1 and 2 have no c1
	if self.oracle.attempt([c4, c4, c4, c1, c4]) == 1:
	# its 0 and 3
	self.try221withknown2(c1, 0, 3, c2, c3)
	else:
	# its 0 and 4
	self.try221withknown2(c1, 0, 4, c2, c3)
	else:
	# this is truly unfortunate since we cant tell if its 0 and 2, or if its 1 and 3/4.
	# we can still find this out in the last 2 attempts tho
	if self.oracle.attempt([c4, c4, c4, c1, c1]) == 0:
	# its 0 and 2, since 3 and 4 do not have c1s
	self.try221withknown2(c1, 0, 2, c2, c3)
	else:
	if self.oracle.attempt([c4, c4, c4, c1, c4]) == 1:
	# 1 and 3
	self.try221withknown2(c1, 1, 3, c2, c3)
	else:
	# 1 and 4
	self.try221withknown2(c1, 1, 4, c2, c3)

	def try221withknown2(self, c1, p1, p2, c2, c3):
	# we know p1 and p2 both have c1, and there are 2 c2s and 1 c3 left
	# bruteforce last 3 possibilities
	c3pos = list(range(5))
	c3pos.remove(p1)
	c3pos.remove(p2)
	for p in c3pos:
	self.oracle.attempt([
	c1 if i == p1 or i == p2 else
	c3 if i == p else
	c2 for i in range(5)
	])

	def solve311(self, c1, c2, c3, c4):
	# we cant just use 4 tries to find c2 and 4 tries to find c3
	# it will fail on occasion
	# therefore, we have to use a fancier method
	# a similar method is also later used in solve2111
	r = self.oracle.attempt([c2, c2, c3, c3, c3])
	if r == 2:
	# this is neat, we can use 1 attempt to find c2, and up to 3 attempts for c3, easy
	c2loc = self.oracle.attempt([c4, c2, c4, c4, c4])
	for c3loc in range(2, 5):
	self.oracle.attempt([
	c2 if i == c2loc else
	c3 if i == c3loc else
	c1 for i in range(5)
	])
	elif r == 0:
	# this is just r==2 in reverse
	c3loc = self.oracle.attempt([c4, c3, c4, c4, c4])
	for c2loc in range(2, 5):
	self.oracle.attempt([
	c2 if i == c2loc else
	c3 if i == c3loc else
	c1 for i in range(5)
	])
	elif r == 1:
	# this is a problem
	# however, this means c2 and c3 are in the same partition
	# keep in mind we have 6 attempts left
	# first, are they both in the first partition?
	r = self.oracle.attempt([c2, c2, c4, c4, c4])
	if r == 1:
	# yes! this should be easy, only 2 choices available
	self.oracle.attempt([c2, c3, c1, c1, c1])
	self.oracle.attempt([c3, c2, c1, c1, c1])
	else:
	# time to do some further digging in the 2nd partition
	# fortunately we have 5 attempts left
	# which should be enough for a simple bruteforce
	c2loc = 4
	for c2loca in range(2, 4):
	if self.oracle.attempt([c2 if i == c2loca else c4 for i in range(5)]) == 1:
	c2loc = c2loca
	break
	for c3loc in range(2, 5):
	if c3loc == c2loc:
	continue
	self.oracle.attempt([
	c2 if i == c2loc else
	c3 if i == c3loc else
	c1 for i in range(5)
	])

	def solve2111(self, c1, c2, c3, c4):
	# okay, we're in a bit of a pickle here
	# this is gonna be hell
	# lets try to identify the position of the two least common colors
	r = self.oracle.attempt([c3, c3, c4, c4, c4])
	if r == 2:
	# this means we know c3 is in the 1st partition, and c4 is in the 2nd
	# we can use 1 attempt to find c3, 2 attempts to find c4
	# which leaves us 3 attempts to find c2, which is all we need
	if self.oracle.attempt([c3, c4, c4, c4, c4]) == 2:
	c3loc = 0
	else:
	c3loc = 1
	c4loc = 4
	for c4loca in range(2,4):
	if self.oracle.attempt([c4 if i == c4loca else c3 for i in range(5)]) == 2:
	c4loc = c4loca
	break
	# we now have 3 attempts to find c2
	for c2loc in range(5):
	if c2loc == c3loc or c2loc == c4loc:
	continue
	self.oracle.attempt([
	c2 if i == c2loc else
	c3 if i == c3loc else
	c4 if i == c4loc else
	c1 for i in range(5)])
	elif r == 0:
	# this is the exact opposite of r==2, use same strat
	if self.oracle.attempt([c4, c3, c3, c3, c3]) == 2:
	c4loc = 0
	else:
	c4loc = 1
	c3loc = 4
	for c3loca in range(2,4):
	if self.oracle.attempt([c3 if i == c3loca else c4 for i in range(5)]) == 2:
	c3loc = c3loca
	break
	for c2loc in range(5):
	if c2loc == c3loc or c2loc == c4loc:
	continue
	self.oracle.attempt([
	c2 if i == c2loc else
	c3 if i == c3loc else
	c4 if i == c4loc else
	c1 for i in range(5)])
	else:
	# r==1, this is kinda bad
	# we do know that c3 and c4 are in the same partition
	# but we only have 6 tries left
	# spend 1 try trying to figure out which partition they're both in
	# we use c3 c3 c1 c1 c1 to figure this out
	# if c3 and c4 are both in the first partition, the c3 would match, and the two c1s must match the three we have
	# therefore, result is 3 lights right
	# if c3 and c4 are both in the second partition, the first two are incorrect, and at most one c1 would be correct
	# therefore, results can be 0 lights right (if c2 c3 c4 are all in the 2nd partition)
	# or 1 light correct (c2 is in the first partition, c3 and c4 in the second)
	r = self.oracle.attempt([c3, c3, c1, c1, c1])
	if r == 3:
	# nice, we have 5 tries left, and we can spend 1 on finding c3 and c4, and 3 on finding c2, and we're done
	r = self.oracle.attempt([c3, c1, c1, c1, c1])
	if r == 3:
	# c3 is right
	c3loc = 0
	c4loc = 1
	elif r == 2:
	# c3 is wrong, so must be at 1
	c3loc = 1
	c4loc = 0
	else:
	# we should never get here
	# using elif earlier cuz im not 100% sure my logic is right
	# so adding this here as a sanity check
	raise Exception
	for c2loc in range(2,5):
	self.oracle.attempt([
	c2 if i == c2loc else
	c3 if i == c3loc else
	c4 if i == c4loc else
	c1 for i in range(5)])
	elif r == 0:
	# c2 c3 c4 are all in the 2nd partition
	# this means we know both c1s must be in the first
	# 5 attempts left, use 2 to find color at spot 2, then 2 for spots 3/4, then we're done
	if self.oracle.attempt([c1, c1, c2, c1, c1]) == 3:
	coloratspot2 = c2
	remainingcolor1 = c3
	remainingcolor2 = c4
	elif self.oracle.attempt([c1, c1, c3, c1, c1]) == 3:
	coloratspot2 = c3
	remainingcolor1 = c2
	remainingcolor2 = c4
	else:
	coloratspot2 = c4
	remainingcolor1 = c2
	remainingcolor2 = c3
	self.oracle.attempt([c1, c1, coloratspot2, remainingcolor1, remainingcolor2])
	self.oracle.attempt([c1, c1, coloratspot2, remainingcolor2, remainingcolor1])
	elif r == 1:
	# c2 in first partition, c3 and c4 in second
	# 5 attempts left, use 1 attempt to locate c2, then use the last 4 to pin the second partition
	r = self.oracle.attempt([c2, c1, c1, c1, c1])
	if r == 3:
	# c2 is right
	ca0 = c2
	ca1 = c1
	else:
	assert r == 1 # sanity check cuz im questioning mine atm
	ca0 = c1
	ca1 = c2
	# cool, we have pinned down the first two spots
	# 4 tries left to find one of c1, c3 and c4 in the second partition
	# 2 tries to pin down what spot 2 is
	# and 2 to vary spots 3 and 4
	# we win! hooray!
	if self.oracle.attempt([ca0, ca1, c1, c2, c2]) == 3:
	ca2 = c1
	rc1 = c3
	rc2 = c4
	elif self.oracle.attempt([ca0, ca1, c3, c2, c2]) == 3:
	ca2 = c3
	rc1 = c1
	rc2 = c4
	else:
	ca2 = c4
	rc1 = c1
	rc2 = c3
	self.oracle.attempt([ca0, ca1, ca2, rc1, rc2])
	self.oracle.attempt([ca0, ca1, ca2, rc2, rc1])

	class NaiveMinMaxSolver:
	# first iteration of the minmax solver
	# was kind of a failure, there are 16 cases that needs 12 guesses and 88 cases that needs 11 guesses
	# i tried some rudimentary steps to fix it but they all failed
	# this is kept here for historical curiosity
	totalpossiblepatterns = [int2pattern(i) for i in range(4**5)]
	def __init__(self, oracle):
	self.oracle = oracle
	self.possiblepatterns = self.totalpossiblepatterns[:] # copy array

	@classmethod
	def solve(cls, oracle):
	self = cls(oracle)
	self.step()
	# to save some computing time, the first attempt should be all orange
	initpattern = [Color.ORANGE]*5
	oracleresult = self.oracle.attempt(initpattern)
	# simulate an oracle to see how the oracle would respond if a pattern is the right pattern
	def simoracle(soln, attempt):
	return sum(1 if a==b else 0 for a,b in zip(soln, attempt))
	self.possiblepatterns = [p for p in self.possiblepatterns if simoracle(p, initpattern) == oracleresult]
	self.step()
	raise Exception("Algorithm freaked out on pattern", oracle.soln)

	def step(self):
	# deal with edge case: if only one possible pattern left, try it
	if len(self.possiblepatterns) == 1:
	self.oracle.attempt(self.possiblepatterns[0])
	return
	# simulate an oracle to see how the oracle would respond if a pattern is the right pattern
	def simoracle(soln, attempt):
	return sum(1 if a==b else 0 for a,b in zip(soln, attempt))
	# find the pattern to test that eliminates max number of possible patterns
	bestpattern = -1
	bestpatternminelimcount = -1
	for p in range(4**5):
	attemptpattern = int2pattern(p)
	counter = [0]*6
	for a in self.possiblepatterns:
	counter[simoracle(a, attemptpattern)] += 1
	# we need to deal with the edge case that if we dont have many patterns left, we're gonna get stuck
	# if we simply use min(counter) as patternminelimcount, we will get 0 most of the time
	# in this case, it's necessary to remove the 0s that won't tell us any info
	# this is a horrifying hack
	counter = [i for i in counter if i != 0]
	if len(counter) == 1:
	# using this would give us no info
	continue
	patternminelimcount = min(counter)
	if (patternminelimcount > bestpatternminelimcount and patternminelimcount != len(self.possiblepatterns)) or (patternminelimcount == bestpatternminelimcount and attemptpattern in self.possiblepatterns):
	# the or is necessary because in e.g. a situation with 2 possibilities left, we'd rather try an option that's one of the two possibilities
	# as opposed to some third pattern that can pin down which possibiligy is left
	# this also helps find solutions a bit quicker, as without that "or" we sometimes (very rarely) exceed 10 tries
	bestpatternminelimcount = patternminelimcount
	bestpattern = p
	# now that we have the best pattern, let's actually try it and eliminate the rest
	bestpattern = int2pattern(bestpattern)
	oracleresult = self.oracle.attempt(bestpattern)
	self.possiblepatterns = [p for p in self.possiblepatterns if simoracle(p, bestpattern) == oracleresult]
	print(self.possiblepatterns)
	# try again
	self.step()

	class MaxEntropySolver:
	# second attempt at a non-handcrafted algorithm that tries to minimize the number of possible solutions
	# instead of optimizing for worst case performance (maximizing the number of eliminated patterns in the worst case)
	# this algorithm calculates the average amount of entropy we can gather from each guess and maximizes that
	# this solver can solve all possible puzzles in 8 attempts and takes 5.8173828125 tries on average
	# guess count distribution is: [0, 1, 3, 10, 55, 243, 505, 201, 6, 0, 0]
	# if you can beat this, please let me know! would be interested what kind of optimizations you can make
	# maybe some sort of lookahead to maximize the average entropy from 2 guesses into the future?
	totalPossiblePatterns = [int2pattern(i) for i in range(4**5)]
	def __init__(self, oracle):
	self.oracle = oracle
	self.possiblePatterns = self.totalPossiblePatterns[:] # copy array

	@classmethod
	def solve(cls, oracle):
	self = cls(oracle)
	# to save some computing time, first guess is always all oranges (tbh all first guesses are exactly equal)
	firstGuessResult = self.executeGuess([Color.ORANGE]*5)
	# and the second guess has been precomputed as well
	secondGuesses = [
	[Color.RED, Color.RED, Color.RED, Color.RED, Color.RED], # 0 correct
	[Color.ORANGE, Color.RED, Color.RED, Color.RED, Color.RED], # 1 correct
	[Color.ORANGE, Color.ORANGE, Color.RED, Color.RED, Color.RED], # 2 correct
	[Color.BLUE, Color.BLUE, Color.BLUE, Color.ORANGE, Color.ORANGE], # 3 correct
	[Color.BLUE, Color.BLUE, Color.BLUE, Color.ORANGE, Color.ORANGE], # 4 correct
	]
	self.executeGuess(secondGuesses[firstGuessResult])
	while True:
	guess = self.findBestGuess()
	self.executeGuess(guess)

	@staticmethod
	def simOracle(solution, pattern):
	# simulates an oracle result
	return sum(1 if a == b else 0 for a,b in zip(solution, pattern))

	def executeGuess(self, pattern):
	# actually asks the oracle for a pattern, then reduce total possible patterns to what's possible
	result = self.oracle.attempt(pattern)
	newPossiblePatterns = [p for p in self.possiblePatterns if self.simOracle(p, pattern) == result]
	self.possiblePatterns = newPossiblePatterns
	return result

	def findBestGuess(self):
	totalPatterns = len(self.possiblePatterns)
	if totalPatterns <= 2:
	return self.possiblePatterns[0] # short circuit, if we have only one or two possible solutions, might as well guess
	# otherwise, for all 4**5 possible guesses, which one gives us the most amount of information?
	maxEntropy = 0
	for p in range(4**5):
	attemptPattern = int2pattern(p)
	counter = [0]*6
	for soln in self.possiblePatterns:
	counter[self.simOracle(soln, attemptPattern)] += 1
	entropy = -sum(c/totalPatterns * math.log(c/totalPatterns) for c in counter if c != 0)
	#print(attemptPattern, counter, entropy)
	if entropy > maxEntropy:
	maxEntropy = entropy
	bestguess = attemptPattern
	elif entropy == maxEntropy and attemptPattern in self.possiblePatterns:
	# given the same amount of entropy, always prioritize a solution that's possible
	# just for that small chance of actually hitting it
	bestguess = attemptPattern
	return bestguess

	def verify():
	guessFreq = [0] * 11
	for pattern in range(4**5):
	soln = int2pattern(pattern)
	print('Now testing:', soln, "%d/%d"%(pattern, 4**5))
	oracle = Oracle(soln)
	try:
	#HumanLogicSolver.solve(oracle)
	MaxEntropySolver.solve(oracle)
	except SolveSuccess:
	guessFreq[oracle.attempts] += 1
	else:
	raise Exception("Solver returned without finding correct solution, this should never happen")
	print("Algorithm verification success")
	print("Average number of tries is", sum(cf for c,f in enumerate(guessFreq)) / (4*5))
	print("Guess count distribution is", guessFreq)

	if __name__ == "__main__":
	#HumanLogicSolver.solve(Oracle([Color.BLUE, Color.GREEN, Color.BLUE, Color.RED, Color.ORANGE]))
	#MaxEntropySolver.solve(Oracle([Color.GREEN, Color.GREEN, Color.GREEN, Color.GREEN, Color.ORANGE]))
	#MaxEntropySolver.solve(Oracle([Color.GREEN, Color.GREEN, Color.GREEN, Color.GREEN, Color.GREEN]))
	verify()