Mathematics – Page 3 – The Renegade Coder

Recently, the students in my Java course were completing an assignment similar to Rock Paper Scissors when one of them came up with a clever question: can we compare each choice numerically? After thinking a moment, I realized we could totally implement Rock Paper Scissors using modular arithmetic. Rock Paper Scissors Rules Before we get into the solution, I find it's always useful to lay out the requirements. In particular, what is Rock Paper Scissors, and how can we model it in a computer game? Just so we're clear, Rock Paper Scissors is a one-on-one strategy game where individuals simultaneously select rock, paper, or scissors. The winner is decided based on the relationship between the different choices: paper beats rock, rock beats scissors, and scissors beats paper. To model this type of game in a program, we'll have to set some basic rules. Instead of rock, paper, and scissors, we'll use the numbers 1, 2, and 3. This allows us to avoid user input issues. For example, who wants to deal with all the variations of strings (i.e. rock, ROCK, RoCk, etc.)? In addition, we'll set up the program so users can play the computer. To do this, we'll have the program generate a random number between 1 and 3 while requesting a number between 1 and 3 from the user. If a user enters an invalid number, they'll lose automatically. With these rules in place, we should be able to implement a relatively trivial solution to Rock Paper Scissors. Rock Paper Scissors Challenges Of course, in my experience, implementing Rock Paper Scissors is actually not that easy. In fact, I've seen a lot of students struggle to write the program for a number of reasons. In some cases, students have just learned control flow, so they struggle to set up their conditions. Other times, they have a hard time simplifying their solution, so there are cases all over the place—hence why I try to avoid processing user input if possible. In the latter case, I find that many students want to cover all of the possible cases explicitly: Paper vs. PaperPaper vs. RockPaper vs. ScissorsRock vs. RockRock vs. PaperRock vs. ScissorsScissors vs. ScissorsScissors vs. PaperScissors vs. RockBad Input Very quickly, students will realize that writing out 10 if statements is painful. By the fifth one, they'll start to wonder if they're doing something wrong. At that point, they'll usually revise their strategy, reduce their test cases, and possibly ignite their passion for computer science. After all, I always find reducing complexity to be a really fun and rewarding task. Of course, not everyone is like me. At any rate, many students will notice that there are some redundant cases in the solution above. In particular, they may find that they can reduce all three tying cases down to a single case (i.e. `choice == choice`java). Unfortunately, that only reduces ten cases down to eight. So, is there a better way? Well, according to one of my students there is, but we're not there yet! Instead, I want to take some time to dig into the code. Rock Paper Scissors Solutions When I first solved this problem, I was writing a JUnit test case, so I could automate student grading. As you can see, I went the eight case route from above, but I used Enums for code clarity purposes. Why refer to rock as 1 when I could call it what it is, `Game.ROCK`java? After thinking about this problem a bit more, I'm sure there are an infinite number of cleaner solutions. For instance, if I were to go back and rework my code, I'd probably populate some lookup table. That way, I could use the user choice and the computer choice as indices in a matrix. Instead of writing eight if statements, I'd just need to retrieve the result from the table. That said, I want to take some time to walk through some typical solutions. For my own sanity, all solutions will be in Python rather than Java, but the idea will be the same. The General Boilerplate All of the following solutions will share some of the same code. To avoid copying boilerplate, we'll cover all of that now: import random import sys # Create number to choice mapping mapping = { 1: "Rock", 2: "Paper", 3: "Scissors" } # Generate computer choice pc_choice = random.randint(1, 3) pc_choice_output = "I chose %s." % mapping[pc_choice] # Request user choice try: user_choice = int(input("Choose Rock (1), Paper (2), or Scissors (3): ")) user_choice_output = "You chose %s." % mapping[user_choice] except (ValueError, KeyError): print(pc_choice_output) print("You chose nothing.") print("You lose by default.") sys.exit(0) # Share choices print(pc_choice_output) print(user_choice_output) # Setup results i_win = "%s beats %s - I win!" % (mapping[pc_choice], mapping[user_choice]) u_win = "%s beats %s - you win!" % (mapping[user_choice], mapping[pc_choice]) tie = "Tie!" In this code snippet, we start by importing the `random`python library which we use to generate the computer player's random choice (more on that later). In addition to the random library, we also import the `sys`python library which we'll use to exit on bad input: import random import sys After that, we create a number to string mapping which maps our numeric choices to the strings they represent—rock, paper, and scissors: mapping = { 1: "Rock", 2: "Paper", 3: "Scissors" } Then, we generate the computer's choice using the random library we referenced before. While we're there, we create a string which will indicate what choice the computer made to the user : pc_choice = random.randint(1, 3) pc_choice_output = "I chose %s." % mapping[pc_choice] Following that, we come to a try/except block which we use to do some rough data validation. In particular, we want to make sure that the user enters a valid number. If the user enters a number outside our expected range or they don't enter a number at all, we'd like to be able to detect that. If we do, we print a nice dialog resulting in a user loss that terminates the program: try: user_choice = int(input("Choose Rock (1), Paper (2), or Scissors (3): ")) user_choice_output = "You chose %s." % mapping[user_choice] except (ValueError, KeyError): print(pc_choice_output) print("You chose nothing.") print("You lose by default.") sys.exit(0) Once both players have valid choices, we're able to print them to the user: print(pc_choice_output) print(user_choice_output) Finally, we setup some results strings which we'll populate later. Keep in mind that this code was written before I knew about f-strings. If you're interested, here's an article where I discuss the various ways to format strings. Otherwise, let's keep going! i_win = "%s beats %s - I win!" % (mapping[pc_choice], mapping[user_choice]) u_win = "%s beats %s - you win!" % (mapping[user_choice], mapping[pc_choice]) tie = "Tie!" If we run the solution up to this point, we might see something like the following: Choose Rock (1), Paper (2), or Scissors (3): 2 I chose Rock. You chose Paper. Meanwhile, an unsuccessful execution might look something like the following: Choose Rock (1), Paper (2), or Scissors (3): 5 I chose Paper. You chose nothing. You lose by default. At this point, we're able to dig into the win/loss logic. The 10-Case Behemoth If we wanted to model all ten cases in Python, we could do so using the following nine if statements (bad input was already taken care of): # Share winner if pc_choice == 1 and user_choice == 1: # Rock vs. Rock print(tie) elif pc_choice == 2 and user_choice == 2: # Paper vs. Paper print(tie) elif pc_choice == 3 and user_choice == 3: # Scissors vs. Scissors print(tie) elif pc_choice == 1 and user_choice == 2: # Rock vs. Paper print(u_win) elif pc_choice == 1 and user_choice == 3: # Rock vs. Scissors print(i_win) elif pc_choice == 2 and user_choice == 1: # Paper vs. Rock print(i_win) elif pc_choice == 2 and user_choice == 3: # Paper vs. Scissors print(u_win) elif pc_choice == 3 and user_choice == 1: # Scissors vs. Rock print(u_win) else: # Scissors vs. Paper print(i_win) Of course, a solution like this leaves a lot to be desired. For instance, there's an enormous amount of duplicate code. The following lines appear three times each in the solution: print(u_win) print(i_win) print(tie) In addition, it's kind of tough to remember the mapping when we're doing our comparisons. As a result, I put in extra comments for clarity. That said, it would much nicer for the code to speak for itself. At any rate, this is a perfectly valid solution, but I think we can do better. The 8-Case Stalwart As previously mentioned, we can reduce the ten cases above down to eight by consolidating all the tie scenarios: # Share winner if pc_choice == user_choice: # Same choice print(tie) elif pc_choice == 1 and user_choice == 2: # Rock vs. Paper print(u_win) elif pc_choice == 1 and user_choice == 3: # Rock vs. Scissors print(i_win) elif pc_choice == 2 and user_choice == 1: # Paper vs. Rock print(i_win) elif pc_choice == 2 and user_choice == 3: # Paper vs. Scissors print(u_win) elif pc_choice == 3 and user_choice == 1: # Scissors vs. Rock print(u_win) else: # Scissors vs. Paper print(i_win) In the tie case, we know that the user and the computer made the same choice, so we can compare their values directly. As a result, we can quickly trim two cases off the top. Unfortunately, we still have quite a bit of duplicate code, but slimming these cases down is much harder. While we might want to consolidate all the cases where the computer wins, it's not really clear how we'd do that. Likewise, we may notice that some of these cases are just inverses of each other (i.e. rock vs. paper and paper vs. rock). Maybe there is some way to consolidate those cases, but it isn't clear. The Nesting Doll One way we might try to reduce our duplicate code is by introducing some nested if statements: # Share winner if pc_choice == user_choice: print(tie) elif pc_choice == 1: # Rock if user_choice == 2: # Paper print(u_win) else: # Scissors print(i_win) elif pc_choice == 2: # Paper if user_choice == 1: # Rock print(i_win) else: # Scissors print(u_win) else: # Scissors if user_choice == 1: # Rock print(u_win) else: # Paper print(i_win) Unfortunately, this solution doesn't really reduce our code at all. In some ways, it's actually more confusing. Is there anything we can do to cut down on the code a bit? I'm glad you asked! The Modular Arithmetic Minimalist When I first came up with this solution, it was as a result of a student question about comparing the two choices directly using the relational operators (>, ScissorsRock RockPaper PaperScissors < Rock For some reason, these relationships seem really intuitive. After all, scissors are stronger than paper but weaker than rock. So, it makes sense to think about them as mathematical quantities. The problem is that numbers don't display this cyclical property that rock, paper, and scissors do. Sure, three is greater than two, but one is not greater than three. So, what do we do? As it turns out, there's a mathematical operator that may just save the day called modulo. For our purposes, the modulo operator will allow us to establish this cyclical relationship between the three choices. Take a look: # Share results if pc_choice == user_choice: print(tie) elif (user_choice + 1) % 3 == pc_choice % 3: print(i_win) else: print(u_win) How's that for a drastic reduction in cases? Here, we went from a worst-case scenario of ten cases to just four (including the bad input case), but how does it work? As it turns out, we have to be very careful about the mapping of our choices. In our case, winning occurs in one direction in the cycle while losing occurs in the other direction. In other words, three beats two, two beats one, and one beats three: To capture this cyclical relationship, we use the following condition: (user_choice + 1) % 3 == pc_choice % 3 The left half of this expression is computing the next choice in the cycle. If the user selects rock, the expression would evaluate to two because `(1 + 1) % 3`python is two. If the next choice in the cycle happens to also be the computer's choice, we know the user has lost. Likewise, if the next choice in the cycle is not the computer's choice, we know that we must have won (assuming we've already tested for the tie). With this solution, we no longer have to deal with all that duplicate code. We have one case for bad input, one case for ties, one case for wins, and one case for losses. The Simple Modification After coming up with the modular solution, I realized that there were still ways to simplify the solution. In particular, it would have been helpful to start the mapping from zero. One of the hiccups I ran into in the previous solution was when the user selected paper. As a result, the expression `(user_choice + 1) % 3`python would evaluate to zero which isn't one of our choices. To compensate, the solution has to also evaluate the modulo of the computer's choice. With the change to zero indexing, we no longer have to mod the computer's choice. Another benefit to changing to zero indexing is that we can replace our dictionary with a list. After all, lists use numeric indexing, so rock, paper, and scissors can be mapped directly. The following complete solution is based on the change to zero indexing: import random import sys # Create number to choice mapping mapping = ["Rock", "Paper", "Scissors"] # Generate computer choice pc_choice = random.randint(0, 2) pc_choice_output = "I chose %s." % mapping[pc_choice] # Request user choice try: user_choice = int(input("Choose Rock (0), Paper (1), or Scissors (2): ")) user_choice_output = "You chose %s." % mapping[user_choice] except (ValueError, KeyError): print(pc_choice_output) print("You chose nothing.") print("You lose by default.") sys.exit(0) # Share choices print(pc_choice_output) print(user_choice_output) # Setup results i_win = "%s beats %s - I win!" % (mapping[pc_choice], mapping[user_choice]) u_win = "%s beats %s - you win!" % (mapping[user_choice], mapping[pc_choice]) tie = "Tie!" # Share winner if pc_choice == user_choice: print(tie) elif (user_choice + 1) % 3 == pc_choice: print(i_win) else: print(u_win) And, that's it! We've created a command line Rock Paper Scissors game using modular arithmetic in under 40 lines of code. The Power of Modular Arithmetic After writing this article, I took to the internet to see if anyone had done anything like this before, and it turns out I'm not the first, sadly. On the plus side, there's a lot of information out there on why this solution works. As it turns out, there is a different expression which better captures the relationship between the different choices: (user_choice - pc_choice) % 3 From this expression, we have three cases: 0 (tie)1 (user wins)2 (computer wins) Ironically, this expression would allow us to get rid of conditions altogether. In other words, we could place our results strings directly into a list: print([tie, u_win, i_win][(user_choice - pc_choice) % 3]) Of course, this almost becomes an exercise in code golf where I think the branching solution is more readable. Having revisited this article several times in the last couple years, I may just make a follow up article that takes things to an extreme. For now, however, we'll move on. But wait, there's more! As an added bonus, we can even expand this solution to an arbitrary number of choices. One game I've seen mentioned a handful of times is Rock Paper Scissors Lizard Spock. In this case, we would encode the five choices using the values zero through four and determine winners using the following expression: (user_choice - pc_choice) % 5 From this expression, we'd still have three cases: 0 (tie)1, 2 (user wins)3, 4 (computer wins) In other words, the first half of the difference results in a win for the user while the second half of the difference results in a loss for the user. As we can see, this sort of solution scales to an arbitrary number of choices which is alarmingly efficient. Instead of writing out the square of the number of choices as cases, we only have to handle the same three scenarios. How's that for the power of modular arithmetic? Share Your Stories Despite not being the first to solve Rock Paper Scissors using modular arithmetic, I really thought this was cool and interesting, and I hope you did too. If you know any complex problems that have an elegant solution like this, let us know in the comments. I'd be interested in exploring possible patterns in these types of problem. Perhaps there's some technique for reducing branching that we could glean from a few examples. At any rate, thanks again for taking the time to read one of my articles. If you liked what you read, consider passing it along to a friend. Word of mouth can go a long way to helping me out. Until next time!