8000 2021: Days 9-12 · einarjon/adventofcode.sh@5f88488 · GitHub
[go: up one dir, main page]
Skip to content

Commit 5f88488

Browse files
einarjoneinarjon
committed
2021: Days 9-12
1 parent 31a5721 commit 5f88488

File tree

5 files changed

+163
-2
lines changed

5 files changed

+163
-2
lines changed

‎2021/09.sh

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
#! /usr/bin/env bash
2+
A=($(< "${1:-9.txt}"))
3+
B=(9${A//?/9}9); for i in "${A[@]}"; do B+=(9${i}9); done; B+=($B); C=("${B[@]}");
4+
n=${#A} N=${#A[@]}
5+
declare -A LOWS
6+
for ((y=1; y<=N; ++y)); do
7+
for ((x=1; x<=n; ++x)); do
8+
while (( ${B[y]:x:1} > ${B[y]:x+1:1} )); do ((++x)); done
9+
low=${B[y]:x:1}
10+
if (( low < ${B[y]:x-1:1} && low < ${B[y]:x+1:1}
11+
&& low < ${B[y-1]:x:1} && low < ${B[y+1]:x:1})); then
12+
LOWS[$y,$x]=$low
13+
fi
14+
done
15+
done
16+
printf -v sum "+%s" "${LOWS[@]}"
17+
echo "9A: $((sum + ${#LOWS[@]}))"
18+
19+
C=(${C[@]//[0-8]/-}) c=0
20+
F=({a..z} {A..Z} {0..8} + _ / =)
21+
idx=($(printf "%s\n" "${!LOWS[@]}" | sort -n))
22+
for i in "${idx[@]}"; do
23+
LOWS[$i]=${F[c]}
24+
x=${i/*,} y=${i/,*}
25+
C[y]=${C[y]:0:x}${F[c]}${C[y]:x+1}
26+
for k in 1 -1; do
27+
j=$k
28+
while [[ ${C[y+j]:x:1} != 9 ]]; do
29+
C[y+j]=${C[y+j]:0:x}${F[c]}${C[y+j]:x+1}
30+
((j+=k));
31+
done
32+
done
33+
(( ++c >= ${#F[@]} && ++d)) && c=0
34+
done
35+
# Terrible "grow"
36+
for i in {1..6}; do
37+
C=($(printf "%s\n" "${C[@]}" | sed -e "s/-\([^9-]\)/\1\1/g;s/\([^9-]\)-/\1\1/g"))
38+
done
39+
while [[ "${C[*]}" == *-* ]]; do
40+
#echo "round $((++round))"
41+
for y in ${!C[@]}; do
42+
[[ ${C[y]} != *-* ]] && continue
43+
minus=($(sed "s/./&\n/g" <<< ${C[y]:1} | grep -n '-'))
44+
for x in ${minus[@]//:*}; do
45+
for j in 1 -1; do
46+
k=$j
47+
while [[ ${C[y+k]:x:1} == - ]]; do ((k+=j)); done
48+
p=${C[y+k]:x:1}
49+
if [[ $p != 9 ]]; then
50+
while ((k+=-j)); do C[y+k]=${C[y+k]:0:x}$p${C[y+k]:x+1}; done
51+
C[y]=${C[y]:0:x}$p${C[y]:x+1}
52+
break
53+
fi
54+
done
55+
done
56+
done
57+
for i in {1..2}; do
58+
C=($(printf "%s\n" "${C[@]}" | sed -e "s/-\([^9-]\)/\1\1/g;s/\([^9-]\)-/\1\1/g"))
59+
done
60+
done
61+
62+
AREA=()
63+
for i in ${F[@]}; do
64+
while read -r A;do
65+
AREA+=(${#A}:$A)
66+
done < <(printf "%s\n" "${C[@]}" | grep -a1 $i | tr -cd "$i-" | tr -s '-' '\n')
67+
done
68+
BIG=($(printf "%s\n" "${AREA[@]//:*}" | sort -nr))
69+
echo "9B: $((BIG[0]*BIG[1]*BIG[2]))"

‎2021/10.sh

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
#!/usr/bin/env bash
2+
A=($(tr '()[]{}<>' '1a2b3c4d' < "${1:-10.txt}"))
3+
while [[ ${A[*]} =~ (1a|2b|3c|4d) ]]; do
4+
A=(${A[@]//1a}); A=(${A[@]//2b}); A=(${A[@]//3c}); A=(${A[@]//4d})
5+
done
6+
# shellcheck disable=SC2034
7+
a=3 b=57 c=1197 d=25137 TMP=(${A[@]//[1234]}) C=()
8+
printf -v sum "+%.1s" "${TMP[@]}" # TMP only contains closing brackets. Print first char
9+
echo "10A: $((sum))"
10+
while read -r -a B; do
11+
sum=0
12+
for i in "${B[@]}"; do sum=$((sum*5+i)); done
13+
C+=($sum)
14+
done < <( printf "%s\n" "${A[@]}" | grep -v -E '[a-d]' | rev | sed 's/./ &/g')
15+
C=($(printf "%s\n" "${C[@]}" | sort -n ))
16+
N=${#C[@]}
17+
echo "10B: ${C[N/2]}"

‎2021/11.sh

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
#!/usr/bin/env bash
2+
3+
A=($(sed -e 's/^/X/;s/./& /g' "${1:-11.txt}"))
4+
Zeros=${A[*]//*/0} flashes=0 last=0 idx=(${!A[@]})
5+
A+=(X X X X X X X X X X X X)
6+
A=(${A[@]//X/-999999999})
7+
flash(){
8+
local n=$1 j cur
9+
((++flashes))
10+
for j in -12 -11 -10 -1 1 10 11 12; do
11+
cur=$((n+j))
12+
((++A[cur] >= 10 && F[cur]++ == 0 )) && flash $cur
13+
done
14+
}
15+
round(){
16+
F=(${Zeros})
17+
for i in ${idx[@]}; do ((++A[i] >= 10 && F[i]++ == 0)) && flash $i ; done
18+
A=(${A[@]//1?/0})
19+
#A=(${A[@]//-99??/-9999})
20+
}
21+
for rounds in {1..100}; do
22+
round
23+
done
24+
echo "11A: $flashes"
25+
while ((flashes-last != 100)); do
26+
((last=flashes,rounds++))
27+
round
28+
done
29+
echo "11B: $rounds"

‎2021/12.sh

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
#!/usr/bin/env bash
2+
declare -A Next=()
3+
IFS=$' -\n'
4+
while read -r a b; do
5+
[[ $a != start ]] && Next[$b]+="$a "
6+
[[ $b != start ]] && Next[$a]+="$b "
7+
done < "${1:-12.txt}"
8+
#for i in "${!Next[@]}"; do echo "$i: '${Next[$i]}'"; done
9+
10+
r() {
11+
local route=$1 cur=$2 visited=$3 k deeper=false
12+
if [[ $cur == end ]]; then
13+
PATHS+=("$route:$cur")
14+
elif [[ $cur != "${cur,,}" || $route != *:${cur}:*
15+
|| ($cur == "${cur,,}" && $((visited++)) == 0) ]]; then
16+
for k in ${Next[$cur]}; do
17+
r "$route:$cur" "$k" $visited
18+
done
19+
fi
20+
}
21+
22+
PATHS=()
23+
r "" start 1
24+
echo "12A: ${#PATHS[@]}"
25+
PATHS=()
26+
r "" start 0
27+
echo "12B: ${#PATHS[@]}"

‎2021/README.md

Lines changed: 21 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -21,15 +21,16 @@ Description of what I'm doing. Contains spoilers....
2121
2. Same function, but change the input for every char.
2222

2323
### 04.sh
24-
1. Use an array to store all lines/rows of a bingo card. Delete numbers from all lines until a line is empty.
24+
1. Use an array to store all lines/rows of a bingo card. Delete numbers from all lines until a line is empty.
2525
2. Remove a card when a line is empty. Keep going until all cards are gone.
2626

2727
### 05.sh
2828
1. Mark all points on the grid in a hash table. Return a count of points that are != 1.
2929
2. Mark diagonals on a second hash table. Add the first hash table to it and return a count of points that are != 1.
3030

3131
### 06.sh
32-
Store a count of the fishes each day in a circular buffer, with the current 0-day at n%9. Bash arrays are circular by default.
32+
80 rounds can be done in half a second with string shenaningans, but 256 days would take terabytes of RAM, and lots of time.
33+
Instead store a count of the fishes each day in a circular buffer, with the current 0-day at n%9. Bash arrays are circular by default.
3334

3435
### 07.sh
3536
1. Use the median.
@@ -38,3 +39,21 @@ Description of what I'm doing. Contains spoilers....
3839
### 08.sh
3940
1. Simple grep to fish out the output digits and isolate the ones with 2-4 or 7 digits.
4041
2. A damn bother, since the letters were scrambled. Assigned the numbers based on length. The 5-6 length ones got special handling, by checking the length after removing the letters that make up 4 and 7. That was enough to identify every one.
42+
43+
### 09.sh
44+
1. For each line, go forward in the string while the next char is lower. Once you reach that, add a low point if all 4 neighbours are higher.
45+
2. Clean out the map so that all numbers except edges and 9s are empty. Add each low point from part 1 with a different symbol.
46+
Use terrible bash to grow the symbols until the whole map is filled. Count the size of each symbol block.
47+
48+
### 10.sh
49+
Renamed the brackets for easier grok-ing, and so that I could assign values to each one.
50+
1. Keep removing "innermost" bracket pairs until none remains, then remove opening brackets and sum up the values in the first column, if any.
51+
2. Remove any string containing a closing bracket, reverse the rest. Instead of adding a closing bracket, add the value for each opening bracket at a time.
52+
53+
### 11.sh
54+
1. Convert the map to a 1D array, and add -9999999 to the sides so I don\'t need to think about edges. Recursve function to flash the octopi.
55+
2. Run until all fields flash at once.
56+
57+
### 12.sh
58+
1. Brute force. Simplified version of the recursive functions of 2015 (9 and 13). Collect a hashmap wit the destinations for each cave. Remove "start" from the destinations to simplify coding.
59+
2. Add a dumb check to allow the first lowercase cave twice. Takes way too long to run.

0 commit comments

Comments
 (0)
0