Bash Number Of Disc Intersections
number_of_disc_intersections() {
local -n _a="$1"
local _c=${#_a[@]}
local -a _start _end
local _k
for ((_k = 0; _k < _c; _k++)); do _start[_k]=0; _end[_k]=0; done
for _k in "${!_a[@]}"; do
local _v=${_a[$_k]}
local _key
if (( _k < _v )); then _key=0; else _key=$(( _k - _v )); fi
(( _start[_key]++ ))
if (( _k + _v >= _c )); then _key=$(( _c - 1 )); else _key=$(( _k + _v )); fi
(( _end[_key]++ ))
done
local _sum=0 _active=0
for ((_k = 0; _k < _c; _k++)); do
_sum=$(( _sum + _active * _start[_k] + (_start[_k] * (_start[_k] - 1)) / 2 ))
_active=$(( _active + _start[_k] - _end[_k] ))
if (( _sum > 10000000 )); then
echo -1
return
fi
done
echo "$_sum"
}
This sorts disc start and end points and counts active overlaps without comparing every pair directly.
Bash Odd Occurrences In Array
odd_occurrences_in_array() {
local -n _a="$1"
local -A _count
local _v
for _v in "${_a[@]}"; do
if [[ -z "${_count[$_v]:-}" ]]; then
_count[$_v]=1
else
unset '_count[$_v]'
fi
done
for _v in "${!_count[@]}"; do
echo "$_v"
return
done
}
This uses XOR to cancel out pairs, leaving only the value that appears an odd number of times.
Bash Palindrome Rearranging
palindrome_rearranging() {
local _s=$1
local -A _val
local _i _c
for ((_i = 0; _i < ${#_s}; _i++)); do
_c=${_s:_i:1}
_val[$_c]=$(( ${_val[$_c]:-0} + 1 ))
done
local _odd=0
for _c in "${!_val[@]}"; do
(( _val[$_c] % 2 != 0 )) && ((_odd++))
done
if (( _odd <= 1 )); then echo true; else echo false; fi
}
This counts character frequency and checks whether the string has the right number of odd counts to form a palindrome.
Bash Passing Cars
passing_cars() {
local -n _a="$1"
local _passing=0 _multiply=0 _v
for _v in "${_a[@]}"; do
if (( _v == 0 )); then
((_multiply++))
elif (( _multiply > 0 )); then
_passing=$(( _passing + _multiply ))
if (( _passing > 1000000000 )); then
echo -1
return
fi
fi
done
echo "$_passing"
}
This counts eastbound cars as it scans, then adds them whenever a westbound car appears.
Bash Peaks
peaks() {
local -n _arr="$1"
local _n=${#_arr[@]}
if (( _n <= 2 )); then
echo 0
return
fi
local -a _sum
for ((_i = 0; _i < _n; _i++)); do _sum[_i]=0; done
local _last=-1 _dist=0 _i
for ((_i = 1; _i + 1 < _n; _i++)); do
_sum[_i]=${_sum[_i-1]}
if (( _arr[_i] > _arr[_i-1] && _arr[_i] > _arr[_i+1] )); then
if (( _i - _last > _dist )); then _dist=$(( _i - _last )); fi
_last=$_i
(( _sum[_i]++ ))
fi
done
_sum[_n-1]=${_sum[_n-2]}
if (( _sum[_n-1] == 0 )); then
echo 0
return
fi
if (( _n - _last > _dist )); then _dist=$(( _n - _last )); fi
local _j
for ((_i = (_dist >> 1) + 1; _i < _dist; _i++)); do
if (( _n % _i == 0 )); then
_last=0
for ((_j = _i; _j <= _n; _j += _i)); do
if (( _sum[_j-1] <= _last )); then
break
fi
_last=${_sum[_j-1]}
done
if (( _j > _n )); then
echo $(( _n / _i ))
return
fi
fi
done
for ((_last = _dist; _n % _last != 0; )); do
((_last++))
done
echo $(( _n / _last ))
}
This finds the peak positions, then tests how many equal blocks can each contain at least one peak.
Bash Perm Check
perm_check() {
local -n _a="$1"
local -a _sorted=($(printf '%s\n' "${_a[@]}" | sort -n))
local _c=${#_sorted[@]}
local _k
for ((_k = 0; _k < _c - 1; _k++)); do
if (( _sorted[_k] != _k + 1 )); then
echo 0
return
fi
done
echo 1
}
This validates that every value from 1 to N appears exactly once.
Bash Perm Missing Element
perm_missing_element() {
local -n _a="$1"
local -a _sorted=($(printf '%s\n' "${_a[@]}" | sort -n))
local _k
for _k in "${!_sorted[@]}"; do
if (( _sorted[_k] != _k + 1 )); then
echo $(( _k + 1 ))
return
fi
done
echo $(( ${#_sorted[@]} + 1 ))
}
This uses the expected sum of 1..N+1 and subtracts the actual sum to find the missing value.
Bash Plagiarism Check
plagiarism_check() {
local -n _code1="$1"
local -n _code2="$2"
local _c1 _c2
_c1=$(IFS=' '; echo "${_code1[*]}")
_c2=$(IFS=' '; echo "${_code2[*]}")
if [[ "$_c1" == "$_c2" ]]; then
echo false
return
fi
local -a _d1 _d2
IFS=' ' read -ra _d1 <<< "$_c1"
IFS=' ' read -ra _d2 <<< "$_c2"
local -A _rcand
local -a _rcand_keys=()
local _k
for _k in "${!_d1[@]}"; do
local _v=${_d1[$_k]}
local _w=${_d2[$_k]}
if [[ "$_v" != "$_w" ]] && ! [[ "$_v" =~ ^-?[0-9]+$ ]]; then
if [[ -z "${_rcand[$_v]:-}" ]]; then
_rcand_keys+=("$_v")
fi
_rcand[$_v]=$_w
fi
done
local _orig _repl
for _orig in "${_rcand_keys[@]}"; do
_repl=${_rcand[$_orig]}
_c1=$(echo "$_c1" | sed -E "s/(^|[^A-Za-z0-9_])${_orig}([^A-Za-z0-9_]|$)/\1PLACEHOLDER${_orig}\2/g")
_c1=$(echo "$_c1" | sed -E "s/(^|[^A-Za-z0-9_])${_orig}([A-Za-z0-9_]|$)/\1PLACEHOLDER${_orig}\2/g")
done
for _orig in "${_rcand_keys[@]}"; do
_repl=${_rcand[$_orig]}
_c1=$(echo "$_c1" | sed -E "s/(^|[^A-Za-z0-9_])PLACEHOLDER${_orig}([^A-Za-z0-9_]|$)/\1${_repl}\2/g")
_c1=$(echo "$_c1" | sed -E "s/(^|[^A-Za-z0-9_])PLACEHOLDER${_orig}([A-Za-z0-9_]|$)/\1${_repl}\2/g")
done
if [[ "$_c1" == "$_c2" ]]; then echo true; else echo false; fi
}
This flattens both snippets, tries consistent identifier replacements, and checks whether the rewritten code matches.
Bash Shape Area
shape_area() {
local _n=$1
if (( _n > 1 )); then
echo $(( $(shape_area $(( _n - 1 ))) + 4 * (_n - 1) ))
else
echo 1
fi
}
This returns the area of the growing n-interesting polygon using the direct formula instead of building the shape.
Bash Stone Blocks
stone_blocks() {
local -n _h="$1"
local -a _height
local _index=0 _blocks=0
local _i
for _i in "${_h[@]}"; do
while (( _index > 0 && _height[_index-1] > _i )); do
((_index--))
done
if (( _index > 0 && _height[_index-1] == _i )); then
continue
fi
_height[_index]=$_i
((_blocks++))
((_index++))
done
echo "$_blocks"
}
This uses a stack of active heights and only counts a new block when the wall needs a new height segment.