diff options
| author | tchojnacki <tomaszchojnacki2001@gmail.com> | 2022-08-11 19:24:23 +0200 |
|---|---|---|
| committer | tchojnacki <tomaszchojnacki2001@gmail.com> | 2022-08-11 19:24:23 +0200 |
| commit | 0f1e145b80813ae2331b7dac5ace0c589654ad2a (patch) | |
| tree | 25483b8239436dd5aed2fee8811caf0ba893c0bb /aoc-2021-kotlin | |
| parent | 85fb0396bed6a2129b12392941103924b1ab55be (diff) | |
| download | gleam_aoc2020-0f1e145b80813ae2331b7dac5ace0c589654ad2a.tar.gz gleam_aoc2020-0f1e145b80813ae2331b7dac5ace0c589654ad2a.zip | |
Move subproject to avoid IntelliJ module name issues
Diffstat (limited to 'aoc-2021-kotlin')
28 files changed, 2020 insertions, 0 deletions
diff --git a/aoc-2021-kotlin/README.md b/aoc-2021-kotlin/README.md new file mode 100644 index 0000000..c8c777a --- /dev/null +++ b/aoc-2021-kotlin/README.md @@ -0,0 +1,43 @@ +# Advent of Code 2021 in Kotlin + + + + +Welcome to the Advent of Code Kotlin project created by [tchojnacki][github] using the +[Advent of Code Kotlin Template][template] delivered by JetBrains. + +## Progress + +| Day | Part 1 | Part 2 | +|---------------------------------|:------:|:------:| +| Day 1: Sonar Sweep | π | π | +| Day 2: Dive! | π | π | +| Day 3: Binary Diagnostic | π | π | +| Day 4: Giant Squid | π | π | +| Day 5: Hydrothermal Venture | π | π | +| Day 6: Lanternfish | π | π | +| Day 7: The Treachery of Whales | π | π | +| Day 8: Seven Segment Search | π | π | +| Day 9: Smoke Basin | π | π | +| Day 10: Syntax Scoring | π | π | +| Day 11: Dumbo Octopus | π | π | +| Day 12: Passage Pathing | π | π | +| Day 13: Transparent Origami | π | π | +| Day 14: Extended Polymerization | π | π | +| Day 15: Chiton | π | π | +| Day 16: Packet Decoder | π | π | +| Day 17: Trick Shot | π | π | +| Day 18: Snailfish | π | π | +| Day 19: Beacon Scanner | | | +| Day 20: Trench Map | | | +| Day 21: Dirac Dice | | | +| Day 22: Reactor Reboot | | | +| Day 23: Amphipod | | | +| Day 24: Arithmetic Logic Unit | π | π | +| Day 25: Sea Cucumber | π | | + +[aoc]: https://adventofcode.com + +[github]: https://github.com/tchojnacki + +[template]: https://github.com/kotlin-hands-on/advent-of-code-kotlin-template diff --git a/aoc-2021-kotlin/build.gradle.kts b/aoc-2021-kotlin/build.gradle.kts new file mode 100644 index 0000000..51a5269 --- /dev/null +++ b/aoc-2021-kotlin/build.gradle.kts @@ -0,0 +1,19 @@ +plugins { + kotlin("jvm") version "1.6.10" +} + +repositories { + mavenCentral() +} + +tasks { + sourceSets { + main { + java.srcDirs("src") + } + } + + wrapper { + gradleVersion = "7.3" + } +} diff --git a/aoc-2021-kotlin/gradle/wrapper/gradle-wrapper.jar b/aoc-2021-kotlin/gradle/wrapper/gradle-wrapper.jar Binary files differnew file mode 100644 index 0000000..7454180 --- /dev/null +++ b/aoc-2021-kotlin/gradle/wrapper/gradle-wrapper.jar diff --git a/aoc-2021-kotlin/gradle/wrapper/gradle-wrapper.properties b/aoc-2021-kotlin/gradle/wrapper/gradle-wrapper.properties new file mode 100644 index 0000000..e750102 --- /dev/null +++ b/aoc-2021-kotlin/gradle/wrapper/gradle-wrapper.properties @@ -0,0 +1,5 @@ +distributionBase=GRADLE_USER_HOME +distributionPath=wrapper/dists +distributionUrl=https\://services.gradle.org/distributions/gradle-7.3-bin.zip +zipStoreBase=GRADLE_USER_HOME +zipStorePath=wrapper/dists diff --git a/aoc-2021-kotlin/gradlew b/aoc-2021-kotlin/gradlew new file mode 100755 index 0000000..1b6c787 --- /dev/null +++ b/aoc-2021-kotlin/gradlew @@ -0,0 +1,234 @@ +#!/bin/sh + +# +# Copyright Β© 2015-2021 the original authors. +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# https://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. +# + +############################################################################## +# +# Gradle start up script for POSIX generated by Gradle. +# +# Important for running: +# +# (1) You need a POSIX-compliant shell to run this script. If your /bin/sh is +# noncompliant, but you have some other compliant shell such as ksh or +# bash, then to run this script, type that shell name before the whole +# command line, like: +# +# ksh Gradle +# +# Busybox and similar reduced shells will NOT work, because this script +# requires all of these POSIX shell features: +# * functions; +# * expansions Β«$varΒ», Β«${var}Β», Β«${var:-default}Β», Β«${var+SET}Β», +# Β«${var#prefix}Β», Β«${var%suffix}Β», and Β«$( cmd )Β»; +# * compound commands having a testable exit status, especially Β«caseΒ»; +# * various built-in commands including Β«commandΒ», Β«setΒ», and Β«ulimitΒ». +# +# Important for patching: +# +# (2) This script targets any POSIX shell, so it avoids extensions provided +# by Bash, Ksh, etc; in particular arrays are avoided. +# +# The "traditional" practice of packing multiple parameters into a +# space-separated string is a well documented source of bugs and security +# problems, so this is (mostly) avoided, by progressively accumulating +# options in "$@", and eventually passing that to Java. +# +# Where the inherited environment variables (DEFAULT_JVM_OPTS, JAVA_OPTS, +# and GRADLE_OPTS) rely on word-splitting, this is performed explicitly; +# see the in-line comments for details. +# +# There are tweaks for specific operating systems such as AIX, CygWin, +# Darwin, MinGW, and NonStop. +# +# (3) This script is generated from the Groovy template +# https://github.com/gradle/gradle/blob/master/subprojects/plugins/src/main/resources/org/gradle/api/internal/plugins/unixStartScript.txt +# within the Gradle project. +# +# You can find Gradle at https://github.com/gradle/gradle/. +# +############################################################################## + +# Attempt to set APP_HOME + +# Resolve links: $0 may be a link +app_path=$0 + +# Need this for daisy-chained symlinks. +while + APP_HOME=${app_path%"${app_path##*/}"} # leaves a trailing /; empty if no leading path + [ -h "$app_path" ] +do + ls=$( ls -ld "$app_path" ) + link=${ls#*' -> '} + case $link in #( + /*) app_path=$link ;; #( + *) app_path=$APP_HOME$link ;; + esac +done + +APP_HOME=$( cd "${APP_HOME:-./}" && pwd -P ) || exit + +APP_NAME="Gradle" +APP_BASE_NAME=${0##*/} + +# Add default JVM options here. You can also use JAVA_OPTS and GRADLE_OPTS to pass JVM options to this script. +DEFAULT_JVM_OPTS='"-Xmx64m" "-Xms64m"' + +# Use the maximum available, or set MAX_FD != -1 to use that value. +MAX_FD=maximum + +warn () { + echo "$*" +} >&2 + +die () { + echo + echo "$*" + echo + exit 1 +} >&2 + +# OS specific support (must be 'true' or 'false'). +cygwin=false +msys=false +darwin=false +nonstop=false +case "$( uname )" in #( + CYGWIN* ) cygwin=true ;; #( + Darwin* ) darwin=true ;; #( + MSYS* | MINGW* ) msys=true ;; #( + NONSTOP* ) nonstop=true ;; +esac + +CLASSPATH=$APP_HOME/gradle/wrapper/gradle-wrapper.jar + + +# Determine the Java command to use to start the JVM. +if [ -n "$JAVA_HOME" ] ; then + if [ -x "$JAVA_HOME/jre/sh/java" ] ; then + # IBM's JDK on AIX uses strange locations for the executables + JAVACMD=$JAVA_HOME/jre/sh/java + else + JAVACMD=$JAVA_HOME/bin/java + fi + if [ ! -x "$JAVACMD" ] ; then + die "ERROR: JAVA_HOME is set to an invalid directory: $JAVA_HOME + +Please set the JAVA_HOME variable in your environment to match the +location of your Java installation." + fi +else + JAVACMD=java + which java >/dev/null 2>&1 || die "ERROR: JAVA_HOME is not set and no 'java' command could be found in your PATH. + +Please set the JAVA_HOME variable in your environment to match the +location of your Java installation." +fi + +# Increase the maximum file descriptors if we can. +if ! "$cygwin" && ! "$darwin" && ! "$nonstop" ; then + case $MAX_FD in #( + max*) + MAX_FD=$( ulimit -H -n ) || + warn "Could not query maximum file descriptor limit" + esac + case $MAX_FD in #( + '' | soft) :;; #( + *) + ulimit -n "$MAX_FD" || + warn "Could not set maximum file descriptor limit to $MAX_FD" + esac +fi + +# Collect all arguments for the java command, stacking in reverse order: +# * args from the command line +# * the main class name +# * -classpath +# * -D...appname settings +# * --module-path (only if needed) +# * DEFAULT_JVM_OPTS, JAVA_OPTS, and GRADLE_OPTS environment variables. + +# For Cygwin or MSYS, switch paths to Windows format before running java +if "$cygwin" || "$msys" ; then + APP_HOME=$( cygpath --path --mixed "$APP_HOME" ) + CLASSPATH=$( cygpath --path --mixed "$CLASSPATH" ) + + JAVACMD=$( cygpath --unix "$JAVACMD" ) + + # Now convert the arguments - kludge to limit ourselves to /bin/sh + for arg do + if + case $arg in #( + -*) false ;; # don't mess with options #( + /?*) t=${arg#/} t=/${t%%/*} # looks like a POSIX filepath + [ -e "$t" ] ;; #( + *) false ;; + esac + then + arg=$( cygpath --path --ignore --mixed "$arg" ) + fi + # Roll the args list around exactly as many times as the number of + # args, so each arg winds up back in the position where it started, but + # possibly modified. + # + # NB: a `for` loop captures its iteration list before it begins, so + # changing the positional parameters here affects neither the number of + # iterations, nor the values presented in `arg`. + shift # remove old arg + set -- "$@" "$arg" # push replacement arg + done +fi + +# Collect all arguments for the java command; +# * $DEFAULT_JVM_OPTS, $JAVA_OPTS, and $GRADLE_OPTS can contain fragments of +# shell script including quotes and variable substitutions, so put them in +# double quotes to make sure that they get re-expanded; and +# * put everything else in single quotes, so that it's not re-expanded. + +set -- \ + "-Dorg.gradle.appname=$APP_BASE_NAME" \ + -classpath "$CLASSPATH" \ + org.gradle.wrapper.GradleWrapperMain \ + "$@" + +# Use "xargs" to parse quoted args. +# +# With -n1 it outputs one arg per line, with the quotes and backslashes removed. +# +# In Bash we could simply go: +# +# readarray ARGS < <( xargs -n1 <<<"$var" ) && +# set -- "${ARGS[@]}" "$@" +# +# but POSIX shell has neither arrays nor command substitution, so instead we +# post-process each arg (as a line of input to sed) to backslash-escape any +# character that might be a shell metacharacter, then use eval to reverse +# that process (while maintaining the separation between arguments), and wrap +# the whole thing up as a single "set" statement. +# +# This will of course break if any of these variables contains a newline or +# an unmatched quote. +# + +eval "set -- $( + printf '%s\n' "$DEFAULT_JVM_OPTS $JAVA_OPTS $GRADLE_OPTS" | + xargs -n1 | + sed ' s~[^-[:alnum:]+,./:=@_]~\\&~g; ' | + tr '\n' ' ' + )" '"$@"' + +exec "$JAVACMD" "$@" diff --git a/aoc-2021-kotlin/gradlew.bat b/aoc-2021-kotlin/gradlew.bat new file mode 100644 index 0000000..107acd3 --- /dev/null +++ b/aoc-2021-kotlin/gradlew.bat @@ -0,0 +1,89 @@ +@rem +@rem Copyright 2015 the original author or authors. +@rem +@rem Licensed under the Apache License, Version 2.0 (the "License"); +@rem you may not use this file except in compliance with the License. +@rem You may obtain a copy of the License at +@rem +@rem https://www.apache.org/licenses/LICENSE-2.0 +@rem +@rem Unless required by applicable law or agreed to in writing, software +@rem distributed under the License is distributed on an "AS IS" BASIS, +@rem WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +@rem See the License for the specific language governing permissions and +@rem limitations under the License. +@rem + +@if "%DEBUG%" == "" @echo off +@rem ########################################################################## +@rem +@rem Gradle startup script for Windows +@rem +@rem ########################################################################## + +@rem Set local scope for the variables with windows NT shell +if "%OS%"=="Windows_NT" setlocal + +set DIRNAME=%~dp0 +if "%DIRNAME%" == "" set DIRNAME=. +set APP_BASE_NAME=%~n0 +set APP_HOME=%DIRNAME% + +@rem Resolve any "." and ".." in APP_HOME to make it shorter. +for %%i in ("%APP_HOME%") do set APP_HOME=%%~fi + +@rem Add default JVM options here. You can also use JAVA_OPTS and GRADLE_OPTS to pass JVM options to this script. +set DEFAULT_JVM_OPTS="-Xmx64m" "-Xms64m" + +@rem Find java.exe +if defined JAVA_HOME goto findJavaFromJavaHome + +set JAVA_EXE=java.exe +%JAVA_EXE% -version >NUL 2>&1 +if "%ERRORLEVEL%" == "0" goto execute + +echo. +echo ERROR: JAVA_HOME is not set and no 'java' command could be found in your PATH. +echo. +echo Please set the JAVA_HOME variable in your environment to match the +echo location of your Java installation. + +goto fail + +:findJavaFromJavaHome +set JAVA_HOME=%JAVA_HOME:"=% +set JAVA_EXE=%JAVA_HOME%/bin/java.exe + +if exist "%JAVA_EXE%" goto execute + +echo. +echo ERROR: JAVA_HOME is set to an invalid directory: %JAVA_HOME% +echo. +echo Please set the JAVA_HOME variable in your environment to match the +echo location of your Java installation. + +goto fail + +:execute +@rem Setup the command line + +set CLASSPATH=%APP_HOME%\gradle\wrapper\gradle-wrapper.jar + + +@rem Execute Gradle +"%JAVA_EXE%" %DEFAULT_JVM_OPTS% %JAVA_OPTS% %GRADLE_OPTS% "-Dorg.gradle.appname=%APP_BASE_NAME%" -classpath "%CLASSPATH%" org.gradle.wrapper.GradleWrapperMain %* + +:end +@rem End local scope for the variables with windows NT shell +if "%ERRORLEVEL%"=="0" goto mainEnd + +:fail +rem Set variable GRADLE_EXIT_CONSOLE if you need the _script_ return code instead of +rem the _cmd.exe /c_ return code! +if not "" == "%GRADLE_EXIT_CONSOLE%" exit 1 +exit /b 1 + +:mainEnd +if "%OS%"=="Windows_NT" endlocal + +:omega diff --git a/aoc-2021-kotlin/settings.gradle.kts b/aoc-2021-kotlin/settings.gradle.kts new file mode 100644 index 0000000..05a7a1f --- /dev/null +++ b/aoc-2021-kotlin/settings.gradle.kts @@ -0,0 +1 @@ +rootProject.name = "aoc-2021-kotlin" diff --git a/aoc-2021-kotlin/src/Day01.kt b/aoc-2021-kotlin/src/Day01.kt new file mode 100644 index 0000000..4ac1ef7 --- /dev/null +++ b/aoc-2021-kotlin/src/Day01.kt @@ -0,0 +1,24 @@ +object Day01 { + fun part1(input: List<Int>) = + input + .zipWithNext() + .count { it.second > it.first } + + fun part2(input: List<Int>) = + input + .asSequence() + .windowed(3) + .map { it.sum() } + .zipWithNext() + .count { it.second > it.first } +} + +fun main() { + val testInput = readInputAsNumbers("Day01_test") + check(Day01.part1(testInput) == 7) + check(Day01.part2(testInput) == 5) + + val input = readInputAsNumbers("Day01") + println(Day01.part1(input)) + println(Day01.part2(input)) +} diff --git a/aoc-2021-kotlin/src/Day02.kt b/aoc-2021-kotlin/src/Day02.kt new file mode 100644 index 0000000..2eb085a --- /dev/null +++ b/aoc-2021-kotlin/src/Day02.kt @@ -0,0 +1,56 @@ +object Day02 { + private fun dispatchCommands(commands: List<String>, action: (command: String, argument: Int) -> Unit) { + for (line in commands) { + val parts = line.split(" ") + val command = parts[0] + val argument = parts[1].toInt() + + action(command, argument) + } + } + + fun part1(input: List<String>): Int { + var horizontal = 0 + var depth = 0 + + dispatchCommands(input) { command, argument -> + when (command) { + "forward" -> horizontal += argument + "down" -> depth += argument + "up" -> depth -= argument + } + } + + return horizontal * depth + } + + fun part2(input: List<String>): Int { + var horizontal = 0 + var depth = 0 + var aim = 0 + + dispatchCommands(input) { command, argument -> + when (command) { + "forward" -> { + horizontal += argument + depth += aim * argument + } + + "down" -> aim += argument + "up" -> aim -= argument + } + } + + return horizontal * depth + } +} + +fun main() { + val testInput = readInputAsLines("Day02_test") + check(Day02.part1(testInput) == 150) + check(Day02.part2(testInput) == 900) + + val input = readInputAsLines("Day02") + println(Day02.part1(input)) + println(Day02.part2(input)) +} diff --git a/aoc-2021-kotlin/src/Day03.kt b/aoc-2021-kotlin/src/Day03.kt new file mode 100644 index 0000000..1418a2e --- /dev/null +++ b/aoc-2021-kotlin/src/Day03.kt @@ -0,0 +1,51 @@ +object Day03 { + private fun addLists(l1: List<Int>, l2: List<Int>) = l1.zip(l2).map { it.first + it.second } + + private fun valueOfBits(bitList: List<Int>) = bitList.reduce { acc, bit -> acc * 2 + bit } + + private fun invertBits(bitList: List<Int>) = bitList.map { bit -> 1 - bit } + + private fun mostCommonBits(input: List<List<Int>>): List<Int> = + input + .reduce(::addLists) + .map { bit -> if (bit.toDouble() / input.size >= 0.5) 1 else 0 } + + private fun selectByBitCriteria( + input: List<List<Int>>, + comparisonCriteria: (currentList: List<List<Int>>) -> List<Int> + ): List<Int>? { + var list = input + var index = 0 + + while (list.size > 1 && index < list[0].size) { + list = list.filter { e -> e[index] == comparisonCriteria(list)[index] } + index += 1 + } + + return list.getOrNull(0) + } + + fun part1(input: List<List<Int>>): Int = + mostCommonBits(input) + .let { gammaBits -> + val epsilonBits = invertBits(gammaBits) + return valueOfBits(gammaBits) * valueOfBits(epsilonBits) + } + + fun part2(input: List<List<Int>>): Int { + val oxygenRating = selectByBitCriteria(input) { mostCommonBits(it) }!! + val scrubberRating = selectByBitCriteria(input) { invertBits(mostCommonBits(it)) }!! + + return valueOfBits(oxygenRating) * valueOfBits(scrubberRating) + } +} + +fun main() { + val testInput = readInputAsBitLists("Day03_test") + check(Day03.part1(testInput) == 198) + check(Day03.part2(testInput) == 230) + + val input = readInputAsBitLists("Day03") + println(Day03.part1(input)) + println(Day03.part2(input)) +} diff --git a/aoc-2021-kotlin/src/Day04.kt b/aoc-2021-kotlin/src/Day04.kt new file mode 100644 index 0000000..96cdf3b --- /dev/null +++ b/aoc-2021-kotlin/src/Day04.kt @@ -0,0 +1,97 @@ +object Day04 { + private class Bingo(private val revealQueue: ArrayDeque<Int>, private val boards: List<Board>) { + companion object { + fun fromString(input: String): Bingo { + val sections = input.trim().split("(\\r?\\n){2}".toRegex()) + + val revealQueueString = sections.first() + val revealQueue = ArrayDeque(revealQueueString.split(",").map(String::toInt)) + + val boards = sections.drop(1).map { Board.fromMatrixString(it) } + + return Bingo(revealQueue, boards) + } + } + + fun getResults() = sequence { + while (revealQueue.isNotEmpty() && boards.any { !it.didWin }) { + val number = revealQueue.removeFirst() + + for (board in boards.filter { !it.didWin }) { + board.reveal(number) + + if (board.didWin) { + yield(board.sumOfUnmarked * number) + } + } + } + } + + private class Board(private var rows: List<List<Square>>) { + companion object { + fun fromMatrixString(matrixString: String): Board = Board( + matrixString.trim().split("\\r?\\n".toRegex()).map { rowString -> + rowString.trim().split("\\s+".toRegex()).map { squareString -> + Square.Unmarked(squareString.toInt()) + } + } + ) + + private const val SIZE = 5 + + private val ROWS = (0 until SIZE).map { row -> + (0 until SIZE).map { square -> + Pair(row, square) + } + } + + private val COLUMNS = (0 until SIZE).map { column -> + (0 until SIZE).map { square -> + Pair(square, column) + } + } + + private val WINNING_CONFIGURATIONS = ROWS + COLUMNS + } + + fun reveal(number: Int) { + rows = rows.map { row -> + row.map { square -> + if (square is Square.Unmarked && square.number == number) Square.Marked else square + } + } + } + + val didWin: Boolean + get() = WINNING_CONFIGURATIONS.any { configuration -> + configuration.all { (row, column) -> rows[row][column] is Square.Marked } + } + + val sumOfUnmarked: Int + get() = rows.fold(0) { rowAcc, row -> + rowAcc + row.fold(0) { squareAcc, square -> + squareAcc + if (square is Square.Unmarked) square.number else 0 + } + } + + sealed class Square { + object Marked : Square() + class Unmarked(val number: Int) : Square() + } + } + } + + fun bothParts(input: String) = Bingo.fromString(input).getResults().let { it.first() to it.last() } +} + +fun main() { + val testInput = readInputAsString("Day04_test") + val testOutput = Day04.bothParts(testInput) + check(testOutput.first == 4512) + check(testOutput.second == 1924) + + val input = readInputAsString("Day04") + val output = Day04.bothParts(input) + println(output.first) + println(output.second) +} diff --git a/aoc-2021-kotlin/src/Day05.kt b/aoc-2021-kotlin/src/Day05.kt new file mode 100644 index 0000000..2c5e219 --- /dev/null +++ b/aoc-2021-kotlin/src/Day05.kt @@ -0,0 +1,62 @@ +import kotlin.math.absoluteValue +import kotlin.math.max +import kotlin.math.sign + +object Day05 { + private data class Line(val start: Pos2D, val end: Pos2D) { + companion object { + fun fromString(input: String): Line { + val (start, end) = input.split(" -> ").map { coordinateString -> + val (x, y) = coordinateString.split(",").map(String::toInt) + Pos2D(x, y) + } + + return Line(start, end) + } + } + + val isHorizontalOrVertical: Boolean + get() = start.x == end.x || start.y == end.y + + val isDiagonal: Boolean + get() = (end.x - start.x).absoluteValue == (end.y - start.y).absoluteValue + + val pointSequence: Sequence<Pos2D> + get() = sequence { + val xOffset = end.x - start.x + val yOffset = end.y - start.y + + for (s in 0..max(xOffset.absoluteValue, yOffset.absoluteValue)) { + val x = start.x + s * xOffset.sign + val y = start.y + s * yOffset.sign + + yield(Pos2D(x, y)) + } + } + } + + private fun helper(input: List<String>, linePredicate: (line: Line) -> Boolean) = input + .asSequence() + .map(Line::fromString) + .filter(linePredicate) + .flatMap(Line::pointSequence) + .groupingBy { it } + .eachCount() + .values + .count { it >= 2 } + + fun part1(input: List<String>): Int = helper(input, Line::isHorizontalOrVertical) + + fun part2(input: List<String>): Int = helper(input) { it.isHorizontalOrVertical || it.isDiagonal } + +} + +fun main() { + val testInput = readInputAsLines("Day05_test") + check(Day05.part1(testInput) == 5) + check(Day05.part2(testInput) == 12) + + val input = readInputAsLines("Day05") + println(Day05.part1(input)) + println(Day05.part2(input)) +} diff --git a/aoc-2021-kotlin/src/Day06.kt b/aoc-2021-kotlin/src/Day06.kt new file mode 100644 index 0000000..4627cca --- /dev/null +++ b/aoc-2021-kotlin/src/Day06.kt @@ -0,0 +1,38 @@ +object Day06 { + private fun calculateFishPopulation(input: String, days: Int): Long { + val fishCounts = + input + .trim() + .split(",") + .map(String::toInt) + .groupingBy { it } + .eachCount() + .mapValues { (_, v) -> v.toLong() } + .toMutableMap() + + repeat(days) { + val readyToBirth = fishCounts.getOrDefault(0, 0) + repeat(8) { + fishCounts[it] = fishCounts.getOrDefault(it + 1, 0) + } + fishCounts.merge(6, readyToBirth, Long::plus) + fishCounts[8] = readyToBirth + } + + return fishCounts.values.sum() + } + + fun part1(input: String): Int = calculateFishPopulation(input, 80).toInt() + + fun part2(input: String): Long = calculateFishPopulation(input, 256) +} + +fun main() { + val testInput = readInputAsString("Day06_test") + check(Day06.part1(testInput) == 5934) + check(Day06.part2(testInput) == 26984457539) + + val input = readInputAsString("Day06") + println(Day06.part1(input)) + println(Day06.part2(input)) +} diff --git a/aoc-2021-kotlin/src/Day07.kt b/aoc-2021-kotlin/src/Day07.kt new file mode 100644 index 0000000..9c1b79f --- /dev/null +++ b/aoc-2021-kotlin/src/Day07.kt @@ -0,0 +1,27 @@ +import kotlin.math.absoluteValue + +object Day07 { + fun part1(input: String): Int { + val numbers = input.trim().split(",").map(String::toInt) + val range = numbers.minOrNull()!!..numbers.maxOrNull()!! + + return range.minOf { n -> numbers.sumOf { (it - n).absoluteValue } } + } + + fun part2(input: String): Int { + val numbers = input.trim().split(",").map(String::toInt) + val range = numbers.minOrNull()!!..numbers.maxOrNull()!! + + return range.minOf { n -> numbers.map { (it - n).absoluteValue }.sumOf { (it * (it + 1)) / 2 } } + } +} + +fun main() { + val testInput = readInputAsString("Day07_test") + check(Day07.part1(testInput) == 37) + check(Day07.part2(testInput) == 168) + + val input = readInputAsString("Day07") + println(Day07.part1(input)) + println(Day07.part2(input)) +} diff --git a/aoc-2021-kotlin/src/Day08.kt b/aoc-2021-kotlin/src/Day08.kt new file mode 100644 index 0000000..b513352 --- /dev/null +++ b/aoc-2021-kotlin/src/Day08.kt @@ -0,0 +1,51 @@ +object Day08 { + fun part1(input: List<String>): Int = + input.sumOf { + it + .split("|")[1] + .trim() + .split(" ") + .map(String::length) + .count { len -> len in listOf(2, 3, 4, 7) } + } + + fun part2(input: List<String>): Long = input.sumOf { line -> + val (patternString, outputString) = line.split("|").map(String::trim) + val patterns = patternString.split(" ").map(String::toSet) + + val one = patterns.first { it.size == 2 } + val four = patterns.first { it.size == 4 } + val seven = patterns.first { it.size == 3 } + val eight = patterns.first { it.size == 7 } + + val top = seven - one + val middle = patterns.filter { it.size == 5 }.reduce(Set<Char>::intersect) intersect four + val five = patterns.filter { it.size == 6 }.reduce(Set<Char>::intersect) + middle + val bottom = five - (four + top) + val nine = four + top + bottom + val lowerLeft = eight - nine + val six = five + lowerLeft + val lowerRight = one intersect six + val three = one + top + middle + bottom + val zero = eight - middle + val upperLeft = nine - three + val two = eight - (upperLeft + lowerRight) + + val encodings = listOf(zero, one, two, three, four, five, six, seven, eight, nine) + + outputString + .split(" ") + .joinToString("") { encodings.indexOf(it.toSet()).toString() } + .toLong() + } +} + +fun main() { + val testInput = readInputAsLines("Day08_test") + check(Day08.part1(testInput) == 26) + check(Day08.part2(testInput) == 61229L) + + val input = readInputAsLines("Day08") + println(Day08.part1(input)) + println(Day08.part2(input)) +} diff --git a/aoc-2021-kotlin/src/Day09.kt b/aoc-2021-kotlin/src/Day09.kt new file mode 100644 index 0000000..9d0c41d --- /dev/null +++ b/aoc-2021-kotlin/src/Day09.kt @@ -0,0 +1,40 @@ +object Day09 { + private fun Map<Pos2D, Int>.getLowPoints() = + filter { (pos, num) -> Pos2D.directions4.all { num < getOrDefault(pos + it, 9) } } + + fun part1(input: List<String>) = + parseToMap(input).getLowPoints().values.sumOf { it + 1 } + + fun part2(input: List<String>): Int { + val map = parseToMap(input) + + fun traverseBasin(pos: Pos2D, acc: MutableSet<Pos2D>) { + acc.add(pos) + Pos2D.directions4 + .map { pos + it } + .filter { !acc.contains(it) && map.getOrDefault(it, 9) < 9 } + .forEach { traverseBasin(it, acc) } + } + + return map + .getLowPoints() + .map { + val visited = mutableSetOf<Pos2D>() + traverseBasin(it.key, visited) + visited.size + } + .sortedDescending() + .take(3) + .sum() + } +} + +fun main() { + val testInput = readInputAsLines("Day09_test") + check(Day09.part1(testInput) == 15) + check(Day09.part2(testInput) == 1134) + + val input = readInputAsLines("Day09") + println(Day09.part1(input)) + println(Day09.part2(input)) +} diff --git a/aoc-2021-kotlin/src/Day10.kt b/aoc-2021-kotlin/src/Day10.kt new file mode 100644 index 0000000..d6d026c --- /dev/null +++ b/aoc-2021-kotlin/src/Day10.kt @@ -0,0 +1,91 @@ +object Day10 { + private enum class ChunkDelimiter(val open: Char, val close: Char) { + Parentheses('(', ')'), + Brackets('[', ']'), + Braces('{', '}'), + Angled('<', '>'); + + companion object { + fun isOpening(character: Char): Boolean = values().any { it.open == character } + fun isClosing(character: Char): Boolean = values().any { it.close == character } + fun from(character: Char): ChunkDelimiter = + values().find { it.open == character || it.close == character }!! + } + } + + private sealed class SyntaxError { + object None : SyntaxError() + class IncompleteLine(private val stack: ArrayDeque<ChunkDelimiter>) : SyntaxError() { + val score: Long + get() { + fun delimiterValue(delimiter: ChunkDelimiter): Int = when (delimiter) { + ChunkDelimiter.Parentheses -> 1 + ChunkDelimiter.Brackets -> 2 + ChunkDelimiter.Braces -> 3 + ChunkDelimiter.Angled -> 4 + } + + return stack.fold(0) { acc, elem -> acc * 5 + delimiterValue(elem) } + } + } + + class CorruptedLine(private val invalidDelimiter: ChunkDelimiter) : SyntaxError() { + val score: Int + get() = when (invalidDelimiter) { + ChunkDelimiter.Parentheses -> 3 + ChunkDelimiter.Brackets -> 57 + ChunkDelimiter.Braces -> 1197 + ChunkDelimiter.Angled -> 25137 + } + } + } + + private fun parse(line: String): SyntaxError { + val stack = ArrayDeque<ChunkDelimiter>() + + for (char in line) { + when { + ChunkDelimiter.isOpening(char) -> stack.addFirst(ChunkDelimiter.from(char)) + ChunkDelimiter.isClosing(char) -> { + val closingDelimiter = ChunkDelimiter.from(char) + if (stack.first() == closingDelimiter) { + stack.removeFirst() + } else { + return SyntaxError.CorruptedLine(closingDelimiter) + } + } + } + } + + if (stack.isNotEmpty()) { + return SyntaxError.IncompleteLine(stack) + } + + return SyntaxError.None + } + + fun part1(input: List<String>): Int = input + .map { parse(it) } + .filterIsInstance<SyntaxError.CorruptedLine>() + .sumOf { it.score } + + fun part2(input: List<String>): Long = + input + .asSequence() + .map { parse(it) } + .filterIsInstance<SyntaxError.IncompleteLine>() + .map { it.score } + .sorted() + .toList() + .let { it[it.size / 2] } +} + +fun main() { + val testInput = readInputAsLines("Day10_test") + check(Day10.part1(testInput) == 26397) + check(Day10.part2(testInput) == 288957L) + + val input = readInputAsLines("Day10") + println(Day10.part1(input)) + println(Day10.part2(input)) +} diff --git a/aoc-2021-kotlin/src/Day11.kt b/aoc-2021-kotlin/src/Day11.kt new file mode 100644 index 0000000..db56d61 --- /dev/null +++ b/aoc-2021-kotlin/src/Day11.kt @@ -0,0 +1,48 @@ +object Day11 { + private fun flashSequence(input: Map<Pos2D, Int>) = sequence { + val map = input.toMutableMap() + + while (true) { + val flashed = mutableSetOf<Pos2D>() + fun canFlash(entry: Map.Entry<Pos2D, Int>): Boolean = entry.value > 9 && !flashed.contains(entry.key) + + // 1) + map.forEach { (pos, energy) -> map[pos] = energy + 1 } + + // 2) + while (map.any(::canFlash)) { + map + .filter(::canFlash) + .forEach { (pos, _) -> + flashed.add(pos) + Pos2D.directions8.map { pos + it }.forEach { + if (map.containsKey(it)) { + map[it] = map[it]!! + 1 + } + } + } + } + + // 3) + flashed.forEach { map[it] = 0 } + + yield(flashed.size) + } + } + + fun bothParts(input: List<String>) = flashSequence(parseToMap(input)).let { seq -> + seq.take(100).sum() to seq.indexOfFirst { it == 100 } + 1 + } +} + +fun main() { + val testInput = readInputAsLines("Day11_test") + val testOutput = Day11.bothParts(testInput) + check(testOutput.first == 1656) + check(testOutput.second == 195) + + val input = readInputAsLines("Day11") + val output = Day11.bothParts(input) + println(output.first) + println(output.second) +} diff --git a/aoc-2021-kotlin/src/Day12.kt b/aoc-2021-kotlin/src/Day12.kt new file mode 100644 index 0000000..d3368da --- /dev/null +++ b/aoc-2021-kotlin/src/Day12.kt @@ -0,0 +1,72 @@ +object Day12 { + private class CaveGraph { + companion object { + fun fromLines(input: List<String>): CaveGraph = + CaveGraph().apply { input.forEach { addConnection(it) } } + } + + private val adjacencyList = mutableMapOf<Node, Set<Node>>() + + private fun addConnection(connectionString: String) { + val (from, to) = connectionString.split("-").map(Node::fromString) + + adjacencyList.merge(from, setOf(to), Set<Node>::union) + adjacencyList.merge(to, setOf(from), Set<Node>::union) + } + + fun countPaths(canUseDoubleTraversal: Boolean = false): Int = + traverse(Node.Start, setOf(), !canUseDoubleTraversal) + + private fun traverse(from: Node, visitedBefore: Set<Node>, usedUpDoubleTraverse: Boolean): Int { + return adjacencyList[from]!!.sumOf { + when (it) { + is Node.Start -> 0 + is Node.End -> 1 + is Node.Big -> traverse(it, visitedBefore + from, usedUpDoubleTraverse) + is Node.Small -> { + if (!visitedBefore.contains(it)) { + traverse(it, visitedBefore + from, usedUpDoubleTraverse) + } else if (!usedUpDoubleTraverse) { + traverse(it, visitedBefore + from, true) + } else { + 0 + } + } + } + } + } + + private sealed class Node { + companion object { + fun fromString(text: String): Node = when (text) { + "start" -> Start + "end" -> End + else -> if (text == text.uppercase()) { + Big(text) + } else { + Small(text) + } + } + } + + object Start : Node() + object End : Node() + data class Small(private val identifier: String) : Node() + data class Big(private val identifier: String) : Node() + } + } + + fun bothParts(input: List<String>) = CaveGraph.fromLines(input).let { it.countPaths() to it.countPaths(true) } +} + +fun main() { + val testInput = readInputAsLines("Day12_test") + val testOutput = Day12.bothParts(testInput) + check(testOutput.first == 226) + check(testOutput.second == 3509) + + val input = readInputAsLines("Day12") + val output = Day12.bothParts(input) + println(output.first) + println(output.second) +} diff --git a/aoc-2021-kotlin/src/Day13.kt b/aoc-2021-kotlin/src/Day13.kt new file mode 100644 index 0000000..0f9b096 --- /dev/null +++ b/aoc-2021-kotlin/src/Day13.kt @@ -0,0 +1,99 @@ +object Day13 { + private sealed class FoldCommand { + abstract fun dispatch(dots: Set<Pos2D>): Set<Pos2D> + + class AlongX(private val x: Int) : FoldCommand() { + override fun dispatch(dots: Set<Pos2D>): Set<Pos2D> = dots + .filter { it.x != x } + .map { + if (it.x < x) { + it + } else { + Pos2D(2 * x - it.x, it.y) + } + } + .toSet() + } + + class AlongY(private val y: Int) : FoldCommand() { + override fun dispatch(dots: Set<Pos2D>): Set<Pos2D> = dots + .filter { it.y != y } + .map { + if (it.y < y) { + it + } else { + Pos2D(it.x, 2 * y - it.y) + } + } + .toSet() + } + } + + private fun parseOrigami(input: List<String>): Pair<Set<Pos2D>, Sequence<FoldCommand>> { + val dots = mutableSetOf<Pos2D>() + val commands = mutableListOf<FoldCommand>() + + for (line in input) { + if (line.matches("\\d+,\\d+".toRegex())) { + val (x, y) = line.split(",").map(String::toInt) + dots.add(Pos2D(x, y)) + } + + if (line.matches("fold along [xy]=\\d+".toRegex())) { + val equation = line.substring(11) + val (axis, valueString) = equation.split("=") + val value = valueString.toInt() + + commands.add( + when (axis) { + "x" -> FoldCommand.AlongX(value) + "y" -> FoldCommand.AlongY(value) + else -> throw IllegalStateException("Illegal axis given!") + } + ) + } + } + + return dots to commands.asSequence() + } + + fun part1(input: List<String>): Int { + val (dots, commands) = parseOrigami(input) + + return commands.first().dispatch(dots).size + } + + fun part2(input: List<String>): String { + val origami = parseOrigami(input) + var dots = origami.first + val commands = origami.second + + commands.forEach { + dots = it.dispatch(dots) + } + + val bounds = dots.reduce { max, pos -> + when ((pos.x > max.x) to (pos.y > max.y)) { + true to true -> pos + true to false -> Pos2D(pos.x, max.y) + false to true -> Pos2D(max.x, pos.y) + else -> max + } + } + + val lines = Array(bounds.y + 1) { Array(bounds.x + 1) { ' ' } } + + dots.forEach { lines[it.y][it.x] = '#' } + + return lines.joinToString("\n") { it.joinToString("") } + } +} + +fun main() { + val testInput = readInputAsLines("Day13_test") + check(Day13.part1(testInput) == 17) + + val input = readInputAsLines("Day13") + println(Day13.part1(input)) + println(Day13.part2(input)) +} diff --git a/aoc-2021-kotlin/src/Day14.kt b/aoc-2021-kotlin/src/Day14.kt new file mode 100644 index 0000000..920ea9e --- /dev/null +++ b/aoc-2021-kotlin/src/Day14.kt @@ -0,0 +1,46 @@ +object Day14 { + private fun getPolymerLetterCounts(input: List<String>, iterations: Int): Long { + val template = input.first() + val rules = input.drop(2).associate { + val (pattern, replacement) = it.split(" -> ") + (pattern[0] to pattern[1]) to replacement.first() + } + + var pairCounts = template + .zipWithNext() + .groupingBy { it } + .eachCount() + .mapValues { (_, v) -> v.toLong() } + + repeat(iterations) { + val newCounts = mutableMapOf<Pair<Char, Char>, Long>() + + pairCounts.forEach { (pair, count) -> + newCounts.merge(rules[pair]!! to pair.second, count, Long::plus) + newCounts.merge(pair.first to rules[pair]!!, count, Long::plus) + } + + pairCounts = newCounts + } + + val letterCounts = mutableMapOf<Char, Long>() + pairCounts.forEach { (pair, count) -> letterCounts.merge(pair.second, count, Long::plus) } + letterCounts.merge(template.first(), 1, Long::plus) + + return letterCounts.values.let { it.maxOrNull()!! - it.minOrNull()!! } + } + + fun part1(input: List<String>): Long = getPolymerLetterCounts(input, 10) + + fun part2(input: List<String>): Long = getPolymerLetterCounts(input, 40) +} + +fun main() { + val testInput = readInputAsLines("Day14_test") + check(Day14.part1(testInput) == 1588L) + check(Day14.part2(testInput) == 2188189693529L) + + val input = readInputAsLines("Day14") + println(Day14.part1(input)) + println(Day14.part2(input)) +} diff --git a/aoc-2021-kotlin/src/Day15.kt b/aoc-2021-kotlin/src/Day15.kt new file mode 100644 index 0000000..6d0de5c --- /dev/null +++ b/aoc-2021-kotlin/src/Day15.kt @@ -0,0 +1,117 @@ +import java.util.* + +object Day15 { + private class CustomPriorityQueue<T>(private val array: Array<T>, private val comparator: Comparator<T>) { + init { + array.sortWith(comparator) + } + + private var i = 0 + + private fun indexOfStartingFrom(elem: T, start: Int): Int { + for (i in (start until array.size)) { + if (array[i] == elem) { + return i + } + } + + return -1 + } + + fun isNotEmpty(): Boolean = i < array.size + + fun take(): T = array[i++] + + fun revalidate(elem: T) { + val currentIndex = indexOfStartingFrom(elem, i) + + if (currentIndex == -1) { + return + } + + val newIndex = Arrays + .binarySearch(array, i, currentIndex, elem, comparator) + .let { if (it >= 0) it else -(it + 1) } + + System.arraycopy(array, newIndex, array, newIndex + 1, currentIndex - newIndex) + + array[newIndex] = elem + } + } + + private class Matrix(private val data: Array<IntArray>, private val size: Int) { + companion object { + fun fromInput(input: List<String>): Matrix { + val data = input.map { line -> + line.map { it.digitToInt() }.toIntArray() + }.toTypedArray() + + check(data.isNotEmpty()) { "No rows found!" } + check(data.first().isNotEmpty()) { "No columns found!" } + + return Matrix(data, data.size) + } + } + + fun expand(): Matrix { + val expandedData = Array(size * 5) { row -> + IntArray(size * 5) { col -> + ((data[row % size][col % size] + row / size + col / size) - 1) % 9 + 1 + } + } + + return Matrix(expandedData, size * 5) + } + + private fun neighbours(pos: Pair<Int, Int>): Sequence<Pair<Int, Int>> { + val offsets = sequenceOf(0 to 1, 1 to 0, 0 to -1, -1 to 0) + + return offsets + .map { pos.first + it.first to pos.second + it.second } + .filter { it.first in 0 until size && it.second in 0 until size } + } + + fun dijkstra(): Int { + val positions = (0 until size) + .flatMap { row -> (0 until size).map { col -> row to col } } + + val distances = + positions + .associateWith { Int.MAX_VALUE } + .toMutableMap() + + distances[0 to 0] = 0 + + + val queue = CustomPriorityQueue(positions.toTypedArray(), compareBy { distances[it]!! }) + + while (queue.isNotEmpty()) { + val u = queue.take() + + for (v in neighbours(u)) { + val newDist = distances[u]!! + data[v.first][v.second] + if (distances[v]!! > newDist) { + distances[v] = newDist + queue.revalidate(v) + } + } + } + + return distances[size - 1 to size - 1]!! + } + } + + fun part1(input: List<String>): Int = Matrix.fromInput(input).dijkstra() + + fun part2(input: List<String>): Int = Matrix.fromInput(input).expand().dijkstra() +} + +fun main() { + val testInput = readInputAsLines("Day15_test") + check(Day15.part1(testInput) == 40) + check(Day15.part2(testInput) == 315) + + val input = readInputAsLines("Day15") + println(Day15.part1(input)) + println(Day15.part2(input)) +} diff --git a/aoc-2021-kotlin/src/Day16.kt b/aoc-2021-kotlin/src/Day16.kt new file mode 100644 index 0000000..d11219d --- /dev/null +++ b/aoc-2021-kotlin/src/Day16.kt @@ -0,0 +1,161 @@ +object Day16 { + private sealed class Packet( + private val bits: Int, + protected val version: Int, + ) { + private class Literal( + bits: Int, + version: Int, + private val literalValue: Long, + ) : Packet(bits, version) { + override fun versionSum(): Int = version + + override val value: Long + get() = literalValue + } + + private class Operator( + bits: Int, + version: Int, + private val typeId: Int, + private val subpackets: List<Packet>, + ) : Packet(bits, version) { + override fun versionSum(): Int = version + subpackets.sumOf { it.versionSum() } + + override val value: Long + get() = when (typeId) { + 0 -> subpackets.sumOf { it.value } + 1 -> subpackets.fold(1) { acc, packet -> acc * packet.value } + 2 -> subpackets.minOf { it.value } + 3 -> subpackets.maxOf { it.value } + 5, 6, 7 -> { + val (first, second) = subpackets.map { it.value } + + if (when (typeId) { + 5 -> first > second + 6 -> first < second + 7 -> first == second + else -> false + } + ) { + 1 + } else { + 0 + } + } + + else -> throw IllegalStateException("Illegal packet type id.") + } + } + + abstract fun versionSum(): Int + + abstract val value: Long + + companion object { + fun parse(bitQueue: ArrayDeque<Char>): Packet { + var packetBits = 0 + + fun takeBits(n: Int): Int { + packetBits += n + return (0 until n) + .joinToString("") { bitQueue.removeFirst().toString() } + .toInt(2) + } + + val version = takeBits(3) + + when (val typeId = takeBits(3)) { + 4 -> { // Literal packet + var literalValue = 0L + while (true) { + val groupHeader = takeBits(1) + val groupValue = takeBits(4) + + literalValue = (literalValue shl 4) + groupValue + + if (groupHeader == 0) { + break + } + } + + return Literal(packetBits, version, literalValue) + } + + else -> { // Operator packet + val subpackets = mutableListOf<Packet>() + + when (takeBits(1)) { + 0 -> { + val subpacketLength = takeBits(15) + + var currentSubpacketLength = 0 + while (currentSubpacketLength < subpacketLength) { + val subpacket = parse(bitQueue) + currentSubpacketLength += subpacket.bits + subpackets.add(subpacket) + } + } + + 1 -> { + val subpacketCount = takeBits(11) + + repeat(subpacketCount) { + subpackets.add(parse(bitQueue)) + } + } + + else -> throw IllegalStateException("Illegal length type id.") + } + + packetBits += subpackets.sumOf { it.bits } + + return Operator(packetBits, version, typeId, subpackets) + } + } + } + } + } + + private fun parse(input: String): Packet { + val bitQueue = ArrayDeque( + input + .flatMap { + it + .toString() + .toInt(16) + .toString(2) + .padStart(4, '0') + .toList() + } + ) + + return Packet.parse(bitQueue) + } + + fun part1(input: String): Int = parse(input).versionSum() + + fun part2(input: String): Long = parse(input).value +} + + +fun main() { + check(Day16.part1("8A004A801A8002F478") == 16) + check(Day16.part1("620080001611562C8802118E34") == 12) + check(Day16.part1("C0015000016115A2E0802F182340") == 23) + check(Day16.part1("A0016C880162017C3686B18A3D4780") == 31) + + check(Day16.part2("C200B40A82") == 3L) + check(Day16.part2("04005AC33890") == 54L) + check(Day16.part2("880086C3E88112") == 7L) + check(Day16.part2("CE00C43D881120") == 9L) + check(Day16.part2("D8005AC2A8F0") == 1L) + check(Day16.part2("F600BC2D8F") == 0L) + check(Day16.part2("9C005AC2F8F0") == 0L) + check(Day16.part2("9C0141080250320F1802104A08") == 1L) + + + val input = readInputAsString("Day16") + println(Day16.part1(input)) + println(Day16.part2(input)) +} diff --git a/aoc-2021-kotlin/src/Day17.kt b/aoc-2021-kotlin/src/Day17.kt new file mode 100644 index 0000000..5e0170b --- /dev/null +++ b/aoc-2021-kotlin/src/Day17.kt @@ -0,0 +1,62 @@ +import kotlin.math.max +import kotlin.math.sign + +object Day17 { + data class Target(val left: Int, val right: Int, val bottom: Int, val top: Int) + + private class Probe(private var vel: Pos2D, private val target: Target) { + companion object { + fun search(target: Target): Pair<Int, Int> { + var highest = 0 + var count = 0 + + for (vx in 0..1000) { + for (vy in -1000..1000) { + val probe = Probe(Pos2D(vx, vy), target) + var currentHighest = 0 + + while (probe.canHitTarget) { + probe.step() + currentHighest = max(currentHighest, probe.pos.y) + + if (probe.isInTarget) { + count++ + highest = max(highest, currentHighest) + break + } + } + } + } + + return highest to count + } + } + + private var pos = Pos2D(0, 0) + + private fun step() { + pos += vel + vel = vel.copy(x = vel.x - vel.x.sign, y = vel.y - 1) + } + + private val canHitTarget + get() = pos.y > target.bottom + + private val isInTarget + get() = pos.x in target.left..target.right && pos.y in target.bottom..target.top + } + + fun bothParts(input: Target) = Probe.search(input) +} + +fun main() { + val testInput = Day17.Target(20, 30, -10, -5) + val testOutput = Day17.bothParts(testInput) + check(testOutput.first == 45) + check(testOutput.second == 112) + + val input = Day17.Target(192, 251, -89, -59) + val output = Day17.bothParts(input) + println(output.first) + println(output.second) +} diff --git a/aoc-2021-kotlin/src/Day18.kt b/aoc-2021-kotlin/src/Day18.kt new file mode 100644 index 0000000..84575b7 --- /dev/null +++ b/aoc-2021-kotlin/src/Day18.kt @@ -0,0 +1,137 @@ +import kotlin.math.ceil +import kotlin.math.floor + +object Day18 { + private class SnailfishNum private constructor(private val data: MutableList<Entry>) { + private data class Entry(var num: Int, val depth: Int) + + companion object { + fun parse(input: String): SnailfishNum { + var depth = 0 + val list = mutableListOf<Entry>() + + for (char in input) { + when (char) { + '[' -> depth += 1 + ']' -> depth -= 1 + ',' -> {} + else -> list.add(Entry(char.toString().toInt(), depth)) + } + } + + return SnailfishNum(list) + } + } + + private val shouldExplode + get() = data + .zipWithNext() + .any { it.first.depth == it.second.depth && it.first.depth >= 5 } + + private val shouldSplit + get() = data.any { it.num >= 10 } + + private fun explode() { + val (leftIndex, rightIndex) = data + .zipWithNext() + .indexOfFirst { it.first.depth == it.second.depth && it.first.depth >= 5 } + .let { it to it + 1 } + + if (leftIndex - 1 in data.indices) { + data[leftIndex - 1].num += data[leftIndex].num + } + + if (rightIndex + 1 in data.indices) { + data[rightIndex + 1].num += data[rightIndex].num + } + + data[leftIndex] = Entry(0, data[leftIndex].depth - 1) + data.removeAt(rightIndex) + } + + private fun split() { + val index = data.indexOfFirst { it.num >= 10 } + val depth = data[index].depth + + val half = data[index].num / 2.0 + val roundedDown = floor(half).toInt() + val roundedUp = ceil(half).toInt() + + data[index] = Entry(roundedUp, depth + 1) + data.add(index, Entry(roundedDown, depth + 1)) + } + + private fun reduce() { + while (true) { + if (shouldExplode) { + explode() + } else if (shouldSplit) { + split() + } else { + break + } + } + } + + fun magnitude(): Int { + val dataCopy = data.toMutableList() + + while (dataCopy.size > 1) { + val maxDepth = dataCopy.maxOf { it.depth } + + val (leftIndex, rightIndex) = dataCopy + .zipWithNext() + .indexOfFirst { it.first.depth == it.second.depth && it.first.depth == maxDepth } + .let { it to it + 1 } + + dataCopy[leftIndex] = Entry( + dataCopy[leftIndex].num * 3 + dataCopy[rightIndex].num * 2, + maxDepth - 1 + ) + dataCopy.removeAt(rightIndex) + } + + return dataCopy.first().num + } + + operator fun plus(other: SnailfishNum): SnailfishNum = + SnailfishNum( + (this.data + other.data).map { Entry(it.num, it.depth + 1) }.toMutableList() + ).also { it.reduce() } + } + + private fun <T> combinations(items: Sequence<T>): Sequence<Pair<T, T>> = + sequence { + items.forEach { a -> + items.forEach { b -> + yield(a to b) + } + } + } + + fun part1(input: List<String>): Int = + input + .asSequence() + .map(SnailfishNum::parse) + .reduce(SnailfishNum::plus) + .magnitude() + + fun part2(input: List<String>): Int = + combinations( + input + .asSequence() + .map(SnailfishNum::parse) + ) + .filter { it.first !== it.second } + .maxOf { (it.first + it.second).magnitude() } +} + +fun main() { + val testInput = readInputAsLines("Day18_test") + check(Day18.part1(testInput) == 4140) + check(Day18.part2(testInput) == 3993) + + val input = readInputAsLines("Day18") + println(Day18.part1(input)) + println(Day18.part2(input)) +} diff --git a/aoc-2021-kotlin/src/Day24.kt b/aoc-2021-kotlin/src/Day24.kt new file mode 100644 index 0000000..9ca300c --- /dev/null +++ b/aoc-2021-kotlin/src/Day24.kt @@ -0,0 +1,231 @@ +object Day24 { + @JvmInline + private value class Register private constructor(val address: Int) { + companion object { + val W = Register(0) + val X = Register(1) + val Y = Register(2) + val Z = Register(3) + + fun fromString(string: String) = when (string) { + "x" -> X + "y" -> Y + "z" -> Z + "w" -> W + else -> throw IllegalArgumentException(string) + } + } + } + + private sealed class Instruction { + companion object { + fun fromString(string: String) = string.split(" ").let { parts -> + val operatorString = parts[0] + val target = Register.fromString(parts[1]) + + if (operatorString == "inp") { + Input(target) + } else { + val opcode = when (operatorString) { + "add" -> Binary.Opcode.ADD + "mul" -> Binary.Opcode.MUL + "div" -> Binary.Opcode.DIV + "mod" -> Binary.Opcode.MOD + "eql" -> Binary.Opcode.EQL + else -> throw IllegalArgumentException(operatorString) + } + + val source = when (val parsed = parts[2].toLongOrNull()) { + is Long -> Source.Literal(parsed) + else -> Source.Memory(Register.fromString(parts[2])) + } + + Binary(opcode, target, source) + } + } + } + + data class Input(val register: Register) : Instruction() + data class Binary(val opcode: Opcode, val a: Register, val b: Source) : Instruction() { + enum class Opcode { + ADD, MUL, DIV, MOD, EQL + } + } + + sealed class Source { + data class Memory(val register: Register) : Source() + data class Literal(val value: Long) : Source() + } + } + + private data class ALU(private val memory: LongArray) { + @Suppress("unused") + val w get() = memory[Register.W.address] + + @Suppress("unused") + val x get() = memory[Register.X.address] + + @Suppress("unused") + val y get() = memory[Register.Y.address] + + @Suppress("unused") + val z get() = memory[Register.Z.address] + + fun toMutable() = MutableALU(memory.clone()) + + override fun equals(other: Any?): Boolean { + if (this === other) return true + if (javaClass != other?.javaClass) return false + return memory.contentEquals((other as ALU).memory) + } + + override fun hashCode() = memory.contentHashCode() + } + + private class MutableALU(private val memory: LongArray) { + constructor() : this(LongArray(4) { 0L }) + + fun toImmutable() = ALU(memory.clone()) + + fun executeBatch(batch: List<Instruction.Binary>) { + batch.forEach { + memory[it.a.address] = when (it.opcode) { + Instruction.Binary.Opcode.ADD -> fetch(it.a) + fetch(it.b) + Instruction.Binary.Opcode.MUL -> fetch(it.a) * fetch(it.b) + Instruction.Binary.Opcode.DIV -> fetch(it.a) / fetch(it.b) + Instruction.Binary.Opcode.MOD -> fetch(it.a) % fetch(it.b) + Instruction.Binary.Opcode.EQL -> if (fetch(it.a) == fetch(it.b)) 1L else 0L + } + } + } + + fun feedInput(input: Instruction.Input, value: Long) { + memory[input.register.address] = value + } + + private fun fetch(register: Register) = memory[register.address] + + private fun fetch(source: Instruction.Source) = when (source) { + is Instruction.Source.Literal -> source.value + is Instruction.Source.Memory -> memory[source.register.address] + } + } + + private class Program private constructor(private val parts: List<Part>) { + companion object { + fun compileFrom(inputs: List<String>): Program { + val instructionQueue = inputs.map(Instruction::fromString) + + val parts = mutableListOf<Part>() + + val currentStep = mutableListOf<Instruction.Binary>() + var currentInput: Instruction.Input? = null + + instructionQueue.forEach { + when (it) { + is Instruction.Input -> { + parts.add(Part(currentInput, currentStep.toList())) + + currentStep.clear() + currentInput = it + } + + is Instruction.Binary -> currentStep.add(it) + } + } + + parts.add(Part(currentInput, currentStep.toList())) + + return Program(parts) + } + } + + private data class Part(val input: Instruction.Input?, val instructionBatch: List<Instruction.Binary>) + + private data class Checkpoint(val partNumber: Int, val alu: ALU) + + fun findInputDigits( + digitRange: IntProgression = 0..9, + successCondition: (ALU) -> Boolean + ): Sequence<Long> { + val cache = mutableSetOf<Checkpoint>() + val matchingCheckpoints = mutableSetOf<Checkpoint>() + + fun solveRecursively(checkpoint: Checkpoint, accumulator: Long): Sequence<Long> = sequence { + if (cache.contains(checkpoint)) return@sequence + + if (checkpoint.partNumber == parts.size) { + if (successCondition(checkpoint.alu)) { + yield(accumulator) + val statesOfCurrent = inputStateSequence(accumulator).toSet() + matchingCheckpoints.addAll(statesOfCurrent) + cache.removeAll(statesOfCurrent) + } + + return@sequence + } + + digitRange.forEach { + yieldAll( + solveRecursively( + Checkpoint( + checkpoint.partNumber + 1, + executePart(checkpoint.partNumber, checkpoint.alu, it.toLong()), + ), + accumulator * 10 + it, + ) + ) + } + + if (!matchingCheckpoints.contains(checkpoint)) cache.add(checkpoint) + + Runtime.getRuntime().let { + if (it.totalMemory().toDouble() / it.maxMemory() > 0.75) { + cache.clear() + it.gc() + } + } + } + + return solveRecursively(Checkpoint(1, executePart(0)), 0L) + } + + private fun inputStateSequence(input: Long) = sequence { + var checkpoint = Checkpoint(1, executePart(0)) + yield(checkpoint) + + input.toString().toCharArray().map { it.toString().toInt() }.forEach { + checkpoint = Checkpoint( + checkpoint.partNumber + 1, + executePart(checkpoint.partNumber, checkpoint.alu, it.toLong()) + ) + yield(checkpoint) + } + } + + private fun executePart(partNumber: Int, alu: ALU? = null, input: Long? = null): ALU { + val part = parts[partNumber] + val executor = alu?.toMutable() ?: MutableALU() + + if (part.input != null && input != null) + executor.feedInput(part.input, input) + + executor.executeBatch(part.instructionBatch) + + return executor.toImmutable() + } + } + + fun bothParts(input: List<String>) = Program + .compileFrom(input) + .findInputDigits(digitRange = 9 downTo 1) { it.z == 0L } + .let { it.first() to it.last() } +} + +fun main() { + val input = readInputAsLines("Day24") + val output = Day24.bothParts(input) + + println(output.first) + println(output.second) +} diff --git a/aoc-2021-kotlin/src/Day25.kt b/aoc-2021-kotlin/src/Day25.kt new file mode 100644 index 0000000..36a2f75 --- /dev/null +++ b/aoc-2021-kotlin/src/Day25.kt @@ -0,0 +1,87 @@ +object Day25 { + private class SeaCucumbers(private val width: Int, private val height: Int, private val matrix: Array<SeaTile>) { + companion object { + fun fromLines(lines: List<String>) = + Pos2D( + lines.getOrNull(0)?.length ?: throw IllegalArgumentException("Sea must have a non-zero height!"), + lines.size + ).let { size -> + SeaCucumbers(size.x, size.y, Array(size.x * size.y) { + when (val char = lines[it / size.x][it % size.x]) { + '>' -> SeaTile.Cucumber.EastFacing + 'v' -> SeaTile.Cucumber.SouthFacing + '.' -> SeaTile.EmptyTile + else -> throw IllegalArgumentException("Found '$char', expected '>', 'v' or '.'!") + } + }) + } + } + + private sealed class SeaTile { + object EmptyTile : SeaTile() + sealed class Cucumber : SeaTile() { + object EastFacing : Cucumber() + object SouthFacing : Cucumber() + } + } + + private fun moveIndex(index: Int, offset: Pos2D) = + ((index / width + offset.y) % height) * width + (index + offset.x) % width + + private inline fun <reified T : SeaTile.Cucumber> stepDirection(pos: Pos2D) { + matrix + .asSequence() + .withIndex() + .map { (index, seaTile) -> + val nextIndex = moveIndex(index, pos) + if (seaTile is T && matrix[nextIndex] is SeaTile.EmptyTile) { + index to nextIndex + } else { + null + } + } + .filterNotNull() + .toList() + .forEach { (index, nextIndex) -> + matrix[nextIndex] = matrix[index].also { matrix[index] = SeaTile.EmptyTile } + } + } + + private fun stepOnce() { + stepDirection<SeaTile.Cucumber.EastFacing>(Pos2D(1, 0)) + stepDirection<SeaTile.Cucumber.SouthFacing>(Pos2D(0, 1)) + } + + fun simulate(): Int { + var count = 0 + + do { + val previousHashCode = matrix.contentHashCode() + stepOnce() + count++ + } while (matrix.contentHashCode() != previousHashCode) + + return count + } + + override fun toString(): String = matrix + .withIndex() + .joinToString("") { (index, seaTile) -> + when (seaTile) { + SeaTile.Cucumber.EastFacing -> ">" + SeaTile.Cucumber.SouthFacing -> "v" + SeaTile.EmptyTile -> "." + } + (if (index % width == width - 1) "\n" else "") + } + } + + fun singlePart(input: List<String>) = SeaCucumbers.fromLines(input).simulate() +} + +fun main() { + val testInput = readInputAsLines("Day25_test") + check(Day25.singlePart(testInput) == 58) + + val input = readInputAsLines("Day25") + println(Day25.singlePart(input)) +} diff --git a/aoc-2021-kotlin/src/Utils.kt b/aoc-2021-kotlin/src/Utils.kt new file mode 100644 index 0000000..f0a420b --- /dev/null +++ b/aoc-2021-kotlin/src/Utils.kt @@ -0,0 +1,32 @@ +import java.io.File + +fun readInputAsLines(name: String): List<String> = File("src", "$name.txt").readLines() + +fun readInputAsString(name: String): String = File("src", "$name.txt").readText() + +fun readInputAsNumbers(name: String): List<Int> = readInputAsLines(name).map(String::toInt) + +fun readInputAsBitLists(name: String): List<List<Int>> = + readInputAsLines(name) + .map { binaryString -> binaryString.toList().map { bit -> bit.toString().toInt() } } + +data class Pos2D(val x: Int, val y: Int) { + companion object { + val directions4 = listOf(Pos2D(0, 1), Pos2D(1, 0), Pos2D(0, -1), Pos2D(-1, 0)) + val directions8 = directions4 + listOf( + Pos2D(1, 1), + Pos2D(1, -1), + Pos2D(-1, -1), + Pos2D(-1, 1), + ) + } + + operator fun plus(other: Pos2D) = Pos2D(x + other.x, y + other.y) +} + +fun parseToMap(input: List<String>): Map<Pos2D, Int> = + input.flatMapIndexed { y, line -> + line.mapIndexed { x, char -> + Pos2D(x, y) to char.toString().toInt() + } + }.toMap() |