Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- KX Community
- :
- Discussion Forums
- :
- Developer Tools
- :
- Re: Advent of code2020 day 15 solution improvement

Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

Advent of code2020 day 15 solution improvement

Options

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

2020.12.15 03:00 AM

(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.

________________

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?

8 REPLIES 8

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

2020.12.15 05:45 AM

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;

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.

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]

________________ [.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.

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

2020.12.15 06:30 AM

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]};

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

2020.12.15 07:52 AM

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[x]:c;c+::1;l}

(N-count i)f/last i

f:{l:j x;l:$[l<c;c-l;0];j[x]:c;c+::1;l}

(N-count i)f/last i

Regards,

András

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

2020.12.15 08:09 AM

Actually,

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

is more elegant, does not seem to be faster.

Andras

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

2020.12.16 12:49 AM

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

2020.12.16 12:51 AM

Regards.

- Rohith

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

2020.12.16 12:33 AM

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

2020.12.16 12:26 AM

Related Content

Main Office Contacts

**EMEA**

Tel: +44 (0)28 3025 2242

**AMERICAS**

Tel: +1 (212) 447 6700

**APAC**

Tel: +61 (0)2 9236 5700

Useful Information

Resources

Popular Links

Follow Us

KX. All Rights Reserved.

KX and kdb+ are registered trademarks of KX Systems, Inc., a subsidiary of FD Technologies plc.