Contest Python: ACSL › Unit 5 — Bit-String Flicking
Exercises: Unit 5 — Bit-String Flicking
There are two kinds of exercises here, just as on an ACSL contest.
- Short-answer: work it out with pencil and paper and write one exact answer.
- Write every bit string at its full length, including 0s on the left:
00110, not110. - When a question asks for all the values of x, list them in increasing order, separated by a comma and a space:
0011, 1011. - When it asks how many, write just the number, such as
4. - Use
*for a free bit only when the question asks for one pattern.
- Write every bit string at its full length, including 0s on the left:
- Programming: write a complete program that reads the input with
input()and prints exactly the output described. Save it as a.pyfile and run it from a terminal, typing the sample input or feeding it a file.
Each exercise is marked with the lowest ACSL division it belongs to. Do every exercise at or below your division. Exercises marked Challenge are extra practice for when you want more.
Exercise 1: Flip Every Bit
Evaluate NOT 1011010.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: A bit string at its full length, with the 0s on the left kept (`00110`, not `110`).
Exercise 2: Both Must Be On
Evaluate 10110101 AND 01111100.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: A bit string at its full length, with the 0s on the left kept (`00110`, not `110`).
Exercise 3: Exclusive Or
Evaluate 10110 ⊕ 11011.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: A bit string at its full length, with the 0s on the left kept (`00110`, not `110`).
Exercise 4: Different Lengths
Evaluate 1101 OR 1010011.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 5: Slide Right
Evaluate RSHIFT-3 11010110.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: A bit string at its full length, with the 0s on the left kept (`00110`, not `110`).
Exercise 6: Round and Round
Evaluate LCIRC-11 1011001.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: A bit string at its full length, with the 0s on the left kept (`00110`, not `110`).
Exercise 7: Which Goes First?
Evaluate NOT 10110 AND 01110 OR 10001.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 8: Right to Left
Evaluate LSHIFT-2 NOT RCIRC-1 101100.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 9: Lost Off the Edge
Find all 4-bit values of x for which LSHIFT-1 x = 0110.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Every solution in increasing order, each a bit string at its full length (0s on the left kept: `00110`, not `110`), separated by a comma and a space.
Exercise 10: One Pattern
Find all 5-bit values of x for which x AND 10110 = 00100.
Write all of them as one pattern, using * for each bit that can be either 0 or 1.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: One pattern at full length, with `*` for each free bit (as in `**110010`).
Exercise 11: How Many Switches?
How many 6-bit values of x satisfy x OR 100101 = 110111?
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 12: Undo the XOR
Find all 5-bit values of x for which x XOR 01101 = 11000.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Every solution in increasing order, each a bit string at its full length (0s on the left kept: `00110`, not `110`), separated by a comma and a space.
Exercise 13: The Cue Sheet
A stage light board shows a bit string. The cue sheet lists commands, and the board carries them out one at a time, from the top of the list down. Each command is one of:
NOTAND s,OR sorXOR s, wheresis a bit string the same length as the boardLSHIFT-k,RSHIFT-k,LCIRC-korRCIRC-k, wherekis a whole number
The first line of input holds the board.
The second line holds N, the number of commands.
Each of the next N lines holds one command.
After each command, print the board on its own line.
Constraints
- The board has 1 to 30 bits.
1 <= N <= 201 <= k <= 100. A shift by the length or more leaves all zeros; a circulate count may be bigger than the length.
Sample Input
10110010
4
RCIRC-3
AND 11110000
NOT
XOR 00001111Sample Output
01010110
01010000
10101111
10100000How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output line by line.
Exercise 14: Unary Chain
The input is one line: zero or more one-string operators, then a bit string, all separated by single spaces.
Each operator is NOT, LSHIFT-k, RSHIFT-k, LCIRC-k or RCIRC-k.
Evaluate the expression by ACSL's rules (one-string operators go from right to left) and print the result at full length.
Constraints
- The bit string has 1 to 30 bits.
- There are at most 10 operators.
1 <= k <= 100. A shift by the length or more leaves all zeros; a circulate count may be bigger than the length.
Sample Input
RCIRC-9 NOT LSHIFT-1 0110101Sample Output
0100101LSHIFT-1 0110101 = 1101010, then NOT gives 0010101, and RCIRC-9 on 7 bits is RCIRC-2, giving 0100101.
How this is checked: Checked by running your program on 6 test inputs (1 sample, 5 hidden) and comparing its output line by line.
Exercise 15: Symbols Only
Evaluate RCIRC-3 LSHIFT-1 ~11001 ⊕ 10110 & 11100.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: A bit string at its full length, with the 0s on the left kept (`00110`, not `110`).
Exercise 16: Parentheses First
Evaluate (RCIRC-14 110100 OR 001011) AND NOT LSHIFT-2 101101.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: A bit string at its full length, with the 0s on the left kept (`00110`, not `110`).
Exercise 17: Two Moves Back
Find all 5-bit values of x for which RSHIFT-1 LCIRC-2 x = 00110.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Every solution in increasing order, each a bit string at its full length (0s on the left kept: `00110`, not `110`), separated by a comma and a space.
Exercise 18: Spin and Mask
Find all 5-bit values of x for which (LCIRC-2 x) AND 11011 = 01010.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Every solution in increasing order, each a bit string at its full length (0s on the left kept: `00110`, not `110`), separated by a comma and a space.
Exercise 19: Find Every x
The first line of input is a chain of one-string operators ending in the letter x, separated by single spaces, such as RSHIFT-1 LCIRC-2 x.
Each operator is NOT, LSHIFT-k, RSHIFT-k, LCIRC-k or RCIRC-k, and they apply from right to left.
The second line is a bit string T.
Find every bit string x of the same length as T for which the chain applied to x gives T.
Print them one per line, in increasing order.
If there are none, print NONE.
Constraints
Thas 1 to 12 bits.- There are 1 to 10 operators.
1 <= k <= 100
Sample Input
LSHIFT-1 RCIRC-2 x
0110Sample Output
1100
1110With x = abcd, RCIRC-2 x = cdab and LSHIFT-1 of that is dab0, so d = 0, a = 1, b = 1, and c is free.
How this is checked: Checked by running your program on 8 test inputs (1 sample, 7 hidden) and comparing its output line by line.
Exercise 20: Two Copies of x
Find all 5-bit values of x for which (LCIRC-1 x) XOR (RSHIFT-1 x) = 10100.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Every solution in increasing order, each a bit string at its full length (0s on the left kept: `00110`, not `110`), separated by a comma and a space.
Exercise 21: The Whole Expression
The input is one line holding an ACSL bit-string expression with no parentheses, its parts separated by single spaces.
It uses bit strings, the one-string operators NOT, LSHIFT-k, RSHIFT-k, LCIRC-k and RCIRC-k, and the two-string operators AND, XOR and OR.
Every bit string in the expression has the same length.
Evaluate it with ACSL's order of operations and print the result.
Constraints
- Each bit string has 1 to 30 bits.
- There are 1 to 10 bit strings.
1 <= k <= 100
Sample Input
LSHIFT-1 01101 XOR RCIRC-2 11011 AND NOT 10101 OR 00010Sample Output
10010The one-string operators give 11010 XOR 11110 AND 01010 OR 00010; AND next gives 11010 XOR 01010 OR 00010; then XOR gives 10000 OR 00010, and OR gives 10010.
How this is checked: Checked by running your program on 6 test inputs (1 sample, 5 hidden) and comparing its output line by line.