🌟 Advent of Code (AoC) 2020 🌟

PermalÀnk
Medlem ★
●
Skrivet av Ingetledigtnamn:

Jag gav upp och kikade pÄ andra lösningar i trÄden och hittade lösningen @gibbon_ postade. Det var inte helt lÀtt att först vad som hÀnde dÀr men efter en hel del pannveckande insÄg jag att det egentligen var en cirkulÀr lista men att han bara höll reda pÄ next-"pekarna" och struntade i koppnumret för det var alltid samma som indexet i tabellen. Man lÀr sig mycket av att lÀsa andras lösningar och jÀmföra med sin egen lösning. Man lÀr sig Ànnu mer om man har tid att skriva om sin egen lösning och byta till en bÀttre metod som nÄgon annan anvÀnt. Offra inte för mycket tid pÄ mina lösningar i ful-Python och gibbon_s awk, vi har inte haft lÀttlÀsthet högst upp pÄ prioritetslistan

Jag Àr ganska nöjd med de lösningar jag kom upp med, men nÄgot jag kan helt sÀkert sÀga Àr att de absolut hade sett vÀldigt annorlunda ut om jag gjort dem i nÄgot annat sprÄk. Det hÀr knepet du nÀmner t.ex. hade jag aldrig kommit pÄ om jag inte varit sÄ begrÀnsad. Jag visste att jag behövde en lÀnkad lista för prestandans skull, och hur gör man dÄ nÀr allt man har Àr en hashmap liksom?

..passar vÀl pÄ att posta nÄgra att de dagar jag inte delade tidigare

NÄgot jag fann intressant hÀr var att jag kunde serialisera data jag annars hade bevarat i strukturer, och bara skickade runt den serialiserade strÀngen istÀllet för strukturerna, som awk inte har stöd för.

<in awk -f d20.awk

d20.awk

BEGIN { for (x = 0; x <= 1; x++) { for (r = 0; r <= 3; r++) { configurations[++c] = x"|"r } } } /Tile/ { split($2, v, ":"); t = v[1] } length($0) > 0 && $0 !~ /Tile/ { dim = length($0) - 2; tiles[t] = tiles[t] == "" ? $0 : tiles[t]"|"$0 } END { for (t in tiles) { not_fitted[t] } while (length(not_fitted)) { for (t in not_fitted) { if (try_fit(t)) { delete not_fitted[t] } } } for (f in fitted) { split(fitted[f], fc, "|") split(fc[1], p, ",") c_max_x = c_max_x > p[1] ? c_max_x : p[1]; c_min_x = c_min_x < p[1] ? c_min_x : p[1] c_max_y = c_max_y > p[2] ? c_max_y : p[2]; c_min_y = c_min_y < p[2] ? c_min_y : p[2] } p1res = 1 for (f in fitted) { split(fitted[f], fc, "|") split(fc[1], p, ",") if (p[1] == c_max_x && p[2] == c_max_y) { p1res *= f } if (p[1] == c_max_x && p[2] == c_min_y) { p1res *= f } if (p[1] == c_min_x && p[2] == c_max_y) { p1res *= f } if (p[1] == c_min_x && p[2] == c_min_y) { p1res *= f } } print p1res for (f in fitted) { split(fitted[f], fc, "|") split(fc[1], p, ",") gx = (p[1] - c_min_x) * dim gy = ((c_max_y - c_min_y) - (p[2] - c_min_y)) * dim split(transform(f, fc[2]), trows, "|") for (r = 2; r < length(trows); r++) { split(trows[r], tcols, "") for (c = 2; c < length(tcols); c++) { grid[(gx + c - 2)" "(gy + r - 2)] = tcols[c] } } } image = "" for (y = 0; y < (c_max_y - c_min_y + 1) * dim; y++) { row = "" for (x = 0; x < (c_max_x - c_min_x + 1) * dim; x++) { row = row""grid[x" "y] } image = image == "" ? row : image"|"row } tiles[0] = image monster[0] = " # " monster[1] = "# ## ## ###" monster[2] = " # # # # # # " for (y = 0; y < length(monster); y++) { split(monster[y], mrow, "") for (x = 0; x < length(mrow); x++) { if (mrow[x + 1] == "#") { mon[x" "y] cmon++ } } } for (c in configurations) { delete grid split(transform(0, c), rows, "|") dimy = length(rows) for (y = 0; y < length(rows); y++) { split(rows[y + 1], cols, "") dimx = length(cols) for (x = 0; x < length(cols); x++) { if (cols[x + 1] == "#") { grid[x" "y] } } } found = 0 for (y = 0; y <= dimy - length(monster); y++) { for (x = 0; x <= dimx - length(monster[0]); x++) { gottem = 1 for (m in mon) { split(m, p); gottem = gottem && x + p[1]" "y + p[2] in grid } if (gottem) { found++ } } } if (found != 0) { break } } print length(grid) - (found * cmon) } function try_fit(t) { if (length(fitted) == 0) { fitted[t] = "0,0|1" return 1 } delete try_pos delete elim_pos for (f in fitted) { split(fitted[f], fc, "|") split(fc[1], p, ",") try_pos[p[1] + 1","p[2]] try_pos[p[1] - 1","p[2]] try_pos[p[1]","p[2] + 1] try_pos[p[1]","p[2] - 1] elim_pos[fc[1]] } for (e in elim_pos) { delete try_pos[e] } for (pos in try_pos) { for (cc in configurations) { if (test_fitting(transform(t, cc), pos)) { fitted[t] = pos"|"cc return 1 } } } return 0 } function test_fitting(tile, pos) { split(tile, trows, "|") split(pos, p, ",") fits = 1 for (f in fitted) { split(fitted[f], fc, "|") dir = in_range(pos, fc[1]) if (dir >= 0) { split(transform(f, fc[2]), frows, "|") } if (dir == 0) { fits = frows[10] == trows[1] } if (dir == 1) { fits = get_col(1, trows) == get_col(10, frows) } if (dir == 2) { fits = frows[1] == trows[10] } if (dir == 3) { fits = get_col(10, trows) == get_col(1, frows) } if (!fits) { break } } return fits } function get_col(n, rows) { col = "" for (r = 1; r <= length(rows); r++) { col = col""substr(rows[r], n, 1) } return col } function in_range(posa, posb) { split(posa, pa, ",") split(posb, pb, ",") if (pa[1] == pb[1] && pa[2] == (pb[2] - 1)) { return 0 } if (pa[1] == (pb[1] - 1) && pa[2] == pb[2]) { return 3 } if (pa[1] == pb[1] && pa[2] == (pb[2] + 1)) { return 2 } if (pa[1] == (pb[1] + 1) && pa[2] == pb[2]) { return 1 } return -1 } function transform(t, c) { split(configurations[c], cs, "|") tile = cs[1] ? flip(tiles[t]) : tiles[t] for (n = 0; n < cs[2]; n++) { tile = rotate(tile) } return tile } function flip(tile) { split(tile, rows, "|") new_tile = "" for (r = 1; r <= length(rows); r++) { split(rows[r], cols, "") new_row = "" for (c = 1; c <= length(cols); c++) { new_row = cols[c]""new_row } new_tile = new_tile == "" ? new_row : new_tile"|"new_row } return new_tile } function rotate(tile) { split(tile, rows, "|") for (r = 1; r <= length(rows); r++) { split(rows[r], cols, "") for (c = 1; c <= length(cols); c++) { rgrid[c" "r] = cols[c] } max_x = length(cols) } max_y = length(rows) new_tile = "" for (cy = 1; cy <= max_y; cy++) { new_row = "" for (cx = 1; cx <= max_x; cx++) { new_row = new_row""rgrid[cy" "(max_y - cx + 1)] } new_tile = new_tile == "" ? new_row : new_tile"|"new_row } return new_tile }

Dag 20, code galore

<in sed 's/(contains/\|/;s/)//;s/,//g' | awk -f d21.awk

d21.awk

{ split($0, prod, "|") split(prod[1], ingredients) split(prod[2], allergens) for (i in ingredients) { ingredient_count[ingredients[i]]++ } for (a in allergens) { sus[allergens[a]] = allergens[a] in sus ? intersection(sus[allergens[a]], prod[1]) : prod[1] } } END { do { elim = "" for (i in sus) { split(sus[i], xs) if (length(xs) == 1) { def[i] = sus[i] delete sus[i] elim = elim" "def[i] } } for (i in sus) { sus[i] = difference(sus[i], elim) } } while (length(sus)) for (i in def) { baddies[def[i]] allergens_s = allergens_s" "i } for (i in ingredient_count) { p1res += i in baddies ? 0 : ingredient_count[i] } "echo "allergens_s" | tr ' ' '\n' | sort | tr '\n' ' '" | getline sorted_allergens_s split(sorted_allergens_s, sorted_allergens) for (i = 1; i <= length(sorted_allergens); i++) { p2res = p2res == "" ? def[sorted_allergens[i]] : p2res","def[sorted_allergens[i]] } print p1res print p2res } function intersection(list_a, list_b) { return set_op(list_a, list_b, "int") } function difference(list_a, list_b) { return set_op(list_a, list_b, "diff") } function set_op(list_a, list_b, op) { split(list_a, as); split(list_b, bs) delete ibs; for (x in bs) { ibs[bs[x]] } res = "" for (x in as) { test = (op == "diff" && !(as[x] in ibs)) || (op == "int" && (as[x] in ibs)); if (test) { res = res == "" ? as[x] : res" "as[x] } } return res }

Dag 21

Rekursion i awk Àr inte kul, nÀr mer eller mindre allt hamnar i globalt scope.. Skjuter undan lokal data i en liten stash som jag jag kan ÄterstÀlla nÀr jag kommer tillbaka.

<in awk -v p1=1 -f d22.awk <in awk -f d22.awk

d22.awk

/Player 1/ { reading = 1 } /Player 2/ { reading = 2 } /^[0-9]+$/ && reading == 1 { deck1 = append(deck1, $0) } /^[0-9]+$/ && reading == 2 { deck2 = append(deck2, $0) } function append(deck, card) { return deck == "" ? card : deck" "card } END { winner = play(++tot, deck1, deck2) split(winner, w, "|") split(w[2], cards) for (i = 1; i <= length(cards); i++) { res += cards[i] * (length(cards) - i + 1) } print res } function play(game, deck1, deck2) { do { i = match(deck1, " "); c1 = int(i > 0 ? substr(deck1, 1, i - 1) : deck1); deck1 = i > 0 ? substr(deck1, i + 1) : "" i = match(deck2, " "); c2 = int(i > 0 ? substr(deck2, 1, i - 1) : deck2); deck2 = i > 0 ? substr(deck2, i + 1) : "" if (p1) { winner = c1 > c2 ? 1 : 2 } else { state = game"|"deck1"|"deck2 if (state in memory) { return "1|"deck1 } memory[state] split(deck1, cards1); count1 = length(cards1) split(deck2, cards2); count2 = length(cards2) if (count1 >= c1 && count2 >= c2) { stash_p1[game] = c1; stash_p2[game] = c2; stash_deck1[game] = deck1; stash_deck2[game] = deck2 deck1 = ""; for (i = 1; i <= c1; i++) { deck1 = append(deck1, cards1[i]) } deck2 = ""; for (i = 1; i <= c2; i++) { deck2 = append(deck2, cards2[i]) } winner = play(++tot, deck1, deck2) split(winner, w, "|") winner = w[1] c1 = stash_p1[game]; c2 = stash_p2[game]; deck1 = stash_deck1[game]; deck2 = stash_deck2[game] } else { winner = c1 > c2 ? 1 : 2 } } if (winner == 1) { deck1 = append(deck1, c1) deck1 = append(deck1, c2) } else { deck2 = append(deck2, c2) deck2 = append(deck2, c1) } } while (deck1 != "" && deck2 != "") return deck1 == "" ? "2|"deck2 : "1|"deck1 }

Dag 22
PermalÀnk
Medlem ♄
●
Skrivet av Yoshman:

Skillnaden ligger i hur din kod berÀknar loop_size jÀmfört med t.ex. min Swift-lösning (som anvÀnder reduce).

Med fold/reduce blir det dyrare att berÀkna resultatet ju högre vÀrde man har pÄ loop_size och framförallt blir resultatet O(N^2) om man anropar transform() vid berÀkningen av loop_size

Min Swift-lösning översatt till Rust blir ungefÀr detta (med din indata)

type Num = u64; const CARD_PUB_KEY: Num = 8458505; const DOOR_PUB_KEY: Num = 16050997; const DIVISOR: Num = 20201227; fn transform(subject_number: Num, loop_size: Num) -> Num { (0..loop_size).fold(1, |value, _| (value * subject_number) % DIVISOR) } fn loop_size_calc(pub_key: Num) -> Num { let subject_number: Num = 7; let mut loop_size: Num = 0; let mut value: Num = 1; while value != pub_key { loop_size += 1; value = (value * subject_number) % DIVISOR; } return loop_size; } fn day25(card_pub_key: Num, door_pub_key: Num) { let card_loop_size = loop_size_calc(card_pub_key); let secret_key = transform(door_pub_key, card_loop_size); println!("🌟 Part 1 : {}", secret_key) } fn bench(f: &dyn Fn()) { let start = std::time::Instant::now(); f(); println!("⌚ Took : {}ms", start.elapsed().as_millis()); } fn main() { bench(&||day25(CARD_PUB_KEY, DOOR_PUB_KEY)); }

Denna lösning hittar loop_size pÄ linjÀr tid mot storleken pÄ loop_size. PÄ min 3900X tar ovan 84 ms för att slutföra berÀkningen.

Ändrar man den markerade delen till detta blir det i stĂ€llet O(N^2), orkade inte vĂ€nta till berĂ€kningen blev klar dĂ„ (tar mer Ă€n en minut).

fn loop_size_calc(pub_key: Num) -> Num { let subject_number: Num = 7; let mut loop_size: Num = 0; while transform(subject_number, loop_size) != pub_key { loop_size += 1 } return loop_size; }

Implementerar man istÀllet transform() pÄ det sÀtet du gjort blir den funktionen tillrÀckligt effektiv för att anvÀnda transform() Àven i loop_size_calc(), men ÀndÄ lÄngsammare Àn den iterativa lösningen dÀr man inte alls anvÀnder transform().

PÄ min dator tar din Rust-lösning 1,4s.

Dold text

Jag tror kodblindheten slagit till. (Eller glöggen) Att börja om summeringen för varje "varv" i iteratorn lÄter vÀldigt O(N^2). Det Àr nu man undrar varför man inte ens sÄg det. Det Àr inte ens mycket kod.

Tack Yoshman.

PermalÀnk
Medlem ♄ ★
●
Skrivet av GLaDER:

Hur lÄngt kom du?

Den lilla fritid jag har haft har lagts pÄ annat sÄ att sÀga... jag planerar att göra ett ordentligt försök att ta mig igenom sÄ mycket som möjligt Àven om kalendern Àr "över".

Jag har gjort dag ett...

PermalÀnk
Medlem ★
●

För att dela alla lösningar och fÄ avslut, hÀr Àr min skam för Äret, dag 19. Jag vet inte var det gick snett, men jag gav mer eller mindre upp och försökte mig pÄ brute force med lite cache. NÀr jag ser pÄ andras lösningar tycker jag Àven att jag kÀnner igen mig, att jag provade liknande lösningar, men fick aldrig till det pga prestandabrist. Sen hade jag nÄ ofantliga problem med scope den dagen, att mina variabler skrevs över i andra funktioner eller rekursiva anrop etc etc.. Jag var vÀldigt över det hela pÄ dagens slut.

part1$ <in awk -v p1=1 -f d19.awk part2$ <in awk -f d19.awk

d19.awk

/:/ { split($0, v, ":") num = v[1] rules[num] = substr(v[2], 2) if (!p1 && num == 8) { rules[num] = rules[num]" | 42 8" } if (!p1 && num == 11) { rules[num] = rules[num]" | 42 11 31" } if (rules[num] ~ /[0-9]/) { rule_list[num] = rules[num] } else { terms[num] = substr(rules[num], 2, 1); deal[nxt++] = num } } length($0) == 0 { cur = 0 while (length(deal) > 0) { num = deal[cur] split(terms[num], ts, "|") delete expanded_rules for (rule_num in rule_list) { split(rule_list[rule_num], rs, "|") expanded_rules[rule_num] = expand_rule(rs, ts, num) } delete rule_list for (rule_num in expanded_rules) { if (expanded_rules[rule_num] ~ /[0-9]/) { rule_list[rule_num] = expanded_rules[rule_num] } else { split(expanded_rules[rule_num], new_terms, "|") term_list = "" for (i in new_terms) { split(new_terms[i], xs, " ") term = "" for (x = 1; x <= length(xs); x++) { term = term""xs[x] } term_list = term_list == "" ? term : term_list"|"term } terms[rule_num] = term_list if (rule_num != 8 && rule_num != 11) { deal[nxt++] = rule_num } } } delete deal[cur++] } for (num in terms) { split(terms[num], ts, "|") for (t in ts) { pre_calc[num]; cache[ts[t]" "num] } } } length($0) > 0 && $0 !~ /:/ { if (cached($0, 0)) { result++ } } END { print result } function cached(str, num) { if (num in pre_calc) { return str" "num in cache } return cache[str" "num] = str" "num in cache ? cache[str" "num] : matches(str, num) } function matches(str, num) { if (rules[num] ~ /a|b/) { return rules[num] ~ str } if (rules[num] ~ /\|/) { split(rules[num], subs, "|"); if (match_seq(str, subs[1])) { return 1 } split(rules[num], subs, "|"); if (match_seq(str, subs[2])) { return 1 } } else { if (match_seq(str, rules[num])) { return 1 } } return 0 } function match_seq(str, rule) { split(rule, subs) if (length(subs) == 1) { return cached(str, subs[1]) } else { for (len[str","rule] = 1; len[str","rule] < length(str); len[str","rule]++) { split(rule, subs) if (match_seq(substr(str, 1, len[str","rule]), subs[1])) { split(rule, subs) if (match_seq(substr(str, len[str","rule] + 1, length(str) - len[str","rule]), subs[2]" "subs[3])) { return 1 } } } } return 0 } function expand_rule(rules, terminals, term_num) { new_rules = "" for (x in rules) { split(rules[x], nums) delete slots for (i in nums) { if (nums[i] == term_num) { slots[i] } } split(combinations(terminals, length(slots)), tcs, "|") add = "" if (length(tcs) == 0) { add = rules[x] } else { for (i in tcs) { split(tcs[i], tc) new_rule = ""; k = 0 for (j in nums) { e = j in slots ? tc[++k] : nums[j] new_rule = new_rule == "" ? e : new_rule" "e } add = add == "" ? new_rule : add"|"new_rule } } new_rules = new_rules == "" ? add : new_rules"|"add } return new_rules } function combinations(xs, len) { if (len == 0) { return "" } split(combinations(xs, len - 1), sr, "|") res = "" for (i in xs) { if (length(sr) == 0) { res = res == "" ? xs[i] : res"|"xs[i] } else { for (j in sr) { res = res == "" ? xs[i]" "sr[j] : res"|"xs[i]" "sr[j] } } } return res }

Dold text
PermalÀnk
Medlem ♄
●

Jag och flickvÀnnen började göra advent of code för nÄgra datar sedan,
vi har mest löst uppgifterna i python hitils.
BestÀmde mig för att testa Rust för första gÄngen för lucka 13.
Ni fÄr gÀrna ge mig tips pÄ hur man anvÀnder rust mer effeiktivt.
Standard IO var inte lika lÀtt som IO stream I C++. Det lilla jag
testat av streams och optional hantering var vÀldigt anvdvÀndbart.
Dokumentationen var ocksÄ vÀldigt anvÀndbar med exempel.

use std::io;

fn main() {
let mut input = String::new();
io::stdin().read_line(&mut input).expect("Expected input");
let startTime : u32 = input.trim().parse::<u32>()
.expect("Needs to be a number");
println!("{}",startTime);

io::stdin().read_line(&mut input).expect("Expected another line");
let busses : Vec<u32> = input.split("\n").skip(1)
.next().expect("Needs input").split(',')
.filter_map(|x| match x.parse::<u32>() {
Ok(i) => Some(i),
Err(_) => None,
}
).collect();

println!("{:?}", buss);

let mut results =
busses.iter().map(|bus| match buss % startTime {
0 => (0, bus),
_ =>
((bus * (startTime/bus + 1))-startTime,
bus)
}).collect::<Vec<(u32,&u32)>>();

results.sort_by_key(|b| b.0);

println!("First Buss {} at time {}", results[0].1, results[0].0);
println!("Answer {}", results[0].0 * results[0].1);
}

Dold text
PermalÀnk
Medlem ♄
●
Skrivet av xobust:

Jag och flickvÀnnen började göra advent of code för nÄgra datar sedan,
vi har mest löst uppgifterna i python hitils.
BestÀmde mig för att testa Rust för första gÄngen för lucka 13.
Ni fÄr gÀrna ge mig tips pÄ hur man anvÀnder rust mer effeiktivt.
Standard IO var inte lika lÀtt som IO stream I C++. Det lilla jag
testat av streams och optional hantering var vÀldigt anvdvÀndbart.
Dokumentationen var ocksÄ vÀldigt anvÀndbar med exempel.

use std::io;

fn main() {
let mut input = String::new();
io::stdin().read_line(&mut input).expect("Expected input");
let startTime : u32 = input.trim().parse::<u32>()
.expect("Needs to be a number");
println!("{}",startTime);

io::stdin().read_line(&mut input).expect("Expected another line");
let busses : Vec<u32> = input.split("\n").skip(1)
.next().expect("Needs input").split(',')
.filter_map(|x| match x.parse::<u32>() {
Ok(i) => Some(i),
Err(_) => None,
}
).collect();

println!("{:?}", buss);

let mut results =
busses.iter().map(|bus| match buss % startTime {
0 => (0, bus),
_ =>
((bus * (startTime/bus + 1))-startTime,
bus)
}).collect::<Vec<(u32,&u32)>>();

results.sort_by_key(|b| b.0);

println!("First Buss {} at time {}", results[0].1, results[0].0);
println!("Answer {}", results[0].0 * results[0].1);
}

Dold text

Det Àr absoult inget fel pÄ detta. SjÀlv har jag mest lÀst frÄn filer.
En variant skulle kunna se ut sÄ hÀr med lite smÄjusteringar. Hoppas det hjÀlpte.

use std::io::{self, BufRead}; fn main() -> std::result::Result<(), Box<dyn std::error::Error>> { // LÄs stdin och hÀmta ett buffrat handtag let stdin = io::stdin(); let handtag = stdin.lock(); // HÀmta ut 2 rader let data = handtag .lines() .take(2) .filter_map(|s| s.ok()) .collect::<Vec<_>>(); // Ingen trim behövs. Nyrad redan borttagen frÄn .lines() let start_time = data[0].parse::<u32>()?; println!("Start: {}", start_time); let busses = data[1] .split(',') // AnvÀnd .ok() som konverterar direkt till en Option frÄn ett result. .filter_map(|x| x.parse::<u32>().ok()) .collect::<Vec<u32>>(); println!("{:?}", busses); let mut results = busses .iter() .map(|bus| match bus % start_time { 0 => (0, bus), _ => ((bus * (start_time / bus + 1)) - start_time, bus), }) .collect::<Vec<(u32, &u32)>>(); results.sort_by_key(|b| b.0); println!("First Buss {} at time {}", results[0].1, results[0].0); println!("Answer {}", results[0].0 * results[0].1); Ok(()) }

Dold text