$($Python$)$

The line above is from the perennial favorite $1980$s movie adaptation of William Goldman's The Princess Bride, wherein a mysterious hero sits down to a battle of wits with a villainous Sicilian kidnapper. The setup: two cups positioned between the two, one of which $($purportedly$)$ contains a colorless, odorless, lethal poison $($viz$.,$ iocane powder$).$ After a guess is made as to which cup contains the poison, both drink, and the winner is the one left standing.

For this machine problem you will write a program that simulates multiple rounds of this battle of wits, allowing the player to repeatedly guess which cup is poisoned. The computer will "place" the poison before the player guesses, and will reveal who is right... and who is dead, afterwards.

At the outset, the computer will always place the poison in cup $2$ before letting the player guess, but after enough guesses have been entered the computer will start to place the poison based on the pattern of previous guesses so as to outsmart the player.

Here's a sample game session $($note how the silly player keeps alternating guesses, and that the computer catches on to this fact after a while$)$:

Where is the iocane powder: my cup $(1)$ or yours $(2)?1$

Wrong! Ha$!$ Never bet against a Sicilian!

You died $1$ times, and I drank the poison $0$ times

Where is the iocane powder: my cup $(1)$ or yours $(2)?2$

Good guess! Ack! I drank the poison!

You died $1$ times, and I drank the poison $1$ times

Where is the iocane powder: my cup $(1)$ or yours $(2)?1$

Wrong! Ha$!$ Never bet against a Sicilian!

You died $2$ times, and I drank the poison $1$ times

Where is the iocane powder: my cup $(1)$ or yours $(2)?2$

Good guess! Ack! I drank the poison!

To keep track of the pattern of previous guesses, you will use a dictionary that maps a pattern $($of fixed length$)$ to a list of counts for the subsequent guess.

For instance, imagine that the computer observes the player continuing to alternate guesses across ten separate attempts, like so: $\text{'}1\text{'},\text{'}2\text{'},\text{'}1\text{'},\text{'}2\text{'},\text{'}1\text{'},\text{'}2\text{'},\text{'}1\text{'},\text{'}2\text{'},\text{'}1\text{'},\text{'}2\text{'}.$ If we are using a pattern detection length of three, then after the fourth guess we can create an entry in our dictionary that maps the key $\text{'}121\text{'}$ to the list $[0,1],$ where the second value $(1)$ in the list indicates that the player guessed $\text{'}2\text{'}$ following the sequence $\text{'}1\text{'},\text{'}2\text{'},\text{'}1\text{'}.$ After the fifth guess, we create the entry $\text{'}212\text{'}->[1,0],$ and after the sixth guess we update the value for $\text{'}121\text{'}$ to $[0,2]($since the user guesses $\text{'}2\text{'}$ again, after the sequence $\text{'}1\text{'},\text{'}2\text{'},\text{'}1\text{'}).$

Once the player enters a series of guesses that matches a previously seen pattern, the computer should place the poison in the cup that the player is least likely to guess next. When the player enters the next guess, the dictionary should be updated to reflect the actual guess.

This means that if the computer has yet to see a given pattern of guesses, or when the counts are tied, it will have to place the poison "blindly" $---$ your implementation should simply place the poison furthest away from itself $($cup $2).$

Exercise $1$: record$\_$guess $(5$ points$)$

The first function you are to complete is record$\_$guess. It will take the following arguments:

a dictionary to update $($possibly containing previously recorded pattern $->$ list mappings$)$

a pattern string

a guess $--$ which is either $\text{'}1\text{'}$ or $\text{'}2\text{'}.$

If necessary, the function will create a new entry for the pattern $($if one doesn't already exist$),$ then record the updated count for the guess. Since the dictionary is updated in place $($i$.$e$.,$ mutated$),$ the function will not return anything.

Exercise $2$: next$\_$placement $(5$ points$)$

The next function you'll write will take a dictionary of pattern $->$ counts mappings and a string representing the pattern of most recent guesses, and return the next best location $($either $\text{'}1\text{'}$ or $\text{'}2\text{'})$ for the poison $($i$.$e$.,$ to try and outwit the player$).$ If the pattern hasn't been seen previously or the counts are tied, the function should return $\text{'}2\text{'}.$

Exercise $3$: play$\_$interactive $($optional$,$ but fun!$)$

Now for some fun. The function play$\_$interactive will take just one argument $---$ the length of patterns to use as keys in the dictionary $---$ and will start an interactive game session, reading either $\text{'}1\text{'}$ or $\text{'}2\text{'}$ from the player as guesses, using the functions you wrote above and producing output as shown in the sample game session at the beginning of this writeup. If the player types in any other input $($besides $\text{'}1\text{'}$ or $\text{'}2\text{'}),$ the game should terminate.

Exercise $4$: play$\_$batch $(10$ points$)$

Finally, so that we can check your implementation against a lengthier sequence of guesses without having to play an interactive session, implement the play$\_$batch function, which will take the pattern$\_$length argument as your play$\_$interactive function did, but will also take a sequence of guesses. The function will return the total numbers of wins and losses, as determined by the same algorithm as before.