Javascript/node.js - 2588847

Algoritm is a bit different then most here as it makes use of precalculated regions and diff states between calcualtions. It runs under 10 minutes here if you are worried about speed becuase of javascript.

var fs = require('fs') var file = fs.readFileSync('floodtest','utf8'); var boards = file.split('\n\n'); var linelength = boards[0].split('\n')[0].length; var maxdim = linelength* linelength; var board = function(info){ this.info =[]; this.sameNeighbors = []; this.differentNeighbors = []; this.samedifferentNeighbors = []; for (var i = 0;i <info.length;i++ ){ this.info.push(info[i]|0); }; this.getSameAndDifferentNeighbors(); } board.prototype.getSameAndDifferentNeighbors = function(){ var self = this; var info = self.info; function getSameNeighbors(i,value,sameneighbors,diffneighbors){ var neighbors = self.getNeighbors(i); for(var j =0,nl = neighbors.length; j< nl;j++){ var index = neighbors[j]; if (info[index] === value ){ if( sameneighbors.indexOf(index) === -1){ sameneighbors.push(index); getSameNeighbors(index,value,sameneighbors,diffneighbors); } }else if( diffneighbors.indexOf(index) === -1){ diffneighbors.push(index); } } } var sneighbors = []; var dneighbors = []; var sdneighbors = []; for(var i= 0,l= maxdim;i<l;i++){ if (sneighbors[i] === undefined){ var sameneighbors = [i]; var diffneighbors = []; getSameNeighbors(i,info[i],sameneighbors,diffneighbors); for (var j = 0; j<sameneighbors.length;j++){ var k = sameneighbors[j]; sneighbors[k] = sameneighbors; dneighbors[k] = diffneighbors; } } } for(var i= 0,l= maxdim;i<l;i++){ if (sdneighbors[i] === undefined){ var value = []; var dni = dneighbors[i]; for (var j = 0,dnil = dni.length; j<dnil;j++){ var dnij = dni[j]; var sdnij = sneighbors[dnij]; for(var k = 0,sdnijl = sdnij.length;k<sdnijl;k++){ if (value.indexOf(sdnij[k])=== -1){ value.push(sdnij[k]); } } }; var sni = sneighbors[i]; for (var j=0,snil = sni.length;j<snil;j++){ sdneighbors[sni[j]] = value; }; }; } this.sameNeighbors = sneighbors; this.differentNeighbors = dneighbors; this.samedifferentNeighbors =sdneighbors; } board.prototype.getNeighbors = function(i){ var returnValue = []; var index = i-linelength; if (index >= 0){ returnValue.push(index); } index = i+linelength; if (index < maxdim){ returnValue.push(index); } index = i-1; if (index >= 0 && index/linelength >>> 0 === i/linelength >>> 0){ returnValue.push(index); } index = i+1; if (index/linelength >>> 0 === i/linelength >>> 0){ returnValue.push(index); } if (returnValue.indexOf(-1) !== -1){ console.log(i,parseInt(index/linelength,10),parseInt(i/linelength,10)); } return returnValue } board.prototype.solve = function(){ var i,j; var info = this.info; var sameNeighbors = this.sameNeighbors; var samedifferentNeighbors = this.samedifferentNeighbors; var middle = 9*19+9; var maxValues = []; var done = {}; for (i=0; i<sameNeighbors[middle].length;i++){ done[sameNeighbors[middle][i]] = true; } var usefullNeighbors = [[],[],[],[],[],[],[]]; var diff = []; var count = [0]; count[1] = 0; count[2] = 0; count[3] = 0; count[4] = 0; count[5] = 0; count[6] = 0; var addusefullNeighbors = function(index,diff){ var indexsamedifferentNeighbors =samedifferentNeighbors[index]; for (var i=0;i < indexsamedifferentNeighbors.length;i++){ var is = indexsamedifferentNeighbors[i]; var value = info[is]; if (done[is] === undefined && usefullNeighbors[value].indexOf(is) === -1){ usefullNeighbors[value].push(is); diff.push(value); } } } addusefullNeighbors(middle,diff); while( usefullNeighbors[1].length > 0 || usefullNeighbors[2].length > 0 || usefullNeighbors[3].length > 0 || usefullNeighbors[4].length > 0 || usefullNeighbors[5].length > 0 || usefullNeighbors[6].length > 0 ){ for (i=0;i < diff.length;i++){ count[diff[i]]++; }; var maxValue = count.indexOf(Math.max.apply(null, count)); diff.length = 0; var used = usefullNeighbors[maxValue]; for (var i=0,ul = used.length;i < ul;i++){ var index = used[i]; if (info[index] === maxValue){ done[index] = true; addusefullNeighbors(index,diff); } } used.length = 0; count[maxValue] = 0; maxValues.push(maxValue); } return maxValues.join(""); }; var solved = []; var start = Date.now(); for (var boardindex =0;boardindex < boards.length;boardindex++){ var b = boards[boardindex].replace(/\n/g,'').split(''); var board2 = new board(b); solved.push(board2.solve()); }; var diff = Date.now()-start; console.log(diff,boards.length); console.log(solved.join('').length); console.log("end"); fs.writeFileSync('solution.txt',solved.join('\n'),'utf8');