Bash

I am just beginning to learn Linux, and so for Euler1, I've tried my hand at Bash. This shell debuted in 1989. Here is my first attempt:

#!/bin/bash
#Euler1 in Bash

euler1() {
    retval=0

    for i in $(seq $1); do
        if [ $[$i%3] -eq 0 ]  ||  [ $[$i%5] -eq 0 ]; then
            retval=$[ $retval+$i ]
        fi
    done

    echo $retval
}

echo $(euler1 999)

It only took me a couple of hours to bang out this version of Euler1 upon first playing with bash. At first glance, I was horrified by how clunky much of the syntax is - it feels like it has to jump through contextual hoops to get anything done. For example, integers are often passed into another context as string values and then have to be recast back as integer types to continue. And both whitespace and sigils are mandated.

Check out how a value is returned from a function. You have to toss it to STDIO, where it gets caught like an exception by the calling routine and then consumed. Notice above, that there are two ECHO statements but only one value is displayed in the console output. This is because bash doesn't allow functions to return values to the caller. Instead, just like an OS process, a bash function returns a value to STDIO on exit using echo. The calling routine then yanks it from STDIO also using echo.

Here’s another version using a Quicksort-based algorithm. Here we recursively break the list up in half and then reassemble it. Instead of sorting each half, though, we’ll filter the pivot value, converting it to 0 if it’s not divisible. Here, euler1 returns euler1 calculated on the half of the list before the pivot element, euler1 calculated on the half of the list after the pivot element, and the pivot element or 0, all added together. It took me approximately 8 hours to write it:

#!/bin/bash
# Euler1 in Bash

euler1() {
    # if the list is empty, return 0
    if [ $# -le 0 ]; then
        echo 0

    else
        #get the index position of the list's middle element
        pivot=(( ($#-1) / 2 + 1 ))

        #calculate a value for the middle element
        thisVal=${!pivot}
        if [ $[$thisVal%3] -gt 0 ] && [ $[$thisVal%5] -gt 0 ]; then
            thisVal=0
        fi

        #recursively process the half of the list below the middle element
        pre=`euler1 ${@:1:(($pivot-1))}`
        #recursively process the half of the list above the middle element
        post=`euler1 ${@:(($pivot+1))}`

        #return thisVal + the results from the first and last halves
        echo $(( $thisVal + $pre + $post ))
    fi
}

echo $( euler1 `seq 1 999` )

Of note is how recursive calls are made, and how an arbitrarily long list of parameters are passed. Also of note is all the strange sigils and punctuation, which, I'll be honest, I still haven't wrapped my head around. The runtime seems to be very anal about whitespace and punctuation, and the rules seem to be quite arbitrary. This language is quite capable, but I am not a fan of its syntax. I tried running the same code on a Bash shell in Cygwin, but it wouldn't work - I think the shell was an older version. I actually had to make extensive changes to get this to work, including replacing the implicit passed-in variable with an explicitly declared one, different array access notation, and the way the recursive calls are made:

#!/bin/bash
#Euler1 in bash

euler1() {
    ints=("$@")

    # if the list is empty, return 0
    len=${#ints[@]}
    if [ $len -le 0 ]; then
        echo 0

    else
        #get the index position of the list
        pivot=$[ ($len-1)/2 ]

        thisVal=${ints[$pivot]}
        if [ $[$thisVal%3] -gt 0 ] && [ $[$thisVal%5] -gt 0 ]; then
            thisVal=0
        fi

        #recursively process the half of the list below the middle element
        intsPre=${ints[@]:0:(($pivot))}
        pre=$( euler1 $intsPre )
        #recursively process the half of the list above the middle element
        intsPost=${ints[@]:(($pivot)+1)}
        post=$( euler1 $intsPost )

        echo $[ $pre+$thisVal+$post ]
    fi
}

echo $( euler1 `seq 1 999` )

Here is QuickSort one more time, written in a slightly different manner. This one runs dramatically faster than the last two, not sure why...

#!/bin/bash
# Euler1 in Bash

euler1(){
    # if the list is empty, return 0
    if [ $# -le 0 ]; then
        echo 0

    else
        #get the index position of the list's middle element
        pivot=$((($#-1) / 2 + 1))
        pre=`euler1 ${@:1:(($pivot - 1))}`
        post=`euler1 ${@:(($pivot + 1))}`
        i=0
        if [ $[${!pivot} % 3] = 0 ] || [ $[${!pivot} % 5] = 0 ]; then
            i=${!pivot}
        fi
        echo $(( $pre + $i + $post ))
    fi
}

Here’s one more – an elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. Don’t sweat it if this seems inscrutable; click the blog link above for an explanation.

#!/bin/bash
#Euler1 in bash

mySum() {
    echo "(($2/$1) * (($2/$1)+1) * $1 / 2)"
}

euler1() {
    echo $[ $(mySum 3 $1) + $(mySum 5 $1) - $(mySum 15 $1) ]
}

echo $(euler1 999)

Bash does ship with a couple of debuggers, which look very capable, but for some reason I didn't have a lot of luck with them. To run this code: there's a shebang, simply call your script.

$ ./euler1.sh
233168