K Idioms
========

These are some fun ngn/k tricks idioms and tricks I've found helpful in solving this year's challenges.


Grade? What's that?
-------------------
When first learning an array language, grade might seem odd. What use could knowing the indices to sort an array be? But this turns out to be a superpower: you can pre-process the array first.

For example:

 a:("crocodile";"alligator";"mouse";"bear";"squid")  / animals

 a@<a          / sort normally
("alligator"
 "bear"
 "crocodile"
 "mouse"
 "squid")
 #'a           / length of each animal's name
9 9 5 4 5
 a@<#'a        / sort by length
("bear"
 "mouse"
 "squid"
 "crocodile"
 "alligator")
 a@<a@\:1      / sort by second letter
("bear"
 "alligator"
 "mouse"
 "squid"
 "crocodile")

 :l:a!8 2 7 10 3  / how much i like each animal
("crocodile";"alligator";"mouse";"bear";"squid")!8 2 7 10 3

 a@>l a           / most liked to least liked animals
("bear"
 "crocodile"
 "mouse"
 "squid"
 "alligator")

Group it!
---------
Similarly to grade, group acts as a group-by:

 a@=#'a  / group animals by word length
!/+((9;("crocodile";"alligator"))
    (5;("mouse";"squid"))
    (4;,"bear"))

Let's say you have an array of keys and an array of values, and you want a dict that associates the each key to all its values. Here are two ways to do it:

 k:`a`b`c`a
 v:9 2 8 3
 v@=k
!/+((`a;9 3)
    (`b;,2)
    (`c;,8))
 =v!k
!/+((`a;9 3)
    (`b;,2)
    (`c;,8))

Suppose you are on Halloween, taking candy orders. You have two lists: one of kids, and another of their preferred candies. However, some naughty kids request multiple candies, and they are only allowed one! We want to take only the first request of each kid.

 k:`dan`bob`alex`dan`martha`john`martha
 c:`smarties`mnm`reeses`caramel`reeses`lollipop`toffee
 c@=k
!/+((`dan   ;`smarties`caramel)
    (`bob   ;,`mnm)
    (`alex  ;,`reeses)
    (`martha;`reeses`toffee)
    (`john  ;,`lollipop))
 *'c@=k
!/+((`dan   ;`smarties)
    (`bob   ;`mnm)
    (`alex  ;`reeses)
    (`martha;`reeses)
    (`john  ;`lollipop))

Fixpoint Fun
------------
Many things defined by fixpoints can be implemented with converge.

For example, the golden ratio ɸ = a%b = (a+b)%a. In other words, it's the ratio of two lengths when that ratio is equal to the ratio of the sum of the lengths to the longer length.

a%b  =  (a+b)%a
a%b  =  (a%a) + b%a
a%b  =  1 + b%a
ɸ    =  1 + 1%ɸ

So, the golden ration is a fixpoint of the function 1+1%
We can use this to calculate the golden ratio:

 (1+1%)/1
1.618033988749895

Say we have a grid, and we want to know the shortest distance from the start to all squares. This solution is the fixpoint to the function where every square's value is the minimum of itself and 1 + its neighbours, since to go from a neighbour to yourself is an increase of one step.

This can be used anywhere you need a floodfill/dijkstra's, though it is much less efficient than the traditional imperative way.

A clean implementation of this in day 18, and I also use it in days 12, 16 and 24.


Moving a Position
-----------------
If you store velocity and position as (vel;pos), you can do:

 x:2 10
 +/x    / next position (1 step)
12
 14/x   / 14 steps
38
 +\x    / next position with same velocity (so you can move again)
2 12
 -/|x   / previous position
8
 -':x   / previous position with same velocity
2 8

Generating Direction Vectors
----------------------------
To generate a list of up, down, left, and right, we can use ,/-:\=2, which is the concatenation of I2 and its negation.
To generate a list of these and diagonals, we can use (+1-!3 3)^,&2. Often, you can eliminate the ()^,&2 by writing your function so that not moving doesn't do anything.

 ,/-:\=2
(1 0
 0 1
 -1 0
 0 -1)
 (+1-!3 3)^,&2
(1 1
 1 0
 1 -1
 0 1
 0 -1
 -1 1
 -1 0
 -1 -1)

Seed Sowing
-----------
If we want to make sure f holds for x and g holds for all elements of y, our first instinct might be to use (f x)&&/g'y. However, we can use a seed to make this nicer: (f x)&/g'y. Of course, this also applies for other folds (|, *, etc).

 f:0<
 g:~2!
 (f 3)&/g 8 2 4
1
 (f 3)&/g 8 2 5
0
 (f -10)&/g 8 2 4
0

Index in Range?
---------------
To check if an index x is the range of an input array i, we can use (~^i.)x. This indexes into the array, and makes sure it's not null (i.e. it is a valid index). However, it won't work if there are any nulls (probably spaces) in your array.

 i:("***";"*..";".*.")
 x:2 1    / a valid index
 (~^i.)x
1
 x:3 -4
 (~^i.)x  / an invalid index
0

~/aoc24k/idioms.html