Building Multi-Branch Jenkins Pipeline

Being remote developer and work from home during this pandemic, I realize that there is need of system or mechanism which monitor state of the your project. Some tool which does following for you

• Continuously run unit tests on each check-in pushed in any branch
• Run other checks say lint, security tools, static analysis
• Running tests on multiple platform
• Send notification to team in case of failure
• Pull Request build status

Jenkins is typically used as CI/CD. But I would like to consider Jenkins as a product quality checker, running unit tests continuously on various platforms. Here is how to setup a CI/CD using jenkins for Multi-branch pipeline.

Choose a Multiple branch item

Add branch source details

Build configuration using Jenkinfile

What is jenkinfile

‘Pipeline as code’ or defining the deployment pipeline through code rather than configuring a running CI/CD tool, provides tremendous benefits for teams automating infrastructure across their environments. One of the most popular ways to implement a pipeline as code is through Jenkins Pipeline. Jenkins, an open source automation server, is used to automate tasks associated with building, testing, and deploying software.

Following is the typical Jenkins file I used for my GoLang project.

pipeline {
    agent {
        node {
            label 'label to get the node'
        }
    }
    parameters {
        booleanParam(name: 'releaseBuild', defaultValue: false, description: 'New Release Build')
        booleanParam(name: 'skipTests', defaultValue: false, description: 'Skip Tests')
        booleanParam(name: 'uploadBuild', defaultValue: false, description: 'Upload the tar Artifactory')
    }
    environment {
        DISABLE_AUTH = 'true'
        DB_ENGINE    = 'sqlite'
        def t = readFile(file: 'VERSION')
        VERSION_ENV = t.trim()
    }
    stages {
        stage('Build dependent projects/Module') {
            when {
                allOf {
                    expression { params.releaseBuild }
                    branch 'master'
                }
            }
            steps {
                sh '<build Command>'
            }
        }
        stage('Execute depedent project/modules tests') {
            when {
                allOf {
                    expression { params.releaseBuild }
                    expression { !params.skipTests }
                    branch 'master'
                }
            }
            steps {
                sh '<test command>'
            }
        }


        stage ('Build') {
            steps {
                sh 'printenv'
                sh 'ls -alf .'
                sh '<build command>'
            }
        }

        stage ('Test') {
            when {
                allOf {
                    expression { !params.skipTests }
                }
            }
            steps {
                sh 'make test'
                sh 'echo "done"'
            }
        }

        stage('Stage') {
            when {
                allOf {
                    expression { params.releaseBuild  || params.uploadBuild }
                    branch 'master'
                }
            }
            steps {
                script {
                    sh 'make build-stage TARGET_FILE_NAME=*.tar'
                    sh 'ls -lrt out'
                    sh 'ls -lrt'
                }
            }
        }

        stage('Upload To Artifactory') {
            when {
                allOf {
                    expression { params.releaseBuild  || params.uploadBuild }
                    branch 'master'
                }
            }
            steps {
                script {
                    def server = Artifactory.server "Artifactory"

                    def uploadSpec = """{
                        "files": [
                            {
                                "pattern": "*.tar",
                                "target": "linux/"
                            }
                        ]
                    }"""
                    def buildInfo = server.upload spec: uploadSpec
                    server.publishBuildInfo buildInfo
                }
            }
        }

        stage("Build Installer") {
            when {
                allOf {
                    expression { params.releaseBuild }
                    branch 'master'  //only run these steps on the master branch
                }
            }
            steps {
                script {
                    build job: 'installer/master',
                    propagate: true,
                    wait: true,
                    parameters: [
                        [$class: 'BooleanParameterValue', name: 'releaseBuild', value: "${params.releaseBuild}"],
                        [$class: 'StringParameterValue', name: 'stageFileName', value: "*.tar"],
                        [$class: 'StringParameterValue', name: 'platform', value: "linux"],
                        [$class: 'StringParameterValue', name: 'buildNumber', value: "${BUILD_NUMBER}"]
                    ]
                }
            }
        } // deploy
    } // stages

    post {
        always {
            mail to: 'receipient@jenkins.com',
                 subject: "${currentBuild.currentResult} Pipeline: ${currentBuild.fullDisplayName}",
                 body: "More Details ${env.BUILD_URL}"
        }
    }

}

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))

    }
}

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')))
    }
}

Ninety-Nine Scala Problems – Problem 1 – 10

This one is inspired by Ninety-Nine Haskell Problems. Since both are functional languages, I am giving a try to solve the problems in Scala.

Problem 1 : Find the last element of a list.

object Problem1 {
    def myLast[T](list: List[T]): Option[T] = list match {
        case Nil => None
        case x :: Nil => Some(x)
        case x :: xs => myLast(xs)
    }

    def main(args: Array[String]) {
        assert(myLast(1 to 10 toList) == Some(10))
        assert(myLast(List(1)) == Some(1))
        assert(myLast(Nil) == None)

        assert(myLast('a' to 'z' toList) == Some('z'))

    }
}

Problem 2 : Find the last but one element of a list.

object Problem2 {
    def myButLast[T](list: List[T]): Option[T] = list match {
        case Nil => None
        case x :: Nil => Some(x)
        case x :: xs => {
            if (xs.length == 1) Some(x)
            else
                myButLast(xs)
        }
    }

    def main(args: Array[String]): Unit = {
        assert(myButLast(1 to 10 toList) == Some(9))
        assert(myButLast(List(1)) == Some(1))
        assert(myButLast(Nil) == None)

        assert(myButLast('a' to 'z' toList) == Some('y'))
    }
}

Problem 3 : Find the K’th element of a list. The first element in the list is number 1.

object Problem3 {
    def elementAt[T](list: List[T], index: Int): Option[T] = {

        def loop(subList: List[T]): Option[T] = subList match {
            case Nil => None
            case x :: xs => {
                if (xs.length == list.length - index) Some(x)
                else loop(xs)
            }
        }

        if (index > list.length) None
        if (index < 0) None

        loop(list)
    }

    def main(args: Array[String]) {
        assert(elementAt(1 to 10 toList, 5) == Some(5))
        assert(elementAt('a' to 'z' toList, 10) == Some('j'))
        assert(elementAt(Nil, 10) == None)
        assert(elementAt('a' to 'z' toList, 100) == None)
        assert(elementAt('a' to 'z' toList, -1) == None)

    }
}

Problem 4 : Find the number of elements of a list.

object Problem4 {
    def myLength[T](list: List[T]): Int = list match {
        case Nil => 0
        case x :: xs => 1 + myLength(xs)
    }

    def main(args: Array[String]): Unit = {
        assert(myLength(1 to 10 toList) == 10)
        assert(myLength('a' to 'z' toList) == 26)
        assert(myLength("Hello, world!" toList) == 13)
    }
}

Problem 5 : Reverse a list.

object Problem5 {
    def myReverse[T](list: List[T]): List[T] = list match {
        case Nil => Nil
        case x::xs => myReverse(xs) ::: List(x)
    }

    def main(args: Array[String]): Unit = {
        assert( myReverse(1 to 10 toList) == (10 to 1 by -1 toList))
        assert( myReverse(List('a','b','c','d','e')) == (List('e','d','c','b','a')))
    }
}

Problem 6 : Find out whether a list is a palindrome. A palindrome can be read forward or backward; e.g. (x a m a x).

object Problem6 {
    def isPalindrome[T](list : List[T]) : Boolean = list match {
        case Nil => true
        case x::Nil => true
        case x::xs => (list.head == list.last) && isPalindrome(list.tail.init)
    }
    def main(args: Array[String]) {
        assert ( isPalindrome(List(1,2,3)) == false)
        assert ( isPalindrome("madamimadam".toList) == true )
        assert ( isPalindrome(List(1,2,4,8,16,8,4,2,1)) == true )
    }
}

Problem 7 :Flatten a nested list structure.

object Problem7 {
    def myflatten[T](list: List[T]): List[T] = list match {
        case Nil => list
        case (x: List[T]) :: xs => myflatten(x) ::: myflatten(xs)
        case x :: xs => x :: myflatten(xs)

    }

    def main(args: Array[String]) {
        println(myflatten(List('a', List('b', List('c', 'd'), 'e'))))
        println(myflatten(List('X', ('a' to 'z' toList))))
    }
}

Problem 8 : Eliminate consecutive duplicates of list elements.

object Problem8 {
    def compress[T](list: List[T]): List[T] = list match {
        case Nil => Nil
        case x :: xs => x :: compress(xs.dropWhile(_ == x))

    }

    def main(args: Array[String]): Unit = {
        val a = List('a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'c', 'c')
        println("Result ----> " + compress(a))
        val b = List('a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e')
        println("Result ----> " + compress(b))
        println("Result ----> " + compress('a' to 'z' toList))

    }
}

Problem 9: Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements they should be placed in separate sublists.

/**
 * Problem 9
 * (**) Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements they should be placed in separate sublists.
 * Example:
 * (pack '(a a a a b c c a a d e e e e))
 * ((A A A A) (B) (C C) (A A) (D) (E E E E))
 */
object Problem9 {
    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 main(args: Array[String]) {
        println(pack(List('a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e')))
    }

}

Problem 10 : Run-length encoding of a list. Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E.

/**
 *
 * Run-length encoding of a list. Use the result of problem P09 to implement the so-called run-length encoding data
 * compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of
 * duplicates of the element E.
 * Example:
 * (encode '(a a a a b c c a a d e e e e))
 * ((4 A) (1 B) (2 C) (2 A) (1 D)(4 E))
 *
 */
object Problem10 {

    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[T](list: List[T]): List[(Int, T)] = {
        def encodeHelper[T](packedList: List[Any], result: List[(Int, T)]): List[(Int, T)] = {
            packedList match {
                case Nil => Nil
                case (x: List[T]) :: Nil =>
                    result ::: List((x.length, x.head))
                case (x: List[T]) :: (xs: List[T]) =>
                    result ::: List((x.length, x.head)) ::: encodeHelper(xs, result)
                case _ => Nil
            }
        }
        encodeHelper(pack(list), Nil)
    }

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

Non-Intrusive Linked List

Non-Intrusive Linked List
Long time back I have seen some interesting implementation of linked list.
Recently I saw some discussion on hackernews, got again intested to understand that list implementation.
Similar implementation is used by Linux kernel linked list

Normally when a developer defines a linked list, he/she will add data part as member of linked list node
say you want to create linked list of Integers then one would have struct as follows

struct intList {
   int data;
   struct intList *prev;
   struct intList *next;
}

– Now this list is attached to data-type integer.
– You cannot have same node part of two different list.
– This is called as Intrusive Linked List.
– You have to do lot of careful surgery of list, need to check pointers is null or not.

Non-Intrusive Linked list is amazing way of getting rid of these restrictions.

Let us define a new Non-Intrusive linked list which will work with any POD in C language.

struct llhead {
  struct llhead *prev, *next;
};

Note that there is no mention of the type it is storing. This seems strange at first.
Intrusive linked lists flip the memory layout inside out. Instead of the list node providing memory for
a POD, POD provides memory for a list node. The ‘intrusive’ part of the name comes from the fact that
we store the list node inside the type POD.

Let us define some operation on this list

#define LL_INIT(N)      ((N)->next = (N)->prev = (N))
#define LL_HEAD(H)      struct llhead H = { &H, &H }
#define LL_ENTRY(P,T,N) ((T *)((char *)(P) - offsetof(T, N)))
#define LL_TAIL(H, N)                   \
  do {                                  \
    ((H)->prev)->next = (N);            \
    (N)->prev = ((H)->prev);            \
    (N)->next = (H);                    \
    (H)->prev = (N);                    \
  } while (0)
#define LL_DEL(N)                       \
  do {                                  \
    ((N)->next)->prev = ((N)->prev);    \
    ((N)->prev)->next = ((N)->next);    \
    LL_INIT(N);                         \
  } while (0)
#define LL_FOREACH(H,N) for (N = (H)->next; N != (H); N = (N)->next)
#define LL_FOREACH_SAFE(H,N,T)         \
  for (N = (H)->next, T = (N)->next; N != (H);     \
      N = (T), T = (N)->next)

Remember this is actually Circular doubly linked list.

Now I want to create a list of integers, this is how I will be writing my POD

struct integerList {
  struct llhead link;
  int data;
};

Initialize the head of the list.

LL_HEAD(mylist);

Here is the complete working example.

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include "ilist.h"


struct llhead {
  struct llhead *prev, *next;
};

#define LL_INIT(N)      ((N)->next = (N)->prev = (N))
#define LL_HEAD(H)      struct llhead H = { &H, &H }
#define LL_ENTRY(P,T,N) ((T *)((char *)(P) - offsetof(T, N)))
#define LL_TAIL(H, N)                   \
  do {                                  \
    ((H)->prev)->next = (N);            \
    (N)->prev = ((H)->prev);            \
    (N)->next = (H);                    \
    (H)->prev = (N);                    \
  } while (0)
#define LL_DEL(N)                       \
  do {                                  \
    ((N)->next)->prev = ((N)->prev);    \
    ((N)->prev)->next = ((N)->next);    \
    LL_INIT(N);                         \
  } while (0)
#define LL_FOREACH(H,N) for (N = (H)->next; N != (H); N = (N)->next)
#define LL_FOREACH_SAFE(H,N,T)         \
  for (N = (H)->next, T = (N)->next; N != (H);     \
      N = (T), T = (N)->next)


struct integerList {
  struct llhead link;
  int data;
};

int main(int argc, char **argv) {
  int k = 0; 
  struct llhead *head;
  static LL_HEAD(mylist);

  for ( k = 0; k < 10; k++) {
    struct integerList *elem = 
          (struct integerList *)malloc(sizeof(struct integerList));
    elem->data = k;
    LL_TAIL(&mylist, &elem->link);
  }

  LL_FOREACH(&mylist, head) {
    struct integerList *elem = LL_ENTRY(head, struct integerList, link);
    printf("%d\n", elem->data );
  }

  return 0;
}

Try me Trie

Have you ever used Auto-complete feature ?
It’s implemented using Trie. Trie is a data structure which is very efficient for searching word .
However, it has one very big disadvantage of using a lot of memory as every node contains character array of alphabet size.
It marks down the ending of word by assigning it as leaf node.
Searching a word in trie has complexity of O(n) ,where n is the length of a word searched.
Time as well as space complexity can be reduced by using Compressed Trie.

Let us write a code for Trie Datastructure

Here are some pre-processors defined which will be used later.

#define ALPHABETS_SIZE (94)
#define PIVOT_CHARACTER ((int)'!')
#define TRIE_NODE_NULLPTR (trie_t*)0
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define FOUND 1
#define NOT_FOUND 0
#define INVALID_WORD -1
#define BUFFERSIZE (1024)

C structure definition is as follows

typedef struct trie_t {
  char value;
  int isLeaf;
  int count;
  struct trie_t *trieArray[ALPHABETS_SIZE];
} trie_t;

How to create a new node of Trie.

trie_t *getNewNode() {
  int index = 0;
  trie_t *tmp = (trie_t*) malloc ( sizeof ( trie_t));
  tmp->isLeaf = 0;
  tmp->count =  0;
  for ( index = 0; index < ALPHABETS_SIZE; index++){
    tmp->trieArray[index] = TRIE_NODE_NULLPTR;
  }
  return tmp;
}

How to get the position of new character in the trieArray

int getPosition(char ch ) {
  int pos = (ch) - PIVOT_CHARACTER;
#ifdef DEBUGME 
  if ( pos > ALPHABETS_SIZE ) {
    printf("RANGE ERROR for ALPHABETS_SIZE\n");
  }
#endif
  return pos;
}

How to insert new character in the Trie

void insert(const char *word) {
  int charIndex = 0;
  trie_t *pCurrentNode = gRoot;
  if ( !word && strlen(word) != 0 ) {
    return;
  }
#ifdef DEBUGME 
  printf("Word -> %s\n", word);
#endif

  for ( charIndex = 0; charIndex < strlen(word); charIndex++) {
    /* Find the position where new character will be stored */
    int position = getPosition(word[charIndex]);
    /* If current slot is NULL create new one */
    if ( pCurrentNode->trieArray[position] ==  TRIE_NODE_NULLPTR) {
        pCurrentNode->trieArray[position] = getNewNode();
    }
    pCurrentNode->value = word[charIndex];
    pCurrentNode = pCurrentNode->trieArray[position];
  }
  pCurrentNode->isLeaf = 1;
  pCurrentNode->count++;
}

How to search a string in trie

int search(const char *word) {
  int length = 0;
  int index = 0;


  trie_t *pCurrentNode = gRoot;

  if ( !word && strlen(word) != 0 ) {
    return INVALID_WORD;
  }
  length = strlen(word);
  for ( index = 0; index < length; index++) {
    int position = getPosition(word[index]);
    if ( pCurrentNode->trieArray[position] == TRIE_NODE_NULLPTR ) {
      return NOT_FOUND;
    }
    pCurrentNode = pCurrentNode->trieArray[position];
  } 
  
#ifdef DEBUGME 
  printf("Count for %s = %d\n", word, pCurrentNode->count);
#endif        
  return FOUND;
}       

Here is running program

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define ALPHABETS_SIZE (94)
#define PIVOT_CHARACTER ((int)'!')
#define TRIE_NODE_NULLPTR (trie_t*)0
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define FOUND 1
#define NOT_FOUND 0
#define INVALID_WORD -1
#define BUFFERSIZE (1024)


typedef struct trie_t {
  char value;
  int isLeaf;
  int count;
  struct trie_t *trieArray[ALPHABETS_SIZE];
} trie_t;

trie_t *gRoot = (trie_t*)0;

trie_t *getNewNode() {
  int index = 0;
  trie_t *tmp = (trie_t*) malloc ( sizeof ( trie_t));
  tmp->isLeaf = 0;
  tmp->count =  0;
  for ( index = 0; index < ALPHABETS_SIZE; index++){
    tmp->trieArray[index] = TRIE_NODE_NULLPTR;
  }
  return tmp;
}

int getPosition(char ch ) {
  int pos = (ch) - PIVOT_CHARACTER;
#ifdef DEBUGME 
  if ( pos > ALPHABETS_SIZE ) {
    printf("RANGE ERROR for ALPHABETS_SIZE\n");
  }
#endif
  return pos;
}

void insert(const char *word) {
  int charIndex = 0;
  trie_t *pCurrentNode = gRoot; 
  if ( !word && strlen(word) != 0 ) {
    return;
  }
#ifdef DEBUGME 
  printf("Word -> %s\n", word);
#endif

  for ( charIndex = 0; charIndex < strlen(word); charIndex++) {
    /* Find the position where new character will be stored */
    int position = getPosition(word[charIndex]);
    /* If current slot is NULL create new one */
    if ( pCurrentNode->trieArray[position] ==  TRIE_NODE_NULLPTR) {
        pCurrentNode->trieArray[position] = getNewNode();
    }
    pCurrentNode->value = word[charIndex];
    pCurrentNode = pCurrentNode->trieArray[position];
  }
  pCurrentNode->isLeaf = 1;
  pCurrentNode->count++;
}

int search(const char *word) {
  int length = 0;
  int index = 0;


  trie_t *pCurrentNode = gRoot; 

  if ( !word && strlen(word) != 0 ) {
    return INVALID_WORD;
  }
  length = strlen(word);
  for ( index = 0; index < length; index++) {
    int position = getPosition(word[index]);
    if ( pCurrentNode->trieArray[position] == TRIE_NODE_NULLPTR ) {
      return NOT_FOUND;
    }
    pCurrentNode = pCurrentNode->trieArray[position];
  }
  
#ifdef DEBUGME 
  printf("Count for %s = %d\n", word, pCurrentNode->count);
#endif
  return FOUND;
}

int main( int argc, char **argv) {
  gRoot = getNewNode();

  char buffer[BUFFERSIZE];
  while ( 1 ) {
    printf("TrieShell > ");
    fgets(buffer, BUFFERSIZE, stdin);

    if (buffer[strlen(buffer) - 1] == '\n') {
        buffer[strlen(buffer) - 1] = '\0';
    }

    if(!strcmp(buffer, "exit") || 
       !strcmp(buffer, "quit") || 
       !strcmp(buffer, "q")) {
      exit(0);
    }

    if(strstr(buffer, "insert")) {
      char *token;
      const char delim[2] = " ";
      token = strtok(buffer, delim);
      token = strtok(NULL, delim);
      while( token != NULL )  {
        insert(token);
        token = strtok(NULL, delim);
      }
    }


    if(!strcmp(buffer, "help")) {
      printf("Commands :\n");
      printf("insert <string|URL>:\n");
      printf("quit | exit | q <To exist from the shell>\n");
    }
  }
#ifdef DEBUGME 
  char keys[][8] = {"the", "a", "there", "answer", "any", "by", "bye", "their"};
  gRoot = getNewNode();
  int index;
  for(index = 0; index < ARRAY_SIZE(keys); index++) {
    insert(keys[index]);
  }
  for(index = 0; index < ARRAY_SIZE(keys); index++) {
    insert(keys[index]);
  }
  printf("Insert Done !!! \n");

  for(index = 0; index < ARRAY_SIZE(keys); index++) {
    int found = search(keys[index]);
    printf("%s --> %s\n", keys[index], found == FOUND ? "FOUND" : "NOT FOUND");
  }
  
#endif
  return 0;
}

Magical C Language, Loop Un-Rolling and Duffs Device

After so many years of working with C language. It always Surprises me. Today I came across Duff’s Device. It is really a cleaver technique.
Suppose you want to copy a buffer of 100 bytes, typical code you will write will have following construct

for ( int i = 0; i < 100; i++ ) {
    *dest++ = *source++
}

There are bunch of instruction involves here, Compare Instruction, Increment Instruction …
But important thing is this all is done for 100 times.

Duff’s Device is intelligent method of solving this following as given in following code.

#include <stdio.h>
#include <string.h>

#define SIZE 10000

void duffsDevice(const char *source, char *destination, int length) {
  int numberOfPass = 0;
  int n = (length + 7) / 8;
  switch (length % 8) {
    case 0:
      do {
        *destination++ = *source++; 
        case 7:   *destination++ = *source++; 
        case 6:   *destination++ = *source++; 
        case 5:   *destination++ = *source++; 
        case 4:   *destination++ = *source++; 
        case 3:   *destination++ = *source++; 
        case 2:   *destination++ = *source++; 
        case 1:   *destination++ = *source++; 
      } while (numberOfPass++,--n > 0);
  }

  printf("Number of Loops = %d\n", numberOfPass);

}


int main(int argc, char** argv) {
  char source[SIZE + 1] = { 'a' };
  char destination[SIZE + 1] = { 'c' };

  memset(source, 'x', SIZE);
  memset(source, 'z', SIZE);

  printf("Source = [%s]\n", source);

  memcpy(destination, source, SIZE);

  duffsDevice(source, destination, SIZE);
  destination[SIZE] = '\0';

  printf("Destination = [%s]\n", destination);
}

For copying 10000 bytes it take only 1250 loops.

Ohh !!! and I thought do…while(0) is just useless

Over the period of years, I saw following kind of code in many places

#define FOO(X) do { f(X); g(X); } while (0)

But this is not useless but a clear trick to avoid unwanted Empty Expression

Consider you have defined the same macro as follows

#define BAR(X) f(x); g(x)

and you are using the same as follows in your main code

if (corge)
  BAR(corge);
else
  gralt();

Above code would be expanded as follows

if (corge)
  f(corge); g(corge);
else
  gralt();

This would cause compiler to cry from bottom of its neck. This is not what you wanted, and this is where do…while(0) trick comes as a savior.

Smallest Zero One Number of multiples of n

ZeroOne is the number, whose digits are either 0 or 1. You have given a number n and need to find the smallest multiplier which is ZeroOne Number

For example for 4 smallest possible ZeroOne Multipler is 100

Solution

I have tried to solve this but really could not find the optimize solution.

#include <stdio.h>
int getZeroOneMultipler(int number) {
  long multiplier = 1;
  while(1) {
    long product = multiplier++ * number;
    long temp = product;
    while ( temp != 0 ) {
      int digit = temp % 10;
      if ( digit != 0 && digit != 1 ) {
        break;
      }
      temp /= 10;
    }
    if ( temp == 0 ) {
      return product;
    }
  }
}

int main(int argc, char** argv) {
  int i = 0;
  for ( i = 0; i < 100; i++) {
      printf("%d = %d\n", i, getZeroOneMultipler(i));
  }
  return 0;
}

British computer magazine had a programming contest [ Updated ]

Friend ( Rishitesh Mishra ) suggested to increment counter by 9, as he believe that 9 is magic number and to my surprise I could get the result in less than a second.

package avdongre.bcm.puzzle;

import java.util.Arrays;

public class Solution {
	public static void main(String[] args) {
		long start = java.util.Calendar.getInstance().getTimeInMillis();
		int[] set = new int[10];
		int counter = 0;
		boolean solutionFound = false;
		for (int i = 123456789; i < 987654321; i = i + 9) {
			if (solutionFound) {
				break;
			}
			Arrays.fill(set, 0);
			int temp = i;
			boolean validNumber = true;
			while (temp != 0) {
				int digit = temp % 10;
				if (digit == 0) {
					validNumber = false;
					break;
				}
				if (set[digit] == 0) {
					set[digit] = 1;
				} else {
					validNumber = false;
					break;
				}
				temp /= 10;
			}
			if (validNumber) {
				counter++;
				if (counter == 100000) {
					System.out.println(i);
					solutionFound = true;
				}
			}
		}
		long end = java.util.Calendar.getInstance().getTimeInMillis();
		System.out.println("it took this long to complete this stuff: "
				+ ((end - start) * 0.001) + " seconds");
	}
}