rubyをawkのように使うには [プログラミング]
#!/bin/awk -f BEGIN{ 〜 } /hoge/{ 〜 }
という感じで書きますが、Rubyの場合、環境によってインストール場所が違うことを考慮して、
#!/usr/bin/env ruby
#!/bin/sh exec ruby -S -nax $0 "$@" #! ruby
#!/usr/bin/ruby -na
項目 | awk | ruby |
フィールドセパレータ | FS | $; |
出力フィールドセパレータ | OFS | $, |
レコードセパレータ | RS | $/ |
出力レコードセパレータ | ORS | $\ |
カレント行番号 | NR | $. |
分割されたフィールド | $1, $2,... | $F[0],$F[1],... |
パターンマッチ | $1 ~ /正規表現/ | if $F[0] =~ /正規表現/ |
BEGINブロック内変数のスコープ | グローバル |
1.8まではBEGINブロック内、
2.0以降はグローバル
|
next文のふるまい |
次の入力行を読み込み、
スクリプトの最初から実行
|
ループを1個抜けるだけ
|
rubyでバイナリファイルを読んでみる [プログラミング]
#!/usr/bin/env ruby
#
# stream.rb -- GDSII Data Parser
# "Stream Format" is output format of GDSII data.
#
# Todo:
# - do like ruby.
# - probably bug about upper/lower nibble
#
# Reference:
# GDSII Format: http://www7b.biglobe.ne.jp/~garaku/HSGDS/GDSII_p01.html
#
# History:
# 0.2 change method to class of each record, add Colrow
# 0.1 implement some records will be used usually
#
# Author:
# M.Hori
####################
# Constant
####################
# Variables
MY_VERSION = '0.2'
USAGE_MSG = "Usage: " << $PROGRAM_NAME << " [options] GDSII_File"
####################
# Module
####################
module Util
# Data Converter
def int2(input)
input.unpack("n")[0]
end
def int4(input)
input.reverse.unpack("l*")[0]
end
def real4(input)
end
def real8(input)
# S=sign, E=index, M=mantissa
# SEEEEEEE MMMMMMMM MMMMMMMM ...(total 7 byte)... MMMMMMMM
# real8 = (-1)^sign * (0.mantissa)_2 * 16^(index-64)
sign = (input & 0x8000000000000000)>>63
index = (input & 0x7F00000000000000)>>56
mantissa = (input & 0x00FFFFFFFFFFFFFF)/(2.0**56)
((-1)**sign)*(mantissa*16**(index-64))
end
def ascii(input)
input.unpack("A*")
end
# long print
def lpr(*var)
printf(*var) if $long
end
module_function :int2, :int4, :real4, :real8, :ascii, :lpr
end
####################
# クラス
####################
class Record
# 2byte ==> unpack("n") # convert to big endian (byte order)
# 1byte ==> unpack("c")
# +----------------------+
# | size | 2 byte
# +-----------+----------+ --+
# |record_type|_data_type| 1 byte + 1 byte |
# +-----------+----------+ +-- others
# | data | (size-4) byte |
# | : | |
# +----------------------+ --+
# readable instance variables
attr_reader :record_type, :_data_type, :data
# Array
@@record_type_array = [
"HEADER", "BGNLIB", "LIBNAME", "UNITS", "ENDLIB",
"BGNSTR", "STRNAME", "ENDSTR", "BOUNDARY", "PATH",
"SREF", "AREF", "TEXT", "LAYER", "DATATYPE",
"WIDTH", "XY", "ENDEL", "SNAME", "COLROW",
"TEXTNODE", "NODE", "TEXTTYPE", "PRESENTATION","SPACING",
"STRING", "STRANS", "MAG", "ANGLE", "UNITEGER",
"USTRING", "REFLIBS", "FONTS", "PATHTYPE", "GENERATIONS",
"ATTRTABLE","STYPTABLE","STRTYPE", "ELFLAGS", "ELKEY",
"LINKTYPE", "LINKKEYS", "NODETYPE", "PROPATTR", "PROPVALUE",
"BOX", "BOXTYPE", "PLEX", "BGNEXTN", "ENDEXTN",
"TAPENUM", "TAPECODE", "STRCLASS", "RESERVED", "FORMAT",
"MASK", "ENDMASKS", "LIBDIRSIZE","SRFNAME", "LIBSECUR",
]
@@data_type_array = [
"NO_DATA", "BIT_ARRAY", "INT_2", "INT_4", "REAL_4",
"REAL_8", "STRING",
]
# Initializer
def initialize(size, others)
@size = size
@record_type, @_data_type = others[0,2].unpack("cc")
@data = others[2,size-4] # size=2, record=1, data=1, total=4byte
end
# to_s
def to_s
return @@record_type_array[@record_type],
@@data_type_array[@_data_type]
end
# no_operation
def no_operation
Util.lpr(" --------------------")
end
# Parser
def parse_data
case record_type
when 0 # HEADER
Util.lpr(" GDSII_Version=%s", Header.new(@data).gds_version)
when 1 # BGNLIB
_m, _a = Bgnlib.new(@data).date
Util.lpr(" Mod=%s Acc=%s", _m, _a)
when 2 # LIBNAME
Util.lpr(" LibraryName=%s", Libname.new(@data).name)
when 3 # UNITS
#units()
_uu, _um = Units.new(@data).units
Util.lpr(" dbUnitByUserUnit=%.1e dbUnitByMeter=%.1e", _uu, _um)
when 4 # ENDLIB
no_operation()
when 5 # BGNSTR
$log["structures"] += 1
_m, _a = Bgnstr.new(@data).date
Util.lpr(" Mod=%s Acc=%s", _m, _a)
when 6 # STRNAME
Util.lpr(" StructureName=%s", Strname.new(@data).name)
when 7 # ENDSTR
no_operation()
when 8 # BOUNDARY
$log["boundaries"] += 1
no_operation()
when 9 # PATH
$log["paths"] += 1
no_operation()
when 10 # SREF
$log["srefs"] += 1
no_operation()
when 11 # AREF
$log["arefs"] += 1
no_operation()
when 12 # TEXT
$log["texts"] += 1
no_operation()
when 13 # LAYER
Util.lpr(" LayerNumber=%d", Layer.new(@data).number)
when 14 # DATATYPE
Util.lpr(" DataType=%d", Datatype.new(@data).number)
when 15 # WIDTH
Util.lpr(" Width=%.1f", Width.new(@data).width)
when 16 # XY
Util.lpr(" %s", Xy.new(@data).xy_list)
when 17 # ENDEL
no_operation()
when 18 # SNAME
Util.lpr(" StructureName=%s", Sname.new(@data).name)
when 19 # COLROW
_col, _row = Colrow.new(@data).colrow
Util.lpr(" Col=%d, Row=%d", _col, _row)
when 22 # TEXTTYPE
Util.lpr(" Text_Type=%d", Texttype.new(@data).number)
when 23 # PRESENTATION
_obj = Presentation.new(@data)
Util.lpr(" Font#=%d Origin=%s", _obj.font, _obj.origin)
when 25 # STRING
Util.lpr(" String=%s", Strings.new(@data).name)
when 26 # STRANS
_obj = Strans.new(@data)
Util.lpr(" Mirror=%s Mag=%d Angle=%d",
_obj.mirror_flag, _obj.mag_flag, _obj.angle_flag)
when 27 # MAG
Util.lpr(" Mag=%.1e", Mag.new(@data).value)
when 28 # ANGLE
Util.lpr(" Angle=%.1f", Angle.new(@data).value)
when 33 # PATHTYPE
Util.lpr(" PathType=%d", Pathtype.new(@data).number)
when 48 # BGNEXTN
Util.lpr(" ProjectionSize=%.1f", Bgnextn.new(@data).width)
when 49 # ENDEXTN
Util.lpr(" ProjectionSize=%.1f", Endextn.new(@data).width)
end
end
end
# HEADER
class Header
def initialize(data)
@data = data
end
def gds_version
case @data.unpack("n")[0]
when 0 then @ver = "v3.0"
when 3 then @ver = "v3.0"
when 4 then @ver = "v4.0"
when 5 then @ver = "v5.0"
when 600 then @ver = "v6.0"
else @ver = "unknown"
end
@ver
end
end
# BGNLIB
class Bgnlib
def initialize(data)
@data = data
end
def date
my,mm,md,mh,mn,ms,ay,am,ad,ah,an,as = @data.unpack("n12")
@last_modify =
"%4d/%02d/%02d,%02d:%02d:%02d"%([1900+my,mm,md,mh,mn,ms])
@last_access =
"%4d/%02d/%02d,%02d:%02d:%02d"%([1900+ay,am,ad,ah,an,as])
return @last_modify, @last_access
end
end
# LIBNAME
class Libname
def initialize(data)
@data = data
end
def name
Util.ascii(@data)
end
end
# UNITS
class Units
def initialize(data)
@data = data
end
def units
# unpack("H16") H: Hex(upper nibble first)
@unit_by_uu = Util.real8(@data[0, 8].unpack("H16").join.hex)
@unit_by_meter = Util.real8(@data[8, 8].unpack("H16").join.hex)
return @unit_by_uu, @unit_by_meter
end
end
# BGNSTR
class Bgnstr < Bgnlib
end
# STRNAME
class Strname < Libname
end
# LAYER
class Layer
def initialize(data)
@data = data
end
def number
Util.int2(@data)
end
end
# DATATYPE
class Datatype < Layer
end
# WIDTH
class Width
def initialize(data)
@data = data
end
def width
Util.int4(@data)
end
end
# XY
class Xy
def initialize(data)
@data = data
end
def xy_list
# unpack("l*") : long(32bit signed int)
# reverse : convert endian
# map(&:to_i) : convert array to int
xys = @data.reverse.unpack("l*").map(&:to_i)
@xy_list = ""
xys.each_slice(2) do |x, y|
@xy_list <<= "(" << x.to_s << "," << y.to_s << ")"
# '<<' beter more than '+' for cat strings
end
@xy_list
end
end
# SNAME
class Sname < Libname
end
# COLROW
class Colrow
def initialize(data)
@data = data
end
def colrow
@data.unpack("n2")
end
end
# TEXTTYPE
class Texttype < Layer
end
# PRESENTATION
class Presentation
def initialize(data)
@data = data
end
def font
@data.unpack("c2")[0].to_i
end
def origin
text_origin_array = [
"upperLeft", "upperCenter", "upperRight", nil,
"centerLeft", "centerCenter", "centerRight", nil,
"lowerLeft", "lowerCenter", "lowerRight", nil
]
text_origin_array[@data.unpack("c2")[1].to_i]
end
end
# STRING
class Strings < Libname
end
# STRANS
class Strans
def initialize(data)
@data = data
end
def mirror_flag
(@data.unpack("c2")[0] & 0x80)>>7
end
def mag_flag
(@data.unpack("c2")[1] & 0x04)>>2
end
def angle_flag
(@data.unpack("c2")[1] & 0x02)>>1
end
end
# MAG
class Mag
def initialize(data)
@data = data
end
def value
Util.real8(@data[0, 8].unpack("H16").join.hex)
end
end
# ANGLE
class Angle < Mag
end
# PATHTYPE
class Pathtype < Layer
# 0=no projection,1=half round projection,
# 2=half width projection, 4=width is BGNEXTN,ENDEXTN
end
# BGNEXTN
class Bgnextn < Width
end
# ENDEXTN
class Endextn < Width
end
####################
# Main
####################
# Variables
$log = {
"records" => 0,
"structures" => 0,
"boundaries" => 0,
"paths" => 0,
"srefs" => 0,
"arefs" => 0,
"texts" => 0,
}
# Method
def usage()
STDERR.printf("%s\n", USAGE_MSG)
end
def cprint(*var)
console = open('/dev/tty', "w") do |con|
con.printf(*var)
end
end
# Parse Options
require 'optparse'
OptionParser.new do |opt|
opt.banner = USAGE_MSG
opt.version = MY_VERSION
opt.on('-l', 'print long format information') { |v| $long = v }
begin
opt.parse!(ARGV)
rescue OptionParser::InvalidOption => e
puts e.message
usage
exit
end
end
# Open File then Read and Parse
INPUT_FILE = ARGV[0]
if !INPUT_FILE then usage; exit end
begin
# not neccesary file.close
File.open(INPUT_FILE, "rb") do |file|
record = {}
c = 0
$bgnstr = 0; $boundary = 0; $path =0;
$sref = 0; $aref = 0; $text = 0
# Display Title
Util.lpr("%4s %3s %-12s %-9s %s\n",
"#", "byte", "RecType", "DataType",
"Contents (XY,WIDTH is dbUnit)")
# Read File
while !file.eof
# Get Record Size
size = file.read(2).unpack("n")[0] # to big endian
if size > 0
data = file.read(size-2) # get remain record
record[c] = Record.new(size, data)
_record_type, _data_type = record[c].to_s
Util.lpr("%4d: %3d %-12s %-9s",
c, size, _record_type, _data_type)
record[c].parse_data()
Util.lpr("\n")
else
break
end
c += 1
cprint("\r%d records loaded.", c) if !$long
end
cprint("%s: %d records, %d structures, %d boundaries, %d paths, %d srefs, %d arefs, %d texts\n",
INPUT_FILE, c, $log["structures"], $log["boundaries"], $log["paths"], $log["srefs"], $log["arefs"], $log["texts"])
end
rescue Errno::ENOENT
STDERR.printf("\n%s not found.\n", INPUT_FILE)
rescue Errno::EACCES
STDERR.printf("\ncannot open %s.\n", INPUT_FILE)
rescue => e
STDERR.printf("\nexception: class=#{e.class}, msg=#{e.message}\n")
end
#EOF
偏差値 [雑記]
学生にはおなじみの「偏差値」ですが、あいまいな理解だったので、少し調べてみました。備忘録です。
定義は以下。
Z = 50 + 10*(x - m)/σ
ここで、Zが偏差値、xが自分の点数、mが平均点、σが標準偏差です。
つまりは、平均点との差をとることで平均を0に、σで割って10掛けることで標準偏差を10に正規化し、50を足すことで平均を50にしています。ここで、なぜ標準偏差が10で平均が50かっていうと、特に数学的な意味はなく、単にそうした、というもののようです。
ただの正規分布の話になってしまいますが、偏差値60(平均+1σ)なら上位16%に、70(平均+2σ)なら上位3%にいる、ということになります。目安の数字として覚えておくといいですね。
ただし、一般の試験において、平均点は発表されることが多いので知ることができますが、標準偏差は発表されませんし、全員の点数がわからないと計算できないので、上記の定義式では偏差値を算出するのは困難です。
そこで、簡易的な式があります。
Z' = 50 + (x - m)/2
ZとZ'を比べてみると、σ=20と見なしていることがわかります。これは、一般的にテストはσ=20を目指して設計されることから来ているようです。
これなら平均点がわかれば計算できます。100点満点で、平均点が50点、自分が60点なら、偏差値は55ということです。
遺伝的アルゴリズム [プログラミング]
遺伝的アルゴリズムを知ったのはもう10年以上も前になるでしょうか。アルゴリズムとかプログラムというものは、解析的というか、わかっている解法を実行するものだと思っていたものですから、遺伝的アルゴリズムやニューラルネットワーク、さらには最近はやりの強化学習のように、解法というかそのパラメータをプログラム自身が探索する、解法はブラックボックス、というアプローチが、とても斬新に思えたものでした。
遺伝的アルゴリズムは、基本的なものは実装も簡単なので、素人でもその強力さが実感できて面白いです。こちらの「エンジニアが正しく「I love you」と伝えるための遺伝的アルゴリズム(殺伐) 」というページを拝見して、興味が再燃したので、おなじ課題をCで組んでみました。ランダムな文字列から出発して、世代交代を繰り返し、「I love you」にたどり着けるか?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#define TARGET "I love you"
#define MUTATE_CHANCE 0.5
#define GENE_NUM 20
#define NUM_OF_MUTATE 1
#define ASCII_MIN 32
#define ASCII_MAX 127
typedef struct {
char *gstr;
int gval;
}GENE;
GENE gene[GENE_NUM];
int gstr_len;
int debug = 0;
void init_gene( void );
int eval( char * );
void gene_sort( void );
int comp( const void *, const void * );
void cross( void );
void mutate( float );
void pr( void );
void pr_usage( void );
// compare for qsort
int comp( const void *c1, const void *c2 ) {
GENE t1 = *(GENE *)c1;
GENE t2 = *(GENE *)c2;
return t1.gval - t2.gval;
}
// init gene
void init_gene() {
int i, j;
// allocate memory
gstr_len = strlen( TARGET );
for ( i = 0; i < GENE_NUM; i++ ) {
gene[i].gstr = (char *)malloc( sizeof(char)*(gstr_len+1) );
if ( gene[i].gstr == NULL ) {
printf( "memory allocation faild.\n" );
exit( EXIT_FAILURE );
}
}
// generate string & sort
srand( (unsigned)time( NULL ) );
for ( i = 0; i < GENE_NUM; i++ ) {
for ( j = 0; j < gstr_len; j++ ) {
sprintf( &gene[i].gstr[j], "%c", rand()%(ASCII_MAX-ASCII_MIN)+ASCII_MIN );
}
gene[i].gstr[j+1] = '\0';
gene[i].gval = eval( gene[i].gstr );
}
qsort( gene, sizeof(gene)/sizeof(gene[0]), sizeof(gene[0]), comp );
}
// mutation
void mutate( float chance ) {
int i, j, k;
int pm;
for ( i = 0; i < GENE_NUM; i++ ) {
if ( chance*10 < rand()%10 ) {
j = rand()%gstr_len;
pm = rand()%2 == 0 ? 1 : -1;
if ( gene[i].gstr[j] == ASCII_MIN) pm = 1;
if ( gene[i].gstr[j] == ASCII_MAX) pm = -1;
gene[i].gstr[j] += pm;
}
}
}
// evaluation
int eval( char *str ) {
int i, v;
int r = 0;
char target[] = TARGET;
for ( i = 0; i < gstr_len; i++ ) {
v = strncmp( target+i, str+i, 1 );
r += v*v;
}
return( r );
}
// select & cross
void cross() {
int i, cp;
cp = rand()%gstr_len;
for ( i = 0; i < gstr_len; i++ ) {
if ( i < cp ) {
gene[GENE_NUM-2].gstr[i] = gene[0].gstr[i];
gene[GENE_NUM-1].gstr[i] = gene[1].gstr[i];
} else {
gene[GENE_NUM-2].gstr[i] = gene[1].gstr[i];
gene[GENE_NUM-1].gstr[i] = gene[0].gstr[i];
}
}
}
void pr() {
int i;
for ( i = 0; i < GENE_NUM; i++ ) {
printf( " >%2d %10s %d\n", i, gene[i].gstr, gene[i].gval );
}
}
// usage
void pr_usage() {
printf( "usage: ga [-dh]\n" );
}
// main
int main( int argc, char **argv ) {
int i, j;
int generation = 0;
int opt;
// optrion
while ( ( opt = getopt( argc, argv, "dh" ) ) != -1 ) {
switch ( opt ) {
case 'd': debug = 1; break;
case '?':
case 'h':
default: pr_usage(); exit( EXIT_SUCCESS );
}
}
// init
init_gene();
if ( debug ) pr();
// loop
while ( gene[0].gval > 0 ) {
// select & cross
cross();
// mutation
mutate( MUTATE_CHANCE );
// evaluation
for ( i = 0; i < GENE_NUM; i++ ) {
gene[i].gval = eval( gene[i].gstr );
}
// sort
qsort( gene, sizeof(gene)/sizeof(gene[0]), sizeof(gene[0]), comp );
printf( "%4d %5d %10s\n", generation, gene[0].gval, gene[0].gstr );
if ( debug ) pr();
generation++;
}
}
実行結果がこちら。左端の数字は世代です。2列目は、「I love you」からどれだけ遠いか、3列目がその文字列。2, 3列目はその世代で最も優秀な個体のものが示されています。
「I love you」にたどり着くと実行が停止します。数百世代を経て、ようやくたどり着きました。でもCygwinでも実行時間はあっという間です。
何世代くらいでたどり着くのか、100回繰り返してみました。横軸が世代数で、縦軸が「I love you」からどれくらい遠いか、です。0でたどり着いたことになるのですが、0近辺を拡大するために logスケールにしてみました。なので1が最小値です。1にたどり着く世代数には、結構、幅があります。
今回の例では、1世代の個体数は20で、ベストな2個体で交叉してワースト2個体と交換します。その後、突然変異は全個体に対して確率50%で生じ、どれか1文字がASCIIコードで1だけ変化します。
このあたりのパラメータを変えてみるとなかなか興味深いです。突然変異なしでは、一向に収束しません。突然変異の確率は、高い方が早く収束するようです。世代交代は、ベスト2個体をワースト2個体と交換するだけでも十分で、交叉はあまり収束性に影響しないようです。
ラングトンのループ [プログラミング]
ラングトンにはもうひとつ、ループというものがあります。
永久に自己増殖を繰り返していくセル・オートマトンです。
ルールはなんと219個!、しかも初期状態がかなり複雑です。
またまた、ルールだけを参考に、ncursesを利用して自前で組んでみました。
無限増殖とはいえ、画面には限りがあるので、上辺と下辺、左辺と右辺がそれぞれ繋がっているトーラス状の世界としてみました。
無限に続くので、終了はCtrl-Cによるものとし、シグナルをキャッチして終わるようにしました。
毎世代、画面の全セルごとに、ルールを検索することになるのですが、最初は甘く見て普通のリニアサーチにしてみたら、ループが増殖するに従い、目に見えて画面更新が遅くなっていきます。これは、最初の黒が多い状態ではルールテーブルの最初のあたりで検索が済むのに対し、色のついたセルのルールはテーブルの下方にあるので、検索に時間がかかるためでした。
Linuxではともかく、Cygwinでは待てないほど遅くなります。それに進むにしたがって遅くなる、というのもカッコ悪いです。
そこで、stdlibにあるバイナリサーチbsearchを使ってみました。バイナリサーチはテーブルがソートされていることが前提なので、これまたstdlibにあるクイックソートqsortを使いました。
効果てきめん! 安定して超高速になりました。
//
// langton's loop
// make: gcc lloop.c -lncurses -o lloop
//
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <ncurses.h>
#include <unistd.h>
#include <signal.h>
#define LLOOP_TABLE "lloop.table"
#define TABLE_SIZE 256
#define RULE_SIZE 10
#define BUF_SIZE 256
#define Q_W 15
#define Q_H 10
#define USLEEP 1000
#define VALUE_AT_NO_RULE 0
int **prev, **post;
char table[TABLE_SIZE*4][RULE_SIZE];
int num_of_table = 0;
int width, height;
int debug = 0;
int num_of_search;
void finalizer( void );
void sig_catch( int );
void rotate_rule( char *, char *, int );
int comp( const void *, const void * );
int comp2( const void *, const void * );
void load_table( void );
int search_table( int, int, int, int, int );
void alloc_mem( void );
void def_color( void );
void init_array( void );
void print_usage( void );
// finalizer
void finalizer() {
int i;
// free
for ( i = 0; i < width; i++ ) free( prev[i] );
free( prev );
for ( i = 0; i < width; i++ ) free( post[i] );
free( post );
attrset( COLOR_PAIR(0) );
mvprintw( 1, 0, "Hit any key" );
getch();
endwin();
exit( EXIT_SUCCESS );
}
// signal handler
void sig_catch( int sig ) {
finalizer();
}
// rotate rule
void rotate_rule( char *in, char *out, int rot ) {
int i;
out[0] = in[0];
for ( i = 1; i <= 4; i++ ) {
out[i] = in[(i-1+rot)%4+1];
}
out[5] = in[5];
}
// compare for qsort
int comp( const void *c1, const void *c2 ) {
return strcmp( (char *)c2, (char *)c1 );
}
// compare for bsearch
int comp2( const void *c1, const void *c2 ) {
return strncmp( (char *)c2, (char *)c1, 5 );
}
// load table
void load_table() {
FILE *fp;
char buf[BUF_SIZE];
if ( (fp = fopen( LLOOP_TABLE, "r" )) == NULL ) {
printf("faile open error\n");
exit( EXIT_FAILURE );
}
while ( fgets( buf, BUF_SIZE, fp ) != NULL ) {
if ( isdigit( buf[0] ) ) {
strncpy( table[num_of_table], buf, 6 );
table[num_of_table][6] = '\0';
num_of_table++;
// expand rule
rotate_rule( buf, table[num_of_table++], 1 );
rotate_rule( buf, table[num_of_table++], 2 );
rotate_rule( buf, table[num_of_table++], 3 );
}
}
// sort for bsearch
qsort( table, sizeof(table)/sizeof(table[0]), sizeof(table[0]), comp );
if ( debug ) {
for ( int i = 0; i < num_of_table; i++ ) {
printf("rule: %d %s\n", i, table[i] );
}
}
}
// search table
int search_table( int c, int n, int e, int s, int w ) {
int i;
char *result;
char key[RULE_SIZE];
sprintf( key, "%d%d%d%d%d", c, n, e, s, w );
result = bsearch( key, table, sizeof(table)/sizeof(table[0]), sizeof(table[0]), comp2 );
if ( result == NULL ) {
return( VALUE_AT_NO_RULE );
} else {
return( atoi( result+5 ) );
}
}
// allocate memory
void alloc_mem() {
int i;
prev = (int **)malloc( sizeof(int *)*width );
if ( prev == NULL ) {
printf("memory allocation failed.\n");
exit(EXIT_FAILURE);
}
for ( i = 0; i < width; i++ ) {
prev[i] = (int *)malloc( sizeof(int)*height );
if ( prev[i] == NULL ) {
printf("memory allocation failed.\n");
exit(EXIT_FAILURE);
}
}
post = (int **)malloc( sizeof(int *)*width );
if ( post == NULL ) {
printf("memory allocation failed.\n");
exit(EXIT_FAILURE);
}
for ( i = 0; i < width; i++ ) {
post[i] = (int *)malloc( sizeof(int)*height );
if ( post[i] == NULL ) {
printf("memory allocation failed.\n");
exit(EXIT_FAILURE);
}
}
}
// define color
void def_color() {
start_color();
init_pair( 0, COLOR_BLACK, COLOR_BLACK );
init_pair( 1, COLOR_BLACK, COLOR_BLUE );
init_pair( 2, COLOR_BLACK, COLOR_RED );
init_pair( 3, COLOR_BLACK, COLOR_GREEN );
init_pair( 4, COLOR_BLACK, COLOR_YELLOW );
init_pair( 5, COLOR_BLACK, COLOR_MAGENTA );
init_pair( 6, COLOR_BLACK, COLOR_WHITE );
init_pair( 7, COLOR_BLACK, COLOR_CYAN );
}
// init array
void init_array() {
int i, j;
int init_q[Q_H][Q_W] = {
{ 0,2,2,2,2,2,2,2,2,0,0,0,0,0,0 },
{ 2,1,7,0,1,4,0,1,4,2,0,0,0,0,0 },
{ 2,0,2,2,2,2,2,2,0,2,0,0,0,0,0 },
{ 2,7,2,0,0,0,0,2,1,2,0,0,0,0,0 },
{ 2,1,2,0,0,0,0,2,1,2,0,0,0,0,0 },
{ 2,0,2,0,0,0,0,2,1,2,0,0,0,0,0 },
{ 2,7,2,0,0,0,0,2,1,2,0,0,0,0,0 },
{ 2,1,2,2,2,2,2,2,1,2,2,2,2,2,0 },
{ 2,0,7,1,0,7,1,0,7,1,1,1,1,1,2 },
{ 0,2,2,2,2,2,2,2,2,2,2,2,2,2,0 } };
for ( i = 0; i < width; i++ ) {
for ( j = 0; j < height; j++ ) {
if ( i >= (width-Q_W)/2 &&
i < (width+Q_W)/2 &&
j >= (height-Q_H)/2 &&
j < (height+Q_H)/2 ) {
prev[i][j] = init_q[j-(height-Q_H)/2][i-(width-Q_W)/2];
} else {
prev[i][j] = 0;
}
}
}
}
// print usage
void print_usage() {
printf( "usage: lloop [-dh]\n" );
}
// main
int main( int argc, char **argv ){
int i, j;
int x, y;
int generation = 0;
int c, n, e, s, w;
int opt;
int change = 0;
// option
while ( (opt = getopt( argc, argv, "dh" )) != -1 ) {
switch ( opt ) {
case 'd':
debug = 1; // debug mode
break;
case 'h':
case '?':
default:
print_usage();
exit(EXIT_SUCCESS);
}
}
// set signal handler
if ( SIG_ERR == signal( SIGINT, sig_catch ) ) {
fprintf( stderr, "cannot set signal handler.\n" );
exit( EXIT_FAILURE );
}
// load rule table
load_table();
// init screen
if ( !debug ) {
initscr();
getmaxyx( stdscr, height, width );
} else {
width = 80; height=51;
}
// define color
if ( !debug ) def_color();
// allocate memory
alloc_mem();
// init prev
init_array();
// init position
for ( i = 0; i < width; i++ ) {
for ( j = 0; j < height; j++ ) {
if ( !debug ) {
attrset( COLOR_PAIR( prev[i][j] ));
mvaddstr( j, i, " " );
}
}
}
if ( !debug ) {
mvprintw( 0, 0, "Hit any key" );
refresh();
}
getch();
if ( !debug ) erase();
// endless loop
for (;;) {
for ( i = 0; i < width; i++ ) {
for ( j = 0; j < height; j++ ) {
// set next generation
c = prev[i][j];
if ( j == 0 ) {
n = prev[i][height-1];
} else {
n = prev[i][j-1];
}
e = prev[(i+1)%width][j];
if ( i == 0 ) {
w = prev[width-1][j];
} else {
w = prev[i-1][j];
}
s = prev[i][(j+1)%height];
post[i][j] = search_table( c, n, e, s, w );
if ( post[i][j] < 0 ) {
printf("search faild.\r\n");
exit( EXIT_FAILURE );
}
}
}
// draw
change = 0;
for ( i = 0; i < width; i++ ) {
for ( j = 0; j < height; j++ ) {
if ( !debug ) {
attrset( COLOR_PAIR( post[i][j] ));
mvaddstr( j, i, " " );
}
if ( prev[i][j] != post[i][j] ) change++;
prev[i][j] = post[i][j];
}
}
// not changed
if ( change == 0 ) {
finalizer();
}
// print generation
if ( !debug ) {
attrset( COLOR_PAIR(6) | A_REVERSE );
mvprintw( 0, 0, "%d", generation );
num_of_search = 0;
refresh();
} else {
printf( "%d %d\n", generation, num_of_search );
num_of_search = 0;
if ( generation >= 500 ) exit(EXIT_SUCCESS);
}
generation++;
//usleep( USLEEP );
}
// finalize
finalizer();
}
実行するとこんな感じ。 カラーでにぎやか。わっかがぐるぐる回りながら上下左右に増えていきます。
真っ暗な世界を増殖する場合はいいんですが、自分の残骸などに衝突すると、ルールに記載のないパターンになることがあるみたいで、その場合は死ぬ(黒くなる)ようにしてみたら、最後に残骸だけ残って停止します。
ラングトンのアリ [プログラミング]
前回書いたライフゲームを調べていたら、「ラングトンのアリ」というものを知りました。ライフゲームよりももっと簡単なたった2個のルールで、まさにアリが歩いた跡のような、複雑な図形が生成されます。
もっと興味深いのは、10000ステップを過ぎたあたりから、それまで混沌(カオス)としていた足跡が、急に規則正しく変化して、右下に一直線に走って行ってしまうように変化することです。
「カオスの縁」というのだそうですが、局所的な単純なルールから、全体的には混沌が生じ、その混沌から突然秩序が生じるわけです。なぞです。
これまた、ルールだけを頼りに自前でコーディングしてみました。またncursesを使いましたが、アリにはもっと広いフィールドが必要な感じです。ncursesだとどうしても表示の分解能が文字単位になってしまうので粗いです。
前回のライフゲームでは、フィールドの大きさを #define で決めうちにしていたのですが、今回は、ターミナルの大きさいっぱいを使うようにしました。起動時のターミナルサイズを取得しmallocしました。アリがフィールドから飛び出るとプログラムが止まるようにしました。
あと、Linuxではループごとにusleepで少し待たないとあっという間に終わってしまうのですが、Cygwinでは何秒に指定しようがusleepを呼ぶだけのオーバーヘッドが数十msくらいある感じで非常に遅いです。下の例ではusleepをコメントアウトしています。
//
// langton's ant
//
#include <stdlib.h>
#include <ncurses.h>
#include <unistd.h>
#define USLEEP 1
int **array;
int width, height;
enum DIR { NORTH, EAST, SOUTH, WEST };
void alloc_mem( void );
void def_color( void );
void init_array( void );
// allocate memory
void alloc_mem() {
int i;
array = (int **)malloc( sizeof(int *)*width );
if ( array == NULL ) {
printf("memory allocation failed.\n");
exit(EXIT_FAILURE);
}
for ( i = 0; i < width; i++ ) {
array[i] = (int *)malloc( sizeof(int)*height );
if ( array[i] == NULL ) {
printf("memory allocation failed.\n");
exit(EXIT_FAILURE);
}
}
}
// define color
void def_color() {
start_color();
init_pair( 0, COLOR_WHITE, COLOR_BLACK );
init_pair( 1, COLOR_BLACK, COLOR_WHITE );
}
// init array
void init_array() {
int i, j;
for ( i = 0; i < width; i++ ) {
for ( j = 0; j < height; j++ ) {
array[i][j] = 0;
}
}
}
// main
int main(){
int i;
int x, y;
int counter = 0;
enum DIR dir;
// init screen
initscr();
getmaxyx( stdscr, height, width );
// define color
def_color();
// allocate memory
alloc_mem();
// init array
init_array();
// init position
x = width / 2;
y = height / 2;
dir = NORTH;
mvprintw( y, x, "Hit any key" );
getch();
erase();
// endless loop
for (;;) {
if ( array[x][y] == 1 ) {
array[x][y] = 0;
attrset( COLOR_PAIR(0) );
mvaddstr( y, x, " " );
switch ( dir ) {
case NORTH:
dir = EAST;
x = x + 1;
break;
case EAST:
dir = SOUTH;
y = y + 1;
break;
case SOUTH:
dir = WEST;
x = x - 1;
break;
case WEST:
dir = NORTH;
y = y - 1;
break;
}
} else {
array[x][y] = 1;
attrset( COLOR_PAIR(1) );
mvaddstr( y, x, " " );
switch ( dir ) {
case SOUTH:
dir = EAST;
x = x + 1;
break;
case WEST:
dir = SOUTH;
y = y + 1;
break;
case NORTH:
dir = WEST;
x = x - 1;
break;
case EAST:
dir = NORTH;
y = y - 1;
break;
}
}
// judge overflow
if ( x < 0 || y < 0 || x > width-1 || y > height-1 ) {
break;
}
// draw
mvprintw( 0, 0, "%d", counter );
refresh();
counter++;
//usleep( USLEEP );
}
// finalize
attrset( COLOR_PAIR(0) );
mvprintw( 1, 0, "Hit any key" );
getch();
endwin();
return(0);
}
動かすとこんな感じ。
ライフゲーム [プログラミング]
ライフゲームといってもボードゲームの人生ゲームではなく、昔のUNIXには/usr/game/lifeとしてインストールされていたもののことです。
ふと思い立って、Cで実装してみました。ネットに溢れている実装例は見ていないので、正解ではないでしょうが、それっぽく動きます。ncursesを試しに使ってみたらきれいにできました。
//
// life
//
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <ncurses.h>
#include <string.h>
#define XSIZE 40
#define YSIZE 20
#define DIVBY 5
#define USLEEP 500000
#define MESSAGE "hit any key to exit"
int prev[XSIZE][YSIZE], post[XSIZE][YSIZE];
// initialize array
void init_array() {
int i, j, r;
srand( (unsigned)time( NULL ) );
for ( i = 0; i < XSIZE; i++ ) {
for ( j = 0; j < YSIZE; j++ ) {
r = rand() % DIVBY;
if ( r != 0 ) {
prev[i][j] = 0;
} else {
prev[i][j] = 1;
}
}
}
}
// judge dead or alive
int dora( int sum, int now ) {
if ( now == 1 ) {
if ( sum == 2 || sum == 3 ) {
return(1);
} else {
return(0);
}
} else {
if ( sum == 3 ) {
return(1);
} else {
return(0);
}
}
}
// change generation
void chgen() {
int i, j;
int z;
for ( i = 0; i < XSIZE; i++ ) {
for ( j = 0; j < YSIZE; j++ ) {
if ( i == 0 && j == 0 ) {
z = prev[i+1][j] + prev[i+1][j+1] + prev[i][j+1];
} else if ( i == XSIZE-1 && j == YSIZE-1 ) {
z = prev[i-1][j] + prev[i-1][j-1] + prev[i][j-1];
} else if ( i == 0 ) {
z = prev[i][j-1] + prev[i][j+1] \
+ prev[i+1][j-1] + prev[i+1][j] + prev[i+1][j+1];
} else if ( i == XSIZE-1 ) {
z = prev[i][j-1] + prev[i][j+1] \
+ prev[i-1][j-1] + prev[i-1][j] + prev[i-1][j+1];
} else if ( j == 0 ) {
z = prev[i-1][j] + prev[i+1][j] \
+ prev[i-1][j+1] + prev[i][j+1] + prev[i+1][j+1];
} else if ( j == YSIZE-1 ) {
z = prev[i-1][j] + prev[i+1][j] \
+ prev[i-1][j-1] + prev[i][j-1] + prev[i+1][j-1];
} else {
z = prev[i-1][j-1] + prev[i-1][j] \
+ prev[i-1][j+1] + prev[i][j-1] + prev[i][j+1] \
+ prev[i+1][j-1] + prev[i+1][j] + prev[i+1][j+1];
}
post[i][j] = dora(z, prev[i][j]);
}
}
}
// copy array
void copy_array() {
int i, j;
for ( i = 0; i < XSIZE; i++ ) {
for ( j = 0; j < YSIZE; j++ ) {
prev[i][j] = post[i][j];
}
}
}
// judge loop
int isSilence() {
int i, j;
int z = 0;
for ( i = 0; i < XSIZE; i++ ) {
for ( j = 0; j < YSIZE; j++ ) {
if ( prev[i][j] != post[i][j] ) {
z++;
}
}
}
return(z);
}
// main routine
int main() {
int i, j;
int x, y, w, h;
int gen;
// initialize screen
initscr();
getmaxyx( stdscr, h, w );
// initialize array
init_array();
erase();
for (;;) {
gen++;
x = w / 2;
y = ( h - YSIZE ) / 2 - 2;
move(y, x);
printw("%d", gen);
for ( i = 0; i < XSIZE; i++ ) {
for ( j = 0; j < YSIZE; j++ ) {
// display
x = ( w - XSIZE ) / 2 + i;
y = ( h - YSIZE ) / 2 + j;
move(y, x);
if ( prev[i][j] == 0 ) {
addch('.');
} else {
addch('@');
}
}
}
refresh();
// change generation
chgen();
// jedge silence
if ( 0 == isSilence() ) {
break;
}
copy_array();
usleep( USLEEP );
}
x = w / 2 - strlen( MESSAGE ) / 2;
y = h / 2 + YSIZE / 2 + 2;
move(y, x);
printw( MESSAGE );
timeout(-1);
getch();
endwin();
return(0);
}
動かすとこんな感じ。
ずっと見ていられます。
ズンドコキヨシ問題 [プログラミング]
先日、ズンドコキヨシ問題というのを知りました。
少し前に流行ったらしいのですが、プログラミングのセンスを試すのに課される問題のようです。
上記のページに様々な言語での実装例が載っています。そこになかった、awkで実装してみました。
BEGINブロックのみというawkにあるまじき実装ですが。
#!/bin/awk -f
# zunzoko.awk
BEGIN{
srand()
for (;;) {
if ( 0 == int((rand()*10)%2) ) {
z++
printf("ズン ")
} else {
printf("ドコ")
if ( z == 4 ) {
printf(" キ・ヨ・シ!\n")
break
}
z = 0
printf("\n")
}
}
}
動かすとこんな感じ。
ズンが4回より多く続いた場合はキヨシコールしないようにしたので、間抜けにズンが長い場合があります。
関数電卓
また関数電卓を買ってしまいました(中央)。
CASIOのfx-JP900です。液晶が高精細なのが、これまでの電卓にはなかった特徴です。高精細とは言ってもスマホなどに比べれば全然ですが。
正直、これらの関数電卓はもう高機能すぎて、ほとんどの機能は使いません(断言)。自分の使いたい機能が使いやすく実装されているか、につきるわけです。
右に写っているCannonのF-766Sは、他の製品にない特徴があって、-9乗のn(ナノ)や、6乗のM(メガ)など、電気屋が多様する単位が2アクションで入力できます。表示もできます。CASIOもできるけど、入力も表示も手間が2、3倍掛かって使う気がしない。CASIOのテンキーには機能がアサインされていないキーがあるので、ぜひここに実装してほしいところです。Shift-3で3乗のk、Alfa-3で-3乗のm、6にuとM、9にnとG、2にpとT、5にfとP、とアサインすれば2アクションで入力できるし、覚えやすいじゃないですか。
左に写っているSHARPは、16進数の入力や計算が他メーカより簡単にできるので購入しました。その後、16進数計算はあまり使わなくなってしまったので、今回、CASIOを買いました。
液晶は確かにきれいなのですが、使っていてうれしかったのは、薄く軽くなっていることです。今の技術なら、もっともっと薄く軽くできるのにって、ずっと思っていたんです。まあ、コストとの兼ね合いなのでしょうが。ただし、机に置いて使うと、歪んでいるのか、カタカタして使いにくい。
少々高くてもいいから、スマホの実装技術を駆使して、かっちりと薄く、キーも固く、液晶も超高精細で、というのを作れませんかね。いや、作れるんでしょうが、売れないんでしょうね。
とにかく、各社のいいとこどりをしたベストな関数電卓がほしいです。
ランサム・サーガ [本]
岩波少年文庫のランサム・サーガ新訳がついに完結しました。といってももう数か月も前ですけど。
子供が持って行ってしまっているので、最後の2巻分(上下で4冊)しか写真はありませんが、数年かけて全12巻(24冊)揃えましたよ。長かった。
岩波少年文庫は本当に名作ぞろいで、小中学校のうちにすべて読破すべき、と思うくらいです。ランサム・サーガを知ったのは残念ながら大人になってからだったので、少年時代に読みたかった、と思いました。
きっとコアなファンがたくさん解説していらっしゃると思いますので、 簡単にしか紹介しませんが、少年少女のありようが詰まっていて、忘れていた子供の頃の気持ちを思い出すことのできる、稀有な作品です。
また、ヨットが重要なモチーフとなっており、その技術的な面や船乗りとしての規律など、私には特に興味深く感じられました。
小学生のお子さんにぜひ勧めてください! 旧訳ならどこの図書館にも揃っています。
気になった方は、作者「アーサー・ランサム」や、このシリーズの第1作「ツバメ号とアマゾン号」などで検索してみてください。