[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

題目解釋:給一個正整數 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);
        }

產品程式碼設計概念:

  1. 先將 input 轉成 char array, 再轉成 List<int> 以便後續處理。
  2. 右邊的數字與左邊的數字 swap ,將 swap 完的 List<int> 透過 Select() + Math.Pow() 轉換成十進位數字。
  3. 原本 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);
        }

產品程式碼演算法解釋如下:

  1. 從 input 最右邊的位數往左邊一位比較,如果右邊比左邊小,則往下一位 shift 繼續比較。以這例子來說,就是 6 比 7 小,shift 下一位換 7 跟 5 比較。
  2. 當右邊的數字,比左邊大時,我們先把原本的 input 以 L,T,R 來表示。以這例子來說,右邊的 7 比左邊的 5 大,要進行 swap 的處理。這時 T 就是 5,R 就是 {7, 6},L 就是空集合
  3. 右邊待 swap 的數字,從 R 的集合中,找出大於 T 的最小值。以這例子來說,就是從 {7,6} 找到比 5 大的最小值為 6
  4. 將找到右邊待 swap 的數字,與 T 交換。
  5. 針對新的  R 做升冪處理,才能確保是最小值的組合。
  6. 最後的結果為 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 時必用的工具】

  1. 地表最強的 IDE:Visual Studio。
  2. Refactor 神兵:ReSharper。
  3. 即時進行 TDD 神兵:Alive。(VS2017內建了)
  4. Debug 測試案例執行過程神兵:OzCode。

 

對敏捷開發有興趣的朋友,可以參考我的粉絲專頁:91敏捷開發之路

對 TDD 課程有興趣的朋友,課程內容、大綱與學員心得,可以參考 skilltree 的公開課程:自動測試與 TDD 實務開發

若需要聯絡我,可以透過粉絲專頁私訊或是側欄的關於我。