Bash Notes

Bash Dominator

dominator() {
    local -n _a="$1"
    local _size=0 _value=0 _count=0 _index=0
    local _k _v
    for _k in "${!_a[@]}"; do
        _v=${_a[$_k]}
        if (( _size == 0 )); then
            ((_size++))
            _value=$_v
            _index=$_k
        elif (( _value != _v )); then
            ((_size--))
        else
            ((_size++))
        fi
    done
    local _candidate
    if (( _size > 0 )); then _candidate=$_value; else _candidate=-1; fi
    _count=0
    for _v in "${_a[@]}"; do
        if (( _v == _candidate )); then ((_count++)); fi
    done
    if (( _count <= ${#_a[@]} / 2 )); then
        _index=-1
    fi
    echo "$_index"
}

This finds a value that appears in more than half of the array, then returns one valid index for it.

Bash Equi Leader

equi_leader() {
    local -n _a="$1"
    local _leaderSize=0 _value=0 _leaderCount=0
    local _k _v
    for _k in "${!_a[@]}"; do
        _v=${_a[$_k]}
        if (( _leaderSize == 0 )); then
            ((_leaderSize++))
            _value=$_v
        elif (( _value != _v )); then
            ((_leaderSize--))
        else
            ((_leaderSize++))
        fi
    done
    local _candidate
    if (( _leaderSize > 0 )); then _candidate=$_value; else _candidate=-1; fi
    _leaderCount=0
    for _v in "${_a[@]}"; do
        if (( _v == _candidate )); then ((_leaderCount++)); fi
    done
    local _leader=-1
    local _count=${#_a[@]}
    if (( 2 * _leaderCount > _count )); then
        _leader=$_candidate
    fi
    local _lLeaderCount=0 _equiLeaders=0
    for _k in "${!_a[@]}"; do
        _v=${_a[$_k]}
        local _leftHalf=$(( (_k + 1) / 2 ))
        local _rightHalf=$(( (_count - _k - 1) / 2 ))
        if (( _v == _leader )); then
            ((_lLeaderCount++))
        fi
        local _rLeaderCount=$(( _leaderCount - _lLeaderCount ))
        if (( _lLeaderCount > _leftHalf && _rLeaderCount > _rightHalf )); then
            ((_equiLeaders++))
        fi
    done
    echo "$_equiLeaders"
}

This keeps leader counts on both sides of the split and counts positions where the same leader survives in each half.

Bash Fib Frog

fib_frog() {
    local -n _arr="$1"
    local _size=${#_arr[@]}
    local -a _fib=(0 1)
    local _i=1
    while (( _fib[_i] <= _size )); do
        ((_i++))
        _fib[_i]=$(( _fib[_i-1] + _fib[_i-2] ))
    done
    local -a _q_idx=(-1) _q_jmp=(0)
    local _head=0
    local -a _steps
    for ((_i = 0; _i < _size; _i++)); do _steps[_i]=0; done
    while (( _head < ${#_q_idx[@]} )); do
        local _cidx=${_q_idx[_head]} _cjmp=${_q_jmp[_head]}
        ((_head++))
        local _fidx
        for ((_fidx = ${#_fib[@]} - 1; _fidx >= 2; _fidx--)); do
            local _idx=$(( _cidx + _fib[_fidx] ))
            if (( _idx == _size )); then
                echo $(( _cjmp + 1 ))
                return
            fi
            if (( _idx > _size )) || (( ${_steps[_idx]:-0} )) || (( _arr[_idx] == 0 )); then
                continue
            fi
            if (( _arr[_idx] == 1 )); then
                _steps[_idx]=1
                _q_idx+=("$_idx")
                _q_jmp+=($(( _cjmp + 1 )))
            fi
        done
    done
    echo -1
}

This precomputes Fibonacci jumps, then uses a breadth-first search to find the shortest valid path across the river.

Bash Fish

fish() {
    local -n _a="$1"
    local -n _b="$2"
    local _size=${#_a[@]}
    local _dead=0
    local -a _stack=()
    local _i
    for ((_i = 0; _i < _size; _i++)); do
        if (( _b[_i] == 1 )); then
            _stack+=("${_a[_i]}")
        elif (( ${#_stack[@]} > 0 )); then
            while (( ${#_stack[@]} > 0 )); do
                ((_dead++))
                local _top=${_stack[-1]}
                if (( _a[_i] > _top )); then
                    unset '_stack[-1]'
                    _stack=("${_stack[@]}")
                else
                    break
                fi
            done
        fi
    done
    echo $(( _size - _dead ))
}

This uses a stack for downstream fish and resolves fights only when opposite directions meet.

Bash Flags

flags() {
    local -n _a="$1"
    local _size=${#_a[@]}
    local -a _peak _nxt
    _peak[0]=0
    local _i
    for ((_i = 1; _i < _size; _i++)); do
        local _right=0
        (( _i + 1 < _size )) && _right=${_a[_i+1]}
        if (( _a[_i-1] < _a[_i] && _a[_i] > _right )); then _peak[_i]=1; else _peak[_i]=0; fi
    done
    _nxt[_size-1]=-1
    for ((_i = _size - 2; _i >= 0; _i--)); do
        if (( _peak[_i] )); then _nxt[_i]=$_i; else _nxt[_i]=${_nxt[_i+1]}; fi
    done
    _i=1
    local _result=0
    while (( _i * (_i - 1) <= _size )); do
        local _pos=0 _num=0
        while (( _pos < _size && _num < _i )); do
            _pos=${_nxt[_pos]}
            if (( _pos == -1 )); then break; fi
            ((_num++))
            _pos=$(( _pos + _i ))
        done
        ((_i++))
        (( _num > _result )) && _result=$_num
    done
    echo "$_result"
}

This finds all peaks first, then checks how many flags can be placed while keeping the required distance.

Bash Frog Jmp

frog_jmp() {
    local _x=$1 _y=$2 _d=$3
    echo $(( (_y - _x + _d - 1) / _d ))
}

This computes the jump count with math instead of simulation, which is the cleanest way to solve it.

Bash Frog River One

frog_river_one() {
    local _x=$1
    local -n _a="$2"
    local -A _existing
    local _k _v
    for _k in "${!_a[@]}"; do
        _v=${_a[$_k]}
        if [[ -z "${_existing[$_v]:-}" ]] && (( _v <= _x )); then
            _existing[$_v]=1
            if (( ${#_existing[@]} == _x )); then
                echo "$_k"
                return
            fi
        fi
    done
    echo -1
}

This tracks the earliest time each needed position appears and stops as soon as the frog can cross.

Bash Genomic Range Query

genomic_range_query() {
    local _s=$1
    local -n _p="$2"
    local -n _q="$3"
    local -n _out="$4"
    _out=()
    local _k _idx
    for _idx in "${!_p[@]}"; do
        local _pi=${_p[$_idx]} _qi=${_q[$_idx]}
        local _len=$(( _qi - _pi + 1 ))
        local _sub=${_s:_pi:_len}
        if [[ "$_sub" == *A* ]]; then
            _out[_idx]=1
        elif [[ "$_sub" == *C* ]]; then
            _out[_idx]=2
        elif [[ "$_sub" == *G* ]]; then
            _out[_idx]=3
        else
            _out[_idx]=4
        fi
    done
}

This builds prefix counts for each DNA letter so every query can return the minimum impact factor quickly.

Bash Is Ipv 4 Adress

is_ipv4_address() {
    local _s=$1
    local -a _parts
    IFS='.' read -ra _parts <<< "$_s"
    if (( ${#_parts[@]} != 4 )); then echo false; return; fi
    local _v
    for _v in "${_parts[@]}"; do
        if [[ -z "$_v" ]] || ! [[ "$_v" =~ ^[0-9]+$ ]]; then
            echo false; return
        fi
        if (( ${#_v} > 1 && ${_v:0:1} == 0 )); then
            echo false; return
        fi
        if (( _v > 255 )); then
            echo false; return
        fi
    done
    echo true
}

This splits the string by dots and validates each part as a normal IPv4 octet.

Bash Ladder

ladder() {
    local -n _aArr="$1"
    local -n _bArr="$2"
    local -n _outArr="$3"
    local _size=${#_aArr[@]}
    local _maxB
    _maxB=$(printf '%s\n' "${_bArr[@]}" | sort -n | tail -1)
    local _mod=$(( (1 << _maxB) - 1 ))
    local _limitA
    _limitA=$(printf '%s\n' "${_aArr[@]}" | sort -n | tail -1)
    local -a _fib=(0 1)
    local _i
    for ((_i = 2; _i < _limitA + 2; _i++)); do
        _fib[_i]=$(( (_fib[_i-1] + _fib[_i-2]) & _mod ))
    done
    _outArr=()
    for ((_i = 0; _i < _size; _i++)); do
        _outArr[_i]=$(( _fib[_aArr[_i]+1] & ((1 << _bArr[_i]) - 1) ))
    done
}

This precomputes climb counts once and applies the modulo per query, which avoids recalculating the same paths over and over.