Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Nov 2011

Advent of Code 2018

Jag hittade en tråd från 2016, men ingen för i år.

Advent of Code är en kalender där luckorna innehåller kluriga uppgifter som med fördel löses av datorskrivna program. Varje dag, klockan 06:00 (Svensk tid), öppnas en ny lucka och man kan ge sig i kast med att lösa problemen i vilken språk man vill.

Jag har skapat en leaderboard som jag tänkte att vi kunde använda som en SweClockers-leaderboard. Joina med koden: 115994-59705230 på följande länk: https://adventofcode.com/2018/leaderboard/private

Om du redan har börjat lösa kommer dina poäng automagiskt kopieras till leaderboarden ovan. Har du inte börjat är det hög tid.

Häng med, det blir kul!

Linux: the operating system with a CLUE; Command Line User Environment.

GNU/Linux

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Nov 2011

Jag tänker vidare att vi kan dela lösningar, ge ledtrådar, osv här. Så använd spoiler-taggar om ni delar lösningar. Gärna på formen:

Dag: 4
Språk: Python
Lösning:

if __name__ == "__main__: return solution(day4)

Dold text

Linux: the operating system with a CLUE; Command Line User Environment.

GNU/Linux

Trädvy Permalänk
Medlem
Registrerad
Nov 2013

Kul sida, inte sett den tidigare. Gjorde 2 första dagarna nu innan jag kände att jag behöver vara mer produktiv... Återkommer nog imorgon!

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Nov 2011

Dagens utmaning var en riktig smärta för mig. Jag gjorde en tabbe (se spoiler) som gjorde att jag la nästan en timme istället för de 20 minuter det tog att skriva lösningen.

Dag: 5
Språk: Python
Lösning:

Felet jag gjorde var att inte ta bort whitespace från input, så jag fick 10497 som svar istället för 10496. Skrev tre olika lösningar (en dum rekursiv, en dum iterativ, och en stack-lösning (se nedan)) och alla fick samma svar så då fick jag kolla så inte input var fel....

def stack_polymer(string): reduced = "" for c in string: reduced += c if len(reduced) > 1 and reacts(reduced[-1], reduced[-2]): reduced = reduced[:-2] return reduced def reacts(l1, l2): if l1.lower() == l2.lower(): if (l1.islower() and l2.isupper()) or (l1.isupper() and l2.islower()): return True return False ## MAIN ## if __name__ == "__main__": with open("input") as in_f: polymer = in_f.readline().strip() ## a reduced_polymer = stack_polymer(polymer) print(f"a: {len(reduced_polymer)}") ## b best_unit_removed = "" best_length = 99999999999999999999 for c in "abcdefghijklmnopqrstuvwxyz": modified_polymer = polymer.replace(c, "").replace(c.upper(), "") reduced_polymer = stack_polymer(modified_polymer) if len(reduced_polymer) < best_length: best_length = len(reduced_polymer) best_unit_removed = c print(f"b: {best_length}")

Dold text

Linux: the operating system with a CLUE; Command Line User Environment.

GNU/Linux

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Apr 2004

Lyckades ta mig tid att bli klar, ingen vaker lösning men if it works <:
Dag: 5
Språk: JS
Lösning:

Gjorde samma miss med whitespace

_Extract = $0.innerText function dayOfCodeDay5(){ console.log(`Started`); function removePair(position){ var LastPart = _Extract.slice(position+2); var FirstPart = _Extract.substring(0,position); _Extract = FirstPart + LastPart; } function checkPair(valueOne){ diff = valueOne.charCodeAt(0) - valueOne.charCodeAt(1); return Math.abs(diff) == 32; } i = 0 while(i+2 <= _Extract.length){ if(checkPair(_Extract.substring(i,i+2))){ removePair(i); i = 0; }else{ i++; } } console.log(`The result is: ${_Extract.trim().length}`) }

Dold text
Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011

Har tänkt gänga på advent of code både i år och förra året, men rätt svårt att hitta tiden så här i jultider och årsslut
Hann t.ex. inte posta nedan igår som tänkt...

Dag: 5
Språk: C++
Lösning:

#include <algorithm> #include <numeric> #include <cstring> #include <fmt/format.h> #include <limits> #include <sstream> #include <string> #include <vector> // const vector<std::string|int> input = {...}; #include "input.hpp" bool sameType(char a, char b) { return toupper(a) == toupper(b); } bool samePolarity(char a, char b) { return isupper(a) == isupper(b); } std::string synthesis(std::string polymer, char unit) { if (polymer.size() > 0 && sameType(polymer.back(), unit) && !samePolarity(polymer.back(), unit)) { polymer.pop_back(); } else { polymer += unit; } return polymer; } size_t react(std::string polymer) { return std::accumulate (polymer.begin(), polymer.end(), std::string(""), synthesis).size(); } std::string distinctTypes() { auto types = input.front(); std::transform(types.begin(), types.end(), types.begin(), ::tolower); std::sort(types.begin(), types.end()); types.erase(std::unique(types.begin(), types.end()), types.end()); return types; } unsigned part1() { return react(input.front()); } unsigned part2() { auto originalPolymer = input.front(); auto shortestLen = std::numeric_limits<size_t>::max(); for (auto typeToRemove: distinctTypes()) { std::stringstream reducedPolymer; std::remove_copy_if(originalPolymer.begin(), originalPolymer.end(), std::ostream_iterator<char>(reducedPolymer), [=](char t) { return sameType (t, typeToRemove); }); auto polymerLen = react(reducedPolymer.str()); if (polymerLen < shortestLen) { shortestLen = polymerLen; } } return shortestLen; } int main() { fmt::print("Part 1: {}\n", part1()); fmt::print("Part 2: {}\n", part2()); }

Dold text

Började med C++, men tänkte sedan att orsakerna att vara med i Advent of code är endera att gå för leader-board, men det är ju redan kört i år då jag missade första dagarna.

Andra uppenbara anledningen är ju att det är ett gyllne tillfälle att lägga lite tid på något programspråk man inte jobbar med på en daglig basis. Använder R en del hemma då det är ett lämpligt språk för att använda till att borra lite i olika datamängder.

Är inte direkt perfekt match för sträng hantering, men dag 5 blev ändå helt OK i R. Problemet är primärt att R är rätt snabbt när man jobbar på tänkt sätt med data, det är allt annat än snabbt texthantering...

Dag: 5
Språk: R
Lösning:

library(readr) polymer <- gsub("[\r\n]", "", read_file("input")) isUpper <- function(c) grepl("[[:upper:]]", c) sameType <- function(a,b) toupper(a) == toupper(b) samePolarity <- function(a, b) isUpper(a) == isUpper(b) stringAsList <- function(s) unlist(strsplit(s, "")) # Part 1 removeLast <- function(s) substr(s, 1, nchar(s) - 1) lastChr <- function(s) if (nchar(s) > 0) stringAsList(s)[nchar(s)] else s synthesis <- function(result, unit) { lastUnit <- lastChr(result) if (sameType(unit, lastUnit) & !samePolarity(unit, lastUnit)) { removeLast(result) } else { paste(result, unit, sep="") } } react <- function(polymer) Reduce(synthesis, stringAsList(polymer), "") cat(sprintf("Part 1: %d\n", nchar(react(polymer)))) # Part 2 uniqueUnits <- levels(factor(sapply(stringAsList(polymer), toupper))) # This will take a while... cat("Working with part 2 ") reducedPolyLen <- sapply(uniqueUnits, function (unitToRemove) { p <- stringAsList(polymer) cat(".") r <- react(p[!sameType(p, unitToRemove)]) nchar(r) }) cat(sprintf("\nPart 2: %d\n", min(reducedPolyLen)))

Dold text

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011

Tänkte lösa dagens problem direkt på morgonen, sedan blev man träffad av alla "måsten"...

Var i alla fall ett roligt problem, andra delen är något de med åsikten "bara dåliga programmerare som är hinder för att nyttja många kärnor" borde studera i detalj

Tog C++ idag, är lite för mycket nybörjare på R så har inte tid just nu. Får nog bli ett semesterprojekt i stället.

Dag: 7
Språk: C++
Lösning:

#include <algorithm> #include <fmt/format.h> #include <iterator> #include <map> #include <optional> #include <queue> #include <regex> #include <set> #include <string> #include <utility> #include <vector> #include <iostream> // const std::vector<std::string|int> input = {...}; #include "input.hpp" using Step = char; using Prereq = std::set<char>; using Steps = std::map<char, Prereq>; struct Work { Work(Step s, unsigned c) : step(s) , completedSec(c) { } bool operator<(const Work & a) const { return this->completedSec > a.completedSec; } Step step; unsigned completedSec; }; using WorkQ = std::priority_queue<Work>; using Result = std::pair<std::string, unsigned>; Steps stepsGet() { std::regex re( "Step ([A-Z]) must be finished before step ([A-Z]) can begin."); std::smatch matches; Steps steps; for (auto line : input) { std::regex_search(line, matches, re); Step pre = matches[1].str()[0]; Step step = matches[2].str()[0]; steps[pre]; steps[step].insert(pre); } return steps; } unsigned workCost(Step step, unsigned latency) { return (step - 'A' + 1) + latency; } std::optional<Step> nextStep(Steps & steps, const Prereq & fulfilled) { auto it = std::find_if(steps.begin(), steps.end(), [&](auto & step) { return std::includes(fulfilled.begin(), fulfilled.end(), step.second.begin(), step.second.end()); }); if (it == steps.end()) { return std::nullopt; } return std::optional<Step>(it->first); } Result compute(Steps steps, unsigned numWorkers = 1, unsigned latency = 0) { Prereq fulfilled; std::string done; unsigned elapsedSec = 0; unsigned availWorkers = numWorkers; WorkQ workQ; do { auto step = nextStep(steps, fulfilled); if (step && availWorkers > 0) { // Schedule more work Step s = step.value(); availWorkers--; steps.erase(s); workQ.push(Work(s, elapsedSec + workCost(s, latency))); } else { // Move to closest second where work is commited, commit all work // for that second do { auto work = workQ.top(); fulfilled.insert(work.step); done += work.step; elapsedSec = work.completedSec; availWorkers++; workQ.pop(); } while (!workQ.empty() && elapsedSec == workQ.top().completedSec); } } while (!steps.empty() || !workQ.empty()); return std::pair(done, elapsedSec); } auto part1() { return compute(stepsGet()).first; } auto part2() { return compute(stepsGet(), 5, 60).second; } int main() { fmt::print("Part 1: {}\n", part1()); fmt::print("Part 2: {}\n", part2()); }

Dold text

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Nov 2011

Så kom en ny dag. Har tyckt att svårighetsgraden har ökat rejält sedan de första 3-4 problemen. Har behövt rådfråga vänner eller rentav glimta på lösningar för att klara några av de senare deluppgifterna.

Hur som haver. Idag gick det lite bättre. Efter en ledtråd från en vänlig själ lyckades jag lösa a och b var därefter inte särskilt svår.

Dag: 8
Språk: Python
Lösning:

# part a def find_metasum(nodes): children = nodes[0] metaentries = nodes[1] rem = nodes[2:] metasum = 0 for i in range(children): child_metasum, rem = find_metasum(rem) metasum += child_metasum metasum += sum(rem[:metaentries]) return metasum, rem[metaentries:] # part b def find_root_value(nodes): children = nodes[0] metaentries = nodes[1] rem = nodes[2:] values = [] for i in range(children): child_value, rem = find_root_value(rem) values.append(child_value) if children == 0: value = sum(rem[:metaentries]) else: value = 0 for n in rem[:metaentries]: if n > children: value += 0 else: value += values[n-1] return value, rem[metaentries:] ## MAIN ## if __name__ == "__main__": data = get_input(8) print(f"a: {find_metasum(data)}") print(f"b: {find_root_value(data)}")

Dold text

Linux: the operating system with a CLUE; Command Line User Environment.

GNU/Linux

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Nov 2011

Dagens problem var roligt tycker jag!

Dag: 9
Språk: Python
Lösning:

Precis som sig bör började jag med vad jag trodde var en enkel lösning. Det tog alldeles för lång tid att hitta rätt i min array (alltså för min egna del, datorn klarade det bra) men tillslut hade jag en primitiv array-lösning. Sen tänkte jag: "100 gånger så många kulor? Det ska den väl klara?"..... satte igång programmet och besökte toaletten. Kom tillbaka och inget hade hänt, så då började jag ge mig på en länkad-lista-lösning. Spenderade 30 minuter med att återuppfinna hjulet innan jag bestämde mig för att bara nyttja det som är mig givet: deque.

deque.rotate kom väl till pass då jag alltid såg till att ha "current marble" längst till höger i listan. Då kunde jag snurra åt endera håll efter behag. Slutresultatet ses nedan och runtime är enligt följande:

  • Uppgift a med array-implementation: 380ms

  • Uppgift a med länkad lista: 20ms (nästan 20ggr snabbare)

  • Uppgift b med array-implementation: N/A

  • Uppgift b med länkad lista: 2200ms

def task_1(players=9, last_marble_point=25): scores = [0] * players circle = [0] p = 0 marble = 0 current_marble_idx = 0 while marble < last_marble_point: p = (p + 1) % players marble += 1 insert_at = (current_marble_idx + 2) % len(circle) if marble % 23 == 0: current_marble_idx = (insert_at - 9) % len(circle) score = marble score += circle.pop(current_marble_idx) scores[p] += score else: circle.insert(insert_at, marble) current_marble_idx = insert_at return(max(scores)) def task_2(players=9, last_marble_point=25): scores = [0] * players circle = deque() circle.insert(0, 0) p = 0 marble = 0 while marble < last_marble_point: p = (p + 1) % players marble += 1 if marble % 23 == 0: circle.rotate(-7) score = marble score += circle.pop() scores[p] += score else: circle.rotate(2) circle.append(marble) return(max(scores)) ## MAIN ## if __name__ == "__main__": data = get_input(9) print(f"a: {task_1(data[0], data[1])}") print(f"b: {task_2(data[0], data[1]*100)}")

Dold text

Linux: the operating system with a CLUE; Command Line User Environment.

GNU/Linux

Trädvy Permalänk
Medlem
Registrerad
Feb 2007

Jag har fått för mig att lösa alla uppgifter i Elixir, för det använder jag nästan aldrig och det är ett väldigt spännande språk. Men för dagens uppgift var jag lite för dålig för att klara helt i Elixir, så det blev en lösning i Go också, för det använder jag också nästan aldrig :).

Dag: 9
Språk: Elixir
Lösning:

Jag insåg redan när jag skrev koden att List.insert_at skulle vara långsam, men jag hoppades att det skulle räcka för inputstorleken man fick. Tji fick jag. Löser första delen på ca en minut, men jag har inte ens försökt köra del två med denna kod.

Data i Elixir är immutable så det är kanske egentligen ett ganska opassande språk för dagens problem. Men det finns sätt att arbeta sig runt och skriva en optimerad version. Skulle dock ta mer tid än vad jag har idag.

defmodule Marble do def put([], marble, _) do {[marble], 0, 0} end def put(circle, marble, current) when rem(marble, 23) == 0 do new_current = rem(current - 7 + length(circle), length(circle)) {score, new_circle} = List.pop_at(circle, new_current) {new_circle, new_current, score + marble} end def put(circle, marble, current) do new_current = rem(current + 1, length(circle)) + 1 new_circle = List.insert_at(circle, new_current, marble) {new_circle, new_current, 0} end end players = 465 marbles = 71498 high_score = Enum.reduce(0..marbles, {[], 0, %{}}, fn marble, {circle, current, scores} -> {circle, current, score} = Marble.put(circle, marble, current) player = rem(marble, players) scores = Map.update(scores, player, score, fn s -> s + score end) {circle, current, scores} end) |> elem(2) |> Map.values |> Enum.max IO.puts("Highest score: #{inspect(high_score)}")

Dold text

Dag: 9
Språk: Go
Lösning:

Hittade en inbyggd datastruktur som var perfekt, kör på ca 1,5 sekunder för del två.

package main import ( "container/ring" "fmt" ) func main() { circle := ring.New(1) circle.Value = 0 score := make(map[int]int) numPlayers := 465 lastMarble := 7149800 for i := 1; i <= lastMarble; i++ { if i%23 == 0 { circle = circle.Move(-6) toRemove := circle.Move(-2) score[i%numPlayers] += circle.Prev().Value.(int) + i toRemove.Unlink(1) } else { newElement := ring.New(1) newElement.Value = i circle = circle.Next().Link(newElement).Prev() } } maxScore := 0 for _, v := range score { if v > maxScore { maxScore = v } } fmt.Printf("Max: %v\n", maxScore) }

Dold text
Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011

Dag 10:
Enda relevanta att diskutera idag tror jag är: vilken heurestik använde ni för att avgöra när meddelandet visade sig?

Räknade ut högsta hastighet två punkter rörde sig relativt varandra i Y-led. Hoppade sedan fram sekund för sekund till att alla punkter befann sig inom detta spann i Y-led.

Dold text

Dag: 9
Språk: C++

Lite förvånad att Go är så pass mycket långsammare här jämfört med C++. Gjorde rätt mycket den enklast tänkbara lösningen, d.v.s. tog standard-implementationen av C++ dubbel-länkade lista (<list>) och lade till framåt/bakåt manövrering som-om den vore cirkulär.

På min dator med min input:
Python3: 1,4s
Go: 0,8s
C++: 0,2s

Att det tar till "Ragnarök" att få ett resultat med en C-style array blir rätt uppenbart om man gör ett överslag på hur mycket data som ska flyttals totalt sett. Det ovanpå att mängden data som flyttals kommer trilla ur L3$ i slutändan.

~7M kulor -> ~28M data för att hålla reda på en i en array (om vi antar att de represteras som 32-bitars heltal).

I genomsnitt kommer man behöva flytta 1/4 av denna mängd varje gång, så 7M (vilket i sig får plats i L3$ på vissa CPUer, men det är som sagt genomsnitt, cachen blir trashad rätt ofta då mer data flyttas).

Totalt kommer man behöver hantera 7M (antal rundor) * 7M (genomsnittlig mängd data att skyffla) = ~49 TB. Givet att bandbredd mot L3 är ett par hundra GB/s och bandbredd mot RAM är några tiotals GB/s så kommer det ta en stund...

Lösning

auto clockwiseMove(auto & circle, auto it, unsigned n) { while (n-- > 0) { ++it; if (it == circle.end()) { it = circle.begin(); } } return it; } auto counterClockwiseMove(auto & circle, auto it, unsigned n) { while (n-- > 0) { if (it == circle.begin()) { it = circle.end(); } --it; } return it; } unsigned winningScore(unsigned numPlayers, unsigned finalMarble) { std::list<unsigned> circle{ 0 }; std::vector<unsigned> scores(numPlayers); unsigned player = 0; unsigned marbleNr = 0; auto cur = circle.begin(); while (++marbleNr != finalMarble) { if (marbleNr % 23 == 0) { cur = counterClockwiseMove(circle, cur, 7); scores[player] += (marbleNr + *cur); cur = circle.erase(cur); } else { cur = clockwiseMove(circle, cur, 2); cur = circle.insert(cur, marbleNr); } if (++player == numPlayers) { player = 0; } } return *std::max_element(scores.begin(), scores.end()); }

Dold text

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Nov 2011
Skrivet av Yoshman:

Dag 10:
Enda relevanta att diskutera idag tror jag är: vilken heurestik använde ni för att avgöra när meddelandet visade sig?

Räknade ut högsta hastighet två punkter rörde sig relativt varandra i Y-led. Hoppade sedan fram sekund för sekund till att alla punkter befann sig inom detta spann i Y-led.

Dold text

Jag höll koll på avståndet mellan högsta och lägsta "stjärnan". I exemplet var bokstäverna 10 punkter höga så jag loopade tills dy < 12 och hoppades att det skulle fungera. Det gjorde det

Dold text

Linux: the operating system with a CLUE; Command Line User Environment.

GNU/Linux

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Nov 2011

Dag: 11

Jag. Hatar. Edge cases.

Gjorde en snabb lösning och fick rätt på första. Den var modulär och bra så det gick att återanvända allt och bara lägga till en till loop för att lösa andra. Fick fel svar. Kollade koden; allt såg bra ut. Subtraherade/adderade ett från svaret för att se om det var ett off-by-one error. Nope.

Gick till reddit. Tog "top voted" Python-lösning och körde den med min input - samma svar som jag fick.
Tog andra bästa Python-lösningen - annat svar, också fel.
Tog tredje Python-lösningen jag hittade -- rätt svar.

Det tog nog en timme extra att lösa del 2, bara för att just mitt svar låg längs med ytterkanten av matrisen. Ogillar.

Dold text

Linux: the operating system with a CLUE; Command Line User Environment.

GNU/Linux

Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011

Blev en del frustration med del två av dagens (dag 12) lösning för min del. Insåg rätt snabbt att brute-force inte skulle gå att använda, men lyckades messa upp den fungerade lösning jag hade och var korkad nog att inte git-commit:a det jag startade från... När jag väl lurade ut hur man borde göra tog det först en onödigt lång stund att få ordning på det som tidigare hade fungerat.

På tal om "brute-force", hur löste ni del 2 i gårdagens problem?

Brute force (blev det inte O(N^5)?) ihop med C++ / OpenMP samt 8C/16T löste i slutändan det hela på <20s, cache-ade inte ens cell-resultaten utan gjorde beräkningen varje gång

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Nov 2011
Skrivet av Yoshman:

På tal om "brute-force", hur löste ni del 2 i gårdagens problem?

Printed "bästa" av varje size och efter size 14 blev det bara sämre och sämre. Ctrl-C vid size 20 och skrev det som var bäst so far.

Skickades från m.sweclockers.com

Linux: the operating system with a CLUE; Command Line User Environment.

GNU/Linux

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Nov 2011

Usch.

Dag: 14
Språk: Python
Lösning:

Del ett var okay, men del två blev bara hemsk. Aja. Det blev rätt tillslut.

def create_track(track, height=150, width=150): matrix = [[" " for i in range(height)] for j in range(width)] carts = [] r = 0 c = 0 for t in list(track): if t == "\n": r += 1 c = 0 continue if t in ["^","v"]: matrix[r][c] = "|" carts.append((r, c, t, "l", 1)) elif t in ["<",">"]: matrix[r][c] = "-" carts.append((r, c, t, "l", 1)) else: matrix[r][c] = t c = (c+1) % width return matrix, carts def print_track(track, carts=[], height=150, width=150): for r in range(height): for c in range(width): found, _, cart = find_cart(track, carts, r, c) if found: print(cart[2], end="") else: print(track[r][c], end="") print() def find_cart(track, carts, r, c): for i, cart in enumerate(carts): y = cart[0] x = cart[1] if y == r and x == c: return True, i, cart return False, False, False def drive(track, carts, height=150, width=150, show=True): counter = 0 done = False pos = [] carts = sorted(carts, key=lambda c: (c[0], c[1])) while True: if show: print_track(track, carts, height, width) for i, cart in enumerate(carts): carts = move_cart(track, carts, i, height, width) carts = detect_collision(carts) if one_left(carts): break carts = [c for c in carts if c[-1] is not 0] carts = sorted(carts, key=lambda c: (c[0], c[1])) carts = [c for c in carts if c[-1] is not 0] return carts def one_left(carts): not_crashed = len(carts) for cart in carts: if cart[-1] == 0: not_crashed -= 1 if not_crashed == 1: return True return False def detect_collision(carts): for i, cart1 in enumerate(carts): if cart1[-1] == 0: continue p1 = (cart1[0], cart1[1]) for j, cart2 in enumerate(carts): p2 = (cart2[0], cart2[1]) if cart2[-1] == 0: continue if i != j: if p1 == p2: print(f"Crash on pos: {cart1[1]},{cart1[0]}") carts[i] = (carts[i][0], carts[i][1], carts[i][2], carts[i][3], 0) carts[j] = (carts[i][0], carts[i][1], carts[i][2], carts[i][3], 0) return carts def move_cart(track, carts, i, height, width): cart = carts[i] # (row, col, dir, next turn) r = cart[0] c = cart[1] d = cart[2] n = cart[3] a = cart[4] # going up if d == "^": if track[r-1][c] == "|": carts[i] = (r-1, c, d, n, a) elif track[r-1][c] == "\\": carts[i] = (r-1, c, "<", n, a) elif track[r-1][c] == "/": carts[i] = (r-1, c, ">", n, a) elif track[r-1][c] == "+": if n == "l": carts[i] = (r-1, c, "<", "s", a) elif n == "s": carts[i] = (r-1, c, "^", "r", a) elif n == "r": carts[i] = (r-1, c, ">", "l", a) # going down if d == "v": if track[r+1][c] == "|": carts[i] = (r+1, c, d, n, a) elif track[r+1][c] == "\\": carts[i] = (r+1, c, ">", n, a) elif track[r+1][c] == "/": carts[i] = (r+1, c, "<", n, a) elif track[r+1][c] == "+": if n == "l": carts[i] = (r+1, c, ">", "s", a) elif n == "s": carts[i] = (r+1, c, "v", "r", a) elif n == "r": carts[i] = (r+1, c, "<", "l", a) # going left if d == "<": if track[r][c-1] == "-": carts[i] = (r, c-1, d, n, a) elif track[r][c-1] == "\\": carts[i] = (r, c-1, "^", n, a) elif track[r][c-1] == "/": carts[i] = (r, c-1, "v", n, a) elif track[r][c-1] == "+": if n == "l": carts[i] = (r, c-1, "v", "s", a) elif n == "s": carts[i] = (r, c-1, "<", "r", a) elif n == "r": carts[i] = (r, c-1, "^", "l", a) # going right if d == ">": if track[r][c+1] == "-": carts[i] = (r, c+1, d, n, a) elif track[r][c+1] == "\\": carts[i] = (r, c+1, "v", n, a) elif track[r][c+1] == "/": carts[i] = (r, c+1, "^", n, a) elif track[r][c+1] == "+": if n == "l": carts[i] = (r, c+1, "^", "s", a) elif n == "s": carts[i] = (r, c+1, ">", "r", a) elif n == "r": carts[i] = (r, c+1, "v", "l", a) return carts def task_1(data): height = 150 width = 150 track, carts = create_track(data, height, width) carts = drive(track, carts, height, width, False) carts = [c for c in carts if c[-1] is not 0] return(f"Last standing cart: {carts[0]}") ## MAIN ## if __name__ == "__main__": data = get_input(13) print(f"result: {task_1(data)}")

Dold text

Linux: the operating system with a CLUE; Command Line User Environment.

GNU/Linux

Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011

Har inte hunnit titta på dagens lucka än, gjorde gårdagens runt midnatt...

Var lite mer jobb än många tidigare, men ändå rätt kul.

Försöker använda C++ standardbibliotek så mycket som möjligt, här blev det då enkelt att få till en en O(N) i genomsnitt, O(N*log(N)) i värsta fall, för att reda ut kollision.

Dag: 13
Språk: C++
Lösning:

#include <fmt/format.h> #include <memory> #include <numeric> #include <optional> #include <sstream> #include <tuple> // const std::vector<std::string|int> input = {...}; #include "input.hpp" using Tracks = std::vector<std::string>; using Path = char; enum class Turn { Left, Straight, Right }; enum class Dir { N, E, S, W }; struct Coord { Coord(int x_, int y_) : x(x_) , y(y_) { } std::string str() const { std::stringstream ss; ss << x << ',' << y; return ss.str(); } unsigned x, y; }; Turn nextTurn(Turn turn) { switch (turn) { case Turn::Left: return Turn::Straight; case Turn::Straight: return Turn::Right; default: return Turn::Left; } } Dir turnLeft(Dir dir) { switch (dir) { case Dir::N: return Dir::W; case Dir::E: return Dir::N; case Dir::S: return Dir::E; default: return Dir::S; } } Dir turnRight(Dir dir) { switch (dir) { case Dir::N: return Dir::E; case Dir::E: return Dir::S; case Dir::S: return Dir::W; default: return Dir::N; } } struct Cart { Cart(Coord locStart, Dir dirStart, const Tracks & tr) : coord(locStart) , dir(dirStart) , lastIntersection(Turn::Right) , tracks(tr) { } void followTrack(Path path) { Turn turn(Turn::Straight); switch (path) { case '-': case '|': break; case '+': turn = nextTurn(lastIntersection); lastIntersection = turn; break; default: if (dir == Dir::N || dir == Dir::S) { turn = (path == '/' ? Turn::Right : Turn::Left); } else { turn = (path == '/' ? Turn::Left : Turn::Right); } break; } switch (turn) { case Turn::Straight: break; case Turn::Left: dir = turnLeft(dir); break; case Turn::Right: dir = turnRight(dir); break; } } void step() { switch (dir) { case Dir::W: coord.x--; break; case Dir::E: coord.x++; break; case Dir::N: coord.y--; break; case Dir::S: coord.y++; break; } followTrack(tracks[coord.y][coord.x]); } Coord coord; Dir dir; Turn lastIntersection; const Tracks & tracks; }; using CartPtr = std::shared_ptr<Cart>; using Carts = std::vector<CartPtr>; bool cartLt(CartPtr a, CartPtr b) { return ((a->coord.y < b->coord.y) || (a->coord.y == b->coord.y && a->coord.x < b->coord.x)); } bool cartEq(CartPtr a, CartPtr b) { return (a->coord.x == b->coord.x) && (a->coord.y == b->coord.y); } Tracks tracksGet() { Tracks tracks = input; for (auto & row : tracks) { for (Path & path : row) { if (path == '<' || path == '>') { path = '-'; } if (path == '^' || path == 'v') { path = '|'; } } } return tracks; } Carts cartsGet(const Tracks & tracks) { Carts carts; for (unsigned y = 0; y < input.size(); y++) { auto & row = input[y]; for (unsigned x = 0; x < row.size(); x++) { Path path = row[x]; Dir dir; switch (path) { case '^': dir = Dir::N; break; case '<': dir = Dir::W; break; case '>': dir = Dir::E; break; case 'v': dir = Dir::S; break; default: continue; } carts.push_back(std::make_shared<Cart>(Coord(x, y), dir, tracks)); } } return carts; } std::optional<Coord> collision(Carts & carts) { std::sort(carts.begin(), carts.end(), cartLt); auto it = std::adjacent_find(carts.begin(), carts.end(), cartEq); if (it == carts.end()) { return std::nullopt; } return std::optional((*it)->coord); } void removeCollidingCarts(Carts & carts, Coord collisionAt) { auto it = std::adjacent_find(carts.begin(), carts.end(), cartEq); carts.erase(it, it + 2); } auto part1() { Tracks tracks = tracksGet(); Carts carts = cartsGet(tracks); Carts stepOrder; std::optional<Coord> collisionAt; while (!(collisionAt = collision(carts))) { if (stepOrder.empty()) { stepOrder = carts; std::sort(stepOrder.rbegin(), stepOrder.rend(), cartLt); } stepOrder.back()->step(); stepOrder.pop_back(); } return collisionAt.value().str(); } auto part2() { Tracks tracks = tracksGet(); Carts carts = cartsGet(tracks); Carts stepOrder; while (carts.size() > 1 || !stepOrder.empty()) { if (stepOrder.empty()) { stepOrder = carts; std::sort(stepOrder.rbegin(), stepOrder.rend(), cartLt); } stepOrder.back()->step(); stepOrder.pop_back(); auto collisionAt = collision(carts); if (collisionAt) { removeCollidingCarts(carts, collisionAt.value()); } } return carts.front()->coord.str(); } int main() { fmt::print("Part 1: {}\n", part1()); fmt::print("Part 2: {}\n", part2()); }

Dold text

Edit: tacksamt med en relativt enkel "lucka" så här inför helgen
Dag: 14
Språk: C++
Lösning, underlättar om man redan löst dag 9 då det finns ett par parallelleller

#include <algorithm> #include <fmt/format.h> #include <list> #include <tuple> // const std::vector<std::string|int> input = {...}; #include "input.hpp" #define NUM_MEASURING_RECIPIES 10 using Score = unsigned; using Scoreboard = std::list<Score>; using CurrentRecipe = Scoreboard::const_iterator; void recipesMake(Scoreboard & scoreboard, Score a, Score b) { Score sum = a + b; if (sum > 9) { scoreboard.push_back(sum / 10); } scoreboard.push_back(sum % 10); } CurrentRecipe recipePick(const Scoreboard & scoreboard, CurrentRecipe cur) { auto steps = *cur + 1u; while (steps-- > 0) { ++cur; if (cur == scoreboard.end()) { cur = scoreboard.begin(); } } return cur; } std::string scoresGet(const Scoreboard & scoreboard, Scoreboard::difference_type fromIdx, Scoreboard::difference_type toIdx) { CurrentRecipe it = std::next(scoreboard.begin(), fromIdx); CurrentRecipe end = std::next(scoreboard.begin(), toIdx); std::string scores; while (it != end) { scores.push_back('0' + *it); ++it; } return scores; } Scoreboard patternMake(unsigned digits) { Scoreboard pattern; while (digits > 0) { pattern.push_back(digits % 10); digits /= 10; } std::reverse(pattern.begin(), pattern.end()); return pattern; } std::tuple<CurrentRecipe, bool> matchCheck(const Scoreboard & scoreboard, const Scoreboard & pattern, CurrentRecipe it) { while ((unsigned)std::distance(it, scoreboard.end()) >= pattern.size()) { if (std::mismatch(pattern.cbegin(), pattern.cend(), it).first == pattern.cend()) { return std::make_tuple(it, true); } ++it; } return std::make_tuple(it, false); } auto part1() { Scoreboard scoreboard{ 3, 7 }; CurrentRecipe elf1 = scoreboard.begin(); CurrentRecipe elf2 = std::next (scoreboard.begin()); auto numTrainingRecipies = input[0]; while (scoreboard.size() < numTrainingRecipies + NUM_MEASURING_RECIPIES) { recipesMake(scoreboard, *elf1, *elf2); elf1 = recipePick(scoreboard, elf1); elf2 = recipePick(scoreboard, elf2); } return scoresGet(scoreboard, numTrainingRecipies, numTrainingRecipies + NUM_MEASURING_RECIPIES); } auto part2() { Scoreboard scoreboard{ 3, 7 }; CurrentRecipe elf1 = scoreboard.begin(); CurrentRecipe elf2 = std::next(scoreboard.begin()); Scoreboard pattern = patternMake(input[0]); CurrentRecipe it = scoreboard.begin(); bool match = false; while (!match) { recipesMake(scoreboard, *elf1, *elf2); elf1 = recipePick(scoreboard, elf1); elf2 = recipePick(scoreboard, elf2); std::tie(it, match) = matchCheck(scoreboard, pattern, it); } return std::distance(scoreboard.cbegin(), it); } int main() { fmt::print("Part 1: {}\n", part1()); fmt::print("Part 2: {}\n", part2()); }

Dold text

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer