1<<-DOC
  2You're given 2 huge integers represented by linked lists.
  3Each linked list element is a number from 0 to 9999 that
  4represents a number with exactly 4 digits.
  5The represented number might have leading zeros.
  6Your task is to add up these huge integers and
  7return the result in the same format.
  8
  9Example
 10
 11For a = [9876, 5432, 1999] and b = [1, 8001], the output should be
 12addTwoHugeNumbers(a, b) = [9876, 5434, 0].
 13
 14Explanation: 987654321999 + 18001 = 987654340000.
 15
 16For a = [123, 4, 5] and b = [100, 100, 100], the output should be
 17addTwoHugeNumbers(a, b) = [223, 104, 105].
 18
 19Explanation: 12300040005 + 10001000100 = 22301040105.
 20
 21Input/Output
 22
 23[time limit] 4000ms (rb)
 24[input] linkedlist.integer a
 25
 26The first number, without its leading zeros.
 27
 28Guaranteed constraints:
 290 ≤ a size ≤ 104,
 300 ≤ element value ≤ 9999.
 31
 32[input] linkedlist.integer b
 33
 34The second number, without its leading zeros.
 35
 36Guaranteed constraints:
 370 ≤ b size ≤ 104,
 380 ≤ element value ≤ 9999.
 39
 40[output] linkedlist.integer
 41
 42The result of adding a and b together, returned without leading zeros in the same format.
 43DOC
 44
 45describe "#add_two_huge_numbers" do
 46  def to_number(head)
 47    number, x = [head.value.to_s.rjust(4, '0')], head
 48    number.push(x.value.to_s.rjust(4, '0')) while x = x.next
 49    number.join.to_i
 50  end
 51
 52  def add_two_huge_numbers(a, b)
 53    x, y = to_number(a), to_number(b)
 54    sum = x + y
 55    chunks = sum.to_s.chars.reverse.each_slice(4).to_a.reverse.map(&:reverse)
 56    chunks.map(&:join).map(&:to_i).to_a
 57  end
 58
 59  [
 60    { a: [9876, 5432, 1999], b: [1, 8001], x: [9876, 5434, 0] },
 61    { a: [123, 4, 5], b: [100, 100, 100], x: [223, 104, 105] },
 62    { a: [0], b: [0], x: [0] },
 63    { a: [1234, 1234, 0], b: [0], x: [1234, 1234, 0] },
 64    { a: [0], b: [1234, 123, 0], x: [1234, 123, 0] },
 65    { a: [1], b: [9998, 9999, 9999, 9999, 9999, 9999], x: [9999, 0, 0, 0, 0, 0] },
 66    { a: [1], b: [9999, 9999, 9999, 9999, 9999, 9999], x: [1, 0, 0, 0, 0, 0, 0] },
 67    { a: [8339, 4510], b: [2309], x: [8339, 6819] },
 68  ].each do |x|
 69    it do
 70      expect(add_two_huge_numbers(
 71        ListNode.to_list(x[:a]), ListNode.to_list(x[:b])
 72      )).to eql(x[:x].to_a)
 73    end
 74  end
 75
 76  class ListNode
 77    attr_accessor :value, :next
 78
 79    def initialize(value, next_node: nil)
 80      @value = value
 81      @next = next_node
 82    end
 83
 84    def to_a
 85      result = []
 86      current = self
 87      until current.nil?
 88        result.push(current.value)
 89        current = current.next
 90      end
 91      result
 92    end
 93
 94    def self.to_list(items)
 95      x = nil
 96      items.inject(nil) do |memo, item|
 97        node = new(item)
 98        if memo.nil?
 99          x = node
100        else
101          memo.next = node
102        end
103        node
104      end
105      x
106    end
107  end
108end