9

6 files changed, 241 insertions, 1 deletions

diff --git a/2021/.gitignore b/2021/.gitignore
index ebbfb2e..b0507d5 100644
--- a/2021/.gitignore
+++ b/2021/.gitignore
@@ -9,6 +9,7 @@ obj/
 7
 8
 9
+9pre
 10
 11
 12
@@ -25,3 +26,6 @@ obj/
 23
 24
 25
+
+# generated by futhark
+9.c
diff --git a/2021/9.fut b/2021/9.fut
new file mode 100644
index 0000000..10b5f82
--- /dev/null
+++ b/2021/9.fut
@@ -0,0 +1,91 @@
+let zip2d 'a 'b [h] [w] (a: [h][w]a) (b: [h][w]b) : [h][w](a, b) =
+  map2 (map2 (\x y -> (x, y))) a b
+
+let fst 'a 'b (t: (a, b)) : a = let (x, _) = t in x
+let snd 'a 'b (t: (a, b)) : b = let (_, y) = t in y
+
+let get 'a [h] [w] (def: a) (field: [h][w]a) (y: i64) (x: i64) : a =
+  if x < 0 || y < 0 || x >= w || y >= h
+    then def
+    else field[y, x]
+
+let stencil 'a 'b [h] [w] (def: a) (field: [h][w]a) (f: a -> (a,a,a,a) -> b) : [h][w]b =
+  tabulate h (\y ->
+    tabulate w (\x ->
+      f (get def field y x)
+        (get def field (y-1) x
+        ,get def field y (x+1)
+        ,get def field (y+1) x
+        ,get def field y (x-1))))
+
+let red4 'a 'b (f: a -> b) (g: b -> b -> b) (tup: (a, a, a, a)) : b =
+  let (a, b, c, d) = tup
+  in g (g (g (f a) (f b)) (f c)) (f d)
+
+let markpits [h] [w] (field: [h][w]u8) : [h][w]u8 =
+  stencil 9 field
+    (\v env -> if red4 (\d -> v < d) (&&) env
+                 then v + 1
+                 else 255)
+
+let pits [h] [w] (field: [h][w]u8) : []u8 =
+  filter (!= 255) (flatten (markpits field))
+
+let grow [h] [w] (field: [h][w]u8) (basin: [h][w]bool) : [h][w]bool =
+  stencil (9, false) (zip2d field basin) (\(d, v) env -> d < 9 && (v || red4 snd (||) env))
+
+let floodfill [h] [w] (field: [h][w]u8) : *[h][w]bool =
+  let basin0 = map (map (!= 255)) (markpits field)
+  let basin1 = grow field basin0
+  let changed a b = reduce_comm (||) false (flatten (map2 (map2 (!=)) a b))
+  let (res, _) =
+        loop (a, b) = (basin0, basin1) while changed a b do
+          (b, grow field b)
+  in res
+
+let merge [h] [w] (ids: [h][w]i64) : [h][w]i64 =
+  stencil i64.highest ids
+    (\n env -> if n == i64.highest
+                 then i64.highest
+                 else i64.min n (red4 id i64.min env))
+
+let markbasins [h] [w] (basins: [h][w]bool) : *[h][w]i64 =
+  let numbers = unflatten h w (iota (h * w))
+  let ids0 = map2 (map2 (\n b -> if b then n else i64.highest)) numbers basins
+  let ids1 = merge ids0
+  let changed a b = reduce_comm (||) false (flatten (map2 (map2 (!=)) a b))
+  let (res, _) =
+        loop (a, b) = (ids0, ids1) while changed a b do
+          (b, merge b)
+  in res
+
+let collect_used_ids [h] [w] (ids: [h][w]i64) : []i64 =
+  let nums = flatten ids
+  let bitmap = scatter (tabulate (h * w) (\_ -> false)) nums (map (\_ -> true) nums)
+  in map snd (filter fst (zip bitmap (iota (h * w))))
+
+let ipow (base: i64) (exponent: i64) : i64 =
+  loop res = 1 for _i < exponent do res * base
+
+entry main [h] [w] (field: [h][w]u8) : (i32, i64) =
+  let ids = map (map (\n -> if n == i64.highest then -1 else n))
+                (markbasins (floodfill field))
+  let used = collect_used_ids ids
+  let sizes = map (\n -> reduce_comm (+) 0 (map ((==n) >-> i64.bool) (flatten ids))) used
+  let sizes_map = reduce_by_index (tabulate (h * w) (\_ -> 0))
+                                  (+) 0
+                                  sizes (map (\_ -> 1) sizes)
+  let count_size_cumulcount =
+        zip sizes_map (iota (h * w))
+        |> filter (\(cnt, _sz) -> cnt > 0)
+        |> reverse
+        |> (\arr -> zip arr (scan (+) 0 (map fst arr)))
+        |> take 3
+  let wanted_count =
+        map (\((cnt, _sz), cmlcnt) -> i64.max 0 (i64.min cnt (3 - (cmlcnt - cnt))))
+            count_size_cumulcount
+  let part2 = reduce_comm (*) 1
+                (map2 (\wc ((_cnt, sz), _cmlcnt) -> ipow sz wc)
+                      wanted_count count_size_cumulcount)
+  in (reduce_comm (+) 0 (map i32.u8 (pits field))
+     ,part2)
diff --git a/2021/9.in b/2021/9.in
new file mode 100644
index 0000000..10120f9
--- /dev/null
+++ b/2021/9.in
@@ -0,0 +1,100 @@
+9876543234679310943456798433456798998764321357921025689921987899896498799923491297654545679876212347
+6987675036678939874567987012567897899975532467892334567890996789789989679895989398743236789865101456
+5598983124589598765689765423678956789876543568943565678999765395679876598789678987654345998764313689
+4349994235695329976789998634678946789987987679757678989398653234598767459654567998767499899875424568
+3298987656795419899896459745989134568998998789968789699219772123987654398753456899989989689986576789
+2126598787896998788902349897991013457899999997989994567909765244598875697542346789798764593987897897
+1012349898999887567893956999543234967967988656799323459898954355699876989331238996659875691298998956
+4123467999598765456789897987654347899659876545678912398767896466789987979210349965545996789399659235
+3234598985439878567896789198795456789898765434189329987546789998994699867991467894534987899985432123
+4347899876567989678965994349987897899909996521034998675323597899123989659889578943023498999875321014
+5456987997689299989254789498798998999919989992129876543213456789239877545678989432145999998989432345
+6567896798792109892123569987679999998898767889234997854324597994399765434689996565236789987698544456
+7898945689899998763012458976597989987784345678949998985434989219987654323456899854345699996597655678
+8949239796958899954124567895435678996543234567897889876599878998698765435678998765496978989498966899
+9932198965346789867258789932124567987655123458976778987988769876569876646889019887989869979329987957
+9893987896234568954345898743245798998766234567894567899875457987421987756799934999876649868912398946
+8789876789195689875457999655466799679879845678913348987654346987630298867897895988965432946794459435
+7653245678989799876767899867578954568989658799101234999869234598541349998976789876894321987895568910
+9654134789678986988979989878989243456799767895312349898998945987676556789345698765789210398996678999
+8765245696567895399898979999599012367899898986423498776566899999887687990296987984694331239989989888
+9954346897379964219787767893478943479901999597434569653465678999998798921989896593789452398978998767
+0976557898298965398656456794569894998919589439765698542324599689929899439976789432599543987767999656
+2998678999997897987642347895698769867898478929876987321015689599845996598765678953498959876656897545
+9859789899886789998756468998789655456797569999989996432326796498656789987654567894997899965545998968
+7643996798654567949898979659897643245698979989994987543689895329868999998765678949876778964234899879
+5432345697543458957999989545998732124569998967943198964599943210979098969876899129875467996446789989
+8584557987654569767899993123989841034979987654599979989679985341989197854987989039654346789677899899
+7675678998765699898988932034976432149898998863278954393989876832698986543298968998765956799898998789
+8776789439897789909977794255987543298787899985369893212399989764567997432129456789979899989949987699
+9899899524989896429865689356898655398656799876456789105679899895678987521012359891398797778932397569
+9987978939878987898754578967898786499545892998968994323456789989989498432154467910987676567891986478
+9876568998767898999743679879969897987656901239879895544678999879897599543265998934977567456789765399
+7765459876546999898654798989456998998767893446989796665678998768789987654399899949765432345996996989
+6984345995437898759995987892399999439978998669995689776889997656667998969989789899986645567895789878
+5493234989425789647889876891987899321989998778934578987999876543459549998875569789998786688934899767
+4321049875414678936979965789976678910198989989323469998967987652368932987654414579989887999023987656
+5493959954323469324767894679864567891987878993212378999545698710456891099843203458976998942125998543
+7989898965434568913456893589653456789876567992105567894434789322567992129874212367895459993349879432
+8979767996576679102378921098732345898676456789213458943226798763456789298765673456789345989659765310
+9865656889677889293467892129641237899545345698924567899012999654567899349876654597891299978978987821
+8654345679898999989679953498432356789321234567897698978929898765678998956987875698910987567899398932
+7543234578929898878989769976544578996532356878998789567998769888789987897898986789321297478921239543
+5432143456919657667899898989757689987653479989019893478987847999898796789949997996548396567890198656
+8961012367898943456789987698768789998954568998929989569876435445989654678929898987657987678954239967
+7642123456976432367893297569899898769765679456998678978987321334678965799898769598767998999876349879
+8843234568965321245892195479901989859887894367899568989765410123457896893799654329878999899987456989
+9754545678976432496789989567899876543998999578965467999876923245569987932679954212989898789998567894
+9898758789876545789897678998967989862369998679754345699989874356998898921569896102398767678999978943
+9998767894988656896935569549459898973456899789643234987998765459876789932499789213988654589989899432
+8789978943299767965423478921298767895569964996532146986799878598765999893987689929876542679878798921
+9689989652129878987314567890989856789678953987844299875989989679754666789986567898986321299767687899
+6567897541012989796205679999976545679999654598765987654678998798673245678965438957895410987954576778
+4489995432123497654317895798765432459898767679876798763567899899542134589875312346689929996543134567
+3235789543235698785456954349876721248789878789989899874698999998753234696543201234567898987654235678
+2124678965346789896787893212987210187678989892198942976789998769876545987654415345698976798966547899
+1014589878456893987899954301297321234589899999977893988894987456998668998765623466989765429987858943
+2123578989569902398978975212976542475789789998756789199953986568989889679876734569879954312398969652
+3234567897698943469869865323987643567898699999547894349992197689679995566987655698767893202459878943
+4345978998997899598756998764598764678987569898769976998989999796598754324499878999859994312378989965
+5656899569866968965431279879689985789998498769878989876865778965469843212347989898948975459459999876
+6787932499754357896542456998789699899886329856989999765954567894345954353456798797837988678969878997
+7898953987643239919757567899897543998765498745899886644212678901234969754668997655126898789998868998
+8999654996544128929898978934998631349877899635789765432103789212349898975678986543235679892987657899
+9998969875431017999939989325698752356989998523489876643214897423598787896999697655356799921098545989
+9997978996652126789129893216799763467899896412678999765625996545987676569896598766587898943985432877
+9886899429863245679399789109999878978998765324569769889436789679876543456789439898698987899874321466
+8765678910964376899987698998784989989549995445678945996547899798965432387696429999789556789766440355
+7654569899875487999896587899543494399929987678799434987667934977994321234597998998995445678954321234
+6543456789989568998785476998932359239898998989893223699788999866789410165789896987654324479765535445
+5432567899987678997665365767899498998767999699932104567999987654789421256899765698985212356986787568
+4321256789999789886543214456798997987656789569543213469765498765678933345998754109876323567897898679
+5434345678998998765432102349987856798545993498994999578954329878989654658987653212987434878998929989
+6565656799567899876545214498986534987656789597789878989865912989498768767899864324598546789989939999
+7676768923456999987756725987995423898967896986678767993999894994239989878998975435987659896765798989
+8787879734567898998998999876789545789989954965483458912987789892129796989787896745898789975454447678
+9898989656789987889999987494899656789195899754312379909876556789097645692546999856789897654322334589
+8969398797996545978899976323678967991024789876106567899985434567998732101235678969897998854310123459
+7654249899975323456789985214567898942195678998217879999876524567986544212346989989976799965924265678
+8652135987976896568999953107998929769989899999356989998765213456987656434587896492455678999895696799
+9543299876989987689659864315789319898878989876467999989874301345699786547998954321234589987689989892
+7654987664698998796549874323498901997659878987578997779765432456789987856899967432355678996578678921
+9965799543567899987856975434567892987543656898989986569876753697897598767977898645698789975457568910
+9899898632356792198977896565678969876532345689995987432987884789966449878956789876899899764325457891
+6678997653458999299989979876799349865431334678953294321098765789654323989345999988967998955212345789
+4599298964578998988998968987891234986210123689964498753129877897654312993234789999654987742101234699
+3989129765679997667987899998910129876433234589876569876534988998973209894365678919869876543232348789
+2878939876799896543566999879321236997645345679987893997699999529994698765489799201978997654343469892
+3467899987986789432355698765432345698987456789298932398988965410989989876569895412399989765499598921
+5679979999895678921234569989543456789998987891019643599877896329879879999678976523989878979988987932
+6789568987784569990146678998656567899969898989998754988756899499764768998789897949876767989877656893
+9893499976543478989236789239767898998756789878899869876645798987653456799898789498765456799765346789
+6912987665421299879345678949879989976545698765789979865434687898432567895965689398754345678974235699
+5439876543210987769967899999989567895431987543695491984323456989943458954397899999665265667895127678
+6545997654521976458899910989996468986532398654599392395664677979894568965989959876543123456789024568
+7666798766439894346778929878987347897747498765678989987775899866789789999878943997651016567892123456
+8789899876598789234567898969876456798856569876789778998986798754989899989766959898764323456789236768
+9898999987697655139879987655987898949987899987894566989987986543478999876745898759877467897897345679
+8967998799798743016791098943498929956798999898913455678999876542359998765636789542976578949985498789
+7649876549899752145892987632349547897899498769101234589212987656767899443323498931987989539876569893
+8432987632999863236789876545678956789902349854213455678903498987898954321014567890198994321987689912
diff --git a/2021/9.sh b/2021/9.sh
new file mode 100755
index 0000000..739d62d
--- /dev/null
+++ b/2021/9.sh
@@ -0,0 +1,13 @@
+#!/usr/bin/env bash
+if [[ $# -ge 1 ]]; then
+	if [[ $1 = c ]]; then
+		xsel -bo | ./9pre | ./9
+	elif [[ $1 = - ]]; then
+		./9pre | ./9
+	else
+		echo >&2 "What are you even doing with your command line params"
+		./9pre <9.in | ./9
+	fi
+else
+	./9pre <9.in | ./9
+fi
diff --git a/2021/9pre.cpp b/2021/9pre.cpp
new file mode 100644
index 0000000..2ef4707
--- /dev/null
+++ b/2021/9pre.cpp
@@ -0,0 +1,26 @@
+#include <iostream>
+#include <vector>
+#include <string>
+#include <cstdint>
+
+
+int main() {
+	std::vector<std::string> lines;
+	std::string line;
+	while (std::getline(std::cin, line)) {
+		for (char &c : line) c -= '0';
+		lines.emplace_back(std::move(line));
+	}
+
+	const uint64_t height = lines.size();
+	const uint64_t width = lines[0].size();
+	std::cout.put('b');
+	std::cout.put(2);
+	std::cout.put(2);
+	std::cout.write("  u8", 4);
+	std::cout.write((const char*)&height, 8);
+	std::cout.write((const char*)&width, 8);
+	for (uint64_t y = 0; y < height; y++) {
+		std::cout.write(lines[y].data(), width);
+	}
+}
diff --git a/2021/Makefile b/2021/Makefile
index 7ad280f..bacaeff 100644
--- a/2021/Makefile
+++ b/2021/Makefile
@@ -3,6 +3,7 @@ GHCBASEFLAGS = -package parsec -package array
 GHCFLAGS = $(GHCBASEFLAGS) -Wall -O2 -threaded -fdefer-typed-holes
 CXX = g++
 CXXFLAGS = -Wall -Wextra -std=c++17 -O2
+FUTHARK = futhark
 
 OBJDIR = obj
 
@@ -12,8 +13,10 @@ HASKELL_SRC := $(filter-out $(HASKELL_AUX),$(wildcard *.hs))
 CPP_SRC     := $(filter-out $(CPP_AUX),$(wildcard *.cpp))
 HASKELL_BIN := $(HASKELL_SRC:.hs=)
 CPP_BIN     := $(CPP_SRC:.cpp=)
+FUTHARK_SRC := $(wildcard *.fut)
+FUTHARK_BIN := $(FUTHARK_SRC:.fut=)
 
-BINARIES := $(HASKELL_BIN) $(CPP_BIN)
+BINARIES := $(HASKELL_BIN) $(CPP_BIN) $(FUTHARK_BIN)
 
 .PHONY: all clean depend
 
@@ -36,6 +39,9 @@ $(HASKELL_BIN): %: %.hs | $(OBJDIR)/%
 $(CPP_BIN): %: %.cpp $(CPP_AUX) | $(OBJDIR)
 	$(CXX) $(CXXFLAGS) -o $@ $<
 
+$(FUTHARK_BIN): %: %.fut
+	$(FUTHARK) c $<
+
 $(OBJDIR)/%:
 	mkdir -p $@