aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--2022/07-no-space-left-on-device/example23
-rw-r--r--2022/07-no-space-left-on-device/first.zig55
-rw-r--r--2022/07-no-space-left-on-device/input1010
-rw-r--r--2022/07-no-space-left-on-device/second.zig67
4 files changed, 1155 insertions, 0 deletions
diff --git a/2022/07-no-space-left-on-device/example b/2022/07-no-space-left-on-device/example
new file mode 100644
index 0000000..09a921e
--- /dev/null
+++ b/2022/07-no-space-left-on-device/example
@@ -0,0 +1,23 @@
+$ cd /
+$ ls
+dir a
+14848514 b.txt
+8504156 c.dat
+dir d
+$ cd a
+$ ls
+dir e
+29116 f
+2557 g
+62596 h.lst
+$ cd e
+$ ls
+584 i
+$ cd ..
+$ cd ..
+$ cd d
+$ ls
+4060174 j
+8033020 d.log
+5626152 d.ext
+7214296 k
diff --git a/2022/07-no-space-left-on-device/first.zig b/2022/07-no-space-left-on-device/first.zig
new file mode 100644
index 0000000..b10a522
--- /dev/null
+++ b/2022/07-no-space-left-on-device/first.zig
@@ -0,0 +1,55 @@
+const std = @import("std");
+
+const example = @embedFile("example");
+const input = @embedFile("input");
+
+pub fn main() anyerror!void {
+ var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
+ defer arena.deinit();
+ const allocator = arena.allocator();
+
+ try std.testing.expectEqual(try solve(example, allocator), 95437);
+ const result = try solve(input, allocator);
+ try std.io.getStdOut().writer().print("{}\n", .{result});
+}
+
+fn solve(puzzle: []const u8, allocator: std.mem.Allocator) !u64 {
+ var it = std.mem.tokenize(u8, puzzle, "\n");
+ var tot: usize = 0;
+ var n: usize = 0; // depth
+ var stack = std.ArrayList(u64).init(allocator);
+ _ = it.next() orelse unreachable; // drop the cd /
+ try stack.append(0);
+ while (it.next()) |line| {
+ if (line[2] == 'c') { // a cd command
+ if (line[5] == '.') { // going up
+ const v = stack.pop();
+ n -= 1;
+ stack.items[n] += v;
+ if (v <= 100000) {
+ tot += v;
+ }
+ } else { // going down
+ n += 1;
+ try stack.append(0);
+ }
+ } else if (line[2] == 'l') { // a ls command
+ continue;
+ } else if (line[2] == 'r') { // a dir entry in a ls command
+ continue;
+ } else { // a file entry in a ls command
+ var elts = std.mem.split(u8, line, " ");
+ const v = try std.fmt.parseInt(u64, elts.next() orelse unreachable, 10);
+ stack.items[n] += v;
+ }
+ }
+ while (n > 1) : (n -= 1) {
+ const v = stack.pop();
+ n -= 1;
+ stack.items[n] += v;
+ if (v <= 100000) {
+ tot += v;
+ }
+ }
+ return tot;
+}
diff --git a/2022/07-no-space-left-on-device/input b/2022/07-no-space-left-on-device/input
new file mode 100644
index 0000000..1f6ede4
--- /dev/null
+++ b/2022/07-no-space-left-on-device/input
@@ -0,0 +1,1010 @@
+$ cd /
+$ ls
+dir ddpgzpc
+dir mqjrd
+dir mrqjg
+dir rglgbsq
+298050 tjmjp.cqm
+dir wlqhpwqv
+$ cd ddpgzpc
+$ ls
+290515 cvrd.hcf
+dir mlm
+122034 rrtnthnt.zgs
+12680 tvnrl
+49534 vljqzqg
+dir zffbmlbd
+18557 zfhnw.jfd
+$ cd mlm
+$ ls
+102897 zfhnw.zpd
+$ cd ..
+$ cd zffbmlbd
+$ ls
+dir bqpwdh
+dir gqrlmdhs
+315267 mjm.dhc
+294364 mrqdw.npr
+dir szqz
+76621 tvnrl
+285948 vpdbrh
+155914 vwl.vsq
+dir zfhnw
+$ cd bqpwdh
+$ ls
+dir bhmw
+27669 dtzw
+dir lfhgjw
+dir pjqwq
+$ cd bhmw
+$ ls
+190433 zbcbr
+$ cd ..
+$ cd lfhgjw
+$ ls
+dir ndrcgmd
+$ cd ndrcgmd
+$ ls
+98160 mjm.dhc
+$ cd ..
+$ cd ..
+$ cd pjqwq
+$ ls
+50937 dtzw
+186171 mjm.dhc
+305433 mlm
+272969 mlm.rhf
+$ cd ..
+$ cd ..
+$ cd gqrlmdhs
+$ ls
+dir blc
+331077 dcchtmp
+dir mlm
+199021 rlzjl
+253162 vghhgvjq
+dir zfhnw
+$ cd blc
+$ ls
+53872 drjdcqw.szd
+115417 ggh.qsl
+65105 pjqwq
+$ cd ..
+$ cd mlm
+$ ls
+dir bqpwdh
+200734 gjhzr.ffz
+277561 lwnl.jsl
+dir sdjnlsf
+dir trqhm
+140014 tvnrl
+$ cd bqpwdh
+$ ls
+dir jzfgz
+$ cd jzfgz
+$ ls
+334790 dtzw
+$ cd ..
+$ cd ..
+$ cd sdjnlsf
+$ ls
+326446 mjm.dhc
+dir vpdbrh
+$ cd vpdbrh
+$ ls
+20883 bwjjdszc
+10518 dtzw
+64779 ppmwtlj.btf
+320555 rpf.tmw
+295126 vwl.vsq
+$ cd ..
+$ cd ..
+$ cd trqhm
+$ ls
+184138 rmnmsl
+$ cd ..
+$ cd ..
+$ cd zfhnw
+$ ls
+dir pjqwq
+$ cd pjqwq
+$ ls
+dir qjzscp
+$ cd qjzscp
+$ ls
+299311 tvnrl
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd szqz
+$ ls
+dir bqpwdh
+107678 jmqq
+109752 vtmgq.bcz
+301721 zjdlztw
+dir zwvzzz
+$ cd bqpwdh
+$ ls
+dir mlm
+$ cd mlm
+$ ls
+178616 mlm.rnn
+$ cd ..
+$ cd ..
+$ cd zwvzzz
+$ ls
+135690 rrbv.ntn
+$ cd ..
+$ cd ..
+$ cd zfhnw
+$ ls
+dir dtgnbb
+55267 dtzw
+119612 mjm.dhc
+$ cd dtgnbb
+$ ls
+74360 zjq
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd mqjrd
+$ ls
+dir ccnpn
+176761 rmnmsl
+$ cd ccnpn
+$ ls
+116424 pjqwq.ctj
+$ cd ..
+$ cd ..
+$ cd mrqjg
+$ ls
+dir bsphvqnh
+266338 lwfdlqzq.wmj
+287488 mjm.dhc
+211569 mlm.mbn
+231144 vpdbrh
+260476 vtqjh.wfj
+$ cd bsphvqnh
+$ ls
+101783 pscn.zdh
+$ cd ..
+$ cd ..
+$ cd rglgbsq
+$ ls
+dir bqpwdh
+dir fdmhnzw
+dir fgz
+213313 hbj.lgh
+dir lftcr
+dir pjqwq
+1614 rmnmsl
+dir rpz
+dir vpcq
+dir zfhnw
+$ cd bqpwdh
+$ ls
+35649 mjm.dhc
+53750 nqdlf.trh
+102195 vpdbrh.lbn
+$ cd ..
+$ cd fdmhnzw
+$ ls
+222384 dtzw
+$ cd ..
+$ cd fgz
+$ ls
+dir rzrsgst
+dir tqdghbj
+$ cd rzrsgst
+$ ls
+120970 dtzw
+dir zfhnw
+$ cd zfhnw
+$ ls
+154286 fmbzztww.hvt
+$ cd ..
+$ cd ..
+$ cd tqdghbj
+$ ls
+275314 rmblptm
+$ cd ..
+$ cd ..
+$ cd lftcr
+$ ls
+148378 cwjj.trb
+215545 zfhnw.fjl
+$ cd ..
+$ cd pjqwq
+$ ls
+dir bppdtc
+dir dnlzz
+$ cd bppdtc
+$ ls
+276258 zfhnw.rfn
+$ cd ..
+$ cd dnlzz
+$ ls
+286311 cjzm.nhs
+239107 ggdr.rgz
+dir zfhnw
+$ cd zfhnw
+$ ls
+dir rzht
+$ cd rzht
+$ ls
+100504 thj
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd rpz
+$ ls
+182300 brsnhb
+dir pblmwf
+261712 rmnmsl
+dir zfhnw
+$ cd pblmwf
+$ ls
+121117 mlm.zdq
+$ cd ..
+$ cd zfhnw
+$ ls
+281353 gwbrctf
+dir hgpnj
+dir lvhwhz
+dir mlm
+dir pcfljzhm
+dir vpdbrh
+$ cd hgpnj
+$ ls
+103619 vwl.vsq
+$ cd ..
+$ cd lvhwhz
+$ ls
+236328 bqpwdh.qtn
+dir gjwth
+118100 jfcmcq
+dir lwsdfhg
+51327 mjm.dhc
+41403 mlm
+dir vpdbrh
+313830 zmwhlcsw
+$ cd gjwth
+$ ls
+dir bqpwdh
+128093 css
+290123 pjqwq.djg
+89091 whdwbssf.tss
+$ cd bqpwdh
+$ ls
+186274 rmnmsl
+$ cd ..
+$ cd ..
+$ cd lwsdfhg
+$ ls
+218938 mjm.dhc
+$ cd ..
+$ cd vpdbrh
+$ ls
+139398 lrrjnvr
+$ cd ..
+$ cd ..
+$ cd mlm
+$ ls
+278462 fdlb.jsr
+176936 tvnrl
+29208 vwl.vsq
+$ cd ..
+$ cd pcfljzhm
+$ ls
+295983 nnvq.lcg
+$ cd ..
+$ cd vpdbrh
+$ ls
+16998 lswwmjc.vmv
+52872 pmbzp.mmg
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd vpcq
+$ ls
+dir tnrpllzj
+$ cd tnrpllzj
+$ ls
+226232 nqrjs.qds
+$ cd ..
+$ cd ..
+$ cd zfhnw
+$ ls
+188324 dtzw
+263511 lnwwh
+217287 lst.wvw
+178366 vzctflm
+$ cd ..
+$ cd ..
+$ cd wlqhpwqv
+$ ls
+dir bqpwdh
+dir ffw
+dir lpzgcrd
+dir lszdbd
+51178 mlm
+dir ntcpvg
+dir pjqwq
+dir pmpftw
+dir ppf
+dir vpdbrh
+dir zfhnw
+$ cd bqpwdh
+$ ls
+194389 dnqngfzh
+$ cd ..
+$ cd ffw
+$ ls
+dir mfqd
+dir npgnwwf
+dir tcvt
+$ cd mfqd
+$ ls
+214846 vwl.vsq
+$ cd ..
+$ cd npgnwwf
+$ ls
+dir ddqsmtsj
+dir gcq
+dir ldtpnr
+1802 vwl.vsq
+$ cd ddqsmtsj
+$ ls
+309790 rmnmsl
+$ cd ..
+$ cd gcq
+$ ls
+80203 lvqhwzfn
+$ cd ..
+$ cd ldtpnr
+$ ls
+dir spzj
+123522 tvnrl
+$ cd spzj
+$ ls
+139171 bpgpdzt.zzp
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd tcvt
+$ ls
+dir jcvcjz
+dir qmtcr
+dir vpdbrh
+$ cd jcvcjz
+$ ls
+274564 hsv.wsr
+309010 vpdbrh
+$ cd ..
+$ cd qmtcr
+$ ls
+dir mfjd
+dir pmbdsb
+$ cd mfjd
+$ ls
+202111 vpdbrh
+$ cd ..
+$ cd pmbdsb
+$ ls
+dir brghd
+313440 chwzrz.bmf
+$ cd brghd
+$ ls
+216516 dtzw
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd vpdbrh
+$ ls
+134552 sbs.bsn
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd lpzgcrd
+$ ls
+244257 bqpwdh.hsz
+118275 flgfbstp.flp
+dir gcwg
+dir mlm
+dir nfj
+189443 rtwwbgfs.nvl
+dir trbwtdb
+dir vpdbrh
+dir ztwbpvbq
+$ cd gcwg
+$ ls
+dir bqpwdh
+304960 dtzw
+9496 pfpwtsp
+dir pjqwq
+dir vpdbrh
+dir vqp
+186883 vwl.vsq
+$ cd bqpwdh
+$ ls
+79064 fbjdqsn.cgp
+$ cd ..
+$ cd pjqwq
+$ ls
+106371 cplcj
+204740 mhdq.lhc
+313462 pjqwq.lsn
+249876 rmnmsl
+209574 vwl.vsq
+$ cd ..
+$ cd vpdbrh
+$ ls
+166549 mjm.dhc
+270734 rmnmsl
+$ cd ..
+$ cd vqp
+$ ls
+dir nbq
+dir nts
+dir rlbhdgm
+dir srvqpq
+dir zfhnw
+$ cd nbq
+$ ls
+63369 mjm.dhc
+314393 smd
+70181 tbwpwtt.ccj
+97954 vpdbrh.fmw
+$ cd ..
+$ cd nts
+$ ls
+11300 zfhnw.pnj
+$ cd ..
+$ cd rlbhdgm
+$ ls
+dir bzd
+dir hfhzj
+65400 mbrqjnp.wqz
+dir pztwz
+$ cd bzd
+$ ls
+dir bqpwdh
+168832 cdlg.zhp
+dir dtb
+22418 fttt.twt
+dir gmlgvnq
+101839 hnpjbjsc.whd
+dir pdmqn
+122491 smvjvw
+dir wmtdbrqm
+52142 zfhnw.gmt
+$ cd bqpwdh
+$ ls
+dir btb
+37220 gzj.mhf
+dir lwl
+112215 qcfqd.fwz
+210303 qlwgqnsp
+dir trpm
+$ cd btb
+$ ls
+dir rqftrtb
+dir vsb
+$ cd rqftrtb
+$ ls
+dir ndwphjw
+dir pjqwq
+dir zfhnw
+$ cd ndwphjw
+$ ls
+256159 lpprpwjq.srz
+$ cd ..
+$ cd pjqwq
+$ ls
+dir fpb
+$ cd fpb
+$ ls
+42692 pjqwq
+$ cd ..
+$ cd ..
+$ cd zfhnw
+$ ls
+dir bqpwdh
+$ cd bqpwdh
+$ ls
+17467 mshfwzv.ppr
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd vsb
+$ ls
+278554 rmnmsl
+$ cd ..
+$ cd ..
+$ cd lwl
+$ ls
+28409 mjm.dhc
+$ cd ..
+$ cd trpm
+$ ls
+dir mlm
+$ cd mlm
+$ ls
+304742 dtzw
+108223 mjm.dhc
+dir mvh
+52532 nzc.vhj
+dir tdhrrhm
+$ cd mvh
+$ ls
+99770 cgfw.pgm
+$ cd ..
+$ cd tdhrrhm
+$ ls
+326653 lrmsnt.fdh
+157903 mlm
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd dtb
+$ ls
+179072 vpdbrh
+3435 vpdbrh.hpv
+$ cd ..
+$ cd gmlgvnq
+$ ls
+dir rrjgswsd
+$ cd rrjgswsd
+$ ls
+dir zfhnw
+$ cd zfhnw
+$ ls
+278562 mvqbv
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd pdmqn
+$ ls
+233744 pjqwq
+$ cd ..
+$ cd wmtdbrqm
+$ ls
+dir lngc
+dir wgpwcj
+225374 wphwht.nvn
+$ cd lngc
+$ ls
+4415 zfhnw
+$ cd ..
+$ cd wgpwcj
+$ ls
+165889 bqpwdh.ngg
+331254 dlpr
+97910 mzjlswr.spn
+dir rqhshd
+49222 vwl.vsq
+$ cd rqhshd
+$ ls
+145902 qwhr
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd hfhzj
+$ ls
+92623 ldlpnvw
+146918 mjm.dhc
+$ cd ..
+$ cd pztwz
+$ ls
+dir jllmcfjf
+$ cd jllmcfjf
+$ ls
+245363 dtzw
+81345 mbh.vdq
+164199 ntwzgfr
+14466 rmnmsl
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd srvqpq
+$ ls
+271019 zfhnw.rlc
+$ cd ..
+$ cd zfhnw
+$ ls
+104520 bqpwdh.qqv
+12312 lspg
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd mlm
+$ ls
+259906 cbgmp
+dir rjshqvb
+$ cd rjshqvb
+$ ls
+309983 mlm.qmm
+$ cd ..
+$ cd ..
+$ cd nfj
+$ ls
+44759 mlm
+228634 njrrs.sjj
+dir rfmw
+$ cd rfmw
+$ ls
+273185 bcbjq.vlw
+$ cd ..
+$ cd ..
+$ cd trbwtdb
+$ ls
+307053 mjm.dhc
+301028 zzg
+$ cd ..
+$ cd vpdbrh
+$ ls
+dir bzdp
+169466 grnvt.mst
+dir pjqwq
+123590 vwl.vsq
+$ cd bzdp
+$ ls
+225941 trrzqz
+241249 vpdbrh.lsj
+$ cd ..
+$ cd pjqwq
+$ ls
+dir ddfpql
+dir fgbqzm
+329174 mjm.dhc
+6701 mlm.ffp
+dir phf
+$ cd ddfpql
+$ ls
+103799 lpbp.bpt
+$ cd ..
+$ cd fgbqzm
+$ ls
+dir spsz
+$ cd spsz
+$ ls
+34049 mfgph
+$ cd ..
+$ cd ..
+$ cd phf
+$ ls
+84883 qdj.hbt
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd ztwbpvbq
+$ ls
+138429 bqpwdh.mlr
+151403 cqmbgfdh.gvh
+9087 ngm
+335933 sswtt
+318963 tvnrl
+dir wdhjpzp
+$ cd wdhjpzp
+$ ls
+119932 pjqwq
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd lszdbd
+$ ls
+dir cpqpvbz
+dir hnl
+dir llprt
+$ cd cpqpvbz
+$ ls
+dir ltlcz
+dir wmpsvm
+$ cd ltlcz
+$ ls
+262150 zfhnw.zsg
+$ cd ..
+$ cd wmpsvm
+$ ls
+dir bqpwdh
+$ cd bqpwdh
+$ ls
+51488 pvhcb.qmw
+44038 zfhnw
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd hnl
+$ ls
+dir pjqwq
+$ cd pjqwq
+$ ls
+170454 mhg.ddj
+$ cd ..
+$ cd ..
+$ cd llprt
+$ ls
+268114 bmvwwbdt.cqm
+207425 dtzw
+180660 mgqz
+297846 qbpcd
+112867 zdb
+$ cd ..
+$ cd ..
+$ cd ntcpvg
+$ ls
+74161 bqpwdh.gbr
+257792 vwl.vsq
+$ cd ..
+$ cd pjqwq
+$ ls
+279738 hwdgzvj
+dir jsdbnwrc
+dir pcjfjsgs
+11113 rqrtcq
+208212 tvnrl
+dir vllzsh
+$ cd jsdbnwrc
+$ ls
+11720 fvj
+$ cd ..
+$ cd pcjfjsgs
+$ ls
+dir bqpwdh
+195046 mjm.dhc
+dir ssq
+dir vpdbrh
+$ cd bqpwdh
+$ ls
+42769 dlrvsj
+159280 zfhnw
+239759 zqqcb
+$ cd ..
+$ cd ssq
+$ ls
+67639 bqpwdh.csb
+$ cd ..
+$ cd vpdbrh
+$ ls
+dir bqdpwrst
+dir qtj
+$ cd bqdpwrst
+$ ls
+57800 fndpnj.fgt
+132712 vpdbrh
+$ cd ..
+$ cd qtj
+$ ls
+dir szjtvcb
+$ cd szjtvcb
+$ ls
+93993 mgmqtdb.fzd
+dir stbczmlq
+$ cd stbczmlq
+$ ls
+dir nhq
+$ cd nhq
+$ ls
+27749 hqgngdt.tmq
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd vllzsh
+$ ls
+dir nlwwrz
+237293 wlgbt
+dir zhmwl
+$ cd nlwwrz
+$ ls
+99990 bjv.szl
+$ cd ..
+$ cd zhmwl
+$ ls
+dir hbpps
+dir hfv
+$ cd hbpps
+$ ls
+7520 mlm.ltq
+$ cd ..
+$ cd hfv
+$ ls
+dir qpfrd
+$ cd qpfrd
+$ ls
+dir mlm
+$ cd mlm
+$ ls
+288919 qmtpwqn
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd pmpftw
+$ ls
+118859 mlm
+103896 pjqwq
+128800 tvnrl
+$ cd ..
+$ cd ppf
+$ ls
+dir drszpqf
+dir fbs
+202594 gdpw.bds
+dir ldnrpg
+176398 mbbmmf.plr
+dir tfjnj
+$ cd drszpqf
+$ ls
+dir pjqwq
+dir qtblb
+191392 tvnrl
+$ cd pjqwq
+$ ls
+dir lrrlbgwh
+dir nfcc
+dir pqm
+$ cd lrrlbgwh
+$ ls
+182434 mjm.dhc
+238706 vpdbrh.lgz
+$ cd ..
+$ cd nfcc
+$ ls
+253846 vpdbrh
+268229 vwl.vsq
+$ cd ..
+$ cd pqm
+$ ls
+56573 vwl.vsq
+$ cd ..
+$ cd ..
+$ cd qtblb
+$ ls
+28941 zcm.dtw
+52282 zmhw.lhm
+$ cd ..
+$ cd ..
+$ cd fbs
+$ ls
+dir gpttw
+$ cd gpttw
+$ ls
+dir bqpwdh
+$ cd bqpwdh
+$ ls
+98780 wvzhlfht.rdd
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd ldnrpg
+$ ls
+205523 bqpwdh.qlb
+54924 pcq.clf
+$ cd ..
+$ cd tfjnj
+$ ls
+237752 bqpwdh.bvf
+dir lwl
+295520 mjm.dhc
+dir qsgpsmzw
+278576 rmnmsl
+dir vljqlw
+225025 vwl.vsq
+100780 zgjhtrv
+$ cd lwl
+$ ls
+150713 dhrl
+$ cd ..
+$ cd qsgpsmzw
+$ ls
+265288 bqpwdh
+92636 ntgrlr
+182224 wdb
+$ cd ..
+$ cd vljqlw
+$ ls
+dir pcnd
+dir pjqwq
+317809 tvnrl
+$ cd pcnd
+$ ls
+8283 gmq
+195909 rmnmsl
+183891 tvnrl
+182837 vwl.vsq
+$ cd ..
+$ cd pjqwq
+$ ls
+dir vwp
+$ cd vwp
+$ ls
+dir crpztfmf
+dir fhrfrbqg
+$ cd crpztfmf
+$ ls
+257441 dpztgnd
+$ cd ..
+$ cd fhrfrbqg
+$ ls
+64573 mjm.dhc
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd ..
+$ cd vpdbrh
+$ ls
+80449 mjm.dhc
+266777 qfjwb
+dir qzmz
+100029 tvnrl
+28910 zqnp
+$ cd qzmz
+$ ls
+9583 wsfwpznj
+$ cd ..
+$ cd ..
+$ cd zfhnw
+$ ls
+dir pmdsb
+106595 vwl.vsq
+dir zdv
+$ cd pmdsb
+$ ls
+dir bqpwdh
+dir pjqwq
+$ cd bqpwdh
+$ ls
+dir tstqlh
+143862 vpdbrh.thr
+$ cd tstqlh
+$ ls
+119310 tcmglrz.hzp
+$ cd ..
+$ cd ..
+$ cd pjqwq
+$ ls
+56885 rmnmsl
+$ cd ..
+$ cd ..
+$ cd zdv
+$ ls
+209148 nhcdqmd.hgh
+dir pjdhn
+119411 pjqwq.vrq
+154423 rmnmsl
+178813 vhbjqhhq.tbf
+$ cd pjdhn
+$ ls
+dir gnthzp
+116732 qhrz.ssb
+dir rvbw
+117225 svmpwv
+$ cd gnthzp
+$ ls
+dir bqpwdh
+$ cd bqpwdh
+$ ls
+312253 rmnmsl
+$ cd ..
+$ cd ..
+$ cd rvbw
+$ ls
+dir cjdhwbv
+268173 lsmmthf
+99445 vwl.vsq
+$ cd cjdhwbv
+$ ls
+302711 tbhb
+173182 tmj.frb
diff --git a/2022/07-no-space-left-on-device/second.zig b/2022/07-no-space-left-on-device/second.zig
new file mode 100644
index 0000000..537ef6e
--- /dev/null
+++ b/2022/07-no-space-left-on-device/second.zig
@@ -0,0 +1,67 @@
+const std = @import("std");
+
+const example = @embedFile("example");
+const input = @embedFile("input");
+
+pub fn main() anyerror!void {
+ var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
+ defer arena.deinit();
+ const allocator = arena.allocator();
+
+ try std.testing.expectEqual(try solve(example, allocator), 24933642);
+ const result = try solve(input, allocator);
+ try std.io.getStdOut().writer().print("{}\n", .{result});
+}
+
+fn solve(puzzle: []const u8, allocator: std.mem.Allocator) !u64 {
+ var it = std.mem.tokenize(u8, puzzle, "\n");
+ var tot: usize = 0;
+ var n: usize = 0; // depth
+ var sizes = std.ArrayList(u64).init(allocator);
+ var stack = std.ArrayList(u64).init(allocator);
+ _ = it.next() orelse unreachable; // drop the cd /
+ try stack.append(0);
+ while (it.next()) |line| {
+ if (line[2] == 'c') { // a cd command
+ if (line[5] == '.') { // going up
+ const v = stack.pop();
+ n -= 1;
+ stack.items[n] += v;
+ try sizes.append(v);
+ } else { // going down
+ n += 1;
+ try stack.append(0);
+ }
+ } else if (line[2] == 'l') { // a ls command
+ continue;
+ } else if (line[2] == 'r') { // a dir entry in a ls command
+ continue;
+ } else { // a file entry in a ls command
+ var elts = std.mem.split(u8, line, " ");
+ const v = try std.fmt.parseInt(u64, elts.next() orelse unreachable, 10);
+ stack.items[n] += v;
+ tot += v;
+ }
+ }
+ while (n > 1) : (n -= 1) { // we unwrap the cd up to /
+ const v = stack.pop();
+ n -= 1;
+ stack.items[n] += v;
+ try sizes.append(v);
+ }
+ try sizes.append(stack.items[n]); // we do not forget the last one
+ n = 30000000 - (70000000 - tot); // the amount of space we need to free
+ // let's run a dychotomy on the array
+ std.sort.sort(u64, sizes.items, {}, std.sort.asc(u64));
+ var a: usize = 0;
+ var b = sizes.items.len - 1;
+ while (b - a > 2) {
+ const m = a + (b - a) / 2;
+ if (sizes.items[m] < n) {
+ a = m;
+ } else {
+ b = m;
+ }
+ }
+ return sizes.items[b];
+}