challenge-100/abigail/bash/ch-2.sh


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#!/bin/sh

#
# See ../README.md
#

#
# Run as: bash ch-2.sh < input-file
#

set -f

#
# Bash only has one-dimensional arrays, so we're using a function
# to map 2-d indices to a 1-d index.
#
# Note also that we can only return numbers 0 - 255 as "return" values
# (by hijacking the return status), which isn't good enough for us,
# so we use the global variable "index" to pass the result back.
#

function idx () {
    local x=$1
    local y=$2
    index=$((x * (x + 1) / 2 + y))
}

#
# Read in the data: we can read a line at the time, and have
# it split on white space, giving use an array of numbers in "row".
# We iterate over the row, mapping the x, y coordinates to a
# single index, and storing the result in the array "numbers".
#

x=0
while read -a row
do    for  ((y = 0; y < ${#row[*]}; y ++))
      do   idx $x $y
           numbers[$index]=${row[$y]}
      done
      x=$((x + 1))
done

#
# Work bottom to top to calculate the minimum path.
#
for  ((r = $x - 2; r >= 0; r --))
do   for  ((y = 0; y <= $r; y ++))
     do   idx $((r + 1)) $y
          val1=${numbers[$index]}
          idx $((r + 1)) $((y + 1))
          val2=${numbers[$index]}
          min=$((val1 < val2 ? val1 : val2))
          idx $r $y
          numbers[$index]=$((numbers[$index] + $min))
     done
done


#
# Print the result.
#
echo ${numbers[0]}