Advertisement
B1KMusic

Secret Santa Chain Thing

Dec 18th, 2017
261
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Modified version of [1] to run in node.js console
  2. // 1: https://jsfiddle.net/B1KMusic/gu4ofjre/3/embedded/result%2Cjs/
  3.  
  4. // Purpose: to see how high the number of independent chains in a secret santa drawing can get.
  5.  
  6. function FY_sort(list){
  7.     let len = list.length;
  8.     let sel;
  9.  
  10.     while(len){
  11.         sel = Math.floor(Math.random() * len--);
  12.         [list[len], list[sel]] = [list[sel], list[len]];
  13.     }
  14.  
  15.     return list;
  16. }
  17.  
  18. function exclusive_pop(list, exclude){
  19.     let candidate = list.pop();
  20.  
  21.     if(candidate !== exclude)
  22.         return candidate;
  23.  
  24.     list.unshift(candidate);
  25.     return list.pop();
  26. }
  27.  
  28. function getchain(list){
  29.     let head = list.shift();
  30.     let out = head.slice(0);
  31.     let candidate = null;
  32.    
  33.     while((candidate = list.find(x => x[0] === out[out.length-1])) !== undefined){
  34.         out.push(candidate[1]);
  35.         list.splice(list.indexOf(candidate), 1);
  36.     }
  37.        
  38.     return out;
  39. }
  40.  
  41. function write_chains(list){
  42.     let newlist = list.slice(0);
  43.     let chains = new Array;
  44.    
  45.     while(newlist.length > 0)
  46.         chains.push(getchain(newlist));
  47.    
  48.     console.log(`Chains: ${chains.length} / ${list.length}`);
  49.     return chains.length;
  50. }
  51.  
  52. function runit(names){
  53.     let l1 = names.split(",");
  54.     let l2 = FY_sort(l1.slice(0));
  55.     let l3 = new Array;
  56.  
  57.     l1.forEach(function(el){
  58.         l3.push([el, exclusive_pop(l2, el)]);
  59.     });
  60.    
  61.     return write_chains(l3);
  62. }
  63.  
  64. const max = (a,b) => (a > b ? a : b);
  65.  
  66. (function(){
  67.     let highest = 0;
  68.     let arr = "abcdefghijklmnopqrstuvwxyz".split("");
  69.  
  70.     for(let i = 0, l; l = arr.length, i < 6; i++)
  71.         arr.forEach(function(el){
  72.             arr.push(el+arr[l-1]);
  73.         });
  74.  
  75.     for(let i = 0; i < 1000; i++)
  76.         highest = max(highest, runit(arr.join(",")));
  77.  
  78.     console.log(`Highest number of chains after 1,000 runs: ${highest}`);
  79. }());
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement