Cassidoo’s Interview question of the week | 451

Learning Resources
1

Hello :waving_hand:

This week question is about returning unique combinations of a given integer.

Given an integer n, return all unique combinations of Perrin numbers (up to and including the nth Perrin number) that sum to a target value k, where each Perrin number can be used at most once. Return the combinations sorted in ascending order.

> perrinCombinations(7, 12)
[[0,2,3,7],[0,5,7],[2,3,7],[5,7]]

> perrinCombinations(6, 5)
[[0,2,3],[0,5],[2,3],[5]]

Happy coding!

2
Solution 👀 
def perrin_numbers(n)
  return [3][0..n] if n <= 0
  return [3, 0][0..n] if n == 1
  return [3, 0, 2][0..n] if n == 2

  perrin = [3, 0, 2]
  (3..n).each { |i| perrin << perrin[i-2] + perrin[i-3] }

  perrin
end

def perrin_combinations(n, k)
  numbers = perrin_numbers(n).uniq.sort
  result = []

  find_combinations(numbers, k, 0, [], result)

  result.sort_by { |combo| [combo.length, combo] }
end

def find_combinations(numbers, remaining, start, current, result)
  result << current.dup if remaining == 0

  numbers.each_with_index do |num, i|
    next if i < start
    break if num > remaining

    current << num
    find_combinations(numbers, remaining - num, i + 1, current, result)
    current.pop
  end
end
1 Like
3

Here are two versions: my first solution, and then a refactored version after I realized (after looking at the solution by @eayurt) that it could be more efficient.

Original solution 
def perrin_combinations(n, k)
  numbers = (0..n).map { perrin_number(it) }

  (1..numbers.count).flat_map { |count|
    numbers.combination(count).map(&:uniq).map(&:sort).select { |combo| combo.sum == k }
  }.uniq.sort
end

def perrin_number(n)
  case n
  when ...0 then raise("n cannot be negative")
  when 0 then 3
  when 1 then 0
  when 2 then 2
  else perrin_number(n - 2) + perrin_number(n - 3)
  end
end
Refactored solution 
def perrin_combinations(n, k)
  perrin_numbers(n)
    .uniq
    .sort
    .then { sum_combinations(it, k) }
    .sort
end

def perrin_numbers(n)
  raise("n cannot be negative") if n.negative?

  numbers = [3, 0, 2]
  (3..n).each do |i|
    numbers << numbers[i - 2] + numbers[i - 3]
  end

  numbers[0..n]
end

def sum_combinations(numbers, k_remaining, current = [])
  return [current] if k_remaining.zero?

  numbers
    .take_while { it <= k_remaining }
    .flat_map.with_index { |num, i|
      sum_combinations(numbers[i + 1..], k_remaining - num, current + [num])
    }
end
1 Like
4

This was fun once I realised what a Perrin number was!

Solution 
#!/usr/bin/env ruby

$perrin_numbers = [3, 0, 2]

def perrin_number(n)
  return $perrin_numbers[n] if $perrin_numbers[n]

  raise ArgumentError if n < 2

  $perrin_numbers[n] = perrin_number(n - 2) + perrin_number(n - 3)
end

def perrin_combinations(n, target)
  perrin_numbers = (0..n).map { perrin_number it }.reject { it > target }.uniq

  perrin_count = perrin_numbers.size

  (1...perrin_count).flat_map do |chunk|
    perrin_numbers.combination(chunk).select do |combo|
      combo.sum == target
    end
  end
end

p perrin_combinations(7, 12)
p perrin_combinations(6, 5)
1 Like