6
\$\begingroup\$

This is for Project Euler #30:

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

\$1634 = 1^4 + 6^4 + 3^4 + 4^4\$
\$8208 = 8^4 + 2^4 + 0^4 + 8^4\$
\$9474 = 9^4 + 4^4 + 7^4 + 4^4\$

As \$1 = 1^4\$ is not a sum it is not included. The sum of these numbers is \$1634 + 8208 + 9474 = 19316\$.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.


list = []
2.upto(1_000_000) do |num|
 list << num if num.to_s.split("").map(&:to_i).map { |num| num ** 5 }.inject(:+) == num
end

puts list.inject(:+)

This works, and I am here for three reasons:

  1. I use map twice, and this smells but I don't know an easier/better way.
  2. How does the & work? Notice I do map(&:to_i) and inject(:+). I have seen examples of this but don't know why they are different and what is going on.
  3. Any suggestions on code improvements?
\$\endgroup\$
5
\$\begingroup\$

Here is a little simpler way to write your code:

list = (2..1_000_000).select do |num|
  num.to_s.chars.map {|digit| digit.to_i ** 5}.inject(:+) == num
end
  1. Using map twice is not big issue here, you operate on small collection and memory is not an issue (for really big collections you would probably want to use lazy, it's slower but somehow smarter).

  2. The ampersand converts a symbol to a proc.

    Inject without ampersand works pretty much the same, see documentation for details:

    If you specify a symbol instead, then each element in the collection will be passed to the named method of memo

    Given memo = 0 and element 12 ruby does: 0 passed-symbol 12.

  3. I'm not sure improvements are worth it, you can't really make it shorter or easier to read and performance or design is not necessary an issue here.

\$\endgroup\$
2
\$\begingroup\$

With these Project Euler problems, always look for ways to break out early if you're going to brute force. Alternately, study the problems and try to find an algorithm shortcut. In this particular problem, some examination can improve the brute force time:

  1. range can be reduced
  2. can break out if partial sum is greater than n

There are probably more optimizations. Also I'd say reduce(:+) seems more readable for sum of an array. Edit: just realized String#chars is much faster than splitting.

#if we limit search to 6 digits, greatest sum is 6 * 9**5 == 354294
def digit_fifth
  list = []  
  (2..354_294).each {|n|
    sum=0
    n.to_s.chars.each {|x|
      sum += x.to_i**5
      break if sum>n
    }
    list << n if sum==n
  }
  list
end

p digit_fifth
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.