A*アルゴリズムの実装

もし次の常駐先が女子エンジニアばっかりだったらで出題された「霧島京子からの挑戦状」を解いてみましたので、結果をば。

問題

問題を簡単に説明すると、とある地点Sからとある地点Tまでの最短経路を調べて、その移動方向を出力しろというもの。

ただし、経路上には罠と罠を解除する鍵が置かれている場合があり、鍵がない状態で罠を通過しようとすると通常の100倍移動コストがかかります。

この時のコストが少なければ少ないほど評価されるという仕組みです。

解法

解法というほどたいそれたことはしていませんが、最短経路問題ということは問題文と例から理解したので、それを解決するアルゴリズムを調べて実装しました。

そのアルゴリズムとは、A*(エースター)アルゴリズムと呼ばれるものです。

参考にしたところ

よくわかるA*(A-star)アルゴリズム (Unity2Dのサンプルコードつき)

A* - Wikipedia

実装

以下のように実装しましたが、いくつか問題があるようです。

  1. 罠解除鍵を取得するべきか、取得せずに罠を突破すべきかの判断ができていない
  2. もっとシンプルに実装できるのでは？

2は美意識の問題ですが、1は他の方の結果と見比べると結果が極端に違いますので、この辺りの実装ができてないのが原因だと考えています。 リファクタリングしながらもう少し考えてみたいですね。

「霧島京子の挑戦状」A*アルゴリズムをJavaScriptで実装した。

Node.jsでのhttpサーバの基本

動作確認環境

Node.js

  • v6.3.1

Node.jsでhttpサーバを使う

httpサーバの起動

let http = require('http'),
  server = http.createServer();

server.on('request', (request, response) => {
  response.writeHead(200, {'Content-Type': 'text/html'});
  response.write('Hello World');
  response.end();
});

server.listen('3000', '127.0.0.1', () => {
  console.log(`Server running at 127.0.0.1:3000`);
});

以上のファイルを testServer.js として保存し、node testServer.jsをターミナルで実行するとServer running at 127.0.0.1:3000というログが表示される。 この状態でブラウザから127.0.0.1:3000(localhost:3000)にアクセスすると、Hello Worldが表示される。 サーバを終了するときはターミナルでCtrl+Cを入力し、強制終了させる。

httpサーバの設定を外部から読み込む

別のファイルに保存したサーバの設定を読み込む。

exports.port = 3000;
exports.host = '127.0.0.1';

上記ファイルを testServer.js と同じディレクトリに保存する。 testServer.jsを以下のように変更する。

 let http = require('http'),
+  settings = require('./settings.js'),
   server = http.createServer();

 server.on('request', (request, response) => {
   response.writeHead(200, {'Content-Type': 'text/html'});
   response.write('Hello World');
   response.end();
 });

 server.listen('3000', '127.0.0.1', () => {
-   console.log(`Server running at 127.0.0.1:3000`);
+   console.log(`Server running at ${settings.host}:${settings.port}`);
 });

あとは httpサーバの起動 と同様の操作をすれば同様の結果が得られる。

httpサーバを終了する

ブラウザからアクセスしたら終了するように実装する。

  let http = require('http'),
    settings = require('./settings.js'),
    server = http.createServer();

  server.on('request', (request, response) => {
    response.writeHead(200, {'Content-Type': 'text/html'});
    response.write('Hello World');
    response.end();
+
+   server.close();
+   request.connection.end();
+   request.connection.destroy();
  });

  server.listen(settings.port, settings.host, () => {
    console.log(`Server running at ${settings.host}:${settings.port}`);
  });
+
+ server.once('close', () => {
+   console.log(`close`);
+ });

httpサーバの設定を外部から読み込む や httpサーバの起動 と同様に操作すると、ブラウザでアクセスしたときにcloseのログがコンソールに表示され、サーバが終了する。

エラー処理をする

404エラーを返す処理を実装する。 testServer.js と同じディレクトリに hello.html を作成する。中身は適当はhtmlで構わない。

<! DOCTYPE>
<html>
  <head></head>
  <body>
    <h1>Hello</h1>
  </body>
</html>

testServer.js を以下のように変更する。

  let http = require('http'),
    settings = require('./settings.js'),
+   fs = require('fs'),
    server = http.createServer();

  server.on('request', (request, response) => {
+   fs.readFile(__dirname + '/hello.html', 'utf-8', (err, data) => {
+   if(err){
+     response.writeHead(404, {'Content-Type': 'text/plain'});
+     response.write('Not Found');
+     return response.end();
+   }
+
    response.writeHead(200, {'Content-Type': 'text/html'});
-   response.write('Hello World');
+   response.write(data);
    response.end();
 
    server.close();
    request.connection.end();
    request.connection.destroy();
  });

  server.listen(settings.port, settings.host, () => {
    console.log(`Server running at ${settings.host}:${settings.port}`);
  });
 
  server.once('close', () => {
    console.log(`close`);
  });

サーバを起動し、localhost:3000/hello.htmlにブラウザからアクセスするとHelloという文字( hello.html の中身)が表示される。 hello.html をリネームして(サーバも起動して)再度アクセスすると、Not Foundという文字が表示される。

JavaSciptの配列操作を非破壊的に行う

取り扱うメソッド

Array.prototype - JavaScript | MDNの変更メソッド

動作確認環境

  • Node.js v6.1.0

何をするか

破壊的なメソッドを非破壊的な関数に置き換えることで、参照透過性を維持する。

自作関数range()

まず説明のコード簡略化のため、配列を作成するための簡単な関数を作成する。

この関数は0から与えられた引数までの整数を配列の要素として格納し、その配列を返す。

function range(num){
  if(toString.call(num) !== '[object Number]') return null;
  if(num <= 0)  return null;
  var i = 0,
      arr = [];
  for(i = 0; i <= num; i++){
    arr.push(i);
  }
  return arr;
}

console.log(range(10));
//[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

slice

Array.prototype.slice() - JavaScript | MDN

Array.prototype.slice()は配列から配列の一部を取り出し、新しい配列を返すメソッドである。

このとき一部の配列操作メソッド(pop, shift等)とは異なり、元の配列には何ら影響しない。

つまり、slice()を使用して配列全てを取り出すと、元の配列のシャローコピーを作成することができる。

var arr = range(10);
console.log(arr.slice());
//[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

console.log(arr);
//[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

これを利用して、破壊的メソッドを非破壊的関数に変換していく。

pop

Array.prototype.pop() - JavaScript | MDN

Array.prototype.pop()は配列の最後の要素を取り除き、その値を返すメソッドである。

var a, arr = range(10);
a = arr.pop();
console.log(a);
//10
console.log(arr);
//[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

配列の最後の要素を取り除く動作と、配列の最後の要素を返す動作が同時に行われている。

pop()は元になる配列を変更してしまっているため、破壊的なメソッドである。これを非破壊的な関数に置き換える。

function pop(arr){
  if(toString.call(arr) !== '[object Array]') return null;
  if(arr.length === 0) return null;
  var copy = arr.slice();
  copy.pop();
  return copy;
}

var a = range(10);
console.log(pop(a));
//[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
console.log(a);
//[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

(関数名の是非はともかく)これで非破壊的な動作を行うようになる。配列の後ろの要素から何らかの処理を行いたい場合は、配列の要素を逆転させてmap()を使った方がわかりやすい。

配列の最後の要素を取得したいだけならばpop()を使う必要はないため、作成したpop関数の動作でも問題はないはず。

push

Array.prototype.push() - JavaScript | MDN

Array.prototype.push()は配列の末尾に要素を追加するメソッドである。また、戻り値として新たなる配列の要素数を返す。

var b, arr = range(10);
b = arr.push(100);
console.log(b);
//12
console.log(arr);
//[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100 ]

破壊的なメソッドなので、これも非破壊的な関数へ置き換える。

function push(arr, elem){
  if(toString.call(arr) !== '[object Array]') return null;
  var copy = arr.slice();
  copy.push(elem);
  return copy;
}

var b = range(10);
console.log(push(b, 100));
//[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100 ]
console.log(b);
//[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

shift

Array.prototype.shift() - JavaScript | MDN

Array.prototype.shift()は配列の先頭の要素を取り除き、その値を返すメソッドである。

var c, arr = range(10);
c = arr.shift();
console.log(c);
//0
console.log(arr);
//[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

破壊的なメソッドなので、これも非破壊的な関数へ置き換える。

function tail(arr){
  if(toString.call(arr) !== '[object Array]') return null;
  if(arr.length === 0) return null;
  var copy = arr.slice();
  copy.shift();
  return copy;
}

var c = range(10);
console.log(tail(c));
//[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
console.log(c);
//[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

ついでなので、配列の先頭の要素を取得する関数も作成してみる。

function head(arr){
  if(toString.call(arr) !== '[object Array]') return null;
  if(arr.length === 0) return null;
  var copy = arr.slice();
  return copy.shift();
}

console.log(head(c));
//0
console.log(c);
//[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

unshift

Array.prototype.unshift() - JavaScript | MDN

Array.prototype.unshift()は配列の先頭に要素を追加し、新たな配列の長さを返すメソッドである。

var d, arr = range(10);
d = arr.unshift(100);
console.log(d);
//12
console.log(arr);
//[ 100, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

破壊的なメソッドなので、これも非破壊的な関数へ置き換える。

function unshift(arr, elem){
  if(toString.call(arr) !== '[object Array]') return null;
  var copy = arr.slice();
  copy.unshift(elem);
  return copy;
}

var d = range(10);
console.log(unshift(d, 100));
//[ 100, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
console.log(d);
//[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

sort

Array.prototype.sort() - JavaScript | MDN

Array.prototype.sort()は配列の要素をソートするメソッドである。

var e, arr = [4, 1, 9, 6, 2, 8, 5, 9, 6, 1, 7];
e = arr.sort();
console.log(e);
//[ 1, 1, 2, 4, 5, 6, 6, 7, 8, 9, 9 ]
console.log(arr);
//[ 1, 1, 2, 4, 5, 6, 6, 7, 8, 9, 9 ]

function ascending(x, y){
  if(x < y){
    return -1;
  }else if(x > y){
    return 1;
  }else{
    return 0;
  }
}

function descending(x, y){
  if(x > y){
    return -1;
  }else if(x < y){
    return 1;
  }else{
    return 0;
  }
}

arr = [4, 1, 9, 6, 2, 8, 5, 9, 6, 1, 7];
e = arr.sort(ascending);
console.log(e);
//[ 1, 1, 2, 4, 5, 6, 6, 7, 8, 9, 9 ]
console.log(arr);
//[ 1, 1, 2, 4, 5, 6, 6, 7, 8, 9, 9 ]

arr = [4, 1, 9, 6, 2, 8, 5, 9, 6, 1, 7];
e = arr.sort(descending);
console.log(e);
//[ 9, 9, 8, 7, 6, 6, 5, 4, 2, 1, 1 ]
console.log(arr);
//[ 9, 9, 8, 7, 6, 6, 5, 4, 2, 1, 1 ]

破壊的なメソッドなので、これも非破壊的な関数へ置き換える。

function sort(arr, compare){
  if(toString.call(arr) !== '[object Array]') return null;
  if(arr.length === 0) return null;
  var copy = arr.slice();
  return copy.sort(compare);
}

var e = [4, 1, 9, 6, 2, 8, 5, 9, 6, 1, 7];
console.log(sort(e, ascending));
//[ 1, 1, 2, 4, 5, 6, 6, 7, 8, 9, 9 ]
console.log(e);
//[ 4, 1, 9, 6, 2, 8, 5, 9, 6, 1, 7 ]

reverse

Array.prototype.reverse() - JavaScript | MDN

Array.prototype.reverse()は配列の要素を反転させ、配列を書き換えるメソッドである。

var f, arr = range(10);
f = arr.reverse();
console.log(f);
//[ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ]
console.log(arr);
//[ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ]

破壊的なメソッドなので、これも非破壊的な関数へ置き換える。

function reverse(arr){
  if(toString.call(arr) !== '[object Array]') return null;
  if(arr.length === 0) return arr;
  var copy = arr.slice();
  return copy.reverse();
}

var f, arr = range(10);
console.log(reverse(f));
//[ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ]
console.log(f);
//[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

splice

Array.prototype.splice() - JavaScript | MDN

Array.prototype.splice()は配列から要素を取り除き、新しい要素を追加するメソッドである。

var g, arr = range(10);
g = arr.splice(3, 4, 11, 12, 13); //index3から4要素を取り除き、12, 13を追加する
console.log(g);
//[ 3, 4, 5, 6 ]
console.log(arr);
//[ 0, 1, 2, 11, 12, 13, 7, 8, 9, 10 ]

破壊的なメソッドなので、これも非破壊的な関数へ置き換える。

function splice(arr, index, howMany /*, elements*/){
  if(toString.call(arr) !== '[object Array]') return null;
  if(arr.length === 0) return null;
  var copy = arr.slice(),
    arg = Array.prototype.slice.call(arguments);
  arg.shift();
  Array.prototype.splice.apply(copy, arg);
  return copy;
}

var g, arr = range(10);
console.log(splice(g, 3, 4, 11, 12, 13));
//[ 0, 1, 2, 11, 12, 13, 7, 8, 9, 10 ]
console.log(g); 
//[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

fill

Array.prototype.fill() - JavaScript | MDN

Array.prototype.fill()は配列中の開始インデックスから終了インデックスまで固定値に変更するメソッドである。

var h, arr = range(10);
h = arr.fill(2, 6, arr.length);
console.log(h);
//[ 0, 1, 2, 3, 4, 5, 2, 2, 2, 2, 2 ]
console.log(arr);
//[ 0, 1, 2, 3, 4, 5, 2, 2, 2, 2, 2 ]

破壊的なメソッドなので、これも非破壊的な関数へ置き換える。

function fill(arr, value /*, start, end*/){
  if(toString.call(arr) !== '[object Array]') return null;
  if(arr.length === 0) return null;
  var copy = arr.slice(),
    arg = Array.prototype.slice.call(arguments);
  arg.shift();
  Array.prototype.fill.apply(copy, arg);
  return copy;
}

var h = range(10);
console.log(fill(h, 2, 6, h.length));
//[ 0, 1, 2, 3, 4, 5, 2, 2, 2, 2, 2 ]
console.log(h);
//[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

copyWithin

Array.prototype.copyWithin() - JavaScript | MDN

Array.prototype.copyWithin()はstartからendまでの値をtargetの位置から始まるyousoにコピーするメソッドである。

var i, arr = range(10);
i = arr.copyWithin(4, 8); //arr[8]〜arr[10]をarr[4]〜arr[6]にコピーする
console.log(i);
//[ 0, 1, 2, 3, 8, 9, 10, 7, 8, 9, 10 ]
console.log(arr);
//[ 0, 1, 2, 3, 8, 9, 10, 7, 8, 9, 10 ]

破壊的なメソッドなので、これも非破壊的な関数へ置き換える。

function copyWithin(arr, target, start /*, end */){
  if(toString.call(arr) !== '[object Array]') return null;
  if(arr.length === 0) return null;
  var copy = arr.slice(),
    arg = Array.prototype.slice.call(arguments);
  arg.shift();
  Array.prototype.copyWithin.apply(copy, arg);
  return copy;
}

var i = range(10);
console.log(copyWithin(i, 4, 8));
//[ 0, 1, 2, 3, 8, 9, 10, 7, 8, 9, 10 ]
console.log(i);
//[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

最後に

非破壊的な関数を作ったものの、何回も同じ関数を使い回すと処理時間が大幅に増えてしまうため、場合によっては破壊的なメソッドを使って高速に処理した方がいいかもしれない。

参照透過性を重視するなら、こういうライブラリを自作したりLodashやUnderscoreを使うといい。

また、配列のようなオブジェクトにはこのエントリで定義した関数は使えないため、Array.prototype.slice.call(arrayLike)などで配列に変換してから使う必要がある。

C90頒布情報

今回も無事新刊を出せることとなりましたので、告知します。

  • 日時:8/13土曜日
  • スペース:東J-07a
  • 頒布物:艦これでR -増補改訂版-
  • 頒布価格:300円
  • 内容:艦これを題材に統計処理言語Rを軽く使ってみる。

以上、よろしくお願い致します。

JavaScript版艦これSSキャプチャー

はじめに

El Capitanに更新したので、前に作成したAppleScriptの艦これSSキャプチャーをJXAにしました。

といっても内容は全く変わらず、おまけにJXA的に正しいのか自信が持てません。

Yosemite以降ならば動くと思いますので、とりあえず使ってみたい方はご自由にどうぞ。

ちなみにスクリプトエディターはアプリケーション/ユーティリティにあります。

var system = Application("System Events"),
safari = system.processes["Safari"],
window = safari.windows["艦隊これくしょん -艦これ- - オンラインゲーム - DMM.com"],
position = window.uiElements[0].uiElements[1].uiElements[0].uiElements[0].uiElements[0].uiElements[0].uiElements[2].uiElements[0].uiElements[0].uiElements[0].position();


var x = position[0],
y = position[1],
w = 800,
h = 480,
param = x + "," + y + "," + w + "," + h;

var kancolleImagePath = "Your Image Path",
filename = "`date '+%F'` `date '+%H.%M.%S'`.png"
var cmd = "screencapture -R" + param + " " + '"' + kancolleImagePath + filename + '"';

var app = Application.currentApplication();
app.includeStandardAdditions = true;
app.doShellScript(cmd);

相変わらず決め打ちなので美しくないです。

ちなみにDMM側で艦これのサイトのtitleが変更された場合、それに合わせて変数windowの文字列を変更しなければなりません。

サイトの構造が変更された場合は変数positionで決め打ちしているuiElementsの番号や深さが変わる可能性があります。

注意点

システム環境設定のセキュリティとプライバシー内にあるプライバシータブのアクセシビリティで、アプリケーションにコンピュータの制御を許可しないと実行できません。

最後に

言わなくてもわかるとは思いますが、これはMac専用です。 Automaterでサービス化してすべてのアプリケーションで使えるようにしておくと、SafariがActiveでなくてもSSをキャプチャできるようになります。ついでにショートカット登録しておくと便利です。

この時にもコンピュータの制御を許可しておく必要があります。面倒ですね。

C89頒布情報

ようやくできあがったので、頒布情報などを。

  • 書名：艦これでR
  • 価格：200円
  • 場所：2日目東N08a

不具合情報：5ページ目最下部のコードに不自然なスペースがあるのですが、余計な文字が混入していたのを手作業で修正した影響です。本来ならば以下のようにスペースは空きません。

result <- table(radar$結果)

当日はよろしくお願いいたします。