To: Agent 047. Mission: Acquire suitcase from room #723. Briefing: We managed to get you into room #719, which is on the same floor of the hotel. The hotel still uses the old pin tumbler locks. Housekeeping should have a master key that works for the entire floor. Obtain it in order to get to room #723 undetected. This mission statement will self-destruct in five seconds. In case it does not, please tear it into small pieces and eat it.
Pin tumbler locks
The photograph on the right shows a door with a pin tumbler lock. The static part of the lock is highlighted in green. The inside part, called the plug, is shown in yellow. This part of the lock rotates when a correct key is inserted and turned.
Below are four drawings of the inside of the lock. The first one shows a lock without any key. Inside the lock there are multiple metal pins (blue+red). If there is no key present, the springs push these pins almost, but not entirely, into the plug.
The second and third drawing show what happens when a correct key is inserted into the lock: Each of the pins is actually cut into two separate parts (a blue part and a red part). When a key is inserted into the lock, it pushes the pins out of the plug. The correct key has the property that the boundary between the red and the blue part of each pin exactly matches the boundary of the plug. When this happens, the key can be used to turn the plug and thereby to lock/unlock the door.
The last drawing shows what happens when an incorrect key is inserted into the lock. The pins will be aligned differently and they will block the plug from turning.
Master keys
When you run a hotel, you have the following situation: On one hand, you have a lot of guests, and each guest should only be able to open their own door. On the other hand, you don’t want housekeeping to carry a ring with hundreds of keys. It is way more convenient for them to have a master key – a single key that can open all the locks.
With pin tumbler locks, creating a master key is really simple. You can even take a set of existing locks+keys and one new key and modify the locks to achieve the desired state – each lock can still be unlocked by its original key, and the new key can unlock all of the locks. How to do this? Each pin in each lock will now be divided in two places: one that corresponds to the original key, and one that corresponds to the new master key. (Technically, some of the pins will still be divided in one place. This happens whenever the original key and the master key have the same height at the corresponding location.)
The drawing on the right shows the lock from the previous drawings modified to also admit the second key. Three of the five pins are now divided into three parts (blue, cyan, and red). Now the plug can also be rotated with this new key inside. When that happens, the red and some of the cyan parts of the pins will be inside the plug.
Key profiles and bitting
On the right you can see a key profile – an “empty” key. If you want to create a new key for a lock, you need to take the corresponding key profile (one that fits your lock) and then you need to create the right pattern (called bitting) on the part of the key that goes into the lock. The locksmiths have machines that do this easily, but you can also do it using an iron file, if you have to. (In this task, you have to.)
Each particular bitting can be described by a string of digits. If you have a lock with p pins, there will be exactly p locations on the key that touch the pins when the key is inserted properly. Each pin can be cut in one of k ≤ 10 places. (The possible cut locations are sufficiently apart to prevent the same key from working with differently cut pins.) Thus there are exactly kp different lock-key pairs. Each particular key can be described as a string of p digits from the set {0,…,k − 1}.
Different manifacturers use different encodings of the bitting. In this problem, 0 represents the shortest pin and correspondingly the shallowest cut on the key. (I.e., the larger the number, the more you have to file away when creating the key from an empty profile.) The first number is the pin closest to your hand. (This actually does not matter in this problem.)
In this problem, an empty key profile works as a key with bitting containing all zeroes.
(Note: In practice there is also a standard saying that adjacent pins should have similar cut locations. This is to ensure that the correct key can be inserted and removed smoothly. In this problem we will ignore this and consider all possible keys valid – after all, you will not be using any key too many times.)
The red line in the figure on the right shows how to file the key profile in order to obtain a key for p = 6, k = 5, and bitting 034132.
Problem specification
You may assume that the bittings of the three actual keys (the master key and the guest keys for rooms #719 and #723) are distinct and that they were generated uniformly at random before you started solving the task. (I.e., our grader will not try to do any nasty tricks.)
Your task is to unlock the room #723, using any key that works. There are two completely independent scenarios with slightly different rules. You will be submitting your actions for the easier scenario as output files for the subproblem K1, and for the harder scenario as K2. Here is the list of allowed actions:
Rules common for both subproblems
Specific rules for the easy subproblem
Specific rules for the hard subproblem
Communication example (for the easy subproblem)
Notes: The problem statement describes an actual way how master keys for pin tumbler locks are made. The first four drawings in the problem statement are derived works from pictures in the Wikipedia article “Pin tumbler lock”. Their authors are Wikipedia users Wapcaplet, GWirken and Pbroks13. The drawings are available under the CC BY-SA 3.0 licence.