~/problems / Greedy

Crack a 4-digit code with exact-match feedback

medium ~30 min Airbnb

A smart lock hides a 4-digit code such as "0472" or "9999": each character is a digit 0-9, digits may repeat, and leading zeros are allowed. You can't read the code, but you can query a server object:

server.guess(attempt: str) -> int

attempt must be a string of exactly 4 digits (anything else raises ValueError). The server answers with the number of positions where attempt has the same digit in the same place as the code. Nothing is said about right digits in the wrong place.

Write crack(server) -> str that returns the code, calling server.guess at most 20 times. (There are 10,000 possible codes, so trying them one by one is far too many.)

# code is "3131"
server.guess("0000")   # 0
server.guess("1111")   # 2   -> the code holds two 1s
server.guess("2222")   # 0
server.guess("3333")   # 2   -> and two 3s; that's all 4 digits
server.guess("1000")   # 0   -> position 0 is not a 1 (0 is known absent, so it can't add matches)
...
crack(server)          # "3131"

The tests run crack on every possible code, check the answer and count your calls. Returning the code doesn't need a final confirming guess.

Show hint

first learn which digits occur and how often (what does guessing "dddd" tell you?). A digit that doesn't occur at all makes a handy filler later.

Topic: Greedy with sorting. Sort, then take the locally best choice; prove it with an exchange argument.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc