Q For Problems - Episode 1

[jkane17]

Q For Problems - Episode 1 

Hi everyone,

Please check out episode 1 for my new Q For Problems video series.

This series will use the Q language to solve various programming problems.

Episode 1 covers problem 1 from the Project Euler problem set. Project Euler - Problem 1 

Feel free to share your own solutions and ideas in the comments as I would be very interested to see what other people come up with.

Thanks

[lfox]

Nice video, I didnt compare performance but here's what I came up with initially;

f:{sum distinct (3*1+til n div 3),5*1+til (n:x-1) div 5}

The same idea with the lists but I have joined and distinct on the lists rather than calculating for 15.

[Root]

Thank your for taking the time to explain this to me Jonathan! Very well organized video.

[jkane17]

Nice one!

I ran the perf test and these were the results compared to s1 and s2.

Below 1000:

f              n      total                average              mem  
---------------------------------------------------------------------
(`s1;1000;3 5) 100000 0D00:00:01.000680000 0D00:00:00.000010007 41120
(`s2;999;3 5)  100000 0D00:00:00.061489000 0D00:00:00.000000615 384  
(`lfox;1000)   100000 0D00:00:00.261888000 0D00:00:00.000002619 17536

Below 100000:

f                n    total                average              mem    
-----------------------------------------------------------------------
(`s1;100000;3 5) 1000 0D00:00:01.112241000 0D00:00:00.001112241 5243040
(`s2;99999;3 5)  1000 0D00:00:00.000624000 0D00:00:00.000000624 384    
(`lfox;100000)   1000 0D00:00:00.149855000 0D00:00:00.000149855 1310848

[lfox]

Nice, thanks. Somewhere in between then, maybe the join/distinct isn't very performant then 

[jkane17]

Yeah, it still has to create and traverse the list of numbers, so space and time requirements will grow with n. But, it is a significant improvement over s1!

[SJT]

Not as fast as s2 but much faster than s1:

q){til each y}[10;3 5]
0 1 2
0 1 2 3 4
q){(y-1)=til each y}[10;3 5]
001b
00001b
q){(x-1)#'(y-1)=til each y}[10;3 5]
001001001b
000010000b
q){any(x-1)#'(y-1)=til each y}[10;3 5]
001011001b
q){where any(x-1)#'(y-1)=til each y}[10;3 5]
2 4 5 8
q){1+where any(x-1)#'(y-1)=til each y}[10;3 5]
3 5 6 9
q){sum 1+where any(x-1)#'(y-1)=til each y}[10;3 5]
23

q)\ts:10000 s1[1000;3 5]
141 41344
q)\ts:10000 s2[1000;3 5]
12 960
q)\ts:10000 s3[1000;3 5]
32 8480

Of course there is no need to add 1 to each index before summing. For high values of x, just add in to the sum of the indices their count.

q)s4:{sum(count;sum)@\:where any(x-1)#'(y-1)=til each y}
q)s4[1000;3 5]
233168
q)\ts:10000 s4[1000;3 5]
30 5408

[jkane17]

Interesting solution to build up the multiples using the take (#) on the Boolean list to create a repeated list with the true values occurring where the multiples lay.

[SJT]

Not as mathematically sophisticated as s2, but exploits the speed of the interpreter’s mapping of bits to indices. 

Of course the bit pattern repeats in groups of 15, so one can shorten the arguments to any, but it takes a large value of x for this to pay off.

q)s5:{sum(sum;count)@\:where (x-1)#any prd[y]#'(y-1)=til each y}

q)\ts:1000 s4[1000000;3 5]
745 5243168
q)\ts:1000 s5[1000000;3 5]
635 5243168

[DBaker]

Great video, looking forward to episode 2!