Project Euler: Problem 33

Euler0033.scala

package euler.zerosum

object Euler0033 {

  val TWO_DIGIT_NUMS = (10 to 99).toStream

  def main(args: Array[String]) {
    val fractions =
      TWO_DIGIT_NUMS
      .foldLeft(List((1, 1)))((x, y) =>
        x ++ TWO_DIGIT_NUMS.filter(y < _).map((y, _)))
      .tail
      .map(x => (x._1.toString.toList, x._2.toString.toList))
      .filter(x => {
        val numer = x._1
        val denom = x._2
        numer.contains(denom(0)) || numer.contains(denom(1))
      })

    println(
      fractions
      .filter(x => {
        val numer = x._1.map(_.toString).reduce(_ + _).toInt
        val denom = x._2.map(_.toString).reduce(_ + _).toInt
        cancel(x) == new Rational(numer, denom)
      })
      .filterNot(_._2(1) == '0')
      .map(x => {
        val numer = x._1.map(_.toString).reduce(_ + _).toInt
        val denom = x._2.map(_.toString).reduce(_ + _).toInt
        new Rational(numer, denom)
      })
      .reduce(_ * _)
      .denom
    )
  }

  private def cancel(fraction: (List[Char], List[Char])): Rational = {
    val nHead = fraction._1.head.toString.toInt
    val nLast = fraction._1.last.toString.toInt
    val dHead = fraction._2.head.toString.toInt
    val dLast = fraction._2.last.toString.toInt

    dLast match {
      case `nHead` => new Rational(nLast, dHead)
      case `nLast` => new Rational(nHead, dHead)
      case 0 => new Rational(0, 1)
      case _ => dHead match {
        case `nHead` => new Rational(nLast, dLast)
        case `nLast` => new Rational(nHead, dLast)
      }
    }
  }

  class Rational(n: Int, d: Int) {
    require(d != 0)

    private val g = gcd(n.abs, d.abs)
    val numer = n / g
    val denom = d / g

    def this(n: Int) = this(n, 1)

    def *(that: Rational): Rational = {
      new Rational(numer * that.numer, denom * that.denom)
    }

    def *(i: Int): Rational = {
      new Rational(numer * i, denom)
    }

    private def gcd(a: Int, b: Int): Int = {
      if (b == 0) a else gcd(b, a % b)
    }

    override def toString = numer + "/" + denom

    override def equals(other: Any): Boolean = other match {
      case that: Rational =>
        that.canEqual(this) && numer == that.numer && denom == that.denom
      case _ => false
    }

    def canEqual(other: Any): Boolean = {
      other.isInstanceOf[Rational]
    }
  }

}