Advent of code2020 day 15 solution improvement

Community Support
1

(TL; DR) No improvement in performance despite using unique key dictionary i.e (`u#())!() .. but similar algorithm in python  was giving results much much faster. Wondering if I had took a wrong approach in solving the problem

Q)  https://adventofcode.com/2020/day/15

A) the algorithm i was trying to implement:  https://np.reddit.com/r/adventofcode/comments/kdf85p/2020\_day\_15\_solutions/gfwrwx6/

so we have to keep on appending numbers to the initial list (example 0 3 6) on the following conditions:

  1. if last element of the unappended list has already occured (i.e not new) then append 0
  2. else append the diiference between the current index and the index of  last occurence

Eventually the list goes like this
 
0 3 6 0 3 3 1 0 4 0 …
the questions asked were to find 2020th, 30000000th elements of such list

My initial solution:

________________

x: 13 0 10 12 1 5

f: {$[1 = count ind: where x = last x; x, 0; x, last deltas -2#ind]}

last (2020 - count x) f/ x
________________
it was slow for the second part (30000000th). so I used a hash map to store last occurrence

https://github.com/8wgf3b/letsee/blob/master/aoc2020/15.q

the problem was that there was no significant improvement in performance.

What do you guys suggest?            
                                                                       

2

Here the solution will get slower and slower the more elements it has because it will hold the entire list produce in memory and then iterates over and adds to it for each new element for your solution and then that is the end output. 
This current problem is not that KDB friendly and it is difficult to use KDB vectorization usefully.

So in your function nextramb  will always retain x and that list is getting bigger and bigger
so initially your x is 
13 0 10 12 1 5 
13 0 10 12 1 5 0

13 0 10 12 1 5 0  5
13 0 10 12 1 5 0 5 … 

Which slows down the function massively.

My solution that applies similar iteration logic that Python code had. My code essentially saves the unique values and indices they appear in and then iterates over the entire list of values. 

So my solution as follows:
________________ 
I:2 0 1 9 5 19;.s.d:(u#I)!u#2#'til[count I];.s.l:last I;

\ts {$[all (x-1)=.s.d[.s.l];
  [.s.d,:enlist[0]!enlist 2#(.s.d[0;1],x) except 0N;.s.l:0];
  [.s.l:last deltas .s.d[.s.l];.s.d,:enlist[.s.l]!enlist 2#(.s.d[.s.l;1],x) except 0N]];
  :x+1}/[30000000-count I;count I]
________________   
I have the Initial input as a global. Then my dictionary (.s.d) of unique values that appear on the sequence and then .s.l the last item that we iterate over.
The unique attribute will remain on the keys as I will only append to the dictionary when a new value is encountered. So all the operations work on the attributed dictionary that has fast indexing as it has the unique attribute. 

The function iterates through all the indices starting from the last input index and going to the amount specified either 30m or 2020.
If the last element in the dictionary is new then it changes .s.l to be 0 and update the indices associated with 0 in the dictionary.
If the last element is not new, then it gets the relevant indices and the step between last occurrence and current occurrence and updates the dictionary with the value. 
Then finally typing .s.l you can get the answer for what the last element was. 

The performance is that for every 1m elements it runs roughly 2seconds. So for 30m it is 60seconds. 

3

Here is my version:

d15:{[n;x]ns:“J”$","vs x;
    arr:(1+max[ns])#0N;
    arr[-1_ns]:1+til count[ns]-1;
    c:n-count ns;
    num:last ns;
    step:count[ns];
    do[c;
        nxt:0^step-arr[num];
        if[count[arr]<=num;arr,:num#0N];
        arr[num]:step;
        num:nxt;
        step+:1;
    ];
    num};
d15p1:{d15[2020;x]};
d15p2:{d15[30000000;x]};

d15p2 “14,1,17,0,3,20” runs in about 19.2s on my machine.

I originally tried to do it with the / iterator as well but the do loop seems to be faster.

Péter

4

My two cents:

i:11 0 1 10 5 19

N:30000000;j:N#N;j[i]:til count i;c:-1+count i
f:{l:j x;l:$[l<c;c-l;0];j:c;c+::1;l}
(N-count i)f/last i

Regards,

András

5

Actually,

f:{l:0|c-j x;j:c;c+::1;l}

is more elegant, does not seem to be faster.

Andras

6

TIL a new way of using q data structures! Understood your explanation too. Thanks for taking time to clear the doubt!

7

Agreed.  Ill try this do loop method too. I like your code structure too. Thank you so much peter

8

Thats a simpler way to implement. Works faster than mine too. Thanks for the help Andras.

9

Appreciate all the help  I got here. I’m sure that you are busy and so I really appreciate your response :)

Regards.

  • Rohith