Codewars 上的 kata: Next bigger number with the same digits
You have to create a function that takes a positive integer number and returns the next bigger number formed by the same digits:
f(12) == 21
f(513) == 531
f(2017) == 2071
If no bigger number can be composed using those digits, return -1:
f(9) == -1
f(111) == -1
f(531) == -1
題目解釋：給一個正整數 input，回傳由相同數字所組成的下一個更大的數字。
本文要透過 TDD 的方式，來解釋我的思路跟程式碼演進過程。
嚴格來說，這個需求用「窮舉法+排序」找下一個更大的值，應該是最快、最直覺的，但這樣比較感受不到 TDD 的過程。所以這個需求，我們將用特定的演算法來求出下一個更大的數字。
第一個紅燈，input = 1, return -1; 因為 1 已經是最大的數字
測試案例用意：先透過第一個測試案例產生對應產品程式碼的骨架。
測試程式碼如下：
[TestClass]
public class UnitTest1
{
private const int NoLargerNumber = -1;
[TestMethod]
public void Test_1_should_be_largestNumber()
{
var input = 1;
var expected = NoLargerNumber;
int actual = NextLargerNumber.Next(input);
Assert.AreEqual(expected, actual);
}
}
產生出來的產品程式碼如下：
public static class NextLargerNumber
{
public static int Next(int input)
{
throw new NotImplementedException();
}
}
接著用最簡單的方式通過測試，直接 return -1;
產品程式碼如下：
public static int Next(int input)
{
return -1;
}
新增一個測試案例：input = 12, should return 21;
這個測試案例用意，需先處理 input 整數要透過 char 取得各位的數字， swap ，以及回傳時要再把 char 組成十進位的數字。
測試程式如下：
[TestMethod]
public void Test_input_is_12_should_return_21()
{
var input = 12;
var expected = 21;
var actual = NextLargerNumber.Next(input);
Assert.AreEqual(expected, actual);
}
產品程式碼設計概念：
- 先將 input 轉成 char array, 再轉成
List<int>以便後續處理。 - 右邊的數字與左邊的數字 swap ，將 swap 完的
List<int>透過Select()+Math.Pow()轉換成十進位數字。 - 原本
return -1;的邏輯，在這先定義為如果 input 產生的List<int>的Count只有 1 時，則return -1;（等到別的測試案例因此失敗或重構時，再來調整。）
注意：我刻意略過了一個商業邏輯，應該是當右邊數字比左邊大，才進行 swap 的動作。這一段商業邏輯，我決定用下一個測試案例 input = 21 來補。
產品程式碼如下：
public static int Next(int input)
{
var inputNumbers = input.ToString().ToCharArray().Select(x => (int)Char.GetNumericValue(x)).ToList();
if (inputNumbers.Count == 1)
{
return -1;
}
var temp = inputNumbers[1];
inputNumbers[1] = inputNumbers[0];
inputNumbers[0] = temp;
int result = GetNumbericFromValueList(inputNumbers);
return result;
}
private static int GetNumbericFromValueList(List<int> inputNumbers)
{
var count = inputNumbers.Count;
var result = inputNumbers.Select((x, index) => x * (Math.Pow(10, (count - index - 1)))).Sum();
return Convert.ToInt32(result);
}
新增下一個測試案例，input=21, should return -1;
這裡有兩種思維，一種是把 21 當作最大值得回傳 -1 來做，合併進去 return -1 的判斷式。另一種則是併入 swap 的判斷式。在這，我決定採後者。因為我期望等等重構時，可以把 return -1 的邏輯也進行重構。
測試案例如下：
[TestMethod]
public void Test_input_is_21_should_be_largestNumber()
{
var input = 21;
var expected = NoLargerNumber;
var actual = NextLargerNumber.Next(input);
Assert.AreEqual(expected, actual);
}
產品程式碼設計概念，只有當右邊的數字 > 左邊的數字，才進行 swap。
如果最後處理完的結果，與傳入的 input 相同，代表已為最大值，應回傳 -1 。
產品程式碼如下：
public static int Next(int input)
{
var inputNumbers = input.ToString().ToCharArray().Select(x => (int)Char.GetNumericValue(x)).ToList();
if (inputNumbers.Count == 1)
{
return -1;
}
if (inputNumbers[1] > inputNumbers[0])
{
var temp = inputNumbers[1];
inputNumbers[1] = inputNumbers[0];
inputNumbers[0] = temp;
}
int result = GetNumbericFromValueList(inputNumbers);
return result == input ? -1 : result;
}
重構
我想先消掉
inputNumbers[1]跟inputNumbers[0]magic number 的壞味道，所以加上 for loop 以 index 取代 1 與 0。
產品程式碼如下：
public static int Next(int input)
{
var inputNumbers = input.ToString().ToCharArray().Select(x => (int)Char.GetNumericValue(x)).ToList();
if (inputNumbers.Count == 1)
{
return -1;
}
for (int index = inputNumbers.Count - 1; index > 0; index--)
{
if (inputNumbers[index] > inputNumbers[index - 1])
{
var temp = inputNumbers[index];
inputNumbers[index] = inputNumbers[index - 1];
inputNumbers[index - 1] = temp;
}
}
int result = GetNumbericFromValueList(inputNumbers);
return result == input ? -1 : result;
}
重構
我想消掉第一個
return -1的判斷式，因為最後的 return 已經有判斷，如果處理完的結果與傳入的 input 相同時，回傳 -1。這一段邏輯是涵蓋了我們 input = 1 的測試案例。
產品程式碼如下：
public static int Next(int input)
{
var inputNumbers = input.ToString().ToCharArray().Select(x => (int)Char.GetNumericValue(x)).ToList();
for (int index = inputNumbers.Count - 1; index > 0; index--)
{
if (inputNumbers[index] > inputNumbers[index - 1])
{
var temp = inputNumbers[index];
inputNumbers[index] = inputNumbers[index - 1];
inputNumbers[index - 1] = temp;
}
}
int result = GetNumbericFromValueList(inputNumbers);
return result == input ? -1 : result;
}
重構
當巡覽
inputNumbers有發生 swap 動作時，代表與原本的 input 不一樣了，這邊就直接回傳 swap 完的結果值。（因為目前測試案例只有兩位數，所以可以直接回傳）反之，如果巡覽過程中，左邊全都比右邊大，沒發生任何 swap 動作，代表本身就是最大值，則 return -1;
產品程式碼如下：
public static int Next(int input)
{
var inputNumbers = input.ToString().ToCharArray().Select(x => (int)Char.GetNumericValue(x)).ToList();
for (int index = inputNumbers.Count - 1; index > 0; index--)
{
if (inputNumbers[index] > inputNumbers[index - 1])
{
var temp = inputNumbers[index];
inputNumbers[index] = inputNumbers[index - 1];
inputNumbers[index - 1] = temp;
return GetNumbericFromValueList(inputNumbers);
}
}
return -1;
}
新增一個預計會通過的測試案例：input = 345, should return 354;
這個測試案例會通過的原因是，第一次的 5 與 4 交換後，剛好是下一個最大值，但 input 已經來到三位數了。
測試案例如下：
[TestMethod]
public void Test_input_is_345_should_return_354()
{
var input = 345;
var expected = 354;
var actual = NextLargerNumber.Next(input);
Assert.AreEqual(expected, actual);
}
新增一個演算法最關鍵的測試案例：input = 576, should return 657;
這個測試案例的用意在於，修正 swap 與處理方式。雖然 input 仍是三位數，但如果照原本的產品程式碼邏輯，最後會回傳是 756，因為第一輪 576 右邊的的 6 比左邊的 7 小，不進行 swap。第二輪右邊的 7 比左邊的 5 大，swap 後的結果是 756。
測試案例如下：
[TestMethod]
public void input_is_576_should_return_657()
{
var input = 576;
var expected = 657;
var actual = NextLargerNumber.Next(input);
Assert.AreEqual(expected, actual);
}
產品程式碼演算法解釋如下：
- 從 input 最右邊的位數往左邊一位比較，如果右邊比左邊小，則往下一位 shift 繼續比較。以這例子來說，就是 6 比 7 小，shift 下一位換 7 跟 5 比較。
- 當右邊的數字，比左邊大時，我們先把原本的 input 以 L,T,R 來表示。以這例子來說，右邊的 7 比左邊的 5 大，要進行 swap 的處理。這時 T 就是 5，R 就是 {7, 6}，L 就是空集合。
- 右邊待 swap 的數字，從 R 的集合中，找出大於 T 的最小值。以這例子來說，就是從 {7,6} 找到比 5 大的最小值為 6。
- 將找到右邊待 swap 的數字，與 T 交換。
- 針對新的 R 做升冪處理，才能確保是最小值的組合。
- 最後的結果為 swap 完畢後的 L + T + R。
註：實際的程式碼為了好寫，L 的集合直接先 include T 的值，比較好進行 swap。
產品程式碼如下：
public static int Next(int input)
{
var inputNumbers = input.ToString().ToCharArray().Select(x => (int)Char.GetNumericValue(x)).ToList();
for (int index = inputNumbers.Count - 1; index > 0; index--)
{
var rightFlag = inputNumbers[index];
var leftFlag = inputNumbers[index - 1];
if (rightFlag > leftFlag)
{
var t = leftFlag; //暫存 for swap
var r = inputNumbers.Skip(index).Take(inputNumbers.Count - index).ToList();
var l = inputNumbers.Take(index).ToList(); //包含t
for (int i = r.Count - 1; i >= 0; i--)
{
if (r[i] > t)
{
l[index - 1] = r[i];
r[i] = t;
break; //找到第一個可以swap的，就是比t大的最小值
}
}
l.AddRange(r.OrderBy(x => x));
return GetNumbericFromValueList(l);
}
}
return -1;
}
重構
將
rightFlag與leftFlag變成 inline variable, 消除不必要的變數。（如果你有用 ReSharper, 這個動作用熱鍵就可以執行）
程式碼如下：
public static int Next(int input)
{
var inputNumbers = input.ToString().ToCharArray().Select(x => (int)Char.GetNumericValue(x)).ToList();
for (int index = inputNumbers.Count - 1; index > 0; index--)
{
if (inputNumbers[index] > inputNumbers[index - 1])
{
var t = inputNumbers[index - 1]; //暫存 for swap
var r = inputNumbers.Skip(index).Take(inputNumbers.Count - index).ToList();
var l = inputNumbers.Take(index).ToList(); //包含t
for (int i = r.Count - 1; i >= 0; i--)
{
if (r[i] > t)
{
l[index - 1] = r[i];
r[i] = t;
break; //找到第一個可以swap的，就是比t大的最小值
}
}
l.AddRange(r.OrderBy(x => x));
return GetNumbericFromValueList(l);
}
}
return -1;
}
重構
將
t變成 inline variable，消除不必要的變數。移除註解。
產品程式碼如下：
public static int Next(int input)
{
var inputNumbers = input.ToString().ToCharArray().Select(x => (int)Char.GetNumericValue(x)).ToList();
for (int index = inputNumbers.Count - 1; index > 0; index--)
{
if (inputNumbers[index] > inputNumbers[index - 1])
{
var r = inputNumbers.Skip(index).Take(inputNumbers.Count - index).ToList();
var l = inputNumbers.Take(index).ToList();
for (int i = r.Count - 1; i >= 0; i--)
{
if (r[i] > inputNumbers[index - 1])
{
l[index - 1] = r[i];
r[i] = inputNumbers[index - 1];
break;
}
}
l.AddRange(r.OrderBy(x => x));
return GetNumbericFromValueList(l);
}
}
return -1;
}
重構
將
Skip().Take().ToList()的部分，改用List.GetRange()取代，原因是來源是 List, 最後也要 List，不如直接用GetRange()避免不必要的巡覽。
重構完程式碼如下：
public static int Next(int input)
{
var inputNumbers = input.ToString().ToCharArray().Select(x => (int)Char.GetNumericValue(x)).ToList();
for (int index = inputNumbers.Count - 1; index > 0; index--)
{
if (inputNumbers[index] > inputNumbers[index - 1])
{
var r = inputNumbers.GetRange(index, inputNumbers.Count - index);
var l = inputNumbers.GetRange(0, index);
for (int i = r.Count - 1; i >= 0; i--)
{
if (r[i] > inputNumbers[index - 1])
{
l[index - 1] = r[i];
r[i] = inputNumbers[index - 1];
break;
}
}
l.AddRange(r.OrderBy(x => x));
return GetNumbericFromValueList(l);
}
}
return -1;
}
重構
將 swap 的處理，擷取方法到
Swap()
程式碼如下：
public static int Next(int input)
{
var inputNumbers = input.ToString().ToCharArray().Select(x => (int)Char.GetNumericValue(x)).ToList();
for (int index = inputNumbers.Count - 1; index > 0; index--)
{
if (inputNumbers[index] > inputNumbers[index - 1])
{
var r = inputNumbers.GetRange(index, inputNumbers.Count - index);
var l = inputNumbers.GetRange(0, index);
Swap(r, inputNumbers, index, l);
l.AddRange(r.OrderBy(x => x));
return GetNumbericFromValueList(l);
}
}
return -1;
}
private static void Swap(List<int> r, List<int> inputNumbers, int index, List<int> l)
{
for (int i = r.Count - 1; i >= 0; i--)
{
if (r[i] > inputNumbers[index - 1])
{
l[index - 1] = r[i];
r[i] = inputNumbers[index - 1];
break;
}
}
}
重構
inputNumbers[index - 1]提取變數到 for loop 外面，且改用 L 集合取代。因為inputNumbers[index-1]與L[index-1]等義。接著消去未使用到的參數
inputNumbers。
程式碼如下：
public static int Next(int input)
{
var inputNumbers = input.ToString().ToCharArray().Select(x => (int)Char.GetNumericValue(x)).ToList();
for (int index = inputNumbers.Count - 1; index > 0; index--)
{
if (inputNumbers[index] > inputNumbers[index - 1])
{
var r = inputNumbers.GetRange(index, inputNumbers.Count - index);
var l = inputNumbers.GetRange(0, index);
Swap(r, index, l);
l.AddRange(r.OrderBy(x => x));
return GetNumbericFromValueList(l);
}
}
return -1;
}
private static void Swap(List<int> r, int index, List<int> l)
{
var t = l[index - 1];
for (int i = r.Count - 1; i >= 0; i--)
{
if (r[i] > t)
{
l[index - 1] = r[i];
r[i] = t;
break;
}
}
}
最終的產品程式碼
public static class NextLargerNumber
{
public static int Next(int input)
{
var inputNumbers = input.ToString().ToCharArray().Select(x => (int)Char.GetNumericValue(x)).ToList();
for (int index = inputNumbers.Count - 1; index > 0; index--)
{
if (inputNumbers[index] > inputNumbers[index - 1])
{
var r = inputNumbers.GetRange(index, inputNumbers.Count - index);
var l = inputNumbers.GetRange(0, index);
Swap(r, index, l);
l.AddRange(r.OrderBy(x => x));
return GetNumbericFromValueList(l);
}
}
return -1;
}
private static void Swap(List<int> r, int index, List<int> l)
{
var t = l[index - 1];
for (int i = r.Count - 1; i >= 0; i--)
{
if (r[i] > t)
{
l[index - 1] = r[i];
r[i] = t;
break;
}
}
}
private static int GetNumbericFromValueList(List<int> inputNumbers)
{
var count = inputNumbers.Count;
var result = inputNumbers.Select((x, index) => x * (Math.Pow(10, (count - index - 1)))).Sum();
return Convert.ToInt32(result);
}
}
最終的測試案例集：
[TestClass]
public class UnitTest1
{
private const int NoLargerNumber = -1;
[TestMethod]
public void Test_1_should_be_largestNumber()
{
var input = 1;
var expected = NoLargerNumber;
int actual = NextLargerNumber.Next(input);
Assert.AreEqual(expected, actual);
}
[TestMethod]
public void Test_9_should_be_largestNumber()
{
var input = 9;
var expected = NoLargerNumber;
int actual = NextLargerNumber.Next(input);
Assert.AreEqual(expected, actual);
}
[TestMethod]
public void Test_input_is_12_should_return_21()
{
var input = 12;
var expected = 21;
var actual = NextLargerNumber.Next(input);
Assert.AreEqual(expected, actual);
}
[TestMethod]
public void Test_input_is_21_should_be_largestNumber()
{
var input = 21;
var expected = NoLargerNumber;
var actual = NextLargerNumber.Next(input);
Assert.AreEqual(expected, actual);
}
[TestMethod]
public void Test_input_is_111_should_be_largestNumber()
{
var input = 111;
var expected = NoLargerNumber;
var actual = NextLargerNumber.Next(input);
Assert.AreEqual(expected, actual);
}
[TestMethod]
public void Test_input_is_531_should_be_largetNumber()
{
var input = 531;
var expected = NoLargerNumber;
var actual = NextLargerNumber.Next(input);
Assert.AreEqual(expected, actual);
}
[TestMethod]
public void Test_input_is_345_should_return_354()
{
var input = 345;
var expected = 354;
var actual = NextLargerNumber.Next(input);
Assert.AreEqual(expected, actual);
}
[TestMethod]
public void input_is_576_should_return_657()
{
var input = 576;
var expected = 657;
var actual = NextLargerNumber.Next(input);
Assert.AreEqual(expected, actual);
}
[TestMethod]
public void Test_11200_should_return_12001()
{
var input = 11200;
var expected = 12001;
var actual = NextLargerNumber.Next(input);
Assert.AreEqual(expected, actual);
}
[TestMethod]
public void Test_15963_should_return_16359()
{
var input = 15963;
var expected = 16359;
var actual = NextLargerNumber.Next(input);
Assert.AreEqual(expected, actual);
}
}
還有演算法的優化空間，但這個 kata 我想把展示的重點放在 TDD 的 baby step 與及時進行小範圍重構，有興趣的朋友可以自行再鑽研演算法，例如用
substring做也行。
結論
看到這麼長一篇文章，紅燈、綠燈、重構、重構、重構，到實現一個完整、乾淨的演算法 ，就知道為什麼這麼少人寫這麼詳細的 TDD 文章了。（笑）
【摘要重點】
- 從最簡單的測試案例下手。
- 每次要新增的失敗的測試案例，都應該基於目前的測試案例集（或是指目前 production code 還少哪一個關鍵處理）去延伸設計。一次只做一件最小但最重要的事，對工程師的人性來說相當具有挑戰。
- 重構一定要及時
【TDD 時必用的工具】
- 地表最強的 IDE：Visual Studio。
- Refactor 神兵：ReSharper。
- 即時進行 TDD 神兵：Alive。（已被微軟買走）
- Debug 測試案例執行過程神兵：OzCode。
