var story = function () {
  var content = '从前有座山，山里有座庙，庙里有个老和尚他在讲故事，他说：'
  return content + story()
}

var story = function (times) {
  if (times > 0) {
    var content = '从前有座山，山里有座庙，庙里有个老和尚他在讲故事，他说：'
    return content + story(--times)
  } else {
    return '(未完待续...)'
  }
}

// 得到 array 的第一个元素
// head([1,2,3,4,5]) 
// => 1
var head = function (array)  {
  return array[0]
}

// 得到 array 除第一个元素外的其他元素
// tail([1,2,3,4,5])
// => [2,3,4,5]
var tail = function (array) {
  return array.slice(1, array.length)
}

// forEach([1,2,3], function (x) { console.log(x) })
// => 1
// => 2
// => 3
var forEach = function (array, fn) {
  if (array.length > 0) {
    fn(head(array))
    forEach(tail(array), fn)
  }
}

// map([1,2,3], function (x) { return x+1 })
// => [2,3,4]
var map = function (array, fn) {
  if (array.length > 0) {
    return [fn(head(array))].concat(map(tail(array), fn))
  } else {
    return []
  }
}

// filter([1,2,3,4,5], function (x) { return x>2 })
// => [3,4,5]
var filter = function (array, fn) {
  if (array.length > 0) {
     if (fn(head(array)) === true) {
       return [head(array)].concat(filter(tail(array), fn))
     } else {
       return [].concat(filter(tail(array), fn))
     }
  } else {
     return []
  }
}

diff('saturday', 'sunday')
/* output
[{
  content: 'n',
  index: 4,
  type: 'UPDATE'
}, {
  content: 't',
  index: 2,
  type: 'REMOVE',
}, {
  content: 'a',
  index: 1,
  type: 'REMOVE',
}]
*/

// 定义三种编辑方式
var REMOVE = 'REMOVE',
    INSERT = 'INSERT',
    UPDATE = 'UPDATE'

// 求解从 list1 到 list2 的最小编辑步骤
// 这里的 levenshteinDistance 不再是返回 matrix 的最后一个单元格，而是返回整个 matrix
// diff('saturday', 'sunday', levenshteinDistance('saturday', 'sunday', match))
/* output
[{
  content: 'n',
  index: 4,
  type: 'UPDATE'
}, {
  content: 't',
  index: 2,
  type: 'REMOVE',
}, {
  content: 'a',
  index: 1,
  type: 'REMOVE',
}]
*/
var diff = function (list1, list2, matrix) {
  var len1 = list1.length,
      len2 = list2.length,
      edits = [],
      minimus,
      current,
      over,
      left,
      leftOver,
      x,
      y

  // 设置最后一个单元格为起点
  x = len1
  y = len2
  current = matrix[x][y]

  // 开始回溯
  while (x > 0 || y > 0) {
    // 路径到达了最左边的一列，就只能往上走，于是出现了要往 list1 开头连续添加元素的情况。
    // 例如： def => abcdef 会连续进入下方的 if 三次，每次进入分别插入 c，b，a。
    if (x === 0) {
      edits.push({type: INSERT, index: x-1, content: list2[y-1]})
      y--
      continue
    }
    // 路径到达了最上面的一行，就只能横着往左走，于是出现了要往 list1 开头连续删除元素的情况。
    // 例如：abcdef ＝> def 会连续进入下方的 if 三次，每次进入分别删除 c，b，a。
    if (y === 0) {
      edits.push({type: REMOVE, index: x-1, content: list1[x-1]})
      x--
      continue
    }

    // 找到有可能会前往的三个方向的的值
    over = matrix[x][y-1]
    left = matrix[x-1][y]
    leftOver = matrix[x-1][y-1]

    // 总是忘三个方向中值最小的方向前进
    minimus = Math.min(over, left, leftOver)    
    switch (minimus) {
      // 优先往左上方前进，更新操作或不操作
      case leftOver:
        // 当值变化，表示有编辑操作发生
        if (current > minimus) {
          edits.push({type: UPDATE, index: x-1, content: list2[y-1]})
        }
        current = leftOver
        x--
        y--
        break

      // 往上方前进，插入操作
      case over:
        // 当值变化，表示有编辑操作发生
        if (current > minimus) {
          edits.push({type: INSERT, index: x-1, content: list2[y-1]})
        }
        y--
        current = over
        break

      // 往左方前进，删除操作
      case left:
        // 当值变化，表示有编辑操作发生
        if (current > minimus) {
          edits.push({type: REMOVE, index: x-1, content: list1[x-1]})
        }
        x--
        current = left
        break
    }
  }
  return edits
}

diff(['jquery', 'reactjs', 'redux', 'require'], ['jquery', 'react', 'reflux', 'webpack', 'elm'], 
            levenshteinDistance(['jquery', 'reactjs', 'redux', 'require'], ['jquery', 'react', 'reflux', 'webpack', 'elm'], match))

diff('saturday', 'sunday', levenshteinDistance('saturday', 'sunday', match))

levenshteinDistance('saturday', 'sunday')
// => 3

// 如果两个参数相等，则返回 0，否则返回 1
var match = function (str1, str2) {
  return str1 === str2 ? 0 : 1
}

// 如果两个参数相等，则返回 0，否则返回 1
var match = function (str1, str2) {
  return str1 === str2 ? 0 : 1
}

// 求 list1 和 list2 的编辑距离
// levenshteinDistance('saturday', 'sunday', match)
// => 3
var levenshteinDistance = function (list1, list2, match) {
  var len1 = list1.length,
      len2 = list2.length,
      matrix = [], // 表格
      left,
      over,
      leftOver,
      i,
      j

  // 填写表格的第一行和第一列
  for (i = 0; i <= len1; i++) {
    matrix[i] = []
    matrix[i][0] = i
  }
  for (i = 0; i <= len2; i++) {
    matrix[0][i] = i
  }

  // 自底向上推导
  for (i = 1; i <= len1; i++) {
    for (j = 1; j <= len2; j++) {
      over = matrix[i][j - 1]
      left = matrix[i - 1][j]
      leftOver = matrix[i - 1][j - 1]
      matrix[i][j] = Math.min(
        left + 1, 
        over + 1, 
        leftOver + match(list1[i - 1], list2[j - 1])
      )
    }
  }
  // 将最后一个单元格的值返回
  return matrix[len1][len2]
}

  // 以下是他们所能吃的东西的上限和菜单
  var capacity = 30,
      collections = [
        {name: '米饭'       , weight: 7,  price: 10}, 
        {name: '宫保鸡丁'    , weight: 6,  price: 40}, 
        {name: '紫菜蛋花汤'  , weight: 12, price: 30}, 
        {name: '水煮牛肉'    , weight: 10, price: 50}, 
        {name: '海鲜蒸蛋'    , weight: 8,  price: 35}, 
        {name: '炭烤生蚝'    , weight: 2,  price: 40}, 
        {name: '白灼时蔬'    , weight: 5,  price: 30}
      ]

  // 以下是他们所能吃的东西的上限和菜单
  var capacity = 30,
      collections = [
        {name: '米饭'        , weight: 7,  price: 10}, 
        {name: '宫保鸡丁'    , weight: 6,  price: 40}, 
        {name: '紫菜蛋花汤'  , weight: 12, price: 30}, 
        {name: '水煮牛肉'    , weight: 10, price: 50}, 
        {name: '海鲜蒸蛋'    , weight: 8,  price: 35}, 
        {name: '炭烤生蚝'    , weight: 2,  price: 40}, 
        {name: '白灼时蔬'    , weight: 5,  price: 30}
      ]

  var knapsackProblemByGreedy = function (collections, capacity, sortBy) {
    // 获得排好序的菜单
    var collections = sortBy(collections),
        result = {
          totalPrice: 0,
          totalWeight: 0,
          selected: []
        },
        currentWeight = 0  // 记录已点的菜的总重量

    // 遍历排好序的菜单
    collections.forEach(function (collection) {
      var temp = currentWeight + collection.weight
      // 如果点下当前的菜，菜的重量总和会超过两人的饭量总和（capacity）的值
      // 则程序不会进入下面的 if 语句去修改结果（result）的值
      currentWeight = temp <= capacity ? temp : currentWeight 
      if (currentWeight === temp) {
        result.totalPrice += collection.price
        result.totalWeight += collection.weight
        result.selected.push(collection)
      }
    })
    return result
  }

  // 将菜单按照性价比排序
  var sortByCostPerformance = function (collections) {
    // 这里的 slice(0) 是希望生成一个排序后的副本，而不是在原来的数组上做排序操作
    return collections.slice(0).sort(function (a, b) {
      return (b.price / b.weight) - (a.price / a.weight)
    })
  }

  console.log(knapsackProblemByGreedy(collections, capacity, sortByCostPerformance))

  // 以下是他们所能吃的东西的上限和菜单
  var capacity = 30,
      collections = [
        {name: '米饭'       , weight: 7,  price: 10}, 
        {name: '宫保鸡丁'    , weight: 6,  price: 40}, 
        {name: '紫菜蛋花汤'  , weight: 12, price: 30}, 
        {name: '水煮牛肉'    , weight: 10, price: 50}, 
        {name: '海鲜蒸蛋'    , weight: 8,  price: 35}, 
        {name: '炭烤生蚝'    , weight: 2,  price: 40}, 
        {name: '白灼时蔬'    , weight: 5,  price: 30}
      ]

// 菜单 
var  collections = [
        {name: '米饭'       , weight: 7,  price: 10}, 
        {name: '宫保鸡丁'    , weight: 6,  price: 40}, 
        {name: '紫菜蛋花汤'  , weight: 12, price: 30}, 
        {name: '水煮牛肉'    , weight: 10, price: 50}, 
        {name: '海鲜蒸蛋'    , weight: 8,  price: 35}, 
        {name: '炭烤生蚝'    , weight: 2,  price: 40}, 
        {name: '白灼时蔬'    , weight: 5,  price: 30}
      ]

  var capacity = 30,
      collections = [
        {name: '米饭'        , weight: 7,  price: 10}, 
        {name: '宫保鸡丁'    , weight: 6,  price: 40}, 
        {name: '紫菜蛋花汤'  , weight: 12, price: 30}, 
        {name: '水煮牛肉'    , weight: 10, price: 50}, 
        {name: '海鲜蒸蛋'    , weight: 8,  price: 35}, 
        {name: '炭烤生蚝'    , weight: 2,  price: 40}, 
        {name: '白灼时蔬'    , weight: 5,  price: 30}
      ]
  // 动态规划
  var getMatrix = function (collections, capacity) {
    var len = collections.length,
        matrix = [],
        currentPrice = 0,
        x,
        y

    // 建立二维表格，并且将第一行和第一列的值初始化为 0
    for (x = 0; x <= capacity; x++) {
      matrix[x] = []
      matrix[x][0] = 0
    }

    for (y = 0; y <= len; y++) {
      matrix[0][y] = 0
    }

    // 从上到下，从左往右遍历表格
    for (x = 1; x <= capacity; x++) {
      for (y = 1; y <= len; y++) {
        // 如果当前菜的重量超过当前饭量上限则判定为不点
        if (collections[y - 1].weight > x) {
          matrix[x][y] = matrix[x][y - 1]
        } else {
          // 从点和不点中找到最大值
          matrix[x][y] = Math.max(
            matrix[x - collections[y - 1].weight][y-1] + collections[y - 1].price, // 点当前菜
            matrix[x][y - 1] // 不点当前菜
          )
        }
      }
    }

    return matrix
  }

  console.log(getMatrix(collections, capacity))

  // collections 菜单， capacity 饭量上限
  var knapsackProblemByDynamicProgramming = function (collections, capacity) {
    var matrix = getMatrix(collections, capacity), // 获得填写好的表格，  getMatrix 是之前的动态规划算法
        len = collections.length,
        result = {
           totalPrice: 0,
           totalWeight: 0,
           selected: []
        },
        x,
        y

    // 将 x, y 设置为最后一个单元格的 x, y 
    x = capacity
    y = len

    // 开始回溯
    while (x > 0 || y > 0) {
      // 如果当前菜的重量超过当前饭量则判定为不点
      if (collections[y - 1].weight > x) {
        y--
      } else {
        // 判断当前单元格的值是点下当前菜得来的还是不点得来的
        if ((matrix[x - collections[y - 1].weight][y-1] + collections[y - 1].price) > matrix[x][y - 1]) {
          // 是点下得来的
          result.selected.unshift(collections[y - 1]) // 将当前菜加入结果
          x = x - collections[y - 1].weight // 移动 x
          y-- // 移动 y
        } else {
          // 是不点得来的
          y-- // 移动 y
        }
      }
    }

    // 计算结果集合中价格和重量的总和
    result.selected.forEach(function (item) {
      result.totalPrice += item.price
      result.totalWeight += item.weight
    })

    return result
  }