Bash Notes

Bash Largest String

largest_string() {
    local _s=$1
    local -a _c
    local _i _len=${#_s}
    for ((_i = 0; _i < _len; _i++)); do _c[_i]=${_s:_i:1}; done
    local _cur=""
    for ((_i = _len - 1; _i >= 0; _i--)); do
        _cur="${_c[_i]}${_cur}"
        if (( ${#_cur} == 3 )); then
            if [[ "$_cur" == "abb" ]]; then
                _c[_i]="b"; _c[_i+1]="a"; _c[_i+2]="a"
                if [[ -n "${_c[_i+4]:-}" && "${_c[_i+4]}" == "b" ]]; then
                    _i=$(( _i + 4 + 1 ))
                elif [[ -n "${_c[_i+3]:-}" && "${_c[_i+3]}" == "b" ]]; then
                    _i=$(( _i + 3 + 1 ))
                elif [[ "${_c[_i+2]}" == "b" ]]; then
                    _i=$(( _i + 2 + 1 ))
                fi
            fi
            if [[ "${_c[_i+1]}" == "b" ]]; then
                _i=$(( _i + 1 + 1 ))
            else
                ((_i++))
            fi
            _cur=""
        fi
    done
    local _out=""
    for ((_i = 0; _i < _len; _i++)); do _out="${_out}${_c[_i]}"; done
    echo "$_out"
}

This builds the biggest valid string it can under the challenge rules by always choosing the best next character it is allowed to use.

Bash Max Counters

max_counters() {
    local _n=$1
    local -n _a="$2"
    local -n _out="$3"
    local -a _counters
    local _i
    for ((_i = 0; _i < _n; _i++)); do _counters[_i]=0; done
    local _maxCounter=0 _lastUpdate=0
    local _condition=$(( _n + 1 ))
    local _v
    for _v in "${_a[@]}"; do
        if (( _v <= _n )); then
            local _index=$(( _v - 1 ))
            if (( _counters[_index] < _lastUpdate )); then
                _counters[_index]=$_lastUpdate
            fi
            (( _counters[_index]++ ))
            (( _counters[_index] > _maxCounter )) && _maxCounter=${_counters[_index]}
        fi
        if (( _v == _condition )); then
            _lastUpdate=$_maxCounter
        fi
    done
    for _i in "${!_counters[@]}"; do
        if (( _counters[_i] < _lastUpdate )); then
            _counters[_i]=$_lastUpdate
        fi
    done
    _out=("${_counters[@]}")
}

This delays the expensive “set all counters to max” work until it is really needed, which keeps the solution fast.

Bash Max Double Slice Sum

max_double_slice_sum() {
    local -n _arr="$1"
    local _size=${#_arr[@]}
    if (( _size < 3 )); then
        echo 0
        return
    fi
    local -a _p1 _p2
    _p1[1]=0
    _p2[_size-2]=0
    local _i
    for ((_i = 2; _i < _size - 1; _i++)); do
        local _left=$(( _p1[_i-1] + _arr[_i-1] ))
        (( _left < 0 )) && _left=0
        _p1[_i]=$_left
        local _right=$(( _p2[_size-_i] + _arr[_size-_i] ))
        (( _right < 0 )) && _right=0
        _p2[_size-_i-1]=$_right
    done
    local _sum=$(( _p1[1] + _p2[1] ))
    for ((_i = 1; _i < _size - 1; _i++)); do
        local _cand=$(( _p1[_i] + _p2[_i] ))
        if (( _cand > _sum )); then _sum=$_cand; fi
    done
    echo "$_sum"
}

This keeps the best sum ending on the left and starting on the right, then combines them around each middle position.

Bash Max Product Of Three

max_product_of_three() {
    local -n _a="$1"
    local -a _sorted=($(printf '%s\n' "${_a[@]}" | sort -n))
    local _c=${#_sorted[@]}
    local _p1=$(( _sorted[_c-1] * _sorted[_c-2] * _sorted[_c-3] ))
    local _p2=$(( _sorted[0] * _sorted[1] * _sorted[_c-1] ))
    if (( _p1 > _p2 )); then echo "$_p1"; else echo "$_p2"; fi
}

This checks the useful extremes, because the best product can come from either the three largest numbers or two negatives plus one large positive.

Bash Max Profit

max_profit() {
    local -n _a="$1"
    local _price=${_a[0]} _profit=0 _v
    for _v in "${_a[@]}"; do
        (( _v < _price )) && _price=$_v
        local _cur=$(( _v - _price ))
        (( _cur > _profit )) && _profit=$_cur
    done
    echo "$_profit"
}

This tracks the lowest buy price seen so far and updates the best profit as it scans the prices once.

Bash Max Slice Sum

max_slice_sum() {
    local -n _arr="$1"
    local _tmp=-9223372036854775808 _max=-9223372036854775808
    local _v
    for _v in "${_arr[@]}"; do
        if (( _tmp + _v > _v )); then _tmp=$(( _tmp + _v )); else _tmp=$_v; fi
        if (( _tmp > _max )); then _max=$_tmp; fi
    done
    echo "$_max"
}

This is a Kadane-style scan: keep the best running sum and the best overall sum while moving once through the array.

Bash Min Avg Two Slice

min_avg_two_slice() {
    local -n _a="$1"
    local _idx=0
    local _min
    _min=$(echo "scale=10; (${_a[0]} + ${_a[1]}) / 2" | bc)
    local _count=${#_a[@]} _i
    for ((_i = 0; _i < _count - 1; _i++)); do
        local _cur
        _cur=$(echo "scale=10; (${_a[_i]} + ${_a[_i+1]}) / 2" | bc)
        if (( _i + 2 < _count )); then
            local _three
            _three=$(echo "scale=10; (${_a[_i]} + ${_a[_i+1]} + ${_a[_i+2]}) / 3" | bc)
            if (( $(echo "$_three < $_cur" | bc -l) )); then
                _cur=$_three
            fi
        fi
        if (( $(echo "$_cur < $_min" | bc -l) )); then
            _min=$_cur
            _idx=$_i
        fi
    done
    echo "$_idx"
}

This leans on the key trick for this problem: the minimum average slice is always length 2 or 3.

Bash Min Perimeter Rectangle

min_perimeter_rectangle() {
    local _n=$1
    local _i=1
    local _min=9223372036854775807
    while (( _i * _i < _n )); do
        if (( _n % _i == 0 )); then
            local _perim=$(( 2 * (_i + _n / _i) ))
            (( _perim < _min )) && _min=$_perim
        fi
        ((_i++))
    done
    echo "$_min"
}

This searches factor pairs up to the square root and picks the pair with the smallest perimeter.

Bash Missing Integer

missing_integer() {
    local -n _a="$1"
    local -a _sorted=($(printf '%s\n' "${_a[@]}" | sort -nu))
    local _min=1 _v
    for _v in "${_sorted[@]}"; do
        if (( _v > 0 )); then
            if (( _min != _v )); then
                break
            fi
            ((_min++))
        fi
    done
    echo "$_min"
}

This records the positive numbers that exist, then returns the smallest positive value that is still missing.

Bash Nesting

nesting() {
    local _s=$1
    if [[ -z "$_s" ]]; then echo 1; return; fi
    local -a _stack=()
    local _i _c
    for ((_i = 0; _i < ${#_s}; _i++)); do
        _c=${_s:_i:1}
        if [[ "$_c" == ")" ]]; then
            if (( ${#_stack[@]} == 0 )) || [[ "${_stack[-1]}" != "(" ]]; then
                echo 0; return
            fi
            unset '_stack[-1]'
        else
            _stack+=("$_c")
        fi
    done
    if (( ${#_stack[@]} == 0 )); then echo 1; else echo 0; fi
}

This treats the string like a balance counter: open parentheses add one, closing ones remove one.