diff options
author | Jack Sangdahl <[email protected]> | 2024-12-09 22:26:30 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-09 22:26:30 -0700 |
commit | f58fe1976f49eefc8d06b7806e00cfcde2647af4 (patch) | |
tree | 064652b51e05f2ea590964e817f0ca762a77ee4e | |
parent | 9f021d6971920e37f250ea35c52324436aa1b428 (diff) | |
download | aoc-f58fe1976f49eefc8d06b7806e00cfcde2647af4.tar.gz aoc-f58fe1976f49eefc8d06b7806e00cfcde2647af4.zip |
Day 10 2024
-rw-r--r-- | 10_2024.py | 51 | ||||
-rw-r--r-- | data/10_2024.txt | 57 |
2 files changed, 108 insertions, 0 deletions
diff --git a/10_2024.py b/10_2024.py new file mode 100644 index 0000000..081c07c --- /dev/null +++ b/10_2024.py @@ -0,0 +1,51 @@ +from collections import deque + +input = "data/10_2024.txt" +data = open(input).read().strip() +lines = data.split("\n") +lines = [[int(x) for x in row] for row in lines] +rows, cols = len(lines), len(lines[0]) +p1, p2, dp = 0, 0, {} + + +def ways0(sr, sc): + q = deque([(sr, sc)]) + res, vis = 0, set() + while q: + r, c = q.popleft() + if (r, c) in vis: + continue + vis.add((r, c)) + if lines[r][c] == 0: + res += 1 + for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]: + rr = r + dr + cc = c + dc + if 0 <= rr < rows and 0 <= cc < cols and lines[rr][cc] == lines[r][c] - 1: + q.append((rr, cc)) + return res + + +def ways1(r, c): + if lines[r][c] == 0: + return 1 + if (r, c) in dp: + return dp[(r, c)] + res = 0 + for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]: + rr = r + dr + cc = c + dc + if 0 <= rr < rows and 0 <= cc < cols and lines[rr][cc] == lines[r][c] - 1: + res += ways1(rr, cc) + dp[(r, c)] = res + return res + + +for r in range(rows): + for c in range(cols): + if lines[r][c] == 9: + p1 += ways0(r, c) + p2 += ways1(r, c) + +print(p1) +print(p2) diff --git a/data/10_2024.txt b/data/10_2024.txt new file mode 100644 index 0000000..06fa313 --- /dev/null +++ b/data/10_2024.txt @@ -0,0 +1,57 @@ +321021092121234789832103214321006541010132106541017654300 +438934783010345676543345305453217432187233477832018980211 +567015654501296489410256456569348945096544986910129871232 +456723123456987334320107567678758996898555678901236789543 +309854010987106212430198438734367987567456967432545210692 +219764110899234302341234329765210803456327876545694356781 +078743211898765671296541017891010712987818760176783543490 +165430302345610980387652132169125621076909859285432892101 +234321459654324341455678923078434018565012348396501783030 +965078968767865210564543014568742109410983467487645654121 +870165678654978109634332125989653478321474326576546553239 +743234589623089238723765223678764569436565015961038764548 +658921056712109841014894014569655234587652103876129855697 +067876549803458958965023789012345105698501212365012342786 +149989034104567567874112632101437656787432323453210031245 +238701123234789810983201543654328941095467654534509120430 +345632010345654321012317123788911032876338943210678921221 +765643101234983498765498014697802123943223458901098834569 +894356909875676543034567765656543112310110567812347721678 +018247812365889832103077896578987003451541476905456430549 +329106321458981018212186987107832128765434985876965501232 +478905450123472789567095011016541289892125676767874610541 +565210567012563665498144322123450156701010065367823789670 +984303498781014572301238983210761043214012153456910432987 +676542187692125981019345674529832980123723472347234561098 +701410096583455850128543265678745679654874781298100678121 +892323823496566767817610121060123498765965690107321789030 +765214910787665016901001438901298567543876212346496576543 +564305807879854325012312567652347345672104301454587432656 +678986706987763434325493498743656256783265420963678101765 +367210215432102521456786781234562101894378510872539819834 +456520344895601610569035690105678980123459826761223422123 +307431456784778700678124303234983456234389439870314565012 +218942349823869891233298212104572367945476512365409874303 +354654332210958398544567198703671398876532403456589701234 +763783041032141237653211003612980432345641123969676510145 +892892156543030340344509112501876521898750014878105430656 +321891067674321651225678783432985010456767625565254321787 +100765018789810787810589698343274981347898766984369930896 +235654329878910896923410587650123876210184567874378876787 +346543012897601235210401456871014985011543498965210765498 +457892126780540344323302345921001234327612321070178780301 +569234045601239653014212234834912321098501078789869691212 +678105030430548732012323100765873434323456539834054587101 +767876121521696671021234561234564565210766545743123456078 +878987437601787787430965876501259678703897832652012167569 +989096598912321096566876903412348789612345991001765078438 +870110182105431234565678912089987432541016787569894369327 +963223273676980017874987652176506501232346765456701254310 +854134564587832156983676543005218765101239894301012563210 +343065432196347847892565034114309450120340123219823472121 +212876701098256930101656123423212301239658921008768989032 +108989870187107821234587630123498418948767830119657812398 +017129871256766210187696541454567699859656543234546903457 +210034560345897654098543076501298788768501765401445498766 +325676894324388943089432185432107632103432852332332320125 +434589765410210012176501898543234543214345901021041010134 |