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
題目解釋：給一個(gè)正整數(shù) input，回傳由相同數(shù)字所組成的下一個(gè)更大的數(shù)字。
本文要透過 TDD 的方式炊琉，來解釋我的思路跟程式碼演進(jìn)過程打月。
嚴(yán)格來說郎逃，這個(gè)需求用「窮舉法+排序」找下一個(gè)更大的值葱色，應(yīng)該是最快廊营、最直覺的衰齐，但這樣比較感受不到 TDD 的過程任斋。所以這個(gè)需求，我們將用特定的演算法來求出下一個(gè)更大的數(shù)字耻涛。
第一個(gè)紅燈废酷，input = 1, return -1; 因?yàn)?1 已經(jīng)是最大的數(shù)字
測試案例用意：先透過第一個(gè)測試案例產(chǎn)生對應(yīng)產(chǎn)品程式碼的骨架。
測試程式碼如下：
[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);
}
}
產(chǎn)生出來的產(chǎn)品程式碼如下：
public static class NextLargerNumber
{
public static int Next(int input)
{
throw new NotImplementedException();
}
}
接著用最簡單的方式通過測試抹缕，直接 return -1;
產(chǎn)品程式碼如下：
public static int Next(int input)
{
return -1;
}
新增一個(gè)測試案例：input = 12, should return 21;
這個(gè)測試案例用意澈蟆，需先處理 input 整數(shù)要透過 char 取得各位的數(shù)字， swap 卓研，以及回傳時(shí)要再把 char 組成十進(jìn)位的數(shù)字趴俘。
測試程式如下：
[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);
}
產(chǎn)品程式碼設(shè)計(jì)概念：
- 先將 input 轉(zhuǎn)成 char array, 再轉(zhuǎn)成
List<int>以便後續(xù)處理。 - 右邊的數(shù)字與左邊的數(shù)字 swap 奏赘，將 swap 完的
List<int>透過Select()+Math.Pow()轉(zhuǎn)換成十進(jìn)位數(shù)字寥闪。 - 原本
return -1;的邏輯，在這先定義為如果 input 產(chǎn)生的List<int>的Count只有 1 時(shí)磨淌，則return -1;（等到別的測試案例因此失敗或重構(gòu)時(shí)疲憋，再來調(diào)整。）
注意：我刻意略過了一個(gè)商業(yè)邏輯梁只，應(yīng)該是當(dāng)右邊數(shù)字比左邊大缚柳，才進(jìn)行 swap 的動(dòng)作。這一段商業(yè)邏輯敛纲，我決定用下一個(gè)測試案例 input = 21 來補(bǔ)喂击。
產(chǎn)品程式碼如下：
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);
}
新增下一個(gè)測試案例，input=21, should return -1;
這裡有兩種思維淤翔，一種是把 21 當(dāng)作最大值得回傳 -1 來做翰绊，合併進(jìn)去 return -1 的判斷式。另一種則是併入 swap 的判斷式。在這监嗜，我決定採後者谐檀。因?yàn)槲移谕鹊戎貥?gòu)時(shí)，可以把 return -1 的邏輯也進(jìn)行重構(gòu)裁奇。
測試案例如下：
[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);
}
產(chǎn)品程式碼設(shè)計(jì)概念桐猬，只有當(dāng)右邊的數(shù)字 > 左邊的數(shù)字，才進(jìn)行 swap刽肠。
如果最後處理完的結(jié)果溃肪，與傳入的 input 相同，代表已為最大值音五，應(yīng)回傳 -1 惫撰。
產(chǎn)品程式碼如下：
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;
}
重構(gòu)
我想先消掉
inputNumbers[1]跟inputNumbers[0]magic number 的壞味道，所以加上 for loop 以 index 取代 1 與 0躺涝。
產(chǎn)品程式碼如下：
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;
}
重構(gòu)
我想消掉第一個(gè)
return -1的判斷式厨钻，因?yàn)樽钺岬?return 已經(jīng)有判斷，如果處理完的結(jié)果與傳入的 input 相同時(shí)坚嗜，回傳 -1夯膀。這一段邏輯是涵蓋了我們 input = 1 的測試案例。
產(chǎn)品程式碼如下：
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;
}
重構(gòu)
當(dāng)巡覽
inputNumbers有發(fā)生 swap 動(dòng)作時(shí)苍蔬，代表與原本的 input 不一樣了诱建，這邊就直接回傳 swap 完的結(jié)果值。（因?yàn)槟壳皽y試案例只有兩位數(shù)银室，所以可以直接回傳）反之涂佃，如果巡覽過程中，左邊全都比右邊大蜈敢，沒發(fā)生任何 swap 動(dòng)作，代表本身就是最大值汽抚，則 return -1;
產(chǎn)品程式碼如下：
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;
}
新增一個(gè)預(yù)計(jì)會(huì)通過的測試案例：input = 345, should return 354;
這個(gè)測試案例會(huì)通過的原因是抓狭，第一次的 5 與 4 交換後，剛好是下一個(gè)最大值造烁，但 input 已經(jīng)來到三位數(shù)了否过。
測試案例如下：
[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);
}
新增一個(gè)演算法最關(guān)鍵的測試案例：input = 576, should return 657;
這個(gè)測試案例的用意在於，修正 swap 與處理方式惭蟋。雖然 input 仍是三位數(shù)苗桂，但如果照原本的產(chǎn)品程式碼邏輯，最後會(huì)回傳是 756告组，因?yàn)榈谝惠?576 右邊的的 6 比左邊的 7 小煤伟，不進(jìn)行 swap。第二輪右邊的 7 比左邊的 5 大，swap 後的結(jié)果是 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);
}
產(chǎn)品程式碼演算法解釋如下：
- 從 input 最右邊的位數(shù)往左邊一位比較围辙，如果右邊比左邊小，則往下一位 shift 繼續(xù)比較放案。以這例子來說姚建，就是 6 比 7 小，shift 下一位換 7 跟 5 比較吱殉。
- 當(dāng)右邊的數(shù)字掸冤，比左邊大時(shí)，我們先把原本的 input 以 L,T,R 來表示友雳。以這例子來說贩虾，右邊的 7 比左邊的 5 大，要進(jìn)行 swap 的處理沥阱。這時(shí) T 就是 5缎罢，R 就是 {7, 6}，L 就是空集合考杉。
- 右邊待 swap 的數(shù)字策精，從 R 的集合中，找出大於 T 的最小值崇棠。以這例子來說咽袜，就是從 {7,6} 找到比 5 大的最小值為 6。
- 將找到右邊待 swap 的數(shù)字枕稀，與 T 交換询刹。
- 針對新的 R 做升冪處理，才能確保是最小值的組合萎坷。
- 最後的結(jié)果為 swap 完畢後的 L + T + R凹联。
註：實(shí)際的程式碼為了好寫，L 的集合直接先 include T 的值哆档，比較好進(jìn)行 swap蔽挠。
產(chǎn)品程式碼如下：
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; //找到第一個(gè)可以swap的，就是比t大的最小值
}
}
l.AddRange(r.OrderBy(x => x));
return GetNumbericFromValueList(l);
}
}
return -1;
}
重構(gòu)
將
rightFlag與leftFlag變成 inline variable, 消除不必要的變數(shù)瓜浸。（如果你有用 ReSharper, 這個(gè)動(dòng)作用熱鍵就可以執(zhí)行）
程式碼如下：
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; //找到第一個(gè)可以swap的澳淑，就是比t大的最小值
}
}
l.AddRange(r.OrderBy(x => x));
return GetNumbericFromValueList(l);
}
}
return -1;
}
重構(gòu)
將
t變成 inline variable，消除不必要的變數(shù)插佛。移除註解杠巡。
產(chǎn)品程式碼如下：
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;
}
重構(gòu)
將
Skip().Take().ToList()的部分，改用List.GetRange()取代雇寇，原因是來源是 List, 最後也要 List氢拥，不如直接用GetRange()避免不必要的巡覽蚌铜。
重構(gòu)完程式碼如下：
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;
}
重構(gòu)
將 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;
}
}
}
重構(gòu)
inputNumbers[index - 1]提取變數(shù)到 for loop 外面兄一，且改用 L 集合取代厘线。因?yàn)?code>inputNumbers[index-1] 與L[index-1]等義。接著消去未使用到的參數(shù)
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;
}
}
}
最終的產(chǎn)品程式碼
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);
}
}
還有演算法的優(yōu)化空間造壮，但這個(gè) kata 我想把展示的重點(diǎn)放在 TDD 的 baby step 與及時(shí)進(jìn)行小範(fàn)圍重構(gòu)，有興趣的朋友可以自行再鑽研演算法骂束，例如用
substring做也行耳璧。
結(jié)論
看到這麼長一篇文章，紅燈展箱、綠燈旨枯、重構(gòu)、重構(gòu)混驰、重構(gòu)攀隔，到實(shí)現(xiàn)一個(gè)完整、乾淨(jìng)的演算法 栖榨，就知道為什麼這麼少人寫這麼詳細(xì)的 TDD 文章了昆汹。（笑）
【摘要重點(diǎn)】
- 從最簡單的測試案例下手。
- 每次要新增的失敗的測試案例婴栽，都應(yīng)該基於目前的測試案例集（或是指目前 production code 還少哪一個(gè)關(guān)鍵處理）去延伸設(shè)計(jì)满粗。一次只做一件最小但最重要的事，對工程師的人性來說相當(dāng)具有挑戰(zhàn)愚争。
- 重構(gòu)一定要及時(shí)
【TDD 時(shí)必用的工具】
- 地表最強(qiáng)的 IDE：Visual Studio映皆。
- Refactor 神兵：ReSharper。
- 即時(shí)進(jìn)行 TDD 神兵：Alive轰枝。（已被微軟買走）
- Debug 測試案例執(zhí)行過程神兵：OzCode捅彻。
