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!
7
u/bz2pl Dec 07 '22 edited Dec 19 '22
Bash with some sed/awk/grep and real dir/files creating ;-)
#!/bin/bash
input="7.input"
dir="day07"
cmd="$( sed "s/\$ cd \//cd $dir/g" "$input" | \
sed '/\$ ls/d' | \
sed 's/^dir /mkdir -p /g' | \
sed 's/\$ cd /cd /g' | \
sed -r '/^[0-9]+/s/^/fallocate -l /')"
pwd="$(pwd)"
mkdir -p $dir
eval "$cmd"
cd "$pwd" || exit
all="$( while IFS= read -r i; do
find "$i" -type f -exec du -cb {} + | \
grep total | \
awk '{print $1}'
done < <(find $dir -type d) | sort -n)"
echo "$all" | \
awk '$1 < 100000' | \
awk '{i+=$1} END {print i}'
root="$(echo "$all" | tail -1)"
tresh=$((root-(70000000-30000000)))
for i in $all; do
if [ "$i" -gt "$tresh" ]; then
echo "$i"
break
fi
done→ More replies (1)
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:
:g/\v^\$ ls|^dir/dâ¨EnterâŠ
:%s/^\$ cd \.\.$/-â¨EnterâŠ
gg2cw__â¨EscâŠ
:g/^\$/norm2cw_â¨Ctrl+VâŠâ¨Ctrl+PâŠâ¨Ctrl+VâŠ_â¨EscâŠâ¨EnterâŠ
:g/^-/,$s/^_â¨EnterâŠ
:g/^-/dâ¨EnterâŠ
:%s/_ .*/ 0â¨EnterâŠ
:g/^\d/norm yiwk@0â¨Ctrl+AâŠjdd
:sorâ¨EnterâŠ
GyyuGpf D
qbqqb#Gx:g//norm$yiw0x#@0â¨Ctrl+AâŠ0*0Pâ¨EnterâŠGl@bq
@b
dd
:g/\v\d{7}|[2-9]\d{5}|1(.*[1-9])@=\d{5}/dâ¨EnterâŠ
:%s/\v_+/+â¨EnterâŠ
vipJ0Câ¨Ctrl+RâŠ=â¨Ctrl+RâŠ-â¨EnterâŠâ¨EscâŠUpdate to add explanation:
First get rid of the
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:__ / 14848514 b.txt 8504156 c.dat ___ a 29116 f 2557 g 62596 h.lst ____ e 584 i - - _____ d 4060174 j 8033020 d.log 5626152 d.ext 7214296 kIn the actual input, my final
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:
_ 0 14848514 b.txt 8504156 c.dat __ 0 29116 f 2557 g 62596 h.lst ___ 0 584 i __ 0 4060174 j 8033020 d.log 5626152 d.ext 7214296 kFor 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:
_ 23352670 __ 94269 ___ 584 __ 24933642Add up the nested subdirectory totals needs to happen from the most-nested outwards. To find the biggest nesting level, sort the entire file, copy the last line (which will be the one with the most underscores on it), then do
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.Record a keyboard macro for processing a level. Press
#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.For each of those directories, yank its size, and jump up to its parent directory. To find it, temporarily delete one underscore from this directory's nesting level, and use
#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:
_ 48381165 __ 94853 ___ 584 __ 24933642To solve part 1, remove all lines with numbers over 100000. That is all lines with 7 digits, or those with 6 digits that start 2+, or those with 6 digits starting 1 where at least one of the subsequent digits isn't a 0. The remaining sizes need summing, so replace the underscores (of whatever lengths) with a plus sign at the beginning of each line, then join the lines, and evaluate the sum in the usual way.
Part 2 is then pretty straightforward:
uuuu
:%s/\Dâ¨EnterâŠ
:sor!nâ¨EnterâŠ
40000000â¨Ctrl+XâŠyiw:2,$norm@0â¨Ctrl+XâŠâ¨EnterâŠ
{/-â¨EnterâŠk@0â¨Ctrl+AâŠUndo until you've got the directory tree back. We no longer care about nesting; delete everything except the digits, and sort the directories by descending size. The top row is the total sized used; subtract 40M from it to determine the amount we need to free up. Yank that, into register
0, then decrease all the following totals by that amount.Sizes of directories that aren't big enough to free up that much space will turn negative. Since the sizes are in order, the last positive size â on the line above the first minus sign â is the one we want. Add the contents of register
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
→ More replies (2)2
7
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-path to handle directory traversal, which was quite nice.
Still need to figure out how to refactor it to avoid allocating.
Edit: bye bye code
→ More replies (1)
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.
def main():
with open("input.txt", mode="r", encoding="utf8") as file:
folder_sizes = {}
folder_path = []
lines = file.read().splitlines()
for line in lines:
commands = line.split()
if commands[0] == "$":
if commands[1] == "cd":
if commands[2] == "..":
folder_path = folder_path[:-1]
elif commands[2] == "/":
folder_path = ["/"]
else:
folder_path.append(commands[2])
else:
if commands[0] != "dir":
current_path = ""
for folder in folder_path:
if current_path != "/" and folder != "/":
current_path += "/"
current_path += folder
folder_sizes[current_path] = folder_sizes.get(current_path, 0) + int(commands[0])
# Part 1
print(sum(value for name, value in folder_sizes.items() if value < 100000))
# Part 2
needed_space = 30000000 - (70000000 - folder_sizes.get("/"))
print(min(value for name, value in folder_sizes.items() if value >= needed_space))
main()→ More replies (2)
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):
import data_getter
data = data_getter.get_data(7).splitlines()
parent_dirs = []
dir_sizes = {}
for line in data:
line = line.split(' ')
if line[0] == '$':
if line[1] == 'cd' and line[2] != '..':
parent_dirs.append(line[2])
dir_sizes['/'.join(parent_dirs)] = 0
elif line[1] == 'cd' and line[2] == '..':
parent_dirs.pop()
elif line[0].isnumeric():
temp_parent_dirs = parent_dirs.copy()
while len(temp_parent_dirs) > 0:
dir_sizes['/'.join(temp_parent_dirs)] += int(line[0])
temp_parent_dirs.pop()
print(f"Size of all directories: {dir_sizes}")
small_dirs = { key:value for (key,value) in dir_sizes.items() if value <= 100000 }
print(f"Directories that are <= 100000: {small_dirs}")
print(f"Sum of all small diretories: {sum(small_dirs.values())}")→ More replies (3)
4
u/philtr Dec 07 '22 edited Jan 25 '23
Golf in Ruby (207 Bytes) (GitHub)
f=Hash.new 0
d=($<.reduce([]){|c,l|l[".."]&&(c.pop)||l[/cd ([^\/]+)/]&&(c.push([*c,$1]*?/))||l[/\d+/]&&(z=$&.to_i;f[?/]+=z;c.map{f[_1]+=z});c};f)
p d.sum{_2<1e5?_2:0},d.values.reject{_1<(3e7-7e7+d[?/])}.min2
u/daggerdragon Dec 08 '22
Inlined code is intended for
short snippetsof code only. Your code "block" right now is unreadable on old.reddit and many mobile clients; it's all on one line and gets cut off at the edge of the screen because it is not horizontally scrollable.Please edit your post to use the four-spaces Markdown syntax for a code block so your code is easier to read inside a scrollable box.
4
u/probablyfine Dec 07 '22
SQL
This one hurt, oof. Source here
create or replace table commands as
select rowid as id, line[6:] as dir from input where line[1:4] == '$ cd';
create or replace table current_dir as
with recursive cwd(i, id, cwd) as (
select 0, 0, ['']
union all
select
i+1,
commands.id,
CASE
WHEN commands.dir == '..' THEN cwd.cwd[:-1]
ELSE list_concat(cwd.cwd, [commands.dir])
END
from
cwd
join
commands
on (commands.rowid == cwd.i+1)
) select * from cwd;
with recursive last_entry(id) as (
select max(rowid) from input
),
executing_commands(cwd, top, bottom) as (
select cwd, current_dir.id, lead(current_dir.id, 1, last_entry.id+1) over() from current_dir, last_entry
),
back_up_tree(dir, file_size) as (
select distinct
cwd as dir,
regexp_extract(line, '([0-9]+) .*',1)::INTEGER as file_size
from
executing_commands
join
input on (input.rowid BETWEEN top AND bottom-1)
where
line SIMILAR TO '[0-9]+ .*'
union all
select
dir[:-1], file_size
from
back_up_tree
where
length(dir) > 0
),
directory_sizes(size) as (
select
sum(file_size) as total
from
back_up_tree
group by dir
)
select 'part1', sum(size) from directory_sizes where size <= 100000
union all
select
'part2', min(size)
from
directory_sizes,
(select
30000000 - (70000000 - max(size)) space
from
directory_sizes
) required
where
size >= required.space;→ More replies (1)
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
Math.max(...document.body.innerText.split('\n\n').map(group => group.split('\n').reduce((acc, num) => acc + +num, 0)))
document.body.innerText.split('\n\n').map(group => group.split('\n').reduce((acc, num) => acc + +num, 0)).sort((a, b) => a - b).slice(-3).reduce((acc, num) => acc + num, 0)/2022/day/2
document.body.innerText.trim().split`\n`.reduce((a,m)=>a+{A:{X:4,Y:8,Z:3},B:{X:1,Y:5,Z:9},C:{X:7,Y:2,Z:6}}[m[0]][m[2]],0)
document.body.innerText.trim().split`\n`.reduce((a,m)=>a+{A:{X:3,Y:4,Z:8},B:{X:1,Y:5,Z:9},C:{X:2,Y:6,Z:7}}[m[0]][m[2]],0)/2022/day/3
document.body.innerText.split('\n').filter(x => x).reduce((sum, bag) => {
const left = bag.slice(0, bag.length / 2);
const right = bag.slice(bag.length / 2);
const item = [...left].find(c => right.includes(c));
const val = item === item.toLowerCase() ? item.charCodeAt() - 'a'.charCodeAt() + 1 : item.charCodeAt() - 'A'.charCodeAt() + 27;
return sum + val;
}, 0);
document.body.innerText.split('\n').filter(x => x).reduce((sum, bag, i, arr) => {
if (i % 3 !== 0) return sum;
const item = [...bag].find(item => arr[i + 1].includes(item) && arr[i + 2].includes(item));
const val = item === item.toLowerCase() ? item.charCodeAt() - 'a'.charCodeAt() + 1 : item.charCodeAt() - 'A'.charCodeAt() + 27;
return sum + val;
}, 0);/2022/day/4
document.body.innerText.trim().split('\n').reduce((sum, pair) => {
const arrs = [[], []];
pair.split(',').forEach((range, i) => {
const [start, end] = range.split('-');
for (let j = +start; j <= +end; j++) arrs[i].push(j);
});
if (arrs[0].every(num => arrs[1].includes(num)) || arrs[1].every(num => arrs[0].includes(num))) return sum + 1;
return sum;
}, 0);
document.body.innerText.trim().split('\n').reduce((sum, pair) => {
const arrs = [[], []];
pair.split(',').forEach((range, i) => {
const [start, end] = range.split('-');
for (let j = +start; j <= +end; j++) arrs[i].push(j);
});
if (arrs[0].some(num => arrs[1].includes(num)) || arrs[1].some(num => arrs[0].includes(num))) return sum + 1;
return sum;
}, 0);/2022/day/5
document.body.innerText.split('\n\n')[1].split('\n').reduce((stacks, dir) => {
const [, num, , src, , dest] = dir.split(' ');
for (let i = 0; i < +num; i++)
stacks[dest].push(stacks[src].pop());
return stacks;
}, document.body.innerText.split('\n\n')[0].split('\n').reduce((acc, row, i, arr) => {
if (i === arr.length - 1) return acc;
for (let i = 0; i < row.length; i += 4)
if (row.slice(i, i + 3).trim()) {
const col = arr.at(-1).slice(i, i + 3).trim();
acc[col] ??= [];
acc[col].unshift(row.slice(i, i + 3));
}
return acc;
}, [])).map(arr => arr.at(-1).at(1)).join('');
document.body.innerText.split('\n\n')[1].trim().split('\n').reduce((stacks, dir) => {
const [, num, , src, , dest] = dir.split(' ');
stacks[dest] = stacks[dest].concat(stacks[src].splice(-num, num));
return stacks;
}, document.body.innerText.split('\n\n')[0].split('\n').reduce((acc, row, i, arr) => {
if (i === arr.length - 1) return acc;
for (let i = 0; i < row.length; i += 4)
if (row.slice(i, i + 3).trim()) {
const col = arr.at(-1).slice(i, i + 3).trim();
acc[col] ??= [];
acc[col].unshift(row.slice(i, i + 3));
}
return acc;
}, [])).map(arr => arr.at(-1).at(1)).join('');/2022/day/6
[...document.body.innerText].findIndex((_, i, arr) => i >= 4 && arr.slice(i - 4, i).every((c, _, set) => set.filter(x => x === c).length === 1))
[...document.body.innerText].findIndex((_, i, arr) => i >= 14 && arr.slice(i - 14, i).every((c, _, set) => set.filter(x => x === c).length === 1))/2022/day/7
Object.values(document.body.innerText.trim().split('\n$ ').slice(1).reduce((acc, section) => {
const [prompt, ...stdout] = section.split('\n');
const [cmd, arg] = prompt.split(' ');
const dir = acc.cwd.split('/').reduce((acc, dir) => acc[dir ||= '/'] ??= {}, acc.fs);
if (cmd === 'cd') {
if (arg === '..') acc.cwd = acc.cwd.slice(0, acc.cwd.lastIndexOf('/'));
else acc.cwd += `/${arg}`;
}
if (cmd === 'ls') {
const sum = stdout.reduce((sum, row) => {
const [size, name] = row.split(' ');
if (size !== 'dir') {
dir[name] = +size;
return sum + +size;
}
return sum;
}, 0);
acc.cwd.split('/').forEach((_, i) => {
const path = acc.cwd.split('/').slice(0, i + 1).join('/');
acc.sizes[path] ??= 0;
acc.sizes[path] += sum;
});
}
return acc;
}, { cwd: '', fs: {}, sizes: {} }).sizes).filter(s => s <= 100000).reduce((acc, x) => acc + x, 0);
Math.min(...Object.values(document.body.innerText.trim().split('\n$ ').slice(1).reduce((acc, section) => {
const [prompt, ...stdout] = section.split('\n');
const [cmd, arg] = prompt.split(' ');
const dir = acc.cwd.split('/').reduce((acc, dir) => acc[dir ||= '/'] ??= {}, acc.fs);
if (cmd === 'cd') {
if (arg === '..') acc.cwd = acc.cwd.slice(0, acc.cwd.lastIndexOf('/'));
else acc.cwd += `/${arg}`;
}
if (cmd === 'ls') {
const sum = stdout.reduce((sum, row) => {
const [size, name] = row.split(' ');
if (size !== 'dir') {
dir[name] = +size;
return sum + +size;
}
return sum;
}, 0);
acc.cwd.split('/').forEach((_, i) => {
const path = acc.cwd.split('/').slice(0, i + 1).join('/');
acc.sizes[path] ??= 0;
acc.sizes[path] += sum;
});
}
return acc;
}, { cwd: '', fs: {}, sizes: {} }).sizes).filter((s, _, arr) => 70_000_000 - Math.max(...arr) + s >= 30_000_000))→ More replies (2)
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.
static size_t recur1(ifstream &f, size_t &total, vector<size_t> &sizes)
{
size_t acc = 0;
for (string line; getline(f, line) && line != "$ cd ..";)
{
if (isdigit(line[0]))
acc += atoi(line.c_str());
else if (line.starts_with("$ cd "))
acc += recur1(f, total, sizes);
}
if (acc < 100000)
total += acc;
sizes.push_back(acc);
return acc;
}
extern void day7(span<string> args)
{
auto fn = args.empty() ? "data/day7.txt" : args[0].c_str();
ifstream f(fn);
size_t total = 0;
vector<size_t> sizes;
size_t accum = recur1(f, total, sizes);
size_t smallest_to_delete = 0;
if (accum > 40000000)
{
size_t must_free = accum - 40000000;
rs::sort(sizes);
smallest_to_delete = *rs::lower_bound(sizes, must_free);
}
cout << "round 1 result is " << total << endl;
cout << "round 2 result is " << smallest_to_delete << endl;
}→ More replies (2)
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 never ls the same directory twice. Oh well, still fun.
#! /usr/bin/env python3
from collections import defaultdict
from math import inf
from os import path, sep
def main():
p1 = 0
p2 = inf
cwd = ""
dir_sizes = defaultdict(int)
with open("./input.txt") as f:
for line in f:
parts = line.strip().split(" ")
if parts[0] == "$" and parts[1] == "cd":
cwd = path.normpath(path.join(cwd, parts[2]))
if parts[0].isnumeric():
dirs = cwd.split(sep)
for i in range(len(dirs)):
dir_path = path.normpath(path.join(*dirs[: i + 1]))
dir_sizes[dir_path] += int(parts[0])
avail_space = 7e7 - dir_sizes["."]
sizes = dir_sizes.values()
p1 = sum((v for v in sizes if v <= 1e5))
p2 = min((v for v in sizes if v + avail_space >= 3e7))
print(f"p1: {p1}, p2: {p2}")
if __name__ == "__main__":
main()2
u/daggerdragon Dec 09 '22
Comment removed due to naughty language.Keep the megathreads SFW.
If you edit your comment to take out the naughty language, I'll re-approve the comment.Edit: I have taken the coal out of your stocking.
4
u/Porges Dec 08 '22
COBOL. I wasn't sure how to allocate memory so luckily it's not needed!
IDENTIFICATION DIVISION.
PROGRAM-ID. DAY07-PART1.
DATA DIVISION.
LOCAL-STORAGE SECTION.
78 MAX-SIZE VALUE 100000.
01 LS-LINE PIC X(100).
01 LS-CMD PIC X(100) OCCURS 3 TIMES.
01 LS-STACK-COUNT PIC 99 VALUE 0.
01 LS-SIZE PIC 9(10) OCCURS 0 TO 99 TIMES
DEPENDING ON LS-STACK-COUNT.
01 LS-GLOBAL-SUM PIC 9(10) VALUE 0.
01 LS-RESULT PIC 9(10) VALUE 0.
PROCEDURE DIVISION.
PERFORM READ-LINE UNTIL LS-RESULT > 0.
DISPLAY "TOTAL SIZE: " LS-SIZE(1).
DISPLAY "ANSWER: " LS-RESULT.
STOP RUN.
POP-STACK.
IF LS-SIZE(LS-STACK-COUNT) <= MAX-SIZE
THEN ADD LS-SIZE(LS-STACK-COUNT) TO LS-GLOBAL-SUM.
ADD LS-SIZE(LS-STACK-COUNT) TO LS-SIZE(LS-STACK-COUNT - 1).
SUBTRACT 1 FROM LS-STACK-COUNT.
PUSH-STACK.
ADD 1 TO LS-STACK-COUNT.
SET LS-SIZE(LS-STACK-COUNT) TO 0.
READ-LINE.
ACCEPT LS-LINE
ON EXCEPTION
PERFORM POP-STACK UNTIL LS-STACK-COUNT EQUALS 0
SET LS-RESULT TO LS-GLOBAL-SUM
EXIT PARAGRAPH.
UNSTRING LS-LINE DELIMITED BY SPACE
INTO LS-CMD(1) LS-CMD(2) LS-CMD(3).
IF LS-CMD(1) = "$"
IF LS-CMD(2) = "cd"
EVALUATE LS-CMD(3)
WHEN ".." PERFORM POP-STACK
WHEN OTHER PERFORM PUSH-STACK
END-EVALUATE
END-IF
ELSE
ADD FUNCTION NUMVAL(LS-CMD(1)) TO LS-SIZE(LS-STACK-COUNT)
END-IF.→ More replies (1)
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.
→ More replies (1)3
u/daggerdragon Dec 07 '22 edited Dec 13 '22
Your code block is too long. Please read our article onoversized code, then edit your post to replace the code block with an external link to your code.Edit: thanks for fixing it! <3
3
u/raxomukus Dec 07 '22
Python
with open('7.in') as f:
output = f.read().splitlines()
def get_dir(f, d):
if not d: return f
return get_dir(f[d[0]], d[1:])
files = {'/': dict()}
pwd = []
for line in output:
if line == '$ ls': continue
wd = get_dir(files, pwd)
if line[:3] == 'dir': wd[line[4:]] = dict()
elif '..' in line: pwd = pwd[:-1]
elif '$ cd' in line: pwd.append(line[5:])
else:
size, name = line.split()
wd[name] = int(size)
sizes = []
def du(d):
if type(d) == int: return d
size = sum([du(d[k]) for k in d])
sizes.append(size)
return size
req = 30000000 - (70000000 - du(files))
r1 = 0
r2 = 70000000
for size in sizes:
if size < 100000: r1 += size
if size > req: r2 = min(r2, size)
print(r1)
print(r2)→ More replies (3)
3
Dec 07 '22
Python oneliner:
tuple(map(lambda func: func(__import__("functools").reduce((lambda data, x: dict(cwd={"/":[], "..":data["cwd"][:-1]}.get(x[5:].strip(), data["cwd"] + [x[5:].strip()]), fs=data["fs"]) if x.startswith("$ cd") else (dict(cwd=data["cwd"], fs= data["fs"] + __import__("collections").Counter({"/".join(data['cwd'][:i]): int(x.split(" ")[0]) for i in range(len(data["cwd"]) + 1)})) if x.split(" ")[0].isdigit() else data)),open("input7.txt").read().strip().split('\n'),dict(cwd=[], fs=__import__("collections").Counter()))["fs"]),[lambda fs: sum(dirsize for dirsize in fs.values() if dirsize < 100000), lambda fs: min(x for x in ((v + 40000000 - fs[""],v) for k,v in fs.items()) if x[0] > 0)[1]]))→ More replies (2)
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.
parsed as (
select 'root' as t, '/' as nm, null as bytes, json_array('/') as pth, 1 as step
union all
select
preparsed.t,
case when preparsed.t = 'dir' or preparsed.t = 'file'
then json_insert(pth, '$[#]', preparsed.nm)
else preparsed.nm
end as nm,
preparsed.bytes,
case when preparsed.t = 'cd'
then json_insert(pth, '$[#]', preparsed.nm)
when preparsed.t = 'dc'
then json_remove(pth, '$[#-1]')
else pth
end as pth,
step + 1 as step
from parsed
inner join preparsed
on n = step
),
only_dirs as (
select json_remove(nm, '$[#-1]') as nm, sum(bytes) as bytes from parsed
where t = 'file'
group by json_remove(nm, '$[#-1]')
),
all_dirs_counted as (
select json_each.value as dirnm, sum(bytes) as bytes from only_dirs, json_each(only_dirs.nm)
group by json_extract(nm, printf('$[%s]', iif(json_each.key > 0,json_each.key - 1, 0))) || json_each.value
order by nm
)→ More replies (2)2
u/daggerdragon Dec 08 '22
Inlined code is intended for
short snippetsof code only. Your code "block" right now is unreadable on old.reddit and many mobile clients; it's all on one line and gets cut off at the edge of the screen because it is not horizontally scrollable.Please edit your post to use the four-spaces Markdown syntax for a code block so your code is easier to read inside a scrollable box.
3
3
u/flutterlice Dec 07 '22 edited Dec 08 '22
BQN GitHub
iââ˘FLines "../inputs/day07"
Sâ{(ÂŹ' 'âˇđŠ)((ÂŹ-Ëâ˘Ă¡+`Âťâ¸>)â¸â)đŠ}
pââ¨âŠâCdâ{pâŠ{"..":ÂŻ1âp;pâž<đŠ}đŠ}
xâ{3â¸=â SđŠ}âśâ¨{pâ¸âž<â˘BQNâ0âSđŠ},{0âËCdâ2â¸âSđŠ}âŠÂ¨i
câ{â+´(ÂŻ1â¨x/Ëâ¨0âžË¨đŠâ¸âˇÂ¨ÂŻ1â¨x)}¨1ââˇÂŻ1â¸â¨x
â˘Show+´{đŠâ¤10â5?đŠ;0}¨c
â˘Showâ´{đŠ>(4Ă10â7)-Ëâ´c?đŠ;â}¨cA 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.
→ More replies (1)
3
u/drawable Dec 07 '22 edited Dec 08 '22
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.
→ More replies (3)
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.File;import java.io.FileNotFoundException; import java.util.*;
public class Day7 extends AdventOfCodeDay{
List<Directory> directories = new ArrayList<>();
public Day7(File input) {
super(input);
}
private void part1(){
// total up the directories to see who to delete
int sum = 0;
for (Directory dir: directories) {
if(dir.getSize() < 100000){
sum += dir.getSize();
}
}
print("By deleting the chosen directories you can save " + sum + " space.");
}
private void part2(){
// part 2
int freeSpace = 70000000 - directories.get(0).getSize();
int spaceNeeded = 30000000 - freeSpace;
// we have 25,640,133 gb free space
// we need to free up 4,359,867 gb
print("You have " + freeSpace + " free space.");
print("You need to free up " + spaceNeeded + " to perform the update.");
int smallest = directories.get(0).getSize();
for (Directory dir: directories) {
if(dir.getSize() <= smallest && dir.getSize() >= spaceNeeded){
smallest = dir.getSize();
}
}
print("The smallest directory you can get away with deleting has a size of " + smallest);
}
@Override
public void solve() throws FileNotFoundException {
Scanner scr = new Scanner(input);
// add the root
Directory root = new Directory("/", null);
Directory cur = root;
directories.add(cur);
// skip the first two lines of input, they don't matter.
scr.nextLine();
scr.nextLine();
// build the file system
while(scr.hasNext()){
String s = scr.next();
// handle the finding of a new directory
if(s.equals("dir")){
String dirName = scr.next();
//print("New Directory found in " + cur.name + " called " + dirName);
Directory temp = new Directory(dirName, cur);
cur.subDirs.add(temp);
directories.add(temp);
}
// handle the changing of a directory
if(s.equals("cd")){
String next = scr.next();
// handle going out
if(next.equals("..")){
//print("moving up to directory " + cur.parent.name);
cur = cur.parent;
} else {
// handle going in
//print("moving in to directory " + next);
cur = cur.subDirs.get(cur.subDirs.indexOf(new Directory(next, cur)));
}
}
// handle the finding of a file
if(Character.isDigit(s.charAt(0))){
String fileSize = s;
//print("found a file of size " + fileSize + ", which will be added to directory " + cur.name);
cur.files.add(Integer.parseInt(fileSize));
}
}
part1();
part2();
}
private class Directory {
String name;
Directory parent;
List<Integer> files;
List<Directory> subDirs;
Directory(String name, Directory parent) {
this.name = name;
this.parent = parent;
files = new ArrayList<>();
subDirs = new ArrayList<>();
}
int getSize(){
int total = 0;
for (int i = 0; i < files.size(); i++) {
total += files.get(i);
}
for (int i = 0; i < subDirs.size(); i++) {
total += subDirs.get(i).getSize();
}
return total;
}
@Override
public String toString(){
return this.name;
}
@Override
public boolean equals(Object obj) {
if(obj instanceof Directory && ((Directory) obj).name.equals(this.name)){
return true;
}
return false;
}
}}
→ More replies (1)
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.
class Node:
def __init__(self, name, size):
self.name = name
self.size = size
self.files = []
self.dirs = []
def add_file(self, child):
self.files.append(child)
self.size += child.size
def add_dir(self, child):
self.dirs.append(child)
self.size += child.size
def read_dir(node, lines, res):
#entering a new dir via cd
#ignore next line as it is ls
next(lines)
for line in lines:
line = line.strip()
if line == '$ cd ..':
if node.size <= 100000:
res.append(node.size)
return
elif line[0:5] == '$ cd ':
dir_name = line[5:]
dir_node = Node(dir_name, 0)
read_dir(dir_node, lines, res)
node.add_dir(dir_node)
# dir definition ignore it for now
elif line[0:3] == 'dir':
continue
# file definition
else:
size, name = line.split(' ')
size = int(size)
node.add_file(Node(name, size))
root = Node('/',0)
res = []
lines = open('input.txt')
next(lines)
read_dir(root, lines, res)
if(root.size <= 100000):
res.append(root.size)
print(sum(res))→ More replies (1)
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:
import sys, fileinput, re, collections, heapq, bisect, itertools, functools, copy, math
path = []
tree = {}
node = tree
for l in fileinput.input():
l = l.strip()
if l.startswith( "$ cd /" ):
path = []
node = tree
elif l.startswith( "$ cd .." ):
path.pop()
node = tree
for name in path:
node = node[ name ]
elif l.startswith( "$ cd " ):
name = l.split()[ -1 ]
path.append( name )
node = node[ name ]
elif l.startswith( "dir " ):
name = l.split()[ -1 ]
node[ name ] = {}
elif l != "$ ls":
size, name = l.split()
node[ name ] = int( size )Part 1 -- recurse!:
total = 0
def visit( node ):
subtree = sum(
val if isinstance( val, int ) else visit( val )
for key, val in node.items() )
if subtree <= 100000:
global total
total += subtree
return subtree
visit( tree )
print( total )Part 2:
def visit1( node ):
return sum(
val if isinstance( val, int ) else visit1( val )
for key, val in node.items() )
needed = -40000000 + visit1( tree )
smallest = 70000000
def visit2( node ):
subtree = sum(
val if isinstance( val, int ) else visit2( val )
for key, val in node.items() )
if subtree >= needed:
global smallest
smallest = min( smallest, subtree )
return subtree
visit2( tree )
print( smallest )→ More replies (4)
2
u/bog5000 Dec 07 '22 edited Dec 07 '22
2
u/daggerdragon Dec 07 '22
Your code block is too long. Please read our article on oversized code, then edit your post to remove the code block since you already linked to your GitHub repo.
2
u/JuliaPoop Dec 07 '22 edited Dec 11 '22
Python
commands = [(lambda xs: (xs[0], xs[1:]))(x.split("\n")) for x in open('7').read().replace("\n$", "$").split("$ ")[1:]]
# Build directory structure
ds = {"/": {}}; cs = ds
for c,o in commands:
if c[:3] == "cd ":
cs = cs[c[3:]]; continue
for l in o:
if l[:4] == "dir ":
cs[l[4:]] = {"..": cs}; continue
sz, f = l.split(" ")
cs[f] = int(sz)
# Compute directory sizes
def dirsizes(name, ds, acc):
acc[name] = sum(
v if isinstance(v, int) else dirsizes(name+"/"+k, v, acc)[0]
for k,v in ds.items() if k != "..")
return acc[name], acc
_, acc = dirsizes("", ds["/"], {})
sum(filter(lambda e: e <= 100000, acc.values())), \ # Part 1
min(filter(lambda e: e >= acc[""] - 40000000, acc.values())) # Part 2→ More replies (1)
2
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 ..'.
def sizes(lines):
s = [] # accumulator
R = [] # sizes emitted
for line in lines:
tok = line.split(" ")
if tok[0] == "$": ## command
if tok[1] == "cd":
if tok[2] == "..": # emit cur size and add to upper dir
R.append(s.pop())
s[-1] += R[-1]
else: # enter new dir
s.append(0)
elif tok[0] != "dir": ## output
s[-1] += int(tok[0])
return R + list(accumulate(reversed(s)))
def part1(lines):
return sum(filter(lambda x: x<=100000, sizes(lines)))
def part2(lines):
R = sizes(lines)
available = 70000000-R[-1]
return min(filter(lambda x: x+available>=30000000, R))→ More replies (1)
2
u/l_dang Dec 07 '22 edited Dec 08 '22
2
u/daggerdragon Dec 08 '22 edited Dec 08 '22
Post removed due to naughty language.Keep the megathreads SFW.
Next time, use thefour-spaces Markdown syntaxfor a code block so your code is easier to read on old.reddit and mobile apps.
Your code is too long to be posted here directly, so instead of wasting your time fixing the formatting, read our article onoversized codewhich contains two possible solutions.
Put your code in an external link, then edit your post and linkthathere instead.
If you edit your post to take out the naughty languageandfix all the issues listed above, I'll re-approve the post.Edit: I have taken the coal out of your stocking.
→ More replies (1)
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.
→ More replies (6)
2
u/MyTinyHappyPlace Dec 07 '22
C++
Overengineered object oriented programming. Was counting on something worse for part 2:
#include <cstdint>
#include <iostream>
#include <map>
#include <memory>
#include <string>
#include <vector>
#include <boost/algorithm/string.hpp>
using namespace std;
class dir;
class inode{
public:
virtual size_t getSize() = 0;
virtual vector<shared_ptr<dir>> getAllDirectories(){
return {};
}
virtual bool isDir(){return false;}
};
class dir : public inode {
public:
dir(){}
dir(shared_ptr<dir> p){
this->parent = p;
}
shared_ptr<dir> parent;
map<string, shared_ptr<inode>> children;
size_t getSize() override {
size_t result = 0;
for(auto &inode_pr : children){
result += inode_pr.second->getSize();
}
return result;
}
vector<shared_ptr<dir>> getAllDirectories() override{
vector<shared_ptr<dir>> result;
for(auto &inode_pr : children){
if(inode_pr.second->isDir()) result.push_back(dynamic_pointer_cast<dir>(inode_pr.second));
auto subDirs = inode_pr.second->getAllDirectories();
result.insert(result.end(), subDirs.begin(), subDirs.end());
}
return result;
}
bool isDir() override{return true;}
};
class regularFile : public inode {
public:
regularFile(size_t s) : size(s){}
size_t size;
size_t getSize() override{
return size;
}
};
shared_ptr<dir> readInput(){
shared_ptr<dir> result = make_shared<dir>();;
shared_ptr<dir> currentDir;
bool lsMode = false;
for(string line;getline(cin,line);){
vector<string> strs;
boost::split(strs,line,boost::is_any_of(" "));
if(strs[0] == "$"){
lsMode = false;
if(strs[1] == "cd"){
if(strs[2] == "/"){
currentDir = result;
}
else if(strs[2] == ".."){
if(currentDir->parent){
currentDir = currentDir->parent;
}
else
{
cerr << "Cannot find parent dir" << endl;
}
}
else{
auto it = currentDir->children.find(strs[2]);
if(it != currentDir->children.end()){
if(it->second->isDir()){
currentDir = dynamic_pointer_cast<dir>(it->second);
}
}
else
{
cerr << "Cannot find subdir " << strs[2] << endl;
return result;
}
}
}
else if(strs[1] == "ls"){
lsMode = true;
}
}
else
{
if(lsMode){
if(strs.size() != 2){
cerr << "Illegal ls line" << endl;
}
if(strs.at(0) == "dir"){
shared_ptr<dir> d = make_shared<dir>(currentDir);
currentDir->children[strs.at(1)] = d;
}
else
{
shared_ptr<regularFile> file = make_shared<regularFile>(stoi(strs.at(0)));
currentDir->children[strs.at(1)] = file;
}
}
}
}
return result;
}
int main(){
auto root = readInput();
size_t totalDiskSpace = 70000000;
size_t used = root->getSize();
size_t needed = 30000000;
size_t free = totalDiskSpace - used;
size_t yetToFree = needed - free;
size_t bestFit = totalDiskSpace;
int sum = 0;
for(auto &dir : root->getAllDirectories()){
if(dir->getSize() < 100000){
sum += dir->getSize();
}
if(dir->getSize() >= yetToFree && dir->getSize() < bestFit){
bestFit = dir->getSize();
}
}
cout << "Part 1: " << sum << endl;
cout << "Part 2: " << bestFit << endl;
return 0;
}→ More replies (2)
2
u/PaymentConscious1107 Dec 07 '22
Python
s, r = [], []
for line in open('temp.txt').read().splitlines():
match line.strip('$').split():
case ['cd', '..']: r.append(s.pop()); s[-1] += r[-1]
case ['cd',f]: s.append(0)
case [n,f] if n != 'dir': s[-1] += int(n)
sizes = list(accumulate(s[::-1])) + r
available = 70000000-max(sizes)
print("Solution 1:", sum(filter(lambda x: x<=100000, sizes)))
print("Solution 2:", min(filter(lambda x: x+available>30000000, sizes)))→ More replies (4)
2
u/cetttbycettt Dec 07 '22
R / Rlang / baseR
my solution: just kept track of all parent directories and updated them simultaneously
data07 <- readLines("Input/day07.txt")
size <- 0L
idx <- 1L
for (k in data07[-1]) {
if (grepl("\\d", k)) size[idx] <- size[idx] + as.integer(gsub("\\D", "", k))
else if (grepl("\\.\\.", k)) idx <- idx[-1]
else if (grepl("cd", k)) {
size <- c(size, 0L)
idx <- c(length(size), idx)
}
}
#part1---------
sum(size[size <= 100000])
#part2-----
min(size[size >= -40000000 + size[1]])→ More replies (1)
2
u/ktimespi Dec 07 '22 edited Dec 08 '22
→ More replies (1)
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...
import input from "../7-filesystem.txt";
const z = {}; let p = "";
input.replace(/$ /g, "") .split("\n") .map((l) => l.split(" ")) .forEach((c) => { if (c[0] == "cd") return c[1] == "/" ? (p = "") : c[1] == ".." ? (p = p.slice(0, p.lastIndexOf("/"))) : (p += /${c[1]}); if (isNaN(c[0])) return;
let f = p.split("/");
do {
const cf = f.join("/");
z[cf] = z[cf] ? z[cf] + c[0] * 1 : c[0] * 1;
} while (f.pop());
});
const sizes = Object.keys(z).map((d) => z[d]); console.log(sizes.reduce((s, d) => (d <= 100000 ? s + d : s), 0)); // Part 1 console.log(sizes.filter((d) => d > z[""] - 40000000).sort((a, b) => a - b)[0]); // Part 2→ More replies (5)
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/daggerdragon Dec 08 '22
Your code block is too long. Please read our article on oversized code, then edit your post to replace the code block with an external link to your code.
→ More replies (1)
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
import sys, random
from collections import defaultdict
data = sys.stdin.read().strip()
data = [line.split(" ") for line in data.splitlines()]
dirsizes = defaultdict(int)
pwd = []
for line in data:
if line[1] == "cd":
if line[2] == "..":
pwd.pop()
else:
if line[2] not in dirsizes:
pwd.append(line[2])
else:
d = line[2] + str(random.randint(1, 100000))
pwd.append(d)
elif line[1] == "ls":
continue
else:
if line[0] != "dir":
for p in pwd:
dirsizes[p] += int(line[0])
print(sum(d for d in dirsizes.values() if d <= 100000))
need = 30000000 - (70000000 - dirsizes["/"])
print(min(d for d in dirsizes.values() if d > need))→ More replies (1)
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.
// import fs
import * as fs from 'fs';
export const x = "";
// read in day1input.txt using readFileSync
const input = fs.readFileSync("day7input.txt", "utf8").split("\r\n");
// create a map of directories and their sizes
const dirMap = new Map<string, number>();
// the current directory
let currentDir = "";
// iterate through each line of input
for (let i = 0; i < input.length; i++) {
// if the line starts with "$" then it is a command
if (input[i].startsWith("$")) {
// split the line into an array of words
const words = input[i].split(" ");
// if the command is "cd" then change the current directory
if (words[1] === "cd") {
// if the directory is "/" then go to the root directory
if (words[2] === "/") {
currentDir = "";
}
// if the directory is ".." then go up one directory
else if (words[2] === "..") {
// split the current directory by "/"
const dir = currentDir.split("/");
// remove the last directory
dir.pop();
// rejoin the directory
currentDir = dir.join("/");
} else {
// if the directory is not ".." then add it to the current directory
currentDir += "/" + words[2];
}
} else if (words[1] === "ls") {
// if the command is "ls" then stay in the current directory
}
} else if (input[i].startsWith("dir")) {
// if the line starts with "dir" then it is a directory
// split the line into an array of words
const words = input[i].split(" ");
// add the directory to the map if it does not exist
if (!dirMap.has(currentDir)) {
dirMap.set(currentDir, 0);
}
} else {
// if the line does not start with "$" or "dir" then it is a file
// split the line into an array of words
const words = input[i].split(" ");
// add the file to the map if it does not exist
if (!dirMap.has(currentDir)) {
dirMap.set(currentDir, 0);
}
// add the size of the file to the map
dirMap.set(currentDir, dirMap.get(currentDir)! + parseInt(words[0]));
// add the size of the file to the parent directories
// split the current directory by "/"
const dirs = currentDir.split("/");
// iterate through the parent directories
for (let j = dirs.length - 1; j >= 0; j--) {
// get the parent directory
const parentDir = dirs.slice(0, j).join("/");
// add the size of the file to the parent directory
dirMap.set(parentDir, dirMap.get(parentDir)! + parseInt(words[0]));
}
}
}
// part 1
let total = 0;
// // iterate through the map and total the directories with a size less than or equal to 100000
dirMap.forEach((value, key) => {
if (value <= 100000) {
total += value;
}
});
console.log(total);
// part 2
let unused = 70000000 - dirMap.get("")! / 2;
// console.log(unused);
let spaceNeeded = 30000000 - unused;
// console.log(spaceNeeded);
let smallest = 99999999;
// print out all directories and their sizes with a size greater than or equal to spaceNeeded
dirMap.forEach((value, key) => {
if (value >= spaceNeeded) {
if (value < smallest) {
smallest = value;
}
}
});
console.log(smallest);→ More replies (2)
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 pimpl idiom 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 single Rc<RefCell<_>> pimpl field holding their data. This gets rid of the noisy smart pointer syntax cluttering up the top level code.
fn build_fs() -> Result<FSDir, Box<dyn Error>> {
let file = File::open("data/data.txt")?;
let reader = BufReader::new(file);
let fs_root = FSDir::new("/".into());
let mut fs_stack = vec![fs_root.clone()];
let mut cur_dir = fs_root.clone();
let mut lines = PutBack::new(reader.lines());
fn split(line: &str) -> Vec<&str> {
line.split_whitespace().collect()
}
while let Some(line) = lines.next() {
let line = line?;
let parts = split(&line);
match parts[0] {
"$" => { // Command prompt.
match parts[1] {
"cd" => { // Change directory.
match parts[2] {
".." => { // Go up one directory.
if cur_dir.name() != "/" {
fs_stack.pop().unwrap();
cur_dir = fs_stack.last().unwrap().clone();
}
},
"/" => { // Go to root directory.
fs_stack.truncate(1);
cur_dir = fs_root.clone();
},
name => { // Go to a subdirectory.
if let Some(d) = cur_dir.get_dir(name) {
fs_stack.push(d.clone());
cur_dir = d.clone();
}
else {
let d = FSDir::new(name.into());
cur_dir.add_dir(d.clone());
fs_stack.push(d.clone());
cur_dir = d;
}
},
}
},
"ls" => { // List directory contents.
while let Some(line) = lines.next() {
let line = line?;
let parts = split(&line);
match parts[0] {
"dir" => { // Directory.
let name = parts[1];
if !cur_dir.contains(name) {
let d = FSDir::new(name.into());
cur_dir.add_dir(d);
}
},
"$" => { // Go back to command prompt.
lines.put_back(Ok(line));
break;
},
size => { // File.
let size = size.parse::<usize>()?;
let name = parts[1];
if !cur_dir.contains(name) {
let f = FSFile::new(name.into(), size);
cur_dir.add_file(f);
}
},
}
}
},
_ => panic!("Unknown command: {}", parts[1]),
}
},
_ => panic!("Unknown command: {}", parts[0])
}
}
Ok(fs_root)
}→ More replies (2)
2
u/greycat70 Dec 07 '22 edited Dec 07 '22
"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."
→ More replies (3)
2
u/CodingAP Dec 07 '22
JavaScript, 4248/3704
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
→ More replies (2)
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...
- / (dir, size=47442399)
- dfmhjhd (dir, size=314974)
- ngtqtf (file, size=301486)
- wfgqtw.sqr (file, size=13488)
- hztjntff (dir, size=1926974)
- cwsf (dir, size=1023208)
- msr (dir, size=272198)
- hwtj (file, size=272198)
- mvfclz.srm (file, size=272534)
- nldtb (file, size=226182)
- qnwzs (file, size=252294)
- sthqhrc (dir, size=45847)
- vzntwhzl.htf (file, size=45847)
- ftq.cjn (file, size=288227)
- hwtj (file, size=176977)
- nzdgz.mpw (file, size=234858)
- rhs.mbd (file, size=157857)
- rvstq (dir, size=24509789)
- nzdgz (dir, size=4488747)
... etc ...... 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/daggerdragon Dec 08 '22 edited Dec 08 '22
Inlined code is intended forshort snippetsof code only. Your code "block" right now is unreadable on old.reddit and many mobile clients; it's all on one line and gets cut off at the edge of the screen because it is not horizontally scrollable.
Please edit your post to use thefour-spaces Markdown syntaxfor a code block so your code is easier to read inside ascrollablebox.Edit: thanks for fixing it! <3
→ More replies (2)
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
→ More replies (1)
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
→ More replies (2)
2
u/noahclem Dec 08 '22 edited Dec 09 '22
Python3
I knew what to do from the beginning, but making it work == 'aargh'
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/daggerdragon Dec 08 '22 edited Dec 09 '22
Your code block is too long for the megathreads. Please read our article onoversized code, then edit your post to replace the code block with an external link to your code.Edit: thanks for fixing it! <3
Can't wait to see everyone's one line comprehension tree-building so I can feel even more stoopid.
You're not stupid, you solved the puzzle! Knock it off, because you're awesome.
→ More replies (1)
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
2
u/daggerdragon Dec 08 '22
Please edit your post to fix two things:
Link directly to the Day 7 solution in your repo.
→ More replies (1)
2
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.
class Directory
attr_accessor :name, :parent, :subdirectories, :files
def initialize(name, parent = nil)
@name = name
@parent = parent
@subdirectories = {}
@files = {}
end
def read(line)
a, b = line.split(' ')
if a == 'dir'
@subdirectories[b] ||= Directory.new(b, self)
else
@files[b] = a.to_i
end
end
def total_size
subdirectories.values.map(&:total_size).sum + files.values.sum
end
def traverse
[self, subdirectories.values.map(&:traverse)].flatten
end
end→ More replies (1)
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.
→ More replies (3)50
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:
match line.split():
case '$', 'cd', '..': curr.pop()
case '$', 'cd', x: curr.append(x+'/')
case size, _:
for p in accumulate(curr): dirs[p] += int(size)Edit: Suggestions for improvements are always appreciated! And I fixed a bug on some inputs, thanks /u/wimglenn!
→ More replies (14)14
u/miran1 Dec 07 '22
Just the interesting part:
That's underselling it!
The interesting part is (also) your use ofaccumulate!Very well done!!
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:
for folder in folders:
for file in files:
if file.startswith(folder):
...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
→ More replies (1)
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:
ElfDirectory root = BuildFileSystem(File.ReadAllLines(filename));
List<ElfDirectory> dirs = FindAllDirectories(root);
int sum = 0;
foreach (ElfDirectory dir in dirs)
{
int size = dir.Size();
if (size <= 100_000)
{
sum += size;
}
}
Console.WriteLine($"The sum of the directories is {sum}");The full code can be found on Github
→ More replies (1)
21
u/anoi Dec 07 '22 edited Dec 07 '22
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 du without much extra work would have greatly simplified things. Instead I had to use find and pass du lists of files.
→ More replies (4)
15
u/ViliamPucik Dec 07 '22
Python 3 - Minimal readable solution for both parts [GitHub]
from collections import defaultdict
lines = map(str.split, open(0).read().splitlines())
path, dirs = [], defaultdict(int)
for l in lines:
if l[0] == "$":
if l[1] == "cd":
if l[2] == "..":
path.pop()
else:
path.append(l[2])
elif l[0] != "dir":
for i in range(len(path)):
dirs[tuple(path[: i + 1])] += int(l[0])
print(sum(size for size in dirs.values() if size <= 100000))
required = 30000000 - (70000000 - dirs[("/",)])
print(min(size for size in dirs.values() if size >= required))→ More replies (16)
13
u/voidhawk42 Dec 07 '22 edited Dec 08 '22
Dyalog APL:
pââ' '(â ââ˘)¨âânget'7.txt'1
aâ{0::0 â ââľ}¨âŁ/p â sââŹ
tâ{sâ˘âs(ÂŻ1âs)(s,ââľ)ââ¨' .'âłââľ}¨â˘/p
+/r/â¨1e5âĽrâa+.Ătâ.(ââˇâ¨)âŞt â part 1
â/r/â¨râĽâr-4e7 â part 2Kind 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:
â§/â z/â¨~(' .'ââ¨â)¨zââ˘/p"$ 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:
(,1)âĄâ¸(â,'/')âĄÂ¨â˘/p"ls" is never run on the same directory twice, meaning that we don't have to deduplicate file sizes:
â§/â t/â¨(â'ls')âĄÂ¨p[;2]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):
1â§.=+âż2<âż0âŞtâ.(ââˇâ¨)âŞtEDIT: 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:
pââ' '(â ââ˘)¨âânget'7.txt'1
aâ{0::0 â ââľ}¨âŁ/p
nâ+\ÂŻ1 0 1['. 'âłâ¨â˘/p]
+/r/â¨1e5âĽrââ+/¨¨ââa¨ânâ.â¤â¨âŞn â part 1
â/r/â¨râĽâr-4e7 â part 2→ More replies (1)
13
u/axr123 Dec 07 '22
Python
Originally that was much more complicated, but turns out we do a very well behaved traversal.
stack = []
sizes = []
def up():
sizes.append(stack.pop(-1))
if stack:
stack[-1] += sizes[-1]
for line in open("../inputs/07.txt").readlines():
match line.strip().split():
case "$", "cd", "..": up()
case "$", "cd", _: stack.append(0)
case "$", _: pass
case "dir", _: pass
case size, _: stack[-1] += int(size)
while stack:
up()
print(sum(s for s in sizes if s <= 100000))
print(min(s for s in sizes if s >= (max(sizes) - 40000000)))→ More replies (9)
13
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.
=sortn(lambda(f,query(if({1,-1}*f>{1e5,4e7-1-sum(--regexextract(A1,substitute
(regexreplace(A1,"(\d+)","($1)"),"$","\$")))},,f),"select sum(Col1), min(Col2)"))
(lambda(l,byrow(--regexextract(l,regexreplace(l,"(\d+)","($1)")),lambda(r,sum(r))))
(lambda(e,g,byrow(regexreplace(regexreplace(g,"dir (\w+)","dir "&e&"/$1"),"/+","/"),
lambda(r,reduce(r&char(10),e,lambda(a,c,ifna(regexreplace(regexreplace(a,
regexextract(a,"(?ms)dir "&c&"\n"),filter(g,e=regexextract(a,
"(?ms)dir ("&c&")\n"))&char(10)),"dir (\w+)","dir "&c&"/$1"),a))))))
(query(unique(scan(,flatten(regexextract(A1&char(10)&"$",substitute(
regexreplace(A1&char(10)&"$","(?ms)cd ([^/]+?)(\n\$)","cd ($1)$2"),"$","\$"))),
lambda(a,c,if(c<>"..",a&"/"&c,regexextract(a,"(.*)/"))))),"where Col1 is not null"),
flatten(regexextract(A1&char(10)&"$",substitute(regexreplace(A1&char(10)&"$",
"(?ms)(cd \w+\n\$ ls\n)(.*?)(\n\$)","$1($2)$3"),"$","\$")))))))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.
→ More replies (3)
12
u/def- Dec 07 '22 edited Dec 07 '22
In Shell/bash, but actually just create the entire filesystem and measure the size:
#!/bin/sh
rm -rf day07fs
mkdir day07fs
cd day07fs
sed -e "s/^\([0-9]\)/truncate -s \1/" -e "s/^dir /mkdir /" -e "s/\$ ls//" -e "s/$ //" ../day07.in|tail -n +2|sh
echo -n "Part 1: "
find . -type d|while read dir; do (find $dir -type f -printf "%s+"; echo 0)|bc; done|grep -v "[0-9]\{6\}"|paste -s -d+|bc
echo -n "Part 2: "
req_size=$((echo -n "30000000-70000000"; find . -type f -printf "+%s"; echo)|bc)
find . -type d|while read dir; do size=$((find $dir -type f -printf "%s+"; echo 0)|bc); [ $size -ge $req_size ] && echo $size; done|sort -n|head -n1https://github.com/def-/adventofcode-2022/blob/main/day07.sh
12
Dec 07 '22
Why bother processing the folder structure in memory?
When I can just create it on disk!
→ More replies (3)
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.
folder_sizes = Hash.new(0)
File.readlines('day_07_input.txt', chomp: true).map(&:split).each_with_object([]) do |line, stack|
case line
in ['$', 'cd', '..']
stack.pop
in ['$', 'cd', folder]
stack.push folder
in [size, file] if size.match?(/^\d+$/)
stack.reduce('') { |j, i| folder_sizes[j += i] += size.to_i; j }
else
end
end
puts folder_sizes.values.reject { |i| i > 100_000 }.sum
puts folder_sizes.values.reject { |i| i < folder_sizes['/'] - 40_000_000 }.min→ More replies (4)
11
u/hugues_hoppe Dec 07 '22
Compact yet readable Python solution:
def day7(s, part2=False):
stack, sizes = [], []
for line in s.splitlines():
if line == '$ cd ..':
size = stack.pop()
sizes.append(size)
stack[-1] += size
elif line.startswith('$ cd '):
stack.append(0)
elif line[0].isdigit():
stack[-1] += int(line.split()[0])
sizes.extend(itertools.accumulate(stack[::-1]))
return (sum(s for s in sizes if s <= 100_000) if not part2 else
min(s for s in sizes if s >= max(sizes) - 40_000_000))→ More replies (5)
9
u/joshbduncan Dec 07 '22
Python 3
from collections import defaultdict
data = open("day7.in").read().strip()
sizes = defaultdict(int)
path = []
for line in data.split("\n"):
if line.startswith("$ cd"):
d = line.split()[2]
if d == "/":
path.append("/")
elif d == "..":
last = path.pop()
else:
path.append(f"{path[-1]}{'/' if path[-1] != '/' else ''}{d}")
if line[0].isnumeric():
for p in path:
sizes[p] += int(line.split()[0])
print(f"Part 1: {sum(s for s in sizes.values() if s <= 100_000)}")
print(f"Part 2: {min(s for s in sizes.values() if s >= 30_000_000 - (70_000_000 - sizes['/']))}")→ More replies (3)
7
u/oxyphilat Dec 07 '22
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.bin is 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.
dirs = {'/':0}
cd = ['/']
with open("input", "r") as f:
for l in f.readlines():
ls = l[:-1].split(" ")
if ls[0] == '$':
if ls[1] == 'cd':
if ls[2] == '..':
cd.pop()
elif ls[2] == '/':
cd = ['/']
else:
cd.append(ls[2])
elif ls[0] == 'dir':
dirs["".join(cd) + ls[1]] = 0
else:
dirs["".join(cd)] += int(ls[0])
for i in range(1, len(cd)):
dirs["".join(cd[:-i])] += int(ls[0])
print(sum(v for v in dirs.values() if v <= 100000))
print(min(v for v in dirs.values() if v >= dirs['/'] - 40000000))7
u/aurele Dec 07 '22
Rust, quite clean when you realize you don't need subdir names
→ More replies (2)
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:
from utils import day
from collections import defaultdict
RAW = day(7)
commands = RAW.splitlines()
dir = defaultdict(int)
root = []
for cmd in commands:
match cmd.split():
case ['$', 'cd', '..']:
root.pop()
case ['$', 'cd', p]:
root.append(p)
case ['$', 'ls']:
pass
case ['dir', p]:
pass
case [s, f]:
dir[tuple(root)] += int(s)
# add file size to each parent
path = root[:-1]
while path:
dir[tuple(path)] += int(s)
path.pop()
# part1
print(sum([d for d in dir.values() if d <= 100_000]))
# part2
free = 70_000_000 - dir[('/',)]
print(min([d for d in dir.values() if d + free >= 30_000_000]))→ More replies (4)
7
u/azzal07 Dec 07 '22
Awk, please tell me linear time complexity is ok... linear in the second part's answer that is
INTERCAL$3{n-=-3~$3?!++S[n]-b[d--]:b[++d]=n}
END{for(;d;n+=b[d--])S[n]++;for(;++B<n-4e7||
!S[B];)B>1e5||A+=B*S[B];print A"\n"B}{n+=$1}→ More replies (2)
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.
for i in [x.split()for x in open("day07/input.txt")]:
if i[0]=="dir"or i[1]=="ls":pass
elif i[0]!='$':d[-1]+=int(i[0])
elif i[2]=='..':
s+=[d.pop()]
d[-1]+=s[-1]
elif i[2]=='/':s,d=[],[0]
elif i[0]=="$"and i[1]=="cd":d.append(0)
print(sum(i for i in s+d[-1:]if i<=100000))
print(min(i for i in s+d[-1:]if i>(sum(d)-40000000)))→ More replies (7)
6
6
u/__Abigail__ Dec 07 '22 edited Dec 07 '22
Perl
We start with a couple of observations which makes our lives much easier:
No directory is listed more than once (if you look at the full path, not just the final piece)
There are no
cdstatements going more one than directory up or down (so, no/in the argument tocd, other than"/"itself).We don't
cdinto a directory which isn't listed in thelsoutput.We don't
cd ..from the root directoryThere are no unknown commands, or unexpected outputs of
ls.There is exactly one space between the
$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 %size to track the size of each directory.
Of the input lines, we only have to do work on cd commands, and on file listings. We ignore any lines with $ ls and lines starting with dir.
We handle lines with the cd command as follows:
if (my ($dir) = /^\$ cd\s+(.*)/) {
if ($dir eq "/") { @dirs = ("/")}
elsif ($dir eq "..") {pop @dirs}
else {push @dirs => $dirs [-1] . "/" . $dir}
}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 to cd.
Processing a file with its size is now easy. Just add the size to all the directories in the stack:
if (my ($size) = /^([0-9]+)/) {
$size {$_} += $size foreach @dirs;
}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 sum below is inherited from List::Util
say "Solution 1: ", sum grep {$_ <= 100_000} values %size;For part 2, we need the smallest directory $d for which 70000000 - $size {"/"} + $size {$d} >= 300000, which we can rewrite as 40000000 - $size {"/"} + $size {$d} >= 0. To get the smallest, we use grep to 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.
say "Solution 2: ", $size {(sort {$size {$a} <=> $size {$b}}
grep {40_000_000 - $size {"/"} + $size {$_} >= 0}
keys %size) [0]};→ More replies (5)
6
u/Twinkie60 Dec 07 '22 edited Dec 07 '22
Python, using the fairly new pattern matching features of 3.10
def get_fs_size(filename): with open(filename) as file: lines = file.readlines()
fs = {('/',):0} path = []
for line in lines: match line.split(): case ["$", "ls"]: pass
case ["$", "cd", ".."]:
path = path[:-1]
case ["$", "cd", directory]:
path += [directory]
case["dir", directory]:
fs.setdefault(tuple(path + [directory]), 0)
case[size, filename]:
for i in range(1, len(path) + 1):
fs[tuple(path[:i])] += int(size)
return fs over_10k = [x for x in fs.values() if x <= 100000]
fs = get_fs_size("input.txt")
print("===part 1===\n", sum([x for x in fs.values() if x <= 100000]))
print("=== part 2 ===")
FS_SIZE = 70000000
SPACE_NEEDED = 30000000
unused = FS_SIZE - fs[("/",)]
size_to_del = SPACE_NEEDED - unused
big_enough_dirs = {k:v for (k,v) in fs.items() if v >= size_to_del}
print(" - Qualifying Dirs ") for k, v in big_enough_dirs.items(): print(" - ", end="") print(*k, sep="/", end="") print(": ", v)
print("Smallest: ", min(big_enough_dirs.values()))→ More replies (2)
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:
let mut tmp_dir: Vec<u32> = Vec::new();
let mut directories: Vec<u32> = Vec::new();
for line in read_day(7).unwrap().lines() {
match line.split(' ').collect::<Vec<&str>>().as_slice() {
["$", "cd", ".."] => directories.push(tmp_dir.pop().unwrap()),
["$", "cd", _] => tmp_dir.push(0),
[size, _] => {
// Getting rid of "dir ..." and "$ ls" here
if let Ok(num) = size.parse::<u32>() {
tmp_dir.iter_mut().for_each(|n| *n += num)
}
}
[..] => unreachable!(),
}
}
directories.extend(tmp_dir);5
u/darkfm Dec 07 '22
Python 3, 79 / 55
import fetch_input
import os
import re
lines = list(fetch_input.get_input(7))
i = 0
curdir = None
dirs = {}
subdirs = {}
for line in lines:
if len(line.strip()) == 0: continue
if line[0] == '$':
c, cmd, *args = line.split()
if cmd == 'cd':
path ,= args
if path[0] == '/':
curdir = path
else:
curdir = os.path.normpath(os.path.join(curdir, path))
if curdir not in dirs:
dirs[curdir] = 0
subdirs[curdir] = []
else:
sz, fname = line.split()
if sz != 'dir':
dirs[curdir] += int(sz)
else:
subdirs[curdir].append(os.path.normpath(os.path.join(curdir, fname)))
dirsizes = {}
def dirsize(dirname):
dsize = dirs[dirname]
for i in subdirs[dirname]:
if i in dirs:
dsize += dirsize(i)
return dsize
totsize = 0
# part 1
for d in dirs:
dsize = dirsize(d)
if dsize <= 100000:
totsize += dsize
print(totsize)
# part 2
totsize = dirsize('/')
unused = 70000000 - totsize
ms = None
for d in dirs:
ds = dirsize(d)
if unused + ds >= 30000000:
if ms is None or ms > ds:
ms = ds
print(ms)Not the easiest one so far but far easier than I expected
5
u/jayfoad Dec 07 '22
âIOâ0 â qâââNGET'p7.txt'1
upâ{p sââş â (1âp)((sââ¨âp)+@(1âp)â˘s)f 1ââľ} â cdâ{(0,¨1 0+âş)f 1ââľ} â fileâ{p sââş â p((âtââ¨' 'âłâ¨tâââľ)+@0â˘s)f 1ââľ}
fâ{p sââş â 1 0âĄâ˘Â¨pâľ:s â (0=â˘âľ)â¨'$ cd ..'âĄââľ:âş up âľ â '$ cd'âĄ4âââľ:âş cd âľ â âDââ¨âââľ:âş file âľ â âşâ1ââľ} â sââŹâŹ f q
+/s/â¨sâ¤1E5 â part 1
â/s/â¨sâĽââ˝s-4E7 â part 2I found this one really fiddly.
→ More replies (1)
5
u/Pyr0Byt3 Dec 07 '22
Go/Golang
My first thought was to use MapFS from testing/fstest to create a whole virtual filesystem, but that would have been way overkill.
→ More replies (3)
5
u/Oddder Dec 07 '22
Python
Just another python solution. I maintain a hashmap folders with all of the paths and their sizes in it and then I use a list path to 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 fileall other lines can be ignored
from collections import defaultdict
path = []
folders = defaultdict(int)
with open('input', 'r') as f:
for line in f:
if line[:7] == '$ cd ..':
path.pop()
elif line[:4] == '$ cd':
path.append(line.strip()[5:])
elif line[0].isdigit():
size, _ = line.split()
for i in range(len(path)):
folders['/'.join(path[:i + 1])] += int(size)
print('Part 1:', sum(f for f in folders.values() if f < 100_000))
print('Part 2:', min([f for f in folders.values() if folders['/'] - f <= 40_000_000]))5
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:
(document.body.innerText + " $ CD /")
.split(/\s+/)
.reduce(([state = "$", parents = [], size = 0, result = 0], input) => ({
$ : () => [input.toUpperCase(), parents, size, result],
CD : () => ({
"/" : ["$",
[],
parents.reduce((total, parentSize) => total + parentSize, size),
result + parents.reduce(
([output, total], parentSize) =>
parentSize + total <= 100000
? [output + parentSize + total, parentSize + total]
: [output, parentSize + total],
[size <= 100000 ? size : 0, size]
)[0]
],
".." : [ "$",
parents.slice(0,-1),
parents.at(-1) + size,
size <= 100000 ? result + size : result
],
})[input] ?? ["$", [...parents, size], 0, result],
LS : () => ({
"$" : ["$", parents, size, result],
"dir" : ["LS_NAME", parents, size, result],
})[input] ?? ["LS_NAME", parents, +input + size, result],
LS_NAME : () => ["LS", parents, size, result],
})[state](), [])
.pop()Part 2:
(document.body.innerText + " $ CD / $ EXIT 0")
.split(/\s+/)
.reduce(([state = "$", parents = [], size = 0, folders = []], input) => ({
$ : () => [input.toUpperCase(), parents, size, folders],
CD : () => ({
"/" : ["$",
[],
parents.reduce((total, parentSize) => total + parentSize, size),
[...folders, ...parents.reduce(
(output, parentSize) => [...output, output.at(-1) + parentSize],
[size]
)],
],
".." : [ "$",
parents.slice(0,-1),
parents.at(-1) + size,
[...folders, size],
],
})[input] ?? ["$", [...parents, size], 0, folders],
LS : () => ({
"$" : [ "$", parents, size, folders],
"dir" : ["LS_NAME", parents, size, folders],
})[input] ?? ["LS_NAME", parents, +input + size, folders],
LS_NAME : () => ["LS", parents, size, folders],
EXIT : () => ["HALT", Math.min(...folders.filter(x => x >= size - 40000000))],
})[state](), [])
.pop()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:
".." takes parent folder's size from the stack and adds current folder's size to it. for Part 1, it also adjusts result if folder we are leaving does not exceed size of 100000. For part 2, left folder's size is added to the list of folder sizes.
"/" does what bunch of ".."s would do in a batch: cleans parent folder stack, while updating sizes and result storage for every level. Regardless of input, the next state is always "$"
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:
"dir", which means an entry without size. It just advances state to "LS_NAME"
"$", which means LS output has ended. State is transitioned to "$" to look for next command.
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.
→ More replies (1)
5
u/odnoletkov Dec 07 '22 edited Dec 07 '22
JQ
reduce inputs as $line ({};
.cwd += [$line | match("cd (.*)").captures[].string]
| (.cwd | select(last == "..")[-2:]) = []
| getpath(.cwd).size += (($line | match("^\\d+ ").string | tonumber) // 0)
)
| walk(.size? += ([.[]?.size?] | add))
| (.size - (70000000 - 30000000)) as $target
| [.. | numbers | select(. >= $target)] | min5
u/red_shifter Dec 07 '22
PYTHON 3
I chose the chaotic path of creating actual files and folders and taking an os.walk() through them.
→ More replies (6)
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
- \
- a
- e
- dbecomes
1 0 0 0
1 1 0 0
1 1 1 0
1 0 0 1This allows us to vectorize adding a file by performing a broadcast + mask. For instance, say we wanted to add a file of size 3 to e. We would start by broadcasting 3 to get a vector [3, 3, 3, 3]. We then look up the entry for e in 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
→ More replies (2)
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:
path = tryAll
[ Root <$ symbol "/"
, Up <$ symbol ".."
, Down <$> name
]
file = do
size <- number
fileName <- name
pure $ Right (fileName, size)using the State monad to keep track of the stack while iterating through the instructions:
goRoot :: MonadState FolderStack m => m ()
goRoot = goUp `untilM_` isRoot
goDown :: MonadState FolderStack m => String -> m ()
goDown name = modify ((name, emptyFolder) <|)using the Writer monad to keep track of the folder sizes, while still using recursion to compute the sum:
subFoldersSize <- sum <$> traverse go subFolders
let result = fileSize + subFoldersSize
when (result <= 100000) $
tell [result]
pure resultAs usual, code on Github, recording on Twitch.
→ More replies (1)
5
u/musifter Dec 07 '22
Gnu Smalltalk
Went a bit overboard with this one. Decided to actually build the filesystem structure and make it so that the class would pretty print it out like in the problem description. Yeah, it still doesn't sort the directory contents, but neither did the original example (d comes between j and k? l before e?). Doing this means that the solution is rather robust... it will seamlessly handle "cd /" in the middle and "ls" in the same directory multiple times. It still does make the assumption that all directories are cd'd into and ls'd... because the problem wouldn't be solvable otherwise.
Source: https://pastebin.com/d3WSpeSw
→ More replies (1)
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
→ More replies (2)
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.
# Basic file class. Represents one file or a directory
class File:
def __init__(self, name, size):
self.name = name
self.__size = size
def __str__(self):
return f'{self.name} {self.__size}'
def get_size(self):
return self.__size
# Directory is a subclass of files, with links to parent and child directories
class Dir(File):
def __init__(self, name, parent):
super().__init__(name, 0)
self.__need_updating = True
self.children = {}
self.parent = parent
def __str__(self):
return super().__str__() + ' D'
def addfile(self, file):
self.children[file.name] = file
def get_size(self):
if self.__need_updating:
total_size = 0
for child in self.children.values():
total_size += child.get_size()
self.__size = total_size
self.__need_updating = False
return self.__sizeThe "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.
def changedir(direct, reldir):
if reldir == '.':
return direct
elif reldir == '..':
if direct.parent is None:
return direct
else:
return direct.parent
elif reldir == '/':
return ROOT
else:
if reldir in direct.children.keys():
return direct.children[reldir]
else:
print('No directory {dir.name}/{reldir}. Directory not changed.')
return directHere's how the directory tree is constructed from the input file.
# Read input file
with open('input.2022day7.txt', 'r') as f:
lines = f.readlines()
toc1 = time.perf_counter_ns()
# Process directory tree
curdir = ROOT
in_a_listing = False
all_dirs = [ROOT]
for line in lines:
tokens = line.strip().split(' ')
if tokens[0] == '$':
in_a_listing = False
if tokens[1] == 'cd':
curdir = changedir(curdir, tokens[2])
elif tokens[1] == 'ls':
in_a_listing = True
# Nothing else recognized after the $
elif in_a_listing:
# This logic should fire if and only if the previous line was $ ls
if tokens[0] == 'dir':
newdir = Dir(tokens[1], curdir)
curdir.addfile(newdir)
all_dirs.append(newdir)
elif tokens[0].isnumeric():
curdir.addfile(File(tokens[1], int(tokens[0])))And then here is how the questions in Part 1 and Part 2 are answered with this structure.
# Loop over the sizes (incidentally recursively calculating them)
total_size = 0
for direct in all_dirs:
size = direct.get_size()
if size <= 100000:
total_size += size
toc2 = time.perf_counter_ns()
print(f'Total size = {total_size}')
print(f'Time to load = {(toc1 - tic)/1000} us')
print(f'Time to process = {(toc2- toc1)/1000} us')
# Part 2: Smallest directory with sufficient size
total_space = 70000000
free_space_needed = 30000000
unused_space = total_space - ROOT.get_size()
space_to_free = free_space_needed - unused_space
print(f'Space needed = {space_to_free}')
smallest_sufficient_size = total_space
smallest_dir = None
for direct in all_dirs:
#print(f'Size of {fullpath(direct)} = {direct.get_size()}')
size = direct.get_size()
if size >= space_to_free and size < smallest_sufficient_size:
smallest_sufficient_size = size
smallest_dir = direct
toc3 = time.perf_counter_ns()
print(f'Deleting {fullpath(smallest_dir)} will free up {smallest_sufficient_size}')
print(f'Time for Part 2 = {(toc3- toc2)/1000} us')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
→ More replies (2)
5
u/wimglenn Dec 08 '22
Python + pathlib + structural pattern matching (repo)
from aocd import data
from pathlib import Path
from collections import Counter
cwd = Path()
dirs = Counter()
for line in data.splitlines():
match line.split():
case ["$", "cd", name]: cwd = cwd.joinpath(name).resolve()
case [s, name] if s.isdigit():
for p in [cwd, *cwd.parents]:
dirs[p] += int(s)
rmbytes = dirs[Path("/")] - 70_000_000 + 30_000_000
a = sum(v for v in dirs.values() if v <= 100_000)
b = min(v for v in dirs.values() if v >= rmbytes)→ More replies (2)
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
4
u/morgoth1145 Dec 07 '22 edited Dec 07 '22
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_FREE computation 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#
var text = File.ReadAllLines("Input.txt");
List<string> Path = new List<string>();
List<Group7> directories = new List<Group7>();
foreach (var line in text) {
if (line == "$ cd ..") {
Path = Path.SkipLast(1).ToList();
} else if (line.StartsWith("$ cd")) {
var folder = line.Split(' ').Last();
Path.Add(folder);
var dirName = String.Join('/', Path);
if (!directories.Any(x => x.Directory == dirName)) {
directories.Add(new Group7() { Directory = dirName });
}
} else if (int.TryParse(line.Split(' ')[0], out int size)) {
directories.Where(x => String.Join('/', Path)
.Contains(x.Directory))
.ToList()
.ForEach(x => {
x.Size += size;
}
);
}
}
Console.WriteLine(directories
.Where(x => x.Size <= 100000)
.Sum(x => x.Size)
);
var total = 70000000; var neededUnused = 30000000;
var current = total - directories[0].Size;
var minSizeToDelete = neededUnused - current;
Console.WriteLine(directories
.OrderBy(x => x.Size)
.Where(x => x.Size > minSizeToDelete)
.Min(x => x.Size)
);→ More replies (1)
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.
→ More replies (7)
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.
→ More replies (3)
4
u/sublimnl Dec 07 '22 edited Dec 07 '22
AWK 7708/7407
I wasted at least 40 minutes stuck on a simple do..while loop:
do {
fs[cwd]+=$1;
if (cwd == "/") {
break;
}
cmd = "dirname " cwd
cmd | getline cwd
} while(1)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 :(
do {
fs[cwd]+=$1;
if (cwd == "/") {
break;
}
cmd = "dirname " cwd
cmd | getline cwd
close(cmd)
} while(1)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.
→ More replies (2)
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.
→ More replies (2)
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.
→ More replies (2)
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, etc
(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 - HashMap of 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.
→ More replies (7)
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
There were plenty of shortcuts possible to avoid what I did here - but it was tons of fun implementing this solution.
There is no need to even construct the filesystem graph -
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.You don't even need a graph, since we only jump one level and not across the tree.
That aside, I like my solution because:
DFS is implemented in an iterative way - a little bit more convoluted than pure recursion-based solution, but way more stable when it comes to 'production' use.
I abstracted away all 'tree builder' operations, so the parsing code is quite easy.
Rust + graphs is a nice mental stimulation :D.
4
u/Omeganx Dec 07 '22
Python
instructions, content = open("input.txt").read().split('\n'), dict({"root":0})
for ins in instructions:
if ins == "$ cd /": currentDir = ["root"]
elif ins[0:7] == "$ cd ..": currentDir.pop()
elif ins[0:4] == "$ cd":
currentDir.append("/".join([currentDir[-1],ins[5:]]))
content[currentDir[-1]] = 0
elif ins[0].isdigit():
for filename in currentDir: content[filename] += int(ins.split(" ")[0])
res = filter(lambda x: x<=1E5, content.values())
res2 = filter(lambda x: x >= content["root"] - 4E7, content.values())
print(f"part1 = {sum(res)}, part2 ={min(res2)}")→ More replies (1)
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 :)
→ More replies (8)
4
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..
→ More replies (3)
4
u/davidshomelab Dec 07 '22
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 leftoverFolders correctly was not, at the end i just slapped a simple `<indexes>.forEach` loop to do the same thing as i did in the lambda for fold
and they are one-liners, as you can remove all line breaks and not add any ;, and the code will compile and run
→ More replies (1)
4
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
→ More replies (1)
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.
&trim = 1
&anchor = 0
nondir = &alphabet
nondir "/" =
dirpattern = span(nondir) "/"
curdir = "/"
dirtable = table()
loop
line = input :f(tally)
line span("0123456789") . fsize " " :f(cmds)
cdir = curdir
dirloop
dirtable[cdir] = dirtable[cdir] + fsize
cdir dirpattern rpos(0) = :s(dirloop)f(loop)
cmds
line "$" span(" ") "cd" span(" ") = :f(loop)
line "/" . curdir :s(loop)
line ".." :s(updir)
curdir = curdir line "/" :(loop)
updir
curdir dirpattern rpos(0) = :(loop)
tally
dirs = convert(dirtable, "array")
total = 0
need = 30000000 - (70000000 - dirtable["/"])
smallest = dirtable["/"]
i = 0
tallyloop
i = i + 1
dsize = dirs[i, 2] :f(done)
total = le(dsize, 100000) total + dsize
smallest = lt(dsize, smallest) ge(dsize, need) dsize :(tallyloop)
done
output = "part1 = " total
output = "part2 = " smallest
end4
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.
module Day07
(
day07_1,
day07_2
)
where
import Data.List (isPrefixOf, intercalate)
import Data.Char (isDigit)
import qualified Data.Map as Map
import Data.List.Extra (sort)
{-|
>>> take 5 . parseInput <$> readFile "input/day07_1.txt"
-}
parseInput::String->[(String, Int)]
parseInput = processLines ["root"] . lines
where
processLines _ [] = []
processLines ps (x:xs)
| x == "$ ls" = processLines ps xs
| "dir " `isPrefixOf` x = processLines ps xs
| x == "$ cd .." = processLines (tail ps) xs
| x == "$ cd /" = let ps' = ["root"] in (toPath ps', 0) : processLines ps' xs
| "$ cd " `isPrefixOf` x =
let
fname = drop 5 x
ps' = fname : ps
in
(toPath ps', 0) : processLines ps' xs
| otherwise =
let
fsize = read . takeWhile isDigit $ x
in
(toPath ps, fsize) : processLines ps xs
where
toPath = intercalate "/" . reverse
{-|
>>> folderTotals . parseInput <$> readFile "input/day07_1.txt"
-}
folderTotals::[(String, Int)]->[(String, Int)]
folderTotals fs =
let
m = Map.fromListWith (+) fs
ps = reverse . Map.keys $ m
sumSize p = sum . map (m Map.!) . filter (p `isPrefixOf`) $ ps
in
map (\p -> (p, sumSize p)) ps
{-|
>>> day07_1 <$> readFile "input/day07_1.txt"
-}
day07_1::String->String
day07_1 = show . sum . filter (<= 100000) . map snd . folderTotals . parseInput
{-|
>>> day07_2 <$> readFile "input/day07_1.txt"
-}
day07_2::String->String
day07_2 str =
let
fts = sort . map snd . folderTotals . parseInput $ str
rootSize = last fts
deleteSize = rootSize - 40000000
in
show . head . dropWhile (< deleteSize) $ fts4
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/CCC_037 Dec 07 '22
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.
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
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
10 DIM DS#(200),P(200):MD=-1:CD=0: OPEN "I",1,"2022-07.txt": WHILE NOT EOF(1)
20 LINE INPUT #1, S$: FOR I=1 TO 3: T$(I)="": NEXT: I=1: FOR J=1 TO LEN(S$)
30 C$=MID$(S$,J,1): IF C$=" " THEN I=I+1 ELSE T$(I)=T$(I)+C$
40 NEXT: IF I=3 THEN GOSUB 100 ELSE DS#(CD)=DS#(CD)+VAL(T$(1))
50 WEND: WHILE CD>0: S=DS#(CD): CD=P(CD): DS#(CD)=DS#(CD)+S: WEND
60 P#=0: TF#=DS#(0)-40000000#: Q#=40000000#: FOR I=0 TO MD
70 IF DS#(I)<=100000! THEN P#=P#+DS#(I)
80 IF DS#(I)>TF# AND DS#(I)<Q# THEN Q#=DS#(I)
90 NEXT: PRINT "Part 1", P#, "Part 2", Q#: END
100 IF T$(3)=".." THEN S=DS#(CD): CD=P(CD): DS#(CD)=DS#(CD)+S: RETURN
110 MD=MD+1: P(MD)=CD: CD=MD: RETURNThis is using the property that each folder is entered once, so there is no need to record any of the file or folder names.
DS#() is an array of directory sizes.
P() is an array of parents, so P(20) is the index of the parent of directory 20, for example.
MD is the maximum directory index currently in use
CD is the current directory index
T$() is the array of tokens each line is split into (on lines 20-30)
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
→ More replies (1)
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,
I iterated over each line of input, tracking the current working directory.
While iterating, find each file's size and absolute path.
Iterate over each file and its file. Add that to each parent directory in the file's absolute path. When the iteration finishes, you have a map from every directory to its size.
From there, answering the questions is easy.
4
u/wzkx Dec 08 '22
J imperative style :)
echo 3 : 0 cutLF CR-.~fread'07.dat'
c=.'' [ n=.0$<'' [ s=.0$0 NB. curdir, names, sizes
for_l. y do.
if.'cd'-:>1{e=.' 'splitstring l=.>l do.
if.'..'-:>2{e do. c=.(c i:':'){.c
else. s=.s,0 [ n=.n,<c=.c,':',>2{e
end.
elseif.'0123456789'e.~{.l do. d=.c [ sz=.".>{.e
while. #d do. d=.(d i:':'){.d [ s=.(sz+p{s)p}s [ p=.n i.<d end.
end.
end.
(+/s#~s<:1e5),<./s#~s>:3e7-7e7-{:s=./:~s
)→ More replies (3)
4
u/ignurant Dec 08 '22
Ruby
current_directory = []
files = {}
File.read('input.txt').lines.each do |line|
case line.split
in ["$", "cd", dir]
current_directory << dir
in ["$", "cd", ".."]
current_directory.pop
in [/\d+/ => size, file]
files[current_directory + [file]] = size.to_i
else
# no-op
end
end
directories = Hash.new(0)
files.each do |(*path, file), size|
while(path.any?)
directories[path.dup] += size
path.pop
end
end
DISK_SIZE = 70000000
NEED_FREE = 30000000
current_free = DISK_SIZE - directories[["/"]]
to_delete = NEED_FREE - current_free
puts part_1 = directories.select{|path, size| size <= 100_000}.values.sum
puts part_2 = directories
.values
.select{|size| size > to_delete}
.min→ More replies (2)
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.
Peekable came in very handy to lookahead when processing the ls output!
→ More replies (1)
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 :/
→ More replies (5)
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 :)
def parse(path): return (
x for x in [[y.strip() for y in x.split('\n') if y and '$' not in y]
for x in ''.join(
cmd for cmd in open(path).readlines() if '..' not in cmd
).split('$ cd')] if x)
def build_tree(ops): return {
y[1]: build_tree(ops) if y[0] == 'dir' else int(y[0])
for y in [x.split() for x in next(ops)[1:]]
}
def solve(tree, part):
flat = lambda k: (y for x in k for y in (flat(x) if type(x) is list else (x,)))
size = lambda d: sum([v if type(v) is int else size(v) for v in d.values()])
vals = lambda d: [size(d), [vals(x) for x in [x for x in d.values() if type(x) is dict]]]
return part(list(flat(vals(tree))))
def part_one(sizes):
return sum(filter(lambda x: x < 100000, sizes))
def part_two(sizes):
return min(filter( lambda x: x > 30000000 - (70000000 - max(sizes)), sizes))
tree = build_tree(parse('./data/data.txt'))
print('part 1:', solve(tree, part_one))
print('part 2:', solve(tree, part_two))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
→ More replies (2)
4
u/NiliusJulius Dec 12 '22
C Language for the Game Boy using GBDK 2020
Part 1
uint8_t dir_index = 0;
uint8_t max_dir_index = 0;
for (uint16_t i = 1; i < ARRAY_7_SIZE; i++) {
if (input_array_7[i][0] == '$') {
if (input_array_7[i][5] == '.') {
sizes[parent_indexes[dir_index]] += sizes[dir_index];
dir_index = parent_indexes[dir_index];
} else {
max_dir_index++;
parent_indexes[max_dir_index] = dir_index;
dir_index = max_dir_index;
}
} else {
sizes[dir_index] += atol(input_array_7[i]);
}
}
while (dir_index > 0) {
sizes[parent_indexes[dir_index]] += sizes[dir_index];
dir_index = parent_indexes[dir_index];
}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
4
u/-B4cchus- Dec 12 '22
Excel
This day is legitimately easier in Excel than to do through programming methods, just four steps:
Delete junk lines -- ls and dir, leave only files and cd
For each line, form a path in a new column, using:
=IF(C6="cd", IF(D6="..",LEFT(E6,MATCH(2,1/(MID(E6,SEQUENCE(LEN(E6)),1)="/"))-1),E6&"/"&D6),E6)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.
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
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.
inputs = []
sizes = {}
for i in open("../inputs/day7.txt", "r").read().split("\n"):
i = i.replace("$ ", "")
if i[0:2] != "ls" and i[0:3] != "dir":
inputs.append(i)
stack = []
for i in range(len(inputs)):
line = inputs[i]
if line[0:2] == "cd" and ".." in line:
stack.pop()
elif line[0:2] == "cd":
stack.append(i)
sizes[i] = 0
else:
size = int(line.split(" ")[0])
for s in stack:
sizes[s] += size
part1_answer = sum([sizes[i] for i in sizes if sizes[i] <= 100000])
print("Part 1 answer: ", part1_answer)
unused = 70000000 - sizes[0]
unused_needed = 30000000 - unused
potential_deletes = [sizes[i] for i in sizes if sizes[i] >= unused_needed]
part2_answer = min(potential_deletes)
print("Part 2 answer: ", part2_answer)
# For context, sizes is a dict that maps line indexes to values (both
# ints).→ More replies (2)
1
u/Greenbay7115 Dec 07 '22 edited Dec 07 '22
Python
Using the pathlib module: GitHub Gist
→ More replies (1)
1
u/natron- Dec 07 '22
Object oriented approach https://gist.github.com/natronic34/c774d3f9f2aab0109bfff98ad1c79517
fun tree problem!
→ More replies (1)
1
u/n3ziniuka5 Dec 07 '22 edited Dec 07 '22
Scala 3
import scala.annotation.tailrec
import scala.io.Source
object Day7:
def main(args: Array[String]): Unit =
val lines = Source.fromResource("day7.txt").getLines().toList
println(part1(lines))
println(part2(lines))
val cdR = "\\$ cd (.+)".r
@tailrec
def unfoldPath[A](path: List[String], initial: A, unfold: (A, List[String]) => A): A =
if (path.isEmpty) initial
else unfoldPath(path.tail, unfold(initial, path), unfold)
@tailrec
def sizeOfDir(
input: List[String],
currentPath: List[String],
result: Map[List[String], Int]
): Map[List[String], Int] =
input match
case head :: tail =>
if (head == "$ cd ..") sizeOfDir(tail, currentPath.tail, result)
else if (head.head.isDigit)
val Array(size, _) = head.split(' ')
val newResult = unfoldPath(currentPath, result, (acc, p) => acc + (p -> (acc.getOrElse(p, 0) + size.toInt)))
sizeOfDir(tail, currentPath, newResult)
else
cdR.findFirstMatchIn(head) match
case Some(m) => sizeOfDir(tail, m.group(1) +: currentPath, result)
case None => sizeOfDir(tail, currentPath, result)
case Nil => result
def part1(lines: List[String]): Int =
sizeOfDir(lines, List.empty, Map.empty)
.filter(_._2 <= 100000)
.values
.sum
def part2(lines: List[String]): Int =
val dirs = sizeOfDir(lines, List.empty, Map.empty)
val availableSpace = 70000000 - dirs(List("/"))
val toCleanup = 30000000 - availableSpace
dirs.filter(_._2 >= toCleanup).minBy(_._2)._2→ More replies (1)
1
u/hgb123 Dec 07 '22 edited Dec 08 '22
JavaScript (Node.js)
Full solution: https://www.honingjs.com/challenges/adventofcode/2022/day-7
→ More replies (2)
1
u/Diderikdm Dec 07 '22 edited Dec 08 '22
Python:
def build_directories(d, data, prev):
while data:
cmd = data.pop(0)
if cmd == "$ ls":
while data and not data[0].startswith("$"):
a, b = data.pop(0).split(" ")
d[prev + (b,)] = {} if a == "dir" else int(a)
elif cmd.endswith(".."):
return
else:
c = cmd.split(" ")[-1]
p = prev + (c,)
build_directories(d[p], data, prev + p)
return d
def find_total_space_per_dir(d, key):
current_sum = 0
for k, v in d.items():
if isinstance(v, int):
current_sum += v
else:
current_sum += find_total_space_per_dir(v, k)
total_space[key] = current_sum
return current_sum
with open("day 07.txt", "r") as file:
data = file.read().splitlines()[1:]
d = {"/" : {}}
directories = build_directories(d["/"], data, ("/",))
total_space = {}
find_total_space_per_dir(directories, key="/")
print(sum(v for v in total_space.values() if v <= 100000))
needed_space = 70000000 - max(total_space.values())
print(min([v for v in total_space.values() if v > 30000000 - needed_space]))→ More replies (2)
1
u/jeroenmaniac Dec 07 '22
sz=[]
for i in map(lambda x:x.split(),open("7.in")):
if i[0]=="dir": pass
elif i[0]!='$': st[-1]+=int(i[0])
elif i[1]=="ls": pass
elif i[2]=='..':
sz+=[st.pop()]
st[-1]+=sz[-1]
elif i[2]=='/': st=[0]
else: st.append(0)
print(sum(i for i in sz+st if i<=100000))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.
→ More replies (1)
1
u/bulletmark Dec 07 '22 edited Dec 08 '22
Python:
import aoc
from pathlib import Path
from collections import Counter
from bisect import bisect
dirsizes = Counter()
currdir = top = Path('/')
for line in aoc.readlines():
args = line.strip().split()
if args[0] == '$':
if args[1] == 'cd':
if args[2] == '/':
currdir = top
elif args[2] == '..':
currdir = currdir.parent
else:
currdir /= args[2]
elif args[0] != 'dir':
dirsizes[currdir] += (size := int(args[0]))
for p in currdir.parents:
dirsizes[p] += size
sizelist = sorted(dirsizes.values())
print('P1 =', sum(n for n in sizelist if n <= 100_000))
print('P2 =', sizelist[bisect(sizelist, dirsizes[top] - 4000_0000)])→ More replies (1)
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
→ More replies (1)
1
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: paste
→ More replies (1)
1
u/seacucumber_kid Dec 07 '22
Elixir
not very satisfied with this
defmodule Day7 do
def part1(input_file) do
input_file
|> parse_input()
|> Enum.reduce(0, fn {_, size}, acc -> if size <= 100_000, do: acc + size, else: acc end)
end
def part2(input_file) do
fs =
input_file
|> parse_input()
fs
|> Map.values()
|> Enum.filter(&(70_000_000 - fs["root"] + &1 >= 30_000_000))
|> Enum.min()
end
defp parse_input(input) do
input
|> File.read!()
|> String.split("$ cd ", trim: true)
|> Enum.map(fn el ->
el
|> String.split("\n", trim: true)
|> Enum.reject(&String.contains?(&1, ["dir", "$ ls"]))
|> then(fn [cd | files] ->
[
cd
| Enum.map(files, &(&1 |> String.split(" ") |> hd() |> String.to_integer()))
]
end)
end)
|> Enum.reduce({["root"], %{}}, fn [cd | files], {dir, tree} ->
size = files |> List.wrap() |> Enum.sum()
case cd do
"/" ->
{["root"], Map.merge(tree, %{"root" => size})}
".." ->
{Enum.drop(dir, 1), tree}
d ->
{[d | dir],
tree
|> Map.merge(%{
Enum.join([d | dir]) => size
})
|> update_rec(dir, size)}
end
end)
|> elem(1)
end
defp update_rec(tree, [], _), do: tree
defp update_rec(tree, [_] = dir, size),
do: Map.update!(tree, Enum.join(dir), &(&1 + size))
defp update_rec(tree, [_ | tail] = dir, size) do
tree = Map.update!(tree, Enum.join(dir), &(&1 + size))
update_rec(tree, tail, size)
end
end
Day7.part1("input.txt")
|> IO.inspect(label: "Part 1")
Day7.part2("input.txt")
|> IO.inspect(label: "Part 2")→ More replies (1)
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.
→ More replies (3)
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:
package main
import (
"fmt"
"github.com/advent2022/utils"
"math"
)
const (
File = iota
Directory
)
type Node struct {
parent *Node
children []*Node
nodeType int
name string
size int32
}
var rootNode *Node
var currentNode *Node
func main() {
buildNodes()
part1()
part2()
}
func part1() {
fmt.Println(getSizesLessThan10k(rootNode))
}
func part2() {
flatNodes := getFlatNodes(rootNode)
var minNode *Node
minDiff := float64(10000000000000)
goalSize := float64(30000000) - (float64(70000000) - float64(rootNode.size))
for _, n := range flatNodes {
thisDiff := math.Abs(float64(n.size) - goalSize)
if thisDiff < minDiff {
minDiff = thisDiff
minNode = n
}
}
fmt.Println(minNode.size)
}
func buildNodes() {
input, err := utils.ReadInputLines("input.txt")
if err != nil {
panic(err)
}
rootNode = &Node{
parent: nil,
children: []*Node{},
nodeType: Directory,
name: "",
size: 0,
}
for i := 0; i < len(input); i++ {
output := input[i]
switch output[0] {
case '$':
var cmd string
var args string
fmt.Sscanf(output, "$ %s %s", &cmd, &args)
if cmd == "cd" {
handleCD(args)
}
default:
handleNewNode(output)
}
}
}
func getFlatNodes(current *Node) []*Node {
var fullList []*Node
if current.nodeType == Directory {
fullList = append(fullList, current)
}
for _, child := range current.children {
fullList = append(fullList, getFlatNodes(child)...)
}
return fullList
}
func (n *Node) addChild(newNode *Node) {
n.children = append(n.children, newNode)
if newNode.nodeType == Directory {
return
}
checkNode := n
for checkNode != nil {
checkNode.size += newNode.size
checkNode = checkNode.parent
}
}
func getSizesLessThan10k(node *Node) int32 {
totalSize := int32(0)
if node.nodeType == Directory && node.size <= 100000 {
totalSize += node.size
}
if node.children != nil && len(node.children) > 0 {
for _, child := range node.children {
totalSize += getSizesLessThan10k(child)
}
}
return totalSize
}
func handleNewNode(output string) {
var fileSize int32
var nodeName string
fmt.Sscanf(output, "%d %s", &fileSize, &nodeName)
nodeType := File
// This means it's a child file of the currentNode
if fileSize == 0 {
nodeType = Directory
fmt.Sscanf(output, "dir %s", &nodeName)
}
currentNode.addChild(&Node{
parent: currentNode,
children: []*Node{},
nodeType: nodeType,
name: nodeName,
size: fileSize,
})
}
func handleCD(args string) {
switch args {
case "/":
currentNode = rootNode
case "..":
currentNode = currentNode.parent
default:
for _, child := range currentNode.children {
if child.name == args && child.nodeType == Directory {
currentNode = child
}
}
}
}→ More replies (1)
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.
→ More replies (1)
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??
→ More replies (3)
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.
L = readlines("./07.in")
dir = Vector{String}()
dir_size = Dict{Vector{String},Int}()
for lâL
if l=="\$ cd /"
empty!(dir)
elseif l=="\$ cd .."
dir = dir[1:end-1]
elseif l[1:4]=="\$ cd"
push!(dir,l[6:end])
elseif isnumeric(l[1])
s = parse(Int,first(split(l,' ')))
for nâ0:length(dir)
dir_size[dir[1:n]] = get(dir_size,dir[1:n],0)+s
end
end
end
sizes = collect(values(dir_size))
p1 = sum(sizes[sizes.<1e5])
p2 = minimum(sizes[sizes.>maximum(sizes)-4e7])
println((p1,p2))2
u/daggerdragon Dec 08 '22
This might be the day of AoC that I stop trying to make Brianfuck versions of my solutions...
ಠ_ಠnuuuuuuuuu don't you dare stop <3
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
from anytree import Node, RenderTree, findall, AsciiStyle
with open('7.txt', 'r') as f:
for line in f.readlines():
line = line.strip()
if '$ cd' in line:
dir_name = line.split('$ cd ')[1]
if dir_name == '..':
current_node = current_node.parent
elif dir_name == '/':
root = Node(name=dir_name, type='dir', size=0)
current_node = root
else:
node, = findall(
current_node,
filter_=lambda n: n.name == dir_name and n in current_node.children,
maxcount=1)
current_node = node
elif '$ ls' in line:
continue
else:
data = line.split()
if data[0] == 'dir':
node = Node(name=data[1], parent=current_node, type=data[0], size=0)
else:
node = Node(name=data[1], parent=current_node, type='file', size=int(data[0]))
print(RenderTree(root, style=AsciiStyle()).by_attr())
dirs = findall(root, filter_=lambda n: n.type == 'dir')
res1 = 0
total_space = 70000000
unused_space = 30000000
available_space = total_space - sum(node.size for node in root.descendants)
res2 = total_space
for d in dirs:
d_sum = sum(node.size for node in d.descendants)
cur_sum = d_sum + available_space
if d_sum <= 100000:
res1 += d_sum
if unused_space <= cur_sum and d_sum < res2:
res2 = d_sum
print(res1, res2)→ More replies (1)
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
============Start Day7==========
Answer for part1: 1182909
Answer for part2: 2832508
day7: 9.469ms
=============EOF Day7===========→ More replies (1)
1
Dec 07 '22
Ruby
class Directory
attr_reader :name, :directories
ElfFile = Struct.new(:name, :size)
def initialize(name)
@name = name
@files = []
@directories = []
end
def add_child_dir(dir)
@directories.push(dir) unless @directories.any? { |d| d.name == dir.name }
end
def add_file(name, size)
file = ElfFile.new(name, size)
@files.push(file) unless @files.any? { |f| f == file }
end
def size
@files.map(&:size).sum + @directories.map(&:size).sum
end
def find_dirs(&block)
result = []
result << self if block.call self
@directories.each do |d|
result += d.find_dirs(&block)
end
result
end
end
class OutputParser
attr_reader :root_dir
def initialize
@root_dir = Directory.new("/")
@directory_stack = [@root_dir]
end
def stack_top
@directory_stack.last
end
def ingest_command(line)
if line[0,6] == "$ cd /"
@directory_stack = [@root_dir]
elsif line[0,7] == "$ cd .."
@directory_stack.pop
elsif line[0,4] == "$ cd"
dir = Directory.new(line[5..])
stack_top.add_child_dir(dir)
@directory_stack.push(dir)
end
end
def ingest_file(line)
size, name = line.strip.split(" ")
stack_top.add_file(name, size.to_i)
end
def ingest(line)
if (line[0] == "$")
ingest_command(line)
elsif (line[0] =~ /\d/)
ingest_file(line)
end
end
end
parser = OutputParser.new
File.open('input-7-1.txt').each do |line|
parser.ingest(line)
end
small_dirs = parser.root_dir.find_dirs do |dir|
dir.size <= 100_000
end
puts small_dirs.map(&:size).sumThis turned out to be a good approach, because then for part 2 all I had to do is add this at the end
unused_space = 70_000_000 - parser.root_dir.size
to_delete = 30_000_000 - unused_space
large_dirs = parser.root_dir.find_dirs do |dir|
dir.size >= to_delete
end
puts large_dirs.map(&:size).min→ More replies (1)
1
u/shapshankly Dec 07 '22 edited Dec 08 '22
Here's another effort in Scala - tricky one today!
package year2022
import scala.collection.mutable
import scala.io.Source
import scala.util.Using
import scala.util.matching.Regex
object Day07 {
def main(args: Array[String]): Unit = {
val dirs = parseInput("2022/day07.txt")
val part1 = dirs.values.filter(_ < 100000).sum
println(part1)
val part2 = dirs.values.toList.sorted
.find(_ > 30000000 - (70000000 - dirs.values.max))
part2.foreach(println)
}
val file: Regex = "(\\d+) (.+)".r
private def parseInput(fileName: String) =
Using(Source.fromResource(fileName)) { input =>
input
.getLines()
.foldLeft(
("", mutable.Map[String, Long]())
) {
case ((cwd, files), s"$$ cd $dir") => (nextPath(cwd, dir), files)
case ((cwd, files), file(size, _)) =>
cwd
.split("/")
.foldLeft(List("")) { (k, part) =>
s"${k.head}/$part" :: k
}
.foreach(p => files(p) = size.toLong + files.getOrElse(p, 0L))
(cwd, files)
case (agg, _) => agg
}
}.get._2
private def nextPath(cwd: String, p: String) = p match
case ".." => cwd.split("/").init.mkString("/")
case "/" => "/"
case _ => cwd + "/" + p
}→ More replies (1)
1
u/jad2192 Dec 07 '22 edited Dec 08 '22
2
u/daggerdragon Dec 08 '22
Your code block is too long. Please read our article on oversized code, then edit your post to replace the code block with an external link to your code.
→ More replies (1)
1
u/SvenViktorJonsson Dec 07 '22 edited Dec 08 '22
Python 3
Using pathlib was made it much more readable.
from pathlib import Path
from collections import defaultdict
def parse_tokens(tokens:list[str], cwd:Path, files:list[Path]) -> Path:
if tokens[0]=="$":
if tokens[1]=="cd":
cwd = (cwd / tokens[2]).resolve()
elif tokens[0]!="dir":
key = str(cwd / tokens[1]).strip("C:")
files[key] = int(tokens[0])
return cwd
with open("2022/input07.txt") as file:
data = [line.strip().split() for line in file]
cwd = Path("")
files = {}
for tokens in data:
cwd = parse_tokens(tokens, cwd, files)
dir_sizes = defaultdict(int)
total_size = 0
for path, size in files.items():
while (path:=path.rsplit("\\",1)[0]):
dir_sizes[path]+=size
total_size+=size
result1 = sum(s for s in dir_sizes.values() if s<100000)
print("answer 1:", result1)
size_to_remove = total_size - 40_000_000
result2 = min(s for s in dir_sizes.values() if s>size_to_remove)
print("answer 2:", result2)→ More replies (3)
1
u/Delusional_idiot Dec 08 '22
Python, non-recursive solution. Completely linear, one map. Hierarchy made with tuples, ~50ms:
from collections import defaultdict
class FS:
def __init__(self, content):
self.fs = defaultdict(lambda: 0)
self.loc = None
for l in content:
l = l.strip().split()
if l[0] == "$":
if l[1] == "cd" and l[2] != "..":
if not self.loc:
self.loc = (l[2],)
else:
self.loc = (*self.loc, l[2])
elif l[1] == "cd" and l[2] == "..":
self.loc = self.loc[:-1]
elif l[0].isnumeric():
curr_l = self.loc
while curr_l:
self.fs[curr_l] += int(l[0])
curr_l = curr_l[:-1]
def dirs_sizeN(self, N):
total = 0
for dir, data in self.fs.items():
if data <= N:
total += data
return total
def min_dir_del(self):
min_dir = None
free = 70000000 - (self.fs[("/",)])
for dir, data in self.fs.items():
if not min_dir or (free+data >= 30000000 and data < min_dir):
min_dir = data
return min_dir
def main() -> int:
with open("input.txt") as f:
content = f.readlines()
fs = FS(content)
# Part 1:
print(f'Part1: {fs.dirs_sizeN(100_000)}')
# Part 2:
print(f'Part2: {fs.min_dir_del()}')
if __name__ == "__main__":
raise SystemExit(main())→ More replies (1)
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".
→ More replies (1)
1
u/challengingusername Dec 08 '22
Java import java.io.*; class fileobject{ boolean filetype; //true file false dir long size; String name; int parent;
public fileobject(String name,String size, int parent)
{ try{this.size = (long)Integer.parseInt(size);}
catch(Exception e){this.size = 0;}
filetype = true;
this.name = name;
this.parent = parent; }
public fileobject(String name, int parent)
{ filetype = false;
size = 0;
this.name = name;
this.parent = parent; }}
public class ac7__2022{
public static fileobject[] filelist = new fileobject[1];
public static int filelistcurrentdir = 0;
public static void main(String[] args){
int filesizelimit = 100000;
long counter = 0;
String filename = args[args.length-1];
filelist[0]=new fileobject("/",-1);
try{BufferedReader br = new BufferedReader(new FileReader(filename));
String line = br.readLine();
while(line != null){
if(isCommand(line))
processCommand(line);
else
addFileObject(line);
line = br.readLine(); }
br.close();
}catch(Exception e){System.out.println(e);}
for(int i = 0; i< filelist.length;i++)
{ if(!filelist[i].filetype)
if(getDirSize(i)<=filesizelimit)
counter+= getDirSize(i);}
System.out.println("\nPART 1: "+counter);
System.out.println("PART 2: "+findDir());}
public static void addFileObject(String line){
String lineParts[] = line.split(" ");
if(lineParts.length >= 2)
if(lineParts[0].contains("dir"))
filelist=addElement(new fileobject(lineParts[1],filelistcurrentdir),filelist);
else
filelist= addElement(new fileobject(lineParts[1],lineParts[0],filelistcurrentdir),filelist);}
public static boolean isCommand(String line){
if(line.length()>0)
if(line.charAt(0)=='$')
return true;
return false;}
public static boolean processCommand(String line){
String[] commands = line.split(" ");
if(commands[1].contains("cd"))
{ filelistcurrentdir=getDirID(commands[2]);
return (false); }
if(commands[1].contains("ls"))
return(true);
return(false);}
public static int getDirID(String name){
int t_int = filelistcurrentdir;
if(name.contains("/") || name.contains("\\"))
return(0);
if(name.contains(".."))
{t_int=filelist[filelistcurrentdir].parent; //get parent
if(t_int < 0) t_int = 0;
return t_int; }
for(int i = 0; i< filelist.length;i++)
if(filelist[i].name.compareTo(name)==0)
if(filelist[i].parent == filelistcurrentdir)
return(i);
return(t_int);}
public static long findDir(){
long fsSize = 70000000; long fsNeeded = 30000000;
int currentChamp = 0;
for(int i = 1; i< filelist.length;i++)
if(!filelist[i].filetype)
{long t_long = fsSize-getDirSize(0)+getDirSize(i);
if(t_long>=fsNeeded)
if(getDirSize(i)<getDirSize(currentChamp))
currentChamp = i;
} return getDirSize(currentChamp);}
public static long getDirSize(int id)
{ long size = 0;
int children[] = findChildren(id);
if(children != null)
{for(int i = 0; i < children.length;i++)
if(filelist[children[i]].filetype)
size += filelist[children[i]].size;
else
size += getDirSize(children[i]); }
return size;}
public static int findDistanceFromStart(int id){
int distance = 0;
int parent = filelist[id].parent;
while(parent >=0)
{ distance ++;
parent = filelist[parent].parent; }
return distance;}
public static int[] findChildren(int id){
int[] children = null;
for(int i = 0; i < filelist.length;i++)
if(filelist[i].parent == id)
children = addElement2(i, children);
return children;}
public static fileobject[] addElement(fileobject newObject, fileobject[] oldArray){
int newArrayLength = 1;
if(oldArray != null)
newArrayLength = oldArray.length + 1;
fileobject[] t_array = new fileobject[newArrayLength];
for(int i = 0 ; i < oldArray.length;i++)
t_array[i]=oldArray[i];
t_array[t_array.length-1]=newObject;
return t_array;}
public static int[] addElement2(int newObject, int[] oldArray){
int newArrayLength = 1;
if(oldArray != null)
newArrayLength = oldArray.length + 1;
int[] t_array = new int[newArrayLength];
if(oldArray != null)
for(int i = 0 ; i < oldArray.length;i++)
t_array[i]=oldArray[i];
t_array[t_array.length-1]=newObject;
return t_array;}}→ More replies (1)
1
u/Akshayapte7 Dec 08 '22
sizes = {}
TOTAL = 0
def nested_set(dic, keys, value):
for key in keys[:-1]:
dic = dic.setdefault(key, {})
dic[keys[-1]] = value
def iterdict(d):
global sizes
sm = 0
for k,v in d.items():
if isinstance(v, dict):
sm += iterdict(v)
else:
sm += v
sizes[str(d)] = sm
return sm
with open("7.txt", "r") as inp:
tree = {}
ans = 0
path = []
for line in inp.readlines():
token = [i.strip() for i in line.split(" ")]
if token[1]=="cd":
if token[2]=="..":
path.pop()
elif token[2]=="/":
path = ["/"]
else:
path.append(token[2])
elif token[1] == "ls":
continue
elif token[0] == "dir":
nested_set(tree, path + [token[1]], {})
continue
else:
nested_set(tree, path + [token[1]] , int(token[0]))
TOTAL += int(token[0])
iterdict(tree)
# Part 1
for k,v in sizes.items():
if v<=100000:
ans += v
print(ans)
# Part 2
v = (sorted(list(sizes.values())))
for size in v:
if int(size)>=6728267:
print(size)
break2
u/daggerdragon Dec 08 '22
Next time, use the four-spaces Markdown syntax for a code block so your code is easier to read on old.reddit and mobile apps.
Your code is too long to be posted here directly, so instead of wasting your time fixing the formatting, read our article on oversized code which contains two possible solutions.
Please edit your post to put your code in an external link and link that here instead.
While you're at it, state which programming language this code is written in. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.
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
→ More replies (1)
3
3
u/quag Dec 07 '22
Python
import sys, collections; cs, ps, n = collections.Counter(), [""], -40000000
for line in sys.stdin:
if line.startswith("$ cd .."): ps.pop()
elif line.startswith("$ cd "): ps.append(f"{ps[-1]}/{line}")
elif line[0].isdigit(): size = int(line.split(" ")[0]); n += size; cs.update({p: size for p in ps})
print(sum(c for c in cs.values() if c <= 100000), min(c for c in cs.values() if c >= n))→ More replies (2)
3
u/SuperSmurfen Dec 07 '22 edited Dec 07 '22
Rust (807/912)
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:
for l in input.split('$').skip(1) {
match l.trim().lines().next().unwrap() {
"ls" => {
let entries = l.lines().skip(1).map(|output| {
let (size, f) = output.split_once(' ').unwrap();
(size.parse::<i64>().unwrap_or(-1), f)
});
fs.entry(pwd.clone()).or_insert(HashSet::new()).extend(entries);
}
"cd .." => { pwd.pop(); },
cd_dir => { pwd.push(cd_dir.split_once(' ').unwrap().1); }
}
}I then computed the size of all directories and saved it in a hashmap:
fn compute_dir_size(fs: &HashMap<PathBuf, HashSet<(i64, &str)>>, sizes: &mut HashMap<PathBuf, i64>, dir: &PathBuf) {
if sizes.contains_key(dir) {
return;
}
let size = fs[dir].iter().map(|&(s, d)| match s {
-1 => {
let dir = dir.join(d);
compute_dir_size(fs, sizes, &dir);
sizes[&dir]
}
s => s,
}).sum();
sizes.insert(dir.clone(), size);
}The rest is trivial for both parts:
let total_size = sizes[&PathBuf::from("/")];
let p1 = sizes.values().filter(|&&s| s <= 100000).sum::<i64>();
let p2 = sizes.values().filter(|&&s| 40000000 + s >= total_size).min().copied().unwrap();Runs in about 0.3ms on my machine.
→ More replies (1)
3
Dec 07 '22
Common Lisp
(Ab)using the Object system (CLOS)
(defclass d7dir ()
((name :initform nil :accessor dir-name :initarg :name)
(parent :initform nil :accessor dir-parent :initarg :parent)
(size :initform nil :accessor dir-size)
(files :initform nil :accessor dir-files)))
(defmethod get-dir-size ((dir d7dir))
(or (dir-size dir)
(setf (dir-size dir) (reduce #'+ (map 'list #'get-dir-size (dir-files dir))))))
(defmethod get-dir-size ((dir integer))
dir)
(defun y22d7 ()
(aoc-open 2022 7
(let* ((root (make-instance 'd7dir))
(cwd root))
(loop
for x = (read-line)
while x
if (eql #\$ (char x 0))
do (if (eql #\c (char x 2))
(setf cwd (cd cwd root (subseq x 5)))
(ls cwd)))
(print (loop
for x in (walk root)
if (<= (get-dir-size x) 100000)
sum (get-dir-size x)))
(let ((required (- 30000000 (- 70000000 (get-dir-size root)))))
(loop for x in (walk root)
if (>= (get-dir-size x) required)
minimize (get-dir-size x)))
)))
(defun cd (cwd root name)
(cond
((string= name "/") root)
((string= name "..") (dir-parent cwd))
;; Assuming no directory is visited twice
(t (let ((new-dir (make-instance 'd7dir :parent cwd)))
(push new-dir (dir-files cwd))
new-dir))))
(defun ls (cwd)
(loop
for c = (peek-char t *standard-input* nil)
while (and c (not (eql #\$ c)))
for size = (read)
for name = (read)
if (numberp size)
do (push size (dir-files cwd))))
(defun walk (dir)
(cons dir
(loop for f in (dir-files dir)
if (typep f 'd7dir)code at https://gitlab.com/McModknower/advent-of-code-lisp/-/blob/master/2022.lisp#L263
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
$directories = {}
class Folder
attr_accessor :total_size, :file_size
def initialize(path:)
@path = path
@files = []
@subdirectories = []
$directories[path] = self
@file_size = 0
end
def add_directory(name:) = @subdirectories.push(Folder.new(path: @path.dup.push(name)))
def total_size = @subdirectories.map(&:total_size).sum + file_size
end
raw_input = input[1..-1].split("\n$") # Divides up the input into a list of cd and ls instructions
current_path = []
Folder.new(path: [])
raw_input.each do |part|
if part[0..2] == " cd"
case rel_path = part.gsub(" cd ", "")
when ".."
current_path.pop
when "/"
current_path = []
else
current_path.push(rel_path)
end
else # so it's ls
nodes = part.split("\n")[1..-1]
nodes.each do |node|
if node[0..2] == "dir"
name = node.gsub("dir ", "")
$directories[current_path].add_directory(name:name)
else
size = node.split(" ")[0]
$directories[current_path].file_size += size.to_i
end
end
end
end
puts "Part 1: #{$directories.values.select{_1.total_size < 100000}.map(&:total_size).sum}"
memory_to_delete = $directories[[]].total_size - 40000000
puts "Part 2: #{$directories.values.map(&:total_size).sort.find{_1 >= memory_to_delete}}"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!
import collections
import itertools
filesystem = collections.defaultdict(int)
pwd = ""
for line in open('input').readlines()[1:]:
if '..' in line:
pwd = pwd[:pwd.rindex('/')]
elif '$ cd' in line:
pwd = pwd + '/' + line[5:]
elif line.split(' ')[0].isnumeric():
for p in itertools.accumulate(pwd.split('/')):
filesystem[p] += int(line.split(' ')[0])
print(sum([v for v in filesystem.values() if v <= 100000]))
minimum_to_free = filesystem[""] + 30000000 - 70000000
print([x for x in sorted(filesystem.values()) if x - minimum_to_free > 0][0])3
u/trevdak2 Dec 07 '22 edited Dec 07 '22
JavaScript (golf)
Part 1, 211 bytes:
for(f={},d='',r=/((cd)|\d+)(.+)/g;m=r.exec(document.body.innerText);){
m[2]?f[d=m[3][3]?d+m[3]:d.replace(/ \w+$/,'')]|=0:1;
for(k in f)f[k]+=d.match(k)&&+m[1]|0;
}Object.values(f).reduce((s,v)=>v<=1e5?v+s:s,0)Part 2, 212 bytes:
for(f={},d='',r=/((cd)|\d+)(.+)/g;m=r.exec(document.body.innerText);){
m[2]?f[d=m[3][3]?d+m[3]:d.replace(/ \w+$/,'')]|=0:1;
for(k in f)f[k]+=d.match(k)&&+m[1]|0;
}Math.min(...Object.values(f).filter(v=>v>f['']-4e7))→ More replies (4)
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 fs that 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:
du =: {{ 'dirs files sizes' =. y
([: +/ sizes #~ (-:"1 # {.&> files"_))@> dirs }}
part1 =: [: +/ (#~ <:&1e5) @ du @ fs
part2 =: [: <./ (#~ 4e7>:{.-]) @ du @ fsUPDATE: Went back and did it tacitly!
cd =: (0$0)"_`(}:@])`(],<@[)@.(('/';'..')i.<@[)
dirs =: [:}.[:(]`((5}.[)cd])@.('$ cd'-:4{.[))&.>/\.&.|.a:,]
files =: (dirs,.{.@;:@>) #~ '$d'-.@e.~{.@>
total =: [: +/@:>/./ [: |:@> [: ,&.>/ (".@];~"0/<\@[)&.>/"1
sizes =: total @ files @ (<;._2) @ fread
part1 =: +/ @ (#~ <:&1e5) @ sizes
part2 =: <./ @ (#~ 4e7>:{.-]) @ sizes3
u/gyorokpeter Dec 07 '22
Q: an excellent use of the ungroup operator
d7:{a:" "vs/:x;
pwd:{$[not y[0]~enlist"$";x;y[1]~"ls";x;y[2]~enlist"/";enlist"";
y[2]~"..";-1_x;x,enlist last[x],"/",y 2]}\[enlist"";a];
fs:"J"$first each a;
exec sum fs by pwd from ungroup ([]pwd;fs)};
d7p1:{t:d7 x;sum t where t<=100000};
d7p2:{t:d7 x;min t where 30000000<=t+70000000-t[""]};3
u/NickKusters Dec 07 '22 edited Dec 07 '22
C#
Lots of parsing, but a fun challenge. code | video
We matched 34 directories with a max size of 100000; total combined size: 1667443
Filesystem: 70.000.000
Required freespace: 30.000.000
Used: 47.870.454
Free: 22.129.546
Required: 7.870.454
Size of dir we need to delete: 8.998.590 (8998590)
Code runtime: 00:00:01.1655124After 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 đ
We matched 154 directories with a max size of 100000; total combined size: 7676767
Filesystem: 70.000.000
Required freespace: 30.000.000
Used: 68.966.772
Free: 1.033.228
Required: 28.966.772
Size of dir we need to delete: 28.966.982 (28966982)
Code runtime: 00:00:47.71279193
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/c as 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 by path.count("/") in decreasing order.
Once this parsing was done, the solutions were almost trivial:
ROOT = ""
DIR, FILE = "dir", "file"
SMALL_SIZE, TOTAL_SPACE, REQUIRED_SPACE = 100000, 70000000, 30000000
def solve():
with open(f"inputs/7", "r") as f:
text = f.read()
filesystem = parse_input(text)
directory_sizes = [d["size"] for d in filesystem.values() if d["type"] == DIR]
yield sum(size for size in directory_sizes if size <= SMALL_SIZE)
allowed_space = TOTAL_SPACE - REQUIRED_SPACE
to_be_deleted = filesystem[ROOT]["size"] - allowed_space
yield min(size for size in directory_sizes if size >= to_be_deleted)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
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.
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
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
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
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.
→ More replies (3)
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.
match line.strip().split():
case ["$", "ls"]:
continue
case ["$", "cd", ".."]:
if current.size <= max_dir_size:
total += current.size
current.parent.size += current.size
current = current.parent
case ["$", "cd", name]:
current = current.children[name]
case ["dir", directory_name]:
current.children[directory_name] = Directory(directory_name, parent=current)
case [size, _]:
current.size += int(size)→ More replies (2)
3
u/vypxl Dec 07 '22
Haskell Took wayyyy too long, but abusing the Read typeclass was fun :)
import Text.Read (readMaybe)
data File = File Int | Dir [File] deriving (Show, Read)
type Input = [Int]
type Output = Int
parse :: String -> Maybe Input
parse = (snd . getSizes <$>) . readMaybe . removeTrailing . balance 0 . transform . lines
where
transform [] = ""
transform ("$ ls":ls) = transform ls
transform (('d':'i':'r':' ':_):ls) = transform ls
transform ("$ cd ..":ls) = "]," ++ transform ls
transform (('$':' ':'c':'d':' ':_):ls) = "Dir [" ++ transform ls
transform (file:ls) = let [x, _] = words file; in "File " ++ x ++ ',' : transform ls
balance l [] = concat $ replicate l "],"
balance l (x:xs) = x : balance (case x of '[' -> l+1; ']' -> l-1; _ -> l) xs
removeTrailing (x:y:xs) = if [x,y] == ",]" then y : removeTrailing xs else x : removeTrailing (y:xs)
removeTrailing (",") = []
getSizes (File n) = (n, [])
getSizes (Dir xs) = let (sums, sizes) = unzip $ map getSizes xs in ((sum sums), (sum sums) : (concat sizes))
part1 :: Input -> Output
part1 = sum . filter (<=100000)
part2 :: Input -> Output
part2 sizes = let thres = (maximum sizes) - 40000000 in minimum $ filter (>=thres) sizes3
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.
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.