9
\$\begingroup\$

Problem author: https://stats.ioinformatics.org/people/5815

You are given a system with a hidden permutation of the numbers \$1, 2, 3, \ldots, n\$. Your task is to guess this permutation by asking the system a series of questions.

Each question consists of providing the system with a permutation of the numbers \$1, 2, 3, \ldots, n\$. The system will respond with the length of the longest common subsequence between your permutation and the hidden permutation.

A subsequence is defined as a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, \$1, 2\$ would be considered a subsequence of \$1, 3, 2\$.

You must guess the hidden permutation using at most \$n^2\$ questions. If you exceed this limit, the system will kill your program.

You can pick an interaction protocol from the two below.

Interaction protocol 1:

  • Communication with the system occurs over standard input and standard output.
  • At first, the system provides you the number \$n\$, which is the length of the array.
  • To ask the system, the program should write a single permutation of the numbers \$1, 2, 3, \ldots, n\$ to the standard output, followed by a newline character.
  • The system will respond with a single integer, which is the length of the longest common subsequence between the permutation provided by the program and the hidden permutation.
  • You are done when you receive the number \$n\$ from the system.

Interaction protocol 2:

  • You can take a number \$n\$ and a black box function as input. The black box function f(user_input) calculates the longest common subsequence between user_input and the permutation that the system holds, provided that user_input is also a permutation of \$1, 2, 3, \ldots, n\$.
  • You are done when you receive \$n\$ from the black box function.
  • A call to the black box function constitutes asking the system and counts towards your question limit.

In both interaction protocols, if you want, you can communicate by passing permutations of \$0, 1, 2, 3, \ldots, n - 1\$ instead.

After receiving \$n\$, what can I do?

The system stops monitoring your program. Your program can crash, loop forever or ask additional questions. You already guessed the permutation, congratulations.

Sample interaction:

Hidden permutation: 3 2 1
---
Input: 3

Output: 1 2 3

Input: 1

Output: 2 1 3

Input: 2

Output: 3 1 2

Input: 2

Output: 3 2 1

Input: 3

Now you've successfully guessed the permutation.

This is , shortest code wins.

\$\endgroup\$
8
  • 3
    \$\begingroup\$ Can we use the numbers 0 to n-1 instead? Is it ok if we continue doing stuff after receiving n? \$\endgroup\$ Mar 12, 2023 at 17:00
  • \$\begingroup\$ Do you have a proof such a thing is possible? (Not required, but it would be nice.) \$\endgroup\$ Mar 14, 2023 at 20:19
  • \$\begingroup\$ Must we count the size of black box function or we can create it without golfing? \$\endgroup\$
    – EzioMercer
    Mar 14, 2023 at 23:45
  • \$\begingroup\$ @EzioMercer The point of a black box function is you don't know what's inside it. If you create the function, whether or not you score it, you know what's inside of it, which defeats the point. \$\endgroup\$
    – Wheat Wizard
    Mar 15, 2023 at 20:24
  • 1
    \$\begingroup\$ @EzioMercer The black box function is the input. When do you ever add the size of the input to the score? It's not even a fixed number. \$\endgroup\$
    – Wheat Wizard
    Mar 15, 2023 at 21:47

3 Answers 3

4
\$\begingroup\$

R, 112 110 101 bytes

\(f,n,g=1:n)for(i in g)for(j in g)if((d=f(b<-c((a=g[-match(i,g)])[1:j-1],i,tail(a,n-j))))>F){F=d;g=b}

Attempt This Online!

Uses all n^2 guesses, even if it receives a response of n first. No output (but the ATO link forces the 'black box' function to print its response each time so you can at least see something!).
It's pretty efficient: if the 'black box' doesn't need to print its response (try it here), it guesses an array of 50 elements in a few seconds.

How?
Starts with a guess of 1..n. Then tries all positions of each digit, updating the guess-so-far whenever the 'black box' output improves, so that each digit gets placed into its correct position in the growing longest-common-subsequence-so-far. This uses exactly n^2 queries to the 'black box' function, with the output of n usually received for one of the queries of the last digit tried (unless it was already in the last position in the secret permutation).

\$\endgroup\$
4
\$\begingroup\$

Pyth, 71 bytes

M?&GHeS[gGPHgPGH*qeGeHhgPGPH)0JK.pSQ#
=kh?tK.meShMr8SgLbKJK=ZE=KfqZgkTK

Try it online!

Pretty slow, won't run on TIO for \$n>5\$. Truthfully I'm not sure how to prove that this will always guess the permutation in \$n^2\$, but assuming you didn't pose an impossible challenge then this does it. The big idea here is we always ask about the permutation which will provide the maximum amount of information. That is, we keep a list of potential matches, and every time we ask about a permutation and receive the length of the longest common subsequence, we filter this list for permutations that agree with the information. To choose the next permutation to ask about, we look at all permutations and select the one which best splits up our potential matches.

Explanation

First we define the "length of the longest subsequence" function.

M                                 # define g(G,H)
 ?&GH                        0    # if G or H are empty, return 0
     eS[                    )     # otherwise return the maximum of
        gGPH                      # g(G, H[:-1])
            gPGH                  # g(G[:-1], H)
                *qeGeHhgPGPH      # 1 + g(G[:-1], H[:-1]), but only if G[-1] == H[-1]

Then we guess the array.

                                            # implicitly assign Q = eval(input())
JK.pSQ                                      # J = K = all possible permutations of [1, ..., Q]
      #                                     # loop infinitely until error
       =kh                                  # set (and print) k to the first element of
          ?tK                               # if K has more than one element
             .m           J                 #   elements of J which minimize lambda b
                      gLbK                  #     map K over g(_, b)
                 hMr8S                      #     get how many of each element there is
               eS                           #     maximum
                           K                # else: K
                            =ZE             # set Z to the next input
                               =K           # set K to
                                 f     K    # K filtered on lambda T
                                  qZgkT     # Z == g(k, T)
\$\endgroup\$
5
  • 3
    \$\begingroup\$ If it can't handle n > 5, isn't it almost certainly not O(n^2)? (edit: to clarify i'm not saying one way or the other whether n^2 is possible) \$\endgroup\$
    – Jonah
    Mar 14, 2023 at 16:55
  • 4
    \$\begingroup\$ Interesting but I'm afraid you've misread the problem statement. From looking at the code I guess you believe a subsequence is a contiguous section. \$\endgroup\$ Mar 14, 2023 at 17:12
  • \$\begingroup\$ @HuỳnhTrầnKhanh You are right, my bad. Fortunately the concept still works, I just had to change the function defined at the start. It only cost me... 20 bytes :( Anyways it should be fixed now. \$\endgroup\$ Mar 15, 2023 at 14:07
  • 2
    \$\begingroup\$ @Jonah The problem doesn't say it should run in \$ O(n^2) \$, and while (maybe) possible, doing so will not be golfy. It only states we must ask no more than \$ n^2 \$ questions. \$\endgroup\$ Mar 15, 2023 at 14:09
  • \$\begingroup\$ @CursorCoercer Ah, you are correct. \$\endgroup\$
    – Jonah
    Mar 15, 2023 at 19:11
1
\$\begingroup\$

Wolfram Language (Mathematica), 151 bytes

Modified from @Dominic van Essen's answer.


Golfed version, try it online!

Module[{g=Range[n],F=0,d,a,b,i,j},For[i=1,i<=n,i++,For[j=1,j<=n,j++,a=DeleteCases[g,i];b=Join[a[[1;;j-1]],{i},a[[-n+j;;]]];d=f[b];If[d>F,F=d;g=b];]];g]

Ungolfed version

(* First define 'black-box' function *)
lcs[x_List, y_List] := Module[{m = Length[x], n = Length[y], L, i, j},
  L = ConstantArray[0, {m + 1, n + 1}];
  For[i = 0, i <= m, i++,
   For[j = 0, j <= n, j++,
    If[i == 0 || j == 0, L[[i + 1, j + 1]] = 0,
     If[x[[i]] == y[[j]], L[[i + 1, j + 1]] = L[[i, j]] + 1,
      L[[i + 1, j + 1]] = Max[L[[i, j + 1]], L[[i + 1, j]]]
      ]
     ]
    ]
   ];
  L[[m + 1, n + 1]]
  ]

blackBox[x_List] := Module[{n = 0},
  n = n + 1;
  Print["query ", n, " output: ", lcs[x, secret]];
  lcs[x, secret]
  ]

(* Now define our 'guess_the_array' function *)
guessTheArray[f_, n_] := Module[{g = Range[n], F = 0, d, a, b, i, j},
  For[i = 1, i <= n, i++,
   For[j = 1, j <= n, j++,
    a = DeleteCases[g, i];
    b = Join[a[[1 ;; j - 1]], {i}, a[[-n + j ;;]]];
    d = f[b];
    If[d > F, F = d; g = b];
    ]
   ];
  g
  ]

secret = RandomSample[Range[20]];
guess = guessTheArray[blackBox, Length[secret]]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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