Q For Problems - Episode 1

Community Support
1

[Q For Problems - Episode 1](“https://vimeo.com/752172115” "“Q”) 

 

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](“https://projecteuler.net/problem=1” "“Project”) 

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

2

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.

3

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

4

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

 

5

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

6

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!

7

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

 

 

8

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.

9

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

 

 

10

Great video, looking forward to episode 2!