q programming challenge - Narcissistic Numbers

This is the second in an occasional series of q challenges we’ll post on the blog. Please get involved by posting your own solutions in the comments (prior to revealing the solution). As we get through the backlog of challenges that have been posed and completed by the AquaQ team, future challenges will be conducted ‘live’ on the blog, with the best solutions picked from the comments.

[image type=”thumbnail” src=”7080″ alt=”Narcissistic Numbers” link=”true” href=”http://en.wikipedia.org/wiki/Narcissistic_number” target=”blank”]

Puzzle 2 – Narcissistic Numbers

153 is the smallest narcissistic number greater than 10. It’s called narcissistic because when the digits are raised to the power of the count of the digits, you get the original number that is,

1^3 + 5^3 + 3^3 = 1+125+27=153

So the challenge for is using q code, to tell me what is the sum of all the narcissistic numbers between 10 and 2 million inclusive, using the shortest, fastest, q code you can.

[showhide type=”post” more_text=”Show Solution” less_text=”Solution” hidden=”yes”]

Solution 1 – Brute Force

A nice straightforward solution from Andrew using ‘string’ on the sequence of integers, parsing individual digits using “I”$”:

{sl:string l:til x;sum 10_where l=sum each xexp["I"$''sl;count each sl]}2000000

Execution time: approx 4 seconds

Solution 2 – Exponent Matrix

This solution contains two optimisations compared to the first:

Instead of repeating the xexp operation, generate the matrix of x and y arguments (each digit from 0-9 is raised to a maximum of a power of 7, so an 8×10 matrix is sufficient) and index into it
Rather than parsing each digit char, find it in the char list .Q.n instead – the digit value corresponds to the position in that list (e.g. 1 2 3~.Q.n?”123″)

r:til[10] xexp/: til 8;sum x where x=o:sum each r[count each a]@'a:.Q.n?string x:10+til 2000000-9

Execution time: approx 1.2 seconds

Solution 3 – Advanced

Can we do better than that? Well, yes. For solution 2, the string operation is the most expensive part. However, the digits in the sequence of integers from 0 to 2000000 repeat in regular ways – it’s possible to programmatically generate each ‘column’ (1s, 10s, 100s etc) without having to string the list.



narc:{[n]
  / flat list containing exponents - x^y is indexable by doing r[(10*y)+x]
  r:raze til[10] xexp/: til 1+count string n;
  / matrix of digits 
  m:n#'where each deltas each n&sums each 10#/:p:floor 10 xexp til count string n;
  / digit count
  d:n#where deltas[p],n-max p;
  / totals
  o:sum r m+\:10*d;
  / sum of matches
  sum o where til[n]=not[o<10]*o}

narc 2000000

Execution time: approx 0.2 seconds

[/showhide]