Advent of Code 2023

[Mordi]

Wie jedes Jahr läuft auch dieses Jahr in der Vorweihnachtszeit der Advent of Code.
@Rexaris hat ja gestern auch im Programmieranfängerlinkthread gepostet
Findet ihr sowas interessant? Macht ihr mit? Wenn ja, in welcher Sprache?

Ich hab da immer Spaß dran, dieses Jahr versuche ich soweit es geht nur Bash (mit so common Zeugs wie grep, awk, sed, tr, bc etc.) zu lösen. Hat die ersten 2 Tage schon mal gut geklappt

 

[Rexaris]

Ich bin durch einen Studienkollegen vor einigen Jahren auf Advent of Code gestoßen und finde das Klasse.
Ich selber versuche mich daran in Python, da ich diese Sprache für Datenauswertungen etc. beruflich nutze.

Mir ist dann irgendwann allerdings der Zeitaufwand doch etwas zu groß, da ich bei weitem nicht so schnell bin wie die Top 100, die ja einsehbar ist.

Man kann dort private Leaderboards erstellen mit bis zu 200 Personen.
Gäbe es da Interesse an einem CB-Leaderboard?
Mein erster Eindruck ist allerdings, dass das Feedback zu diesem Thema hier eher verhalten ist.

 

[Mordi]

Ich glaube Leaderboard macht wenig Sinn, wenn nicht groß Interesse da ist von paar Leuten. Day 3 kam ich noch nicht dazu, schau ich mir morgen an. Aber hier mal meine Ansätze für Day1 und Day2 (die auch klappten)

Ich selber versuche mich daran in Python, da ich diese Sprache für Datenauswertungen etc. beruflich nutze.

Ich seh das immer als schöne Gelegenheit neue Sprachen zu lernen - oder mich in welchen zu verbessern. 2021 nahm ich glaub Python, letztes Jahr dann Go und dieses Jahr versuch ichs erstmal mit Bash. Mal sehen wie lang es klappt.

#!/bin/bash

while read line
do
  [ -z "$line" ] && break
  CURRENTLINE=""
  linewithspaces=$(echo "$line" | fold -w 1)
  for char in ${linewithspaces} ; do
    CURRENTLINE="$CURRENTLINE$char"
    CURRENTLINE=$(echo "$CURRENTLINE" | sed -e 's/one/1ne/;s/two/2wo/;s/three/3hree/;s/four/4our/;s/five/5ive/;s/six/6ix/;s/seven/7even/;s/eight/8ight/;s/nine/9ine/')
  done
  result1=$(echo $line | tr -d '/a-z,A-Z/' | sed -E 's/([0-9])$/\1\1/g; s/([0-9])[0-9]+([0-9])/\1\2/g')
  result2=$(echo $CURRENTLINE | tr -d '/a-z,A-Z/' | sed -E 's/([0-9])$/\1\1/g; s/([0-9])[0-9]+([0-9])/\1\2/g')

  cumresult1=$((cumresult1 + result1))
  cumresult2=$((cumresult2 + result2))

done
echo $cumresult1, $cumresult2

#!/bin/bash

calculate_factor() {
    local red=$1
    local green=$2
    local blue=$3

    local factor=$((red * green * blue))
    powersum=$((powersum + factor))
}

# Function to process each line
problem1() {
    local line="$1"
    
    # split lines into gameID and key:value pair part
    local game_number=$(echo "$line" | grep -oP '^Game \K\d+')
    local trimmed_string=$(echo "$line" | sed 's/Game [0-9]*: //')
    
    # Split trimmed_string into semicolon-separated parts
    IFS=';' read -ra parts <<< "$trimmed_string"
    
    # Initialize maximum values for each color
    local max_red=0
    local max_green=0
    local max_blue=0

    # Initialize sums for the entire game
    local red_sum=0
    local green_sum=0
    local blue_sum=0

    # Loop through each part and calculate sums
    for part in "${parts[@]}"; do
        # Extract numbers for each color
        local red=$(echo "$part" | grep -oP '\d+ red' | awk '{print $1}')
        local green=$(echo "$part" | grep -oP '\d+ green' | awk '{print $1}')
        local blue=$(echo "$part" | grep -oP '\d+ blue' | awk '{print $1}')

        ((max_red = red > max_red ? red : max_red))
        ((max_green = green > max_green ? green : max_green))
        ((max_blue = blue > max_blue ? blue : max_blue))
        ((red_sum += red))
        ((green_sum += green))
        ((blue_sum += blue))
    done

    for part in "${parts[@]}"; do
        echo "$game_number Maximum Red: $max_red, Maximum Green: $max_green, Maximum Blue: $max_blue" > /dev/null
    done

    calculate_factor "$max_red" "$max_green" "$max_blue"
}
problem2() {
    local input_file="$1"
    local max="$2"
    
    local counter=0
    local valid_game_sum=0

    while IFS= read -r line && ((counter < max)); do
        ((counter++))
        game_number=$(echo "$line" | grep -oP '^Game \K\d+')
        trimmed_string=$(echo "$line" | sed 's/Game [0-9]*: //')
        
        IFS=';' read -ra parts <<< "$trimmed_string"
        
        game_valid=true

        for part in "${parts[@]}"; do
            red_sum=0
            green_sum=0
            blue_sum=0

            red=$(echo "$part" | grep -oP '\d+ red' | awk '{print $1}')
            green=$(echo "$part" | grep -oP '\d+ green' | awk '{print $1}')
            blue=$(echo "$part" | grep -oP '\d+ blue' | awk '{print $1}')

            ((red_sum += red))
            ((green_sum += green))
            ((blue_sum += blue))

            # Check if sums exceed thresholds for the entire game
            if ((red_sum > 12)) || ((green_sum > 13)) || ((blue_sum > 14)); then
                game_valid=false
                break
            fi
        done

        if $game_valid; then
            ((valid_game_sum += game_number))
            for part in "${parts[@]}"; do
                echo "Game $game_number" > /dev/null
            done
        fi
    done < "$input_file"

    echo "Sum of Valid Game Numbers: $valid_game_sum"
}

input_file="puzzle"
max=100
echo "red 12 green 13 blue 14"
counter=0
valid_game_sum=0
powersum=0

while IFS= read -r line && ((counter < $max)); do
    ((counter++))
    problem1 "$line"
done < "$input_file"

echo "Factor of Maximum Values: $powersum"
problem2 "$input_file" "$max"

Wobei der zweite Tag mir nicht gefällt, das ist zweimal fast dasselbe Script in Funktionen, weils mir gestern zu blöd war das schön in eine zu packen. Mal kucken ob ich das noch refactor...

 

[CyborgBeta]

Hm, Tag 1 war nicht so kompliziert, hier mal ne Lösung in Java:

public class Day1 {
    static String day1 = """
            ...
            """;

    public static void main(final String[] args) {
        long sum = 0;
        for (final String line : day1.split("\n")) {
            if (line.isEmpty()) {
                continue;
            }
            StringBuilder sb = new StringBuilder(line);
            char first = '0';
            for (final char c : sb.toString()
                    .toCharArray()) {
                if (Character.isDigit(c)) {
                    first = c;
                    break;
                }
            }
            char last = '0';
            for (final char c : sb.reverse()
                    .toString()
                    .toCharArray()) {
                if (Character.isDigit(c)) {
                    last = c;
                    break;
                }
            }
            sum += 10L * Character.getNumericValue(first) + Character.getNumericValue(last);
        }
        System.out.println("sum = " + sum);
    }
}

Aber für die anderen fehlt mir gerade die Zeit.

Werde morgen noch mal schauen... Was muss man denn tun, um in die Top 100 zu gelangen? FIFO/first serve/Windhund?

 

[Ranayna]

Ich habe vom Advent of Code immer wieder mal gehoert, aber nie dran teilgenommen.
Solche Puzzel "Textaufgaben" finde ich aber interessant.
Ich will und muss eh noch mehr Routine in c# ansammeln und werd mal schauen ob ich dieses Jahr halbwegs regelmaessig teilnehmen kann, oder ich arbeite zwischen den Feiertagen einen der aelteren durch.

 

[H4110]

Respekt für die Lösungen in Bash, mir wäre das zu müßig. 🙃

Ich mache mit meiner Lieblingssprache Kotlin mit, die schockierenderweise nicht vom Code-Tag unterstützt wird. 😉

Spoiler: Tag 1

fun part1(input: List<String>): Int = input.sumOfCalibrationValues()
fun part2(input: List<String>): Int = input.sumOfCalibrationValues(withWords = true)

fun List<String>.sumOfCalibrationValues(withWords: Boolean = false): Int = sumOf { it.calibrationValue(withWords) }

val DIGITS = listOf("one", "two", "three", "four", "five", "six", "seven", "eight", "nine")

fun String.calibrationValue(withWords: Boolean = false): Int =
 indices.mapNotNull { start ->
  this[start].takeIf { it.isDigit() }?.digitToInt()
   ?: if (withWords) {
    val s = substring(start)
    (DIGITS.indexOfFirst { s.startsWith(it) }+1).takeIf { it>=1 }
   } else null
 }.let { 10*it.first()+it.last() }

Spoiler: Tag 2

fun part1(input: List<String>): Int = input.map { Game(it) }.filter { it.isPossible() }.sumOf { it.number }
fun part2(input: List<String>): Int = input.map { Game(it) }.sumOf { it.power() }


enum class Color {
 RED, GREEN, BLUE
}


class Game(line: String) {
 val number: Int
 private val sets: List<ColorSet>

 init {
  val (game, sets) = line.split(": ")
  number = game.split(" ")[1].toInt()
  this.sets = sets.split("; ").map { ColorSet(it) }
 }

 fun isPossible() = sets.all { it.isPossible() }
 fun power() = Color.entries.map { c -> sets.maxOf { it.colors[c] ?: 0 } }.reduce { a, c -> a*c }
}


class ColorSet(s: String) {
 val colors: Map<Color, Int>

 init {
  colors = s.split(", ")
   .map { it.split(" ") }
   .associate { Color.valueOf(it[1].uppercase()) to it[0].toInt() }
 }

 fun isPossible() = colors.all { it.value<=it.key.ordinal+12 }
}

Spoiler: Tag 3

fun part1(input: List<String>): Int = input.lineSets().flatMap { it.partNumbers() }.sum()
fun part2(input: List<String>): Int = input.lineSets().flatMap { it.gearRatios() }.sum()


fun List<String>.lineSets(): List<LineSet> = indices.map { idx ->
 val current = this[idx]
 val surrounding = listOf(idx-1, idx+1).filter { it in indices }.map { this[it] }
 LineSet(current, surrounding)
}


val RE_INT = Regex("\\d+")
fun String.findInts() = RE_INT.findAll(this)
fun Char.isSymbol() = this!='.' && !isDigit()


class LineSet(private val current: String, surrounding: List<String>) {
 private val all: List<String> = surrounding+current
 private fun IntRange.expanded() = (first-1).coerceAtLeast(0)..(last+1).coerceAtMost(current.length-1)

 fun partNumbers(): List<Int> =
  current.findInts().filter { matchResult ->
   val range = matchResult.range.expanded()
   all.any { s -> s.substring(range).any { it.isSymbol() } }
  }.map {
   it.value.toInt()
  }.toList()

 fun gearRatios(): List<Int> =
  current.mapIndexedNotNull { index, c -> index.takeIf { c=='*' } }
   .map { gearIndex -> (gearIndex..gearIndex).expanded() }
   .map { range -> all.flatMap { it.findInts() }.filter { it.range.intersect(range).isNotEmpty() }.map { it.value.toInt() } }
   .filter { numbersInRange -> numbersInRange.size==2 }
   .map { it[0]*it[1] }
}

Spoiler: Tag 4

fun part1(input: List<String>): Int = input.map { Card(it) }
 .map { it.matchCount }
 .filter { it>0 }
 .sumOf { 2.0.pow(it-1).toInt() }


fun part2(input: List<String>): Int {
 val cards = input.map { Card(it) }

 for ((idx, card) in cards.withIndex()) {
  if (idx==cards.size-1) continue
  for (i in (idx+1).coerceAtMost(cards.size-1)..(idx+card.matchCount).coerceAtMost(cards.size-1))
   cards[i].count += card.count
 }

 return cards.sumOf { it.count }
}


val RE_INT = Regex("\\d+")
fun String.findInts(): List<Int> = RE_INT.findAll(this).map { it.value.toInt() }.toList()


class Card(line: String) {
 var count = 1
 val matchCount: Int

 init {
  val (winningNumbers, numbers) = line.split(":")[1].split("|").map { it.findInts() }
  matchCount = numbers.filter { it in winningNumbers }.size
 }
}

 

[H4110]

Tag 5 war bisher der anspruchsvollste. Wenn man bei Teil 2 den naheliegenden, naiven Ansatz wählt, braucht man einen schnellen Rechner und Geduld, oder man lässt sich was besseres einfallen. 🙃 Meine Lösung ist hier.

Tag 6 (heute) ist einfach und fällt in die Kategorie Rechenaufgaben, die sich auch algorithmisch lösen lassen. Bei Teil 2 würde der algorithmische Ansatz jedoch ähnlich wie bei Tag 5 relativ rechenintensiv, im Gegensatz zu Tag 5 aber noch absolut praktikabel.

Tipp: bei beiden Tagen lieber gleich 64bit-Integer nehmen. 😉

 

[Mordi]

Ich muss mal noch schauen beim Tag5, aber ist ziemlicher Schmerz wohl

 

[Mordi]

So, für Tag 5 ein Bash Script geschrieben. Das läuft jetzt seit über 2h und bringt die Laptop CPU (auf allen 8 Threads) zum brennen - und so arschlahm ist ein Core i7-1165G7 auch nicht.
Ich habs jetzt mal testweise auf meinen Homeserver daheim noch geworfen, dann darf sich der Ryzen 4500 ausnahmsweise mal nicht langweilen.
Wenn schon Bruteforcen dann richtig!

 

[BeBur]

Tag 6 (heute) ist einfach und fällt in die Kategorie Rechenaufgaben, die sich auch algorithmisch lösen lassen. Bei Teil 2 würde der algorithmische Ansatz jedoch ähnlich wie bei Tag 5 relativ rechenintensiv, im Gegensatz zu Tag 5 aber noch absolut praktikabel.

Ich habe bei Tag 6 Teil 2 mit einer naiven algorithmischen Lösung (= alles von 0 bis time berechnen) mit C++ ca. 250ms Rechenzeit.

 

[Ranayna]

Ich komm wohl leider erst am Freitag dazu richtig einzusteigen, aber das klingt ja schonmal spannend

 

[BeBur]

Wenn schon Bruteforcen dann richtig!

Ist das Tag 5 Teil 1 oder Teil 2? So wie ich das hier sehe ist Teil 2 mit Skriptsprachen numerisch zu lösen völlig aussichtslos .
Ich hab grad Teil 1 fertig gemacht (C++) und er rechnet gerade an Teil 2. Teil 2 dauert ein hyper-vielfaches länger .

 

[Mordi]

Ist ein Bash Skript was beide Teile auf einmal lösen soll

 

[BeBur]

@Mordi Rein aus Interesse, wo hast du die Aufgabenstellung für den zweiten Teil her? Die wird ja eigentlich erst freigeschaltet, wenn man Teil 1 gelöst hat.

 

[Mordi]

Von nem Kollegen der da flotter war wie ich

 

[BeBur]

Ist ein Bash Skript was beide Teile auf einmal lösen soll

Spoiler: Enthält Lösungsansatz

Berechnest du die mappings pro schritt und verdichtest dann um eine simple Zuordnung zu erhalten?

Ich hab erstmal den straight-forward Weg genommen(*). Aber wenn ich mir anschaue, wie lange das dauert, dann implementiere ich vielleicht doch noch bei Gelegenheit den Ansatz im obigen Spoiler. Jedenfalls würde ich intuitiv sagen, dass das deutlich schneller gehen sollte bei so vielen seeds.

(*)

Spoiler: Enthält Lösungsansatz

Ich suche in jedem Schritt die nächst kleinere source range start und schaue, ob der aktuelle Wert in dem zugehörigen Intervall ist. Wenn ja, dann berechne ich den "offset" und passe den Wert entsprechend an. Ansonsten gebe ich den unveränderten Wert zurück

 

[Mordi]

Über Day 5 denk ich weiter nach wenn mein Script mit dem ganzen Datensatz erfolgreich gelaufen ist.
Hier mal mein funktionales Script für Day 6

Weil ich n fauler Sack bin hab ich in Part 1 denselben forloop 4x copypastet anstatt ne funktion zu basteln.
Mach ich vielleicht heut noch. Mal kucken.
Außerdem habe ich die Größe des Arrays hardcoded (ein for loop pro position, ein Resultat dessen dass ich auf funktionen verzichte), also würde ein Array aus 5 Positionen nicht unterstützt werden derzeit - ich nehme genau 4 mit. Weswegen der Ergebnisoutput für Example auch ne andere var ist
Zum Ergebnis gehts mit:
./main.sh puzzle | grep success | wc -l
Laufzeit ist wieder recht hoch, kann gerne mal richtung 20 Minuten gehen.

#!/bin/bash

input_file="$1"
speed=0
time_array=()
distance_array=()

total1=1
total2=1
total3=1
total4=1

while IFS=':' read -r label values; do
    case $label in
        "Time")
            time_array+=($values)
            ;;
        "Distance")
            distance_array+=($values)
            ;;
    esac
done < "$input_file"

for ((i = 1; i <= ${time_array[0]}; i++)); do
    speed=$(($i))
    remaining_time=$((${time_array[0]} - $i))
    distance_traveled=$((speed * remaining_time))
    if [ "$distance_traveled" -gt "${distance_array[0]}" ]; then
        ((total1++))
    fi
done
for ((i = 1; i <= ${time_array[1]}; i++)); do
    speed=$(($i))
    remaining_time=$((${time_array[1]} - $i))
    distance_traveled=$((speed * remaining_time))
    if [ "$distance_traveled" -gt "${distance_array[1]}" ]; then
        ((total2++))
    fi
done
for ((i = 1; i <= ${time_array[2]}; i++)); do
    speed=$(($i))
    remaining_time=$((${time_array[2]} - $i))
    distance_traveled=$((speed * remaining_time))
    if [ "$distance_traveled" -gt "${distance_array[2]}" ]; then
        ((total3++))
    fi
done
for ((i = 1; i <= ${time_array[3]}; i++)); do
    speed=$(($i))
    remaining_time=$((${time_array[3]} - $i))
    distance_traveled=$((speed * remaining_time))
    if [ "$distance_traveled" -gt "${distance_array[3]}" ]; then
        ((total4++))
    fi
done

((total1--))
((total2--))
((total3--))
((total4--))

exampletotal=$((total1*total2*total3))
total=$((total1*total2*total3*total4))



## part 2
total_ways=1

bignumber() {
    local result=""
    for element in "$@"; do
        result="${result}${element}"
    done
    echo "$result"
}

bigtime=$(bignumber "${time_array[@]}")
bigdist=$(bignumber "${distance_array[@]}")

echo $bigtime
echo $bigdist

calculate_ways_to_win() {
    local time=${1}
    local distance=${2}
    local total=1
   
    for ((i = 1; i <= time; i++)); do
        speed=$((i))
        remaining_time=$((time - i))
        distance_traveled=$((speed * remaining_time))
       
        if [ "$distance_traveled" -gt "$distance" ]; then
            ((total++))
            echo "success"
        fi
    done
   
    return $total
}

calculate_ways_to_win "$bigtime" "$bigdist"
if [ "$input_file" = "example" ]; then
    echo "++++++++++++EXAMPLE ONE $exampletotal++++++++++++++++++"
else
    echo "++++++++++++PART ONE $total++++++++++++++++++"
fi

 

[H4110]

Ich habe bei Tag 6 Teil 2 mit einer naiven algorithmischen Lösung (= alles von 0 bis time berechnen) mit C++ ca. 250ms Rechenzeit.

Jo, bei mir waren es auf der JVM letztendlich auch nur etwa 750 ms, aber zunächst hatte ich noch ein println in jeder Iteration, und dann springt einem die Ineffizienz quasi ins Auge. Die Console der IDE geht dabei auch etwas in die Knie. 🙃

Im Vergleich zu 0,05 ms, die eine Berechnung benötigt, sind 750 ms aber schon heftig. Meine Lösung, die beides macht und die benötigte Zeit ausgibt, ist hier auf dem Kotlin Playground.


Tag 5 Teil 2 habe ich zunächst auch mit Brute Force gelöst. Hat single-threaded auf einem AMD 5950X irgendwas zwischen 15 und 30 Minuten gedauert, habe leider nicht genau drauf geachtet. Mich reizt es irgendwie, das mit Kotlin Multiplatform für JVM, Native und JS zu bauen und die Performance zu vergleichen. Mache ich bei Gelegenheit vielleicht.

 

[BeBur]

Tag 5 Teil 2 habe ich zunächst auch mit Brute Force gelöst. Hat single-threaded auf einem AMD 5950X irgendwas zwischen 15 und 30 Minuten gedauert

Ich hab nochmal eine andere Lösung geschrieben die schneller war, aber immer noch 5 Stunden gebraucht hat. Habe auf Youtube gesehen, wie eine naive Lösung in 10 Sekunden (threaded) durchläuft. Ich denke, irgendwo bei mir waren unnötige Schreibvorgänge o.ä..
Man sollte vllt auch das Release build laufen lassen statt dem debug build . Hat dann bei mir auch nur 100 Sekunden gedauert (single thread).

Tag 6 hatte ich schon, habe gestern mal Tag 7 angefangen, mache ich heute vermutlich fertig. Tag 8 sieht auch ganz cool aus, aber ich werde kommende Woche evtl. nicht mehr so viel Zeit haben viele Aufgaben zu lösen. Zumal die ja kontinuierlich schwerer werden.

 

[H4110]

Tag 7 war cool.

Bei Tag 8 war der erste Teil easy, der zweite irgendwie blöd. Wieder so ein Brute-Force-Ding, noch extremer als Tag 5. Eine allgemeingültige analytische Lösung ist, soweit ich das beurteilen kann, äußerst tricky, aber beim Rumprobieren fielen mir ein paar Begebenheiten auf, die es einfach machten.

Spoiler: Größenordnung des Ergebnisses

Bei meinem Input rund 14 Billionen Schritte.
Habe das mal just for fun gebenchmarkt: single-threaded gehen auf der JVM etwa 210 Millionen Schritte/s.

Ergänzung (9. Dezember 2023)

Spoiler: Lösungshinweis

Man läuft praktischerweise immer zu Beginn der Instruktionen über einen End-Node. Und auch der Weg in den Loop (den es ja geben muss) ist so, dass er keinen Einfluss auf das Intervall hat. Man läuft alle N*(Länge der Instruktionen) Schritte über einen End-Node und alle N sind Primzahlen (d.h. das Vielfache aller N ist auch das kleinste).