スポンサーサイト

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

F#雑記 Character distance

 arnarchy golf のCharacter distanceという問題をやってみました。
(arnarchy golfは短いプログラムを競う所ですが、単なる問題として解いてます) 
 
問題は「使われているどの文字も出現回数が2回である文字列があります。使われている文字の距離を出現順に表示しなさい。」というものです。 
例えば"adcbcbad"であれば 
 
a :  6 
d :  6 
c :  2 
b :  2 
 
という表示になります。 
 
まず、次のような補助関数を定義します。これは、使われている文字の距離一覧と、出現別のリストをタプルで返す関数です。 
 引数のfst_ap_mapは文字とその文字が最初に出現した位置とを対応させるMapです。 
 
> let rec dstSub  (dist_map:Map<char,int>,uniq_charLst:list<char>)(fst_ap_map:Map<char,int>) (cur_pos:int) (charLst:list<char>) = 
    match charLst with 
    | [] -> (dist_map, List.rev uniq_charLst) 
    | hd::tl ->  if not(fst_ap_map.ContainsKey hd) then 
                    dstSub (dist_map, hd::uniq_charLst) (Map.add hd cur_pos fst_ap_map) (cur_pos + 1) tl 
                    else 
                    dstSub (Map.add hd (cur_pos - fst_ap_map.[hd]) dist_map, uniq_charLst) fst_ap_map (cur_pos + 1) tl 
;; 
 
val dstSub : 
  Map<char,int> * char list -> 
    Map<char,int> -> int -> char list -> Map<char,int> * char list 
 
使用例 
 
> dstSub (Map.empty,[]) Map.empty 0 ['a';'d';'c';'b';'c';'b';'a';'d'];; 
val it : Map<char,int> * char list = 
  (map [('a', 6); ('b', 2); ('c', 2); ('d', 6)], ['a'; 'd'; 'c'; 'b'])   
 
では、これを利用して目的の関数を定義します。 
 
> let dispDistances (ori_source:string) = 
    let rec dstSub  (dist_map:Map<char,int>,uniq_charLst:list<char>)(fst_ap_map:Map<char,int>) (cur_pos:int) (charLst:list<char>) = 
        match charLst with 
        | [] -> (dist_map, List.rev uniq_charLst) 
        | hd::tl ->  if not(fst_ap_map.ContainsKey hd) then 
                        dstSub (dist_map, hd::uniq_charLst) (Map.add hd cur_pos fst_ap_map) (cur_pos + 1) tl 
                        else 
                        dstSub (Map.add hd (cur_pos - fst_ap_map.[hd]) dist_map, uniq_charLst) fst_ap_map (cur_pos + 1) tl 
    
    let resDistMap, resUniqCharLst = 
        ori_source.ToCharArray() 
        |>List.ofArray 
        |>dstSub (Map.empty,[]) Map.empty 0 
    
    resUniqCharLst 
    |>List.iter (fun x -> printfn "%c :%3d" x resDistMap.[x]);; 
 
val dispDistances : string -> unit 
 
(実行例) 
> dispDistances "adcbcbad";; 
a :  6 
d :  6 
c :  2 
b :  2 
val it : unit = () 
 
(実行例) 
> dispDistances "ekh5.acwed4db:lls4f3z@x.6f2sw35pub@:x6uo;k2czraj;hjpor";; 
e :  8 
k : 40 
h : 47 
5 : 27 
. : 19 
a : 41 
c : 37 
w : 21 
d :  2 
4 :  7 
b : 21 
: : 22 
l :  1 
s : 11 
f :  7 
3 : 10 
z : 24 
@ : 13 
x : 14 
6 : 13 
2 : 16 
p : 20 
u :  6 
o : 13 
; :  8 
r :  8 
j :  3 
val it : unit = () 
スポンサーサイト

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

trackback


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

Character distance

【F#】Character distance

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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