diff options
Diffstat (limited to '')
| -rw-r--r-- | 2022/07-no-space-left-on-device/example | 23 | ||||
| -rw-r--r-- | 2022/07-no-space-left-on-device/first.zig | 55 | ||||
| -rw-r--r-- | 2022/07-no-space-left-on-device/input | 1010 | ||||
| -rw-r--r-- | 2022/07-no-space-left-on-device/second.zig | 67 |
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]; +} |