@longpostbot's comment on 'Advent of Code 2022: Day 7'

https://adventofcode.com

with open('AdventOfCode2022/input.txt', 'r') as input:
    commands = input.read().split('\n')

    def new_dict(name, parent=None):
        return {
        'name': name,
        'parent':parent,
        'files': 0,
        'dirs': {}
    }

    root_dict = new_dict(name='/', parent=None)
    curr_dict = root_dict

    #Build tree of dicts
    for i in range(len(commands)):
        command_parts = commands[i].split(' ')
        if command_parts[0] == '$':
            if command_parts[1] == 'cd':
                if command_parts[2] == '..':
                    curr_dict = curr_dict['parent']
                elif command_parts[2] == '/':
                    pass
                else:
                    curr_dict = curr_dict['dirs'][command_parts[2]]
        elif command_parts[0] == 'dir':
            if command_parts[1] not in curr_dict:
                curr_dict['dirs'][command_parts[1]] = new_dict(name=command_parts[1], parent=curr_dict)
        elif command_parts[0] == '':
            pass
        else:
            curr_dict['files'] += int(command_parts[0])

    #PART ONE

    MAX_THRESHOLD = 100000
    FINAL_COUNTER = 0
    dict_list = []
    
    def parse_dict(t_dict):
        folder_total = t_dict['files']

        for c_dict in t_dict['dirs'].keys():
            folder_total += parse_dict(t_dict['dirs'][c_dict])

        global dict_list
        dict_list.append(folder_total)

        if folder_total < MAX_THRESHOLD:
            global FINAL_COUNTER # this is the most embarrassing thing I've ever done
            FINAL_COUNTER += folder_total
        return folder_total

    total_used = parse_dict(root_dict)
    print(FINAL_COUNTER)

    #PART TWO
    TOTAL_SPACE = 70000000
    WANTED_SPACE = 30000000
    curr_wanted = WANTED_SPACE - (TOTAL_SPACE - total_used)
    
    larger_than_wanted = []
    for i in dict_list:
        if i > curr_wanted:
            larger_than_wanted.append(i)

    print(min(larger_than_wanted))

Jump in the discussion.

No email address required.

View entire discussion

ihsoy jew/jew

1yr ago #3200032 Edited 1yr ago

c++

fml got stuck for minutes because I am too dumb to read. First I was looking for directories bigger than 100.000 and then looked for 70.000.000 - total_size, instead of 30.000.000 - 70.000.000 - total_size


#include <memory>
#include <string>
#include <fstream>
#include <iostream>
#include <vector>

class Directory {
public:
	Directory* parent;
	std::vector<Directory*> childs;
	int files;
	int total_size;
	std::string name;
	Directory(Directory* parent, std::string name) {
		this->parent = parent;
		this->name = name;
		files = 0;
	}
	Directory* find_child(std::string name) {
		for (Directory* child : this->childs) {
			if (child->name == name) return child;
		}
		return nullptr;
	}
};

void parseFile(std::ifstream& file, Directory* root) {
	Directory* current;
	current = root;
	std::string cmd1;
	while (file >> cmd1) {
		if (cmd1 == "$") {
			std::string command;
			file >> command;
			if (command == "cd") {
				std::string parameter;
				file >> parameter;
				if (parameter == "/") continue;
				else if (parameter == "..") current = current->parent;
				else {
					current = current->find_child(parameter);
				}
			}
			else if (command == "ls") {
				continue;
			}
		}
		else if (cmd1 == "dir") {
			std::string folder;
			file >> folder;
			Directory* child = new Directory(current, folder);
			current->childs.push_back(child);
		}
		else {
			int file_size = std::stoi(cmd1);
			std::string file_name;
			file >> file_name;
			current->files += file_size;
		}
	}
}

int partOne(Directory* dir, int limit, int& counter) {
	int size{ dir->files };
	if (dir->childs.size() >= 0) {
		for (Directory* child : dir->childs) {
			size += partOne(child, limit, counter);
		}
	}
	if (size <= limit) counter += size;
	dir->total_size = size;
	return size;
}

void partTwo(Directory* dir, int needToBeFreed, std::vector<Directory*>& store) {
	if (dir->total_size >= needToBeFreed) store.push_back(dir);
	for (Directory* child : dir->childs) {
		partTwo(child, needToBeFreed, store);
	}
}

int main() {
	std::ifstream file("input.txt");
	Directory root = Directory(nullptr, "/");
	parseFile(file, &root);
	int counter{ 0 };
	int total_size = partOne(&root, 100'000, counter);
	std::cout << "Part 1: " << counter << '\n';

	std::vector<Directory*> store;
	int needToBeFreed = 30'000'000 - (70'000'000 - total_size);
	partTwo(&root, needToBeFreed, store);
	int min_size = INT_MAX;
	for (Directory* a : store) {
		min_size = std::min(min_size, a->total_size);
	}
	std::cout << "Part 2: " << '\n' << '\t' << "need to be freed: " << needToBeFreed << '\n' << '\t' << "Result: " << min_size;
	return 0;
}