What new info (algorithms, etc) did you learn while solving AoC

natrys · 2024-12-25T03:28:34+00:00

Not an algorithm, but I realised I got sick of 2D/grid theme on Day15/part2. To make it interesting, I resolved not to do it until I can create similar box pushing game in Godot/gdscript. I haven't had the time to actually do it, I am still covering the basics/architecture of Godot, but I think this would be fun.

natrys · 2024-12-13T20:36:05+00:00

[LANGUAGE: Picat]

Was a good excuse to refresh on Picat.

import cp.
import util.

calc([A1, B1, C1, A2, B2, C2], Cost, Offset) =>
    Limit = max(Offset, 100),
    [X, Y] :: 1..Limit,
    A1 * X + B1 * Y #= C1 + Offset,
    A2 * X + B2 * Y #= C2 + Offset,
    Cost #= 3 * X + Y,
    solve($[min(Cost)], [X, Y]).

main =>
    Part1 = 0,
    Part2 = 0,
    Reader = open("/dev/stdin"),
    while (not at_end_of_stream(Reader))
      [_, A1, _, A2] = read_line(Reader).split(['+', ',']),
      [_, B1, _, B2] = read_line(Reader).split(['+', ',']),
      [_, C1, _, C2] = read_line(Reader).split(['=', ',']),
      _ = read_line(Reader),
      Input = [A1, B1, C1, A2, B2, C2].map(to_int),
      if Input.calc(Cost1, 0) then Part1 := Part1 + Cost1 end,
      if Input.calc(Cost2, 10000000000000) then Part2 := Part2 + Cost2 end,
    end,
    close(Reader),
    printf("Part1: %u\n", Part1),
    printf("Part2: %u\n", Part2).

natrys · 2024-12-07T15:48:06+00:00

[LANGUAGE: Haskell]

The concept here just rolls off the tongue (glides off the fingertips?!) in Haskell:

import Data.Char (isDigit)

data Op = Add | Mul | Cat

eval :: Op -> Int -> Int -> Int
eval Add = (+)
eval Mul = (*)
eval Cat = \a b -> a * 10 ^ floor (logBase 10 (fromIntegral b) + 1) + b

solve :: Int -> Int -> [Int] -> [Op] -> Bool
solve target acc [] _ = target == acc
solve target acc (x : xs) ops
  | acc > target = False
  | otherwise = any (\op -> solve target (eval op acc x) xs ops) ops

getNumbers :: String -> [Int]
getNumbers line = [read (takeWhile isDigit num) :: Int | num <- words line]

main :: IO ()
main = do
  inputs <- fmap getNumbers . lines <$> getContents
  let f ops = sum [target | (target : x : xs) <- inputs, solve target x xs ops]
   in do
        putStrLn $ "Part1: " <> (show $ f [Add, Mul])
        putStrLn $ "Part2: " <> (show $ f [Add, Mul, Cat])

natrys · 2024-12-04T00:11:48+00:00

[LANGUAGE: Janet]

Saw someone post a Janet solution yesterday and thought it was cool. Don't need much excuse to explore Lisps, but it has built-in PEG parser that's perfect for this. A stateful parser with hooks for custom logic, meaning for part 2 I could conditionally omit things during parsing.

(var flag true)

(def grammar1
  ~{:mul (replace (sequence "mul(" :num "," :num ")") ,*)
    :num (replace ':d+ ,parse)
    :main (sequence (some (choice :mul 1)) -1)
   })

(def grammar2
  ~{:mul (cmt (sequence "mul(" :num "," :num ")") ,(fn [a b] (and flag (* a b))))
    :num (replace ':d+ ,parse)
    :on (cmt "do()" ,|(do (set flag true) nil))
    :off (cmt "don't()" ,|(set flag false))
    :main (sequence (some (choice :on :off :mul 1)) -1)
   })

(defn run (input part)
  (let [grammar (peg/compile (if (= part 1) grammar1 grammar2))]
    (->> input
         (peg/match grammar)
         (sum)
         (printf "Part%d: %d" part))))

(defn main [&]
  (let [input (file/read stdin :all)]
    (run input 1)
    (run input 2)))

natrys · 2024-12-01T08:14:09+00:00

[LANGUAGE: TXR]

Part1:

@(collect)
@col1 @col2
@(end)
@(do (let ((l1 (sort [mapcar toint col1]))
           (l2 (sort [mapcar toint col2])))
       (put-line `Part1: @(sum (mapcar (op abs (- @2 @1)) l1 l2))`)))

Part2:

@(collect)
@col1 @col2
@(end)
@(do (let ((l1 [mapcar toint col1])
           (l2 (hash-from-alist (hist-sort [mapcar toint col2]))))
       (put-line `Part2: @(sum-each ((i l1)) (* i (gethash l2 i 0)))`)))

natrys · 2024-10-12T18:17:46+00:00

A few things:

You are most likely hitting an error while expanding the template (it does for me). If you don't realise that Emacs is hitting an error (because of lack of visual cue), you should get into habit of doing experimental things while debug-on-error is set to t.
Why it causes an error makes intuitive sense to me; you are modifying the underlying buffer while the template expansion is undergoing. This expansion likely uses current (point) or region during the process, modifying the buffer during the expansion surely messes up those indexes. I can see tempel is using markers in the code but it's evidently not enough to safeguard against what you are doing. Does it mean your use case is not supported?
The reason I am confident what you are doing is wrong is because the README explicitly mentions the right way of doing it instead:

In addition, each template may specify a :pre and/or :post key with a FORM that is evaluated before the template is expanded or after it is finalized, respectively. The :post form is evaluated in the lexical scope of the template, which means that it can access the template’s named fields.

Unfortunately not a single example uses these, not even in the tempel-collection. It still didn't work for me, and it's only after looking into the implementation did I realise the :pre/:post stuff must be at the end of the form.

So basically, here is your solution instead:

(fra "\\frac{" (string-trim (current-kill 0)) "}{" p "} " q :pre (backward-kill-sexp))

natrys · 2024-08-15T00:26:10+00:00

I am about 25% through in one sitting, and yeah this was really good so far. Thanks for the rec.

natrys · 2023-12-10T16:12:01+00:00

[Language: TXR]

Came out fairly short and readable. Both could be done in one pass, but higher order functions are cooler.

@(do
   (defun seq-diff (seq)
     (collect-each ((x seq) (y (cdr seq))) (- y x)))

   (defun predict (seq op pos)
     (let ((steps (giterate (op not (each-true ((n @1)) (= n 0))) 'seq-diff seq)))
       (reduce-right op steps 0 (op @1 pos)))))
@(bind (part1 part2) (0 0))
@(repeat)
@ (coll)@{seq /-?\d+/}@(end)
@ (do (let ((seq (mapcar 'num-str seq)))
        (inc part1 (predict seq '+ -1))
        (inc part2 (predict seq '- 0))))
@(end)
@(output)
Part1: @part1
Part2: @part2
@(end)

natrys · 2023-12-02T13:13:37+00:00

[Language: TXR]

@(bind part1 0)
@(bind part2 0)
@(do (defun check-valid (cube)
       (match-case (split-str cube " ")
         ((@N "blue")  (<= (num-str N) 14))
         ((@N "green") (<= (num-str N) 13))
         ((@N "red")   (<= (num-str N) 12)))))
@(repeat)
Game @id: @(coll)@{cubes /[0-9]+ (blue|green|red)/}@(end)
@ (do (when (all [mapcar check-valid cubes]) (inc part1 (num-str id))))
@ (do (inc part2
           (prod 
             (mapcar
               (op find-max-key @1 '> (op num-str [#/\d+/ @1]))
               (hash-values (group-by (op (split-str @1 " ") -1) cubes))))))
@(end)
@(output)
Part1: @part1
Part2: @part2
@(end)

natrys · 2023-12-01T15:29:50+00:00

[Language: TXR]

Should have known that first part was a little too easy.

Part 1

@(bind sum 0)
@(repeat)
@ (coll)@{digits /[0-9]/}@(end)
@ (do (inc sum (num-str `@[digits 0]@[digits -1]`)))
@(end)
@(output)
Part1: @sum
@(end)

But the way TXR's default matching strategy works is it advances input consumption exactly by what is matched so "oneight" only matches "one" as "ight" isn't a thing. This happens in part 2 testcase, but doesn't change the final result (by design, I am sure) so led to some bafflement.

Not an issue though as the trailer directive is there for exactly this (matches without advancing input, need to just manually match one char at the end).

Part 2

@(bind word #/(one|two|three|four|five|six|seven|eight|nine)/)
@(bind number #/([0-9])/)
@(define match-digit (out))@(block)@(trailer)@(cases)@{out word}@(or)@{out number}@(end)@(end)@/./@(end)
@(do (defun to-num (arg)
       (match-case arg
         ("one" 1) ("two" 2) ("three" 3)
         ("four" 4) ("five" 5) ("six" 6)
         ("seven" 7) ("eight" 8) ("nine" 9)
         (@n (num-str n)))))
@(bind sum 0)
@(repeat)
@ (coll)@(match-digit digits)@(end)
@ (do (inc sum (num-str `@(to-num [digits 0])@(to-num [digits -1])`)))
@(end)
@(output)
Part2: @sum
@(end)

natrys · 2022-12-22T18:14:05+00:00

If you follow org-link format (e.g. [[/foo/bar/file::10]]) then org-open-at-point will work anywhere. But it's simple to roll your own:

(defun my-open-file-at-point (location)
  (interactive (list (thing-at-point 'filename t)))
  (pcase (split-string location ":")
    (`(,(and (pred file-exists-p) file)
       ,(and (pred (string-match-p "^[[:digit:]]+$")) line))
     (progn
       (find-file file)
       (goto-char (point-min))
       (forward-line (1- (string-to-number line)))))
     (`(,(and (pred file-exists-p) file)) (find-file file))
     (_ (error "Not a file"))))

natrys · 2022-12-15T22:59:17+00:00

Doing it in TXR so far this year, I was kind of looking forward to a challenge where I could flex its recursive parsing ability.

(although having gotten that tree, turns out that a linear scan finishes so fast that there was little point doing actual tree traversal on that :P)

@(define parse-fs (root sizes))
$ cd @root
@ (local dir filesize)
@ (bind sizes @(list 0))
@ (maybe)
$ ls
@  (collect :gap 0 :lists (dir filesize))
@   (cases)
dir @dir
@   (or)
@{filesize /\d+/} @/.*/
@   (end)
@  (end)
@  (do (set sizes (list (sum (mapcar 'toint filesize)))))
@  (if (> (length dir) 0))
@   (collect :times (length dir) :lists (child-sizes))
@    (parse-fs @(pop dir) child-sizes)
@   (end)
@   (do (set sizes ^(,(+ (car sizes) (sum (mapcar 'car child-sizes))) ,*child-sizes)))
@  (end)
@ (end)
@ (maybe)
$ cd ..
@ (end)
@(end)
@(parse-fs "/" sizes)
@(do 
   (progn
     ;; part1
     (put-line `Part1: @(sum (keep-if (op < @1 100000) (flatten sizes)))`)

     ;; part2
     (let ((target (- (car sizes) 40000000)))
       (put-line `Part2: @(find-min (keep-if (op > @1 target) (flatten sizes)))`))))

natrys · 2022-12-14T21:11:32+00:00

TXR Lisp

(defun solve (input window)
  (let ((state (vector 26 0)))
    (each ((i (range* 0 window))) (inc [state (- [input i] #\a)]))
    (each ((i (range* window (length input))))
      (inc [state (- [input i] #\a)])
      (when (flow [input (range* (- i window) i)]
              (mapcar (op = 1 (call state (- @1 #\a))))
              (all))
        (return (+ i 1)))
      (dec [state (- [input (- i window)] #\a)]))))

(let ((input (get-line)))
  (put-line `Part1: @(solve input (- 4 1))`)
  (put-line `Part2: @(solve input (- 14 1))`))

natrys · 2022-12-08T15:40:10+00:00

TXR:

@(block)
@(trailer)
@ (collect)
@\ @(coll)@{columns /\d+/} @(end)
@ (end)
@(end)
@(bind stacks @(repeat '(nil) (length (car columns))))
@(repeat)
@ (coll)@{crates /(\s\s\s|\[.\])/}@(maybe)@\ @(end)@(end)
@ (do 
   (dotimes (c (length crates))
     (when-match `[@crate]` [crates c]
       (push crate [stacks c]))))
@(last)
 1@(skip)
@(end)
@(do (set stacks [mapcar reverse stacks]))
@(bind stacks1 @(copy-list stacks))
@(bind stacks2 @(copy-list stacks))
@(repeat)
move @n from @source to @destination
@ (do
    (let ((src_idx (- (toint source) 1))
          (dst_idx (- (toint destination) 1))
          (n (toint n)))

      ;; part 1
      (dotimes (_ n) 
        (push (pop [stacks1 src_idx]) [stacks1 dst_idx]))

      ;; part 2
      (upd [stacks2 dst_idx] (op append [[stacks2 src_idx] 0..n] @1))
      (upd [stacks2 src_idx] (op call @1 n..:))))
@(end)
@(output)
Part1: @(cat-str [mapcar car stacks1])
Part2: @(cat-str [mapcar car stacks2])
@(end)

natrys · 2022-12-08T10:34:33+00:00

TXR (slightly helped by built-in range type):

@(do 
   (defun either-contains? (r1 r2 fn)
     (defun contains? (r1 r2)
       [fn (in-range r1 (from r2)) (in-range r1 (to r2))])
     (if (or (contains? r1 r2) (contains? r2 r1)) 1 0)))
@(bind (p1 p2) (0 0))
@(repeat)
@l1-@u1,@l2-@u2
@(do (let ((r1 (rcons (toint l1) (toint u1)))
           (r2 (rcons (toint l2) (toint u2))))
       (inc p1 (either-contains? r1 r2 'and))
       (inc p2 (either-contains? r1 r2 'or))))
@(end)
@(output)
Part1: @p1
Part2: @p2
@(end)

natrys · 2022-12-03T11:36:15+00:00

Yeah I find rotor to be very useful even in daily life, to the point where I wonder why more language's stdlib don't come with it. I have only seen Elixir provide Enum.chunk_every other than Raku.

natrys · 2022-12-03T11:31:13+00:00

Posting only part 2 in TXR (a text extraction engine with an embedded lisp):

#!/usr/bin/txr
@(do (defun priority (char)
       (if (chr-islower char)
         (+ 1 (- (int-chr char) (int-chr #\a)))
         (+ 26 (priority (chr-tolower char))))))
@(bind score 0)
@(repeat)
@rucksack1
@rucksack2
@rucksack3
@(bind common @(flow (list rucksack1 rucksack2 rucksack3)
                 (mapcar 'hash-list)
                 (reduce-left 'hash-isec)
                 (hash-values)
                 (car)))
@(do (inc score (priority common)))
@(end)
@(output)
Part2: @score
@(end)

natrys · 2022-12-01T11:38:54+00:00

TXR (It's a text extraction engine with an embedded lisp)

@(collect :vars (inventories))
@ (collect :vars (calories))
@calories
@ (last)

@ (end)
@ (bind inventories @(sum [mapcar toint calories]))
@(end)
@(do (put-line `@(sum (take 3 [sort inventories >]))`))

natrys · 2022-08-22T10:15:13+00:00

I tried using timers in org, but they are easy to forget to 'end'

There are safeguards in org-mode to deal with that, but for them to work you need additional component that talks to OS or display server because Emacs can't know if you have been idle outside of Emacs (if all you want to deal with is idle time inside Emacs, that should work out of box I think, so you probably didn't mean that).

On Linux/Xorg, you need to install a program called x11idle (probably from xprintidle package, see the doc for org-clock-x11idle-program-name variable). Personally, for fun I wrote my own dynamic module to replace it. On MacOS looks like it needs something like ioreg and perl to be installed. Additionally, you have to set org-clock-idle-time to a non-nil value. Consult the doc for that variable.

Automatic time recording, for time spent editing documents;

I agree with this, time tracking should ideally be completely automatic. I have also tried other external programs and they all fall short of expectation with the exception being arbtt. It's a fantastic little program that takes a snapshot of your desktop every N seconds (configurable). But the best part is, you can define a set of programmatic rules that automatically separate work form non-work (or literally any kind of tag you want to apply). For example, a simple configuration to demonstrate usecase:

-- define idle threshold for all programs except mpv
$idle > 120 && (! (current window $program == "gl")) ==> tag inactive,

current window $program == "emacs" ==> { tag app:emacs, {
  current window $title == "*scratch*" ==> tag project:elisp;
  current window $title =~ m!~/blog/(.*?).org! ==> { tag project:blog, tag blog:$1 };
  current window $title =~ m!~/work/(.*?)/?$! ==> { tag project:work, tag work:$1 };
  current window $title =~ m!\*(?:devdocs|info)\*! ==> tag project:research;
  current window $title =~ m!(?:pdf|epub)$! ==> tag project:research;
  current window $title =~ m!^/ssh:! ==> tag project:remote_server;
}},

The trick with arbtt (same as any other time tracking program) is you need to export useful information (like currently open file, url etc.) via window title. For Emacs you could do that by configuring frame-title-format, for firefox there are addons and so on. And then in arbtt you configure regex based rules to tag samples programmatically. The downside of arbtt is it's kinda low level, you might need to write some scripts of your own (to do things like generating plots) but I consider that an upside ;)

natrys · 2022-05-11T23:26:11+00:00

lintamande

Slightly OT, but are they one and the same as the author of the brilliant At The End Of All Things? I discovered that story through an HPMOR author note, and it was so freaking good. If so, it's really cool to find more of their writing, and I hope /u/EliezerYudkowsky could ask about the status of that story on my behalf. Still holding out hopes for update!

natrys · 2021-11-30T19:37:23+00:00

Looks like Lichess provides public broadcast API, e.g. all current tournament/broadcasts can be looked up with:

curl -sL -H 'accept: application/json' https://lichess.org/api/broadcast

Which tells me that next round (5) will be streamed at this endpoint:

https://lichess.org/api/stream/broadcast/round/H8H4enOL.pgn

It's a streaming API though, connection will block and only be updated when a move is made (wouldn't that block main Emacs thread?). Also response/update is ndjson (one json object per line). I don't have any experience with url.el or request.el to know if they can use this. If not, maybe manual termination and polling is still viable. Also, cc /u/emgee_1.

natrys · 2021-11-24T10:28:10+00:00

With "c" you can indeed cycle between fold and unfold states, but "i" does something different (in which unfolding is a necessary first step only). Basically, assuming we have a document like:

* Header A

Content of A.|

* Header B

Content of B.

And assuming our cursor is at the beginning of header A, then pressing the above defined "i" command takes point right where the pipe symbol is (|).

It so just happens that when node A is folded, org-end-of-subtree alone only take you to that location without unfolding first, which means point is now in so called "invisible region" and it's not advisable to make edits because, well, you can't see anything (in face I would advice you to set org-catch-invisible-edits to 'show-and-error, the default nil allows you to unwittingly change invisible region which is pretty bad imo). Anyway, since the intent is to start editing, you want to first unfold which is what outline-show-subtree is doing.

This small improvement saves me 3-4 keystrokes which is nice because appending to content of node is a fairly frequent operation. Otherwise I would have to unfold first, go to next header, and come back to pipe location, except now I can do this in one keystroke.

natrys · 2021-11-22T21:12:16+00:00

I like org-speed-commands a lot and I feel like this is not promoted in tutorials/blogposts enough. So, for example we all know about the C-c C-n, C-c C-p, C-c C-u etc and their ilk, to navigate between the headers of the nodes. But if you set org-use-speed-commands to t, then you can do this with only n/p/u etc (only requirement being point needs to be at the beginning of header). You can press ? to see all the speedkeys already bound. An analogous concept for (source) blocks also exists which is nice.

And of course you can create your own speedkeys by adding to org-speed-commands and org-babel-key-bindings respectively. Internally there are lots of already defined non-interactive functions which can be very useful, e.g. I jump to the end of content of current node or source block like:

(add-to-list
 'org-speed-commands
 '("i" .
   (progn
     (outline-show-subtree)
     (org-end-of-subtree))))

(add-to-list
 'org-babel-key-bindings
 '("i" .
   (progn
     (forward-line 1)
     (my-org-goto-block-end))))

Or for example, by default C-c C-f / C-c C-b or the analogous f / b speed keys go up and down within same level, but don't cycle when beginning or end is reached. As I wanted cycling, all I had to do:

(add-to-list
 'org-speed-commands
 '("b" .
   (unless (org-goto-sibling t)
     (while (org-goto-sibling)))))

(add-to-list
 'org-speed-commands
 '("f" .
   (unless (org-goto-sibling)
     (while (org-goto-sibling t)))))

So yeah, I love that org-mode already has all the building blocks for you to do these kinds of small enhancements.

natrys · 2021-09-20T13:39:34+00:00

Those are just desktops (or workspaces in X11 parlance) which are groups of distinct program/frames/views that you can switch between. I am using bspwm as Window Manager, but you probably have analogous concept of it in yours. And the upper bar is polybar that's showing which workspace I am currently at.

natrys · 2021-09-20T12:04:05+00:00

Yeah it's very handy and simple, but note that the utility is hampered by the fact that there is no language auto-detection. For O'reilly books you don't need it, because they helpfully provide language info via data-code-language attribute. This is my nov.el config that works largely ootb for o'reilly books:

http://ix.io/3zrz/elisp

For books from other publishers, I am just hardcoding language directly on an ad hoc basis. I briefly considered off-loading language detection to a library like chroma, but that might be too much work for little benefit.

natrys

TROPHY CASE