1
\$\begingroup\$

In an attempt to “liberate” their fellow birds, a group of highly intelligent hens are attempting to compromise the zoo’s security system. To get access to the zoo’s mainframe, the hens first need to guess the administrative password. The hens know that the password is a string built from up to 62 possible characters: a, b, c, ..., z, A, B, C, ..., Z, 0, 1, ... 9. They also know that no character appears more than once in the password, which means that it has a maximum length of 62 (and a minimum length of 1). The password is case-sensitive.

We define a guess be close if and only if the real password can be obtained by inserting additional characters among the letters and numbers of the original guess. In other words, a guess is close if it is a (not necessarily contiguous) subsequence of the password. Every time the hens guess a password, the zoo’s security system will do one of three things:

  • If the guess is exactly equal to the password, it will print ‘C’ and grant the hens access to the mainframe.
  • If the guess close but not exactly equal to the password, it will print ‘Y’.
  • If the guess is neither close nor exactly equal to the password, it will print ‘N’.

The mainframe permits at most 750 guesses before it locks further attempts and alerts the zoo officials of suspicious activity. The hens have hired you to guess the password before you use all of your allotted attempts.

There will be no initial input. Every time your program makes a guess, the grader will output ‘C’, ‘Y’, or ‘N’, which your program can then read via the usual input channel. The grader will only respond to the first 750 guesses. Make sure that you end each guess with a new line.

This question was adapted from the 2020 mBIT Computing Olympiad.

Test Program made by me in Python 3 (works):

from functools import cmp_to_key

def ask(s):
    print(s)
    c = input()
    if c == 'C':
        exit()
    return c == 'Y'

def cmp(a, b):
    return -1 if ask(a + b) else 1

ret = []
for i in range(48, 58):
    if ask(chr(i)):
        ret.append(chr(i))
for i in range(65, 91):
    if ask(chr(i)):
        ret.append(chr(i))
for i in range(97, 123):
    if ask(chr(i)):
        ret.append(chr(i))

ret = "".join(sorted(ret, key=cmp_to_key(cmp)))
print(ret)

I think it can be condensed even further, but that sample is just to show what the program is trying to ask. I do not own this question and all rights are to 2020 mBIT. The rules are simple. Do not just print answers and shortest one wins in any language.

\$\endgroup\$
10
  • 6
    \$\begingroup\$ Hi! This question looks reasonable, but there are a couple of things you need to add. Firstly, if it's code golf, add the code-golf tag (instead of code-challenge). The second is I/O format: consider the community's loose I/O rules. In particular, I'd suggest to allow the answer to be a function and the grader to be passed as a black-box function. \$\endgroup\$ – Sisyphus Nov 9 '20 at 2:18
  • \$\begingroup\$ Some people will print the test cases therefore "matching the test cases" but that is considered cheating. \$\endgroup\$ – VJZGamingHD Nov 9 '20 at 2:34
  • \$\begingroup\$ @VJZGamingHD For the tag, you made a typo: it's not cold-golf, but code-golf. \$\endgroup\$ – Bubbler Nov 9 '20 at 2:42
  • 4
    \$\begingroup\$ @VJZGamingHD "matching the test cases" is a standard loophole here. Don't worry too much about that. \$\endgroup\$ – Razetime Nov 9 '20 at 2:50
  • 1
    \$\begingroup\$ IMO, It could be easy to have an implementation (like the one given in question). Bit it would be hard to prove the implementation always success within 750 guesses. \$\endgroup\$ – tsh Nov 9 '20 at 4:00
2
\$\begingroup\$

Python 3.7, 162 bytes

import string as S,functools as F
A=lambda s:'N'!=Input(s+'\n')
print(''.join(sorted(filter(A,S.ascii_letters+S.digits),key=F.cmp_to_key(lambda a,b:1-2*A(a+b)))))

Tries characters one-by-one to see which ones are in the password. Then sorts those letters using a comparison function. To compare 'A' and 'B', check to see if 'AB' returns 'Y'. If is does, then 'A' comes before 'B', otherwise 'A' comes after 'B'.

\$\endgroup\$
2
  • \$\begingroup\$ @tsh need input(s+'\n') and fixed the bug ('N'!=input()) \$\endgroup\$ – RootTwo Nov 10 '20 at 3:30
  • \$\begingroup\$ @tsh, in response to your comment above about the number of comparisons. In 20k runs with 62 character passwords, my code averaged 350 comparisons and never took more than 362. \$\endgroup\$ – RootTwo Nov 10 '20 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.