# [Community Puzzle] Van Eck's sequence

https://www.codingame.com/training/easy/van-ecks-sequence

Created by @Crypticsy,validated by @TBali,@ItsAFeature and @Andeagi.
If you have any issues, feel free to ping them.

Hi all !
Iāve tried to pass the tests 5 and 6 that respectively compute the 56804th and 1000000th value of Van Eckās sequence. My code is working but on CodinGameās IDE, the compute time is too long (around 7 seconds on my machine for the test 5 and way way way more for test 6).

My first idea was to create a dictionary that holds each number as a key, and itās latest occurence as the keyās value. I append to my sequence the value that corresponds to the sequenceās latest value. Then, I had to increment each value at each loop. This took something like 65 seconds for test 5, and I have not tried test 6.

My second (and way faster) idea was to browse the reverse sequence and append the reversed index when the latest occurence is found :

latestvalue = l[len(sequence)-2::-1].index(sequence[-1])+1
sequence.append(latestvalue)

(latestvalue is the value to check for latest occurence, sequence is Van Eckās sequence)

Then, do you see any way to improve the compute time of the sequence ? Iāve seen people already solved this puzzle using Python, so it should be feasible.

Hey,

Just think about this : do you REALLY need to save ALL the sequence to solve the problem ?
Maintenance of large objects takes time.

5 Likes

Hello. Your first idea (using dictionary) is the right way to solve this problem.
But you should not increment each value at each loop because it will take so long for big inputs.
Instead, when you get some number, you should subtract from current index (length of sequence so far) the index of this number that is in dictionary, so you get number of steps back to last occurrence of this number, and in fact this method is very fast.

5 Likes

Hi @Liam @Deltaspace,
Thanks for your fast answers! Indeed it was not necessary to work with the list containing the full sequence, I kept only the two latest elements of the sequence at each loop according to your advice Liam, and using the value of the round as a value for each key (each number in the sequence) in the dictionary according to your advice Deltaspace and it work perfectly

Now, my program computes the 56804th element of the sequence in 0.03515s and the 1000000th element in 0.63306s.

Thanks again !

2 Likes

The first 2 test cases are really handy to test the basis. However, they both start with A1 at 0. Maybe adding an extra simple test case with A1 != 0 would be really handy.

3 Likes

I agree. I pass the first two cases, but my algorithm may be flawed, b/c I get 15 for the next one instead of 11, and the 1 instead of 7.

Should the āA Little Longerā sequence start off looking something like this?:

1, 0, 0, 1, 1, 2, 0, 2, 1, 3, 0, 3, 1, 4,ā¦

Or am I doing something wrong?

The sequence starts like this : 1, 0, 0, 1, 3, 0, 3, 2, 0, 3, 3, 1, 8, 0, 5, 0, 2, 9ā¦

You are supposed to append the offset with the latest occurence of the number, not the amount of times the number as appeared so far

4 Likes

Cool. Thanks and my bad. I guess I just didnāt understand the instructions at first, but now I have it fixed.

Hi everyone!

Iām really at a loss here. Iām doing this in C++ and that last test doesnāt want to pass.

I have only one loop, in which I check in a map if An has been seen before. This is my only container since I only use the last value of the sequence. I also use a specific variable for the 0, since it comes up so often, so that I donāt have to access my map as often. What am I missing to make it faster ?

Edit : my first test runs at 0.06 ms, A little stress at 24.2 ms, and a custom example of 650000 calculation runs at roughly 300 ms.

Iāve just tried this and the combination of map nearly always being the wrong choice in c++ and no optimisations makes this slightly harder. You could try using unordered_map or putting optimisation pragmas at the top (before includes):

``````#pragma GCC optimize("-O3")
``````

Either of these options let my code pass whereas the version using map with no optimisations will fail the last test.

4 Likes

Thanks, just the `#pragma` command managed to do it for me.

FWIW, I used a `<map>` and no optimization and it went just fine.

100% in Java by using HashMap. No optimisations

The blazingly fast PHP++ also solved it with very simple code. Time complexity O(n), space complexity also O(n). Last ide test takes around 0.1 sec.

1 Like

I had a hard time passing the last stress test on this. I used an unordered_map and tried RoboStacās optimization pragma (thanks RoboStac). Still didnāt pass. I was pretty sure I only kept track of the minimum data required - I think you have to keep track of all the numbers youāve seen, because you donāt know which numbers you will see further in the sequence. I ended up just using a simple array to store the last indices of the numbers seen, and that made it pass. But then I was not using any hash maps at all in the final solution.

Iām having a really hard time passing the final test. Iāve tried rewriting it with only storing the last time each number is seen. I rewrote it in 3 different languages now.

Stuck at 83% banging my head against the wall.

My algo is using a simple āforā cycle N times. In it there is just a simple if-else and a few variable assignments. This takes ~0.1sec for N=1M in an interpreted language. Maybe your algo runs more than N times, or doing something unnecessary complex in it?

I rewrote it using Map in Javascript instead of an array and that was even slower.

Then I went back to using an array to store the current position of each number and it magically started working, though itās the same as before. ĀÆ_(ć)_/ĀÆ

/ragequit