Upload:
3:34 AM 07/08/2019
Description
My girlfriend is a great programmer, she loves to study Complexity of Algorithms, Number Theory, Computational Geometry, Graphs, Dynamic Programming... But she hates sharing her codes.
One day she showed me a program that, given a numerical sequence, showed a value in the output. I used my social engineering skills and managed to steal this executable, but I do not know how it works.
Can you reimplement this algorithm?
paypain on 11:18 AM 07/16/2019: sem nexo
k3rn3lP3nguin on 2:00 AM 08/20/2019: Spent about an hour so far, there's not much at all said on this one so I suppose I'd find my current findings:
binary expects args, lots of args.
You can only use integers, and only count upwards.
./listen-to-your-heart 1 2 3 4 5 (result: 5)
./listen-to-your-heart 5 4 3 2 1 (result: 1)
Found multiple user arguments in suspected main()
Hopefully will find more patterns soon. Anyone else looking into this one?
Nim on 3:04 PM 08/20/2019: I haven't even looked into the code yet, but I found a pattern.
Of course, I'm not 100% sure I'm right, but I haven't been wrong for now.
The program seems to count the numbers you input, but a number is ONLY counted if it's greater than a previous one.
Example:
./listen-to-your-heart 1 2 3 4 5
returns 5, because 2 is greater than 1, 3 is greater than 2, 4 is greater than 3 and 5 is greater than 4, so the counter is incremented 5 times.
But, if we run this:
./listen-to-your-heart 34 36 35 37
that returns 3, because:
-the counter is initialised at 1 (with the input 34)
- +1, because 3634
- +0, because 35 is not greater than 36
- +1, because 3736
I tested this with multiple inputs, of different values, and it worked each time.
So if I had to quickly rewrite the algorithm:
--------------
inputs = list of inputs
max = inputs[0]
counter = 1
for i in inputs:
if i not an integer:
display "Only Integers!"
exit
if imax:
max = i
counter += 1
display counter
exit
------------------------
Nim on 3:06 PM 08/20/2019: (shit, the greater and lesser signs disappeared in my previous comment, and the spaces for indentation too... It's the first time I comment on this website, sorry. I hope it's still clear tho)
growlnx on 3:21 AM 09/19/2019: Hint: There is a great possibility that this program is implementing a classic algorithm.
E13V3N on 10:56 AM 11/29/2019: Did you manipulate the longest increasing subsequence algorithm? It seems like, its counting longest increasing subsequence but in some test cases, it's not giving the longest subsequence length.
vr0n on 5:08 PM 03/05/2020: Anyone got a solve on this one? I've done most of the level 1 chals, but can't seem to get this one.
mistilteinn on 1:33 PM 05/22/2020: author's hint and a bit of playing around allows you to implement the algorithm without static analysis of the actual code
growlnx on 12:19 AM 06/01/2020: its counting longest increasing subsequence but in some test cases, it's not giving the longest subsequence length.
Hey @E13V3N, could you give to us a more detailed example of these test cases? I would like to apologize for the delay in answering your question.
You must me logged to submit a solution