#!/bin/bash

set -u

filename="${1:-example.txt}"
exec 3<"$filename"

max_y=0
max_x=0
declare -A map
declare -A tentative
declare -A lowest_distance=()

while read -u 3 line; do
    if [ "x$line" != "x" ]; then
        max_x=${#line}
        for (( a=0; a<$max_x; a++ )); do
            map[$a,$max_y]=${line:$a:1}
        done
        ((max_y+=1))
    fi
done

((max_x-=1))
((max_y-=1))
total_points=$(($max_x*$max_y))

tentative["0,0"]=0

cur_x=0
cur_y=0

do_cost() {
    echo -n "Progress:  0%"

    # bad implementation of djikstra's algorithm
    while [ ! "${lowest_distance[$max_x,$max_y]+abc}" ]; do
        echo -n -e "\rProgress: "
        printf "%2d" $((((${#lowest_distance[@]}*100) / $total_points)))
        echo -n "%"
        lowest_distance[$cur_x,$cur_y]="${tentative["$cur_x,$cur_y"]}"
        unset tentative[$cur_x,$cur_y]
        # now check to the left / right / up / down from our current node
        # and give them tentative values
        for test_x in $((cur_x-1)) $((cur_x+1)); do
            if [ "${map[$test_x,$cur_y]+abc}" ]; then
                if [ ! "${lowest_distance[$test_x,$cur_y]+abc}" ]; then
                    new_cost=${lowest_distance[$cur_x,$cur_y]}
                    ((new_cost+=${map[$test_x,$cur_y]}))
                    if [ "${tentative[$test_x,$cur_y]+abc}" ]; then
                        if [ $new_cost -lt ${tentative[$test_x,$cur_y]} ]; then
                            tentative[$test_x,$cur_y]=$new_cost
                        fi
                    else
                        tentative[$test_x,$cur_y]=$new_cost
                    fi
                fi
            fi
        done
        for test_y in $((cur_y-1)) $((cur_y+1)); do
            if [ "${map[$cur_x,$test_y]+abc}" ]; then
                if [ ! "${lowest_distance[$cur_x,$test_y]+abc}" ]; then
                    new_cost=${lowest_distance[$cur_x,$cur_y]}
                    ((new_cost+=${map[$cur_x,$test_y]}))
                    if [ "${tentative[$cur_x,$test_y]+abc}" ]; then
                        if [ $new_cost -lt ${tentative[$cur_x,$test_y]} ]; then
                            tentative[$cur_x,$test_y]=$new_cost
                        fi
                    else
                        tentative[$cur_x,$test_y]=$new_cost
                    fi
                fi
            fi
        done

        # find the new lowest tentative
        new_location="-1,-1"
        new_value=-1
        for location in "${!tentative[@]}"; do
            if [ $new_location == "-1,-1" ]; then
                new_location=$location
                new_value=${tentative[$location]}
            elif [ "${tentative[$location]}" -lt $new_value ]; then
                new_location=$location
                new_value=${tentative[$location]}
            fi
        done
        if [ "$new_location" == "-1,-1" ]; then
            break
        fi
        cur_x=${new_location%,*}
        cur_y=${new_location#*,}
    done
    echo -e "\rProgress: 100%"

# if we've reached here, we've got the lowest risk route to the bottom right
    echo "Lowest route cost: ${lowest_distance[$max_x,$max_y]}"
}

display_map() {
    for (( y=0; y<=$max_y; y++ )); do
        for (( x=0; x<=$max_x; x++ )); do
            echo -n ${map[$x,$y]}
        done
        echo
    done
}

echo "Part 1"
do_cost

# first, work left to right on the map on the first iteration, that gets this up to 5 wide
x_width=$((max_x+1))
y_height=$((max_y+1))
for cell in $(seq 2 5); do
    for (( y=0; y<$y_height; y++ )); do
        for (( x=0; x<$x_width; x++ )); do
            old_x=$((($x_width*($cell-2))+$x))
            new_x=$((($x_width*($cell-1))+$x))
            new_value=$((${map[$old_x,$y]} + 1))
            if [ $new_value -gt 9 ]; then
                new_value=1
            fi
            map[$new_x,$y]=$new_value
        done
    done
done
# now, we work on the second to 5th y iteration
# in each case, we can take the 2-5 cells of above
# and copy them, then just do the actual work on the 5th
# cell
for y_rep in $(seq 2 5); do
    y_copy_offset=$((($y_rep - 2)*$y_height))
    y_offset=$((($y_rep - 1)*$y_height))
    for (( y=0; y<$y_height; y++ )); do
        for (( x=0; x<$x_width*4; x++ )); do
            old_x=$((x+$x_width))
            value=${map[$old_x,$(($y_copy_offset+$y))]}
            map[$x,$(($y_offset+$y))]=$value
        done
        # now we want to just copy the left one + 1, ish
        for (( x=0; x<$x_width; x++ )); do
            new_x=$((($x_width*4)+$x))
            old_x=$((($x_width*3)+$x))
            new_value=$((${map[$old_x,$(($y_offset+$y))]}))
            ((new_value+=1))
            if [ $new_value -gt 9 ]; then
                new_value=1
            fi
            map[$new_x,$(($y_offset+$y))]=$new_value
        done
    done
done

# we now have a 5*5 grid of the evil! lets change max_x, max_y, and total_points
max_x=$((($x_width * 5) - 1))
max_y=$((($y_height * 5) - 1))
total_points=$(($max_x*$max_y))

unset tentative
unset lowest_distance
declare -A tentative=()
declare -A lowest_distance=()

tentative[0,0]=0
cur_x=0
cur_y=0

echo "Part 2"
#display_map
do_cost