Ninety-Nine Scala Problems – Problem 31 – 41

Github repository

package avdongre.scala99.problem31to41

import scala.annotation.tailrec

/**
 * Created by adongre on 3/6/15.
 */
object Arithmetic {
    /* Problem 31
     * Determine whether a given integer number is prime.
     * */
    def isPrime(number: Int): Boolean = {
        require(number > 1)

        def isPrimeHelper(divisor: Int): Boolean = {
            if (divisor == 1)
                true
            else
            if (number % divisor == 0)
                false
            else
                isPrimeHelper(divisor - 1)
        }
        isPrimeHelper(number - 1)
    }

    /* Problem 32
     * Determine the greatest common divisor of two positive
     * integer numbers. Use Euclid's algorithm.
     */
    def gcd(a: Int, b: Int): Int = {
        if (b == 0) a
        else gcd(b, a % b)
    }

    /* Problem 33
    * (*) Determine whether two positive integer numbers are coprime.
    * Two numbers are coprime if their greatest common divisor equals 1.
    */

    def coprime(a: Int, b: Int): Boolean = {
        if (gcd(a, b) == 1) true
        else
            false
    }

    /* Problem 34
     * (**) Calculate Euler's totient function phi(m).
     *  Euler's so-called totient function phi(m) is defined as the number of
     *  positive integers r (1 <= r < m) that are coprime to m.
     *  Example: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note the special case: phi(1) = 1.
     */
    def totientPhi(number: Int): Int = {
        def totientPhiLoop(curNum: Int, acc: Int): Int = {
            curNum match {
                case 1 => 1 + acc
                case _ => {
                    if (coprime(curNum, number)) {
                        totientPhiLoop(curNum - 1, acc + 1)
                    } else {
                        totientPhiLoop(curNum - 1, acc)
                    }
                }
            }

        }
        totientPhiLoop(number - 1, 0)
    }


    /* Problem 35
     * (**) Determine the prime factors of a given positive integer.
     * Construct a flat list containing the prime factors in ascending order.
     */
    def primeFactors(input: Int): List[Int] = {
        def primeFactorsHelper(prmFctr: Int, number: Int, acc: List[Int]): List[Int] = {
            prmFctr match {
                case x if (prmFctr > number) => acc
                case x if (isPrime(prmFctr) && (number % prmFctr == 0)) => {
                    primeFactorsHelper(prmFctr, number / prmFctr, acc ::: List(prmFctr))
                }
                case _ => primeFactorsHelper(prmFctr + 1, number, acc)
            }
        }
        primeFactorsHelper(3, input, Nil)
    }

    /* Problem 36
     * (**) Determine the prime factors of a given positive integer.
     * Construct a list containing the prime factors and their multiplicity.
     * Example:
     * (prime-factors-mult 315)
     * ((3 2) (5 1) (7 1))
     */
    def primeFactorsMult(input: Int): List[(Int, Int)] = {
        def primeFactorsMultHelper(v: List[Int], acc: List[(Int, Int)]): List[(Int, Int)] = {

            v match {
                case Nil => Nil
                case x :: Nil => acc ::: List((x, 1))
                case x :: xs if (x == xs.head) && acc.isEmpty => {
                    primeFactorsMultHelper(xs, acc ::: List((x, 1)))
                }
                case x :: xs if (x == xs.head) => {
                    primeFactorsMultHelper(xs, acc ::: List((acc.head._1, acc.head._2 + 1)))
                }
                case x :: xs => {
                    primeFactorsMultHelper(xs, acc ::: List((x, 1)))
                }
            }
        }

        def accumulateResult(input: List[(Int, Int)], accResult: List[(Int, Int)]): List[(Int, Int)] = {
            input match {
                case Nil => Nil
                case x :: Nil => accResult ::: List((x._1, x._2))

                case x :: xs if (x._1 == xs.head._1) => {
                    accumulateResult(xs.tail, accResult ::: List((x._1, x._2 + 1)))
                }
                case x :: xs => accumulateResult(xs, accResult ::: List((x._1, x._2)))
            }
        }
        accumulateResult(primeFactorsMultHelper(primeFactors(input), Nil), Nil)
    }

    /*
     * Problem 39
     * (*) A list of prime numbers.
     * Given a range of integers by its lower and upper limit,
     * construct a list of all prime numbers in that range.
     * Example in Haskell:
     * P29> primesR 10 20
     * [11,13,17,19]
     */
    def primesR(lower: Int, upper: Int): List[Int] = {
        def primesRHelper(start: Int, acc: List[Int]): List[Int] = {
            start match {
                case x if start > upper => acc.reverse
                case x if isPrime(start) => primesRHelper(start + 1, x :: acc)
                case x => primesRHelper(start + 1, acc)
            }
        }
        primesRHelper(lower, Nil)
    }


    /* Problem 40
     * (**) Goldbach's conjecture.
     * Goldbach's conjecture says that every positive even number greater than 2
     * is the sum of two prime numbers. Example: 28 = 5 + 23.
     * It is one of the most famous facts in number theory that has not been proved to be
     * correct in the general case. It has been numerically confirmed up to very
     * large numbers (much larger than we can go with our Prolog system).
     * Write a predicate to find the two prime numbers that sum up to a given even integer.
     * Example:
     * (goldbach 28)
     * (5 23)
     */

    def goldbach(input: Int): (Int, Int) = {
        primesR(3, input) find { p => isPrime((input - p)) } match {
            case None => throw new IllegalArgumentException
            case Some(p1) => (p1, input - p1)
        }

    }

    /*
     * Problem 41
     * (**) Given a range of integers by its lower and upper
     * limit, print a list of all even numbers and their Goldbach composition.
     * In most cases, if an even number is written as the sum of two prime numbers,
     * one of them is very small. Very rarely, the primes are both bigger than say 50.
     * Try to find out how many such cases there are in the range 2..3000.
     */
    def goldbachList(lower: Int, upper: Int): List[(Int, Int)] = {
        (lower to upper filter (_ % 2 == 0)).toList map (p => goldbach(p))
    }


    def main(args: Array[String]): Unit = {
        try {
            isPrime(1)
        } catch {
            case e: IllegalArgumentException => true
            case e: Exception => println("exception caught: " + e);
        }
        assert(isPrime(7) == true)
        assert(isPrime(6) == false)
        assert(isPrime(2) == true)


        assert(gcd(36, 63) == 9)
        assert(gcd(35, 64) == 1)

        assert(coprime(35, 64) == true)

        assert(totientPhi(10) == 4)

        println(primeFactors(315))

        println(primeFactorsMult(315))
        println(primesR(10, 20))

        println(goldbach(28))

        println(goldbachList(9, 20))

    }
}

Advertisements

Ninety-Nine Scala Problems – Problem 11 – 20

Problem 11 : Modified run-length encoding.
Modify the result of problem 10 in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N E) lists.

object Problem11 {
    def pack(list: List[Any]): List[Any] = {
        if (list.isEmpty) List(List())
        else {
            val (packed, next) = list span {
                _ == list.head
            }
            if (next == Nil) List(packed)
            else packed :: pack(next)
        }
    }

    def encode_modified[T](list: List[T]): List[Any] = {
        def encodeHelper[T](packedList: List[Any], result: List[(Int, T)]): List[Any] = {
            packedList match {
                case Nil => Nil
                case (x: List[T]) :: Nil =>
                    if ( x.length == 1)
                        result ::: x
                        else
                    result ::: List((x.length, x.head))
                case (x: List[T]) :: (xs: List[T]) => {
                    if ( x.length == 1)
                        result ::: x ::: encodeHelper(xs, result)
                        else
                    result ::: List((x.length, x.head)) ::: encodeHelper(xs, result)
                }
                case _ => Nil
            }
        }
        encodeHelper(pack(list), Nil)
    }

    def main(args: Array[String]) {
        println(encode_modified(List('a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e')))
    }
}

Problem 12 : Decode a run-length encoded list.
Given a run-length code list generated as specified in problem 11. Construct its uncompressed version.

object Problem12 {
    def pack(list: List[Any]): List[Any] = {
        if (list.isEmpty) List(List())
        else {
            val (packed, next) = list span {
                _ == list.head
            }
            if (next == Nil) List(packed)
            else packed :: pack(next)
        }
    }

    def encode_modified[T](list: List[T]): List[Any] = {
        def encodeHelper[T](packedList: List[Any], result: List[(Int, T)]): List[Any] = {
            packedList match {
                case Nil => Nil
                case (x: List[T]) :: Nil =>
                    if (x.length == 1)
                        result ::: x
                    else
                        result ::: List((x.length, x.head))
                case (x: List[T]) :: (xs: List[T]) => {
                    if (x.length == 1)
                        result ::: x ::: encodeHelper(xs, result)
                    else
                        result ::: List((x.length, x.head)) ::: encodeHelper(xs, result)
                }
                case _ => Nil
            }
        }
        encodeHelper(pack(list), Nil)
    }

    def decodeModified[T](list: List[Any]): List[T] = {
        def decodeModifiedHelper[T](lst: List[Any], result: List[T]): List[T] = {
            lst match {
                case Nil => result
                case (x: (Int, T)) :: (xs: List[Any]) => {
                    decodeModifiedHelper(xs, result ::: List.fill(x._1)(x._2))
                }
                case (x: T) :: (xs: List[Any]) => {
                    decodeModifiedHelper(xs, result ::: List.fill(1)(x))
                }
                case _ => Nil
            }
        }
        decodeModifiedHelper(list, Nil)
    }

    def main(args: Array[String]) {
        val encodedList = encode_modified(List('a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e'))
        println("Encoded List => " + encodedList)
        val x = decodeModified(encodedList)
        println(x)
    }
}

Problem 14 : Duplicate the elements of a list.

object Problem14 {
    def dupli[T](list: List[T]): List[T] = {
        def dupliHelper[T](lst: List[T], result: List[T]): List[T] = {
            lst match {
                case Nil => result
                case x :: xs => dupliHelper(xs, result ::: List(x, x) )
            }
        }

        dupliHelper(list, Nil)
    }

    def main(args: Array[String]) {
        println(dupli(List('a', 'b', 'c', 'c', 'd')))
    }
}

Problem 15 : Replicate the elements of a list a given number of times.

object Problem15 {
    def repli[T](list: List[T], r: Int): List[T] = {
        def repliHelper[T](lst: List[T], result: List[T]): List[T] = {
            lst match {
                case Nil => result
                case x :: xs => repliHelper(xs, result ::: List.fill(r)(x))
            }
        }
        repliHelper(list, Nil)
    }

    def main(args: Array[String]) {
        println(repli(List('a', 'b', 'c'), 3))
    }

}

Problem 16 : Drop every N’th element from a list.

object Problem16 {
    def dropEvery[T](input: List[T], nth: Int): List[T] = {
        def dropHelper(list: List[T], result: List[T], index: Int): List[T] = {
            list match {
                case Nil => result
                case x :: xs => {
                    if (index == nth) {
                        dropHelper(xs, result, 1)
                    }
                    else {
                        dropHelper(xs, result ::: List(x), index + 1)
                    }
                }
            }

        }
        dropHelper(input, Nil, 1)
    }

    def main(args: Array[String]) {
        println(dropEvery(List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k'), 3))
    }
}

Problem 17 : Split a list into two parts; the length of the first part is given.

object Problem17 {
    def split[T](input: List[T], length: Int): List[List[T]] = {
        def splitHelper[T](list: List[T], left: List[T], right: List[T], index: Int): List[List[T]] = {
            list match
            {
                case Nil => List(left) ::: List(right)
                case x :: xs => {
                    if (index <= length) {
                        splitHelper(xs, left ::: List(x), right, index + 1)
                    } else {
                        splitHelper(xs, left, right ::: List(x), index + 1)
                    }
                }
            }
        }
        splitHelper(input, Nil, Nil, 1)
    }

    def main(args: Array[String]) {
        println(split(List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k'), 3))
    }

}

Problem 18 : Extract a slice from a list.
Given two indices, i and k, the slice is the list containing the elements between the i’th and k’th element of the original list (both limits included). Start counting the elements with 1.

object Problem18 {
    def slice[T](input: List[T], left: Int, right: Int): List[T] = {
        def sliceHelper(list: List[T], result: List[T], index: Int): List[T] = {
            list match {
                case Nil => result
                case x :: xs => {
                    if (index >= left && index <= right)
                        sliceHelper(xs, result ::: List(x), index + 1)
                    else
                        sliceHelper(xs, result, index + 1)
                }
            }
        }
        sliceHelper(input, Nil, 1)
    }

    def main(args: Array[String]) {
        println(slice (List('a','b','c','d','e','f','g','h','i','k'),3, 7))
    }
}

Problem 19 : Rotate a list N places to the left.

object Problem19 {
    def split[T](input: List[T], length: Int): List[List[T]] = {
        def splitHelper[T](list: List[T], left: List[T], right: List[T], index: Int): List[List[T]] = {
            list match {
                case Nil => List(left) ::: List(right)
                case x :: xs => {
                    if (index <= length) {
                        splitHelper(xs, left ::: List(x), right, index + 1)
                    } else {
                        splitHelper(xs, left, right ::: List(x), index + 1)
                    }
                }
            }
        }
        splitHelper(input, Nil, Nil, 1)
    }

    def rotate[T](input: List[T], at: Int): List[T] = {
        val r: List[List[T]] = if (at >= 0) split(input, at)
        else split(input, input.length + at)
        r match {
            case Nil => Nil
            /*
             * I got confuse here with pattern matching see here for my confusion
             * http://stackoverflow.com/questions/30523159/pattern-matching-for-list-of-list-in-scala
             */
            case x :: xs :: Nil => {
                xs ::: x
            }
        }
    }

    def main(args: Array[String]): Unit = {
        println(rotate(List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'), 3))
        println(rotate(List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'), -2))
        println(rotate(List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'), 0))
        println(rotate(List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'), 100))
    }

}

Problem 20 : Remove the K’th element from a list.

object Problem20 {
    def split[T](input: List[T], length: Int): List[List[T]] = {
        def splitHelper[T](list: List[T], left: List[T], right: List[T], index: Int): List[List[T]] = {
            list match {
                case Nil => List(left) ::: List(right)
                case x :: xs => {
                    if (index <= length) {
                        splitHelper(xs, left ::: List(x), right, index + 1)
                    } else {
                        splitHelper(xs, left, right ::: List(x), index + 1)
                    }
                }
            }
        }
        splitHelper(input, Nil, Nil, 1)
    }

    def remove_at[T](at:Int, input:List[T]) : List[T] = {
        val r = split(input, at - 1)
        r match  {
            case Nil => Nil
            case x::xs::Nil => x ::: xs.tail
        }
    }

    def main(args: Array[String]) {
        println(remove_at(2, List('a','b','c','d')))
    }
}