[TDD]Find the Next Bigger Number

作者: 就是91 | 来源:发表于2017-02-16 10:57 被阅读116次

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。

我的 Github commit history

[TDD]Find the Next Bigger Number

第一個紅燈，input = 1, return -1; 因為 1 已經是最大的數字

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

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

重構

重構

重構

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

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

重構

重構

重構

重構

重構

最終的產品程式碼

最終的測試案例集：

結論

【摘要重點】

【TDD 時必用的工具】

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

TDD

C#

TDD(测试驱动开发)