topic Re: Advent of code2020 day 15 solution improvement in kdb+ and q
https://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/717#M701
TIL a new way of using q data structures! Understood your explanation too. Thanks for taking time to clear the doubt!<BR /><BR /><DIV class="gmail_quote"></DIV>Wed, 16 Dec 2020 08:26:23 GMTkarnabalaj2020-12-16T08:26:23ZAdvent of code2020 day 15 solution improvement
https://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/712#M696
<DIV></DIV><DIV>(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<BR /></DIV><DIV><BR /></DIV><DIV>Q) https://adventofcode.com/2020/day/15<BR /></DIV><DIV>A) the algorithm i was trying to implement: https://np.reddit.com/r/adventofcode/comments/kdf85p/2020_day_15_solutions/gfwrwx6/<BR /><BR /><BR /></DIV>so we have to keep on appending numbers to the initial list (example 0 3 6) on the following conditions:<BR />1) if last element of the unappended list has already occured (i.e not new) then append 0<BR />2) else append the diiference between the current index and the index of last occurence<BR /><BR />Eventually the list goes like this<BR /> <BR />0 3 6 0 3 3 1 0 4 0 ...<BR />the questions asked were to find 2020th, 30000000th elements of such list<BR /><BR /><DIV>My initial solution:</DIV><DIV>________________</DIV><BR /><DIV>x: 13 0 10 12 1 5<BR /></DIV><DIV>f: {$[1 = count ind: where x = last x; x, 0; x, last deltas -2#ind]}</DIV><DIV>last (2020 - count x) f/ x<BR />________________<BR />it was slow for the second part (30000000th). so I used a hash map to store last occurrence<BR /><BR />https://github.com/8wgf3b/letsee/blob/master/aoc2020/15.q<BR /><BR />the problem was that there was no significant improvement in performance. <BR /></DIV><DIV>What do you guys suggest? <BR /> <BR /></DIV>Tue, 15 Dec 2020 11:00:36 GMThttps://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/712#M696karnabalaj2020-12-15T11:00:36ZRe: Advent of code2020 day 15 solution improvement
https://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/713#M697
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. <BR />This current problem is not that KDB friendly and it is difficult to use KDB vectorization usefully.<BR /><BR />So in your function nextramb will always retain x and that list is getting bigger and bigger<BR />so initially your x is <BR />13 0 10 12 1 5 <BR />13 0 10 12 1 5 0<BR /><DIV>13 0 10 12 1 5 0 5<BR />13 0 10 12 1 5 0 5 .... <BR /><BR />Which slows down the function massively.<BR /><BR />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. <BR /><BR />So my solution as follows:<BR />________________ <BR />I:2 0 1 9 5 19;.s.d:(`u#I)!`u#2#'til[count I];.s.l:last I;<BR /><DIV>\ts {$[all (x-1)=.s.d[.s.l];<BR /> [.s.d,:enlist[0]!enlist 2#(.s.d[0;1],x) except 0N;.s.l:0];<BR /> [.s.l:last deltas .s.d[.s.l];.s.d,:enlist[.s.l]!enlist 2#(.s.d[.s.l;1],x) except 0N]];<BR /> :x+1}/[30000000-count I;count I]</DIV>________________ <BR />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.<BR />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. <BR /><BR />The function iterates through all the indices starting from the last input index and going to the amount specified either 30m or 2020. <BR />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.<BR />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. <BR />Then finally typing .s.l you can get the answer for what the last element was. <BR /><BR />The performance is that for every 1m elements it runs roughly 2seconds. So for 30m it is 60seconds. <BR /><BR /><BR /><BR /></DIV><DIV class="gmail_quote"></DIV>Tue, 15 Dec 2020 13:45:24 GMThttps://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/713#M697sanderroomuscwo2020-12-15T13:45:24ZRe: Advent of code2020 day 15 solution improvement
https://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/714#M698
<DIV>Here is my version:</DIV><DIV><BR /></DIV><DIV><SPAN style="font-family: Courier New;">d15:{[n;x]ns:"J"$","vs x;<BR /> arr:(1+max[ns])#0N;<BR /> arr[-1_ns]:1+til count[ns]-1;<BR /> c:n-count ns;<BR /> num:last ns;<BR /> step:count[ns];<BR /> do[c;<BR /> nxt:0^step-arr[num];<BR /> if[count[arr]<=num;arr,:num#0N];<BR /> arr[num]:step;<BR /> num:nxt;<BR /> step+:1;<BR /> ];<BR /> num};<BR />d15p1:{d15[2020;x]};<BR />d15p2:{d15[30000000;x]};</SPAN><BR /></DIV><DIV><BR /></DIV><DIV><SPAN style="font-family: Courier New;">d15p2 "14,1,17,0,3,20"</SPAN> runs in about 19.2s on my machine.</DIV><DIV>I originally tried to do it with the / iterator as well but the do loop seems to be faster.</DIV><DIV><BR /></DIV><DIV>Péter<BR /></DIV><DIV><BR /></DIV><DIV class="gmail_quote"></DIV>Tue, 15 Dec 2020 14:30:58 GMThttps://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/714#M698gyorokpeter2020-12-15T14:30:58ZRe: Advent of code2020 day 15 solution improvement
https://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/715#M699
<DIV dir="ltr">My two cents:<DIV><BR /></DIV><DIV><FONT face="monospace">i:11 0 1 10 5 19<BR /></FONT></DIV><DIV><FONT face="monospace">N:30000000;j:N#N;j[i]:til count i;c:-1+count i<BR />f:{l:j x;l:$[l<c;c-l;0];j[x]:c;c+::1;l}<BR />(N-count i)f/last i</FONT><BR /></DIV><DIV><BR /></DIV><DIV>Regards,</DIV><DIV>András</DIV><DIV><BR /></DIV></DIV><BR /><DIV class="gmail_quote"></DIV>Tue, 15 Dec 2020 15:52:25 GMThttps://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/715#M699dotsch2020-12-15T15:52:25ZRe: Advent of code2020 day 15 solution improvement
https://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/716#M700
<DIV dir="ltr">Actually,<DIV><BR /></DIV><DIV><FONT face="monospace">f:{l:0|c-j x;j[x]:c;c+::1;l}</FONT></DIV><DIV><BR /></DIV><DIV>is more elegant, does not seem to be faster.</DIV><DIV><BR /></DIV><DIV>Andras</DIV></DIV><BR /><DIV class="gmail_quote"></DIV>Tue, 15 Dec 2020 16:09:53 GMThttps://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/716#M700dotsch2020-12-15T16:09:53ZRe: Advent of code2020 day 15 solution improvement
https://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/717#M701
TIL a new way of using q data structures! Understood your explanation too. Thanks for taking time to clear the doubt!<BR /><BR /><DIV class="gmail_quote"></DIV>Wed, 16 Dec 2020 08:26:23 GMThttps://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/717#M701karnabalaj2020-12-16T08:26:23ZRe: Advent of code2020 day 15 solution improvement
https://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/718#M702
Agreed. Ill try this do loop method too. I like your code structure too. Thank you so much peter<BR /><BR /><DIV class="gmail_quote"></DIV>Wed, 16 Dec 2020 08:33:40 GMThttps://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/718#M702karnabalaj2020-12-16T08:33:40ZRe: Advent of code2020 day 15 solution improvement
https://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/719#M703
Thats a simpler way to implement. Works faster than mine too. Thanks for the help Andras.<BR /><BR /><DIV class="gmail_quote"></DIV>Wed, 16 Dec 2020 08:49:50 GMThttps://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/719#M703karnabalaj2020-12-16T08:49:50ZRe: Advent of code2020 day 15 solution improvement
https://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/720#M704
Appreciate all the help I got here. I'm sure that you are busy and so I really appreciate your response <span class="lia-unicode-emoji" title=":slightly_smiling_face:">🙂</span><BR /><BR /><DIV>Regards.</DIV><DIV>- Rohith<BR /></DIV><BR /><DIV class="gmail_quote"></DIV>Wed, 16 Dec 2020 08:51:37 GMThttps://community.kx.com/t5/kdb-and-q/Advent-of-code2020-day-15-solution-improvement/m-p/720#M704karnabalaj2020-12-16T08:51:37Z