スポンサーサイト

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

F#雑記  trimming

 Anarchy_Golfの次の問題をF#でやってました 
http://golf.shinh.org/p.rb?trimming 
 
________*_____________________ 
_______*___*__________________ 
______*_______*_______________ 
_____*___________*____________ 
________*_______*_____________ 
___________*___*______________ 
______________*_______________ 
 
を下のようにするという問題です。_の部分は本当は空白ですが、表示がずれるので_で表しています。 
 
___*_________ 
__*___*______ 
_*_______*___ 
*___________* 
___*_______*_ 
______*___*__ 
_________*___ 
 
配列で表し上下左右のいらない部分を省くことにします。 
 
例えば 
> let testArr : char[,] = Array2D.create 5 3 ' ' 
testArr.[3,2] <- 'c' 
testArr.[1,1] <- 'd';; 
 
val testArr : char [,] = 
 [[' '; ' '; ' '] 
  [' '; 'd'; ' '] 
  [' '; ' '; ' '] 
  [' '; ' '; 'c'] 
  [' '; ' '; ' ']] 
 
としたときに 
 
> trimArr testArr;; 
val it : char [,] = 
 [['d'; ' '] 
  [' '; ' '] 
  [' '; 'c']] 
 
となるような関数trimArrを定義してみたいと思います。 
 
まず2次元配列内をどのような順番で調べていくかのインデックスのシークエンスを返す関数を定義します。 
 
> let mk2Ds (outerExcM:int) (innerExcM:int) (f:int*int->int*int) = 
    seq{ 
        for outi in seq{0 .. (outerExcM - 1)}do 
            for ini in seq{0 .. (innerExcM - 1)} do 
                yield f(outi,ini) 
       } 
;; 
 
val mk2Ds : int -> int -> (int * int -> int * int) -> seq<int * int> 
 
例えば左上から右、突き当たると次の下の行というのは、次の様に得ることができます。 
> mk2Ds 5 3 (fun (o,i) -> (o,i));; 
val it : seq<int * int> = seq [(0, 0); (0, 1); (0, 2); (1, 0); ...] 
右下から上、突き当たると次の左の列というのは次の様に得ることができます。 
> mk2Ds 3 5 (fun (o,i) -> (5-1-i,3-1-o));; 
val it : seq<int * int> = seq [(4, 2); (3, 2); (2, 2); (1, 2); ...] 
 
それでは次に、配列の要素を一つずつ調べて行って、条件を満たす最初のインデックスに対し関数を適用した値を返す関数を定義します。 
 
> let tryF2D (pred :int*int -> bool) (extrc : int*int -> int) (inSeq : seq<int*int>)= 
     match (Seq.tryFind pred inSeq) with 
     |None -> None 
     |Some(i,j) -> Some(extrc (i,j)) 
;; 
 
val tryF2D : 
  (int * int -> bool) -> (int * int -> int) -> seq<int * int> -> int option 
 
では準備ができたので、本体を定義します。こんな小さな数列では意味はない(逆に遅くなる)のですが、parallelで処理するようにしてみました。 
 
> let trimArr (arr:char[,]) = 
    let cM = Array2D.length1 arr 
    let rM = Array2D.length2 arr 
    let pred = (fun (i,j) -> arr.[i,j] <> ' ' ) 
    let search1 = (fun () -> tryF2D pred (fun (i,j) -> i) (mk2Ds cM rM (fun (o,i) -> (o,i)))) 
    let search2 = (fun () -> tryF2D pred (fun (i,j) -> i) (mk2Ds cM rM (fun (o,i) -> (cM-1-o,rM-1-i)))) 
    let search3 = (fun () -> tryF2D pred (fun (i,j) -> j) (mk2Ds rM cM (fun (o,i) -> (i,o)))) 
    let search4 = (fun () -> tryF2D pred (fun (i,j) -> j) (mk2Ds rM cM (fun (o,i) -> (cM-1-i,rM-1-o)))) 
    let tasksRes = [|search1;search2;search3;search4|] 
                     |> Array.map (fun f -> Func<int option> f) 
                     |> Array.map (fun del -> Task.Factory.StartNew<int option> del) 
                     |> Array.map (fun t -> t.Result) 
    if tasksRes.[0].IsNone then failwith "配列が空です" 
    let (rtMin,rtMax,ctMin,ctMax) = tasksRes.[0].Value,tasksRes.[1].Value,tasksRes.[2].Value,tasksRes.[3].Value 
    Array2D.initBased 0 0 (rtMax-rtMin+1) (ctMax-ctMin+1) (fun r c -> arr.[rtMin+r,ctMin+c]) 
;; 
 
val trimArr : char [,] -> char [,] 
 
全コードは下の通りです。 
 
open System 
open System.Threading 
open System.Threading.Tasks 
 
let mk2Ds (outerExcM:int) (innerExcM:int) (f:int*int->int*int) = 
    seq{ 
        for outi in seq{0 .. (outerExcM - 1)}do 
            for ini in seq{0 .. (innerExcM - 1)} do 
                yield f(outi,ini) 
       } 
 
let tryF2D (pred :int*int -> bool) (extrc : int*int -> int) (inSeq : seq<int*int>)= 
     match (Seq.tryFind pred inSeq) with 
     |None -> None 
     |Some(i,j) -> Some(extrc (i,j)) 
 
let trimArr (arr:char[,]) = 
    let cM = Array2D.length1 arr 
    let rM = Array2D.length2 arr 
    let pred = (fun (i,j) -> arr.[i,j] <> ' ' ) 
    let search1 = (fun () -> tryF2D pred (fun (i,j) -> i) (mk2Ds cM rM (fun (o,i) -> (o,i)))) 
    let search2 = (fun () -> tryF2D pred (fun (i,j) -> i) (mk2Ds cM rM (fun (o,i) -> (cM-1-o,rM-1-i)))) 
    let search3 = (fun () -> tryF2D pred (fun (i,j) -> j) (mk2Ds rM cM (fun (o,i) -> (i,o)))) 
    let search4 = (fun () -> tryF2D pred (fun (i,j) -> j) (mk2Ds rM cM (fun (o,i) -> (cM-1-i,rM-1-o)))) 
    let tasksRes = [|search1;search2;search3;search4|] 
                     |> Array.map (fun f -> Func<int option> f) 
                     |> Array.map (fun del -> Task.Factory.StartNew<int option> del) 
                     |> Array.map (fun t -> t.Result) 
    if tasksRes.[0].IsNone then failwith "配列が空です" 
    let (rtMin,rtMax,ctMin,ctMax) = tasksRes.[0].Value,tasksRes.[1].Value,tasksRes.[2].Value,tasksRes.[3].Value 
    Array2D.initBased 0 0 (rtMax-rtMin+1) (ctMax-ctMin+1) (fun r c -> arr.[rtMin+r,ctMin+c]) 
スポンサーサイト

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

trackback


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

trimming

【F#】trimming

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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