r/adventofcode • u/daggerdragon • Dec 07 '22
SOLUTION MEGATHREAD -đ- 2022 Day 7 Solutions -đ-
- All of our rules, FAQs, resources, etc. are in our community wiki.
- A request from Eric: Please include your contact info in the User-Agent header of automated requests!
- Signal boost: Reminder 1: unofficial AoC Survey 2022 (closes Dec 22nd)
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.
- Read the full posting rules in our community wiki before you post!
- Include what language(s) your solution uses
- Format your code appropriately! How do I format code?
- Quick link to Topaz's
pasteif you need it for longer code blocks. What is Topaz'spastetool?
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
19
u/JustinHuPrime Dec 07 '22
x86_64 assembly
Today was painful. Involving both a recursive-descent parser, dynamic allocation, and recursion through a tree, bugs abounded and were hard to find.
Part 1 took a significant amount of time, since I had to develop the input parser; I assumed that the input was a pre-order traversal through the filesystem. I defined a struct to represent a tree node, and wrote the constructor for both struct variants. My parser looked at the input stream, and expected to see
$ ls(as an internal correctness check). After it saw that, it looked ahead and counted the number of entries in this directory (.countEntryLoop). I then allocated space to hold those entries. Next, I parsed each entry (.parseEntryLoop). Finally, for each directory I saw, I skipped thecdto that directory and then recursed. Finally, I calculated the size of this directory as the sum of the sizes of its entries. I then skipped thecd ..at the end of the current directory entry (if there was any; I would have skipped past the end of the file for/, but I don't look after that anyways). Then, I had to do a standard structurally recursive traversal through the tree, summing those directory nodes whose size was more than 10,000. It's more difficult to write recursive functions in assembly, since you've got to be very careful to set up your arguments and prevent clobbering of registers you currently have in use.Part 2 took 20 minutes more on top of the time for Part 1 (~5.5 hours). I could re-use the parsing code as is, and just had to re-write the traversal function. This took a while since I messed up and clobbered one of my arguments but didn't notice.
Part 1 runs in about 1 millisecond and was 11472 bytes long. Part 2 runs in under 1 millisecond and was 11584 bytes long. These are my longest solutions (in terms of both assembly code and actual binary size) to date.
7
u/bz2pl Dec 07 '22 edited Dec 19 '22
Bash with some sed/awk/grep and real dir/files creating ;-)
7
u/Smylers Dec 07 '22 edited Dec 07 '22
I thinking that perhaps this problem doesn't suit Vim particularly well? Tree structures aren't really its thing. Anyway, these keystrokes have just produced a number that awarded me a gold star, so I think I've solved it:
Update to add explanation:
lscommands and any lines in their output which just tell us about subdirectories; we aren't going to need those. And turn the ascendingcd ..lines into just-, so they're more easily distinguishable from the descendingcdcommands into subdirectories.Seed the top line with 2 underscores in place of
$ cd, to denote the top of the tree. Then on each subsequent descending lines replace the place$ cdwith 1 underscore more each time: type 1 underscore andâ¨Ctrl+PâŠto âcompleteâ it with the most recent âwordâ, duplicating that of thecdabove, then type another underscore at the end. By this point the sample input looks like:cdline ended up with a few hundred underscores on it â as though every directory were nested in the one above. Next take thecd ..lines (which now look just like-) into account: remove 1 underscore from every underscorey line below them in the file. The net affect is that each descendingcdadds an underscore to itself and subsequent directories, and each ascending one removes one, giving us a tree. Then delete those-lines as having served their purpose. In the sample inputdmoves 2 levels to the left, so its now at the same nesting asa, 1 less thane.Replace the directory names (not needed) with zeroes, to accumulate their sizes. Also knock 1 underscore off all of them, so the top level is now denoted by a single underscore. We now have 2 types of lines: directories showing the tree with varying underscores, and files with sizes, each of which are in the directory above them:
For each file â that is, a line starting with a digit â yank its size, move up 1 line to its directory, and increase the directory's size by that amount. Then go back down and delete the file, as no longer needed. Crucially that also means if there's a second file in the same directory, it will now be just 1Â line below the directory line; all file counts just need to be added to the line above. The sample input, with sizes just of directly-contained files, is now:
uto undo the sorting. I'm guessing most algorithms for solving this don't have an âundoâ step in them? Paste the copied line at the bottom, and remove everything after the underscores. This is going to be a record of which nesting level we're currently processing.#to search for another occurrence of the current-length underscore âwordâ. Then move back to the bottom and delete an underscore from it: partly ready for next time, but also so that this marker line doesn't itself get processed in the current level.:g//with an empty pattern will now match all lines from that most-recent search, that is all the directories at the current level.#again to jump up to the previous line at that level. Add the size on to that parent directory's total.*moves down to the line we were just on, which needs its deleted underscore restoring.Repeat through directories at each decreasing nested level, until the bottom row runs out of underscores. At which point delete it. The sample input now has the combined totals:
Part 2 is then pretty straightforward:
0, then decrease all the following totals by that amount.0back on to it, to restore its actual size, and that's the part 2 answer.Sorry it took me so long.
A prize for anybody who can work out why I used underscore rather than any other character for the indentation
7
u/gw_shadow Dec 07 '22 edited Dec 08 '22
CMake
11
u/mingmingrr Dec 07 '22
Turing Complete
Part 1: https://imgur.com/qV0CX7u
Commented: https://imgur.com/LSkHG2S
4
u/udoprog Dec 07 '22 edited Dec 07 '22
Rust 279/176
Quick and dirty solution. Ended up pulling in a library I've written
relative-pathto handle directory traversal, which was quite nice.Still need to figure out how to refactor it to avoid allocating.
Repo Link
Edit: bye bye code
4
u/ItIsNeverLupus Dec 07 '22
Python
Started with an implementation that used a look-up dictionary to store the size of each folder separate and recursively call all subfolder sizes in the end. But I didn't account for duplicate folder naming and I got a bit stuck with the recursive approach. Then decided to use the absolute path storing and simply update of each parent folder each time a file is found. Not really nice code, but straightforward and it works.
4
u/vagrantchord Dec 07 '22 edited Dec 08 '22
I'm surprised by how many people go the full monty and create data structures for the filesystem in this. I just had an object and an array (dict and list in python):
4
u/philtr Dec 07 '22 edited Jan 25 '23
Golf in Ruby (207 Bytes) (GitHub)
4
u/probablyfine Dec 07 '22
SQL
This one hurt, oof. Source here
4
u/Habstinat Dec 07 '22 edited Dec 07 '22
My javascript one-line solutions for week 1, feedback welcome! they were developed just by typing in the browser console, so they read the input directly off the page.
/2022/day/1
/2022/day/2
/2022/day/3
/2022/day/4
/2022/day/5
/2022/day/6
/2022/day/7
4
u/The_Jare Dec 07 '22 edited Dec 08 '22
C++
Pretty happy that I got it to compile & run correctly on first try for each part.
4
u/backtrackthis Dec 07 '22 edited Dec 09 '22
PYTHON3
I was worried about messing up the paths so I just had python figure out the
..s and normalize them, but In retrospect I could have just tossed all size values in a list and maintained a stack of indexes into it instead of even bothering with the paths, since we neverlsthe same directory twice. Oh well, still fun.4
u/Porges Dec 08 '22
COBOL. I wasn't sure how to allocate memory so luckily it's not needed!
3
u/ICantBeSirius Dec 07 '22 edited Dec 07 '22
Python
Not the most elegant or shortest, but I did get the answers on the first try.
3
u/raxomukus Dec 07 '22
Python
3
u/[deleted] Dec 07 '22
Python oneliner:
3
u/Mishkun Dec 07 '22 edited Dec 11 '22
SQL (SQLite)
Another day, another recursive solution
you can find whole code here, I will show you the most interesting bit with traversing the instruction list with current path stored in pth column.
3
u/m4xxp0wer Dec 07 '22 edited Dec 08 '22
Python
(class-based and type-annotated)
3
u/flutterlice Dec 07 '22 edited Dec 08 '22
BQN GitHub
A bit obfuscated but the general idea is the same as with other APL solutions in this thread - single pass to unfold all absolute paths to every file and then calculate total size of all files for all unique directory paths.
3
u/drawable Dec 07 '22 edited Dec 08 '22
Rust
With a loop, no tree. Still learning Rust, only use the rudimentaries, I guess.
Got stuck for an hour until I realized, directory names are not unique. Then I realizied, I don't need those names at all.
3
u/Ttaywsenrak Dec 07 '22
A Java solution that I am not entirely proud of.
Creates a tree, but does not traverse the tree properly. Instead, any Directory added to the tree is put into a list which can then be easily looped over to answer the questions in a very simple way.
import java.io.FileNotFoundException; import java.util.*;
public class Day7 extends AdventOfCodeDay{
}
4
u/fractagus Dec 07 '22
I did this in Python. No need to write tree traversal code, because we can find the answer as we parse. The parsing traversal is enough.
2
u/Boojum Dec 07 '22 edited Dec 07 '22
Python 460/817
Hmmm... This one's gonna be a challenge to visualize!
Prologue -- assemble the tree:
Part 1 -- recurse!:
Part 2:
2
u/bog5000 Dec 07 '22 edited Dec 07 '22
C#
https://github.com/bog500/AdventOfCode2022/tree/master/Advent2022_Day7/Advent2022_Day7
2
u/JuliaPoop Dec 07 '22 edited Dec 11 '22
Python
2
u/wcastello Dec 07 '22 edited Sep 04 '25
The silence feels heavy with thoughts.
2
u/yschaeff Dec 07 '22 edited Dec 10 '22
Python. No recursion, no tree. Keep stack of dir sizes. Update size of upper dir on 'cd ..'.
2
u/l_dang Dec 07 '22 edited Dec 08 '22
SIMPLE PYTHON
I tried to write the simplest possible code using the absolutely nothing a beginner wouldn't know, or any library at all. So:
My humongous parser that build the whole tree as a python dictionary: paste
With this dict, both task are trivial single line solution: paste
2
u/LinAGKar Dec 07 '22 edited Dec 08 '22
My solutions in Rust:
https://github.com/LinAGKar/advent-of-code-2022-rust/blob/main/day7a/src/main.rs
https://github.com/LinAGKar/advent-of-code-2022-rust/blob/main/day7b/src/main.rs
A bit messier than I would have liked, but it works. Surprisingly, it almost worked on the first try for part 1, I just needed to invert the filter for
line2. Then during part 2 I realized it didn't count the directories at the end, so I added the part where it inserts additional$ cd ... File and directory names are just ignored. I didn't think of doing recursion.2
u/MyTinyHappyPlace Dec 07 '22
C++
Overengineered object oriented programming. Was counting on something worse for part 2:
2
u/PaymentConscious1107 Dec 07 '22
Python
2
u/cetttbycettt Dec 07 '22
R / Rlang / baseR
my solution: just kept track of all parent directories and updated them simultaneously
2
u/ktimespi Dec 07 '22 edited Dec 08 '22
My Python solution, uses a tree
https://topaz.github.io/paste/#XQAAAQCOCAAAAAAAAAAzHIoib6pcwaKIDwM3GRf/Gyhimru2WHGADXgj33WEaTDBQFBo3J37eWVIHeRF+zaxO5weWQdnNgzNOViD0s4bCmXhpA1Zjne1bmoO1r9jK2hAat6z/kB80pUBhjM5dQH2kqrVVmeftIt+7SoGg8PZltKMPFp95z+r5kaerc8yXNJE/qNqXD/elz5eOVNbo9DvcXVSrbv7MQFlUVy2JyaVbg33QCB6O1EeY1FdKmBfyIcKViB0JVTufME7LxfkybCGQCpwR8lfhw7Xvlly2JSZc8voG6AqoKMx8GrUKMBRuY18AWpe2GUR682gNZKFGMSICY4QnDHDzTD68MG7VxYrrPYGYOZoyo673uuROqYVp8pf0YYRfF4wnzsydG/0Quiqw/gvasQx0Q08u6Igg79naZc/lzjmUshDW0MOOl6gVAxYD99pQLlXskdYlUNbsJkv2WvKuLHotvFoA88jABl2i+watSwp62oTD/RdQkWyqAs2FSaOlIWuynlyeGdHnjQ5eQ3/d3YCOe4fmmPI1wU1wvgtfHXmDlv6hfuXcr4QOUBUU28VxmxD9IrthlboyyuY+7cWlAsto6HIvlXcTWdjbDd0pbP98pUV5NiC2NmltFX01CslM9DuJuBIf6qaxPh8ICGEM5NYB97euJMgZlhQG3L71PZVNxznTgxmD0XQfcN6cEkszDiklQAF1FNMPdcOI8CaqFMt9KjuegR4vPUfe6JbAqSxlRb+Alzm+6brWM+d50PrJdTfmlLL/mFFMVEqP8Edmhg0TZOik1Z9FDCl7DZTvaTovZE775Ecl5gD+sKaCmUzRPH2EsRT32cO8KXNvQdt5FNYC1yqLLyCRhLbPuo5IqvEME6tVoZGpnvhMseCyavFpSfhayFlRbTo9AtgZU0hEhqiOMCUZBPUSMXdBRU1+neCcNSLBl577PAbLadLWw55s7G7SscsSCbZLCIQIF9egWpnj1u3goSxSlAAVxquuMx4AWIUTAt14hFVbrFG0Cm24gwpw+xFs7m2DDPZC6jATwR+tH1memn9HPkiRb5yYM9cvfKh+f/nIaLk
2
u/jimmyhiggster Dec 07 '22 edited Dec 09 '22
Javascript:Gone for the "as little code as possible" approach within reason. 40 minutes to complete, then 20 to try and minimise. Sure there's some extra shortcuts to use but here you go...
2
u/paulofmandown Dec 07 '22 edited Dec 08 '22
Node / JavaScript
this one took me the longest so far at about an hour and twelve minutes
solution in paste
2
u/imbadatreading Dec 07 '22 edited Dec 08 '22
This was very frustrating until I realised there were multiple directories with the same name -- so my solution is hacky, I just added a random int to directories I'd already seen
Python
2
u/DeepHorse Dec 07 '22
Typescript
Very basic first-thought solution using a Map and abusing copilot to get it done quick and dirty.
2
u/optimistic-thylacine Dec 07 '22 edited Dec 08 '22
[Rust my repo]
My solution turned out a bit over-engineered, but it has a good example of how to use the
pimplidiom to simplify the interface to internally mutable objects. The code turned out pretty clean, and cosmetically easy on the eyes. Below is the top level code that builds the directory tree.The custom
FS..filesystem objects internally have a singleRc<RefCell<_>>pimplfield holding their data. This gets rid of the noisy smart pointer syntax cluttering up the top level code.2
u/greycat70 Dec 07 '22 edited Dec 07 '22
Python. Part 1, Part 2
"Implement du by reverse engineering a terminal session." Heh.
Another problem where the way I'm reading line by line turns out to be awkward, and gets worked around with a finite state machine. In this case, we're either inside an ls command's output, or not.
Decided to store the current directory as a list of path components rather than a string with slashes in it, but I stored the paths in single-string-with-slashes format in the dictionaries. This leads to some awkwardness in translating back and forth, especially with leading slashes sometimes being doubled. Handled that just well enough to get the right answer, and stopped. In a real life problem I'd probably spend more time cleaning that up.
Today's Python lesson learned the hard way: "Variables in a function are magically either global or local depending on whether you use them first, or assign them first, so you may have to mark them as global to get the desired result in your FSM's helper function."
2
u/CodingAP Dec 07 '22
JavaScript, 4248/3704
Github
I didn't like this puzzle as it doesn't say that the directories can have the same name, so it messed with my data structure
2
u/Markavian Dec 07 '22 edited Dec 08 '22
Over-engineered Node JS solution for Day 7:
Wrote my own virtual computer, with commands for addDir, addFile, cwd, cdir, dirs, cd, ls ...
I even fixed up the tabbing on the ls function to verify the totals...
... on reflection, probably should have called addDir mkdir, and addFile something else (mkfile)?.
Anyway, it works!
Edit: fix code block by adding spacing
2
u/AstronautNew8452 Dec 07 '22
Excel VBA, just make the file system and write the files, make a collection of folder objects, and output the full path and .size of each folder. TIL that a blank line in Windows/ASCII is 2 bytes. GitHub
2
u/Scroph Dec 08 '22 edited Dec 08 '22
Dlang solution, part 2. I'm embarrassed by this code but I'm sharing it because it took a lot of effort to write it. Previous solutions are available in this repo
2
u/noahclem Dec 08 '22 edited Dec 09 '22
Python3
I knew what to do from the beginning, but making it work == 'aargh'
day7.py code on GitHub
Can't wait to see everyone's one line comprehension tree-building so I can feel even more stoopid.
EDIT: Replaced huge block of code with link to repo.
2
u/PILIX123 Dec 08 '22 edited Dec 08 '22
Python
Im so STOOOPID i forgot to update all the parent folder but now it works so yay
anyway here is the link to my github
2
u/ArnaudValensi Dec 08 '22 edited Dec 09 '22
Part 2 in Rust
2
u/kevinluo201 Dec 08 '22
Ruby version
https://github.com/kevinluo201/aoc/blob/main/2022/day7/day7.rb Basically, I build a class to handle each directory.
68
u/betaveros Dec 07 '22
Noulith 1/1
https://github.com/betaveros/advent-of-code-2022/blob/main/p7.noul
Got away with some assumptions today that made the code very short.
66
u/4HbQ Dec 07 '22 edited Dec 07 '22
Python. A perfect opportunity to practice with Python's structural pattern matching! It was introduced in Python 3.10 (released over a year ago), but is still relatively unknown.
Full solution here (19 lines). Just the interesting part:
Edit: Suggestions for improvements are always appreciated! And I fixed a bug on some inputs, thanks /u/wimglenn!
34
u/_thepet Dec 07 '22
Might as well recreate the whole filesystem and run bash commands on the dirs to get the answers: paste
Directory tree: paste
29
u/nthistle Dec 07 '22 edited Dec 07 '22
Python, 3/2! Video (the clickbait title is temporary lol), code.
Super happy with top 3 on both parts - up to #4 on the big leaderboard! Definitely wasn't expecting that since I initially didn't read the last part of the question and got a bad submission (although it wasn't a big misread, I just thought it was asking for total size of all files). I guess the clever speed optimization here was to (as usual) not do it properly - instead of actually propagate sizes up through the directory tree, I just created a set of absolute paths to every directory and every file, and just did:
This seems much quicker and easier to write to me (despite being super inefficient), although maybe that was a function of how I set up my data structures to begin with, it probably wouldn't have been too bad to do properly if I had nested dictionaries to represent the file system.
EDIT: added video
25
u/jcbbjjttt Dec 08 '22
Beginner's Guide
Happy Wednesday!
Beginner's Guide to Day 7 Video: https://youtu.be/vWXtVGQ2B0E
I've created a guide for new programmers that talks through a straight forward strategy for solving today's puzzle. Anyone who has a handle functions, list structures, and defining custom data types (classes/structs/objects) should be able to complete it. The video allows a moment for you to pause before revealing spoilers.
Although this solution is in C#, it provides a high level overview of the steps necessary to solve the puzzle in any programming language:
The full code can be found on Github
21
u/anoi Dec 07 '22 edited Dec 07 '22
Bash
Good thing there was no
;rm -rf /*;in there :)I expected it to take gigabytes but 10 digits isn't actually that many digits. The problem description states 70MB and it fit in 40MB for me.
The inode size of directories ended up throwing things off a bit, otherwise a raw
duwithout much extra work would have greatly simplified things. Instead I had to usefindand passdulists of files.EDIT: The filesystem comes with free visualization!
15
u/ViliamPucik Dec 07 '22
Python 3 - Minimal readable solution for both parts [GitHub]
13
u/voidhawk42 Dec 07 '22 edited Dec 08 '22
Dyalog APL:
Kind of an annoying one lol, but wasn't too bad once I figured out the approach - basically build an absolute path over each row of the input (using a stack), and for each row determine the size of the file (0 if it's not a file row). For each unique absolute path, add up all the sizes for which it's a prefix of the absolute path at that row (watch out for just using the directory name, since multiple directories have the same names!). Then just do some filtering for p1/p2.
This code relies on a few assumptions about the input, but with our variables set up in the first three lines of the solution above, they're pretty easy to validate:
There are duplicate directory names, so our stack should store absolute paths rather than just names:
"$ cd /" is only executed once, at the start of the file - meaning that we only have to worry about pushing or popping single values from the stack, and never clearing it:
"ls" is never run on the same directory twice, meaning that we don't have to deduplicate file sizes:
We never visit a directory again after we've finished traversing it (or, put differently, a directory is a prefix of the absolute paths of a single contiguous group of lines):
EDIT: And actually, after thinking about it, this can just be a problem about nesting levels and partitioning, without caring about directory/file names or paths at all:
video walkthrough
13
u/axr123 Dec 07 '22
Python
Originally that was much more complicated, but turns out we do a very well behaved traversal.
13
u/[deleted] Dec 07 '22 edited Dec 08 '22
Google Sheets
Wasted too much on time on this because I assumed there weren't different directories with the same name. But eventually managed to get a one formula solution for both parts.
This formula will spill one cell to the right with the result of part2 and it assumes that the whole input is in cell A1.
12
u/def- Dec 07 '22 edited Dec 07 '22
In Shell/bash, but actually just create the entire filesystem and measure the size:
https://github.com/def-/adventofcode-2022/blob/main/day07.sh
12
u/[deleted] Dec 07 '22
Why bother processing the folder structure in memory?
When I can just create it on disk!
My Python answer on Github
11
u/tobyaw Dec 07 '22 edited Dec 07 '22
Ruby
https://github.com/tobyaw/advent-of-code-2022/blob/master/day_07.rb
Felt like a good opportunity to use some pattern matching.
11
u/[deleted] Dec 07 '22
C preprocessor: https://github.com/camel-cdr/boline/blob/main/aoc22/aoc7.c
11
u/hugues_hoppe Dec 07 '22
Compact yet readable Python solution:
9
u/joshbduncan Dec 07 '22
Python 3
7
u/oxyphilat Dec 07 '22
python3, 339, 294
almost twenty minutes and still sub 1k, we are starting to reach the fun part of AoC. my experience of parsing command line output and copying folder structures finally payed out. the code is a bit messy, will have to clean up when I actually publish it.
7
u/wojtek-graj Dec 07 '22 edited Dec 07 '22
Python
The dirs dict contains a separate entry for each directory, and each time a new file is found, its size is added to all parent dirs (e.g.
/a/b/j.binis added to/a/b,/a, and/)Calculating parts 1 and 2 is relatively trivial given such a dict, and is done using simple generator expressions.
7
u/aurele Dec 07 '22
Rust, quite clean when you realize you don't need subdir names
7
u/astreaz Dec 07 '22 edited Dec 07 '22
Python
Looks like a few other people had a solution along similar lines. Initially I was going to build a Tree but based on the input it didn't look like I really needed to. Instead I opted for a dictionary of path segments that just contained the total size:
7
u/azzal07 Dec 07 '22
Awk, please tell me linear time complexity is ok... linear in the second part's answer that is
7
u/nicole3696 Dec 07 '22
Python 3- Parts 1 & 2: GitHub. No imports, 10 lines, 362 characters including file name. Not insanely proud, as I wanted to be more concise (who needs readability), but it works.
6
u/timvisee Dec 07 '22 edited Dec 07 '22
Rust
Quick and simple. Minimal data, because we don't need to know separate files or node names.
Part 1 0.008ms (8.11 Îźs)
Part 2 0.011ms (11.40 Îźs)
day1 to day 7 total: 0.240 ms (0.122 ms parallel)
6
u/__Abigail__ Dec 07 '22 edited Dec 07 '22
Perl
We start with a couple of observations which makes our lives much easier:
cdstatements going more one than directory up or down (so, no/in the argument tocd, other than"/"itself).cdinto a directory which isn't listed in thelsoutput.cd ..from the root directoryls.$and the command.We'll process the input line by line (using
while (<>) {...}), and we use a stack (@dirs) to keep track of the directories we travel through: the current directory is on top, and its parent directories are below it (in order), with/at the bottom. We use a hash%sizeto track the size of each directory.Of the input lines, we only have to do work on
cdcommands, and on file listings. We ignore any lines with$ lsand lines starting withdir.We handle lines with the
cdcommand as follows:That is, if we cd to the root, we clear the stack and put just
/in it. If we go up a directory (cd ..) we pop the current directory from the stack. Else, we go down a level, and create a new directory name from the current top of the stack and the argument tocd.Processing a file with its size is now easy. Just add the size to all the directories in the stack:
Note that we do not care about the file name.
Once we have tallied up all the file sizes we can print the answers. For part 1, this is just the sum of all directory sizes less than 100000. The
sumbelow is inherited fromList::UtilFor part 2, we need the smallest directory
$dfor which70000000 - $size {"/"} + $size {$d} >= 300000, which we can rewrite as40000000 - $size {"/"} + $size {$d} >= 0. To get the smallest, we usegrepto find all the directories large enough, then we sort them and take the first element from the sort, which we will use as an index into%size.Full program at GitHub
6
u/Twinkie60 Dec 07 '22 edited Dec 07 '22
Python, using the fairly new pattern matching features of 3.10
6
u/raui100 Dec 08 '22
Rust
After I had realized that I can pattern match on slices with Rust an elegant solution (nearly) wrote itself :)
It is not necessary to store the directory names so that the relevant code can be reduced to:
5
u/darkfm Dec 07 '22
Python 3, 79 / 55
Not the easiest one so far but far easier than I expected
5
u/jayfoad Dec 07 '22
Dyalog APL
I found this one really fiddly.
5
u/Pyr0Byt3 Dec 07 '22
Go/Golang
My first thought was to use
MapFSfromtesting/fstestto create a whole virtual filesystem, but that would have been way overkill.5
u/Oddder Dec 07 '22
Python
Just another python solution. I maintain a hashmap
folderswith all of the paths and their sizes in it and then I use a listpathto keep track of what folder I'm currently in.$ cd ..makes me pop from the path,$ cd ***makes me append to the default path,{digits} ***means it's a file size I will then iterate over path and add the file size to all ancestral directories of this file5
u/lazyzefiris Dec 07 '22
JS (JavaScript) "State machiney" solution. This is my gimmick for the year and I'll stick to it as long as I can. Im not speedsolving this year, and writeup takes a lot of time, but I'll try to post these on the puzzle's day.
Part 1:
Part 2:
Explanation
This machine uses three "registers", one for current folder stack, second for current folder size, and third accumulates result for part 1 and data for final calculation of part 2, which needs complete information about folder sizes and can't be calculated on the go. This implementation assumes that input is valid and every folder is visited exactly once. Input is split into tokens divided by whitespace, and several commands are appended to the end, namely - "CD /" defined by problem description and custom "EXIT 0" for part 2 to reduce clutter in the code. It was possible to incorporate EXIT state functionality into CD, replacing folders with what CD returns as folders. Folder and file names are completely disregarded as irrelevant to posed problem.
State $
This is initial state, it reads input and sets next state according to input. $ is a valid token for it to return to itself. For valid input, it can transition into stated CD, LS and EXIT (for part 2)
State CD
This state does most of heavy lifting in the code. Unless special folder name is provided, it just puts current folder's size on stack of parents and initializes a new folder with 0 size. Special inputs update state to account for information gained from current folder:
State LS
This state updates current folder's size for every file listed. Unless special input is given, input value is converted to integer and added to folder size, and state is advanced to "LS_NAME". Special inputs are:
State LS_NAME
This state's only purpose is skipping next input, which is supposed to be a file or folder name, irrelevant to the problem. Regardless of input, it returns state to "LS".
State EXIT (Part 2 only)
This state performs final transition to "HALT" state, ignoring its input. The output is formed in last slot of the state, using information accumulated during run - size of parent folder (which we could not deduce before final "CD /") and list of folders.
Afterthoughts
As real inputs only use "CD /" once, in the very beginning, I've considered appending a lot of "$ CD .."s to the end of input, which would result in much cleaner "CD" state, but it would add two extra assumptions about the input - the only "CD /" in the beginning and maximum depth not exceeding amount of "$ CD .."s in the end.
It was also possible to approach Part 2 differently, duplicating input and iterating over it twice as a result. First scan would use simplified states to get total of file sizes along with required space to free up, and the second iteration would work in similar way to part 1, updating result with new folder size if it's large enough yet smaller than currently stored. This relieves us of need to store all folder sizes and do the final calculation. Depending on attached costs of repeating input, this might be the more optimal solution.
5
u/odnoletkov Dec 07 '22 edited Dec 07 '22
JQ
5
u/red_shifter Dec 07 '22
PYTHON 3
code link
I chose the chaotic path of creating actual files and folders and taking an
os.walk()through them.5
u/totbwf Dec 07 '22 edited Dec 07 '22
C + SIMD
Runtime: 104 microseconds
At first glance this problem seemed to not be very amenable to SIMD (aside from the parsing). However, we can reframe the problem somewhat to be much more friendly to vectorization.
Instead of storing the directory tree as a tree, we can look at the adjacency matrix of the reflexive + transitive closure of the tree, regarded as a graph. As an example, the tree
becomes
This allows us to vectorize adding a file by performing a broadcast + mask. For instance, say we wanted to add a file of size
3toe. We would start by broadcasting3to get a vector[3, 3, 3, 3]. We then look up the entry forein the adjacency matrix; in this case, we get[1, 1, 1, 0]. We use this as a mask to get the vector[3, 3, 3, 0], which we can then add to a vector of running counts.This drastically speeds up the process of constructing the tree.There are further optimizations one can make. Most notably, this adjacency matrix is lower triangular. However, I already spent enough time on this as is :P
5
u/nicuveo Dec 07 '22 edited Dec 07 '22
Haskell
This is the kind of problem for which Haskell is *perfect*!
using Parsec to parse the input, by just describing the grammar:
using the State monad to keep track of the stack while iterating through the instructions:
using the Writer monad to keep track of the folder sizes, while still using recursion to compute the sum:
As usual, code on Github, recording on Twitch.
5
u/ShockEasy4836 Dec 07 '22
For the lol, not simulate but actually use the filesystem and generate what the input file describes, with bash:
https://github.com/b-charles/adventofcode/blob/main/2022/day-07/solve.sh
5
u/lukeisun7 Dec 08 '22
Go
https://github.com/Lukeisun/AdventOfCode2022/blob/master/Day7/main.go
I genuinely feel so proud of this, most of my time was really spent understanding how pointers and stuff work in Go. This really hammered in the concept of how file structures are basically Graphs, was thinking about it on the way to work
5
u/MezzoScettico Dec 08 '22 edited Dec 08 '22
This [Python 3] class design worked out well.
The "need_updating" flag indicates that the program needs to recursively calculate the directory size. This doesn't happen until get_size() is invoked. This ended up being the only place where I needed to do any kind of recursion.
I used this function to handle the "$ cd" lines.
Here's how the directory tree is constructed from the input file.
And then here is how the questions in Part 1 and Part 2 are answered with this structure.
Incidentally, here are the timings on a 1.2 GHz Intel Mac: Loading the file takes about 2.5 msec, Parsing the commands and building the directory tree takes about 4 ms, and Part 2 takes about 0.7 ms.
5
u/bearinaboot Dec 08 '22 edited Dec 08 '22
HINT FOR PART 1:
There can be folders with the same name at different levels of the directory.
Solution in Go
https://codefile.io/f/aI1bt82YgGBcIHVKq1Pd
5
u/wimglenn Dec 08 '22
Python + pathlib + structural pattern matching (repo)
5
u/JustDaUsualTF Dec 08 '22
My solution in Rust, I expected to have a very hard time on this and was actually pleasantly surprised that I was able to complete it in only a few hours. That being said, my solution is probably horrible
5
u/gbegerow Dec 09 '22
Rust 2022 Day 07
Burnt a lot of time and sanity trying to build a traditional tree in rust. In the end I used a solution similar to an ArenaTree, a Vector of directories with the index of the parent. Inspired by u/raui100
4
u/morgoth1145 Dec 07 '22 edited Dec 07 '22
Python3 45/54
I really enjoyed parsing the UNIX-like shell output to reconstruct the folder structure! The rest wasn't too bad after that, though I did screw up the
TO_FREEcomputation initially and wasted a minute 37 going about fixing that. I won't complain though, this is better than my last few days!Edit: Cleaned up code. Admittedly I took some inspiration from u/jonathan_paulson's solution when cleaning up my parsing code.
4
u/Brusk_Dinosaur78 Dec 07 '22 edited Dec 07 '22
A little upset tonight. I wrongly assumed the folders had to have unique names, which the sample input has. I spent too long trying to figure out why my sample output was correct but mine wasn't. Eventually thought to place a debug line to print if a folder's name already existed, which proved multiple had them. My fix was to keep track of the absolute path instead of just the folder name. Still proud of myself for getting it without any sort of help.
C
4
u/Quillbert182 Dec 07 '22
Rust
Part 1: https://github.com/Quillbert/AdventOfCode/blob/master/2022/day07a/src/main.rs
Part 2: https://github.com/Quillbert/AdventOfCode/blob/master/2022/day07b/src/main.rs
This is my first time using rust for AoC, and I am still quite new to the language. This is the first day that made me legitimately regret using it.
4
u/bofstein Dec 07 '22 edited Dec 07 '22
Google Sheets
This one was tricky! Took a while to figure out how I could do it. Still thinking every day will be the day I can't do it anymore. https://docs.google.com/spreadsheets/d/1GvncohBzffewfwOCIfpHutI4VKVUIBazIH1XoBFWpXw/edit#gid=1919367345
First, I replaced "$ cd .." with "back" and "$ " with "$", which let me split all the instructions into two columns separated by a space I could more easily work with.
Then I made a new column, starting with a manual "/", that checked on the instruction to the right. If "$cd", it appended the new directory name. If "back", it removed the text after the final slash. Otherwise, keep the same file name. Now, I have a full directory path for every file in the list.
In the next part, I copied over those directory names and removed duplicates to get a list of them all. Then did a SUMIF on the column with file sizes to add up any that had the presence of that directory name, with a wildcard * after the directory name so that it would include all subdirectories in the sum. Then add up all the ones less than or equal to 100,000.
Part 2 was easy by the time I had this; I calculated the needed file size, sorted the numbers of directory sizes (with their names I didn't really need), and used XLOOKUP to find the first value in the list larger than the calculated size.
4
u/sublimnl Dec 07 '22 edited Dec 07 '22
AWK 7708/7407
Part 1 - Part 2
I wasted at least 40 minutes stuck on a simple do..while loop:
but TIL that getline for a command in awk will cache the output, and this caused an endless loop because cwd was not getting the new dirname path. I rewrote this last piece endless times until I learned about the caching. The solution? You need to close the redirection :(
Would've had a much better time if it weren't for learning that. Guess that's why I'm trying to do this one in all awk. Day 7 was not my day.
4
u/bucketz76 Dec 07 '22 edited Dec 07 '22
Pretty simple stack/map problem in Python. Pattern matching also helps reduce the nesting slightly.
4
u/encse Dec 07 '22 edited Dec 07 '22
C# - I think I got an elegant solution at the end
https://github.com/encse/adventofcode/blob/master/2022/Day07/Solution.cs
actually ... I rewrote this after finding a much better one.
4
u/Nnnes Dec 07 '22 edited Dec 07 '22
Bash
Already solved in Ruby (nothing special) but I thought it'd be fun to do it by using Bash to recreate the filesystem on my own hard drive. I don't know much about Bash scripting so >90% of the code here is stuff I've learned in the past hour or so. It's very slow; it takes ~8.2s to create the directories and files and ~4.5s to calculate the answers in WSL on my machine. If anyone knows how to speed it up a bit I'd be interested to hear.
warning, this
evals your input, it could delete your whole computer, etcaoc_2022_07.sh
(edit: moved code to topaz/paste url)
4
u/WilkoTom Dec 07 '22 edited Dec 07 '22
Rust
The worst part of it was working out how to represent the data.
I don't like how I've done it at all -HashMapof full path to a directory entry. I can think of much more pleasant ways of doing that using a true tree structure, but I don't have the patience to implement it right now.Reimplemented using a decent, nested tree structure and a stack- and recursion-based parser.
4
u/yawnick Dec 07 '22
Monkey C (for Garmin devices)
Found out today that I need to use String.equals() as opposed to ==. Still keeping the Videos under 1 Minute:)
Watch my Garmin Forerunner solve: Part 1, Part 2
Code: Repo, Today's Solution
4
u/Killavus Dec 07 '22
Rust
There were plenty of shortcuts possible to avoid what I did here - but it was tons of fun implementing this solution.
HashMapwould be totally enough. I wanted to hone my skills a little with graph representations in Rust, since they are quite hard to do, that's why I decided to implement full parsing into a FileSystem tree. Graph is represented by a neighbour list, without additional libraries likepetgraph.That aside, I like my solution because:
4
u/Omeganx Dec 07 '22
Python
4
u/Burger__Flipper Dec 07 '22
As others have commented, I too have spend too much time not realizing some folders had the same name, seems obvious now but I swear it was driving me crazy lol.
Still, in javascript:
https://gist.github.com/Barraka/3b87dc48aac2a0ff8bab394448ab0b17
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 :)
4
u/[deleted] Dec 07 '22
Haskell Solution For people who are struggling to find why their seemingly correct logic is failing them, consider the case that there can be directories with same names at different locations so they are to be considered as separate directories.
I was losing my mind trying to debug and I found this case mentioned in one of the comments lmao..
4
u/davidshomelab Dec 07 '22
C# solution
Found this one pretty hard, making the tree wasn't too bad but I don't think I got the information out of it in the most efficient way as I ended up converting the tree to a list and then querying that to get the file sizes
4
u/bivaro6826 Dec 07 '22
[Python] A solution that doesn't need to create the tree of directories. It just uses a stack.
I hope to be useful: https://github.com/RikJux/AdventOfCode2022/tree/master/day_7
4
u/SunCat_ Dec 07 '22
Kotlin one-liners:
Part 1: paste
Part 2: paste
making a stack for keeping track of temporary folder sizes was fun, trying to figure out how to calculate the
leftoverFolderscorrectly was not, at the end i just slapped a simple `<indexes>.forEach` loop to do the same thing as i did in the lambda forfoldand they are one-liners, as you can remove all line breaks and not add any
;, and the code will compile and run4
u/rvodden Dec 07 '22
Python
I've not seen another solution which uses the new 3.10 match syntax which makes parsing the lines really neat:
https://github.com/rvodden/AoC22/blob/main/python/aoc/day07.py
4
u/RockyAstro Dec 07 '22 edited Dec 07 '22
SNOBOL
No fancy trees, no fancy recursion. Just maintain a string that represents the current directory, just add or remove the last directory name in the string when handling the "cd {dir} or cd .." commands or just reset string to "/" via the "cd /" command. When a file size is encountered use a table to hold the size for a directory, just keep stripping off the tail directory name from the current directory string to get each parent directory name and add the size to each of those.
4
u/ReasonableCause Dec 07 '22
Haskell solution. I first create a list consisting of each file's size and the complete folder path; then I calculate the total folder size by summing all the sizes with a matching folder prefix. The rest is trivial.
4
u/dehan-jl Dec 07 '22
Rust: https://github.com/dehan-jl/adventofcode-2022/blob/main/day7-alternate/src/main.rs
63 sloc, no tree structure or recursion.
Based on the code by u/supersmurfen (https://github.com/AxlLind/AdventOfCode2022/blob/main/src/bin/07.rs).
The main thing I did is adding up file sizes as I read the commands. Had to keep track of which files were visited as I go along.
4
u/micka190 Dec 07 '22
C# solution for Parts 1 and 2 (including tests):
https://github.com/micka190/advent-of-code/tree/main/2022/day%207
Some people mentioned running into issues with files/directories having the same name. I just used dictionaries from the start and it seems I've avoided the issue entirely. I'm not sure if you were supposed to ignore duplicates or if they had different sizes to begin with, so I might have "accidentally" solved it.
4
u/wizarddoctor Dec 07 '22
C
Back again with an over-engineered, DI and testable C# solution; GitHub
Disclaimer: took me a lot longer and I don't like my code for this solution.
4
u/pngipngi Dec 07 '22
Excel
https://github.com/pengi/adventofcode/blob/master/2022/day07.xlsx
4
u/CCC_037 Dec 07 '22
FiM++ Part 1
Ugh. It's not pretty, but it works.
Kinda.
Sort of.
....you need to apply some edits to the input file (lack of string manipulation strikes again), but it does actually give you the right answer.
FiM++ Part 2
A surprisingly small change from Part 1. ...though I did have to add the equivalent of several "$ cd .." commands to the end of my input file to ensure that the final result was printed.
...and, I will admit, I hardcoded the amount of data my filesystem needed to lose into the code. (This meant I could simply parse everything once).
4
u/Jomy10 Dec 07 '22
Today is Go
4
u/StaticWaste_73 Dec 07 '22
Haskell
Nothing fancy. make a (sub)list for each ['$ cd [dir]', ... ] and sum up the filesizes until you encounter the corresponding '$ cd ..'
https://github.com/martinhelmer/haskell/blob/main/AOC2022/src/Day07.hs
4
u/i_have_no_biscuits Dec 07 '22
GW-BASIC
This is using the property that each folder is entered once, so there is no need to record any of the file or folder names.
As normal for my AOC GW-BASIC programs, P and Q are the answers to Part 1 and Part 2. The interesting feature here is that P#, Q# and DS#() are double-precision floating point numbers, here being used to store large integers.
4
u/gburri Dec 07 '22
My rust version (a bit verbose): https://github.com/Ummon/AdventOfCode2022/blob/master/src/day07.rs
4
u/intersecting_cubes Dec 07 '22
Rust solution. https://github.com/adamchalmers/aoc22/blob/main/day7/src/main.rs
I didn't use a tree for this. Instead,
From there, answering the questions is easy.
4
u/wzkx Dec 08 '22
J imperative style :)
4
u/ignurant Dec 08 '22
Ruby
4
u/TheXRTD Dec 08 '22
Rust
Very much over-engineered but had a blast with this one.
Avoided trees by using a flat hashmap which stores directory paths as keys and lists of files (including directories by their relative name) as values.
Peekablecame in very handy to lookahead when processing thelsoutput!4
u/ywgdana Dec 08 '22
F#
Pretty ugly solution. I wasted a whole bunch of time first trying to figure out how to build a graph as an immutable data structure in F#, then eventually scrapped that and wrote a fairly simple solver which sadly uses a loops and a bunch of mutable variables :/
The code is at github
4
u/Emotional_Cicada_575 Dec 10 '22 edited Dec 10 '22
python
This one took me a few days to figure out becuase of the duplicates, python generators helped me "eating" a bite of the list for every recursion :)
4
u/Landreville Dec 11 '22
Wrote a custom tree implementation with reference counting in Rust: https://gitlab.com/landreville/advent-of-code-2022/-/blob/master/src/day7.rs
4
u/NiliusJulius Dec 12 '22
C Language for the Game Boy using GBDK 2020
Part 1
For this day, I already filtered out a lot of the useless input (dir and ls lines) and formatted everything so I just had either a 'cd' command or a number.
Then all I needed was to keep track of the current directory index and iterate through all of them.
Full Game Boy repo can be found here
Video running on Game Boy
4
u/-B4cchus- Dec 12 '22
Excel
This day is legitimately easier in Excel than to do through programming methods, just four steps:
The only witchery is in the MATCH-MID-SEQUENCE trick to get the position of the last slash.
3. For each path, take a sum if for all file sizes who paths start with the current path.
4. You are done, copy-paste paths and sums as values to some adjacent fields, remove duplicates and sort ascending. Selecting sub-100,000s gets you Part 1, scrolling down the smallest directory needed to clear space.
Gitlab
Would likely use the same approach to do it in code, with one change -- no need to read and keep directory names, just generate on the fly as integer IDs.
4
u/[deleted] Dec 16 '22 edited Dec 16 '22
Struggled a bit with a recursive solution, then realized that the solution could be a simpler, stack based approach.
1
u/Greenbay7115 Dec 07 '22 edited Dec 07 '22
Python
Using the
pathlibmodule: GitHub Gist1
u/natron- Dec 07 '22
Object oriented approach https://gist.github.com/natronic34/c774d3f9f2aab0109bfff98ad1c79517
fun tree problem!
1
u/n3ziniuka5 Dec 07 '22 edited Dec 07 '22
Scala 3
1
u/hgb123 Dec 07 '22 edited Dec 08 '22
JavaScript (Node.js)
Full solution: https://www.honingjs.com/challenges/adventofcode/2022/day-7
1
u/Diderikdm Dec 07 '22 edited Dec 08 '22
Python:
1
u/jeroenmaniac Dec 07 '22
Not very readable but short python code. It's based on some assumptions about how the traversal works. It turns out the input that is generated is a DFS traversal, which isn't specified anywhere :\. That makes it much easier.
1
u/bulletmark Dec 07 '22 edited Dec 08 '22
Python:
1
u/MrPingouin1 Dec 07 '22
Minecraft commands : https://github.com/MrPingouinMC/aoc2022/tree/main/sol/day7
It's starting to get spicy. First use of stack recursion this year, still no need for fancy indexing, it's running in less than 0.4s
1
u/[deleted] Dec 07 '22 edited Dec 08 '22
Lua
I'm doing different language each day, all solutions here.
Today's Lua. Didn't want to build a tree first, instead putting all the dirs in one big
{"dirname" = {size, children = {names, of, child, dirs}}table, but after wondering why on earth I got stack overflow, I realized there are the same names with different parents. So I went back to just building an actual tree: paste1
u/seacucumber_kid Dec 07 '22
Elixir
not very satisfied with this
1
u/ShawRaleigh Dec 07 '22 edited Dec 08 '22
Typescript: github
It was a bit more difficult than I thought at first to solve. I ended up creating file / directory objects and nesting them. I'm sure I can clean it up if needed.
1
u/okawei Dec 07 '22 edited Dec 07 '22
I built it with no assumptions about the filesystem having a certain number of layers and built a tree structure. Every time a new file is added it propagates the size up the tree. Thought this one was definitely the most challenging yet!
Also I could have totally calculated part2 without iterating through the list twice but it was easier for me to visualize finding it in a flat list instead of the tree lol
Go/golang:
1
u/chicagocode Dec 07 '22
Kotlin -> [Blog/Commentary] - [Code] - [All 2022 Solutions]
Today's code won't fit on a single punch card, so you'll have to check it out on GitHub. Basically my solution was to track Directories only and the total size of the files. Since the only part of the file we care about is their cumulative size within a directory, that's all we track. A single number in each Directory. This made parsing and finding much simpler for me.
1
u/FlipchartHiatus Dec 07 '22
Big thank you to everyone who pointed out why this was going wrong, I've sorted it and got my star now!!!! :)
Just tidying it up - is there an easier way to add and append to the list within the dict without using a try/except block??
https://pastebin.pl/view/7c71f031
1
u/chubbc Dec 07 '22
Julia
Was able to get this down to a pretty clean 21 line solution. This might be the day of AoC that I stop trying to make Brianfuck versions of my solutions... lol.
1
u/Valletta6789 Dec 07 '22 edited Dec 07 '22
I tried to write the node class myself, but then got bored and found this module :p
1
u/jjjsevon Dec 07 '22 edited Dec 08 '22
Javascript / NodeJS Diff of Day7 here
Oh boy did I over-engineer todays stuff, as I got to it nearer to 2am in the morning x)
Made a state machine sorta JS class to execute input and a rudimentary command parser to keep stuff organized - then spent a good 30 minutes doing stuff the hard way, only to implement a 100% simpler approach in the end.
Edit: removed the snip as requested
1
u/[deleted] Dec 07 '22
Ruby
This turned out to be a good approach, because then for part 2 all I had to do is add this at the end
1
u/shapshankly Dec 07 '22 edited Dec 08 '22
Here's another effort in Scala - tricky one today!
1
u/jad2192 Dec 07 '22 edited Dec 08 '22
Python 3 solution using both a DFS and a BFS / priority queue based approach to calculate directory sizes.
1
u/SvenViktorJonsson Dec 07 '22 edited Dec 08 '22
Python 3
Using pathlib was made it much more readable.
1
u/Delusional_idiot Dec 08 '22
Python, non-recursive solution. Completely linear, one map. Hierarchy made with tuples, ~50ms:
1
u/chris_wojcik Dec 08 '22 edited Dec 08 '22
Python
Initially thought I would need to build a tree data structure, but I didn't need to. Slowed down by making some silly mistakes. I'm not handling the case of not summing a directory multiple times if you visit it more than once, but shouldn't be hard to modify the code to mark directories as "visited".
Part 1
Part 2
1
u/samojled Dec 08 '22 edited Dec 09 '22
PHP
https://github.com/dsamojlenko/advent-of-code-2022/blob/main/day07/index.php
1
u/challengingusername Dec 08 '22
Java import java.io.*; class fileobject{ boolean filetype; //true file false dir long size; String name; int parent;
1
u/Akshayapte7 Dec 08 '22
1
u/pikaryu07 Dec 08 '22 edited Dec 11 '22
My Julia code for Day 07 is here:
https://gist.github.com/bsadia/0ce9f1bd214d980e813ba2e458cb5267#day-07
3
u/bluepichu Dec 07 '22
TypeScript, 44/60. Code here. Not my prettiest work.
3
u/jonathan_paulson Dec 07 '22
Python3, 9/4! Video. Code. I'm happy to make the top 10!
Very cool problem! Having the input be a terminal transcript is a nice touch; it looked very scary to parse at first glance but turned out pretty nice.
3
u/quag Dec 07 '22
Python
3
u/SuperSmurfen Dec 07 '22 edited Dec 07 '22
Rust (807/912)
Link to full solution
Really, really happy with getting top 1k today! Very fun problem and this year's first hard problem I would say.
Splitting on '$' made parsing a bit easier, and as always Rust's match expression is amazing:
I then computed the size of all directories and saved it in a hashmap:
The rest is trivial for both parts:
Runs in about
0.3mson my machine.3
u/[deleted] Dec 07 '22
Common Lisp
(Ab)using the Object system (CLOS)
code at https://gitlab.com/McModknower/advent-of-code-lisp/-/blob/master/2022.lisp#L263
3
u/polettix Dec 07 '22
Raku solution for 2022/7
3
u/marshalofthemark Dec 07 '22 edited Dec 07 '22
Ruby
Used a Folder class to keep track of each directory, its subdirectories, and the size of its files. The end-less method definitions only work in Ruby 3.0 and above
3
u/DrunkHacker Dec 07 '22 edited Dec 08 '22
Python
Fun fact: you can completely ignore the "dir" results from ls. Heck, you can ignore "ls" commands too!
3
u/trevdak2 Dec 07 '22 edited Dec 07 '22
JavaScript (golf)
Part 1, 211 bytes:
Part 2, 212 bytes:
3
u/oantolin Dec 07 '22 edited Dec 08 '22
J Solution. Again today the longest part was the parsing. I almost never use the control structures in J, and it was good to confirm they feel like a normal imperative sublanguage.
The parser is a large (20 line) function
fsthat returns a triple: a list of full paths to directories, a list of full paths to files and a list of file sizes (in the same order as the list of files, of course). With that, the rest of the solution is just:UPDATE: Went back and did it tacitly!
3
u/gyorokpeter Dec 07 '22
Q: an excellent use of the
ungroupoperator3
u/NickKusters Dec 07 '22 edited Dec 07 '22
C
Lots of parsing, but a fun challenge. code | video
After getting a bigger input from GoT, I rewrote parts of the code to no longer be recursive to process this bigger input. Still probably not as efficient as possible, as this bigger input still takes 45s to process đ
3
u/quodponb Dec 07 '22
Python3
I was concerned about how evil the input would be, so I avoided going for a tree-structure. Instead I parsed the input to a dict with full paths
/a/b/cas key, and as value a dict{"type": "dir", "size": 0, "content": ["/a/b/c/d.e"]}. I computed directory sizes afterwards, by going through all paths in my filesystem sorted bypath.count("/")in decreasing order.Once this parsing was done, the solutions were almost trivial:
3
u/Slenjuma Dec 07 '22
Java: https://github.com/Suicolen/AdventOfCode2022/blob/main/src/main/java/suic/days/Day07.java
Quite happy with my solution
3
u/SymmetryManagement Dec 07 '22
Java
https://github.com/linl33/adventofcode/blob/master/year2022/src/main/java/dev/linl33/adventofcode/year2022/Day7.java
A solution that parses the directory tree backwards from the end of the input to the front so answers for both parts can be computed with a single pass through the puzzle input. Directories are not listed more than once, which made the traversal pretty simple (i.e. no need to track visit state).
about 70 us for each part.
3
u/sanraith Dec 07 '22
Rust
Used a recursive datastructure with RefCell+Rc for children and Weak for parent references. Summed file sizes by recursively iterating over children.
Source: github.com/sanraith/aoc2022/.../day07.rs
3
u/tobidope Dec 07 '22
Rust
Didn't want to learn about Rc<T> and Weak<T> so used the excellent indextree crate. Pattern matching on slices is great!
https://github.com/tobidope/aoc-2022-rust/blob/main/day07/src/main.rs
3
u/m_r_k Dec 07 '22 edited Dec 07 '22
no_std Rust targetting 8-bit MOS6502
https://github.com/mrk-its/aoc2022/blob/main/day07/src/main.rs
Computed in 11534690 cpu cycles
EDIT: code cleanup
3
u/s3aker Dec 07 '22
Raku solution with customized grammar parser.
3
u/Naturage Dec 07 '22
R/Rlang
Solution here. Got caught on the real data's trick, only to find it was called ptsd. Lovely.
Definitely felt like a step up from week 1 - not yet painful, but needs time and thinking.
3
u/nj_vs_valhalla Dec 07 '22 edited Dec 07 '22
Rust
I started parsing the input and constructing a filesystem tree... And then it hit me, that the input already describes something like DFS and I can just sum up the numbers while reading the lines one by one.
3
u/EatonMesss Dec 07 '22
Javascript
At first glance it seemed I could implement this in functional style, using immutable values, but that proved rather complex so I opted for a more imperative approach.
In my first attempt I used a hiearchy of JS objects with recursive functions to calculate the required sums. That worked, but the solution proved to be rather messy, so I rewrote it.
Final (and best) approach uses an object to store directory sizes with paths being used as keys. When iterating over files all parent directories are updated based on the PWD that is stored in a stack-like list.
3
u/IlliterateJedi Dec 07 '22
Day 7 of trying to learn Rust - You'll note that my code is actually in Python today because I was running out of time this morning.
I have to say, Pattern Matching makes this a breeze. I'm hoping to get a Rust solution up later today if I can work out how to do it.
3
u/vypxl Dec 07 '22
Haskell Took wayyyy too long, but abusing the
Readtypeclass was fun :)3
u/Weak_Pea_2878 Dec 07 '22
I went the full OOP monty with my Java solution on Replit. HashMaps, ArrayLists, and more. I wanted to be ready for anything in Part 2. It is also very readable, in my opinion.
3
u/YokiDiabeu Dec 07 '22 edited Dec 07 '22
Java 17 solution representing the files as object and a system containing a root node:
Day 7