Suppose you and your friend are playing a game.
Your friend thinks of some particular sequence of
n bits, and your task is to deduce the sequence by asking them questions.
However, the only type of question you're allowed to ask is "How long is the longest common subsequence of your sequence and
S is any sequence of bits.
The fewer questions you need, the better.
Your task is to write a program or function that takes as input a positive integer
n, and a binary sequence
R of length
The sequence may be an array of integers, a string, or some other reasonable type of your choice.
Your program shall output the sequence
Your program is not allowed to access the sequence
The only thing it's allowed to do to
R is to give it as input to the function
len_lcs along with another binary sequence
len_lcs(R, S) returns the length of the longest common subsequence of
This means the longest sequence of bits which occurs as a (not necessarily contiguous) subsequence in both
The inputs of
len_lcs which may be of different lengths.
The program should call this function on
R and other sequences some number of times, and then reconstruct the sequence
R based on that information.
Consider the inputs
n = 4 and
R = "1010".
First, we might evaluate
len_lcs(R, "110"), which gives
"110" is the longest common subsequence of
Then we know that
R is obtained from
"110" by inserting one bit at some position.
Next, we might try
len_lcs(R, "0110"), which returns
3 since the longest common subsequences are
"0110" is not correct.
Then we try
len_lcs(R, "1010"), which returns
Now we know that
R == "1010", so we can return that sequence as the correct output.
This required 3 calls to
Rules and scoring
In this repository, you'll find a file called
subsequence_data.txt containing 100 random binary sequences of lengths between 75 and 124.
They were generated by taking three random floats between 0 and 1, taking their average as
a, and then flipping an
You score is the average number of calls to
len_lcs on these sequences, lower score being better.
Your submission should record the number of calls.
There are no time limits, except that you should run your program on the file before submitting it.
Your submission shall be deterministic.
PRNGs are permitted, but they must use today's date,
200116 (or closest equivalent), as the random seed.
You are not allowed to optimize your submission against these particular test cases.
If I suspect this is happening, I will generate a new batch.
This is not code golf, so you're encouraged to write readable code.
Rosetta Code has a page on the longest common subsequence; you may use that to implement
len_lcs in your language of choice.