BashでProject Euler（8） 二次元配列

Bashには二次元配列はもちろんありません。それらしいことを実現するにはかつてのPerl4のように例えばカンマで区切るようなことをしなければなりません。

#!/bin/bash

N=$1
table=()
for y in `seq 1 $N`; do
    b=()
    for x in `seq 1 $N`; do
        b+=($((x*y)))
    done
    table+=(`echo ${b[@]} | tr -s ' ' ','`)
done

for v in ${table[@]}; do
    echo $v
done

s=0
for((i=0; i<N; ++i)); do
    a=(`echo ${table[$i]} | tr -s ',' ' '`)
    let s+=${a[$i]}
done
echo $s

上は、九九（引数が9なら）の表を作って、対角成分の和を取っています。
1行分の配列を作って、trコマンドでカンマ区切りの文字列にして配列の要素にします。逆に要素を取り出すときは、trコマンドでスペース区切りにして配列にします。

これで、Problem 9が解けます。この問題は真面目に解くと素因数分解が必要です。それを二次元配列で表します。例えば、48=2^3*3は、

2,3 3,1

と表します。

#!/bin/bash

# a=l(m^2-n^2)
# b=2lmn
# c=l(m^2+n^2)
# a+b+c=2l(m^2+mn)=2lm(m+n)

gcd() {
    local n=$1
    local m=$2
    if [ $n -eq 0 ]; then
        echo $m
    elif [ $m -eq 0 ]; then
        echo $n
    else
        local d=`gcd $m $((n%m))`
        echo $d
    fi
}

div_pows() {
    n=$1
    d=$2
    e=0
    while :; do
        if [ $((n%d)) -ne 0 ]; then
            break
        fi
        e=$((e+1))
        n=$((n/d))
    done
    echo $e $n
}

factorize() {
    n=$1
    p=2
    while :; do
        if [ $((p*p)) -gt $n ]; then
            break
        fi
        s=`div_pows $n $p`
        set -- $s
        if [ $1 -gt 0 ]; then
            echo $p,$1
            n=$2
        fi
        p=$((p+1))
    done
    if [ $n -gt 1 ]; then
        echo $n,1
    fi
}

divisors_fs() {
    if [ $# -eq 1 ]; then
        local a=(`echo $1 | tr -s ',' ' '`)
        p=${a[0]}
        e=${a[1]}
        for e1 in `seq 0 $e`; do
            echo $((p**e1))
        done
    else
        # divide fs into fs1 and fs2
        local fs1=()
        local fs2=()
        L=$#
        for k in `seq 0 $((L-1))`; do
            if [ $((k%2)) -eq 0 ]; then
                fs1+=($1)
            else
                fs2+=($1)
            fi
            shift
        done
        
        local divs1=(`divisors_fs ${fs1[@]}`)
        local divs2=(`divisors_fs ${fs2[@]}`)
        for d1 in ${divs1[@]}; do
            for d2 in ${divs2[@]}; do
                echo $((d1*d2))
            done
        done
    fi
}

divisors() {
    if [ $1 -eq 1 ]; then
        echo 1
        return
    fi

    fs=(`factorize $1`)
    ds=(`divisors_fs ${fs[@]}`)
    for d in ${ds[@]}; do
        echo $d
    done
}

triple_divisors() {
    N=$1
    for d1 in `divisors $N`; do
        d=$((N/d1))
        for d2 in `divisors $d`; do
            d3=$((d/d2))
            echo $d1,$d2,$d3
        done
    done
}

triangles() {
    p=$(($1/2))
    for s in `triple_divisors $p`; do
        local ds=(`echo $s | tr -s ',' ' '`)
        l=${ds[0]}
        m=${ds[1]}
        n=$((${ds[2]}-m))
        if [ $n -ge $m ] || [ $n -le 0 ]; then
            continue
        fi
        if [ $(((m+n)%2)) -eq 1 ] && [ `gcd $m $n` -eq 1 ]; then
            echo $l,$m,$n
        fi
    done
}

triangle_product() {
    while read x; do
        local a=(`echo $x | tr -s ',' ' '`)
        local l=${a[0]}
        local m=${a[1]}
        local n=${a[2]}
        echo $((2*l**3*m*n*(m**4-n**4)))
    done
}

N=$1
triangles $N | triangle_product