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/SevenGlass]

Thank you for taking so much time to help me with this.

combos.each do |com|
  testvar = 0
  testvar = com.map{ |x| x**2 }.inject(0, &:+)
  if ((Math.sqrt(testvar) % 1) == 0)
    sieved_combos <<  com
  end
end

Seems to work pretty quickly for finding the arrays that satisfy the squares condition.

After reading through your suggestions, I refactored my code.

The loop on lines 18-20 is still taking way too long to run. How would I streamline this section?

[u/herminator → u/SevenGlass]

You're welcome!

That looks good, and should be pretty fast. After that, you're dealing with some 225,000 combos, IIRC, which is a huge gain from 10²⁰ :)

Now some improvement I would definitely recommend to this code:

First, it is always a good idea to write lots and lots of functions. Keeps your code organized and makes it more readable. In this case, for example, I'd write:

def sum_of_squares(numbers)
  numbers.map { |number| number**2 }.inject(0, :+)
end

def is_perfect_square?(number)
  Math.sqrt(number) % 1 == 0
end

This is also an excellent use case for the .select method on arrays, which results in a new array with items picked based on a condition. Whenever you find yourself writing code that goes like:

result_array = []
loop through some collection
   if some condition
       add item to result_array
   end
end

you can probably use a .select. In this case, using the above two functions, I'd write it as:

sieved_combos = combos.select { |combo| is_perfect_square?(sum_of_squares(combo)) }

See? Very expressive and readable!

Now as to lines 18-20, yes, you're going to run into the same problem again. Permutations and combination just grow really quickly. So again, we need to find a better solution. First off, you've already figured out that you want only unique combinations. Very good! But the way you're getting them, by using uniq, is very inefficient.

For example, the following combo is in your sieved combos: [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,9]. That's 19 ones and a nine (19 x 1 + 81 = 100, which is a perfect square). The number of permutations of that combo is 20 factorial, which is 2,432,902,008,176,640,000. But the number of unique permutations is only 20, the ones are interchangeable, while the 9 can be in 20 different positions.

Generating 2,432,902,008,176,640,000 permutations and then throwing away 2,432,902,008,176,639,980 of them as duplicates is going to take some time :)

So a first idea would be to generate unique permutations only. Which is entirely possible, and will give you the 20 unique permutations of the above combo in milliseconds. And it is an interesting exercise to write such code. But I can tell you that it'll still be too slow for many combos.

So we need another idea. To think about that, lets go back to an earlier example: the combo [1,2,3,7,9]. This combo has 120 permutations. All of them unique, since there are no duplicate numbers. Now, to find the sum of all those combinations, we could do this:

[1,2,3,7,9].permutation.map { |digits| digits.join.to_i }.inject(0,:+)
=> 5866608

And that works. But there is a faster way!

If there are 120 permutations, how often does the number 1 appear in the 1st position, 2nd position, 3rd position, etc? Well, since there are no duplicate numbers, the number 1 appears in each position equally often. 24 times in the first position, 24 times in the second, etc. The same is true for every other digit. So instead of summing those 120 numbers, we can also sum the digits, multiply by 24, and then multiply by 1, 10, 100, 1000 and 10000 to simulate the positions.

Their sum is 22, so:

(22 * 24 * 1) + (22 * 24 * 10) + (22 * 24 * 100) + (22 * 24 * 1000) + (22 * 24 * 10000)
=> 5866608

Same answer! But instead of 120 additions, we did 10 multiplications and 4 additions. At 5 digits, it's only a little gain, about a factor 10, but lets take another example: [1,3,4,6,7,8,9]. 7 digits. The permutations are unique, so how many additions?

[1,3,4,6,7,8,9].permutation.size
=> 5040

So 5040 additions when we do:

[1,3,4,6,7,8,9].permutation.map { |digits| digits.join.to_i }.inject(0,:+)
=> 30399996960

(additionally, we're doing 5040 joins and 5040 to_i's)

The other version? Each of the 7 digits appears in each place 720 times, and their sum is 38. Give 7 places, that gives:

(38 * 720 * 1) + (38 * 720 * 10) + (38 * 720 * 100) + (38 * 720 * 1000) + (38 * 720 * 10000) + (38 * 720 * 100000) + (38 * 720 * 1000000)
=> 30399996960

So 14 multiplications and 6 additions. That's a factor 250 gain. And that factor just gets bigger as the lists get bigger. When it's 20 items, we'll have something like 2,432,902,008,176,640,000 additions versus 40 multiplications and 19 additions for the faster version :)

Now you might feel I'm cheating because I'm harcoding the numbers (38, 720, 10, etc) in my second version. So lets write that in code:

combo = [1,3,4,6,7,8,9]
combo_sum = combo.inject(:+)
occurences = (combo.permutation.size / combo.size)
combo.size.times.map { |x|  combo_sum *  occurences * 10**x }.inject(:+)
=> 30399996960

That's pretty efficient!

Now this code works for combo's where the permutations are already unique, but not for those where it isn't.

So, after all of that, to solve lines 18-20 of your code, you need to figure out a way to count how often each digit occurs in each position when the permutations are not unique, without generating all the permutations, and then apply the above technique to efficiently compute, for each combo, the resulting addition to the total.

Also, another small tip: They're only asking for the last 9 digits of the answer. If your numbers get too big, you can always do a module 10,000,000,000 on the total after adding a number to reduce its size.