スポンサーサイト

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

F#雑記 小町リング

Gushwellさんの記事 にある「小町リング」をF#でやってみました。
 
方針としては手計算と同じで、まず最初の2数を選びます。するとこの2数がすべての円共通の3数の和(左端と右端の円は除く)となります。次に残った数の中から一つ選びます、すると次に入るべきなのは和から選んだ数およびその前に置いた数を引いた数になるので、これが残った数に存在すれば、これを置きます。あとは同様な操作の繰り返しです。円の中に3数あり、左端の数を置く時と、真ん中の数を置く場合では手順が違うので2つの関数を利用します。
searchMiddleは真ん中の数を置こうとしている場合に使う関数で、これは置く数に選択性をもちます。
searchInterは端っこの数を置く場合で、これは置く数が自動的に決定されます。
 
ということでコードは次の通りです。
 
> let rec searchMiddle (cSum:int) (mdList:list<int>) (rem:Set<int>) =
    let lastVal = List.head mdList //直前に入れた数
    if rem.Count = 1  then
        let lastRemVal = List.head (List.ofSeq rem) //最後に残った数
        if(lastVal + lastRemVal = cSum) then
           printfn "%A"  (List.rev (lastRemVal :: mdList))
           
    else
       for a in rem do
         if Set.contains (cSum - lastVal - a) rem then
            searchInter cSum (a :: mdList) (rem - (Set.ofList [a]))
 
and searchInter (cSum:int) (mdList:list<int>) (rem:Set<int>) =
    let lv1 = List.head mdList //直前に入れた数
    let lv2 = List.head (List.tail mdList)//直前の前に入れた数
    let cand = cSum - lv1 - lv2
    if Set.contains cand rem then
        searchMiddle cSum (cand :: mdList) (rem - (Set.ofList [cand]))
 
let solve () =
    for a1 in Set.ofList[1 .. 9] do 
        for a2 in Set.ofList[1 .. 9] - Set.ofList [a1] do
            searchMiddle (a1+a2) ([a1;a2]) (Set.ofList([1 .. 9]) - Set.ofList [a1] - Set.ofList [a2]);;
 
val searchMiddle : int -> int list -> Set<int> -> unit
val searchInter : int -> int list -> Set<int> -> unit
val solve : unit -> unit
 
実行してみます。
 
> solve ();;
[9; 2; 5; 4; 6; 1; 7; 3; 8]
[8; 3; 7; 1; 6; 4; 5; 2; 9]
[9; 4; 1; 8; 3; 2; 5; 6; 7]
[7; 6; 5; 2; 3; 8; 1; 4; 9]
[7; 6; 5; 2; 8; 3; 1; 9; 4]
[8; 6; 1; 7; 4; 3; 2; 9; 5]
[4; 9; 1; 3; 8; 2; 5; 6; 7]
[5; 9; 2; 3; 4; 7; 1; 6; 8]
val it : unit = ()
 
 
なお結果をリストに入れて返すには例えば次のように変更します。
 
> let rec searchMiddle2 (cSum:int) (mdList:list<int>) (rem:Set<int>) =
  [  
    let lastVal = List.head mdList //直前に入れた数
    if rem.Count = 1  then
        let lastRemVal = List.head (List.ofSeq rem) //最後に残った数
        if(lastVal + lastRemVal = cSum) then
           yield  (List.rev (lastRemVal :: mdList))
           
    else
       for a in rem do
         if Set.contains (cSum - lastVal - a) rem then
            yield! (searchInter2 cSum (a :: mdList) (rem - (Set.ofList [a])))
    ]
and searchInter2 (cSum:int) (mdList:list<int>) (rem:Set<int>) =
  [  
    let lv1 = List.head mdList //直前に入れた数
    let lv2 = List.head (List.tail mdList)//直前の前に入れた数
    let cand = cSum - lv1 - lv2
    if Set.contains cand rem then
        yield! (searchMiddle2 cSum (cand :: mdList) (rem - (Set.ofList [cand])))
  ]
 
let solve2 () =
  [ 
    for a1 in Set.ofList[1 .. 9] do 
        for a2 in Set.ofList[1 .. 9] - Set.ofList [a1] do
            let result = searchMiddle2 (a1+a2) ([a1;a2]) (Set.ofList([1 .. 9]) - Set.ofList [a1] - Set.ofList [a2])
            if result <> [] then
                yield! result
  ];;
 
val searchMiddle2 : int -> int list -> Set<int> -> int list list
val searchInter2 : int -> int list -> Set<int> -> int list list
val solve2 : unit -> int list list
 
> solve2 ();;
 
val it : int list list =
  [[9; 2; 5; 4; 6; 1; 7; 3; 8]; [8; 3; 7; 1; 6; 4; 5; 2; 9];
   [9; 4; 1; 8; 3; 2; 5; 6; 7]; [7; 6; 5; 2; 3; 8; 1; 4; 9];
   [7; 6; 5; 2; 8; 3; 1; 9; 4]; [8; 6; 1; 7; 4; 3; 2; 9; 5];
   [4; 9; 1; 3; 8; 2; 5; 6; 7]; [5; 9; 2; 3; 4; 7; 1; 6; 8]]

スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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