Advent of Code 2018
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)
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!
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}")
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}`)
}
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());
}
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)))
Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer
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());
}
Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer
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)}")
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)}")
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)}")
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)
}
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.
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());
}
Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer
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.
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
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.
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
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
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)}")
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());
}
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());
}
Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer
Coolt synd att man ej såg detta tidigare. Dock så har jag väldigt ont om tid, men det är en perfekt övning för studenter.
Det känns som om VHDL är ett perfekt hårdvarubeskrivande språk för de som älskar utmaningar till dessa problem.
Kämpar med mina input parsing-skills, så det har inte blivit mycket gjort för min del.
Svårighetsgraden drog iväg ganska snabbt märkte jag
Grubblare
- Igår Efter konkursryktena – Louqe är tillbaka 17
- Igår Kunskapsquiz: IT och det moderna försvaret 41
- 17 / 4 Datorhallar åker på miljardstor skattesmäll – ljög om att utvinna krypto 62
- 17 / 4 Veckans fråga: Möss eller ljud – Vad lägger du mest pengar på? 73
- 16 / 4 X kan råda bot på bottar med betallösning 35
- Snart ber Microsoft dig överge ditt lokala konto112
- moderbord eller moderkort?30
- Dagens fynd (bara tips, ingen diskussion) — Läs första inlägget först!18388
- Experter. Vilket 4070 ti 12gb är detta?7
- Bästa grafikkortsköpet i april 2024171
- Stora feta metaltråden!5032
- Dagens fynd — Diskussionstråden49409
- S24 Ultra utan skärmskydd11
- "Dumma" strömbrytare som folk inte använder av misstag?0
- Här är priserna på LG:s nya OLED-arsenal52
- Köpes Köper Samsung Galaxy Buds 2 Pro / Buds 2
- Säljes LC Power 39 tum 165 hz Bildskärm
- Säljes 12700k | 980 PRO 1tb | Contact Frame TG
- Köpes Söker USB-C transmitter till Steelseries Arctis 7X PLUS
- Säljes Diverse PS5-spel, Ritplatta och Motorola Moto G 5g plus!
- Säljes RTX 3050 8 GB ROG STRIX GAMING OC
- Säljes Sennheiser HD560S och RÖDE NT-USB
- Säljes Mp600 Pro 2TB, hel dator gtx 1080,6700k, ryzen 3600 samt gtx 1070
- Säljes AOC AGON PRO PD32M - 32" 4K IPS MiniLED 144 Hz
- Säljes ASUS Z170-A inklusive CPU i7-6700 och kylare "be quiet! Pure Rock"
- SFW! Läckra ROG Zephyrus G14 med ROG Nebula OLED Display2
- Quest 2 får prissänkning för andra gången i år16
- Elgato lanserar tillbehörsserie för ”vanligt folk”10
- Enhance! Edge kan få klassisk sci-fi-funktion16
- Efter konkursryktena – Louqe är tillbaka17
- Snart ber Microsoft dig överge ditt lokala konto112
- Kunskapsquiz: IT och det moderna försvaret41
- Här är priserna på LG:s nya OLED-arsenal52
- 3dfx grafikkort återuppstår i hobbyprojekt19
- Logitech släpper ”AI-knapp” – snabbgenväg till Chat GPT12