本文是[TDD磕算法] 我為什么嘗試用TDD解算法題系列的一篇贞言。
前情提要見(jiàn)[TDD磕算法] 排排隊(duì)徒欣，吃果果（一）失敗嘗試

題目

考慮到可能有人沒(méi)看前一篇，這里把題目再描述一次蜗字。

假定一隊(duì)人排成一列
每個(gè)人向前看，如果看到前面有1個(gè)比自己高脂新、或者和自己同樣高的人挪捕。就舉個(gè)牌子報(bào)數(shù)1。同理如果有3個(gè)争便，就報(bào)3级零。
如果把每個(gè)人的身高和報(bào)數(shù)列出來(lái)，就形成一個(gè)二元組的隊(duì)列滞乙，比如：
[(172, 0), (160, 1), (182, 0), (170, 2)]
就表示第一個(gè)人172cm奏纪，前面沒(méi)有高于或等于他高度的人；第二個(gè)160cm斩启，前面有一個(gè)序调；……

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

對(duì)于失敗的反思

在第一次嘗試，按部就班卻失敗了的經(jīng)歷后垄琐，我反思了一下這個(gè)題目究竟應(yīng)該怎么解決边酒。是不是真的不適合用TDD的方式做？
感覺(jué)在以下方面是可以改進(jìn)的狸窘。

• 在做的過(guò)程中墩朦，其實(shí)心里一直有種“這道題肯定有很漂亮的解法，說(shuō)不定試試就試到了”的心態(tài)翻擒。有這樣的心態(tài)氓涣，有意無(wú)意的會(huì)避免一些“傻”的寫(xiě)法牛哺，而且會(huì)在還沒(méi)有足夠用例支持的時(shí)候就急于重構(gòu)出較為一般化的代碼結(jié)構(gòu)春哨。然而并不真正匹配問(wèn)題荆隘，反倒給后續(xù)演進(jìn)造成了障礙。
• 因此首先應(yīng)該向著邏輯上而言“絕對(duì)可以解決”的方案進(jìn)行赴背，在完全解決前椰拒，不要被性能的擔(dān)憂(yōu)或者設(shè)計(jì)偏好所干擾。
• 另一個(gè)問(wèn)題是凰荚，在第一次做的時(shí)候其實(shí)沒(méi)有仔細(xì)想清楚測(cè)試順序燃观。雖然按一個(gè)人、二個(gè)人便瑟、三個(gè)人這樣的順序遞增窮盡用例看起來(lái)很合情合理缆毁，但是由此產(chǎn)生的測(cè)試卻未必與程序需要處理的子問(wèn)題同步的。

步驟也許是曲折的到涂，但是一定要通向目標(biāo)

第二次嘗試

全過(guò)程見(jiàn) http://cyber-dojo.org/review/show/8922CE128B?avatar=rabbit&was_tag=1&now_tag=1
第一個(gè)測(cè)試仍然是以一個(gè)人開(kāi)始脊框，和第一次完全一樣，就不詳細(xì)說(shuō)了践啄。

第二個(gè)測(cè)試

兩個(gè)人一隊(duì)浇雹，低的在前。
這次沒(méi)有像上次一樣選擇高的在前屿讽，因?yàn)檫@樣一次引入了兩個(gè)變化：隊(duì)列人數(shù)和排在前面人的邏輯昭灵。

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

實(shí)現(xiàn)代碼，按高度排序

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

第三個(gè)測(cè)試

兩人伐谈，高的在前烂完。引入了前面有一個(gè)人的邏輯。

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

實(shí)現(xiàn)代碼
這次學(xué)乖了诵棵，刻意先老老實(shí)實(shí)的寫(xiě)hardcode通過(guò)抠蚣。

  let sortedByHeight = people.sort( (p1,p2) => p1[HEIGHT] - p2[HEIGHT] );
  if (deepEqual([[3,1],[4,0]], sortedByHeight)) {
    return [[4,0],[3,1]];
  }

第三個(gè)測(cè)試的重構(gòu)

然后開(kāi)始考慮這個(gè)4在3前面的邏輯是怎么來(lái)的，可以假定有個(gè)函數(shù)能給出每個(gè)人應(yīng)有的位置非春，那么就按它返回的index插入數(shù)組即可柱徙。

for(let p of sortedByHeight) {
  result[peoplesBefore(p, sortedByHeight)] = p;
}

這樣，就把硬編碼挪入了新的函數(shù)里奇昙。[3,1],[4,0]的時(shí)候特殊處理护侮，否則返回在按高度排序數(shù)組里的index。

function peoplesBefore(people, peoples) {
  if (deepEqual([[3,1],[4,0]], peoples)) {
    if (deepEqual([4,0], people)) {
      return 0;
    }
    if (deepEqual([3,1], people)) {
      return 1;
    }
  }

  for (let i in peoples) {
    if (deepEqual(peoples[i], people)) {
      return i;
    }
  }
}

進(jìn)一步分解硬編碼储耐，把[3,1]的情況留在硬編碼里特殊處理羊初。先想辦法統(tǒng)一前面沒(méi)有更高的人的情況。
再次假定一個(gè)函數(shù)，它可以數(shù)出前面的人數(shù)长赞，比如對(duì)于[4,0]而言晦攒，在[3,0],[4,0]中返回1，而在[3,1],[4,0]中時(shí)返回0得哆。

  if (deepEqual([[3,1],[4,0]], peoples)) {
    if (deepEqual([3,1], people)) {
      return 1;
    }
  }
  if (people[PEOPLE_BEFORE] === 0) {
    return shorterPeoplesWhoHasNoTallerBefore(people, peoples);
  }
...
function shorterPeoplesWhoHasNoTallerBefore(people, peoples) {
  let result = 0;
  for (let p of peoples) {
    if (p[HEIGHT] < people[HEIGHT] && p[PEOPLE_BEFORE] === 0) {
      result += 1;
    }
  }
  return result;
}

這時(shí)候發(fā)現(xiàn)[3,1]的硬編碼可以簡(jiǎn)化為前面更高人數(shù)為1脯颜。同時(shí)，既然已經(jīng)每次數(shù)一遍更矮的人數(shù)了贩据，前面的排序就沒(méi)有必要了栋操。

function reconstructQueue(peoples) {
  let result = [];
  for(let p of peoples) {
    result[peoplesBefore(p, peoples)] = p;
  }
  return result;
}
 
function peoplesBefore(people, peoples) {
  if (people[PEOPLE_BEFORE] === 0) {
    return shorterPeoplesWhoHasNoTallerBefore(people, peoples);
  }
  if (people[PEOPLE_BEFORE] === 1) {
    return 1;
  }
}

經(jīng)過(guò)一大段重構(gòu)到這個(gè)點(diǎn)時(shí)，感覺(jué)硬編碼基本上消除了饱亮。添加后續(xù)測(cè)試矾芙。

第四個(gè)測(cè)試

與第一次不同，我沒(méi)有按照人數(shù)遞增窮舉所有可能的思路近上，而是根據(jù)當(dāng)前代碼邏輯剔宪。進(jìn)一步擴(kuò)充有PEOPLE_BEFORE === 1的邏輯分支。

三個(gè)人壹无，中等高度的人排在最后葱绒。這樣因?yàn)樗奈恢貌辉偈?所以會(huì)失敗。

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

實(shí)現(xiàn)代碼
發(fā)現(xiàn)可以稍作調(diào)整就快速通過(guò)了斗锭。
把原來(lái)硬編碼的位置1哈街，改為如果沒(méi)有更高人在前時(shí)應(yīng)在的位置加1。
也就是說(shuō)本來(lái)3排在2后面拒迅，現(xiàn)在再后挪一位。

  if (people[PEOPLE_BEFORE] === 1) {
    return shorterPeoplesWhoHasNoTallerBefore(people, peoples) + 1;
  }

第五個(gè)測(cè)試

繼續(xù)擴(kuò)充前面有一個(gè)人的邏輯分支她倘。

三個(gè)人最低的在中間璧微。

reconstruct_should_be([[3,1],[8,0],[5,0]], [[5,0],[3,1],[8,0]]);

這個(gè)用例初看起來(lái)和第三個(gè)測(cè)試類(lèi)似，但是失敗了硬梁。原因是數(shù)位置的時(shí)候是只算[x,0]的個(gè)數(shù)的前硫。這樣8和3都會(huì)認(rèn)為是在位置1的，結(jié)果排出來(lái)的數(shù)組只有兩個(gè)元素荧止。
實(shí)現(xiàn)代碼
發(fā)現(xiàn)實(shí)際上是要把[x,1]這樣的元素插入已經(jīng)排好的[x,0]隊(duì)列里合適的位置屹电。改為如下實(shí)現(xiàn)。
先用原有來(lái)的邏輯處理前面沒(méi)有更高的人跃巡，也就是[x,0]的情況危号。再把[x,1]插入結(jié)果隊(duì)列

function reconstructQueue(peoples) {
  let result = [];
  for(let p of peoples) {
    if (p[PEOPLE_BEFORE] === 0) {
      result[shorterPeoplesWhoHasNoTallerBefore(p, peoples)] = p;
    }
  }
  for (let p of peoples) {
    if (p[PEOPLE_BEFORE] === 1) {
      insertAfterFirstNoShorter(p, result);
    }
  }
  return result;
}

insertAfterFirstNoShorter的實(shí)現(xiàn)是找到第一個(gè)不低于當(dāng)前需要插入高度的人，在他后面加入新的人素邪。
比如[5,0],[8,0],需要加入[3,1]外莲，數(shù)到5是高于3的，把3加入5之后的位置。

function insertAfterFirstNoShorter(people, peoples) {
  for (let i in peoples) {
    if (peoples[i][HEIGHT] >= people[HEIGHT]) {
      peoples.splice(i+1,0,people);
      return;
    }
  }
}

第六個(gè)測(cè)試

[x,1]的邏輯還沒(méi)有完備偷线，增加用例有兩個(gè)[x,1]的情況磨确。

reconstruct_should_be([[3,1],[5,1],[8,0]], [[8,0],[3,1],[5,1]]);

結(jié)果不是預(yù)期的8,3,5，而是8,5,3声邦。因?yàn)槭紫?加在8后面乏奥，之后5也是加入8隨后的位置。順序反了亥曹。
實(shí)現(xiàn)代碼邓了，修改insertAfterFirstNoShorter，把加入第一個(gè)更高的人之后改為第二個(gè)更高的人之前或者隊(duì)尾歇式。名字也相應(yīng)的修改為insertBefore2ndNoShorter驶悟。

function insertBefore2ndNoShorter(people, peoples) {
  let afterFirst = false;
  for (let i in peoples) {
    if (peoples[i][HEIGHT] >= people[HEIGHT]) {
      if (afterFirst) {
        peoples.splice(i,0,people);
        return;
      }
      afterFirst = true;
    }
  }
  peoples.push(people);
}

第六個(gè)測(cè)試的重構(gòu)

又補(bǔ)充了幾個(gè)[x,1]測(cè)試都成功了，我確信代碼已經(jīng)完全處理了有一個(gè)人在前的邏輯材失。開(kāi)始重構(gòu)痕鳍。重構(gòu)的出發(fā)點(diǎn)是覺(jué)得[x,0]和[x,1]的兩段邏輯是可以統(tǒng)一的。
首先修改插入[x,0]的為函數(shù)為insertBefore1stNoShorter龙巨，找到第一個(gè)更高的人笼呆，加在他前面。

  peoples = peoples.sort( (p1, p2) => p1[PEOPLE_BEFORE] - p2[PEOPLE_BEFORE]);
  ...
  for(let p of peoples) {
    if (p[PEOPLE_BEFORE] === 0) {
      insertBefore1stNoShorter(p, result);
    }
    if (p[PEOPLE_BEFORE] === 1) {
      insertBefore2ndNoShorter(p, result);
    }
  }

顯而易見(jiàn)兩個(gè)函數(shù)的區(qū)別只是數(shù)人頭的個(gè)數(shù)旨别。
進(jìn)一步重構(gòu)诗赌，把人數(shù)作為參數(shù)傳入。

  for(let p of peoples) {
    insertBeforeNTimesNoShorter(p, result, p[PEOPLE_BEFORE]+1);
  }

第七個(gè)測(cè)試

增加兩個(gè)人高度相等的用例

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

直接通過(guò)了秸弛，因?yàn)榍懊鎸?xiě)代碼的時(shí)候其實(shí)已經(jīng)加入了相等的判斷铭若。可以說(shuō)這個(gè)測(cè)試加的太晚了递览，或者說(shuō)是實(shí)現(xiàn)代碼寫(xiě)的過(guò)多叼屠。
這個(gè)測(cè)試算是補(bǔ)救，確保提前寫(xiě)的實(shí)現(xiàn)是正確的绞铃。

第八個(gè)測(cè)試

引入有兩個(gè)人在前面的用例镜雨。

reconstruct_should_be([[6,0],[5,2],[3,2],[8,0]], 
      [[6,0],[8,0],[3,2],[5,2]]);

出人意料的是直接過(guò)了，原因是[x,0],[x,1]或[x,2]已經(jīng)在前面重構(gòu)中一般化了儿捧。
仔細(xì)想想荚坞，并增加了幾個(gè)測(cè)試后，發(fā)現(xiàn)原來(lái)已經(jīng)做完了菲盾。
成功好像比上次的失敗來(lái)的更加突然嘛颓影。

體會(huì)

• 這次成功做法的最大不同，是拋開(kāi)了對(duì)性能的擔(dān)心懒鉴。最終做出的結(jié)果性能也確實(shí)是相當(dāng)?shù)牟畈t空。但是至少做完了?/li>
• 另一個(gè)重大區(qū)別是測(cè)試順序。很明顯每一步引起的修改都集中在程序的一部分中，這表明問(wèn)題被分解開(kāi)了咆畏。
• 寫(xiě)這篇回顧時(shí)才發(fā)現(xiàn)的這次練習(xí)一個(gè)不尋常的地方南捂，在于大段的重構(gòu)。一般大的重構(gòu)是前面欠債引起的旧找。而這次卻不是這個(gè)情況溺健。很多代碼結(jié)構(gòu)是在消除硬編碼的時(shí)候經(jīng)過(guò)很多步驟產(chǎn)生出來(lái)的，同時(shí)外部行為并無(wú)變化钮蛛。這究竟是小步帶來(lái)的自然演進(jìn)鞭缭，還是因?yàn)槲医?jīng)過(guò)上次失敗后腦子里已經(jīng)預(yù)想了一些設(shè)計(jì)。目前我還不是特別確定魏颓。

如前面所言岭辣，這個(gè)解法是非常低效的，實(shí)在不能算是個(gè)算法解答甸饱。
下一篇將會(huì)回顧我探索更好的解法的過(guò)程沦童。