[TDD]LeetCode 2. Add Two Numbers

用 TDD 來練習(xí)完成 LeetCode 的第 2 題，題目描述如下。

LeetCode 2. Add Two Numbers

LeetCode 第 2 題 題目解釋：給兩個(gè) ListNode 分別為 **L1 **與 L2，ListNode 的概念就像 LinkedList
的 Node 一樣，可以代表一串正整數(shù)。當(dāng) **L1 **+ L2 代表兩串正整數(shù)相加，加完的 ListNode 應(yīng)為兩串正整數(shù)相加的結(jié)果。

其實(shí)這題目就是兩個(gè)大數(shù)正整數(shù)相加的資料結(jié)構(gòu)設(shè)計(jì)方式。兩個(gè)數(shù)字相加，不管宣告成 int32 或是 long 都有其表示範(fàn)圍的極限，超過就會(huì)出現(xiàn) overflow exception，透過將數(shù)字拆成整數(shù)串列，每一位數(shù)字相加，若有進(jìn)位情況，則將進(jìn)位的數(shù)字 1 帶往下一個(gè) Node，最後將每一個(gè)數(shù)字串起來，代表相加完的結(jié)果即可。所以，L1 與 L2 分別代表倒序排列的正整數(shù)，相加完的結(jié)果，只需要再倒序回來，即為兩正整數(shù)相加的實(shí)際結(jié)果。

前言

這道題我用 TDD 練習(xí)了兩次，第一次 TDD 的過程，最後雖然完成了，但我覺得測(cè)試案例的設(shè)計(jì)順序不對(duì)。應(yīng)先針對(duì)單一個(gè)數(shù)字的所有情況都設(shè)計(jì)完畢後，才考慮兩個(gè)數(shù)字的情況，最後針對(duì)三個(gè)數(shù)字的情況才重構(gòu)成迴圈或遞迴。

本篇文章將以第二次 TDD 的歷程為基準(zhǔn)，目的是用以呈現(xiàn) TDD 時(shí)，

  1. 對(duì)測(cè)試程式的重構(gòu)，是如何提昇 TDD 的生產(chǎn)力。
  2. 設(shè)計(jì)測(cè)試案例的順序，是如何 baby step 的方式堆砌/雕塑出 production code。
  3. 重構(gòu)時(shí)，透過一些簡(jiǎn)單的手法，例如 introduce variable 或 inline variable 來找到重複的 pattern，再將其抽象出來共用。

Step 1, 第一個(gè)紅燈，L1_is_5_and_L2_is_4_should_return_9

測(cè)試案例代表性：L1 長(zhǎng)度為 1，L2 長(zhǎng)度為 1，沒有進(jìn)位

測(cè)試代碼：

        [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);
        }

生產(chǎn)代碼：

    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;
        }
    }

Step 2, 第一個(gè)綠燈，L1.val + L2.val 以通過綠燈

生產(chǎn)代碼：

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

Step 3, 重構(gòu)測(cè)試程式，讓後面的測(cè)試案例用最少的 effort 撰寫

將 assertion 的部分抽取出來為 AssertResult()，測(cè)試代碼如下：

        [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);
        }

這樣後面的測(cè)試案例，Assert 的部分只需要輸入 AR + tab 即可省去原本要打很多字的工作。

Step 4, 新增 ListNode.All() 的測(cè)試案例，以輔助 ListNode 多個(gè) next 值的驗(yàn)證

替 ListNode 增加一個(gè) All() 的方法，其本意其實(shí)是組出 ListNode 的 LinkedList。這一個(gè)方法與 LeetCode 需求無關(guān)，也與 Solution 本身無關(guān)。但 ListNode 有了 All() 的方法，對(duì)後續(xù)驗(yàn)證 ListNode 多個(gè)值有幫助。

ListNode.All() 測(cè)試代碼：

    [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());
        }
    }

生產(chǎn)代碼：

    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;
        }
    }

Step 5, 重構(gòu)測(cè)試程式，改用 ListNode.All() 做 Assertion

測(cè)試代碼調(diào)整如下：

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

Step 6, 新增一個(gè)失敗測(cè)試案例：L1_is_8_and_L2_is_6_should_return_4_1

測(cè)試案例代表性：L1 長(zhǎng)度為 1，L2 長(zhǎng)度為 1，相加進(jìn)位的情況。

測(cè)試代碼如下：

        [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);
        }

Step 7, 通過測(cè)試案例，當(dāng) L1.val + L2.val >= 10 時(shí)，需新增 next ListNode

生產(chǎn)代碼差異如下：

生產(chǎn)代碼迭代差異

加總新 Node 的值需 mod 10，而如果加總值超過 10，進(jìn)位 1 到 next ListNode 的值中。

Step 8, 重構(gòu)測(cè)試案例，使得建立多層 ListNode 更簡(jiǎn)便

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

調(diào)整完測(cè)試代碼如下：

        [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;
        }

Step 9, 新增一個(gè)失敗的測(cè)試案例：L1_is_5_4_and_L2_is_3_should_return_8_4

測(cè)試案例代表性：L1 長(zhǎng)度來到 2，L2 長(zhǎng)度仍為 1，沒有進(jìn)位

測(cè)試代碼如下：

        [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);
        }

Step 10, 通過測(cè)試案例：新增判斷 L1.next 是否有值，若有，則也需新增 next ListNode

生產(chǎn)代碼差異如下：

生產(chǎn)代碼迭代差異

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

Step 11, 新增一個(gè)失敗測(cè)試案例：L1_is_5_and_L2_is_3_4_should_return_8_4

測(cè)試案例代表性：換 L2 長(zhǎng)度為 2，沒有進(jìn)位的情境

測(cè)試代碼：

        [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);
        }

Step 12, 通過測(cè)試案例：增加判斷 L2.next 是否有值，若有，也需新增 next ListNode

生產(chǎn)代碼差異：

生產(chǎn)代碼迭代差異

Step 13, 重構(gòu)生產(chǎn)代碼：整理需新增 next ListNode 的判斷邏輯

當(dāng)發(fā)生進(jìn)位情況，或是 L1.next 與 L2.next 其中一個(gè)有值，都應(yīng)新增 next ListNode

生產(chǎn)代碼重構(gòu)差異如下：

生產(chǎn)代碼迭代

Step 14, 重構(gòu)生產(chǎn)代碼：Introduce Variable，將判斷式的 condition 以 variable 呈現(xiàn)

生產(chǎn)代碼差異如下：

生產(chǎn)代碼迭代差異

Step 15, 新增一個(gè)失敗測(cè)試案例：L1_is_5_4_3_and_L2_is_2_should_return_7_4_3

測(cè)試案例代表性：長(zhǎng)度為 2 的都已經(jīng)處理完畢，接下來?yè)Q L1 長(zhǎng)度為 3，沒有進(jìn)位的情況。

測(cè)試代碼：

        [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);
        }

Step 16, 通過測(cè)試案例：判斷 L1.next.next 是否有值，若有值，需新增 ListNode.next.next

生產(chǎn)代碼差異如下：

生產(chǎn)代碼迭代差異

這一步走得有點(diǎn)髒，卻是剛好滿足測(cè)試案例。我們一樣不急，L2 的判斷與進(jìn)位的判斷，等後面新增測(cè)試案例時(shí)，自然就會(huì)在生產(chǎn)代碼中加入。

Step 17, 新增一個(gè)失敗測(cè)試案例：L1_is_5_and_L2_is_1_2_3_should_return_6_2_3

測(cè)試案例代表性：L2 長(zhǎng)度為 3，無進(jìn)位。逼出生產(chǎn)代碼需判斷 L2.next.next 是否有值

測(cè)試代碼：

        [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);
        }

通過測(cè)試的生產(chǎn)代碼：

        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;
        }

Step 18, 新增一個(gè)失敗的測(cè)試案例：L1_is_5_4_and_L2_is_2_8_should_return_7_2_1

測(cè)試案例代表性：L1 與 L2 長(zhǎng)度為 2，有進(jìn)位的情況。

測(cè)試代碼：

        [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, 調(diào)整生產(chǎn)代碼，通過所有測(cè)試

生產(chǎn)代碼：

        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。

Step 20, 重構(gòu)生產(chǎn)代碼：新增多餘的代碼，讓 next 的處理與 next.next 的處理長(zhǎng)得一樣

我們很清楚，next 的判斷與處理，應(yīng)該與 next.next 相同，因此動(dòng)點(diǎn)手腳，讓兩者的代碼長(zhǎng)得一樣，以便後續(xù)重構(gòu)抽象的處理

生產(chǎn)代碼差異：

生產(chǎn)代碼迭代差異

生產(chǎn)代碼：

        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;
        }

Step 21, 重構(gòu)：以遞迴取代原本的 next 與 next.next 的處理

生產(chǎn)代碼如下：

    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;
        }
    }

第一次進(jìn)位值以 0 帶入。判斷傳入的 L1, L2 若為 null 則終止遞迴。

Step 22, 重構(gòu)：清理，得到最終版本生產(chǎn)代碼

最終版本生產(chǎn)代碼：

    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 nodeSum = NodeSum(l1, l2, carry);

            var result = new ListNode(nodeSum % 10);

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

            return result;
        }

        private static int NodeSum(ListNode l1, ListNode l2, int carry)
        {
            var l1Val = l1?.val ?? 0;
            var l2Val = l2?.val ?? 0;

            var nodeSum = carry + l1Val + l2Val;
            return nodeSum;
        }
    }

通過 LeetCode 所有測(cè)試案例

通過 LeetCode 所有測(cè)試案例

結(jié)論

如前言所說，再次強(qiáng)調(diào)：

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

Reference

兩個(gè)版本的 github commit history

  1. 不夠好的測(cè)試案例順序
  2. 本文的測(cè)試案例順序

社群交流回饋

  • @武可 提到各段落步驟可加上 step 編號(hào)，以利社群交流討論
  • @張?jiān)评?/strong> 提到 hasL1Next 的命名，太過於針對(duì)實(shí)作細(xì)節(jié)的，應(yīng)給予業(yè)務(wù)意義。因?yàn)檫@個(gè)使用情境就是兩大數(shù)相加，所以可以將這個(gè)變數(shù)抽成方法：bool hasHigherDigits(ListNode<int> list)
  • carryNext 改成 carryToHigherDigit
  • @武可 提到，step 10, 12 那兩個(gè) hard-code 的 else if block，到 step 13 的重構(gòu)，看起來代碼異動(dòng)比較大，而且不是被測(cè)試案例驅(qū)動(dòng)的。

我的說明是，我把 step 13 當(dāng)作重構(gòu)，因?yàn)樵趯?step 10 與 12 時(shí)，我心知肚明這邊是 hard-code 的 else if，而且就真實(shí)的商業(yè)邏輯來說，這不該是 else if，而是 可能並存 的情況。兩種說法似乎都成立。我的說法在重構(gòu)，卻改變了原有的邏輯，感覺也說不過去。但 TDD 先 hard-code 某種特殊情況，再進(jìn)行調(diào)整也是合理的。所以，就不太著墨在細(xì)節(jié)了，請(qǐng)讀者記得這邊其實(shí)有兩種作法。你可以選擇在 step 10, step 12 就把生產(chǎn)代碼寫對(duì)，逐步加進(jìn)去，應(yīng)該可以避免一些誤會(huì)或風(fēng)險(xiǎn)。

  • @張?jiān)评?/strong> 提到，L1 is {1}, L2 is {9,9,9} 的測(cè)試案例，在哪一個(gè)部分被涵蓋到。

我的說明：在 step 6 的測(cè)試案例 L1 is {8}, L2 is {6} 結(jié)果應(yīng)為 {4,1} 就被涵蓋到了。因?yàn)檫@次先針對(duì)單一元素的所有情況處理完畢，才接著新增多筆元素的情境。

  • 與 @張?jiān)评?/strong> 討論到測(cè)試案例的設(shè)計(jì)順序，他提到我這篇文的順序是深度優(yōu)先。並提到相關(guān)引用如下：

TDD 的藝術(shù)這本書上提到過「深度優(yōu)先」和「廣度優(yōu)先」皆可。但是實(shí)踐過程中，還是深度優(yōu)先比較容易控制。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容