[TDD]Find the Next Bigger Number from Codewars

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

題目解釋：給一個正整數(shù) input，回傳由相同數(shù)字所組成的下一個更大的數(shù)字。

本文要透過 TDD 的方式，來解釋我的思路跟程式碼演進過程。

嚴格來說，這個需求用「窮舉法+排序」找下一個更大的值，應(yīng)該是最快、最直覺的，但這樣比較感受不到 TDD 的過程。所以這個需求，我們將用特定的演算法來求出下一個更大的數(shù)字。

第一個紅燈，input = 1, return -1; 因為 1 已經(jīng)是最大的數(shù)字

測試案例用意：先透過第一個測試案例產(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;            
        }

新增一個測試案例：input = 12, should return 21;

這個測試案例用意，需先處理 input 整數(shù)要透過 char 取得各位的數(shù)字， swap ，以及回傳時要再把 char 組成十進位的數(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è)計概念：

  1. 先將 input 轉(zhuǎn)成 char array, 再轉(zhuǎn)成 List<int> 以便後續(xù)處理。
  2. 右邊的數(shù)字與左邊的數(shù)字 swap ，將 swap 完的 List<int> 透過 Select() + Math.Pow() 轉(zhuǎn)換成十進位數(shù)字。
  3. 原本 return -1; 的邏輯，在這先定義為如果 input 產(chǎn)生的 List<int> 的 Count 只有 1 時，則 return -1;（等到別的測試案例因此失敗或重構(gòu)時，再來調(diào)整。）

注意：我刻意略過了一個商業(yè)邏輯，應(yīng)該是當右邊數(shù)字比左邊大，才進行 swap 的動作。這一段商業(yè)邏輯，我決定用下一個測試案例 input = 21 來補。

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

新增下一個測試案例，input=21, should return -1;

這裡有兩種思維，一種是把 21 當作最大值得回傳 -1 來做，合併進去 return -1 的判斷式。另一種則是併入 swap 的判斷式。在這，我決定採後者。因為我期望等等重構(gòu)時，可以把 return -1 的邏輯也進行重構(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è)計概念，只有當右邊的數(shù)字 > 左邊的數(shù)字，才進行 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)

我想消掉第一個 return -1 的判斷式，因為最後的 return 已經(jīng)有判斷，如果處理完的結(jié)果與傳入的 input 相同時，回傳 -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)

當巡覽 inputNumbers 有發(fā)生 swap 動作時，代表與原本的 input 不一樣了，這邊就直接回傳 swap 完的結(jié)果值。（因為目前測試案例只有兩位數(shù)，所以可以直接回傳）

反之，如果巡覽過程中，左邊全都比右邊大，沒發(fā)生任何 swap 動作，代表本身就是最大值，則 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;
        }

新增一個預(yù)計會通過的測試案例：input = 345, should return 354;

這個測試案例會通過的原因是，第一次的 5 與 4 交換後，剛好是下一個最大值，但 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);
        }

新增一個演算法最關(guān)鍵的測試案例：input = 576, should return 657;

這個測試案例的用意在於，修正 swap 與處理方式。雖然 input 仍是三位數(shù)，但如果照原本的產(chǎn)品程式碼邏輯，最後會回傳是 756，因為第一輪 576 右邊的的 6 比左邊的 7 小，不進行 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)品程式碼演算法解釋如下：

  1. 從 input 最右邊的位數(shù)往左邊一位比較，如果右邊比左邊小，則往下一位 shift 繼續(xù)比較。以這例子來說，就是 6 比 7 小，shift 下一位換 7 跟 5 比較。
  2. 當右邊的數(shù)字，比左邊大時，我們先把原本的 input 以 L,T,R 來表示。以這例子來說，右邊的 7 比左邊的 5 大，要進行 swap 的處理。這時 T 就是 5，R 就是 {7, 6}，L 就是空集合。
  3. 右邊待 swap 的數(shù)字，從 R 的集合中，找出大於 T 的最小值。以這例子來說，就是從 {7,6} 找到比 5 大的最小值為 6。
  4. 將找到右邊待 swap 的數(shù)字，與 T 交換。
  5. 針對新的 R 做升冪處理，才能確保是最小值的組合。
  6. 最後的結(jié)果為 swap 完畢後的 L + T + R。

註：實際的程式碼為了好寫，L 的集合直接先 include T 的值，比較好進行 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; //找到第一個可以swap的，就是比t大的最小值
                        }
                    }

                    l.AddRange(r.OrderBy(x => x));

                    return GetNumbericFromValueList(l);
                }
            }

            return -1;
        }

重構(gòu)

將 rightFlag 與 leftFlag 變成 inline variable, 消除不必要的變數(shù)。（如果你有用 ReSharper, 這個動作用熱鍵就可以執(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; //找到第一個可以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 集合取代。因為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)化空間，但這個 kata 我想把展示的重點放在 TDD 的 baby step 與及時進行小範圍重構(gòu)，有興趣的朋友可以自行再鑽研演算法，例如用 substring 做也行。

結(jié)論

看到這麼長一篇文章，紅燈、綠燈、重構(gòu)、重構(gòu)、重構(gòu)，到實現(xiàn)一個完整、乾淨的演算法 ，就知道為什麼這麼少人寫這麼詳細的 TDD 文章了。（笑）

【摘要重點】

  • 從最簡單的測試案例下手。
  • 每次要新增的失敗的測試案例，都應(yīng)該基於目前的測試案例集（或是指目前 production code 還少哪一個關(guān)鍵處理）去延伸設(shè)計。一次只做一件最小但最重要的事，對工程師的人性來說相當具有挑戰(zhàn)。
  • 重構(gòu)一定要及時

【TDD 時必用的工具】

  • 地表最強的 IDE：Visual Studio。
  • Refactor 神兵：ReSharper。
  • 即時進行 TDD 神兵：Alive。（已被微軟買走）
  • Debug 測試案例執(zhí)行過程神兵：OzCode。

我的 Github commit history

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

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

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