javascript - 创建用于分配唯一项目的算法

Question

我不确定如何为我的代码中的特定问题创建算法，所以我创建了这个谜题

• 有 3 个 cookies 怪兽。
• 每个怪物都有一个袋子，里面装着从 0 到有限数量(比如 100)的随机数量的 cookies 。
• cookies有很多种，但我们不知道有多少(生成cookies后才能知道)。
• 每个怪物都会从自己的袋子里吃掉 1 个 cookies
  • 其他怪物都不能得到相同类型的 cookies 。
  • 如果两个或两个以上的怪物在他们的袋子里没有任何独特的口味，则索引较低的怪物应该挑选 cookies ，而其他怪物则不会得到 cookies 。
• 如果可能的话，我们要确保每个怪物都能得到一 block cookies 。

.

// A cookie maker for good measure:
function cookieMaker(quant) {
  // Fill in your own flavours...
  const flavours = [...]
  const cookies = []
  for(let i = 0; i < quant; i++) {
    cookies.push(flavours[Math.floor(Math.random() * flavours.length)])
  }
  return cookies
}

// This is our function
function pickCookies(monsters) {
  ...
}

pickCookies([
  {
    name: 'Fluffy',
    cookies: ['choco', 'vanilla', 'blueberry']
  },
  {
    name: 'Pillowpants',
    cookies: ['choco', 'vanilla']
  },
  {
    name: 'Pinky',
    cookies: ['choco']
  }
])

// Should return:
[
  {
    name: 'Fluffy',
    eat: 'blueberry'
  },
  {
    name: 'Pillowpants',
    eat: 'vanilla'
  },
  {
    name: 'Pinky',
    eat: 'choco'
  }
]

// Note, that it should also work if you shuffle the list.

我做了一个list of flavours为您提供 json 格式:

你会如何解决这个难题？

修订

我似乎遗漏了至少一个细节，所以如果您已经开始研究它，我将在此处添加对拼图的任何更改，以免突然更改规则而混淆任何人:

• #1 如果可能的话，怪物应该尝试从袋子顶部(较低的数组索引)获取 cookies 。

Answer 1

我觉得你的问题很有趣，所以我通过创建这个算法来试一试:

文字

1. 为每个怪物创建一个数组，其中包含它们包中的所有 cookie 类型(删除重复项)。
2. 对于每个怪物，计算他们的选择(可用口味)。
3. 选择选项数量最少的怪物。
4. 对于每个选项，检查有多少其他怪物具有这种味道。
5. 取拥有者最少的味道，让怪物吃掉它。
6. 从剩余的怪物包中去除这种味道。
7. 从第 2 步开始重复，直到 [没有其他饥饿的怪物剩下] 或 [每个剩下的怪物都没有更多可用的口味]。

在代码中

第一枪

var monsters = [{name:'Fluffy'}, {name:'Pillowpants'}, {name:'Pinky'}],
    flavors = ['choco', 'vanilla', 'blueberry', 'peanut butter'],
    maxNumberOfCookies = 6;

$('#generateBtn').click(generateExample);
generateExample();

function generateExample() {
  // Fill each monster's bag
  for(var i=0; i<monsters.length; i++) monsters[i].cookies = cookieMaker();
  // 3, 2, 1, bon appetit!
  var res = pickCookies(monsters);
  displayResults(monsters, res);
}

function cookieMaker() {
  var cookies = [],
      // The quantity is random for each monster
      quant = Math.floor(Math.random() * maxNumberOfCookies);
  for(var i=0; i<quant; i++) {
    cookies.push(flavors[Math.floor(Math.random() * flavors.length)])
  }
  return cookies;
}

function pickCookies(monsters) {
  var res = [];
  // List flavors available for each monster
  for(var i=0; i<monsters.length; i++) {
    var m = monsters[i],
        flavorsInBag = [];
    for(var j=0; j<m.cookies.length; j++) {
      if(flavorsInBag.indexOf(m.cookies[j]) < 0) {
        flavorsInBag.push(m.cookies[j]);
      }
    }
    res.push({name: m.name, flavors: flavorsInBag, eat: false});
  }

  while(!allMonstersAte(res) && !noMoreFlavors(res)) {
    // Take the monster with the smallest number of options
    var monsterWithLeastFlavors = false;
    for(var i=0; i<res.length; i++) {
      if(!res[i].flavors.length) continue;
      if(!monsterWithLeastFlavors
      || res[i].flavors.length < monsterWithLeastFlavors.flavors.length) {
        monsterWithLeastFlavors = res[i];
      }
    }
    // Select the flavor owned by the fewest monsters
    var flavorWithLeastOwners = monsterWithLeastFlavors.flavors[0],
        fewestNbOfOwners = res.length;
    for(var i=0; i<monsterWithLeastFlavors.flavors.length; i++) {
      var nbOfOwners = getNbOfOwners(monsterWithLeastFlavors.flavors[i], res);
      if(nbOfOwners < fewestNbOfOwners) {
        flavorWithLeastOwners = monsterWithLeastFlavors.flavors[i];
        fewestNbOfOwners = nbOfOwners;
      }
    }
    makeMonsterEat(monsterWithLeastFlavors, flavorWithLeastOwners, res);
  }
  return res;
}

// Returns true if all monsters have a property "eat" != false
function allMonstersAte(res) {
  return !res.some(function(monster){ return !monster.eat; });
}

// Returns true if all monsters have no flavor left to choose from
function noMoreFlavors(res) {
  return !res.some(function(monster){ return monster.flavors.length; });
}

// Returns the number of monsters who have that flavor
function getNbOfOwners(flavor, monsters) {
  return monsters.filter(function(monster){
    monster.flavors.indexOf(flavor)>-1;
  }).length;
}

function makeMonsterEat(monster, flavor, res) {
  monster.flavors = [];
  monster.eat = flavor;
  for(var i=0; i<res.length; i++) {
    res[i].flavors = res[i].flavors.filter(function(fl){ return fl != flavor; });
  }
}

function displayResults(monsters, res) {
  var initial = "";
  for(var i=0; i<monsters.length; i++) {
    initial += '<b>' + monsters[i].name + '\'s bag contains:</b> '
             + (monsters[i].cookies.length ? monsters[i].cookies.join(', ') : '<span style="color:red">NOTHING</span>') + '<br>';
  }
  var result = "";
  for(var i=0; i<res.length; i++) {
    result += '<b>' + res[i].name + ' ate:</b> '
            + (res[i].eat ? res[i].eat : '<span style="color:red">NOTHING</span>')
            + '<br>';
  }
  $('#result').html('<h2>Initial state</h2>'
                    + initial
                    + '<h2>Result</h2>'
                    + result
                   );
}

*{margin: 0; padding: 0}
body{font-family: Arial, Helvetica, sans-serif; padding: 1em; font-size: 14px}
h2{font-size: 18px; margin: .3em 0}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

<button id="generateBtn">Generate new example</button>
<div id="result"></div>

更实用的方法

我不知道那是不是你想要的，但我试过了......

var monsters = [{name:'Fluffy'}, {name:'Pillowpants'}, {name:'Pinky'}],
    flavors = ['choco', 'vanilla', 'blueberry', 'peanut butter'],
    maxNumberOfCookies = 6;

$.getJSON('https://cdn.rawgit.com/demux/ad32c612b303aa12d1cdf043225fa1d2/raw/3a037fb7ad30d8a383526ebc62b3671a1656c06d/flavours.json')
  .done(init);

function init(data) {
  flavors = data;
  $('body').html('<button id="generateBtn">Generate new example</button><div id="result"></div>');
  $('#generateBtn').click(generateExample);
  generateExample();
}

function generateExample() {
  // Fill each monster's bag
  for (var i = 0; i < monsters.length; i++)
    monsters[i].cookies = cookieMaker(Math.floor(Math.random() * maxNumberOfCookies));
  // 3, 2, 1, bon appetit!
  var res = pickCookies(monsters);
  displayResults(monsters, res);
}

function cookieMaker(quant) {
  var cookies = [];
  for (var i = 0; i < quant; i++) {
    cookies.push(flavors[Math.floor(Math.random() * flavors.length)])
  }
  return cookies;
}

/*
 * Returns a new Array of monsters who ate unique cookies
 */
function pickCookies(monsters) {
  var res = getMonstersWithFlavors(monsters);

  while (!allMonstersAte(res) && !noMoreFlavors(res)) {
    var monsterIndex = indexOfMonsterWithLeastFlavors(res),
      flavor = flavorWithLeastOwners(res[monsterIndex].flavors, res);

    for (var i = 0; i < res.length; i++) {
      if (i == monsterIndex) res[i] = makeMonsterEat(res[i], flavor);
      else res[i] = removeFlavor(res[i], flavor);
    }
  }

  return res;
}

/*
 * Returns a new Array of monsters with their flavors
 */
function getMonstersWithFlavors(monsters) {
  return monsters.map(function(monster) {
    return {
      name: monster.name,
      flavors: removeDuplicates(monster.cookies),
      eat: false
    };
  });
}

/*
 * Returns a new Array without duplicates
 */
function removeDuplicates(arr) {
  return Array.from(new Set(arr));
}

/*
 * Returns the index of the monster with least flavors
 */
function indexOfMonsterWithLeastFlavors(monsters) {
  var tmp = { monsterIndex: -1, count: false };
  for (var i = 0; i < monsters.length; i++) {
    if (!monsters[i].flavors.length) continue;
    if (!tmp.count || monsters[i].flavors.length < tmp.count) {
      tmp = { monsterIndex: i, count: monsters[i].flavors.length };
    }
  }
  return tmp.monsterIndex;
}

/*
 * Returns the flavor owned by least monsters
 */
function flavorWithLeastOwners(flavors, monsters) {
  var tmp = { flavor: '', count: false };
  for (var i = 0; i < flavors.length; i++) {
    var nbOfOwners = getNbOfOwners(flavors[i], monsters);
    if (!tmp.count || nbOfOwners < tmp.count) {
      tmp = { flavor: flavors[i], count: nbOfOwners };
    }
  }
  return tmp.flavor;
}

/*
 * Checks if all monsters have a property "eat" != false
 */
function allMonstersAte(res) {
  return !res.some(function(monster) {
    return !monster.eat;
  });
}

/*
 * Checks if all monsters have no flavor left to choose from
 */
function noMoreFlavors(res) {
  return !res.some(function(monster) {
    return monster.flavors.length;
  });
}

/*
 * Returns the number of monsters who have that flavor
 */
function getNbOfOwners(flavor, monsters) {
  return monsters.filter(function(monster) {
    monster.flavors.indexOf(flavor) > -1;
  }).length;
}

/*
 * Returns a new monster Object with the cookie they ate
 */
function makeMonsterEat(monster, flavor) {
  return {
    name: monster.name,
    flavors: [],
    eat: flavor
  };
}

/*
 * Returns a new monster Object without the cookie flavor
 */
function removeFlavor(monster, flavor) {
  return {
    name: monster.name,
    flavors: monster.flavors.filter(function(fl) {
      return fl != flavor
    }),
    eat: monster.eat
  };
}


function displayResults(monsters, res) {
  var initial = "";
  for (var i = 0; i < monsters.length; i++) {
    initial += '<b>' + monsters[i].name + '\'s bag contains:</b> ' +
      (monsters[i].cookies.length ? monsters[i].cookies.join(', ') : '<span style="color:red">NOTHING</span>') + '<br>';
  }
  var result = "";
  for (var i = 0; i < res.length; i++) {
    result += '<b>' + res[i].name + ' ate:</b> ' +
      (res[i].eat ? res[i].eat : '<span style="color:red">NOTHING</span>') +
      '<br>';
  }
  $('#result').html('<h2>Initial state</h2>' +
    initial +
    '<h2>Result</h2>' +
    result
  );
}

*{margin: 0; padding: 0}
body{font-family: Arial, Helvetica, sans-serif; padding: 1em; font-size: 14px}
h2{font-size: 18px; margin: .3em 0}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

<h2>Loading...</h2>