[TDD]LeetCode 2. Add Two Numbers

用 TDD 來練習完成 LeetCode 的第 2 題,題目描述如下。

LeetCode 第 2 題題目解釋:給兩個 ListNode 分別為 L1 L2ListNode 的概念就像 LinkedList 的 Node 一樣,可以代表一串正整數。當 L1 + L2 代表兩串正整數相加,加完的 ListNode 應為兩串正整數相加的結果。
其實這題目就是兩個大數正整數相加的資料結構設計方式。兩個數字相加,不管宣告成 int32 或是 long 都有其表示範圍的極限,超過就會出現 overflow exception,透過將數字拆成整數串列,每一位數字相加,若有進位情況,則將進位的數字 1 帶往下一個 Node,最後將每一個數字串起來,代表相加完的結果即可。所以,L1 L2 分別代表倒序排列的正整數相加完的結果,只需要再倒序回來,即為兩正整數相加的實際結果

前言 

這道題我用 TDD 練習了兩次,第一次 TDD 的過程,最後雖然完成了,但我覺得測試案例的設計順序不對。應先針對單一個數字的所有情況都設計完畢後,才考慮兩個數字的情況,最後針對三個數字的情況才重構成迴圈或遞迴。

本篇文章將以第二次 TDD 的歷程為基準,目的是用以呈現 TDD 時,

  1. 對測試程式的重構,是如何提昇 TDD 的生產力
  2. 設計測試案例的順序,是如何 baby step 的方式堆砌/雕塑出 production code
  3. 重構時,透過一些簡單的手法,例如 introduce variable 或 inline variable 來找到重複的 pattern,再將其抽象出來共用。

第一個紅燈,L1_is_5_and_L2_is_4_should_return_9

Step 1
測試案例代表性:L1 長度為 1,L2 長度為 1,沒有進位

測試代碼:

        [TestMethod]
        public void L1_is_5_and_L2_is_4_should_return_9()
        {
            var l1 = new ListNode(5);
            var l2 = new ListNode(4);
            var expected = new ListNode(9);

            Assert.AreEqual(expected.val, new Solution().AddTwoNumbers(l1, l2).val);
        }

生產代碼:

    public class Solution
    {
        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            throw new NotImplementedException();
        }
    }

    public class ListNode
    {
        public int val;
        public ListNode next;

        public ListNode(int x)
        {
            val = x;
        }
    }

第一個綠燈,L1.val + L2.val 以通過綠燈

Step 2

生產代碼:

        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            return new ListNode(l1.val + l2.val);
        }

重構測試程式,讓後面的測試案例用最少的 effort 撰寫

Step 3

將 assertion 的部分抽取出來為 AssertResult(),測試代碼如下:

        [TestMethod]
        public void L1_is_5_and_L2_is_4_should_return_9()
        {
            var l1 = new ListNode(5);
            var l2 = new ListNode(4);
            var expected = new ListNode(9);

            AssertResult(expected, l1, l2);
        }

        private static void AssertResult(ListNode expected, ListNode l1, ListNode l2)
        {
            Assert.AreEqual(expected.val, new Solution().AddTwoNumbers(l1, l2).val);
        }
這樣後面的測試案例,Assert 的部分只需要輸入 AR + tab 即可省去原本要打很多字的工。

新增 ListNode.All() 的測試案例,以輔助 ListNode 多個 next 值的驗證

Step 4
ListNode 增加一個 All() 的方法,其本意其實是組出 ListNode LinkedList。這一個方法與 LeetCode 需求無關,也與 Solution 本身無關。但 ListNode 有了 All() 的方法,對後續驗證 ListNode 多個值有幫助。

ListNode.All() 測試代碼:

    [TestClass]
    public class ListNodeTests
    {
        [TestMethod]
        public void Test_All_ListNode_is_4_1()
        {
            var node = new ListNode(4);
            node.next = new ListNode(1);

            var expected = new List<int>() { 4, 1 };
            expected.ToExpectedObject().ShouldEqual(node.All());
        }
    }

生產代碼:

    public class ListNode
    {
        public int val;
        public ListNode next;

        public ListNode(int x)
        {
            val = x;
        }

        public IEnumerable<int> All()
        {
            var result = new List<int>();
            result.Add(this.val);

            if (this.next != null)
            {
                result.AddRange(next.All());
            }

            return result;
        }
    }

重構測試程式,改用 ListNode.All() 做 Assertion

Step 5

測試代碼調整如下:

        private static void AssertResult(ListNode expected, ListNode l1, ListNode l2)
        {
            expected.All().ToExpectedObject().ShouldEqual(new Solution().AddTwoNumbers(l1, l2).All());
        }

新增一個失敗測試案例:L1_is_8_and_L2_is_6_should_return_4_1

Step 6
測試案例代表性:L1 長度為 1,L2 長度為 1,相加會進位。

測試代碼如下:

        [TestMethod]
        public void L1_is_8_and_L2_is_6_should_return_4_1()
        {
            var l1 = new ListNode(8);
            var l2 = new ListNode(6);
            var expected = new ListNode(4);
            expected.next = new ListNode(1);

            AssertResult(expected, l1, l2);
        }

通過測試案例,當 L1.val + L2.val >= 10 時,需新增 next ListNode

Step 7

生產代碼差異如下:

加總新 Node 的值需 mod 10,而如果加總值超過 10,進位 1 到 next ListNode 的值中。

重構測試案例,使得建立多層 ListNode 更簡便

Step 8
可以看到原本要新增 ListNode 代表 {4,1} 得一直塞 next ListNode,這樣撰寫測試案例實在太麻煩,所以我們希望傳入一個 int[] 就可以迅速建立一個完整的 ListNode 使用。

調整完測試代碼如下:

        [TestMethod]
        public void L1_is_8_and_L2_is_6_should_return_4_1()
        {
            var l1 = new ListNode(8);
            var l2 = new ListNode(6);

            var expected = CreateListNodes(new int[] { 4, 1 });

            AssertResult(expected, l1, l2);
        }

        private static ListNode CreateListNodes(int[] nums)
        {
            if (nums.Length == 0)
            {
                return null;
            }

            var listNode = new ListNode(nums[0]);

            var currentNode = listNode;
            for (int i = 1; i < nums.Length; i++)
            {
                currentNode.next = new ListNode(nums[i]);
                currentNode = currentNode.next;
            }

            return listNode;
        }

新增一個失敗的測試案例:L1_is_5_4_and_L2_is_3_should_return_8_4

Step 9
測試案例代表性:L1 長度來到 2,L2 長度仍為 1,沒有進位

測試代碼如下:

        [TestMethod]
        public void L1_is_5_4_and_L2_is_3_should_return_8_4()
        {
            var l1 = CreateListNodes(new int[] { 5, 4 });

            var l2 = CreateListNodes(new int[] { 3 });

            var expected = CreateListNodes(new int[] { 8, 4 });

            AssertResult(expected, l1, l2);
        }

通過測試案例:新增判斷 L1.next 是否有值,若有,則也需新增 next ListNode

Step 10 

生產代碼差異如下:

【注意】
通常在這步驟,一般開發人員就會把 rootSum >=10L1.next !=nullL2.next != null 一併寫完,而 TDD 的 baby step 就是用最小的異動,最簡單的生產代碼,恰好地通過眼前的紅燈。但心裡很清楚,等等要新增一個測試案例是 L2.next != null 以及進位的測試案例。別急,讓子彈飛一會兒。

新增一個失敗測試案例:L1_is_5_and_L2_is_3_4_should_return_8_4

Step 11
測試案例代表性:換 L2 長度為 2,沒有進位的情境

測試代碼:

        [TestMethod]
        public void L1_is_5_and_L2_is_3_4_should_return_8_4()
        {
            var l1 = new ListNode(5);
            var l2 = CreateListNodes(new int[] { 3, 4 });
            var expected = CreateListNodes(new int[] { 8, 4 });
            AssertResult(expected, l1, l2);
        }

通過測試案例:增加判斷 L2.next 是否有值,若有,也需新增 next ListNode

Step 12

生產代碼差異:

重構生產代碼:整理需新增 next ListNode 的判斷邏輯

Step 13
當發生進位情況,或是 L1.next 與 L2.next 其中一個有值,都應新增 next ListNode

生產代碼重構差異如下:

重構生產代碼:Introduce Variable,將判斷式的 condition 以 variable 呈現

Step 14

生產代碼差異如下:

新增一個失敗測試案例:L1_is_5_4_3_and_L2_is_2_should_return_7_4_3

Step 15
測試案例代表性:長度為 2 的都已經處理完畢,接下來換 L1 長度為 3,沒有進位的情況。

測試代碼:

        [TestMethod]
        public void L1_is_5_4_3_and_L2_is_2_should_return_7_4_3()
        {
            var l1 = CreateListNodes(new int[] {5, 4, 3});
            var l2 = new ListNode(2);
            var expected = CreateListNodes(new int[] {7, 4, 3});
            AssertResult(expected, l1, l2);
        }

通過測試案例:判斷 L1.next.next 是否有值,若有值,需新增 ListNode.next.next 

Step 16

生產代碼差異如下:

這一步走得有點髒,卻是剛好滿足測試案例。我們一樣不急,L2 的判斷與進位的判斷,等後面新增測試案例時,自然就會在生產代碼中加入。

新增一個失敗測試案例:L1_is_5_and_L2_is_1_2_3_should_return_6_2_3 

Step 17
測試案例代表性:L2 長度為 3,無進位。逼出生產代碼需判斷 L2.next.next 是否有值

測試代碼:

        [TestMethod]
        public void L1_is_5_and_L2_is_1_2_3_should_return_6_2_3()
        {
            var l1 = new ListNode(5);
            var l2 = CreateListNodes(new int[] { 1, 2, 3 });
            var expected = CreateListNodes(new int[] { 6, 2, 3 });
            AssertResult(expected, l1, l2);
        }

通過測試的生產代碼:

        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            var rootSum = l1.val + l2.val;
            var rootVal = rootSum % 10;

            var result = new ListNode(rootVal);

            var needCarry = rootSum >= 10;
            var hasL1Next = l1.next != null;
            var hasL2Next = l2.next != null;

            if (needCarry || hasL1Next || hasL2Next)
            {
                var carry = needCarry ? 1 : 0;
                var l1NextVal = l1.next?.val ?? 0;
                var l2NextVal = l2.next?.val ?? 0;

                result.next = new ListNode(carry + l1NextVal + l2NextVal);

                if (hasL1Next && l1.next.next != null)
                {
                    result.next.next = new ListNode(l1.next.next.val);
                }
                else if(hasL2Next && l2.next.next != null)
                {
                    result.next.next = new ListNode(l2.next.next.val);
                }
            }

            return result;
        }

新增一個失敗的測試案例:L1_is_5_4_and_L2_is_2_8_should_return_7_2_1

Step 18
測試案例代表性:L1 與 L2 長度為 2,有進位的情況。

測試代碼:

        [TestMethod]
        public void L1_is_5_4_and_L2_is_2_8_should_return_7_2_1()
        {
            var l1 = CreateListNodes(new int[] { 5, 4 });
            var l2 = CreateListNodes(new int[] { 2, 8 });
            var expected = CreateListNodes(new int[] { 7, 2, 1 });
            AssertResult(expected, l1, l2);
        }

調整生產代碼,通過所有測試

Step 19

生產代碼:

        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            var rootSum = l1.val + l2.val;
            var rootVal = rootSum % 10;

            var result = new ListNode(rootVal);

            var needCarry = rootSum >= 10;
            var hasL1Next = l1.next != null;
            var hasL2Next = l2.next != null;

            if (needCarry || hasL1Next || hasL2Next)
            {
                var carry = needCarry ? 1 : 0;
                var l1NextVal = l1.next?.val ?? 0;
                var l2NextVal = l2.next?.val ?? 0;

                var nextSum = carry + l1NextVal + l2NextVal;
                var nextVal = nextSum % 10;

                result.next = new ListNode(nextVal);

                var needCarry_2 = nextSum >= 10;
                var hasL1Next_2 = hasL1Next && l1.next.next != null;
                var hasL2Next_2 = hasL2Next && l2.next.next != null;

                if (needCarry_2 || hasL1Next_2 || hasL2Next_2)
                {
                    var carry_2 = needCarry_2 ? 1 : 0;
                    var l1Next_2_Val = l1.next?.next?.val ?? 0;
                    var l2Next_2_Val = l2.next?.next?.val ?? 0;
                    result.next.next = new ListNode(carry_2 + l1Next_2_Val + l2Next_2_Val);
                }
            }

            return result;
        }
就像第一次判斷是否要新增 next ListNode 一樣,只是這次是判斷是否新增 next.next。

重構生產代碼:新增多餘的代碼,讓 next 的處理與 next.next 的處理長得一樣 

Step 20
我們很清楚,next 的判斷與處理,應該與 next.next 相同,因此動點手腳,讓兩者的代碼長得一樣,以便後續重構抽象的處理

生產代碼差異:

生產代碼:

        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            var carry_0 = 0;
            var l1Val = l1.val;
            var l2Val = l2.val;

            var rootSum = carry_0 + l1Val + l2Val;
            var rootVal = rootSum % 10;

            var result = new ListNode(rootVal);

            var needCarry = rootSum >= 10;
            var hasL1Next = l1.next != null;
            var hasL2Next = l2.next != null;

            if (needCarry || hasL1Next || hasL2Next)
            {
                var carry = needCarry ? 1 : 0;
                var l1NextVal = l1.next?.val ?? 0;
                var l2NextVal = l2.next?.val ?? 0;

                var nextSum = carry + l1NextVal + l2NextVal;
                var nextVal = nextSum % 10;

                result.next = new ListNode(nextVal);

                var needCarry_2 = nextSum >= 10;
                var hasL1Next_2 = hasL1Next && l1.next.next != null;
                var hasL2Next_2 = hasL2Next && l2.next.next != null;

                if (needCarry_2 || hasL1Next_2 || hasL2Next_2)
                {
                    var carry_2 = needCarry_2 ? 1 : 0;
                    var l1Next_2_Val = l1.next?.next?.val ?? 0;
                    var l2Next_2_Val = l2.next?.next?.val ?? 0;
                    result.next.next = new ListNode(carry_2 + l1Next_2_Val + l2Next_2_Val);
                }
            }

            return result;
        }

重構:以遞迴取代原本的 next 與 next.next 的處理

Step 21

生產代碼如下:

    public class Solution
    {
        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            return CreateSumNode(l1, l2, 0);
        }

        private ListNode CreateSumNode(ListNode l1, ListNode l2, int carry)
        {
            if (l1 == null && l2 == null)
            {
                if (carry == 0)
                {
                    return null;
                }

                return new ListNode(carry);
            }

            var l1Val = l1?.val ?? 0;
            var l2Val = l2?.val ?? 0;

            var rootSum = carry + l1Val + l2Val;
            var rootVal = rootSum % 10;

            var result = new ListNode(rootVal);

            var carryNext = rootSum >= 10 ? 1 : 0;
            result.next = CreateSumNode(l1?.next ?? null, l2?.next ?? null, carryNext);

            return result;
        }
    }
第一次進位值以 0 帶入。判斷傳入的 L1, L2 若為 null 則終止遞迴。

重構:Inline Variable 處理,得到最終版本生產代碼 

Step 22

最終版本生產代碼:

    public class Solution
    {
        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            return CreateSumNode(l1, l2, 0);
        }

        private ListNode CreateSumNode(ListNode l1, ListNode l2, int carry)
        {
            if (l1 == null && l2 == null)
            {
                return carry == 0 ? null : new ListNode(carry);
            }

            var l1Val = l1?.val ?? 0;
            var l2Val = l2?.val ?? 0;

            var rootSum = carry + l1Val + l2Val;

            var result = new ListNode(rootSum % 10);

            var carryNext = rootSum >= 10 ? 1 : 0;
            result.next = CreateSumNode(l1?.next ?? null, l2?.next ?? null, carryNext);

            return result;
        }
    }

通過 LeetCode 所有測試案例

結論

如前言所說,再次強調:

  1. 測試程式的重構,有助於提昇 TDD 撰寫測試案例的速度,並凸顯測試案例的關鍵代表性
  2. 設計測試案例的順序,有助降低於 TDD baby step 化繁為簡,用最小步伐堆砌生產代碼的進入門檻。而 baby step 品質的好壞,會影響重構的成本與範圍。
  3. baby step + 及時重構,可以讓重構的難度、成本、範圍,降到最低。重構時使用一些手法輔助,則可以凸顯出重複的代碼邏輯,有利於淬取抽象或共用的方法。

Reference

兩個版本的 github commit history
  1. 不夠好的測試案例順序
  2. 本文的測試案例順序

社群交流回饋

  • @武可 提到各段落步驟可加上 step 編號,以利社群交流討論
  • @張云雷 提到 hasL1Next 的命名,太過於針對實作細節的,應給予業務意義。因為這個使用情境就是兩大數相加,所以可以將這個變數抽成方法:bool hasHigherDigits(ListNode<int> list)
  • carryNext 改成 carryToHigherDigit
  • @武可 提到,step 10, 12 那兩個 hard-code 的 else if block,到 step 13 的重構,看起來代碼異動比較大,而且不是被測試案例驅動的。而我的說明是,我把 step 13 當作重構,因為在寫 step 10 與 12 時,我心知肚明這邊是 hard-code 的 else if,而且就真實的商業邏輯來說,這不該是 else if,而是可能並存的情況。兩種說法似乎都成立,我的說法在重構,卻改變了原有的邏輯,感覺也說不過去。但 TDD 先 hard-code 某種特殊情況,再進行調整也是合理的。所以,就不太著墨在細節了,請讀者記得這邊其實有兩種作法。你可以選擇在 step 10, step 12 就把生產代碼寫對,逐步加進去,應該可以避免一些誤會或風險。
  • @張云雷 提到,L1 is {1}, L2 is {9,9,9} 的測試案例,在哪一個部分被涵蓋到。我的說明:在 step 6 的測試案例 L1 is {8}, L2 is {6} 結果應為 {4,1} 就被涵蓋到了。因為這次先針對單一元素的所有情況處理完畢,才接著新增多筆元素的情境。

blog 與課程更新內容,請前往新站位置:http://tdd.best/