Aoc 2019: tschulte

tschulte

203910?v=4

tschulte
: tschulte

About me

Nothing here yet. Update your profile at /profiles/tschulte.adoc

Day 01: groovy

The Tyranny of the Rocket Equation

First Star

The sollution for the first star was pretty straightforward. Iterate over all lines in the input file, convert the line’s content to an int, calculate the required fuel and sum all values.

def calculateFuel(int mass) {
    return (int)(mass / 3) - 2
}

def fuel = 0
new File('input.txt').eachLine('UTF-8') { line ->
    fuel += calculateFuel(Integer.parseInt(line))
}
println fuel

Second Star

For the second star, I first misunderstood the problem and tried to take the result from the first star and calculate the required fuel for that. But that resulted in a wrong value.

The final solution was to refactor the calculateFuel to recursively call itself, when the fuel was greater than 0.

def calculateFuel(int mass) {
    int fuel = (int)(mass / 3) - 2
    return fuel > 0 ? fuel + calculateFuel(fuel) : 0
}

Day 02: groovy

1202 Program Alarm

The first method parseInput takes the input string, splits it and converts each element to an int.

def parseInput(def input) {
    return input.split(',').collect(Integer.&parseInt)
}

The second method takes the input, replaces it in place with the changed values and returns the output value.

def computeOutput(def input) {
    for (int i = 0; i < input.size();) {
        int operator = input[i++]
        if (operator == 99) {
            break
        }
        int a = input[input[i++]]
        int b = input[input[i++]]
        if (operator == 1) {
            input[input[i++]] = a + b
        }
        else if (operator == 2) {
            input[input[i++]] = a * b
        }
        else {
            throw new IllegalArgumentException("$i")
        }
    }
    return input[0]
}

Now we need a method to replace the noun and the verb.

def restoreState(def input, def noun, def verb) {
    input[1] = noun
    input[2] = verb
    return input
}

Putting it all together to get the first star. We create a copy of the input list, because we will need the input unchanged for the second star, and computeOutput alters the input list.

def input = parseInput(new File('input.txt').getText('UTF-8').trim())
println computeOutput(restoreState(new ArrayList(input), 12, 2))

For the second star, we try every combination of noun and verb in the range 0..99 brute force. Maybe there is a better sollution, but this is fast enough and not worth the effort.

def bruteForce(def input) {
    for (int noun = 0; noun <= 100; noun++) {
        for (int verb = 0; verb <= 100; verb++) {
            if (computeOutput(restoreState(new ArrayList(input), noun, verb)) == 19690720) {
                println (100 * noun + verb)
                return
            }
        }
    }
}

Day 03: groovy

Crossed Wires

day03.groovy

import groovy.transform.*

@EqualsAndHashCode
@ToString
class Coordinate {
    final int x
    final int y

    Coordinate(int x, int y) {
        this.x = x
        this.y = y
    }

    Coordinate next(int x, int y) {
        return new Coordinate(this.x + x, this.y + y)
    }

    int manhattanDistance(Coordinate other) {
        return Math.abs(x - other.x) + Math.abs(y - other.y)
    }
}

def coordinate(int x, int y) {
    return new Coordinate(x, y)
}

assert coordinate(0, 0).manhattanDistance(coordinate(3, -3)) == 6

def wire(String path) {
    def wire = [:]
    def currentPosition = coordinate(0, 0)
    def step = 0
    path.split(',').each { pathStep ->
        int amount = Integer.parseInt(pathStep.substring(1))
        if (pathStep.startsWith('R')) {
            amount.times {
                currentPosition = currentPosition.next(1, 0)
                wire.putIfAbsent(currentPosition, ++step)
            }
        }
        else if (pathStep.startsWith('L')) {
            amount.times {
                currentPosition = currentPosition.next(-1, 0)
                wire.putIfAbsent(currentPosition, ++step)
            }
        }
        else if (pathStep.startsWith('D')) {
            amount.times {
                currentPosition = currentPosition.next(0, 1)
                wire.putIfAbsent(currentPosition, ++step)
            }
        }
        else if (pathStep.startsWith('U')) {
            amount.times {
                currentPosition = currentPosition.next(0, -1)
                wire.putIfAbsent(currentPosition, ++step)
            }
        }
    }
    return wire
}

def combine(def wires) {
    def combined = [:].withDefault { 0 }
    def centralPort = coordinate(0, 0)
    wires.flatten().findAll { it != centralPort }.each { combined[it] = combined[it] + 1 }
    return combined
}

assert wire("R2,D2,L2,U1") == [
    (coordinate(1, 0)): 1,
    (coordinate(2, 0)): 2,
    (coordinate(2, 1)): 3,
    (coordinate(2, 2)): 4,
    (coordinate(1, 2)): 5,
    (coordinate(0, 2)): 6,
    (coordinate(0, 1)): 7,
]
assert wire("R2,D2,L2,U2") == [
    (coordinate(1, 0)): 1,
    (coordinate(2, 0)): 2,
    (coordinate(2, 1)): 3,
    (coordinate(2, 2)): 4,
    (coordinate(1, 2)): 5,
    (coordinate(0, 2)): 6,
    (coordinate(0, 1)): 7,
    (coordinate(0, 0)): 8,
]

def smallestManhattanDistance(List<String> lines) {
    def centralPort = coordinate(0, 0)
    return combine(lines.collect { line -> wire(line) }*.keySet())
        .findAll { entry -> entry.value > 1 }
        .collect { entry -> centralPort.manhattanDistance(entry.key) }
        .sort()
        .first()
}

assert smallestManhattanDistance(["R8,U5,L5,D3", "U7,R6,D4,L4"]) == 6
assert smallestManhattanDistance(["R75,D30,R83,U83,L12,D49,R71,U7,L72", "U62,R66,U55,R34,D71,R55,D58,R83"]) == 159
assert smallestManhattanDistance(["R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51", "U98,R91,D20,R16,D67,R40,U7,R15,U6,R7"]) == 135

println smallestManhattanDistance(new File('input.txt').readLines('UTF-8'))

def smallestSumOfSteps(List<String> lines) {
    def centralPort = coordinate(0, 0)
    def wires = lines.collect { line -> wire(line) }
    return combine(wires*.keySet())
        .findAll { entry -> entry.value > 1 }.keySet()
        .collect { intersection ->
            wires.collect { wire -> wire[intersection] }.sum()
        }.sort().first()
}

assert smallestSumOfSteps(["R8,U5,L5,D3", "U7,R6,D4,L4"]) == 30
assert smallestSumOfSteps(["R75,D30,R83,U83,L12,D49,R71,U7,L72", "U62,R66,U55,R34,D71,R55,D58,R83"]) == 610
assert smallestSumOfSteps(["R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51", "U98,R91,D20,R16,D67,R40,U7,R15,U6,R7"]) == 410

println smallestSumOfSteps(new File('input.txt').readLines('UTF-8'))

Day 04: groovy

Secure Container

For this task I chose to just iterate over the range and check each candidate. There might be a better sollution, but the possible values are still small enough to just check every value.

First Star

def isValid(String password) {
    if (password.size() != 6) {
        return false
    }
    boolean hasDuplicate = false
    Character previousChar = null
    for(int i = 0; i < password.size(); i++) {
        char c = password.charAt(i)
        hasDuplicate = hasDuplicate || c == previousChar
        if (previousChar && previousChar > c) {
            return false
        }
        previousChar = c
    }
    return hasDuplicate
}

assert !isValid("")
assert !isValid("111110")
assert isValid("011111")
assert isValid("111111")
assert isValid("112345")

println((245318..765747).findAll { isValid("$it") }.size())

Second Star

def isValid2(String password) {
    if (password.size() != 6) {
        return false
    }
    def duplicates = [:].withDefault { 1 }
    Character previousChar = null
    for(int i = 0; i < password.size(); i++) {
        char c = password.charAt(i)
        if (c == previousChar) {
            duplicates[c] = duplicates[c] + 1
        }
        if (previousChar && previousChar > c) {
            return false
        }
        previousChar = c
    }
    def duplicateCounts = duplicates*.value
    return !duplicateCounts.empty && !duplicateCounts.findAll { it == 2 }.empty
}


assert isValid2("112233")
assert !isValid2("123444")
assert isValid2("111122")
assert isValid2("111233")

println((245318..765747).findAll { isValid2("$it") }.size())

Day 05: groovy

Sunny with a Chance of Asteroids

For this days task I just copied the sollution from day 2, removed the restoreState and bruteForce methods, and altered the computeOutput method.

computeOutput

def computeOutput(def input, int systemId = 1) {
    for (int i = 0; i < input.size();) {
        int operator = input[i++]
        int firstParameterMode = (int)(operator / 100) % 10
        int secondParameterMode = (int)(operator / 1000) % 10
        int thirdParameterMode = (int)(operator / 10000) % 10
        int opcode = operator % 100
        if (opcode == 99) {
            break
        }
        if (opcode == 1) {
            int a = firstParameterMode == 0 ? input[input[i++]] : input[i++]
            int b = secondParameterMode == 0 ? input[input[i++]] : input[i++]
            input[input[i++]] = a + b
        } else if (opcode == 2) {
            int a = firstParameterMode == 0 ? input[input[i++]] : input[i++]
            int b = secondParameterMode == 0 ? input[input[i++]] : input[i++]
            input[input[i++]] = a * b
        } else if (opcode == 3) {
            input[input[i++]] = systemId
        } else if (opcode == 4) {
            println(firstParameterMode == 0 ? input[input[i++]] : input[i++])
        } else if (opcode == 5) {
            int a = firstParameterMode == 0 ? input[input[i++]] : input[i++]
            int b = secondParameterMode == 0 ? input[input[i++]] : input[i++]
            if (a != 0) {
                i = b
            }
        } else if (opcode == 6) {
            int a = firstParameterMode == 0 ? input[input[i++]] : input[i++]
            int b = secondParameterMode == 0 ? input[input[i++]] : input[i++]
            if (a == 0) {
                i = b
            }
        } else if (opcode == 7) {
            int a = firstParameterMode == 0 ? input[input[i++]] : input[i++]
            int b = secondParameterMode == 0 ? input[input[i++]] : input[i++]
            input[input[i++]] = a < b ? 1 : 0
        } else if (opcode == 8) {
            int a = firstParameterMode == 0 ? input[input[i++]] : input[i++]
            int b = secondParameterMode == 0 ? input[input[i++]] : input[i++]
            input[input[i++]] = a == b ? 1 : 0
        }
        else {
            throw new IllegalArgumentException("$i")
        }
    }
    return input[0]
}

Day 06: bash

Universal Orbit Map

I wanted to solve this days puzzle using git and bash.

The idea was pretty straightforward:

create a git repository
initialize it with the branch COM and an empty commit
for each line of the input file
- split it into two parts
- checkout the branch named by the first part
- create a new branch named by the second part and create an empty commit
iterate over all branches and count the number of commits (and subtract 1)

This worked nice with the sample input, but the lines in the real input where not in the correct order. There where lines, where the first branch has not been created yet. Therefore I had to change the code to not process lines, where the first branch has not been created yet, but process all unprocessed lines again and again, until all lines have been processed.

day06_1.sh

#!/usr/bin/env bash

function initRepo {
    rm -rf repo
    git init repo > /dev/null 2>&1
    git -C repo checkout --orphan COM > /dev/null 2>&1
    git -C repo commit --allow-empty -m "COM" > /dev/null 2>&1
    readarray -t lines < $1
    while [[ ${#lines[@]} > 0 ]]
    do
        current_lines=${lines[@]}
        lines=()
        for line in ${current_lines[@]}
        do
            IFS=')' read -ra split <<< "$line"
            a=${split[0]}
            b=${split[1]}
            if git -C repo checkout "$a" > /dev/null 2>&1
            then
                git -C repo checkout -b "$b" > /dev/null 2>&1
                git -C repo commit --allow-empty -m "$b" > /dev/null 2>&1
            else
                lines+=($line)
            fi
        done
    done
}

function count_orbits {
    git -C repo for-each-ref --format='%(refname)' | while read branch
    do
        count=`git -C repo log --oneline "$branch" | wc -l`
        orbits=$(($orbits + $count - 1))
        echo $orbits
    done
}

initRepo test-input.txt
count_orbits

initRepo input.txt
count_orbits

The initialization of the git repo took very long.

But for the second star, I could now only count the number of commits YOU..SAN~ and SAN..YOU~.

day06_2.sh

#!/usr/bin/env bash


function count_transfers {
    echo "$((`git -C repo log --oneline YOU..SAN~ | wc -l` + `git -C repo log --oneline SAN..YOU~ | wc -l`))"
}

count_transfers

Day 07: groovy

Amplification Circuit

For this days task I just copied the sollution from day 9 (since I solved that day first) and altered the computeOutput method to allow multiple inputs for opcode 3.

computeOutput

int getIndex(def input, int parameterMode, int relativeBase, int index) {
    if (parameterMode == 0) {
        index = input[index]
    } else if (parameterMode == 2) {
        index = input[index] + relativeBase
    }
    return index
}

def getValue(def input, int parameterMode, int relativeBase, int index) {
    return input[getIndex(input, parameterMode, relativeBase, index)] ?: 0L
}
def setValue(def input, int parameterMode, int relativeBase, int index, long value) {
    assert parameterMode != 1
    input[getIndex(input, parameterMode, relativeBase, index)] = value
}

def computeOutput(def input, def io = []) {
    int relativeBase = 0
    for (int i = 0; i < input.size();) {
        long operator = input[i++]
        int firstParameterMode = (int)(operator / 100) % 10
        int secondParameterMode = (int)(operator / 1000) % 10
        int thirdParameterMode = (int)(operator / 10000) % 10
        int opcode = operator % 100
        if (opcode == 1) {
            long a = getValue(input, firstParameterMode, relativeBase, i++)
            long b = getValue(input, secondParameterMode, relativeBase, i++)
            setValue(input, thirdParameterMode, relativeBase, i++, a + b)
        } else if (opcode == 2) {
            long a = getValue(input, firstParameterMode, relativeBase, i++)
            long b = getValue(input, secondParameterMode, relativeBase, i++)
            setValue(input, thirdParameterMode, relativeBase, i++, a * b)
        } else if (opcode == 3) {
            setValue(input, firstParameterMode, relativeBase, i++, io.pop())
        } else if (opcode == 4) {
            io << getValue(input, firstParameterMode, relativeBase, i++)
        } else if (opcode == 5) {
            long a = getValue(input, firstParameterMode, relativeBase, i++)
            long b = getValue(input, secondParameterMode, relativeBase, i++)
            if (a != 0) {
                i = b
            }
        } else if (opcode == 6) {
            long a = getValue(input, firstParameterMode, relativeBase, i++)
            long b = getValue(input, secondParameterMode, relativeBase, i++)
            if (a == 0) {
                i = b
            }
        } else if (opcode == 7) {
            long a = getValue(input, firstParameterMode, relativeBase, i++)
            long b = getValue(input, secondParameterMode, relativeBase, i++)
            setValue(input, thirdParameterMode, relativeBase, i++, a < b ? 1 : 0)
        } else if (opcode == 8) {
            long a = getValue(input, firstParameterMode, relativeBase, i++)
            long b = getValue(input, secondParameterMode, relativeBase, i++)
            setValue(input, thirdParameterMode, relativeBase, i++, a == b ? 1 : 0)
        } else if (opcode == 9) {
            relativeBase += getValue(input, firstParameterMode, relativeBase, i++)
        }
        else if (opcode == 99) {
            break
        }
        else {
            throw new IllegalArgumentException("$i: $opcode")
        }
    }
    return io
}

First Star

def maxThrusterSignal(def input) {
    return (0..4).permutations { phaseSettings ->
        phaseSettings.inject(0L) { output, phaseSetting ->
            return computeOutput(new ArrayList(input), [phaseSetting, output]).first()
        }
    }.max()
}
println maxThrusterSignal(input)

I was not able to solve the second star yet. The following does not work.

Second Star

def maxThrusterSignalFeedbackLoop(def input) {
    return (5..9).permutations { phaseSettings ->
        phaseSettings.collect { phaseSetting ->
            [phaseSetting: phaseSetting, input: new ArrayList(input)]
        }
    }.collect { permutation ->
        def totalOutput = []
        def lastOutput = [0L]
        while (!lastOutput.isEmpty()) {
            lastOutput = permutation.inject(lastOutput) { output, entry ->
                def io = [entry.phaseSetting, output].flatten().findAll { it != null }
                //entry.phaseSetting = null
                return computeOutput(entry.input, io)
            }
            if (!lastOutput.isEmpty()) {
                totalOutput = lastOutput
            }
        }
        return totalOutput.first()
    }.max()
}
println maxThrusterSignalFeedbackLoop(input)

Day 09: groovy

Sensor Boost

For this days task I just copied the sollution from day 5 and altered the computeOutput method.

computeOutput

int getIndex(def input, int parameterMode, int relativeBase, int index) {
    if (parameterMode == 0) {
        index = input[index]
    } else if (parameterMode == 2) {
        index = input[index] + relativeBase
    }
    return index
}

def getValue(def input, int parameterMode, int relativeBase, int index) {
    return input[getIndex(input, parameterMode, relativeBase, index)] ?: 0
}
def setValue(def input, int parameterMode, int relativeBase, int index, long value) {
    assert parameterMode != 1
    input[getIndex(input, parameterMode, relativeBase, index)] = value
}

def computeOutput(def input, long systemId = 1) {
    int relativeBase = 0
    def output = []
    for (int i = 0; i < input.size();) {
        long operator = input[i++]
        int firstParameterMode = (int)(operator / 100) % 10
        int secondParameterMode = (int)(operator / 1000) % 10
        int thirdParameterMode = (int)(operator / 10000) % 10
        int opcode = operator % 100
        if (opcode == 1) {
            long a = getValue(input, firstParameterMode, relativeBase, i++)
            long b = getValue(input, secondParameterMode, relativeBase, i++)
            setValue(input, thirdParameterMode, relativeBase, i++, a + b)
        } else if (opcode == 2) {
            long a = getValue(input, firstParameterMode, relativeBase, i++)
            long b = getValue(input, secondParameterMode, relativeBase, i++)
            setValue(input, thirdParameterMode, relativeBase, i++, a * b)
        } else if (opcode == 3) {
            setValue(input, firstParameterMode, relativeBase, i++, systemId)
        } else if (opcode == 4) {
            output << getValue(input, firstParameterMode, relativeBase, i++)
        } else if (opcode == 5) {
            long a = getValue(input, firstParameterMode, relativeBase, i++)
            long b = getValue(input, secondParameterMode, relativeBase, i++)
            if (a != 0) {
                i = b
            }
        } else if (opcode == 6) {
            long a = getValue(input, firstParameterMode, relativeBase, i++)
            long b = getValue(input, secondParameterMode, relativeBase, i++)
            if (a == 0) {
                i = b
            }
        } else if (opcode == 7) {
            long a = getValue(input, firstParameterMode, relativeBase, i++)
            long b = getValue(input, secondParameterMode, relativeBase, i++)
            setValue(input, thirdParameterMode, relativeBase, i++, a < b ? 1 : 0)
        } else if (opcode == 8) {
            long a = getValue(input, firstParameterMode, relativeBase, i++)
            long b = getValue(input, secondParameterMode, relativeBase, i++)
            setValue(input, thirdParameterMode, relativeBase, i++, a == b ? 1 : 0)
        } else if (opcode == 9) {
            relativeBase += getValue(input, firstParameterMode, relativeBase, i++)
        }
        else if (opcode == 99) {
            break
        }
        else {
            throw new IllegalArgumentException("$i: $opcode")
        }
    }
    return output
}

First Star

def input = parseInput(new File('input.txt').getText('UTF-8').trim())
println computeOutput(new ArrayList(input))

Second Star

println computeOutput(new ArrayList(input), 2)