power_sum.rb

sample_input_0 = """
10
2
"""
sample_input_1 = """
100
2
"""

sample_input_2 = """
1000
2
"""

sample_input_3 = """
100
3
"""

def power_sum(input)
  combinations = []
  count = 0
  x, n = get_numbers(input)
  max = (x**(n**-1)).floor
  range = (1..max).map { |e| e ** n }

  index = 0

  # puts "X: #{x}, N: #{n}"

  (1..max).each do |i|
    range.combination(i).to_a.each_with_index do |array, idx|
      index += idx
      sum = array.inject(0) { |sum, x| sum + x }

      if sum == x
        count += 1
        range = range - array

        # puts "Matching: #{array.inspect}"
        # puts "Current range: #{range.inspect}"
      end

      next if sum > x
    end
  end

  # puts "Complexity (times): #{index}"
  # puts "Power sum: #{count}"
  # puts "________________"

  puts count
  count
end

def get_numbers(str)
  ret = []

  str.lines do |line|
    line = line.delete("\n")
    ret << line.delete("^0-9").to_i unless line.empty?
  end

  ret
end

power_sum(sample_input_0)
power_sum(sample_input_1)
power_sum(sample_input_2)
power_sum(sample_input_3)