Skip to content

Instantly share code, notes, and snippets.

@geppoz-it
Created August 25, 2018 18:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save geppoz-it/2683d87d89284c57cb8dba25436c78da to your computer and use it in GitHub Desktop.
Save geppoz-it/2683d87d89284c57cb8dba25436c78da to your computer and use it in GitHub Desktop.
Hitori solver - bug validator
/**
* 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,'*'));
}
@geppoz-it
Copy link
Author

geppoz-it commented Aug 25, 2018

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!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment