Bash - gregorymorrison/euler1 GitHub Wiki

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 = $(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 a functional version that uses tail recursion with an accumulator. One of the main points here is that the function euler() is deterministic - it will always return the same output for a given input. This is accomplished in part by the absence of any variable manipulation - there are instead only functions which return values. The other main point is that this recursion uses tail call optimization - it's written in such a way that an intelligent compiler can optimize its stack usage to be O(n) instead of O(n!). In English, this means that your program will probably not crash even for hugely recursive calls.

#!/bin/bash
#Euler1 in bash

euler1() {
    if [ $1 -eq 0 ](/gregorymorrison/euler1/wiki/-$1--eq-0-); then
        echo "$2"
    elif [ $(($1%3)) -eq 0 ]] ](/gregorymorrison/euler1/wiki/|-[[-$(($1%5))--eq-0-); then
        echo $(( $(euler1 $(($1-1)) $(($2+$1)) ) ))
    else    
        echo $(( $(euler1 $(($1-1)) $(($2   )) ) ))
    fi
}

echo "euler1 = $(euler1 800 0)"

Well, it turns out that this algorithm gives correct results for smaller values, but it seems that calling euler1() for values ~900 DOES blow the stack. It grinds away for a few minutes, then returns 0. I was running this in a container, and once when the stack blew, it actually crashed not just my container but my docker daemon itself! I wonder if this can be rewritten to handle larger values, or if you can increase the stack space?

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 = $( 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. This one runs half a second slower than the last one, not sure why:

#!/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 = $( euler1 $(seq 1 999) )"

Here is QuickSort one more time, written in a slightly different manner:

#!/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
}

echo "euler1 = $( euler1 $(seq 1 999) )"

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 = $(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