From 5186f8d891c60d61d406779d2890770f9e41f0e7 Mon Sep 17 00:00:00 2001 From: j-james Date: Wed, 7 Dec 2022 16:27:28 -0800 Subject: Day Seven --- 2022/nim/day07/src/main.nim | 68 +++++++++++++++++++++++++++++ 2022/rust/day07/Cargo.lock | 7 +++ 2022/rust/day07/Cargo.toml | 8 ++++ 2022/rust/day07/src/main.rs | 104 ++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 187 insertions(+) create mode 100644 2022/nim/day07/src/main.nim create mode 100644 2022/rust/day07/Cargo.lock create mode 100644 2022/rust/day07/Cargo.toml create mode 100644 2022/rust/day07/src/main.rs diff --git a/2022/nim/day07/src/main.nim b/2022/nim/day07/src/main.nim new file mode 100644 index 0000000..da3bd90 --- /dev/null +++ b/2022/nim/day07/src/main.nim @@ -0,0 +1,68 @@ +# Day 7: No Space Left On Device +import std/[os, strutils] + +let input = paramStr(1).readFile().strip().split("\n") + +type File = object + id: string + size: int + +type Dir = ref object + id: string + files: seq[File] + dirs: seq[Dir] + parent: Dir + size: int + +var root = Dir(id: "/") +var current = root +for line in input[1..^1]: + let output = line.split(" ") + if output.len == 2: + if output[0] == "$": + discard + elif output[0] == "dir": + current.dirs.add(Dir(id: output[1], parent: current)) + else: + current.files.add(File(id: output[1], size: output[0].parseInt())) + else: + assert output[1] == "cd" + if output[2] == "..": + current = current.parent + else: + for i in current.dirs: + if i.id == output[2]: + current = i + break + +proc update_size(a: Dir) = + for i in a.files: + a.size += i.size + for i in a.dirs: + i.update_size() + a.size += i.size +root.update_size() + +const maximum_size = 100000 + +var sum = 0 +proc calc_size(a: Dir) = + if a.size <= maximum_size: + sum += a.size + for i in a.dirs: + i.calc_size() +root.calc_size() +echo sum + +const total_space = 70000000 +const update_space = 30000000 +let needed_space = update_space - (total_space - root.size) + +var min = update_space +proc calc_min(a: Dir) = + if a.size >= needed_space: + min = min(a.size, min) + for i in a.dirs: + i.calc_min() +root.calc_min() +echo min diff --git a/2022/rust/day07/Cargo.lock b/2022/rust/day07/Cargo.lock new file mode 100644 index 0000000..cf14c74 --- /dev/null +++ b/2022/rust/day07/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "day07" +version = "0.1.0" diff --git a/2022/rust/day07/Cargo.toml b/2022/rust/day07/Cargo.toml new file mode 100644 index 0000000..682e4ad --- /dev/null +++ b/2022/rust/day07/Cargo.toml @@ -0,0 +1,8 @@ +[package] +name = "day07" +version = "0.1.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] diff --git a/2022/rust/day07/src/main.rs b/2022/rust/day07/src/main.rs new file mode 100644 index 0000000..1ea8840 --- /dev/null +++ b/2022/rust/day07/src/main.rs @@ -0,0 +1,104 @@ +use std::cell::{Cell, RefCell}; +use std::cmp; +use std::env; +use std::fs; +use std::rc::Rc; + +struct Directory { + id: String, + size: Cell, + // mmm i'd rather have a plain Directory instead of Rc + // but i get "cannot move out of x which is behind a shared reference" + children: RefCell>>, + parent: Option> +} + +fn main() { + let args = env::args().nth(1).expect("missing input"); + let input = fs::read_to_string(args).unwrap(); + let history: Vec<&str> = input.trim().split("\n").collect(); + + let root = Rc::new(Directory { + id: String::from("/"), + size: Cell::from(0), + children: RefCell::from(Vec::new()), + parent: None + }); + + let mut current = root.clone(); + for line in &history[1..] { + let output = line.split(" "); + match output.collect::>()[..] { + ["$", "ls"] => { + // println!("$ ls") + }, + ["$", "cd", ".."] => { + current = current.parent.clone().unwrap(); + // println!("$ cd .."); + }, + ["$", "cd", id] => { + let mut next: Option> = None; + for i in &*current.children.borrow() { + if i.id == id { + next = Option::from(i.clone()); + break; + } + } + current = next.unwrap(); + // println!("$ cd {}", id); + }, + ["dir", id] => { + (current.children.borrow_mut()).push(Rc::from(Directory { + id: String::from(id), + size: Cell::from(0), + children: RefCell::from(Vec::new()), + parent: Option::from(current.clone()) + })); + // println!("dir {}", id) + }, + [size, id] => { + current.size.replace(current.size.get() + size.parse::().unwrap()); + // println!("{} {}", size, id) + }, + _ => panic!("crash and burn"), + } + } + + // Corrects directory sizes by adding the size of nested directories to the directory + fn populate_size(a: &Rc) { + for i in &*a.children.borrow() { + populate_size(&i); + a.size.set(a.size.get() + i.size.get()); + } + } + populate_size(&root); + + const maximum_space: i32 = 100000; + fn calc_size(a: &Rc) -> i32 { + let mut sum = 0; + for i in &*a.children.borrow() { + sum += calc_size(&i); + } + if a.size.get() <= maximum_space { + sum += a.size.get(); + } + return sum; + } + println!("{}", calc_size(&root)); + + const total_space: i32 = 70000000; + const update_space: i32 = 30000000; + // no global variables?? O_O + let needed_space = update_space - (total_space - root.size.get()); + fn calc_min(a: &Rc, min: i32, need: i32) -> i32 { + let mut min = min; + if a.size.get() >= need { + min = cmp::min(a.size.get(), min); + } + for i in &*a.children.borrow() { + min = cmp::min(calc_min(&i, min, need), min); + } + return min; + } + println!("{}", calc_min(&root, update_space, needed_space)); +} -- cgit v1.2.3-70-g09d2