-
Notifications
You must be signed in to change notification settings - Fork 2
/
day07.pl
executable file
·98 lines (85 loc) · 1.94 KB
/
day07.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#!/usr/bin/env perl
use warnings;
use strict;
use feature qw(switch);
my @pwd;
my %fs;
sub get {
my ($path, $tree) = @_;
my $len = scalar(@$path);
if ($len > 0) {
my @subpath = (@$path)[1..($len - 1)];
my $subtree = $tree->{$path->[0]};
return get(\@subpath, $subtree);
} else {
return $tree;
}
}
sub insertFile {
my ($name, $size) = @_;
my ($tree) = get(\@pwd, \%fs);
$tree->{$name} = $size;
}
sub insertDir {
my ($name) = @_;
my ($tree) = get(\@pwd, \%fs);
$tree->{$name} = {};
}
sub cd {
my ($dest) = @_;
given ($dest) {
when ('.') {}
when ('..') { pop @pwd; }
when ('/') { @pwd = (); }
default { push @pwd, $dest; }
}
}
sub computeDirectorySizes {
my ($maxsize, $tree, $output) = @_;
my $total = 0;
my $recursive = 0;
while (my ($key, $value) = each %$tree) {
if ("$value" =~ /^HASH.*/) {
my ($subtotal, $subrecursive) = computeDirectorySizes($maxsize, $value, $output);
$total += $subtotal;
$recursive += $subrecursive;
} else {
$total += $value;
}
}
if ($total <= $maxsize) {
$recursive += $total;
}
push @$output, $total;
return ($total, $recursive);
}
# Parse input
open(FH, '<', 'resources/input.txt') or die $!;
while (<FH>) {
if (my ($command, $arg) = ($_ =~ m/\$\s+(\w+)\s*(.*)/)) {
if ($command eq 'cd') {
cd($arg);
}
} elsif (my ($size, $name) = ($_ =~ m/(\d+)\s+(.+)/)) {
insertFile($name, $size);
} elsif (my ($name) = ($_ =~ m/dir\s+(.+)/)) {
insertDir($name);
}
}
close(FH);
# Compute results
my $maxsize = 100000;
my @dirsizes;
my ($total, $part1) = computeDirectorySizes($maxsize, \%fs, \@dirsizes);
print "Part 1: $part1\n";
my $available = 70000000;
my $required = 30000000;
my $unused = $available - $total;
my $min = $available; # Almost infinity
for my $size (@dirsizes) {
if ($size >= ($required - $unused) && $size < $min) {
$min = $size;
}
}
my $part2 = $min;
print "Part 2: $part2\n";