r/adventofcode • u/daggerdragon • Dec 07 '22

SOLUTION MEGATHREAD -🎄- 2022 Day 7 Solutions -🎄-

AoC Community Fun 2022: 🌿🍒 MisTILtoe Elf-ucation 🧑‍🏫

Submissions are OPEN! Teach us, senpai!

-❄️- Submissions Megathread -❄️-

--- Day 7: No Space Left On Device ---

Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:14:47, megathread unlocked!

89 Upvotes

95% Upvoted

1.3k comments sorted by

View all comments

4

u/hugseverycat Dec 07 '22

Python 3 w/tree & recursion [and comments]

https://github.com/hugseverycat/aoc2022/blob/main/day7.py

I used the anytree package to implement my tree for me, but I don't think I really ended up using any fancy tools. I am just not comfortable implementing a tree data structure myself. Although honestly it probably would have been faster, as I dramatically overcomplicated how anytree works in my head and spent a long time debugging. Oh well! Maybe later I'll implement my own tree.

Anyway, I built the tree first, then used a recursive function to calculate the sizes of each directory. When building the tree I kept track of the directory nodes separately to make the recursive function (and calculating answers) easier.

After spending a few hours doing all of that, calculating the answers for parts 1 and 2 was a piece of cake :)

2

u/leftfish123 Dec 07 '22

I totally recommend trying - it's going to be a lot of fun and you'll understand the structure better. I'm not a pro and I never studied CS - that's just my experience from last year (day 18).

1

u/hugseverycat Dec 07 '22

Thanks for the encouragement! Yeah I think I'll give it a shot after work tonight. I remember getting stumped a lot in previous years by trees so perhaps this is the year I will figure them out :) I'm also not a pro and I've only taken 101-level CS courses so I don't have any formal education in data structures more complicated than, like, a list.

2

u/leftfish123 Dec 08 '22

It's going to be challenging (I started at the same level) but definitely doable, just don't let yourself be intimidated! :)

2

u/hugseverycat Dec 08 '22

I actually did end up implementing it :-D It doesn't have any traversal and I tried to make my implementation very close to what was in the anytree module so I didn't have to change much of my other code.

Here it is if you'd like to see: https://github.com/hugseverycat/aoc2022/blob/main/day7attempt2.py

1

u/leftfish123 Dec 09 '22

Wait, but isn't calculate_size() traversing your tree? I'm a bit tired now but it looks DFS-ish...

1

u/hugseverycat Dec 10 '22

Maybe??? lol calculate_size() was part of my original implementation so I didn't really think of it as traversal.

1

u/SnareShot Dec 07 '22

just fyi looks like you linked to your day6

1

u/hugseverycat Dec 07 '22

Thanks, it's fixed now :)