Solve addition with linked lists

1 files changed, 70 insertions, 0 deletions

diff --git a/2020/08/10/main.rb b/2020/08/10/main.rb
index e69de29..497777f 100644
--- a/2020/08/10/main.rb
+++ b/2020/08/10/main.rb
@@ -0,0 +1,70 @@
+def assert_equal(x, y)
+  raise [x, y].inspect unless x == y
+end
+
+class Node
+  attr_accessor :data, :next
+
+  def initialize(data)
+    @data = data
+  end
+
+  def to_s
+    "#{data}#{self.next&.to_s}"
+  end
+end
+
+class Solution
+  def self.run(l1, l2, carry = 0)
+    return Node.new(carry) if l1.nil? && l2.nil?
+    return l2 if l1.nil?
+    return l1 if l2.nil?
+
+    sum = l1.data + l2.data + carry
+    result = Node.new(sum % 10)
+    result.next = run(l1.next, l2.next, sum / 10);
+    result
+  end
+end
+
+l1 = Node.new(2)
+l1.next = Node.new(4)
+l1.next.next = Node.new(3)
+
+l2 = Node.new(5)
+l2.next = Node.new(6)
+l2.next.next = Node.new(4)
+
+result = Solution.run(l1, l2)
+assert_equal result&.data, 7
+assert_equal result&.next&.data, 0
+assert_equal result&.next&.next.data, 8
+
+l1 = Node.new(9)
+l1.next = Node.new(9)
+l1.next.next = Node.new(9)
+
+l2 = Node.new(9)
+l2.next = Node.new(9)
+l2.next.next = Node.new(9)
+
+result = Solution.run(l1, l2)
+assert_equal result&.data, 8
+assert_equal result&.next&.data, 9
+assert_equal result&.next&.next.data, 9
+assert_equal result&.next&.next&.next.data, 1
+
+=begin
+
+| 1    | 10   | 100  | 1000 |
+| 10^0 | 10^1 | 10^2 | 10^3 |
+| 2 | 4 | 3 |
+| 5 | 6 | 4 |
+
+x == (2 * 10^0) + (4 * 10^1) + (3 * 10^2)
+x == 342
+
+y == (5 * 10^0) + (6 * 10^1) + (4 * 10^2)
+y == 465
+
+=end