SwiftyNote

主にSwiftな技術ブログ

【魔方陣】読ませる気のないアルゴリズムシリーズ【第三弾】

まずはじめに魔陣は魔とはなんら関係ないということを知った。 さて本題にいこう。

方陣とは

n×n 個の正方形の方陣に数字を配置し、縦・横・対角線のいずれの列についても、その列の数字の合計が同じになるもののことである。

行や列単位での交換もできるため、その組み合わせ数は膨大にある。

5 * 5の魔方陣については

1970年代から2億7530万5224通り(対称形などをのぞく)存在することが知られている

とある。Nに対する式で書いて欲しい。

実際に、やってみた。(トレビア風 [ソースコード]

#include <iostream>
#include <iomanip>
using namespace std;
// N * Nの魔方陣(ただしN=奇数)
const int N = 3;
int main() {
    int x,y,c=0,a[N][N];
    // 魔方陣の計算
    for(x=-N/2;x<=N/2;x++)for(y=0;y<N;y++)a[(y-x+N)%N][(y+x+N)%N]=++c;
    // 出力
    for(x=0;x<N*N;x++)cout<<setw(3)<<setfill(' ')<<a[x%N][x/N]<<((x+1)%N?" ":"\n");
}

[出力] 3 * 3

4   9   2
3   5   7
8   1   6

9 * 9

 37  78  29  70  21  62  13  54   5
  6  38  79  30  71  22  63  14  46
 47   7  39  80  31  72  23  55  15
 16  48   8  40  81  32  64  24  56
 57  17  49   9  41  73  33  65  25
 26  58  18  50   1  42  74  34  66
 67  27  59  10  51   2  43  75  35
 36  68  19  60  11  52   3  44  76
 77  28  69  20  61  12  53   4  45

17 * 17

137 282 121 266 105 250  89 234  73 218  57 202  41 186  25 170   9
 10 138 283 122 267 106 251  90 235  74 219  58 203  42 187  26 154
155  11 139 284 123 268 107 252  91 236  75 220  59 204  43 171  27
 28 156  12 140 285 124 269 108 253  92 237  76 221  60 188  44 172
173  29 157  13 141 286 125 270 109 254  93 238  77 205  61 189  45
 46 174  30 158  14 142 287 126 271 110 255  94 222  78 206  62 190
191  47 175  31 159  15 143 288 127 272 111 239  95 223  79 207  63
 64 192  48 176  32 160  16 144 289 128 256 112 240  96 224  80 208
209  65 193  49 177  33 161  17 145 273 129 257 113 241  97 225  81
 82 210  66 194  50 178  34 162   1 146 274 130 258 114 242  98 226
227  83 211  67 195  51 179  18 163   2 147 275 131 259 115 243  99
100 228  84 212  68 196  35 180  19 164   3 148 276 132 260 116 244
245 101 229  85 213  52 197  36 181  20 165   4 149 277 133 261 117
118 246 102 230  69 214  53 198  37 182  21 166   5 150 278 134 262
263 119 247  86 231  70 215  54 199  38 183  22 167   6 151 279 135
136 264 103 248  87 232  71 216  55 200  39 184  23 168   7 152 280
281 120 265 104 249  88 233  72 217  56 201  40 185  24 169   8 153

参考:

方陣 - Wikipedia

【自己組織化写像:SOM】読ませる気のないアルゴリズムシリーズ【第二弾】

自己組織化写像とは

自律的に秩序を持つ構造を作り出す現象

ニューラルネットワークの一種で、教師なし学習が行える。応用としてNNはもちろん、クラスタリング手法としても用いられる。

色彩の分類に応用した例 http://www.sist.ac.jp/~kanakubo/research/neuro/neuro16.png

お、これは前回の記事のようにUIのグラデーション遷移などに応用できそうだ。早速やってみよう。

ソースコード

#include <iostream>
#include <cmath>

using namespace std;

typedef struct {
    int r;
    int g;
    int b;
}RGB;

typedef struct {
    int x;
    int y;
}POS;

const double PI = 3.1415926535;

//マップサイズ
const unsigned int SIZE = 20;

//試行回数
const unsigned int NUM = 10000;

//単調減少関数
double dec(int n){
    return 1.0 - (static_cast<double>(n) / NUM);
}

//結果
void disp(RGB col[SIZE][SIZE]){
    int max, sel;
    for(int i=0; i<SIZE; i++){
        for(int j=0; j<SIZE; j++){
            max=col[i][j].r;
            sel=0;
            if(max<=col[i][j].b && col[i][j].b>=col[i][j].g)sel=2;
            if(max<=col[i][j].g && col[i][j].b<=col[i][j].g)sel=1;
            switch(sel){
                case 0:
                    std::cout<<"● ";
                    break;
                case 1:
                    std::cout<<"× ";
                    break;
                case 2:
                    std::cout<<"□ ";
                    break;
            }
        }
        cout<<endl;
    }
}

//最大相関値の色の位置を取得
POS getMaxCor(RGB col[SIZE][SIZE],RGB value){
    POS pos;
    pos.x = pos.y=0;
    RGB min;
    min.r = min.g = min.b = INT_MAX;
    RGB tmp;
    for(int y=0; y<SIZE; y++){
        for(int x=0; x<SIZE; x++){
            tmp.r=abs(col[y][x].r - value.r);
            tmp.g=abs(col[y][x].g - value.g);
            tmp.b=abs(col[y][x].b - value.b);
            if(min.r+min.g+min.b >= tmp.r+tmp.g+tmp.b){
                min=tmp;
                pos.x=x;
                pos.y=y;
            }
        }
    }
    return pos;
}

//勝者ノードの値に近づける
void divideValue(RGB& col,RGB type){
    col.r = (col.r + type.r) / 2;
    col.g = (col.g + type.g) / 2;
    col.b = (col.b + type.b) / 2;
}

//8近傍関数
void fillMap(RGB col[SIZE][SIZE],RGB type,POS &index){
    int x,y;
    x=index.x;
    y=index.y;
    divideValue(col[y][x], type);
    if(y+1<SIZE && x+1<SIZE) divideValue(col[y+1][x+1], type);
    if(y-1>=0 && x-1>=0) divideValue(col[y-1][x-1], type);
    if(y+1<SIZE && x-1>=0) divideValue(col[y+1][x-1], type);
    if(y-1>=0 && x+1<SIZE) divideValue(col[y-1][x+1], type);
    if(y+1<SIZE) divideValue(col[y+1][x], type);
    if(y-1>=0) divideValue(col[y-1][x], type);
    if(x+1<SIZE) divideValue(col[y][x+1], type);
    if(x-1>=0) divideValue(col[y][x-1], type);
}

int main(int argc, const char * argv[]) {
    RGB rgb[SIZE][SIZE] = {0} , rtmp;
    POS p;
    //マップをランダムに初期化
    for(int y=0; y<SIZE; y++){
        for(int x=0;x<SIZE;x++){
            rgb[y][x].r=arc4random()%256;
            rgb[y][x].g=arc4random()%256;
            rgb[y][x].b=arc4random()%256;
        }
    }
    //自己組織化
    for(int i=0;i<NUM;i++){
        rtmp.r=(arc4random()%256);
        rtmp.g=(arc4random()%256);
        rtmp.b=(arc4random()%256);
        p=getMaxCor(rgb,rtmp);
        fillMap(rgb,rtmp,p);
    }
    //結果
    disp(rgb);
    return 0;
}

実行結果

[1]

× ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● □ □ □ 
× ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● □ □ □ 
× × ● ● ● ● ● ● ● ● ● ● ● ● ● ● □ □ □ □ 
× × ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● □ □ 
× × × × × × ● ● ● ● ● ● ● ● ● ● ● ● □ □ 
□ □ □ □ × × × ● ● ● ● ● ● ● ● ● ● ● ● □ 
□ □ □ □ × × × × ● ● ● ● ● ● ● ● ● ● ● ● 
□ □ □ × × × × × ● ● ● ● ● ● ● ● ● ● ● ● 
□ □ □ × × × × × ● ● ● ● ● ● ● ● ● ● ● ● 
□ □ × × × × × × × × ● ● ● ● ● ● ● ● □ □ 
● × × × × × × × × × × × × × ● ● ● □ □ □ 
● × × × × × × × × × × × × × ● ● □ □ □ □ 
× × × × × × × × × × × × × × □ □ □ □ □ □ 
× × × × × × × × × × × × × × □ □ □ □ □ □ 
× × × × × × × × × □ □ □ □ □ □ □ □ □ □ □ 
× × × × × × × × × □ □ □ □ □ □ □ □ □ □ □ 
× × × × × × × × × □ □ □ □ □ □ □ □ □ □ □ 
× × × × × × × × □ □ □ □ □ □ □ □ □ □ □ □ 
× × × × × × × × □ □ □ □ □ □ □ □ □ □ □ □ 
× × × × × × × × □ □ □ □ □ □ □ □ □ □ □ □ 

[2]

● ● ● ● ● ● × × × × × × × × ● ● ● □ □ × 
● ● ● ● ● ● × × × × × × × × ● ● ● □ □ × 
● ● ● ● ● ● × × × × × × × × ● ● ● □ □ × 
● ● ● ● ● ● × × × × × × × × × × × × × × 
● ● ● ● ● ● × × × × × × × × × × × × × × 
● ● ● ● ● ● × × × × × × × × × × × × × × 
● ● ● ● ● ● × × × × × × × × × × × □ × × 
● ● ● ● ● ● × ● ● ● × × × × × × × × □ □ 
● ● ● ● ● ● ● ● ● ● ● × × × × × × × × □ 
● ● ● ● ● ● ● ● ● ● □ □ □ × × × × × × × 
● ● ● ● ● ● ● ● ● ● □ □ □ □ □ □ □ × × × 
● ● ● ● ● ● ● ● ● ● □ □ □ □ □ □ □ □ □ □ 
● ● ● ● ● ● ● □ □ □ □ □ □ □ □ □ □ □ □ □ 
● ● ● ● □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ 
● ● ● ● □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ × 
● ● ● ● ● □ □ □ □ □ □ □ □ □ □ □ □ ● × × 
● ● ● ● ● □ □ □ □ □ □ □ □ □ □ □ □ ● ● ● 
● ● ● ● ● □ □ □ □ □ □ □ □ □ □ □ □ ● ● ● 
● □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ● × × 
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ × × ×

[3]

● ● ● × × × × × □ □ □ □ □ □ □ □ □ □ □ □ 
● ● ● × × × × × □ □ □ □ □ □ □ □ □ □ □ □ 
● ● ● ● × × × × × × × × □ □ □ □ □ □ □ □ 
● ● ● ● × × × × × × × × × × □ □ □ □ □ □ 
● ● ● ● ● × × × × × × × × × × □ □ □ □ □ 
● ● ● ● ● × × × × × × × × × × × □ □ □ □ 
● ● ● ● ● × × × × × × × × × × × × × □ □ 
● ● ● ● ● × × × × × × × × × × × × × × × 
● ● ● ● ● ● × × × × × × × × × ● ● ● × × 
● ● ● ● ● ● × × × × × × × × × ● ● ● × × 
● ● ● ● ● ● × × × × × × × × ● ● ● ● ● ● 
● ● ● ● ● ● × × × × × × × × □ ● ● ● ● ● 
● ● ● ● ● ● ● ● × × × × × × □ □ □ □ □ ● 
● ● ● ● ● ● ● ● × × × × × □ □ □ □ □ □ □ 
● ● ● ● ● ● ● ● × × × × × □ □ □ □ □ □ □ 
● ● ● ● ● ● ● ● × × × × □ □ □ □ □ □ □ □ 
● ● ● ● ● ● ● ● ● × × × □ □ □ □ □ □ □ □ 
● ● ● ● ● ● ● ● □ □ □ □ □ □ □ □ □ □ □ □ 
● ● ● ● ● □ ● □ □ □ □ × □ □ □ □ □ □ □ □ 
● ● ● ● ● □ □ □ □ □ □ □ □ □ □ □ □ □ □ □

まずい、ある程度読めてしまう。 それは良いとして、なかなか面白い結果になった。今回は●×□の3種類でやってみたがN種類の色で自己組織化MAPを作ればグラデーションやBlurMaskに応用できそうだ。

自己組織化写像 - Wikipedia

自己組織化 - Wikipedia

rinov.hatenablog.com

【ガウス素数】読ませる気のないアルゴリズムシリーズ【第一弾】

自分の中では一番得意な言語であるC/C++言語。業務ではSwiftの内部実装を見る以外に使うことはないので日に日に忘れていってしまいそうである。なのでC++を思い出しつつ、なにかテーマを探し記事としてまとめることで実装力とアルゴリズム力を維持するための1人企画である。 本シリーズは自分用のため、読ませる気はないのでご了承くださいm( )m 絶対に業務では書かないような記法、実装が多々あるためご注意ください。しかし、最低限の処理だけで書きコピペで動作確認できるようなものにしたいと思いますので、奇跡的に学習したいテーマのアルゴリズムだった。などというパターンのみご利用ください。あまり有名なものはチョイスしない方針です。

ガウス素数とは

Wikipediaなどを調べても、ん?となるだけだ。どんなに複雑で難解な説明でもアルゴリズムとその使いみちがわかるほうが数倍重要だと思う。 つまり、ガウス素数は左右対称なきれいな模様を導ける素数とだけ覚えておいたほうが今後役に立つはずだ。(実際にはちゃんと説明は読んだ) 実際にガウス素数の説明には

テーブルクロス織りにも用いられることもある。

と書いてある。もしかしたらカラーグラデーションなどにも応用できるかもしれない。これは期待できる。 早速実装してみよう。

実装

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 27;
char a[N+1][N+1];
int main() {
    int q,p,x,y;
    const int SN = sqrt(N);
    fill(&a[0][0],&a[N][0]+N,1);
    a[0][0] = a[1][0] = a[0][1] = 0;
    for(int i=0;i<SN;i++){
        for(int j=0;j<=i;j++){
            if(!a[i][j])continue;
            p=i;q=j;
            while(p<=N){
                x=p;y=q;
                do{
                    a[x][y]=a[y][x]=0;
                }while ((x-=j)>=0 && (y+=i)<=N);
                x=p;y=q;
                do{
                    a[x][y]=a[y][x]=0;
                }while ((x+=j)<=N && (y-=i)>=0);
                p+=i;q+=j;
            }
            a[i][j]=a[j][i]=1;
        }
    }
    for(int i=-N;i<=N;i++){
        for(int j=-N;j<=N;j++){
                printf("%s",(a[abs(i)][abs(j)] && i*i+j*j<=N*N)?"■■":"  ");
        }
        cout<<endl;
    }
}

実行結果:

                          ■■                          
                ■■  ■■          ■■  ■■                
              ■■  ■■      ■■      ■■  ■■              
            ■■      ■■  ■■  ■■  ■■      ■■            
              ■■  ■■      ■■      ■■  ■■              
            ■■  ■■  ■■          ■■  ■■  ■■            
      ■■  ■■          ■■  ■■  ■■          ■■  ■■      
    ■■  ■■      ■■      ■■  ■■      ■■      ■■  ■■    
  ■■      ■■  ■■  ■■  ■■      ■■  ■■  ■■  ■■      ■■  
    ■■  ■■      ■■      ■■  ■■      ■■      ■■  ■■    
  ■■  ■■  ■■          ■■  ■■  ■■          ■■  ■■  ■■  
            ■■  ■■  ■■  ■■  ■■  ■■  ■■  ■■            
      ■■      ■■  ■■  ■■■■  ■■■■  ■■  ■■      ■■      
■■  ■■  ■■  ■■      ■■          ■■      ■■  ■■  ■■  ■■
      ■■      ■■  ■■  ■■■■  ■■■■  ■■  ■■      ■■      
            ■■  ■■  ■■  ■■  ■■  ■■  ■■  ■■            
  ■■  ■■  ■■          ■■  ■■  ■■          ■■  ■■  ■■  
    ■■  ■■      ■■      ■■  ■■      ■■      ■■  ■■    
  ■■      ■■  ■■  ■■  ■■      ■■  ■■  ■■  ■■      ■■  
    ■■  ■■      ■■      ■■  ■■      ■■      ■■  ■■    
      ■■  ■■          ■■  ■■  ■■          ■■  ■■      
            ■■  ■■  ■■          ■■  ■■  ■■            
              ■■  ■■      ■■      ■■  ■■              
            ■■      ■■  ■■  ■■  ■■      ■■            
              ■■  ■■      ■■      ■■  ■■              
                ■■  ■■          ■■  ■■                
                          ■■                       

なるほど? 使いみちがわからない。

ガウス整数 - Wikipedia

【Swift3】enumでJSONデコーダを作ってみる

JSONデコーダenumで作成したらどうなるかふと思ったので作ってみることに。 最少限度の実装でまずはできるか試して、今度検証したりするとき用のメモ程度に。

個人的にはindirectJSONの階層構造を表現することでちょっとだけ高速になるかもしれないと考えた。 JSONではjson["user"]["name"]のように連想配列的に値にアクセスできる。また、このように同じ階層の値がさらに子を持つことがよくある。連想配列ではハッシュにより任意のキーの値へのアクセスのオーダーはO(1)である、しかし実装によっては(※1)階層が増えれば増えるほどキーアクセスはO(n)となる。なので階層が深いキーなどは通過時に一度パスを保持しておくことでアクセス数が減るのではないかと思ったが、多分、数MB以上のJSONなどでない限り効果が薄すぎてあまり意味ないかもしれない。 とりあえず、まず実用的かは考えずに実装してみる。(indirectを使うとは…言っていない)

// `T`型に変換または`invalidPropertyType`をthrow
func castOrFail<T>(_ any: Any) throws -> T {
    guard let result = any as? T else {
        throw JSONParseError.invalidPropertyType
    }
    return result
}

protocol Decodable {
    static func decode(_ json: JSON) throws -> Self
}

// JSONの値は`String`に変換可能
extension String: Decodable {
    static func decode(_ json: JSON) throws -> String {
        return try castOrFail(json)
    }
}

// JSONの値は`Int`に変換可能
extension Int: Decodable {
    static func decode(_ json: JSON) throws -> Int {
        return try castOrFail(json)
    }
}

// 適当なエラーを定義
enum JSONParseError: Error {
    case invalidJSON
    case invalidPropertyType
}

enum JSON {
    typealias RawValue = Any?

    case json([String: Any])
    
    init?(rawValue: RawValue) {
        guard let json = rawValue as? [String: Any] else { return nil }
        self = .json(json)
    }

    func decode<T: Decodable>(path: String) throws -> T {
        if case .json(let json) = self {
            for node in json {
                if path == node.key { return try castOrFail(node.value) }
                if let newJSON = JSON(rawValue: node.value) {
                    let _: T = try newJSON.decode(path: path)
                }
            }
        }
        throw JSONParseError.invalidJSON
    }

}

// カスタムオペレータの定義
infix operator <| : MultiplicationPrecedence

func <| <T: Decodable>(rhs: JSON, lhs: String) throws -> T {
    return try rhs.decode(path: lhs)
}

// モデルを定義
struct User: Decodable {
    let name: String
    let age: Int
    static func decode(_ j: JSON) throws -> User {
        return try User(
            name: j <| "name",
            age: j <| "age")
    }
}

// JSONデータを用意
let json: Any = [
    "name": "User500",
    "age": 18
]

// デコード
if let json = JSON(rawValue: json),
    let user = try? User.decode(json) {
        print(user.name) // -> User500
        print(user.age) // -> 18
}

とりあえずAny型のJSONデータをデコードできるenumが完成した。あとはネストを考慮したり再起部分を繰り返し処理に変えればもうちょっとましになるかもしれない。 さらに冒頭で考えてた実装をまだ実現できていないので、まだまだ改良の余地がありそう。(それがやりたいなら別にenum使わなくても良かった…)

※1…内部的にキーを連結したものからハッシュが計算可能であればこの限りではない

UITextViewでハッシュタグとメンションを色を変えて表示とタップ検知をする

UITextViewで複数のハイライトを表現したい

最近の実装でSNSなどの普及でか#swiftなどのハッシュタグに加えて@rinovなど個別にハイライトして、タップしたときの挙動も柔軟に指定したい時がありました。 基本的には標準のNS***AttributeNameなどで該当の単語ごとにNSRangeを求めて属性を追加するのですが、この実装方法はかなり良くないと感じました。

Attribute Stringの問題点

UITextViewを用いて文字を装飾したい場合にはAttributedStringで属性と値を指定することで実現します。

例: UITextViewのテキストを赤くする

textView.text = "Hello World"
let attributedText = textView.mutableCopy() as? NSMutableAttributedString
attributedText.addAttribute(NSForegroundColorAttributeName, value: UIColor.red, range: NSMakeRange(0, 5))
textView.attributedText = attributedText

問題点

  • NS***AttributeNameというグローバルな値が属性のキーになっているため一覧性がない
  • UITextViewaddAttributeは値がAny型となっているため、例えばテキストカラーを設定するときにUIColorが設定されることが自明でありながら.redなどの省略が行えない。また、どんな値でも引数に渡せてしまい安全でない。
  • NSMutable~, NSRange, NS***AttributeNameなどObjective-Cの遺産を多く使用している。
  • ハイライトする単語のNSRangeを毎回算出するのが面倒である

上記の例では色を付けるだけでしたが多くの場合特定のキーワードを個別にハイライトしたりタップ時の挙動を柔軟に変更したいです。 UITextViewのプロパティとしてlinkTextAttributesというものがありますが、これはリンク属性の付いたテキストの見た目を一括で装飾の指定を行うことができますが、例えば、ハッシュタグは青色、メンションは赤色など個別に対応した属性の指定を行うことはできません。

// 単語ごとに個別の指定は行えない
textView.linkTextAttributes = [NSForegroundColorAttributeName: UIColor.red]

こういったObjective-CとSwiftの間でコーディングしている感があり、今後Swiftのバージョンアップした時に既存のコードを全て実装しなおすリスクも考えるとなかなか気が進みません。 そこで最近のリッチなテキストを柔軟にカスタマイズしたいと思い、UITextViewで実装したものをライブラリ化しました。

RegeributedTextView

https://github.com/rinov/RegeributedTextView

使い方はREADME.mdまたはhttp://qiita.com/rinov/items/da450d0ba9dffaaf8967にまとめました。

調べた限りでもTTTAttributedLabelなど有名なライブラリ(UILabel専用)がありますが、Swift製で正規表現 + 独自のTextAttributeプロパティを追加しているライブラリはありませんでした。複数単語のハイライトやタップした単語ごとに任意の処理をしたいなどがありましたら一度使用してみていただけると嬉しいです。 またGithubでIssueやPR等いただけるとさらに嬉しいです。

github.com