1時間以内に解けなければプログラマ失格となってしまう5つの問題をscalaで

いまさらながらscalaの勉強を兼ねて実際に解いてみました

intellijのscala worksheetを使いましたがとても便利ですね

問題1

forループ、whileループ、および再帰を使用して、リスト内の数字の合計を計算する3つの関数を記述せよ。

// forループ、whileループ、および再帰を使用して、リスト内の数字の合計を計算する3つの関数を記述せよ。
object P01 {
  def listTotalUsingFor(args: List[Int]) : Int = {
    var sum = 0
    for(n <- args){
      sum += n
    }
    sum
  }

  def listTotalUsingWhile(args: List[Int]) : Int = {
    var sum = 0
    val it  = args.toIterator
    while(it.hasNext){
      sum += it.next()
    }
    sum
  }

  def listTotalUsingRecurse(args: List[Int]) : Int = {
    args match {
      case Nil => 0
      case first::rest => first + listTotalUsingRecurse(rest)
    }
  }
}

val list = List(1,2,3,4,5)
printf("%s: %d\t","Using For",     P01.listTotalUsingFor(list))
printf("%s: %d\t","Using While",   P01.listTotalUsingWhile(list))
printf("%s: %d\t","Using Recurse", P01.listTotalUsingRecurse(list))

問題2

交互に要素を取ることで、2つのリストを結合する関数を記述せよ。たとえば [a, b, c]と[1, 2, 3]という2つのリストを与えると、関数は [a, 1, b, 2, c, 3]を返す。

// 交互に要素を取ることで、2つのリストを結合する関数を記述せよ。例えば [a,, c]と[1,, 3]という2つのリストを与えると、関数は [a,,,,, 3]を返す。

object P02 {
  def toInterchangeList(listA: List[Any], listB: List[Any]): List[Any] = {
    (listA,listB) match {
      case (aFirst::aRest,bFirst::bRest) => aFirst::bFirst::toInterchangeList(aRest,bRest)
      case (aFirst::aRest, bFirst::Nil)  => aFirst::bFirst::toInterchangeList(aRest,List())
      case (aFirst::aRest, List())       => aFirst::toInterchangeList(aRest,List())
      case (aFirst::Nil, bFirst::bRest)  => aFirst::bFirst::toInterchangeList(List(),bRest)
      case (List(), bFirst::bRest)       => bFirst::toInterchangeList(List(),bRest)
      case (_,_) => List()
    }
  }
}
val sameA = List(1,2,3)
val sameB = List("a","b","c")
printf("%s: %s","same size A and B", P02.toInterchangeList(sameA,sameB))

val largeA = List(1,2,3,4,5,6)
val smallB = List("a","b","c")
printf("%s: %s","A is greater than B", P02.toInterchangeList(largeA,smallB))

val smallA = List(1,2,3)
val largeB = List("a","b","c","d","e","f")
printf("%s: %s","A is less than B", P02.toInterchangeList(smallA,largeB))

最初zipとか使っていけるかと色々試したものの要素数が違う場合にうまく処理できなかったので断念

matchを使って処理を分岐させました

多分もっと良い書き方はありそう

問題3

最初の100個のフィボナッチ数のリストを計算する関数を記述せよ。定義では、フィボナッチ数列の最初の2つの数字は0と1で、次の数は前の2つの合計となる。たとえば最初の10個のフィボナッチ数列は、0, 1, 1, 2, 3, 5, 8, 13, 21, 34となる。

// 最初の100個のフィボナッチ数のリストを計算する関数を記述せよ。
// 定義では、フィボナッチ数列の最初の2つの数字は0と1で、次の数は前の2つの合計となる。
// 例えば最初の10個のフィボナッチ数列は、0, 1, 1, 2, 3, 5, 8, 13, 21, 34となる。

object P03 {
  // 遅い
  def fibonacciIn(n: Int ) : Int ={
    n match {
      case 1 => 0
      case 2 => 1
      case _ => fibonacciIn(n - 2) + fibonacciIn(n - 1)
    }
  }
  def numToFibonacciList(n: Int) : List[Int] = {
    n match {
      case 1 => List(fibonacciIn(1))
      case _ => numToFibonacciList(n-1):::List(fibonacciIn(n))
    }
  }
}
printf("%s: %s", "number to fibonacci", P03.numToFibonacciList(10) )

// 末尾再帰を使っているためP03より早い
object P03_2 {
  // 末尾再帰を使う
  def fibonacci(n: Int, a1: BigInt = 0, a2:BigInt = 1) : BigInt ={
    n match {
      case 0|1 => a1
      case _   => fibonacci( n - 1, a1 + a2, a1 )
    }
  }
  def numToFibonacciList(n: Int) : List[BigInt] = {
    n match {
      case 1 => List(fibonacci(1))
      case _ => numToFibonacciList(n-1):::List(fibonacci(n))
    }
  }
}

printf("%s: %s", "number to fibonacci", P03_2.numToFibonacciList(10) )

// Streamを使う
val fib:Stream[Int] = 0 #:: fib.scanLeft(1){_ + _}
fib.take(10).toList

リストの連結で値 + リストの場合(::)とリスト + リストの場合(:::)で結構詰まりました

1つ目の方法だと100個のリスト取得にとても時間が掛かるため実用性は…

そこで2つ目、末尾再帰を用いる方法があるようです

途中の計算結果を引数として渡してあげることで実現できます

最後1つはStreamを使う方法

これはまだちょっと理解が追いついていない感がありますが、無限のリストを定義でき、遅延評価を使うので計算する際に処理が走るというものらしい

問題4

正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。たとえば、[50, 2, 1, 9]が与えられたとき、95021が答えとなる

// 正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。
// 例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる

object P04 {
  def toMaxNum(list: List[BigInt]) : BigInt = {
    val sort: (BigInt,BigInt) => Boolean = (a:BigInt, b:BigInt) => {
      a.toString + b.toString > b.toString + a.toString
    }
    BigInt(list.sortWith(sort).mkString)
  }
}

val list = List[BigInt](3,34,32,5,50,53)

printf("%s: %d", "make the maximum number.", P04.toMaxNum( list ))

// 桁数が同じ場合の比較でうまく動作しない
// println( list.sortBy(_.toString).reverse.mkString )

// 1行で
println( list.sortWith((a,b) => a.toString + b.toString > b.toString + a.toString ).mkString)

最初文字列で比較してソートすれば1行でいけるかと思いましたが、桁が違うときの比較がうまくいかなかったため断念

3,34,32のリストをソートした場合、期待される並び方は34332だが34323のならびになってしまう

数値を足したものどうしを比較すればいける模様

問題5

1,2,…,9の数をこの順序で、”+”、”-“、または何もせず結果が100となるあらゆる組み合せを出力するプログラムを記述せよ。たとえば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる

// 1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。
// 例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる

object P05 {
  val plus  = """(.*)\+([0-9]+)""".r
  val minus = """(.*)\-([0-9]+)""".r
  val single = """([0-9]+)""".r

  def listCombinationExpect(list: List[Int], exp: Int): List[Any] = {
      val patterns = toPatterns(list.tail.head,list.tail.tail,List(list.head))
      for(l <- patterns; if calc(l.toString) == exp ) yield l
  }
  def calc(str: String): Int ={
    str match {
      case plus(h,t)   => calc(h) + t.toInt
      case minus(h,t)  => calc(h) - t.toInt
      case single(num) => num.toInt
    }
  }
  val op = List("+","-","")
  def toPatterns(n: Int,list: List[Int], tmp: List[Any]): List[Any] ={

    val result = for(item <- tmp; o <- op) yield item + o + n

    list match {
      case head::tail => toPatterns(head,tail,result)
      case _ => result
    }
  }
}

val list     = List(1,2,3,4,5,6,7,8,9)
val expected = 100
println(P05.listCombinationExpect(list,expected))