Created
August 25, 2018 18:32
-
-
Save geppoz-it/2683d87d89284c57cb8dba25436c78da to your computer and use it in GitHub Desktop.
Hitori solver - bug validator
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Auto-generated code below aims at helping you parse | |
* the standard input according to the problem statement. | |
**/ | |
var n = parseInt(readline()); | |
var map=[]; | |
for (var i = 0; i < n; i++) { | |
map[i]=readline().split(""); | |
printErr("in:"+map[i]); | |
} | |
// ritorna false o map risolta | |
function solve(m){ | |
printErr("solve:"+m); | |
// no shades adiacenti | |
for (var r=0;r<n;r++) for (var c=0;c<n;c++){ | |
if (m[r][c]===0){ | |
if ((c>0)&&(m[r][c-1]===0)) return false; | |
if ((r>0)&&(m[r-1][c]===0)) return false; | |
} | |
} | |
// no numeri isolati | |
for (var r=0;r<n;r++) for (var c=0;c<n;c++){ | |
if (m[r][c]!==0){ | |
var neigh=0; | |
if ((c>0)) neigh+=+m[r][c-1]; | |
if ((r>0)) neigh+=+m[r-1][c]; | |
if ((c<n-1)) neigh+=+m[r][c+1]; | |
if ((r<n-1)) neigh+=+m[r+1][c]; | |
if (neigh===0) return false; | |
} | |
} | |
// duplicati in righe | |
var numbersrepinrow={}; | |
for (var r=0;r<n;r++){ | |
for (var c=0;c<n;c++){ | |
var x=m[r][c]; | |
if (x!==0){ | |
if (numbersrepinrow[x]===undefined) numbersrepinrow[x]={}; | |
if (numbersrepinrow[x][r]===undefined) numbersrepinrow[x][r]=[]; | |
numbersrepinrow[x][r].push(c); | |
} | |
} | |
} | |
var maxrepnum=-1,maxreprow=-1,nrepnum=10000; | |
Object.keys(numbersrepinrow).forEach(function(num){ | |
Object.keys(numbersrepinrow[num]).forEach(function(r){ | |
if ((numbersrepinrow[num][r].length>1)&&(numbersrepinrow[num][r].length<nrepnum)){ | |
maxrepnum=num;maxreprow=r;nrepnum=numbersrepinrow[num][r].length; | |
} | |
}); | |
}); | |
printErr(JSON.stringify(numbersrepinrow),maxrepnum,maxreprow,nrepnum); | |
if (maxrepnum!=-1){ | |
var cols=numbersrepinrow[maxrepnum][maxreprow]; | |
for(var i=0;i<cols.length;i++){ | |
var m1=JSON.parse(JSON.stringify(m)); | |
m1[maxreprow][cols[i]]=0; | |
var s=solve(m1); | |
printErr("ret solve:"+s); | |
if (s!==false) return s; | |
} | |
return false; | |
} | |
// duplicati in colonne | |
var numbersrepincol={}; | |
for (var c=0;c<n;c++){ | |
for (var r=0;r<n;r++){ | |
var x=m[r][c]; | |
if (x!==0){ | |
if (numbersrepincol[x]===undefined) numbersrepincol[x]={}; | |
if (numbersrepincol[x][c]===undefined) numbersrepincol[x][c]=[]; | |
numbersrepincol[x][c].push(r); | |
} | |
} | |
} | |
var maxrepnum=-1,maxrepcol=-1,nrepnum=10000; | |
Object.keys(numbersrepincol).forEach(function(num){ | |
Object.keys(numbersrepincol[num]).forEach(function(c){ | |
if ((numbersrepincol[num][c].length>1)&&(numbersrepincol[num][c].length<nrepnum)){ | |
maxrepnum=num;maxrepcol=c;nrepnum=numbersrepincol[num][c].length; | |
} | |
}); | |
}); | |
printErr(JSON.stringify(numbersrepincol),maxrepnum,maxrepcol,nrepnum); | |
if (maxrepnum!=-1){ | |
var rows=numbersrepincol[maxrepnum][maxrepcol]; | |
for(var i=0;i<rows.length;i++){ | |
var m1=JSON.parse(JSON.stringify(m)); | |
m1[rows[i]][maxrepcol]=0; | |
var s=solve(m1); | |
printErr("ret solve:"+s); | |
if (s!==false) return s; | |
} | |
return false; | |
} | |
// passati tutti criteri | |
return m; | |
} | |
var ma=solve(map); | |
for (var i=0;i<n;i++){ | |
print(ma[i].join('').replace(/0/g,'*')); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This solver is incomplete, since it doesn't discard the solutions that have the number area splitted.
But if you submit it, you get by chance the right solution on all validators.
So this code get a score of 100%, even if is incomplete!