本文是[TDD磕算法] 我為什么嘗試用TDD解算法題系列的一篇。

題目

原諒我標(biāo)題黨了，其實是這次解的題目很難一言兩語概括出來。這里我嘗試解釋解釋。

假定一隊人排成一列
每個人向前看，如果看到前面有1個比自己高、或者和自己同樣高的人。就舉個牌子報數(shù)1。同理如果有3個，就報3。
如果把每個人的身高和報數(shù)列出來，就形成一個二元組的隊列，比如：
[(172, 0), (160, 1), (182, 0), (170, 2)]
就表示第一個人172cm，前面沒有高于或等于他高度的人；第二個160cm，前面有一個；……

這道題目是，給定打亂順序的一個序列，把他們排回應(yīng)有的順序。
比如：
輸入：[ (7,2), (4,3), (8,0), (7,1), (6,0)]
輸出：[ (6,0), (8,0), (7,1), (4,3), (7,2)]

這道題可以在刷題網(wǎng)站Leetcode上看到，編號406
https://leetcode.com/problems/queue-reconstruction-by-height

初步分析

初看起來題目非常適合TDD解決。排序的邏輯似乎有點復(fù)雜，但是應(yīng)該比較容易一步步從簡單到復(fù)雜演進(jìn)。比如先從最簡單的情況開始，隊列里只有一個人，可以直接返回。兩個人的話有兩種情況……
另外這道題目不禁讓我想起了Combined Number這道Kata。同樣也是實現(xiàn)排序，排序的邏輯有些繞。最終可以很漂亮的把問題的幾個方面分離開解決掉。

關(guān)于Combined Number，可以在這里看到更詳細(xì)的練習(xí)和討論。
http://cyber-dojo.org/kata/edit/FCDDF1?avatar=zebra
https://groups.google.com/forum/#!topic/agileshanghai/d6cy6tCXHA8

失敗嘗試

大致想想之后就開始信心滿滿的TDD起來了，果不其然失敗了……
全過程見 http://cyber-dojo.org/review/show/8922CE128B?avatar=ray&was_tag=1&now_tag=1
大體歷程如下

第一個測試

只有一個人的話，必然前面沒有更高的人。

reconstruct_should_be([[3,0]], [[3,0]]);

reconstruct_should_be的第一個參數(shù)是輸入，第二個是預(yù)期的輸出。

實現(xiàn)代碼，輸入什么就返回什么。

function reconstrutQueue(people) {
  return people;
}

第二個測試

兩個人，有一個前面有更高的人，另一個沒有。

reconstruct_should_be([[2,1],[3,0]], [[3,0],[2,1]]);

實現(xiàn)代碼，按前面人數(shù)排序。

function reconstructQueue(people) {
  return people.sort( (p1, p2) => p1[1] -p2[1]);
}

稍作重構(gòu)，抽取常量

return people.sort( (p1, p2) => p1[PRE] -p2[PRE]);

第三個測試

兩個人，前面都沒有更高的人。也就是說是低的在前。

reconstruct_should_be([[2,0],[3,0]], [[2,0],[3,0]]);

直接通過了。

第四個測試

三個人，從低到高排。

reconstruct_should_be([[2,0],[3,0],[1,0]], [[1,0],[2,0],[3,0]]);

實現(xiàn)代碼，如果前面人數(shù)一樣，按高度排序。

  return people.sort( (p1, p2) => {
    if (p1[PRE] === p2[PRE]) return p1[0] - p2[0]
    return p1[PRE] -p2[PRE]
  });

第五個測試

三個人，中等高度的排在最高的后面。

reconstruct_should_be([[2,1],[3,0],[1,0]], [[1,0],[3,0],[2,1]]);

又一次直接通過了。

第六個測試

三個人，最矮的排在中間。

reconstruct_should_be([[2,0],[3,0],[1,1]], [[2,0],[1,1],[3,0]]);

實現(xiàn)代碼，排序方式改為先按高度排列，相同高度的按前面人數(shù)排列。這樣三個人就會排成[1,1],[2,0],[3,0]。

  let result = people.sort( (p1, p2) => {
    if (p1[VAL] === p2[VAL]) { 
      return p1[PRE] - p2[PRE];
    }
    return p1[VAL] - p2[VAL];
  });

在排序之后增加一個調(diào)整順序的過程。硬編碼快速通過，把前面有1個人的項目向后挪一位。也就是[1,1]挪到[2,0]后面。

  for (let i=0; i<result.length; i++) {
    if (result[i][PRE] === 1) {
      let temp = result[i];
      result[i] = result[i+1];
      result[i+1] = temp;
      i++;
    }
  }

第七個測試

三個人，最矮的排在最后。

reconstruct_should_be([[2,0],[3,0],[1,2]], [[2,0],[3,0],[1,2]]);

實現(xiàn)代碼，增加第二個硬編碼分支，處理有2個人在前面的情況。

  for (let i=0; i<result.length; i++) {
    if (result[i][PRE] === 1) {
    ...
    }
    if (result[i][PRE] === 2) {
      let temp = result.splice(i,1)[0];
      result.splice(i+2,0,temp);
      i+=2;
    }
  }

重構(gòu)，把兩個分支改寫成相同的邏輯。

    if (result[i][PRE] === 1) {
      let temp = result.splice(i,1)[0];
      result.splice(i+1,0,temp);
      i+=1;
    }
    if (result[i][PRE] === 2) {
      let temp = result.splice(i,1)[0];
      result.splice(i+2,0,temp);
      i+=2;
    }

重構(gòu)，統(tǒng)一為一個分支。

    if (sortedByVal[i][PRE] > 0) {
      let nLater = sortedByVal[i][PRE];
      let temp = sortedByVal.splice(i,1)[0];
      sortedByVal.splice(i+nLater,0,temp);
      i+=nLater;
    }

第八個測試

最高的人在前面，后面的兩個按高度排。

reconstruct_should_be([[2,1],[3,0],[1,1]], [[3,0],[1,1],[2,1]]);

實現(xiàn)代碼，呃…… 就這么掉坑里了。
首先是沒有很容易的快速通過的思路。
反復(fù)幾次后發(fā)現(xiàn)在排好的數(shù)組里挪動的方式，把一個人向后挪了之后，換來的人可能也需要后移。
所以決定不在原來的數(shù)組里挪動位置，而是全部插入一個新數(shù)組。插入時比較新數(shù)組里的位置和這個人前面人的個數(shù)，直到所有的人都插入新數(shù)組為止。

function reorder(sortedByVal) {
  let result = [];
  let length = sortedByVal.length;
  for (let i=0; i<length; i++) {
    for (let j=0; j<sortedByVal.length; j++) {
      if (sortedByVal[j][PRE] <= i) {
        result.push(sortedByVal[j]);
        sortedByVal.splice(j,1);
        break;
      }
    }
  }
  return result;
}

但是發(fā)現(xiàn)這時候[ [ 1, 0 ], [ 3, 0 ], [ 2, 1 ] ]這個測試又失敗了。
經(jīng)過一段思索無法繼續(xù)后，我覺得就算通過苦思冥想把這個題解出來，也已經(jīng)和TDD無關(guān)了。就此停止了這次練習(xí)。

感想

從來沒有嘗試過仔細(xì)描述一段失敗的過程。不知道你讀到這里是和感受？

• “簡直是浪費時間嘛”？
• “早就知道這樣做不靠譜”？
• “看起來還有救啊，怎么就失敗了”？
• “太菜了，讓我來”？

這里說說掉坑的心得。怎么知道自己掉坑了。

• 最終爬不出來的點很容易判定。突然發(fā)現(xiàn)自己思考了10分鐘，還是沒有寫代碼。
• 顧此失彼，寫了一段代碼快速通過當(dāng)前測試，結(jié)果前面的測試掛了。
• 感覺前面重構(gòu)出的結(jié)構(gòu)在阻礙新的用例快速通過。
• 一個早期征兆是想不清楚下一個測試是什么？比如這個過程中兩次直接通過的測試，都代表了對當(dāng)前程序的行為沒有理解清楚。
• 測試想不清楚的背后是沒有想出逐步分解問題的思路，進(jìn)而加入測試的順序可能不是適宜代碼演進(jìn)。導(dǎo)致重構(gòu)時對實現(xiàn)進(jìn)行重大調(diào)整。比如第六步和最后一步。

下一篇文章會總結(jié)我在反思之后重新解決的過程，敬請期待。