スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#雑記 spiral 

 anarchy golf の問題を解いてみました。 
問題は2次元配列について、左上から始めて時計回りで、indexを表示せよというものです。 
例えば 
 
n = 4という入力に対しては 
 
4次元配列 
(0,3) (1,3) (2,3) (3,3)  
(0.2) (1,2) (2,2) (3,2)  
(0.1) (1,1) (2,1) (3,1)  
(0,0) (1,0) (2,0) (3,0  
が対応し 
 
[(0, 3); (1, 3); (2, 3); (3, 3); (3, 2); (3, 1); (3, 0); (2, 0); (1, 0); 
   (0, 0); (0, 1); (0, 2); (1, 2); (2, 2); (2, 1); (1, 1)] 
    
が出力となるような関数を定義します。 
 
 
まず 
 
(-1,3) (0,3) (1,3) (2,3) (3,3)  
       (0.2) (1,2) (2,2) (3,2)  
       (0.1) (1,1) (2,1) (3,1)  
       (0,0) (1,0) (2,0) (3,0)  
 
と左上の左に一個成分を付け加えておきます。この数を開始点とすると 
 
(1.0)を座標に加えていくことを4回、次に向きをかえて、(0,-1)を加えていくことを3回、 
向きを変えて(-1,0)を加えていくことを3回、向きを変えて(0,1)を加えていくことを2回 
向きを変えて(1,0)を加えていくことを2回、向きを変えて(0,-1)を加えていくことを1回 
向きを変えて(-1,0)を1回加えて終了です。 
 
変化する前の向きを(vx,vy)だとすると、変化した後の向きは(vy,-vx)です。 
また回数に着目するとn=4に対して[4;3;3;2;2;1;1]という数列は次の様にして求めることができます。 
 
> let calcEachCount n = 
    [(2*n) .. -1 .. 2] 
    |> List.map (fun x -> x/2);; 
 
val calcEachCount : int -> int list 
 
> calcEachCount 4;; 
val it : int list = [4; 3; 3; 2; 2; 1; 1] 
 
あとは上のリストのそれぞれの数の回数分だけ移動しては、向きを変えるようにすればよいので、関数を次のように定義します。 
 
> let rec makeSpiralSub lst (vx,vy) (x,y) res = 
    match lst with 
    |h :: tl when h > 1 -> makeSpiralSub ((h-1)::tl) (vx,vy) (x+vx,y+vy) ((x+vx,y+vy)::res) 
    |h :: tl when h = 1 -> makeSpiralSub        tl   (vy,-vx) (x+vx,y+vy) ((x+vx,y+vy)::res) 
    |_ -> List.rev res;; 
 
val makeSpiralSub : 
  int list -> int * int -> int * int -> (int * int) list -> (int * int) list 
 
使ってみます。 
 
> makeSpiralSub [4;3;3;2;2;1;1] (1,0) (-1,3) [];; 
val it : (int * int) list = 
  [(0, 3); (1, 3); (2, 3); (3, 3); (3, 2); (3, 1); (3, 0); (2, 0); (1, 0); 
   (0, 0); (0, 1); (0, 2); (1, 2); (2, 2); (2, 1); (1, 1)] 
    
 では一般化します。 
  
 > let makeSpiral n =  
 
    let rec makeSpiralSub lst (vx,vy) (x,y) res = 
        match lst with 
        |h :: tl when h > 1 -> makeSpiralSub ((h-1)::tl) (vx,vy) (x+vx,y+vy) ((x+vx,y+vy)::res) 
        |h :: tl when h = 1 -> makeSpiralSub        tl   (vy,-vx) (x+vx,y+vy) ((x+vx,y+vy)::res) 
        |_ -> List.rev res 
 
    let calcEachCount n = 
        [(2*n) .. -1 .. 2] 
        |> List.map (fun x -> x/2) 
 
    makeSpiralSub (calcEachCount n) (1,0) (-1,n-1) [];; 
 
val makeSpiral : int -> (int * int) list 
 
(実行例) 
> makeSpiral 1;; 
val it : (int * int) list = [(0, 0)] 
 
> makeSpiral 2;; 
val it : (int * int) list = [(0, 1); (1, 1); (1, 0); (0, 0)] 
 
> makeSpiral 3;; 
val it : (int * int) list = 
  [(0, 2); (1, 2); (2, 2); (2, 1); (2, 0); (1, 0); (0, 0); (0, 1); (1, 1)] 
 
> makeSpiral 5;; 
val it : (int * int) list = 
  [(0, 4); (1, 4); (2, 4); (3, 4); (4, 4); (4, 3); (4, 2); (4, 1); (4, 0); 
   (3, 0); (2, 0); (1, 0); (0, 0); (0, 1); (0, 2); (0, 3); (1, 3); (2, 3); 
   (3, 3); (3, 2); (3, 1); (2, 1); (1, 1); (1, 2); (2, 2)] 
 
> makeSpiral 6;; 
val it : (int * int) list = 
  [(0, 5); (1, 5); (2, 5); (3, 5); (4, 5); (5, 5); (5, 4); (5, 3); (5, 2); 
   (5, 1); (5, 0); (4, 0); (3, 0); (2, 0); (1, 0); (0, 0); (0, 1); (0, 2); 
   (0, 3); (0, 4); (1, 4); (2, 4); (3, 4); (4, 4); (4, 3); (4, 2); (4, 1); 
   (3, 1); (2, 1); (1, 1); (1, 2); (1, 3); (2, 3); (3, 3); (3, 2); (2, 2)]  
    
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

trackback


この記事にトラックバックする(FC2ブログユーザー)

spiral

【F#】spiral

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。