API tools faq
paste
Advertisement
Guest User

12232016[Hard]

a guest
Dec 28th, 2016
407
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
JavaScript 15.77 KB | None | 0 0
raw download clone embed print report
  1. <body>
  2.  
  3. <pre><code>
  4. 1 2 2 1
  5. 1 3 3 1
  6. 1 3 3 2
  7. 2 2 2 2
  8. </code></pre>
  9. <pre><code>3 3 4 5
  10. 5 4 2 3
  11. 4 2 1 1
  12. 5 5 2 4
  13. </code></pre>
  14. <pre><code>2 5 3 1
  15. 4 3 1 3
  16. 4 5 1 3
  17. 4 1 5 4
  18. </code></pre>
  19. <pre><code>5 1 4 2
  20. 1 5 1 3
  21. 2 4 3 5
  22. 1 2 3 2
  23. </code></pre>
  24. <pre><code>3 3 2 5
  25. 3 2 5 3
  26. 2 4 1 5
  27. 4 2 3 1
  28. </code></pre>
  29. <pre><code>4 4 1 4
  30. 5 1 5 1
  31. 3 5 1 3
  32. 1 4 3 4
  33. </code></pre>
  34.  
  35. <pre><code>1 7 2 7 6
  36. 5 5 5 5 3
  37. 6 5 6 6 2
  38. 1 4 1 2 7
  39. 4 6 1 4 1
  40. </code></pre>
  41.  
  42. <pre><code>
  43. 1 2 5 5 3 4
  44. 1 3 5 1 7 2
  45. 5 5 5 1 2 2
  46. 5 1 7 1 3 7
  47. 6 3 4 1 4 9
  48. 3 6 3 4 4 4
  49. </code></pre>
  50.  
  51. </body>
  52.  
  53.  
  54. <script type='application/javascript'>
  55.     /*12/23/16 [Hard] puzzle for /r/dailyprogrammer */
  56.     /*
  57.         Input is a grid of numbers,
  58.             official base spec is a 4x4 grid of numbers 1-5
  59.        
  60.         Any adjacent cells (sharing a wall) that have the same value form a group.
  61.         Groups can be incremented or decremented by 1 as a 'move',
  62.         If their new value equals that of an adjacent group, the two groups merge.
  63.         The challenge is to come up with the minumum moves to 'flatten' a grid into one group
  64.    
  65.         I felt like this problem could be solved fairly difinitively, rather than relying on
  66.         a constrained brute-force approach.
  67.     */
  68.     (()=>{
  69.         let start = new Date();
  70.         let blocks = document.getElementsByTagName('code');
  71.         for(let b in blocks){
  72.             b = blocks[b];
  73.             let input = b.innerHTML;
  74.             if(!input) { continue; }
  75.             let str = input;
  76.             str = str.replace(/\n/g,'');
  77.             str = str.replace(/\s/g,'');
  78.             log('entibo.fr/lvlr/#'+str);// The problem as a game
  79.             let puzzle = new flood_fill(input);
  80.             puzzle.solve();
  81.         }
  82.         let end = new Date();
  83.         log('elapsed: ' + (end-start) +'ms')
  84.      })()
  85.  
  86.     function log(msg){ console.log(msg+'\n'); }
  87.  
  88.     function flood_fill(input){
  89.         this.initial_input = input;
  90.         this.input = [], // initial input stored as two-dimensional array for coordinate parsing.
  91.         this.cells = {},
  92.         this.groups = {},
  93.  
  94.         input = input.split('\n');// parse initial input into two-dimensional array
  95.         for(let i in input){ if(input[i].length>0){ this.input.push(input[i].split(' ')); } }
  96.        
  97.         // First pass: traverse input array
  98.         // Define 'cell' objects for each coordinate
  99.         // Create new groups for them, or merge them with appropriate existing groups
  100.         // Create interlocking references with the cells and the groups
  101.         for(let x in this.input){
  102.             let col = this.input[x];
  103.             let abc = 'abcdefghijklmnopqrstuvwxyz';// Used in group-naming
  104.             for(let y in col){  
  105.                 let new_cell = {
  106.                     coords: [x,y],
  107.                     name : x+','+y,
  108.                     value : col[y],
  109.                     group : null
  110.                 }
  111.                 let first_neighbor = this.cells[x+','+(y-1)];
  112.                 let second_neighbor = this.cells[(x-1)+','+y];
  113.  
  114.                 if(first_neighbor && first_neighbor.value === new_cell.value){
  115.                     first_neighbor.group.cells.push(new_cell);
  116.                     new_cell.group = first_neighbor.group;
  117.                 }
  118.                 else if (second_neighbor && second_neighbor.value === new_cell.value){
  119.                     second_neighbor.group.cells.push(new_cell);
  120.                     new_cell.group = second_neighbor.group;
  121.                 }
  122.                 else {
  123.                     for(let l in abc){
  124.                         let letter = abc[l];
  125.                         if(this.groups[new_cell.value+letter]){ continue; }
  126.                         let new_group = {
  127.                             name : new_cell.value+letter,
  128.                             value : new_cell.value,
  129.                             cells : [new_cell],
  130.                             neighbors : []
  131.                         }
  132.                         this.groups[new_group.name] = new_group;
  133.                         new_cell.group = new_group;
  134.                         break;
  135.                     }
  136.                 }
  137.                 this.cells[new_cell.name] = new_cell;
  138.             }
  139.         }
  140.         // Second pass: loop over our defined cells
  141.         // If two adjacent groups share the same value, they get merged.
  142.         // Each group records their neighbors.
  143.         for(let c in this.cells){
  144.             let cells = this.cells
  145.             let cell = cells[c];
  146.             let coords = [+cell.coords[0],+cell.coords[1]];
  147.  
  148.             let neighbors = [
  149.                 cells[(coords[0]-1)+','+coords[1]],
  150.                 cells[coords[0]+','+(coords[1]-1)],
  151.                 cells[(coords[0]+1)+','+coords[1]],
  152.                 cells[coords[0]+','+(coords[1]+1)]
  153.             ];
  154.  
  155.             for(let n in neighbors){
  156.                 let neighbor = neighbors[n];
  157.                 if(!neighbor){ continue; }
  158.                 // If our neighbor shares our value but not our group, we merge the groups
  159.                 if(cell.value === neighbor.value && cell.group !== neighbor.group){
  160.                     let ng = neighbor.group;
  161.                     for(let nc in ng.cells){    // for each of the neighbor's members
  162.                         nc = ng.cells[nc];
  163.                         cell.group.cells.push(nc);// merge that group's cells into ours
  164.                         nc.group = cell.group;// and set their group to ours
  165.                     }
  166.                     delete this.groups[ng.name]; // then kill off the old reference
  167.                 }// Else, we can add a reference to the neighboring group if we don't have one
  168.                 else if (neighbor.value !== cell.value && !cell.group.neighbors.includes(neighbor.group)){
  169.                         cell.group.neighbors.push(neighbor.group);
  170.                     }
  171.                 }
  172.             }
  173.  
  174.             /*** ending initialization ***/
  175.             /*** beginning solution helper functions ***/
  176.  
  177.             let puzzle = this;
  178.            
  179.             /*  Identifies, sorts, and returns, all peaks and troughs.
  180.                 Peaks and troughs are groups where all adjacent groups have a lower/higher value. */
  181.             let get_peaks_and_troughs = function (groups){
  182.                 let return_value = { peaks:[],troughs:[] }
  183.                 groups.forEach((g)=>{
  184.                     let is_peak = true, is_trough = true;
  185.                     g.neighbors.forEach((n)=>{
  186.                         if(groups.includes(n)){
  187.                             if(n.value > g.value) { is_peak = false; }
  188.                             if(n.value < g.value) { is_trough = false; }
  189.                         }
  190.                     });
  191.                     if(is_peak) { return_value.peaks.push(g); }
  192.                     if(is_trough) { return_value.troughs.push(g); }
  193.                 });
  194.                 return_value.peaks.sort((x,y)=>{ return x.value < y.value; });
  195.                 return_value.troughs.sort((x,y)=>{ return x.value>y.value; });
  196.                 return return_value;
  197.             }
  198.            
  199.             /* Part of our path finding algorithm. Takes an existing path or
  200.                 seeds a new one.  Then attempts to fork that path into the next
  201.                 1-4 adjacent possibilities. */
  202.             let get_paths = function(working_group, needed_groups, current_path){
  203.                 let return_paths = [];
  204.  
  205.                 // We start from our last added group or, if none, from one of our needed groups
  206.                 // and add all neighbors we don't already have that are within our permissible set.
  207.                 let current_group = current_path[0] || needed_groups[0];
  208.                 current_group.neighbors.forEach((n)=>{
  209.                     let current = current_path.slice();
  210.                     if(!current.includes(n) && working_group.includes(n)){
  211.                          current.unshift(n);
  212.                          return_paths.push(current);
  213.                     }
  214.                 });
  215.                 return return_paths;
  216.             }
  217.  
  218.  
  219.             /*  Finds the cheapest path (group of groups) taht connects all needed_groups.
  220.             cheapness is the cost to raise or lower all members of the group to the set_to value
  221.  
  222.             working_group: The group of cells we are working with, either the whole board or a subset.
  223.             needed_groups: The groups we need to connect to one another
  224.             score_func: either raise_troughs() or lower_peaks depending on our needs during the call.
  225.             set_to: when evaluating the score of a path, it is the number of steps to have all members
  226.                 of the path be set to this value. */
  227.             get_best_path = function(working_group, needed_groups, score_func, set_to){
  228.                 let best_path;
  229.                 let paths = get_paths(working_group,needed_groups,[]);
  230.  
  231.                 // Path finding: early-exit permutations of all groups that connect a set of groups
  232.                 for(let _ in puzzle.cells){
  233.                     if(paths.length ===0){ break; }
  234.                     let copy = paths.slice();
  235.                     paths = [];
  236.                     copy.forEach((p)=>{ // for each existing path, get all next-step branches
  237.                         paths = paths.concat(get_paths(working_group,needed_groups,p));
  238.                     });
  239.                     let complete_paths = [];
  240.                     for(let p in paths){
  241.                         p = paths[p];
  242.  
  243.                         // score each path in relation to the best we have,
  244.                         // if it is more expensive, drop it.
  245.                         let path_score = score_func(p, set_to);
  246.                         if(best_path && path_score >= best_path.score){
  247.                             paths.splice(paths.indexOf(p));
  248.                             continue;
  249.                         }
  250.                        
  251.                         // then, check if it is a completed path
  252.                         let needed = needed_groups.slice();
  253.                         p.forEach((g)=>{
  254.                             g.neighbors.forEach((n)=>{
  255.                                 let ndx = needed.indexOf(n);
  256.                                 if(ndx > -1) { needed.splice(ndx,1); }
  257.                             });
  258.                         });
  259.                         if(needed.length === 0) { // If it is complete, compare it to our best
  260.                             if(!best_path || path_score.cost < best_path.cost){
  261.                                 best_path = path_score;
  262.                                 best_path.path = p;
  263.                             }
  264.                             // and remove any completed paths.
  265.                             paths.splice(paths.indexOf(p));
  266.                         }
  267.                     }
  268.                 }
  269.                 // fixes edge-cases where needed_group[0], which is used to seed the paths, is in the middle of a linear path.
  270.                 if(!best_path){ needed_groups.push(needed_groups.shift());
  271.                 best_path = get_best_path(working_group, needed_groups, score_func, set_to); }
  272.                 return best_path;
  273.             }
  274.  
  275.             /* Get all the peaks in a set of groups, and calculate the cost to lower them down to the lowest value */
  276.             let lower_peaks = (groups, lower_to)=>{
  277.                 let pk = get_peaks_and_troughs(groups);
  278.                 let peaks = pk.peaks;
  279.                
  280.                 let cost_to_flatten = 0;
  281.                 if(peaks.length > 1){ cost_to_flatten += peaks[0].value - peaks[1].value; }
  282.                 let start_value = peaks.length>1?peaks[1].value:peaks[0].value;
  283.                
  284.                 let message = 'Lowering high group: ';
  285.                 peaks.forEach((p)=>{ message += p.name + ', '; });
  286.                 if(cost_to_flatten > 0){ message += '\n ' +cost_to_flatten + ' points spent to equalize top 2+ members'; }
  287.                        
  288.                 let path;
  289.                 if(peaks.length > 1){
  290.                     path = get_best_path(groups, peaks, raise_troughs, start_value);
  291.                     message += '\n Bridging peaks with a common path. ';
  292.                     message += '\n Bridge consists of members: ';
  293.                     path.path.forEach((p)=>{ message+=p.name+', '; });
  294.                     message += '\n Spending ' + path.cost + ' points to raise bridge to ' + start_value;
  295.                     cost_to_flatten += path.cost;
  296.                 }
  297.                 let low_value = 0; // Lowest value is the lowest value in groups that isn't a part of our path.
  298.                 pk.troughs.forEach((t)=>{
  299.                     if(path && path.path.includes(t)){  }  
  300.                     else if(low_value === 0 || t.value < low_value){ low_value = t.value; }
  301.                 });
  302.                 if(lower_to){ low_value = lower_to; }
  303.  
  304.                 let last_cost = start_value - low_value;
  305.                 message += '\n Spending ' + last_cost + ' points to lower peak/s to ' + low_value;
  306.                
  307.                 return { message:message, cost: cost_to_flatten+last_cost, value: low_value };
  308.             }
  309.                    
  310.             /* Get all the troughs in a set of groups, and calculate the cost to raise them to the highest value. */
  311.             let raise_troughs = (groups, raise_to)=>{
  312.                 let pk = get_peaks_and_troughs(groups);
  313.                 let troughs = pk.troughs;
  314.  
  315.                 let cost_to_raise = 0;
  316.                 if(troughs.length > 1) { cost_to_raise += troughs[1].value - troughs[0].value; }
  317.                 let start_value = troughs.length > 1 ? troughs[1].value : troughs[0].value;
  318.  
  319.                 let message = 'Raising low group: ';
  320.                 troughs.forEach((p)=>{ message += p.name + ', '; });
  321.                 if(cost_to_raise > 0) { message += '\n ' +cost_to_raise+ ' points spent to equalize bottom 2 members'; }
  322.  
  323.                 let path;    
  324.                 if(troughs.length > 1){
  325.                     path = get_best_path(groups,troughs,lower_peaks,start_value);
  326.                     message += '\n Bridging troughs with a common path. ';
  327.                     message += '\n Bridge consists of members: ';
  328.                     path.path.forEach((p)=>{ message+=p.name+', '; });
  329.                     message += '\n Spending ' + path.cost + ' points to lower bridge to ' + start_value;
  330.                     cost_to_raise += path.cost;
  331.                 }
  332.                 let high_value = 0;
  333.                 pk.peaks.forEach((p)=>{
  334.                     if(path && path.path.includes(p)){}
  335.                     else if(high_value === 0 || p.value > high_value) { high_value = p.value; }
  336.                 });
  337.                 if(raise_to){ high_value = raise_to; }
  338.  
  339.                 let last_cost = high_value - start_value;
  340.                 message += '\n Sending ' + last_cost + ' points to raise trough/s to ' + high_value;
  341.                
  342.                 return { message:message, cost: cost_to_raise+last_cost, value : high_value };
  343.  
  344.             }
  345.  
  346.             // Calculates the 'score' of a group of groups,
  347.             // or how many moves it will take to raise or lower all members
  348.             // to a uniform goal number
  349.             this.solve = function(){
  350.                 let groups = [];
  351.                 log('Solving for input: ');
  352.                 log(puzzle.initial_input);
  353.                 for(let g in this.groups){ groups.push(this.groups[g]); }
  354.                 let lower = lower_peaks(groups);
  355.                 let raise = raise_troughs(groups);
  356.                
  357.                 let best = (lower.cost <= raise.cost) ? lower : raise;
  358.                 log('Solved with cost of ' + best.cost + ' with following approach');
  359.                 log(best.message)
  360.             }
  361.  
  362.             return this;
  363.         }
  364.  
  365. </script>
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!