eultoil

bench.md

on macbook pro:

Using the non-posix compliant array functionality results in fast code.

$ time bash p43.sh
16695334890

real    0m11.997s
user    0m15.626s
sys     0m11.549s

Making the code posix-compliant (replacing arrays w/ space-delimited strings) made the code slower, though dash is a bit faster than bash. I can't seem to figure out how to do exponents in dash $(()) arithmetic blocks.

$ time bash p43.sh              
16695334890                                 
                               
real    0m37.265s              
user    0m28.518s               
sys     0m22.951s                                                  

$ time dash p43.sh                      
16695334890                                               
                                                                             
real    0m34.491s                                                     
user    0m26.244s                                                                                   
sys     0m22.270s

p43.sh

#!/bin/bash

# PROBLEM STATEMENT: (https://projecteuler.net/problem=43)
# The number, 1406357289, is a 0 to 9 pandigital number because it is made up
# of each of the digits 0 to 9 in some order, but it also has a rather
# interesting sub-string divisibility property.
#
# Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note
# the following:
#
# d2d3d4=406 is divisible by 2
# d3d4d5=063 is divisible by 3
# d4d5d6=635 is divisible by 5
# d5d6d7=357 is divisible by 7
# d6d7d8=572 is divisible by 11
# d7d8d9=728 is divisible by 13
# d8d9d10=289 is divisible by 17
# Find the sum of all 0 to 9 pandigital numbers with this property.

divs=(17 13 11 7 5 3 2 1)

count=0
a=${divs[0]}

# start by finding all the 2- (0-prefixed) & 3-digit numbers divisible by 17
while [ $a -lt 1000 ]
do
    d0=$(($a%10))
    d1=$(($a/10%10))
    d2=$((a/100))
    if [ $d0 -ne $d1 -a $d0 -ne $d2 -a $d1 -ne $d2 ]
        then
        solns[$((count++))]=$a
    fi
    a=$((a+${divs[0]}))
done

for m in $(seq 1 7)
do
    old_solns=${solns[@]}
    count=0
    solns=()
    echo "old solns $m:::" "${old_solns[@]}"
    for val in ${old_solns[@]}
    do
        for j in {0..9}
        do
            c=$((j*10**(m+2)+val))
            r=$(((c/(10**m))%divs[m]))

            if [ $r -eq 0 ]
                then
                    l=$(echo $c | sed 's/\(.\)/\1 /g' | tr ' ' '\n' | sort | uniq | tail +2 | wc -l)
                    if [ $l -eq $((m+3)) -o $m -lt 7 -a $l -ge $((m+2)) ]
                        then
                            solns[$((count++))]=$c
                    fi
            fi
        done
    done
done

echo "solns :::" "${solns[@]}"
echo $(( IFS=+; echo "${solns[*]}" ) | bc)

p43_posix.sh

#!/bin/sh

# PROBLEM STATEMENT: (https://projecteuler.net/problem=43)
# The number, 1406357289, is a 0 to 9 pandigital number because it is made up
# of each of the digits 0 to 9 in some order, but it also has a rather
# interesting sub-string divisibility property.
#
# Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note
# the following:
#
# d2d3d4=406 is divisible by 2
# d3d4d5=063 is divisible by 3
# d4d5d6=635 is divisible by 5
# d5d6d7=357 is divisible by 7
# d6d7d8=572 is divisible by 11
# d7d8d9=728 is divisible by 13
# d8d9d10=289 is divisible by 17
# Find the sum of all 0 to 9 pandigital numbers with this property.

divs="13 11 7 5 3 2 1"

a=17
# start by finding all the 2- (0-prefixed) & 3-digit numbers divisible by 17
while [ $a -lt 1000 ]
do
    d0=$((a%10))
    d1=$((a/10%10))
    d2=$((a/100))
    if [ $d0 -ne $d1 -a $d0 -ne $d2 -a $d1 -ne $d2 ]
        then
        solns=$solns" "$a
    fi
    a=$((a+17))
done

for m in $(seq 1 7)
do
    old_solns=$solns
    mod=$(echo $divs | cut -d ' ' -f $m)
    count=0
    solns=""
    for val in $old_solns
    do
        for j in $(seq 0 9)
        do
            c=$(echo "$j*10^($m+2)+$val" | bc)
            r=$(echo "($c/(10^$m))%$mod" | bc)

            if [ $r -eq 0 ]
                then
                    l=$(echo $c | sed 's/\(.\)/\1 /g' | tr ' ' '\n' | sort | uniq | tail +2 | wc -l)
                    if [ $l -eq $((m+3)) -o $m -lt 7 -a $l -eq $((m+2)) ]
                        then
                            solns=$solns" "$c
                    fi
            fi
        done
    done
done

echo $(echo "0$solns" | sed 's/ /+/g' | bc)