From 0f1e145b80813ae2331b7dac5ace0c589654ad2a Mon Sep 17 00:00:00 2001 From: tchojnacki Date: Thu, 11 Aug 2022 19:24:23 +0200 Subject: Move subproject to avoid IntelliJ module name issues --- .gitignore | 1 + 2021-kotlin/README.md | 43 ---- 2021-kotlin/build.gradle.kts | 19 -- 2021-kotlin/gradle/wrapper/gradle-wrapper.jar | Bin 59536 -> 0 bytes .../gradle/wrapper/gradle-wrapper.properties | 5 - 2021-kotlin/gradlew | 234 --------------------- 2021-kotlin/gradlew.bat | 89 -------- 2021-kotlin/settings.gradle.kts | 1 - 2021-kotlin/src/Day01.kt | 24 --- 2021-kotlin/src/Day02.kt | 56 ----- 2021-kotlin/src/Day03.kt | 51 ----- 2021-kotlin/src/Day04.kt | 97 --------- 2021-kotlin/src/Day05.kt | 62 ------ 2021-kotlin/src/Day06.kt | 38 ---- 2021-kotlin/src/Day07.kt | 27 --- 2021-kotlin/src/Day08.kt | 51 ----- 2021-kotlin/src/Day09.kt | 40 ---- 2021-kotlin/src/Day10.kt | 91 -------- 2021-kotlin/src/Day11.kt | 48 ----- 2021-kotlin/src/Day12.kt | 72 ------- 2021-kotlin/src/Day13.kt | 99 --------- 2021-kotlin/src/Day14.kt | 46 ---- 2021-kotlin/src/Day15.kt | 117 ----------- 2021-kotlin/src/Day16.kt | 161 -------------- 2021-kotlin/src/Day17.kt | 62 ------ 2021-kotlin/src/Day18.kt | 137 ------------ 2021-kotlin/src/Day24.kt | 231 -------------------- 2021-kotlin/src/Day25.kt | 87 -------- 2021-kotlin/src/Utils.kt | 32 --- README.md | 2 +- aoc-2021-kotlin/README.md | 43 ++++ aoc-2021-kotlin/build.gradle.kts | 19 ++ aoc-2021-kotlin/gradle/wrapper/gradle-wrapper.jar | Bin 0 -> 59536 bytes .../gradle/wrapper/gradle-wrapper.properties | 5 + aoc-2021-kotlin/gradlew | 234 +++++++++++++++++++++ aoc-2021-kotlin/gradlew.bat | 89 ++++++++ aoc-2021-kotlin/settings.gradle.kts | 1 + aoc-2021-kotlin/src/Day01.kt | 24 +++ aoc-2021-kotlin/src/Day02.kt | 56 +++++ aoc-2021-kotlin/src/Day03.kt | 51 +++++ aoc-2021-kotlin/src/Day04.kt | 97 +++++++++ aoc-2021-kotlin/src/Day05.kt | 62 ++++++ aoc-2021-kotlin/src/Day06.kt | 38 ++++ aoc-2021-kotlin/src/Day07.kt | 27 +++ aoc-2021-kotlin/src/Day08.kt | 51 +++++ aoc-2021-kotlin/src/Day09.kt | 40 ++++ aoc-2021-kotlin/src/Day10.kt | 91 ++++++++ aoc-2021-kotlin/src/Day11.kt | 48 +++++ aoc-2021-kotlin/src/Day12.kt | 72 +++++++ aoc-2021-kotlin/src/Day13.kt | 99 +++++++++ aoc-2021-kotlin/src/Day14.kt | 46 ++++ aoc-2021-kotlin/src/Day15.kt | 117 +++++++++++ aoc-2021-kotlin/src/Day16.kt | 161 ++++++++++++++ aoc-2021-kotlin/src/Day17.kt | 62 ++++++ aoc-2021-kotlin/src/Day18.kt | 137 ++++++++++++ aoc-2021-kotlin/src/Day24.kt | 231 ++++++++++++++++++++ aoc-2021-kotlin/src/Day25.kt | 87 ++++++++ aoc-2021-kotlin/src/Utils.kt | 32 +++ 58 files changed, 2022 insertions(+), 2021 deletions(-) delete mode 100644 2021-kotlin/README.md delete mode 100644 2021-kotlin/build.gradle.kts delete mode 100644 2021-kotlin/gradle/wrapper/gradle-wrapper.jar delete mode 100644 2021-kotlin/gradle/wrapper/gradle-wrapper.properties delete mode 100755 2021-kotlin/gradlew delete mode 100644 2021-kotlin/gradlew.bat delete mode 100644 2021-kotlin/settings.gradle.kts delete mode 100644 2021-kotlin/src/Day01.kt delete mode 100644 2021-kotlin/src/Day02.kt delete mode 100644 2021-kotlin/src/Day03.kt delete mode 100644 2021-kotlin/src/Day04.kt delete mode 100644 2021-kotlin/src/Day05.kt delete mode 100644 2021-kotlin/src/Day06.kt delete mode 100644 2021-kotlin/src/Day07.kt delete mode 100644 2021-kotlin/src/Day08.kt delete mode 100644 2021-kotlin/src/Day09.kt delete mode 100644 2021-kotlin/src/Day10.kt delete mode 100644 2021-kotlin/src/Day11.kt delete mode 100644 2021-kotlin/src/Day12.kt delete mode 100644 2021-kotlin/src/Day13.kt delete mode 100644 2021-kotlin/src/Day14.kt delete mode 100644 2021-kotlin/src/Day15.kt delete mode 100644 2021-kotlin/src/Day16.kt delete mode 100644 2021-kotlin/src/Day17.kt delete mode 100644 2021-kotlin/src/Day18.kt delete mode 100644 2021-kotlin/src/Day24.kt delete mode 100644 2021-kotlin/src/Day25.kt delete mode 100644 2021-kotlin/src/Utils.kt create mode 100644 aoc-2021-kotlin/README.md create mode 100644 aoc-2021-kotlin/build.gradle.kts create mode 100644 aoc-2021-kotlin/gradle/wrapper/gradle-wrapper.jar create mode 100644 aoc-2021-kotlin/gradle/wrapper/gradle-wrapper.properties create mode 100755 aoc-2021-kotlin/gradlew create mode 100644 aoc-2021-kotlin/gradlew.bat create mode 100644 aoc-2021-kotlin/settings.gradle.kts create mode 100644 aoc-2021-kotlin/src/Day01.kt create mode 100644 aoc-2021-kotlin/src/Day02.kt create mode 100644 aoc-2021-kotlin/src/Day03.kt create mode 100644 aoc-2021-kotlin/src/Day04.kt create mode 100644 aoc-2021-kotlin/src/Day05.kt create mode 100644 aoc-2021-kotlin/src/Day06.kt create mode 100644 aoc-2021-kotlin/src/Day07.kt create mode 100644 aoc-2021-kotlin/src/Day08.kt create mode 100644 aoc-2021-kotlin/src/Day09.kt create mode 100644 aoc-2021-kotlin/src/Day10.kt create mode 100644 aoc-2021-kotlin/src/Day11.kt create mode 100644 aoc-2021-kotlin/src/Day12.kt create mode 100644 aoc-2021-kotlin/src/Day13.kt create mode 100644 aoc-2021-kotlin/src/Day14.kt create mode 100644 aoc-2021-kotlin/src/Day15.kt create mode 100644 aoc-2021-kotlin/src/Day16.kt create mode 100644 aoc-2021-kotlin/src/Day17.kt create mode 100644 aoc-2021-kotlin/src/Day18.kt create mode 100644 aoc-2021-kotlin/src/Day24.kt create mode 100644 aoc-2021-kotlin/src/Day25.kt create mode 100644 aoc-2021-kotlin/src/Utils.kt diff --git a/.gitignore b/.gitignore index 81dea52..9b96758 100644 --- a/.gitignore +++ b/.gitignore @@ -1,4 +1,5 @@ .idea +*.iml .gradle build *.txt diff --git a/2021-kotlin/README.md b/2021-kotlin/README.md deleted file mode 100644 index c8c777a..0000000 --- a/2021-kotlin/README.md +++ /dev/null @@ -1,43 +0,0 @@ -# Advent of Code 2021 in Kotlin -![Kotlin](https://img.shields.io/badge/Kotlin-grey?logo=Kotlin) -![39/50 stars](https://img.shields.io/badge/🌟%20stars-39/50-orange) -![20/25 days](https://img.shields.io/badge/πŸ“…%20days-20/25-blue) - -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/2021-kotlin/build.gradle.kts b/2021-kotlin/build.gradle.kts deleted file mode 100644 index 51a5269..0000000 --- a/2021-kotlin/build.gradle.kts +++ /dev/null @@ -1,19 +0,0 @@ -plugins { - kotlin("jvm") version "1.6.10" -} - -repositories { - mavenCentral() -} - -tasks { - sourceSets { - main { - java.srcDirs("src") - } - } - - wrapper { - gradleVersion = "7.3" - } -} diff --git a/2021-kotlin/gradle/wrapper/gradle-wrapper.jar b/2021-kotlin/gradle/wrapper/gradle-wrapper.jar deleted file mode 100644 index 7454180..0000000 Binary files a/2021-kotlin/gradle/wrapper/gradle-wrapper.jar and /dev/null differ diff --git a/2021-kotlin/gradle/wrapper/gradle-wrapper.properties b/2021-kotlin/gradle/wrapper/gradle-wrapper.properties deleted file mode 100644 index e750102..0000000 --- a/2021-kotlin/gradle/wrapper/gradle-wrapper.properties +++ /dev/null @@ -1,5 +0,0 @@ -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/2021-kotlin/gradlew b/2021-kotlin/gradlew deleted file mode 100755 index 1b6c787..0000000 --- a/2021-kotlin/gradlew +++ /dev/null @@ -1,234 +0,0 @@ -#!/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/2021-kotlin/gradlew.bat b/2021-kotlin/gradlew.bat deleted file mode 100644 index 107acd3..0000000 --- a/2021-kotlin/gradlew.bat +++ /dev/null @@ -1,89 +0,0 @@ -@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/2021-kotlin/settings.gradle.kts b/2021-kotlin/settings.gradle.kts deleted file mode 100644 index 2b9d160..0000000 --- a/2021-kotlin/settings.gradle.kts +++ /dev/null @@ -1 +0,0 @@ -rootProject.name = "advent-of-code-2021-kotlin" diff --git a/2021-kotlin/src/Day01.kt b/2021-kotlin/src/Day01.kt deleted file mode 100644 index 4ac1ef7..0000000 --- a/2021-kotlin/src/Day01.kt +++ /dev/null @@ -1,24 +0,0 @@ -object Day01 { - fun part1(input: List) = - input - .zipWithNext() - .count { it.second > it.first } - - fun part2(input: List) = - 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/2021-kotlin/src/Day02.kt b/2021-kotlin/src/Day02.kt deleted file mode 100644 index 2eb085a..0000000 --- a/2021-kotlin/src/Day02.kt +++ /dev/null @@ -1,56 +0,0 @@ -object Day02 { - private fun dispatchCommands(commands: List, 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): 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): 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/2021-kotlin/src/Day03.kt b/2021-kotlin/src/Day03.kt deleted file mode 100644 index 1418a2e..0000000 --- a/2021-kotlin/src/Day03.kt +++ /dev/null @@ -1,51 +0,0 @@ -object Day03 { - private fun addLists(l1: List, l2: List) = l1.zip(l2).map { it.first + it.second } - - private fun valueOfBits(bitList: List) = bitList.reduce { acc, bit -> acc * 2 + bit } - - private fun invertBits(bitList: List) = bitList.map { bit -> 1 - bit } - - private fun mostCommonBits(input: List>): List = - input - .reduce(::addLists) - .map { bit -> if (bit.toDouble() / input.size >= 0.5) 1 else 0 } - - private fun selectByBitCriteria( - input: List>, - comparisonCriteria: (currentList: List>) -> List - ): List? { - 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>): Int = - mostCommonBits(input) - .let { gammaBits -> - val epsilonBits = invertBits(gammaBits) - return valueOfBits(gammaBits) * valueOfBits(epsilonBits) - } - - fun part2(input: List>): 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/2021-kotlin/src/Day04.kt b/2021-kotlin/src/Day04.kt deleted file mode 100644 index 96cdf3b..0000000 --- a/2021-kotlin/src/Day04.kt +++ /dev/null @@ -1,97 +0,0 @@ -object Day04 { - private class Bingo(private val revealQueue: ArrayDeque, private val boards: List) { - 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>) { - 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/2021-kotlin/src/Day05.kt b/2021-kotlin/src/Day05.kt deleted file mode 100644 index 2c5e219..0000000 --- a/2021-kotlin/src/Day05.kt +++ /dev/null @@ -1,62 +0,0 @@ -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 - 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, 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): Int = helper(input, Line::isHorizontalOrVertical) - - fun part2(input: List): 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/2021-kotlin/src/Day06.kt b/2021-kotlin/src/Day06.kt deleted file mode 100644 index 4627cca..0000000 --- a/2021-kotlin/src/Day06.kt +++ /dev/null @@ -1,38 +0,0 @@ -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/2021-kotlin/src/Day07.kt b/2021-kotlin/src/Day07.kt deleted file mode 100644 index 9c1b79f..0000000 --- a/2021-kotlin/src/Day07.kt +++ /dev/null @@ -1,27 +0,0 @@ -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/2021-kotlin/src/Day08.kt b/2021-kotlin/src/Day08.kt deleted file mode 100644 index b513352..0000000 --- a/2021-kotlin/src/Day08.kt +++ /dev/null @@ -1,51 +0,0 @@ -object Day08 { - fun part1(input: List): Int = - input.sumOf { - it - .split("|")[1] - .trim() - .split(" ") - .map(String::length) - .count { len -> len in listOf(2, 3, 4, 7) } - } - - fun part2(input: List): 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::intersect) intersect four - val five = patterns.filter { it.size == 6 }.reduce(Set::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/2021-kotlin/src/Day09.kt b/2021-kotlin/src/Day09.kt deleted file mode 100644 index 9d0c41d..0000000 --- a/2021-kotlin/src/Day09.kt +++ /dev/null @@ -1,40 +0,0 @@ -object Day09 { - private fun Map.getLowPoints() = - filter { (pos, num) -> Pos2D.directions4.all { num < getOrDefault(pos + it, 9) } } - - fun part1(input: List) = - parseToMap(input).getLowPoints().values.sumOf { it + 1 } - - fun part2(input: List): Int { - val map = parseToMap(input) - - fun traverseBasin(pos: Pos2D, acc: MutableSet) { - 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() - 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/2021-kotlin/src/Day10.kt b/2021-kotlin/src/Day10.kt deleted file mode 100644 index d6d026c..0000000 --- a/2021-kotlin/src/Day10.kt +++ /dev/null @@ -1,91 +0,0 @@ -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) : 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() - - 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): Int = input - .map { parse(it) } - .filterIsInstance() - .sumOf { it.score } - - fun part2(input: List): Long = - input - .asSequence() - .map { parse(it) } - .filterIsInstance() - .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/2021-kotlin/src/Day11.kt b/2021-kotlin/src/Day11.kt deleted file mode 100644 index db56d61..0000000 --- a/2021-kotlin/src/Day11.kt +++ /dev/null @@ -1,48 +0,0 @@ -object Day11 { - private fun flashSequence(input: Map) = sequence { - val map = input.toMutableMap() - - while (true) { - val flashed = mutableSetOf() - fun canFlash(entry: Map.Entry): 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) = 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/2021-kotlin/src/Day12.kt b/2021-kotlin/src/Day12.kt deleted file mode 100644 index d3368da..0000000 --- a/2021-kotlin/src/Day12.kt +++ /dev/null @@ -1,72 +0,0 @@ -object Day12 { - private class CaveGraph { - companion object { - fun fromLines(input: List): CaveGraph = - CaveGraph().apply { input.forEach { addConnection(it) } } - } - - private val adjacencyList = mutableMapOf>() - - private fun addConnection(connectionString: String) { - val (from, to) = connectionString.split("-").map(Node::fromString) - - adjacencyList.merge(from, setOf(to), Set::union) - adjacencyList.merge(to, setOf(from), Set::union) - } - - fun countPaths(canUseDoubleTraversal: Boolean = false): Int = - traverse(Node.Start, setOf(), !canUseDoubleTraversal) - - private fun traverse(from: Node, visitedBefore: Set, 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) = 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/2021-kotlin/src/Day13.kt b/2021-kotlin/src/Day13.kt deleted file mode 100644 index 0f9b096..0000000 --- a/2021-kotlin/src/Day13.kt +++ /dev/null @@ -1,99 +0,0 @@ -object Day13 { - private sealed class FoldCommand { - abstract fun dispatch(dots: Set): Set - - class AlongX(private val x: Int) : FoldCommand() { - override fun dispatch(dots: Set): Set = 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): Set = 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): Pair, Sequence> { - val dots = mutableSetOf() - val commands = mutableListOf() - - 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): Int { - val (dots, commands) = parseOrigami(input) - - return commands.first().dispatch(dots).size - } - - fun part2(input: List): 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/2021-kotlin/src/Day14.kt b/2021-kotlin/src/Day14.kt deleted file mode 100644 index 920ea9e..0000000 --- a/2021-kotlin/src/Day14.kt +++ /dev/null @@ -1,46 +0,0 @@ -object Day14 { - private fun getPolymerLetterCounts(input: List, 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, 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() - 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): Long = getPolymerLetterCounts(input, 10) - - fun part2(input: List): 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/2021-kotlin/src/Day15.kt b/2021-kotlin/src/Day15.kt deleted file mode 100644 index 6d0de5c..0000000 --- a/2021-kotlin/src/Day15.kt +++ /dev/null @@ -1,117 +0,0 @@ -import java.util.* - -object Day15 { - private class CustomPriorityQueue(private val array: Array, private val comparator: Comparator) { - 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, private val size: Int) { - companion object { - fun fromInput(input: List): 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): Sequence> { - 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): Int = Matrix.fromInput(input).dijkstra() - - fun part2(input: List): 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/2021-kotlin/src/Day16.kt b/2021-kotlin/src/Day16.kt deleted file mode 100644 index d11219d..0000000 --- a/2021-kotlin/src/Day16.kt +++ /dev/null @@ -1,161 +0,0 @@ -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(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): 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() - - 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/2021-kotlin/src/Day17.kt b/2021-kotlin/src/Day17.kt deleted file mode 100644 index 5e0170b..0000000 --- a/2021-kotlin/src/Day17.kt +++ /dev/null @@ -1,62 +0,0 @@ -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 { - 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/2021-kotlin/src/Day18.kt b/2021-kotlin/src/Day18.kt deleted file mode 100644 index 84575b7..0000000 --- a/2021-kotlin/src/Day18.kt +++ /dev/null @@ -1,137 +0,0 @@ -import kotlin.math.ceil -import kotlin.math.floor - -object Day18 { - private class SnailfishNum private constructor(private val data: MutableList) { - private data class Entry(var num: Int, val depth: Int) - - companion object { - fun parse(input: String): SnailfishNum { - var depth = 0 - val list = mutableListOf() - - 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 combinations(items: Sequence): Sequence> = - sequence { - items.forEach { a -> - items.forEach { b -> - yield(a to b) - } - } - } - - fun part1(input: List): Int = - input - .asSequence() - .map(SnailfishNum::parse) - .reduce(SnailfishNum::plus) - .magnitude() - - fun part2(input: List): 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/2021-kotlin/src/Day24.kt b/2021-kotlin/src/Day24.kt deleted file mode 100644 index 9ca300c..0000000 --- a/2021-kotlin/src/Day24.kt +++ /dev/null @@ -1,231 +0,0 @@ -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) { - 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) { - companion object { - fun compileFrom(inputs: List): Program { - val instructionQueue = inputs.map(Instruction::fromString) - - val parts = mutableListOf() - - val currentStep = mutableListOf() - 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) - - private data class Checkpoint(val partNumber: Int, val alu: ALU) - - fun findInputDigits( - digitRange: IntProgression = 0..9, - successCondition: (ALU) -> Boolean - ): Sequence { - val cache = mutableSetOf() - val matchingCheckpoints = mutableSetOf() - - fun solveRecursively(checkpoint: Checkpoint, accumulator: Long): Sequence = 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) = 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/2021-kotlin/src/Day25.kt b/2021-kotlin/src/Day25.kt deleted file mode 100644 index 36a2f75..0000000 --- a/2021-kotlin/src/Day25.kt +++ /dev/null @@ -1,87 +0,0 @@ -object Day25 { - private class SeaCucumbers(private val width: Int, private val height: Int, private val matrix: Array) { - companion object { - fun fromLines(lines: List) = - 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 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(Pos2D(1, 0)) - stepDirection(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) = 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/2021-kotlin/src/Utils.kt b/2021-kotlin/src/Utils.kt deleted file mode 100644 index f0a420b..0000000 --- a/2021-kotlin/src/Utils.kt +++ /dev/null @@ -1,32 +0,0 @@ -import java.io.File - -fun readInputAsLines(name: String): List = File("src", "$name.txt").readLines() - -fun readInputAsString(name: String): String = File("src", "$name.txt").readText() - -fun readInputAsNumbers(name: String): List = readInputAsLines(name).map(String::toInt) - -fun readInputAsBitLists(name: String): List> = - 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): Map = - input.flatMapIndexed { y, line -> - line.mapIndexed { x, char -> - Pos2D(x, y) to char.toString().toInt() - } - }.toMap() diff --git a/README.md b/README.md index 4d12987..98f0d2e 100644 --- a/README.md +++ b/README.md @@ -6,7 +6,7 @@ Repository storing my solutions to Advent of Code. See other people's solutions > prep, company training, university coursework, practice problems, or to challenge each other. ## Years πŸ“… -### [2021](2021-kotlin) +### [2021](aoc-2021-kotlin) ![Kotlin](https://img.shields.io/badge/Kotlin-grey?logo=Kotlin) ![39/50 stars](https://img.shields.io/badge/🌟%20stars-39/50-orange) ![20/25 days](https://img.shields.io/badge/πŸ“…%20days-20/25-blue) 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 +![Kotlin](https://img.shields.io/badge/Kotlin-grey?logo=Kotlin) +![39/50 stars](https://img.shields.io/badge/🌟%20stars-39/50-orange) +![20/25 days](https://img.shields.io/badge/πŸ“…%20days-20/25-blue) + +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 new file mode 100644 index 0000000..7454180 Binary files /dev/null and b/aoc-2021-kotlin/gradle/wrapper/gradle-wrapper.jar differ 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) = + input + .zipWithNext() + .count { it.second > it.first } + + fun part2(input: List) = + 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, 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): 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): 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, l2: List) = l1.zip(l2).map { it.first + it.second } + + private fun valueOfBits(bitList: List) = bitList.reduce { acc, bit -> acc * 2 + bit } + + private fun invertBits(bitList: List) = bitList.map { bit -> 1 - bit } + + private fun mostCommonBits(input: List>): List = + input + .reduce(::addLists) + .map { bit -> if (bit.toDouble() / input.size >= 0.5) 1 else 0 } + + private fun selectByBitCriteria( + input: List>, + comparisonCriteria: (currentList: List>) -> List + ): List? { + 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>): Int = + mostCommonBits(input) + .let { gammaBits -> + val epsilonBits = invertBits(gammaBits) + return valueOfBits(gammaBits) * valueOfBits(epsilonBits) + } + + fun part2(input: List>): 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, private val boards: List) { + 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>) { + 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 + 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, 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): Int = helper(input, Line::isHorizontalOrVertical) + + fun part2(input: List): 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): Int = + input.sumOf { + it + .split("|")[1] + .trim() + .split(" ") + .map(String::length) + .count { len -> len in listOf(2, 3, 4, 7) } + } + + fun part2(input: List): 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::intersect) intersect four + val five = patterns.filter { it.size == 6 }.reduce(Set::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.getLowPoints() = + filter { (pos, num) -> Pos2D.directions4.all { num < getOrDefault(pos + it, 9) } } + + fun part1(input: List) = + parseToMap(input).getLowPoints().values.sumOf { it + 1 } + + fun part2(input: List): Int { + val map = parseToMap(input) + + fun traverseBasin(pos: Pos2D, acc: MutableSet) { + 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() + 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) : 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() + + 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): Int = input + .map { parse(it) } + .filterIsInstance() + .sumOf { it.score } + + fun part2(input: List): Long = + input + .asSequence() + .map { parse(it) } + .filterIsInstance() + .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) = sequence { + val map = input.toMutableMap() + + while (true) { + val flashed = mutableSetOf() + fun canFlash(entry: Map.Entry): 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) = 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): CaveGraph = + CaveGraph().apply { input.forEach { addConnection(it) } } + } + + private val adjacencyList = mutableMapOf>() + + private fun addConnection(connectionString: String) { + val (from, to) = connectionString.split("-").map(Node::fromString) + + adjacencyList.merge(from, setOf(to), Set::union) + adjacencyList.merge(to, setOf(from), Set::union) + } + + fun countPaths(canUseDoubleTraversal: Boolean = false): Int = + traverse(Node.Start, setOf(), !canUseDoubleTraversal) + + private fun traverse(from: Node, visitedBefore: Set, 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) = 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): Set + + class AlongX(private val x: Int) : FoldCommand() { + override fun dispatch(dots: Set): Set = 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): Set = 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): Pair, Sequence> { + val dots = mutableSetOf() + val commands = mutableListOf() + + 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): Int { + val (dots, commands) = parseOrigami(input) + + return commands.first().dispatch(dots).size + } + + fun part2(input: List): 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, 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, 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() + 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): Long = getPolymerLetterCounts(input, 10) + + fun part2(input: List): 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(private val array: Array, private val comparator: Comparator) { + 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, private val size: Int) { + companion object { + fun fromInput(input: List): 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): Sequence> { + 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): Int = Matrix.fromInput(input).dijkstra() + + fun part2(input: List): 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(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): 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() + + 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 { + 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) { + private data class Entry(var num: Int, val depth: Int) + + companion object { + fun parse(input: String): SnailfishNum { + var depth = 0 + val list = mutableListOf() + + 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 combinations(items: Sequence): Sequence> = + sequence { + items.forEach { a -> + items.forEach { b -> + yield(a to b) + } + } + } + + fun part1(input: List): Int = + input + .asSequence() + .map(SnailfishNum::parse) + .reduce(SnailfishNum::plus) + .magnitude() + + fun part2(input: List): 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) { + 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) { + companion object { + fun compileFrom(inputs: List): Program { + val instructionQueue = inputs.map(Instruction::fromString) + + val parts = mutableListOf() + + val currentStep = mutableListOf() + 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) + + private data class Checkpoint(val partNumber: Int, val alu: ALU) + + fun findInputDigits( + digitRange: IntProgression = 0..9, + successCondition: (ALU) -> Boolean + ): Sequence { + val cache = mutableSetOf() + val matchingCheckpoints = mutableSetOf() + + fun solveRecursively(checkpoint: Checkpoint, accumulator: Long): Sequence = 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) = 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) { + companion object { + fun fromLines(lines: List) = + 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 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(Pos2D(1, 0)) + stepDirection(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) = 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 = File("src", "$name.txt").readLines() + +fun readInputAsString(name: String): String = File("src", "$name.txt").readText() + +fun readInputAsNumbers(name: String): List = readInputAsLines(name).map(String::toInt) + +fun readInputAsBitLists(name: String): List> = + 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): Map = + input.flatMapIndexed { y, line -> + line.mapIndexed { x, char -> + Pos2D(x, y) to char.toString().toInt() + } + }.toMap() -- cgit v1.2.3