Internet Problem Solving Contest

IPSC 2012

Problem K – Keys and locks

To: Agent 047.
Mission: Acquire suitcase from room #723.
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)

file 13 012012012
try 13 723
file 13 111111111
try 9999 -47
room key: 202102022
key 13 new bitting 012012012
key 13 new bitting 112112112
try failed -- incorrect syntax

try 13 719
file 13 012012012
try 13 723
room key: 220012110
key 13 new bitting 012012012

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.