[TDD]LeetCode 2. Add Two Numbers
2017-02-26 本文已影响63人
就是91
用 TDD 來練習完成 LeetCode 的第 2 題，題目描述如下。
LeetCode 2. Add Two Numbers
LeetCode 第 2 題 題目解釋：給兩個 ListNode 分別為 **L1 **與 L2，ListNode 的概念就像 LinkedList
的 Node 一樣，可以代表一串正整數。當 **L1 **+ L2 代表兩串正整數相加，加完的 ListNode 應為兩串正整數相加的結果。
其實這題目就是兩個大數正整數相加的資料結構設計方式。兩個數字相加，不管宣告成 int32 或是 long 都有其表示範圍的極限，超過就會出現 overflow exception，透過將數字拆成整數串列，每一位數字相加，若有進位情況，則將進位的數字 1 帶往下一個 Node，最後將每一個數字串起來，代表相加完的結果即可。所以，L1 與 L2 分別代表倒序排列的正整數，相加完的結果，只需要再倒序回來，即為兩正整數相加的實際結果。
前言
這道題我用 TDD 練習了兩次，第一次 TDD 的過程，最後雖然完成了，但我覺得測試案例的設計順序不對。應先針對單一個數字的所有情況都設計完畢後，才考慮兩個數字的情況，最後針對三個數字的情況才重構成迴圈或遞迴。
本篇文章將以第二次 TDD 的歷程為基準，目的是用以呈現 TDD 時，
- 對測試程式的重構，是如何提昇 TDD 的生產力。
- 設計測試案例的順序，是如何 baby step 的方式堆砌/雕塑出 production code。
- 重構時，透過一些簡單的手法，例如 introduce variable 或 inline variable 來找到重複的 pattern，再將其抽象出來共用。
Step 1, 第一個紅燈，L1_is_5_and_L2_is_4_should_return_9
測試案例代表性：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;
}
}
Step 2, 第一個綠燈，L1.val + L2.val 以通過綠燈
生產代碼：
public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
{
return new ListNode(l1.val + l2.val);
}
Step 3, 重構測試程式，讓後面的測試案例用最少的 effort 撰寫
將 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即可省去原本要打很多字的工作。
Step 4, 新增 ListNode.All() 的測試案例，以輔助 ListNode 多個 next 值的驗證
替
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;
}
}
Step 5, 重構測試程式，改用 ListNode.All() 做 Assertion
測試代碼調整如下：
private static void AssertResult(ListNode expected, ListNode l1, ListNode l2)
{
expected.All().ToExpectedObject().ShouldEqual(new Solution().AddTwoNumbers(l1, l2).All());
}
Step 6, 新增一個失敗測試案例：L1_is_8_and_L2_is_6_should_return_4_1
測試案例代表性：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);
}
Step 7, 通過測試案例，當 L1.val + L2.val >= 10 時，需新增 next ListNode
生產代碼差異如下：
生產代碼迭代差異
加總新 Node 的值需
mod10，而如果加總值超過 10，進位 1 到nextListNode的值中。
Step 8, 重構測試案例，使得建立多層 ListNode 更簡便
可以看到原本要新增
ListNode代表 {4,1} 得一直塞nextListNode，這樣撰寫測試案例實在太麻煩，所以我們希望傳入一個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;
}
Step 9, 新增一個失敗的測試案例：L1_is_5_4_and_L2_is_3_should_return_8_4
測試案例代表性：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);
}
Step 10, 通過測試案例：新增判斷 L1.next 是否有值，若有，則也需新增 next ListNode
生產代碼差異如下：
生產代碼迭代差異
【注意】
通常在這步驟，一般開發人員就會把rootSum >=10與L1.next !=null與L2.next != null一併寫完，而 TDD 的 baby step 就是用最小的異動，最簡單的生產代碼，恰好地通過眼前的紅燈。但心裡很清楚，等等要新增一個測試案例是L2.next != null以及進位的測試案例。別急，讓子彈飛一會兒。
Step 11, 新增一個失敗測試案例：L1_is_5_and_L2_is_3_4_should_return_8_4
測試案例代表性：換 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);
}
Step 12, 通過測試案例：增加判斷 L2.next 是否有值，若有，也需新增 next ListNode
生產代碼差異：
生產代碼迭代差異
Step 13, 重構生產代碼：整理需新增 next ListNode 的判斷邏輯
當發生進位情況，或是
L1.next與L2.next其中一個有值，都應新增nextListNode
生產代碼重構差異如下：
生產代碼迭代
Step 14, 重構生產代碼：Introduce Variable，將判斷式的 condition 以 variable 呈現
生產代碼差異如下：
生產代碼迭代差異
Step 15, 新增一個失敗測試案例：L1_is_5_4_3_and_L2_is_2_should_return_7_4_3
測試案例代表性：長度為 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);
}
Step 16, 通過測試案例：判斷 L1.next.next 是否有值，若有值，需新增 ListNode.next.next
生產代碼差異如下：
生產代碼迭代差異
這一步走得有點髒，卻是剛好滿足測試案例。我們一樣不急，L2 的判斷與進位的判斷，等後面新增測試案例時，自然就會在生產代碼中加入。
Step 17, 新增一個失敗測試案例：L1_is_5_and_L2_is_1_2_3_should_return_6_2_3
測試案例代表性：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;
}
Step 18, 新增一個失敗的測試案例：L1_is_5_4_and_L2_is_2_8_should_return_7_2_1
測試案例代表性：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;
}
就像第一次判斷是否要新增
nextListNode一樣，只是這次是判斷是否新增next.next。
Step 20, 重構生產代碼：新增多餘的代碼，讓 next 的處理與 next.next 的處理長得一樣
我們很清楚，
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;
}
Step 21, 重構：以遞迴取代原本的 next 與 next.next 的處理
生產代碼如下：
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 則終止遞迴。
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 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 所有測試案例
通過 LeetCode 所有測試案例
結論
如前言所說，再次強調：
- 測試程式的重構，有助於提昇 TDD 撰寫測試案例的速度，並凸顯測試案例的關鍵代表性
- 設計測試案例的順序，有助降低於 TDD baby step 化繁為簡，用最小步伐堆砌生產代碼的進入門檻。而 baby step 品質的好壞，會影響重構的成本與範圍。
- baby step + 及時重構，可以讓重構的難度、成本、範圍，降到最低。重構時使用一些手法輔助，則可以凸顯出重複的代碼邏輯，有利於淬取抽象或共用的方法。
Reference
兩個版本的 github commit history
社群交流回饋
- @武可 提到各段落步驟可加上 step 編號，以利社群交流討論
-
@張云雷 提到
hasL1Next的命名，太過於針對實作細節的，應給予業務意義。因為這個使用情境就是兩大數相加，所以可以將這個變數抽成方法：bool hasHigherDigits(ListNode<int> list) -
carryNext改成carryToHigherDigit -
@武可 提到，step 10, 12 那兩個 hard-code 的
else ifblock，到 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} 就被涵蓋到了。因為這次先針對單一元素的所有情況處理完畢，才接著新增多筆元素的情境。
- 與 @張云雷 討論到測試案例的設計順序，他提到我這篇文的順序是深度優先。並提到相關引用如下：
TDD 的藝術這本書上提到過「深度優先」和「廣度優先」皆可。但是實踐過程中，還是深度優先比較容易控制。
