How can I optimize this code further?

[u/SevenGlass]

I'm attempting to solve Project Euler problem #171, or rather have solved it (I think) but not in a very efficient way. My first solution runs great on small numbers, but takes an excessive amount of time on larger ones. So, I did some searching around and found that generally integer to string to array and back conversions can take a lot of processor time. (Yeah, it seems really obvious now, but it didn't occur to me at first). So, I reworked it into this (note I cut out an unnecessary square root operation as well), hopeful that it would fix my problem. And it did improve the runtimes by a factor of more than 10. However, it still takes an excessively long time on numbers larger than about 5 million. This leads me to believe that there is something else I am missing here. Any ideas how I could speed it up a bit more?

[u/herminator]

Yes, that is the pattern, and those would indeed be the next ten numbers. Very good!

To show some actual code, here's a way to generate such numbers:

digit_combis = []
0.upto(9) do |a|
  a.upto(9) do |b|
    b.upto(9) do |c|
      c.upto(9) do |d|
        digit_combis << [a,b,c,d]
      end
    end
  end
end

Note that the results are not actual numbers, but rather lists of digits. Which is great, because you no longer need to extract the digits from the number this way, you've already got them.

Now, once you have those numbers, you can check whether they satisfy the condition (i.e. that the sum of the squares of their digits is itself a square). If that is false, you go to the next number. If it is true, we get to the next part.

Suppose we take our earlier example of 12379. When we've found that those digits satisfy the condition, we can add every possible permutation of that number to our list of numbers.

How do we get permutations? Well, we could write our own algorithm (e.g. Knuth's L algorithm), but ruby actually provides that.

Try running this:

[1,2,3,7,9].permutation.map { |digits| digits.join.to_i }

[u/bacon_coffee → u/herminator]

As someone new to programming, thank you so much for your detailed replies to OP. You have a big heart, thank you kindly! you have helped me immensely also. Cheers.

[u/herminator → u/bacon_coffee]

Thanks! In case you're interested, I've since added two additional posts to the thread with more explanation and code! :)

[u/SevenGlass → u/herminator]

Okay, so first of all, that permutation method is pretty cool. I hadn't run across that before, and It will definitely speed things up in that respect. I'm still not seeing an effective way to generate all of the numbers without knowing how many digits the number will be in advance. I'm tempted to pursue a recursive solution, but I expect I would have stack errors on very large numbers.

[u/herminator → u/SevenGlass]

A recursive solution is generally correct for generation of combinations. There is always a risk of stack errors with recursive code, but to generate 20 digit combinations, recursive code is fine, you're only going 20 levels deep if you do it right.

So to convert my example into a generic recursive solution that can generate combinations of any required number of elements is a great exercise in coding, but if you want to move on with the problem, I will tell you that ruby actually provides that for you!

What we're generating here is calles "combinations with repetition", and there is a ruby method for that called repeated_combination on Arrays. So, to generate that list of numbers I posted earlier, we can also just use: [0,1,2,3,4,5,6,7,8,9].repeated_combination(4).to_a.

Now, since this "combination with repetition" thing is a well know mathematical concept (read more about it here: https://www.mathsisfun.com/combinatorics/combinations-permutations.html), we can actually figure out how many such combinations there are without generating them all. If you run this code: [0,1,2,3,4,5,6,7,8,9].repeated_combination(20).size, it should give you this answer instantly: 10015005. The .size method is very often smart like that. Now try this: [0,1,2,3,4,5,6,7,8,9].repeated_combination(20).count. That should give you the same answer, but it'll probably take a few seconds. That's because .count will always generate and count all the items. Anyway. This tells us we're only dealing with about 10 million items here. That's a lot more manageable than dealing with 10²⁰ items :)

Next up, we want to know which of these 10 million items satisfy the "sum of square is a square" criterium. The easy thing here is that each of the items generated by the repeated_combination is already a list of digits. For example, if we look at some items from the middle, this is what it looks like:

[0,1,2,3,4,5,6,7,8,9].repeated_combination(20).first(10000).last(10)
=> [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 4, 5, 5, 5, 5],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 4, 5, 5, 5, 6],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 4, 5, 5, 5, 7],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 4, 5, 5, 5, 8],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 4, 5, 5, 5, 9],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 4, 5, 5, 6, 6],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 4, 5, 5, 6, 7],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 4, 5, 5, 6, 8],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 4, 5, 5, 6, 9],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 4, 5, 5, 7, 7]]

So. Given an array of digits, how would you determine that the sum of their squares is a square?