summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-09 22:26:30 -0700
committerJack Sangdahl <[email protected]>2024-12-09 22:26:30 -0700
commitf58fe1976f49eefc8d06b7806e00cfcde2647af4 (patch)
tree064652b51e05f2ea590964e817f0ca762a77ee4e
parent9f021d6971920e37f250ea35c52324436aa1b428 (diff)
downloadaoc-f58fe1976f49eefc8d06b7806e00cfcde2647af4.tar.gz
aoc-f58fe1976f49eefc8d06b7806e00cfcde2647af4.zip
Day 10 2024
-rw-r--r--10_2024.py51
-rw-r--r--data/10_2024.txt57
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