ウラムの螺旋というのを知ったので、実装してみたいと思います。言語は敢えて苦手なjavascriptに挑戦1。ブラウザで誰でもすぐ確認できるのは便利。jsをほとんど書いた事がないので「もっと綺麗な書き方があるよ」とかのツッコミ大歓迎です。
追記: ウラムの螺旋 3D Three.js編を書きました
https://qiita.com/hakaicode/items/f1c55f43acc530b53cc6
概要
ウラムの螺旋の詳細はWikiでも見てもらうとして、簡単に言うと
「数字を1から順番に螺旋状に並べると素数が特定の傾向をもって並ぶ」
ということだけ。実際に数字を並べながら素数に色をつけて見てみたい。
方針
- 素数を探す関数を書く
- 初期値[0,0],初期方向Rightとして次の配置を探す関数を書く
- 画面表示頑張る
素数を書く
エラトステネスの篩とかあるけど効率よく素数を求めるのが目的じゃないので、素直に1と自分以外で割れないことを確認していく
const goal = 1000; // 仮、あとで入力可能にする
var primes = [2]; // 素数が入った配列。1は素数ではない、あらかじめ2を入れておけば残りは奇数のみ
for(var i=3; i<Math.sqrt(goal); i+=2){
// 過去の素数で割り切れなかったら素数リストに追加
if(primes.find(x => i%x==0) == undefined) primes.push(i);
}
昔中国で採用面接やったとき、素数を表示するプログラム書けっていったら3割くらいしかできなかったけど、Qiita読者なら大丈夫ですよね。2
配置
座標と方向クラス
// 座標
class Position{
constructor(x,y){
this.x=x;
this.y=y;
}
equals = (o) => this.x == o.x && this.y == o.y
toString = () => "{ x:" + this.x + ",y:" + this.y +" }";
}
座標x,yは説明不要でしょう。なんか便利メソッドがありますが気にしないでください(各メンバーを比較するequals自分で書かなあかんの?)
// 方向
class Direction {
constructor(name, step) {
this.name = name;
this.step = step;
this.add = (p) => new Position(p.x + step.x, p.y + step.y);
}
}
const Right = new Direction('Right', {x:1, y:0});
const Up = new Direction('Up', {x:0, y:1});
const Left = new Direction('Left', {x:-1, y:0});
const Down = new Direction('Down', {x:0, y:-1});
const directions = [Right, Up, Left, Down];
const nextDirection = direction => {
console.log(direction)
let index = directions.findIndex(d => d.name == direction.name);
let next = index == directions.length - 1 ? 0 : index + 1;
return directions[next];
};
方向クラスはRightならx座標を1増加、Upならy座標を1増加させます。
右->上->左->下->右...の順番なのでnextDirection(direction)で次の方向が取れるようにします。この辺を配列で表しておいて[1,0][0,1][-1,0][0,-1]行列演算しようかなと思ったのですが、Direction.add()の中のように足すのがわかりやすいかなと思いました。ログ表示のためにRight/Leftなど文字列で持たせました。インスタンス名とる方法ないのかなあ、クラス名はx.constructor.nameみたいだけど。
次の配置を探すロジックですが、今右方向に伸びているとします。この時に上方向が埋まっていれば右にそのまま進み、空いていれば上に切り替えます。わかりやすく3x3の状態から説明します。
5-4-3
| |
6 1-2
|
7-8-9→
currentが9で右を向いています。上に曲がりたいのですが上に2がいるので曲がれません。
5-4-3
| |
6 1-2 〇
| ↑
7-8-9-10
一歩進んで10になると上が空いています。上に曲がりましょう。
5-4-3
| | ↑
6 1-2 11
| |
7-8-9-10
currentが11の時、次に曲がりたい方向は左です。左が空くまでは上に進み続けます。
このチェックを行うためには、配置済みの座標を覚えておく必要があります。
// 地図
let __ground = [];
const groundPut = p => __ground.push(Object.assign({}, p));
const groundFind = p => __ground.find(e => e.equals(p));
現在座標のpositionをground[]に入れてしまうと、positionが変わった時にground[]の中の値も変わってしまうので、put(p)ではコピーを入れます。
本当はGroundクラスにground配列はprivateとして隠蔽して、putやfindもグローバルスコープメソッドじゃなくてGroundのメソッドにしたいんだけどjsは本題じゃないので一旦諦めました。OO脳なので出来るだけスコープはせまく抑えて、脳内で考えるときに対象となる変数、関数を減らしたいんですよね。Groundの詳細はGroundの実装をしてる時だけ意識すればよく、利用側にいる時の余計な情報を減らしたい。
// 現在位置 (0,0),下向きスタート
let current = { position: new Position(0,0), direction: Down}
groundPut (current.position);
現在位置を(0,0)と置きます。→から移動し始めますが、最初は４方向とも空きですので、右向きにセットしておくと「お、上に曲がれるな」となって上に行ってしまいます。下向きでセットしておけば「次は右に曲がれるから右」となります。グラウンドに現在位置を登録します。
// 次位置探し
const groundNext = current => {
// console.log("next:current:"+ current.position.toString())
let p = current.position;
let d = current.direction;
// console.log("next:d:"+ d.name)
let nd = nextDirection(d);
let np = nd.add(p);
if (groundFind(np)) {
// 次の方向に曲がったときのポジションが埋まってるなら
return { position: d.add(p), direction: d }; // 現在の方向へ継続
} else {
return { position: np, direction: nd };
}
};
定義終わりっと、ちょっと動かしてみましょう
for(let i =0; i<10; i++){
put (current.position);
current = next(current);
console.log(JSON.stringify(current));
}
結果。
{"position":{"x":1,"y":1},"direction":{"name":"Up"}}
{"position":{"x":0,"y":1},"direction":{"name":"Left"}}
{"position":{"x":-1,"y":1},"direction":{"name":"Left"}}
{"position":{"x":-1,"y":0},"direction":{"name":"Down"}}
{"position":{"x":-1,"y":-1},"direction":{"name":"Down"}}
{"position":{"x":0,"y":-1},"direction":{"name":"Right"}}
{"position":{"x":1,"y":-1},"direction":{"name":"Right"}}
{"position":{"x":2,"y":-1},"direction":{"name":"Right"}}
{"position":{"x":2,"y":0},"direction":{"name":"Up"}}
{"position":{"x":2,"y":1},"direction":{"name":"Up"}}
jsでclassとか初めて書いた。jsのキモチヨクワカラナイ。ちうか最初はDirectionクラスとか書かないでRight{ next: Up }とかしてたんですけどUpなんか知らないって怒られたんですよね。インタプリタだから評価時に定義されてないと駄目って事なのかな。上にtypeで空宣言しとけば通ったのだろうか。ちょっとjsちゃんとの距離が縮まった気がする3。
[0,0]-[0,1]はソース内で決め打ちしてるので、それにこの結果を上から順に足して座標位置に並べるだけ
[-1,1]-[0,1]-[1,1] [2,1]
| | |
[-1,0] [0,0]-[0,1] [2,0]
| |
[-1,-1]-[0,-1]-[1,-1]-[2,-1]
うん大丈夫そう
画面表示
さて、座標に応じた場所に数字を表示していきます。数字が増えるごとに<div>がにょきにょき生えても面白いかなと思ったのですが、しょうもないとではまりたくないのでCanvas使います。まずはhtml。生Canvasは取り扱いが面倒そうなのでjCanvas使います。
<html>
<head>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.12.4/jquery.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/jcanvas/21.0.1/min/jcanvas.min.js" integrity="sha256-rUshvLY805GcMilbPNnko2JxFKj254/GJZwIP6yaiEk=" crossorigin="anonymous"></script>
</head>
<body>
<canvas id="canvas" width="2560" height="1440" style="border: solid 1px #000;"> </canvas>
<canvas id="canvas">
</canvas>
</body>
</body>
まずは数字表示boxを50x20,間隔10くらいで書いてみますか。あ、jCanvasってjQuery2系までしか対応してないのか。そして先にjquery読み込みを宣言しておかないと動きません。今回はこれで行くとして代わりを探さないと。
⇨縦20pxでは足りなかったのでbox: 50x30にしました。
配置の指定
const offset = { x: canvas.width/2, y: canvas.height/2 };
const Area = { width: 50, height: 30, interval: 10 };
const wi = Area.width + Area.interval;
const hi = Area.height + Area.interval;
const convert = pos => new Position(pos.x * wi + offset.x, pos.y * hi * -1 + offset.y);
数値を表示するためのoffsetをcanvasの真ん中に指定してします。jCanvasでは左上座標が(0,0)でx座標は右に行くと増加、y座標は下に行くと増加です。グラフィック系は大体こうなんですかね。初期座標(0,0)からyは上に行くと増加するように考えていたので、convertするときに-1を掛けています。
const box = (p, c) => {
$('canvas').drawRect({
fillStyle: c,
x: p.x,
y: p.y,
width: Area.width,
height: Area.height,
});
};
const drawPos = (p, s, c) => {
$('canvas').drawText({
fillStyle: c,
x: p.x,
y: p.y,
text: s,
});
};
各数値の背景と文字の描画、p: position, s: 表示string, c: colorで任意の色と文字列で表示できるようにしておきます。
const normalColor = { fg: '#000000', bg:'#F0F0FF' }
const primeColor = { fg: '#FFFFFF', bg:'#CC2010' }
const draw = (i, c) => {
const color = primes.includes(i)?primeColor:normalColor;
let dp = convert(c.position);
box(dp, color.bg);
drawPos(dp, i, color.fg);
};
通常/素数の色指定、current.positionをjcanvas用の座標にconvertして、素数か否かで色を変更して表示しています。
draw(1, current); // 初期位置
for (let i = 2; i < maxNumber; i++) {
current = next(current);
put(current.position);
console.log(JSON.stringify(current));
draw(i, current);
}
値=1の初期位置はnext()で探せないので手打ち、あとはfor文で回します。さてできました。
うーん、なんか思っていたのと違う。もっと対角線が綺麗に並び、対角線外には素数が存在しないイメージでした。
ソースはgithubにありまあす。
https://github.com/dobashi/ulam_spiral/blob/master/uram.html
多分jQueryのせいでhtmlpreviewは使えないので、rawでDLしてローカルブラウザで立ち上げてみてください。初期サイズ2560x1440なので注意。
初期位置が探しにくいので色を緑にして、各要素をつなぐ線をいれました。
const calc = (c,n,interval) => {
let s, d, v=interval/2;
if(c > n){
s = c - v;
d = n + v;
}else if(c < n){
s = c + v;
d = n - v
}else{
s = c;
d = n;
}
return {s, d};
}
const drawLine = (cpos, npos) => {
const c = convert(cpos), n=convert(npos);
let x = calc(c.x, n.x, Area.width)
let y = calc(c.y, n.y, Area.height)
$('canvas').drawLine({
strokeStyle: '#333333',
strokeWidth: 2,
rounded: true,
endArrow: true,
x1: x.s, y1: y.s,
x2: x.d, y2: y.d,
});
};
そうするとこんな感じ。
本当はmaxを入力したらリアルタイムに変更しようとしていたんだけど（calcPrimeあたりにその跡が見えます)、jQueryを排除して見た目もガラッと変えたいので前半戦はこの辺で切り上げることにした。2Dでも再描画でちらつかないようにダブルバッファリングとか、固定絵なので差分のみ描画とかやりだすと切りがないですしおすし。
というわけで、[後半]へ続く4。
2019-09-04追記:ファイル整理しました。minifyしようとしたら怒られたのでchrome以外ではエラーがでるかも。chrome76(Windows7/MacOS)で動作確認ずみ。