Advent of Code 2023 Day 3 - Kotlin

cotton·2023년 12월 4일

Advent of Code 2023

목록 보기

3/4

🔥 매년 12월 1일부터 12월 25일까지 한 문제씩 프로그래밍 퍼즐을 제공하는 사이트다. Eric Wastl이 2015년에 만든 사이트로, 재림절 달력(Advent calendar)을 매일 열어보듯이 크리스마스까지 꾸준히 문제를 해결해나간다는 컨셉이다. 퍼즐은 UTC-5 기준으로 자정, 한국시간으로는 오후 2시에 공개된다.
출처 : 나무위키 - Advent of Code

Advent of Code가 2023년 돌아왔습니다! 25일간 프로그래밍 퍼즐을 풀어봅시다.

Jetbrains는 이번에도 어김없이 Kotlin을 통해 25일간의 AoC에 참가하면 코틀린 독점 상품을 받을 수 있는 기회를 준다고 합니다!

자세한 내용은 코틀린 블로그에 개제된 Tackle Advent of Code 2023 With Kotlin and Win Prizes! 를 참고하세요.

오늘은 세 번째 문제인 Gear Ratio 문제를 풀어봤습니다.
이번 문제는 주말에 나왔어서 상당히 난이도가 있는 문제였습니다. 제가 2D Matirx에 상당히 약해서, 문제를 푸는데 꽤 어려웠습니다 😂

Part 1

문제 풀이

고장난 엔진을 고쳐야 합니다.

엔진 도식(퍼즐)은 아래와 같은 구조로 되어 있습니다.

467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..

. 은 빈 공간입니다.
. 을 제외한 기호에 붙어 있는 숫자는 부품 번호입니다.
- 상하좌우 네 방향 뿐만 아니라 대각선을 포함한 총 8방향에 붙어 있는 숫자는 모두 부품 번호입니다.
부품 번호들의 합을 반환하면 됩니다.
- 왼쪽 상단에 있는 * 는 467, 35와 붙어 있으므로, 합계에 467와 35을 더합니다.

내 풀이

우선 기호의 위치를 파악하고 기호에 붙어있는 숫자들을 파악해 합계에 합산하려고 합니다.

기호의 위치를 파악하면, 그 주변에 있는 숫자들의 유무와 위치에 따라 로직을 다르게 구현했습니다.

기호 상 / 하단에 있는 숫자를 파악합니다.
a. 숫자가 있는 경우
- 숫자가 있다면 왼쪽, 오른쪽으로 숫자가 없을 때까지 문자를 가져와 합칩니다.
- 이 때 왼쪽, 오른쪽으로 각각 함수를 호출하므로 별 상단에 있는 숫자는 중복됩니다.
  - 위 사진에서는 35, 57이 됩니다.
- 따라서 왼쪽으로 진행한 문자열의 마지막 글자를 drop하고 오른쪽으로 진행한 문자열을 합칩니다.
  - “35”.drop(1) + “57” = “357”
b. 숫자가 없는 경우
- 숫자가 없더라도 기호 기준 여덟 방향을 모두 체크해야 하므로, 왼쪽과 오른쪽으로 탐색합니다. 왼쪽이나 오른쪽에 숫자가 있다면 숫자가 없을 때까지 탐색합니다.
- 위 사진에서는 상단 왼쪽에 7이라는 숫자가 있습니다. 숫자가 없을 때까지 탐색해, 467이라는 값을 가져옵니다.
- 기호의 상/하단에 있는 경우에는 기호가 있는 위치의 아래에서 좌/우로 탐색을 진행합니다. 이 방식은 마치 DFS과 유사하기 때문에, DFS와 유사하게 구현했습니다.

fun String.filterNumber(idx: Int): List<Int> {
    val left = dfs(this, idx, true)
    val right = dfs(this, idx, false)

    return if (left.isEmpty() && right.isEmpty()) {
        listOf(
            dfs(this, idx - 1, true),
            dfs(this, idx + 1, false)
        ).mapNotNull { it.toIntOrNull() }
    } else {
        listOf(
            left.dropLast(1) + right
        ).mapNotNull { it.toIntOrNull() }
    }
}

fun dfs(str: String, index: Int, left: Boolean): String {
    val c = str.getOrNull(index)
    if (c == null || c == '.') return ""

    return if (left) {
        dfs(str, index - 1, true) + c
    } else {
        c + dfs(str, index + 1, false)
    }
}

기호 좌/우에 있는 숫자를 탐색합니다.

a. 위에 구현한 dfs 함수를 사용하면 된다. 기호의 좌/우를 시작점으로 구현한 dfs 함수를 호출하면 끝!

fun part1(input: List<String>): Int {
    var sum = 0
    input.forEachIndexed { i, str ->
        str.forEachIndexed { j, c ->
            if (input[i][j] != '.' && input[i][j].isDigit().not()) {
                val num1 = input.getOrNull(i - 1)?.filterNumber(j).orEmpty()
                val num2 = dfs(input.getOrNull(i).orEmpty(), j - 1, true).toIntOrNull()
                val num3 = dfs(input.getOrNull(i).orEmpty(), j + 1, false).toIntOrNull()
                val num4 = input.getOrNull(i + 1)?.filterNumber(j).orEmpty()
                val list = num1 + listOfNotNull(num2, num3) + num4
                sum += list.sum()
            }
        }
    }
    return sum
}

다른 사람들 풀이

🔥 다른 사람들의 풀이는 KotlinLang Slack에 참여하면 확인할 수 있습니다!

solve { sumOf { it.sum() } }

private val digits = "([0-9]+)".toRegex()
private val symbols = "([^0-9.])".toRegex()

private fun Sequence<String>.solve(
    sum: Sequence<List<Int>>.() -> Int,
) = windowed(3) { lines ->
    symbols.findAll(lines[1])
        .map(MatchResult::range)
        .map(IntRange::first)
        .map { symbol ->
            lines.flatMap(digits::findAll)
                .map { (it.range.first - 1)..(it.range.last + 1) to it.groupValues[1].toInt() }
                .filter { (target, _) -> symbol in target }.map { (_, number) -> number }
        }
}.flatten().run(sum)

windowed() 를 이용했습니다.
- 슬라이딩 윈도우 알고리즘을 생각하면 됩니다. [1, 2, 3, 4, 5] 라는 리스트에서 windowed(2)를 호출하면 [1, 2], [2, 3] … 과 같이 동작합니다.
- 위의 경우에는 주어진 리스트에 사용했으므로 전체 도식의 문자열들이 세 줄씩 묶여 있는 형태입니다.
세 줄씩 묶어 놓은 문자열 리스트의 가운데(lines[1]) 문자열에 있는 기호들을 symbols 정규식을 통해 찾습니다.
- 중간인 이유는 기호의 상하좌우를 모두 봐야 하기 때문에 위 / 아래에도 문자열이 있어야 하기 때문입니다.
- 해당 기호들의 위치를 range를 통해 파악 한 후 매핑합니다. 위처럼 하면 기호가 있는 위치의 인덱스들의 리스트가 완성됩니다.
해당 기호의 위치를 알았으니 이번에는 숫자의 위치를 파악할 차례입니다.
- 처음에 windowed()를 이용해 가져온 3줄에 있는 숫자 위치를 파악합니다.
- 해당 숫자가 위치한 range 안에 기호의 index가 있는지 판단합니다. index가 있는 경우에는 숫자가 기호에 붙어 있다는 뜻입니다. lines가 기호 기준으로 위 아래로 총 3줄에 한정되어 있기 때문에 위 로직이 동작할 수 있습니다.
해당 값들을 모두 합칩니다.

Part 2

문제 풀이

이번에는 * 기호에 2개의 숫자가 붙어 있는 것만 합계에 합산합니다.

이 때 2개의 숫자는 곱한 값을 합계에 합산하도록 합니다.

내 풀이

part 1 코드가 * 기호 기준으로 동작하므로 조건 2가지만 변경하면 됩니다!

기호를 구분하던 로직을 * 만 비교하도록 변경
합계 로직을 2개의 숫자를 곱하고 합산하도록 변경

fun part2(input: List<String>): Int {
    var sum = 0
    input.forEachIndexed { i, str ->
        str.forEachIndexed { j, c ->
            if (input[i][j] == '*') {
                val num1 = input.getOrNull(i - 1)?.filterNumber(j).orEmpty()
                val num2 = dfs(input.getOrNull(i).orEmpty(), j - 1, true).toIntOrNull()
                val num3 = dfs(input.getOrNull(i).orEmpty(), j + 1, false).toIntOrNull()
                val num4 = input.getOrNull(i + 1)?.filterNumber(j).orEmpty()
                val list = num1 + listOfNotNull(num2, num3) + num4
                if (list.size > 1) {
                    sum += list.first() * list.last()
                }
            }
        }
    }
    return sum
}