Hanafuda Shuffle を関数型言語で。

質問

関数型言語を学んだのですが、あまり概念がよくわかっておりません。

以下のような問題があるとき、関数型言語ではどのように解決すれば良いのでしょうか。

Hanafuda Shuffle
http://www.deqnotes.net/acmicpc/1978/ja

考え方等だけでも大変参考になるのですが、可能であればHaskellやScalaで解いて頂きたいです。
宜しくお願いします。

回答No.3

T_GYOUTEN

Ｆ＃でごめんなさい。下を実行して問題文のように入力すると

data = (5, 2, [(3, 1); (3, 1)]) ans = 4
data = (10, 3, [(1, 10); (10, 1); (8, 3)]) ans = 4

と表示されます。(なお文頭の半角スペースがうまく表示できないので、半角スペースの代わりに全角スペースを使ってます。）

//(方針）カードの位置は一番下を1、一番上をnとする
//逆写像を次々に施して位置n（一番上）にあるものが、どの位置に戻っていくかを調べる。最初の状態で位置と
//カードの数字は同じなので、位置を答えれば答えとなる。

///問題にあるような入力をしたとき[(5, 2, [(3, 1); (3, 1)]); (10, 3, [(1, 10); (10, 1); (8, 3)])]を返す関数
let　inputData　()　=
　　　　let　rec　inputDataSub　subNum　subCountMax　subCount　　subLstAcc　acc　=
　　　　　　　　let　oneLineIntsArr　=　
　　　　　　　　　　　　(System.Console.ReadLine()).Split([|'　'|])
　　　　　　　　　　　　　　　　|>Array.map(fun　str　->　System.Int32.Parse(str.Trim()))
　　　　　　　　match　oneLineIntsArr　with
　　　　　　　　|[|0;0|]　　　　　->　List.rev　(List.tail　((subNum,subCountMax,subLstAcc)::acc))　//最後
　　　　　　　　|[|x;y|]　　when　subCount　=　0　//グループの始まり
　　　　　　　　　　　　　　　　　　　　　->　inputDataSub　　x　　y　1　[]　acc　
　　　　　　　　|[|x;y|]　　when　subCount　=　subCountMax　//グループの終わり
　　　　　　　　　　　　　　　　　　　　　->　inputDataSub　　0　0　0　[]　((subNum,subCountMax,(List.rev　((x,y)::subLstAcc)))::acc)　　　　
　　　　　　　　|[|x;y|]　　　　　->inputDataSub　subNum　subCountMax　(subCount+1)　((x,y)::subLstAcc)　acc　//グループ途中
　　　　　　　　|_　->　failwith　"input　error"

　　　　inputDataSub　0　0　0　[]　[]　

//　getTopNum　(5,　2,　[(3,　1);　(3,　1)])で4を返す関数
let　getTopNum　(n,shouffleCount,p_c_lst)　=
　　　　　　　let　f_inv　n　(p,c)　　=　(fun　x　->　if　x　>　n-c　then　x-p+1　elif　x　<=　n-c-p　then　x　else　x　+　c)//逆写像　
　　　　　　　let　applyFuncLst　=　List.map　(f_inv　n)　(List.rev　p_c_lst)　
　　　　　　　List.fold　(fun　pos　g　->　g　pos)　n　applyFuncLst　//場所nから逆写像でどんどん戻していく

//「入力Dataと答えのタプル」のリスト
let　DataAndAnsLst　=
　　　　inputData　()
　　　　　　　　|>　List.map　(fun　ele　->　(ele,getTopNum　ele))

//表示　　　　　　　　
List.iter(fun　(data,ans)　->printfn　"data　=　%A　ans　=　%A"　data　ans　)　DataAndAnsLst

回答No.2

dscripty

入門して 2週間後 1年半のブランク、全然かけない。とほほ。
とりあえず動くようにはなったけど、無駄が多くて参考になるかどうか。

$ cat | scala Shuffle
5 2
3 1
3 1
10 3
1 10
10 1
8 3
0 0
log => List(3, 5, 4, 2, 1)
log => List(4, 3, 5, 2, 1)
log => List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
log => List(1, 10, 9, 8, 7, 6, 5, 4, 3, 2)
log => List(4, 3, 2, 1, 10, 9, 8, 7, 6, 5)
4
4

$

[Shuffle.scala]
object Shuffle {

  // 一回だけシャフルする関数
  // desk:List[Int] ※ カードの山
  // ds:(Int, Int) ※ データセット p が ds._1 で c が ds._2
  def shuffle_once( deck:List[Int], ds:(Int, Int) ):List[Int] = {
    val (topList, tailList) = deck.splitAt(ds._1-1)
    val (middleList, bottomList) = tailList.splitAt(ds._2)
    // 最後の式が返される
    println("log => " + (middleList ::: topList ::: bottomList).toString) // 状態確認用
    middleList ::: topList ::: bottomList
  }

  // データセットの数だけ再帰
  def shuffle( deck:List[Int], ds:List[(Int, Int)] ):List[Int] = ds match {
    case List() => deck
    case _ => shuffle( shuffle_once(deck, ds.head), ds.tail )
  }

  // 入力データを分割して (カードの山, データセット) のリストを作成
  // input:List[(Int, Int)] ※ 最後が (0, 0) のタプルで入力終了。そのあとは無視。
  // 出力 ※ (List[Int], List[(Int, Int)]) shuffle 関数の入力
  def devideDataSet(input:List[(Int, Int)]):List[(List[Int], List[(Int, Int)])] = input match {
    case List() => List()
    case head::tail => if ( (0, 0) == head ) List() else {
      val (n, r) = head
      val (ds, next) = tail.splitAt(r)
      ((1 to n).reverse.toList, ds) :: devideDataSet(next)
    }
  }

  // String を (Int, Int) へ変換、エラーは null を返す
  def toIntInt(s:String):(Int, Int) = s.split(' ') match {
    case Array(a, b) => try { (a.toInt, b.toInt) } catch { case _ => null }
    case _ => null
  }

  // 標準入力を List[String] へ変換
  def fromStdin():List[String] = readLine match {
    case null => List()
    case s => s::fromStdin()
  }

  def main(args: Array[String]) {

    // 標準入力から読み込んで、異常な行は読み飛ばす
    val input:List[(Int,Int)] = fromStdin().map(toIntInt(_)).filter{
      case null => false
      case _ => true
    }

    // 入力から読み込んだ List[(Int,Int)]
    // → List((カードの山, データセット))
    // → List(カードの山をデータセットの方法でシャフルした結果の一番上のカード)
    // のそれぞれを出力
    devideDataSet(input).map(el => shuffle(el._1,el._2).head).foreach(println(_))
  }
}

回答No.1

hitomura

入力の解析と値のチェックは省略します。
以下をコンパイルして、
hanafuda_shuffle:exec([[（nの値）, （rの値）], [（1番目のpの値）, （1番目のcの値）], [（2番目のpの値）, （2番目のcの値）], …, [（(r - 1)番目のpの値）, （(r - 1)番目のcの値）], [0, 0]]).
と入力してやれば求める結果がでるはずです。

-module(hanafuda_shuffle).

-export([exec/1]).

shuffle(Pile, []) -> % (3)
Pile;
shuffle(Pile, [[0, 0] | _Rest]) -> % (4)
Pile;
shuffle(Pile, [[P, C] | Rest]) -> % (2)
{First, Others} = lists:split(Pile, P - 1),
{Second, Third} = lists:split(Others, C),
shuffle(lists:append(Second, First, Third), Rest);

exec([[N, R] | Shuffle]) ->
[Top | _] = shuffle(lists:seq(N, 1, -1), Shuffle), % (1)
Top.

ただ、listsモジュールに依存していることが問題ですが……あ、Erlangは解いてほしい言語の指定にありませんでしたね。
（まじめな話、自分は関数型言語はErlangしか知らない）

とりあえず、流れとしては
(1)：降順に並んだ山札を作成し（lists:seq(N, 1, -1)）、それと並べ替え手順の列とでshuffle関数を呼び出します。
(2)：並べ替え手順の列から先頭の手順を取り出し、その値によって山札をFirst, Second, Thirdの3つに分けます。そしてそれをSecond, First, Thirdの順に連結しなおして新たな山札とし、手順を取り出した残りの並べ替え手順の列とともにshuffle関数を呼び出します。
（ErlangではリストLの先頭の値を取り出す場合[T | R] = Lと書きます。Lの先頭の値がTに、Lから先頭を取り除いたリストがRに入ります）
(3), (4)：上記の処理を並べ替え手順の列が空になる(3)か手順が0, 0だった(4)ときまで行われます。このとき、その時点での山札がその時点での関数の戻り値になります。
（Erlangは関数内で最後に評価した値がその関数の戻り値となります。このばあい、ただ"Pile"と書いてあるので、ここでPileの値が評価され、それが関数の最後の評価なのでPileの値が戻り値となります）
(2)：shuffle関数を呼び出した結果をそのまま戻り値にします。
(1)：shuffle関数から戻ってきた山札を先頭とそれ以外に分けます。そして、先頭の値を処理結果とします。
となります。

上記が参考になれば幸いです。lists:***のコードも書いてほしいと言うのであれば補足願います（処理の本質と関係ないので必要ないと思いますが）。

補足

ありがとうございます！
ソースコードが簡潔に書かれていて美しいですね！

おかげさまで大枠を掴むことができました。

ところで、関数型言語は変数の扱いが特殊と聞くのですが、
インプットした値をあとで使うように変数で保持することはできないのでしょうか。

可能ならば、題意の通り、
input
5 2
3 1
3 1
10 3
1 10
10 1
8 3
0 0

output
4
4

と出力してみたいのですが。

また、HaskellやScalaで解ける方がいらっしゃいましたら、是非参考にしてみたいです。

宜しくお願いします。