# stacks, queues and lists

All input is from standard input and all output is to standard output.1. (throwingcards.py)

Given is an ordered deck of

Throw away the top card and move the card that is now on the top of the deck to the bottom of the deck.

Your task is to find the sequence of the last

Each line of input contains two non-negative numbers: a number

7 2

19 4

10 5

6 3

4000 7

Last 2 cards discarded: [4, 2]

Remaining card: 6

Last 4 cards discarded: [2, 10, 18, 14]

Remaining card: 6

Last 5 cards discarded: [9, 2, 6, 10, 8]

Remaining card: 4

Last 3 cards discarded: [5, 2, 6]

Remaining card: 4

Last 7 cards discarded: [320, 1344, 2368, 3392, 832, 2880, 1856]

Remaining card: 3904

2. (eval.py)

This questions concerns material covered in Section 3.3 of Miller and Ranum. You will be evaluating integer arithmetic expressions over up to 26 variables (where each variabe is one of the letters in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'). The expressions will be either in infix, prefix, or postfix notation. Aside from the variables, the expressions will consist of the following binary operations: '+', '-', '*', '/', and '^'. These correspond to addition, subtraction, multiplication, division, and exponentiation, respectively (i.e. A^B represents A to the exponent of B). The parentheses, namely '(' and ')' will also be used. You can assume that the parentheses are balanced (if used at all).

The default operator precedence is given as follows: '^' has the highest precedence; '*' and '/' have equal precedence but a lesser precedence than '^'; and '+' and '-' have equal precedence but a lesser precedence than '*' and '/'. For example, this means that A+B*C is equivalent to A+(B*C) and A+B^C/D is equivalent to A+((B^C)/D).

One thing to note about the precedence of operators in infix expressions is that while ties are typically broken from left-to-right, ties are broken between two instances of '^' from right-to-left. For example, A*B/C*D=((A*B)/C)*D and A^B^C=A^(B^C).

The input to your calculator is a sequence of lines. The first character in a line is a tag indicating the nature of the remaining contents of the line. The tag is separated by a space from the remaining contents of the line. The definitions of tags is as follows:

· Tag V

The rest of the line contains up to 26 integer numbers defining the values of the 26 variables listed in alphabetical order. A line with tag V may occur more than once in input, in which case it will override the previously stored values. Note, not all variables will necessarily be set at any one time.

· Tag I

The rest of the line is an expression in infix notation. Lexical tokens in the expression can be but do not have to be separated by spaces. Any number of spaces is equivalent to one space.

· Tag R

The rest of the line is a prefix expression. Parentheses do not occur in prefix expressions. Spaces may also occur in prefix expressions and any number of spaces is equivalent to one space.

· Tag O

The rest of the line is a postfix expression. Parentheses do not occur in postfix expressions. Spaces may also occur in postfix expressions and any number of spaces is equivalent to one space.

· Tag E

This is the last line of input and your program should exit.

Your program should first print out each line it takes as input exactly as it appears. For each line with tag I, R, or O your program should then print the values of the expression using the current values of variables.

Note, you are allowed to build upon the infix-to-postfix and postfix-calculator code from the textbook. However, keep in mind that this existing code does not completely capture the functionality your calculator is expected to exhibit. In particular, it does not handle whitespace properly and it always breaks precedence ties from left-to-right. A complete solution will have to overcome these deficiencies.

V 1 -2 3 4 5 -6 7 8 9 10

I (A+B)-C*F

I C * F - ( A + B )

I G * F - ( H + D )

R -+AB*CF

O AB+CF*-

V 16 17 13 11 5 3

O AB+C-D*E/F^

E

V 1 -2 3 4 5 -6 7 8 9 10

I (A+B)-C*F

17

I C * F - ( A + B )

-17

I G * F - ( H + D )

-54

R -+AB*CF

17

O AB+CF*-

17

V 16 17 13 11 5 3

O AB+C-D*E/F^

85184.0

E

3. (mastermind.py)

Game-play consists of a series of guesses by the code-breaker, each of which is followed by feedback from the code-maker about how accurate the guess was. In our version of the game, the code consists of a sequence of 4 characters, each of which will be one of A, B, C, D, E, or F. For example, the selected code may be CCAE. Each guess will also be a sequence of length 4 of those characters.

After each guess, feedback is given in the following form:

where

Your task is to implement a program to play the role of the code-breaker in a game of Mastermind. That is, the user (code maker) has a code in mind and your program (code-breaker) has to make a series of guesses, for each guess the user provides feedback (in the form described above). Your program must find the code after a small number of guesses. Your program does not have to be optimal but if in any game you need more than 8 guesses then your solution will be considered a failure.

For more information on the game and for strategies for building the code-breaker see the

My guess is: ABDD

1w2b

My guess is: ABCC

2w1b

My guess is: ABFF

1w1b

My guess is: ADCB

3w1b

My guess is: ACBD

0w4b --- Game over in 5 steps!

To simplify input/output, we provide two files (download and unzip mastermind.zip).

One file, named mastermind.py, is the template for a code breaker ADT which has two main methods:

· makeGuess(): is supposed to make a guess at what the code is

· getFeedback(self, feedback): which takes as input a string feedback from the code maker in response to the guess made last time

Your task is to complete these two methods. The second file (in the zip file) is mastermindengine.py, which will use your code (in mastermind.py) to break codes given in standard input.

This also includes a method which computes the feedback for a given pair of "code" and "guess".

You only submit the mastermind.py file.

Given is an ordered deck of

*n*cards numbered 1 to*n*with card 1 at the top and card*n*at the bottom. The following operation is performed as long as there are at least two cards in the deck:Throw away the top card and move the card that is now on the top of the deck to the bottom of the deck.

Your task is to find the sequence of the last

*k*discarded cards and the last remaining card.Each line of input contains two non-negative numbers: a number

*n*(where n ≤ 5000) and a number*k*(where k <*n)*. For each input line produce two lines of output. The first line presents the sequence of*k*discarded cards, the second line reports the last remaining card. See the sample for the expected format.*Sample input*7 2

19 4

10 5

6 3

4000 7

*Output for sample input*Last 2 cards discarded: [4, 2]

Remaining card: 6

Last 4 cards discarded: [2, 10, 18, 14]

Remaining card: 6

Last 5 cards discarded: [9, 2, 6, 10, 8]

Remaining card: 4

Last 3 cards discarded: [5, 2, 6]

Remaining card: 4

Last 7 cards discarded: [320, 1344, 2368, 3392, 832, 2880, 1856]

Remaining card: 3904

2. (eval.py)

This questions concerns material covered in Section 3.3 of Miller and Ranum. You will be evaluating integer arithmetic expressions over up to 26 variables (where each variabe is one of the letters in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'). The expressions will be either in infix, prefix, or postfix notation. Aside from the variables, the expressions will consist of the following binary operations: '+', '-', '*', '/', and '^'. These correspond to addition, subtraction, multiplication, division, and exponentiation, respectively (i.e. A^B represents A to the exponent of B). The parentheses, namely '(' and ')' will also be used. You can assume that the parentheses are balanced (if used at all).

The default operator precedence is given as follows: '^' has the highest precedence; '*' and '/' have equal precedence but a lesser precedence than '^'; and '+' and '-' have equal precedence but a lesser precedence than '*' and '/'. For example, this means that A+B*C is equivalent to A+(B*C) and A+B^C/D is equivalent to A+((B^C)/D).

One thing to note about the precedence of operators in infix expressions is that while ties are typically broken from left-to-right, ties are broken between two instances of '^' from right-to-left. For example, A*B/C*D=((A*B)/C)*D and A^B^C=A^(B^C).

The input to your calculator is a sequence of lines. The first character in a line is a tag indicating the nature of the remaining contents of the line. The tag is separated by a space from the remaining contents of the line. The definitions of tags is as follows:

· Tag V

The rest of the line contains up to 26 integer numbers defining the values of the 26 variables listed in alphabetical order. A line with tag V may occur more than once in input, in which case it will override the previously stored values. Note, not all variables will necessarily be set at any one time.

· Tag I

The rest of the line is an expression in infix notation. Lexical tokens in the expression can be but do not have to be separated by spaces. Any number of spaces is equivalent to one space.

· Tag R

The rest of the line is a prefix expression. Parentheses do not occur in prefix expressions. Spaces may also occur in prefix expressions and any number of spaces is equivalent to one space.

· Tag O

The rest of the line is a postfix expression. Parentheses do not occur in postfix expressions. Spaces may also occur in postfix expressions and any number of spaces is equivalent to one space.

· Tag E

This is the last line of input and your program should exit.

Your program should first print out each line it takes as input exactly as it appears. For each line with tag I, R, or O your program should then print the values of the expression using the current values of variables.

Note, you are allowed to build upon the infix-to-postfix and postfix-calculator code from the textbook. However, keep in mind that this existing code does not completely capture the functionality your calculator is expected to exhibit. In particular, it does not handle whitespace properly and it always breaks precedence ties from left-to-right. A complete solution will have to overcome these deficiencies.

*Sample input*V 1 -2 3 4 5 -6 7 8 9 10

I (A+B)-C*F

I C * F - ( A + B )

I G * F - ( H + D )

R -+AB*CF

O AB+CF*-

V 16 17 13 11 5 3

O AB+C-D*E/F^

E

*Output for sample input*V 1 -2 3 4 5 -6 7 8 9 10

I (A+B)-C*F

17

I C * F - ( A + B )

-17

I G * F - ( H + D )

-54

R -+AB*CF

17

O AB+CF*-

17

V 16 17 13 11 5 3

O AB+C-D*E/F^

85184.0

E

3. (mastermind.py)

*Mastermind*is a two-player game in which one player, the code-maker, selects a code (similar to a password), and the second player, the code-breaker, must decipher that code in as few steps as possible.Game-play consists of a series of guesses by the code-breaker, each of which is followed by feedback from the code-maker about how accurate the guess was. In our version of the game, the code consists of a sequence of 4 characters, each of which will be one of A, B, C, D, E, or F. For example, the selected code may be CCAE. Each guess will also be a sequence of length 4 of those characters.

After each guess, feedback is given in the following form:

*x*w*y*bwhere

*x*and*y*are non-negative integers with*x*+*y*≤ 4. This feedback means that there are*x*characters which are correct but in the wrong position and that there are*y*characters that are both correct and in the right position. For example, if the code is CCAE and the guess is CDEA, then the feedback will be 2w1b since E and A are both in the code but not in the right position, and C is in the right position.Your task is to implement a program to play the role of the code-breaker in a game of Mastermind. That is, the user (code maker) has a code in mind and your program (code-breaker) has to make a series of guesses, for each guess the user provides feedback (in the form described above). Your program must find the code after a small number of guesses. Your program does not have to be optimal but if in any game you need more than 8 guesses then your solution will be considered a failure.

For more information on the game and for strategies for building the code-breaker see the

*Wikipedia page*.*Here is a record of an interactive session of the game*My guess is: ABDD

1w2b

My guess is: ABCC

2w1b

My guess is: ABFF

1w1b

My guess is: ADCB

3w1b

My guess is: ACBD

0w4b --- Game over in 5 steps!

To simplify input/output, we provide two files (download and unzip mastermind.zip).

One file, named mastermind.py, is the template for a code breaker ADT which has two main methods:

· makeGuess(): is supposed to make a guess at what the code is

· getFeedback(self, feedback): which takes as input a string feedback from the code maker in response to the guess made last time

Your task is to complete these two methods. The second file (in the zip file) is mastermindengine.py, which will use your code (in mastermind.py) to break codes given in standard input.

This also includes a method which computes the feedback for a given pair of "code" and "guess".

You only submit the mastermind.py file.

You'll get 1 file (113.3KB)