DevFest Quizパッチワーク問題の回答 CommonJS編

DevFest Quizの回答期限が過ぎたのでエントリにします。パッチワーク問題はJavaScript(CommonJS, Narwhal on Rhino)で解きました。

Google Japan Blog: クイズに答えて DevFest に参加しよう
http://googlejapan.blogspot.com/2010/02/devfest.html

"A" または "B" という文字のみを含む 600 桁、600 行のテキストがあります。これを 600 x 600 の升目状に並べ、上下左右に同じ文字がある部分をつながっているとみなします。

まず、最も多くの文字がつながっている領域をすべて "_" で塗りつぶしてください。 最も多くの文字がつながっている領域が複数存在するならば、それらすべての領域を "_"で塗りつぶすこととします。

そして、各行ごとに "_" が何個含まれているかを数え、それらの数値を改行区切りのテキスト（600 行）として答えてください。

以下の例1を見てください。この入力には単一の文字4つでつながった領域が3箇所あります。これらすべてが「最も多くの文字がつながっている領域」なので、全て"_"で塗りつぶし、その数を数えています。

(以下略)

アルゴリズムの枝刈りが甘いせいか10秒もかかります。data.txtから読み込んでresult.txtに出力してます。

var fs = require('file');
var io = require('io');

var dataSize = {x:600,y:600};
var maxScore = 0;
var maxScoreCells = [];

var dataMap = createMap();
var scoreMap = createScoreMap();

dataMap.forEach(function(line, y) {
  print('check linenum:' + y);
  line.forEach(function(c, x) {
    var score = check(x, y, c);
    scoreMap[y][x] = score;
    if (score > maxScore) {
      maxScore = score;
      maxScoreCells = [{x:x, y:y}];
    } else
    if (score === maxScore) {
      maxScoreCells.push({x:x, y:y});
    }
  });
});

maxScoreCells.forEach(function(p) {
  fill(p.x, p.y, dataMap[p.y][p.x]);
});
output();

// ---- end -----

function createMap() {
  var lines = new io.StringIO(fs.read('data.txt'));
  var result = [];
  lines.forEach(function(line) {
  	result.push(line.split(''));
  });
  return result;
}

function createScoreMap() {
  var result = [];
  for(var i=0; i<dataSize.y; i++) {
    var line = [];
    for(var j=0; j<dataSize.x; j++) {
      line.push(-1);
    }
    result.push(line);
  }
  return result;
}
  
function check(x, y, c) {
  if (x < 0 || 600 <= x || y < 0 || 600 <= y){ return 0; }
  if (scoreMap[y][x] !== -1) { return 0; }
  var score = 0;
  if (c === dataMap[y][x]) {
    score++;
  } else {
    return 0;
  }
  scoreMap[y][x] = 0;
  score+=check(x+1, y, c);
  score+=check(x, y+1, c);
  score+=check(x-1, y, c);
  score+=check(x, y-1, c);
  return score;
}

function fill(x, y, c) {
  if (x < 0 || 600 <= x || y < 0 || 600 <= y){ return 0; }
  if (dataMap[y][x] !== c) { return; }

  dataMap[y][x] = '_';
  fill(x+1, y, c);
  fill(x, y+1, c);
  fill(x-1, y, c);
  fill(x, y-1, c);
}

function output() {
  var results = [];
  dataMap.forEach(function(line) {
    var cnt = 0;
    line.forEach(function(c){if(c === '_'){cnt++;}});
    results.push(cnt);
  });
  fs.write('result.txt', results.join('\n'));
}