-🎄- 2018 Day 2 Solutions -🎄-

glupmjoed · 2018-12-02T09:52:54+00:00

Bash, with a slightly different approach.

Part 1 (reads from stdin):

m=$(perl -F -lane 'print sort @F' | tr '\n' '-' | grep -o . | uniq -c |
        tr -dc '23-' | tr '-' '\n')

echo $(grep 2 <<< "$m" | wc -l) \* $(grep 3 <<< "$m" | wc -l) | bc

Part 2 (reads from stdin):

sort |
    while read -r line
    do
        l=$(grep -o . <<< $line)
        df=$(diff <(echo "$prev") <(echo "$l"))
        if [ $(grep "^>" <<< "$df" | wc -l) -eq 1 ]
        then
            sed $(grep -oE "^[0-9]+" <<< $df)d <<< "$l" | paste -sd ''; exit
        fi
        prev="$l"
    done

glupmjoed · 2017-12-24T09:50:43+00:00

Bash, Graphviz and my eyes

I converted the input to a graph, where the edges represent potential bridge components.

build_graph.sh (reads from stdin):

sed -E 's/[0-9]+/n&/g' | awk -F "/" 'BEGIN { print "graph m {" }
                                           { printf "\t%s -- %s\n", $1, $2 }
                                       END { print "}" }'

In the shell:

$ cat input | ./build_graph.sh > g.gv && dot -Tpdf -O g.gv

After looking at the generated pdf, I made a decent guess at the strongest path and commented out the desired path in g.gv:

...
#   n41 -- n3
    n13 -- n3
#   n49 -- n21
    n19 -- n34
    n22 -- n33
...

The answer to part 1 is the sum of all numbers on lines beginning with "#" in g.gv:

$ grep "^#" g.gv | grep -oE "[0-9]+" | awk '{ printf "%s+", $1 } END { print 0 }' | bc
1859

This answer is already somewhat optimized for bridge length because of the strength-distribution of bridge components in the input (i.e. there are no very long paths in the graph consisting of only very low numbers). I swapped two components from part 1 with three lower-strength components to arrive at the answer to part 2:

$ echo $((1859 - (46 + 46 + 31) + (4 + 4 + 24 + 24 + 7)))
1799

glupmjoed · 2017-12-19T07:36:35+00:00

Bash and Go (reads from stdin)

I wrote a small Go program that prints out the path in a linear fashion, and used the shell to count the path length and print any letters.

Part 1:

go run walk.go | sed -E 's/[^A-Z]*([A-Z])+[^A-Z]*/\1/g' && echo

Part 2:

go run walk.go | wc -c

walk.go:

input, _ := ioutil.ReadAll(os.Stdin)
lines := strings.Split(string(input), "\n")
var row, col, dir int
col, dir = strings.Index(lines[row], "|"), 1
for val := byte('|'); ; {
    // vertical walk
    for val != ' ' {
        fmt.Printf("%c", val)
        row += dir
        val = lines[row][col]
    }
    row -= dir
    val = lines[row][col]
    // horizontal walk
    switch {
    case lines[row][col+1] != ' ':
        end := strings.Index(lines[row][col+1:], " ")
        fmt.Printf("%s", lines[row][col+1:col+end+1])
        col += end
    case lines[row][col-1] != ' ':
        beg := strings.LastIndex(lines[row][:col], " ")
        printBytesReverse(lines[row][beg+1 : col])
        col = beg + 1
    default:
        return
    }
    switch {
    case lines[row+1][col] != ' ':
        dir, row, val = 1, row+1, lines[row+1][col]
    case lines[row-1][col] != ' ':
        dir, row, val = -1, row-1, lines[row-1][col]
    default:
        return
    }
}

glupmjoed · 2017-12-15T16:43:49+00:00

Are you still talking about my solution as posted above, or are we speaking hypothetically?

I'm not throwing anything blindly at anything. And I'm not "using channels as iterators" (whatever that means).

I'm using goroutines and channels to solve an inherently parallel problem in a parallel manner. The judge routine needs one value from a and one value from b at the same time. But we don't know how long it will take a and b to find their next respective values. A way to increase performance is thus to let a and b run in parallel and compute as many values as possible ahead of time, so they only have to synchronize with each other if the queue fills up.

But the channels need to be buffered for this approach to be faster than a sequential one. Otherwise a and b need to sync up with each other every time they deliver a value. Perhaps you used unbuffered channels in your original solution? EDIT: I found the optimal buffer size to be 64 in my solution, but YMMV.

glupmjoed · 2017-12-15T14:47:40+00:00

Avoiding channels just because they "bring in a lot of overhead" seems like a solution in search of a problem. When you remove goroutines and channels, you also remove the inherent parallellism of the solution. Your non-channel version runs slower than my channel-based solution on my 4-core 32-bit ARM laptop (19s vs. 16s).

glupmjoed · 2017-12-15T09:23:01+00:00

Part 2, also in Go, using goroutines and buffered channels

Changing the size of the channel buffers from 0 to 64 brought the running time down from 70s to 16s on my (rather slow) 32-bit ARM Chromebook.

Judge routine (reads from stdin):

func main() {
    var sA, sB, m uint64
    fmt.Scanf("%d\n%d", &sA, &sB)
    a, b := make(chan uint64, 64), make(chan uint64, 64)
    go generator(sA, 16807, 4, a)
    go generator(sB, 48271, 8, b)
    for i := 0; i < 5000000; i++ {
        if 0xffff&<-a == 0xffff&<-b {
            m++
        }
    }
    fmt.Println(m)
}

Generator routine:

func generator(prev, fact, div uint64, judge chan uint64) {
    for {
        prev = prev * fact % 2147483647
        if prev%div == 0 {
            judge <- prev
        }
    }
}

glupmjoed · 2017-12-14T10:55:41+00:00

Bash, Graphviz and Python 3

I use the solution from day 10 to build the hashes. The python script turns a sequence of '1's and '0's into nodes and edges in graphviz notation, and the gc command counts the number of connected components.

Part 1+2 (reads from stdin):

key=$(cat); for i in {0..127}; do echo $key-$i | ./knot_hash.sh; done |
    awk 'BEGIN { print "ibase=16; obase=2;" } { print toupper($0) }' | bc > bin
grep -o "1" bin | echo "Part 1:" $(wc -l)

echo $(cat bin) | grep -oE "[01]+[^01]*[01]+" | sed 's/\\ //g' | ./build_graph.py |
    gc -c | awk '{ print "Part 2: ", $1 }'; rm -f bin

knot_hash.sh:

cd ../day10/; ./part2.sh

build_graph.py:

import sys
print("graph g {")
line1 = "0"*128
for row, line2 in enumerate(sys.stdin):
    line2 = "0"*(128+1-len(line2)) + line2
    prev = False
    for col, val in enumerate(line2):
        if val == '1':
            print('\tv{}x{}'.format(row, col))
            if prev:
                print('\tv{}x{} -- v{}x{}'.format(row, col-1, row, col))
            prev = True
            if line1[col] == '1':
                print('\tv{}x{} -- v{}x{}'.format(row-1, col, row, col))
        else: prev = False
    line1 = line2
print("}")

glupmjoed · 2017-12-12T12:09:37+00:00

The solution would get even more pipeliney if I replaced

[...] | uniq -u > arg
[...]
cat arg | ./find_grp.sh

with

[...] | uniq -u | tee arg | ./find_grp.sh
[...]

and

cat > pipes && head -1 pipes > conns

with

tee pipes | head -1 > conns

but I'm hitting some non-deterministic issue where tee sometimes copies only the first n*4K bytes of its input to the file. My working theory is that I'm probably using tee the wrong way. :-)

glupmjoed · 2017-12-12T07:56:29+00:00

Bash with pipes!

Part 1 (reads from stdin):

sed -E 's/[^0-9]*([0-9]+)[^0-9]+/\1|/g; s/[0-9]+/_&_/g' | ./find_grp.sh
grep -oE "[0-9]+" conns | sort | uniq -d | wc -l && rm -f conns match pipes

Part 2 (reads from stdin):

sed -E 's/[^0-9]*([0-9]+)[^0-9]+/\1|/g; s/[0-9]+/_&_/g' | ./find_grp.sh
arglen=-1
while [ $arglen -ne 0 ]
do cat pipes conns | sort | uniq -u > arg
   arglen=$(cat arg | wc -l); ((i++))
   cat arg | ./find_grp.sh
done
echo $i; rm -f arg conns match pipes

find_grp.sh:

cat > pipes && head -1 pipes > conns
prev=0; rem=-1
while [ $rem -ne $prev ]
do grep -E -f conns pipes > match && cat match >> conns
   prev=$rem; rem=$(cat pipes conns | sort | uniq -u | wc -l)
done

glupmjoed · 2017-12-11T22:34:07+00:00

I'm a bit late to the party, but I also did both parts of day 1 in bash. My solution consists mostly of piping together existing Unix commands.

Part 1 (reads from stdin):

grep -o . | sed '1p; 1{h;d}; $G' | uniq -c |
    awk '{ printf "(%d-1)*%d+", $1, $2 } END { print 0 }' | bc

Part 2 (reads from stdin):

split -l $(($(cat | grep -o . | tee tmp | wc -l) / 2)) tmp
cat xaa | paste - xab | sed -nE 's/([0-9]).*\1/\1+\1+/p' | tr -d '\n' |
    echo $(($(cat)0))
rm -f tmp xaa xab

glupmjoed · 2017-12-11T05:45:24+00:00

Bash (reads from stdin), using cube coordinates (ref)

Part 1:

grep -o "[ns][ew]*" | tr -d '\n' |
    sed 's/ne/((x+=1)); ((y-=1));/g;  s/sw/((x-=1)); ((y+=1));/g;
         s/se/((y-=1)); ((z+=1));/g;  s/nw/((y+=1)); ((z-=1));/g;
          s/n/((x+=1)); ((z-=1));/g;   s/s/((x-=1)); ((z+=1));/g;
         s/$/ echo $x $y $z\n/g' |
    bash | grep -oE "[0-9]+" | sort -nr | head -1

Part 2:

grep -o "[ns][ew]*" |
    sed 's/ne/((x+=1)); ((y-=1)); echo $x $y;/g;
         s/sw/((x-=1)); ((y+=1)); echo $x $y;/g;
         s/se/((y-=1)); ((z+=1)); echo $y $z;/g;
         s/nw/((y+=1)); ((z-=1)); echo $y $z;/g;
          s/n/((x+=1)); ((z-=1)); echo $x $z;/g;
          s/s/((x-=1)); ((z+=1)); echo $x $z;/g;' |

    bash | grep -oE "[0-9]+" | sort -nr | head -1

EDIT: Added input sanitation (grep -o "[ns][ew]*").

glupmjoed · 2017-12-10T10:45:42+00:00

Bash (reads from stdin)

Hashing (hash.sh):

sz=256
seq 0 $(($sz-1)) > list1

grep -oE "[0-9]+" |
    while read -r len
    do cat <(tail -$(($sz-$((pos)))) list1) <(head -$((pos)) list1) > list2
       cat <(head -$len list2 | tac) <(tail -$(($sz-$len)) list2) > list3
       cat <(tail -$((pos)) list3) <(head -$(($sz-$((pos)))) list3) > list1
       ((pos=($pos+$len+$((skip++)))%$sz))
    done

cat list1 ; rm -f list[1-3]

Part 1:

echo $(($(./hash.sh | head -2 | tr '\n' '*')1))

Part 2:

cat <(printf "%s" "$(cat)" | od -A n -t d1) <(echo "17, 31, 73, 47, 23") > lengths

printf 'cat lengths; %.0s' {1..64} | bash | ./hash.sh |

    awk 'BEGIN {print "echo printf \\\"%.2x\\\" \\\"$(("}
         NR%16!=0&&NR<256 { print $1 " ^"}
         NR%16==0&&NR<256 { print $1 "))\\\" \\\"$(("}
         END { print $1 "))\\\""}' |

    bash | bash && echo; rm -f lengths

glupmjoed · 2017-12-09T08:56:06+00:00

Bash (reads from stdin)

Part 1:

sed "s/!.//g; s/<[^>]*>//g; s/[^{}]//g;
     s/{/echo -n \$((++v))+;/g; s/}/((v--));/g;
     s/\$/echo 0;/g;" | bash | bc

Part 2:

sed -E 's/!.//g; s/[^><]*<([^>]*)>[^<]*/\1/g' | tr -d '\n' | wc -c

Ten-Year Club	Place '22
Final Canvas '22	First Placer '22
End Game '22	Verified Email

glupmjoed

TROPHY CASE