与えられた並べ替えを実現するあみだくじの生成
Posted feedbacks - Scala
ソートを掛ける方法で。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | class CGhostLeg(g:List[Int]) {
val s:List[Int] = g.sort { (a,b) => a < b }
var p:List[List[Boolean]] = List()
def create:CGhostLeg = {
def _calc(c:List[Int],r:Tuple2[List[Int],List[Boolean]]):Tuple2[List[Int],List[Boolean]] = c match {
case List() => r
case h::List() => (r._1+h,r._2)
case h::t => h.compare(t.head) match {
case p if p > 0 => _calc(c.slice(2).asInstanceOf[List[Int]],(r._1+c.apply(1)+h,r._2+true++(t match { case h::List() => List(); case _ => List(false) })))
case _ => _calc(t,(r._1+h,r._2+false))
}
case _ => r
}
def _step(c:List[Int]):Unit = {
val n = _calc(c,(List(),List()))
p = n._2::p
if (!n._1.zip(s).filter { d => d._1 != d._2 }.isEmpty) _step(n._1)
}
_step(g)
this
}
def print:Unit = {
def _join(d:String,l:List[String]):String = l.head + l.tail.foldLeft("") { (s,e) => s + d + e }
println(_join(" ",s.map { e => e.toString }))
p.foreach { l =>
println(_join("|",""::(l.map { e => e match { case true => "-"; case _ => " " } })+""))
}
println(_join(" ",g.map { e => e.toString }))
}
}
object GhostLeg {
def main(args:Array[String]):Unit = {
try {
var g:List[Int] = args.length match {
case 0 => List(3,5,2,4,0,1)
case _ => args.toList.map { s => s.toInt }
}
(new CGhostLeg(g)).create.print
} catch {
case e => e.printStackTrace
}
}
}
|
shiro
#4704()
Rating13/13=1.00
お題#4476を見て思いつきました。
0からn (n>=1) までの数字を任意の順で並べたリストが与えられた時、0からnまでが順に並んだ状態から出発して、与えられたリストの順で結果が得られるようなあみだくじを作成して出力するプログラムを書いてください。
与えられたリストが (3 5 2 4 0 1) の場合、出力の1例を示します：
一応、制約条件を示しておきます。
一つのリストに対して複数の解があり得ます。ナイーブな解に飽き足らなければ出力行数をなるべく少なくする解を求める方法を考えてみてください。
[ reply ]