Florentin Putz December 2021

Advent of Code 2021, using J

The Advent of Code is an annual programming competition with fun problems for each day in December leading up to Christmas. In 2021, I teamed up with some colleagues from work to participate. It was fun working on these problems, seeing each day who was the fastest, and discussing our individual approaches afterwards. One of my colleagues used C++, another chose Nim, but most used Python. Typically, I would gravitate towards Python as well, but I decided to add some variety to the team by using J.

J (jlang)

J is a great array programming language by Turing Award winner Kenneth E. IversonIverson received the Turing Award in 1979 “for his pioneering effort in programming languages and mathematical notation resulting in what the computing field now knows as APL”. and Roger Hui. It is heavily inspired by APL, but without the funky non-ASCII characters.

J’s syntax is terse and has a high information density. Usually, the whole program you are working on easily fits on the screen, which is by design so that at all times you can see what’s going on. This terseness admittedly can look weird (and even random) if you are not familiar with APL, but the notation follows logical rules and is seen as a tool for thought.If you’re unfamiliar with array programming languages, I recommend checking them out. They really broadened my perspective on programming, much like when I first learned about functional programming through SICP.

Disclaimer: I’m a beginner in J, having used it only sporadically for a couple of years as a hobby to tackle some programming challenges. While I provide solutions below, there may be more elegant methods available — I’m still not fully familiar with J’s entire standard library.

From a competitive standpoint, I would have been faster to get to a solution with Python, as I’m just much more familiar with that language. For me, working with J is more like solving a puzzle: reframing the problem in terms of array programming, and then figuring out the right built-in functions and language features. And it’s actually very fulfilling to challenge yourself how far you can get without for or while loops; to appreciate the elegance of the resulting code. The REPL workflow works quite well for that type of iterative development, where you incrementally work towards the solution.

Another interesting observation: While it took me some time to get to a solution, the resulting J code often had impressive execution speed (which we also benchmarked). Most of the time, my J code was faster than the best Python code in our team, sometimes even rivalling or surpassing the compiled C++ or Nim speed.

Advent of Code

Check out the problem descriptions for each day on the AoC website. They are really nicely written and follow the elves on their overarching quest to save Christmas.

Each of my solutions will print two numbers, corresponding to the two parts of the problem. My solutions are also available on GitHub; you can execute them using jconsole.

Day 1

in=. ". 'm' fread 'in/01.txt'
echo +/ 2</\ in
echo +/ 2</\ 3+/\ in

For part 1, we are supposed to count the number of values that are larger than the previous value in an array. This can be solved very elegantlyOr rather: compactly. But even if you don’t plan to golf these problems, you might find the compactness inherently elegant. in an array programming language like J, by working on array infixes of size two and counting the amount of ascending infixes. The built-in functions in J can be called using just one or two characters, and these functions (called verbs in J) can be composed and combined, like in functional programming languages. The verbs can also be modified using higher-order functions (called adverbs). But the killer feature is that every function inherently can be applied not only to single values, but also to arrays of two or more dimensions.

For example, consider part two of the problem, which involves calculating sums of a three-measurement sliding window over the input array. The problem description gives the following example:

A      
A B    
A B C  
  B C D
E   C D
E F   D
E F G  
  F G H
    G H
      H

The measurements in the first window are marked A (199, 200, 208); their sum is 199 + 200 + 208 = 607. The second window is marked B (200, 208, 210); its sum is 618.

In J, this can be implementing by applying a statement of just four characters to the input array:

3+/\ in

Let’s look at this code in a bit more detail. It is a J sentence, consisting of the nouns 3 and in, the verb +, and two adverbs / and \. The verb + is easy to understand, because it sums elements. The adverb / modifies this verb to fold it between multiple elements of some higher dimensional array. The adverb \ further modifies the verb to work on infixes of the argument. The parameter 3 makes it construct a three-element sliding window over the input array in. As a result, this statement inserts the + verb between all elements within each three-element infix to calculate the sum of each position of the sliding window.

This example already shows a glimpse of the strength of array programming languages, since we were able to solve this problem without any explicit looping constructs (no for loops), by composing and modifying functions which work not only on single elements but on higher dimensional data.

The following solutions might be interesting to those already familiar with J.

Day 2

'a b' =. |: ;: 'm' fread 'in/02.txt'
b =. ".b
s =. ({."1 a)=]
horizontal =. (b * s'f')
vertical =. b * (s'd') - (s'u')
echo (+/horizontal) * (+/vertical)
echo (+/horizontal) * +/(horizontal * +/\vertical)

Day 3

oxy =: -:@# <: +/
echo (#.@:-.*#.) oxy in=. "."0 'm' fread 'in/03.txt'
co =: (-:@# > +/)`{.@.(<./=>./)
filter =: {{ y #~ a {~"1 {. I. (#>+/) a=.(="1 u"1&|:) y }}
echo (#. (oxy filter)^:_ in) * (#. (co filter)^:_ in)

Day 4

in=: 'm' fread 'in/04.txt'
draws=: ".;._1 ',' , {. in
boards=: }."_1 (_6 [\ ". }. in)
win=: [: +./ *./"1 , *./
winturns=: >:(|:win"2 boards&e.\ draws) i."1 (1)
score=: {{(+/d-.~,boards{~winturns i.y)*{:d=.y{.draws}}
echo score <./winturns
echo score >./winturns

The same, but written more verbosely:

in=. 'm' fread 'in/04.txt'  NB. Read input file.
]draws =: ".;._1 ',' , {. in      NB. List of drawn numbers.
]boards =: }."_1 (_6 [\ ". }. in) NB. List of bingo boards.

NB. Bingo on marked board y? (T/F)
NB.   y is marked bingo board      (rank 2 bool)
NB.   Returns true or false        (rank 0 bool)
win =: [: +./ *./"1 , *./
NB.  Two forks: (AND each row) OR (AND each col)

NB. The winning turn for each bingo board.
]winturns =: >:(|:win"2 boards&e.\ draws) i."1 (1)
NB. boards&e. draws             NB. Mark each board at the state after all draws.
NB. boards&e.\ draws            NB. Mark each board, for EACH individual draw.
NB. win"2 boards&e.\ draws      NB. For each board and draw, determine if the board has bingo.
NB. >:( ... ) i."1 (1)          NB. Determine the (first) draw each board wins.

NB. Calculates the score for a winning board on turn y.
NB. The score is defined as the sum of unmarked numbers on
NB. the bingo board, multiplied with the number drawn in
NB. winning turn.
NB.   y is a turn number           (rank 0 int)
NB.   Returns the score            (rank 0 int)
score =: monad define
  wb =: boards {~ winturns i. y NB. Get the winning board.
  d=. y {. draws                NB. Get all draws until the winning draw
  (+/ d -.~ ,wb) * {: d         NB. (sum of unmarked) * last draw
  NB.  (d -.~ ,wb) is the set of numbers on the board not contained in d
)

echo score <./winturns          NB. Part 1
echo score >./winturns          NB. Part 2

Day 5

in=. 'm' fread 'in/05.txt'
p2=: ;/ (2,2)$"1 ".> 0 2 5 7 {"1 ;: in
p1=: p2 #~ -.*./"1|*-/"2 > p2
ex=: {{(0{y) +"1 |: (*l) * i."0  (0~:*l)*>:|l=. --/y}}
dp=: {{#~.(-.~:f) # f=. ;ex&.>y}}
echo dp p1
echo dp p2

The same, but written more verbosely:

in=. 'm' fread 'in/05.txt'
paths=: ".> 0 2 5 7 {"1 ;: in     NB. Extract the coordinates.
p2=: ;/ (2,2)$"1 paths            NB. Box all paths.
p1=: p2 #~ -.*./"1|*-/"2 > p2     NB. Remove diagonal paths.

NB. Expand paths y to a list of coordinates.
ex=: monad define
  dir=. --/y                      NB. Vector from (x1,y1) -> (x2,y2),
  idir=. (0 ~: *dir) * (>: | dir) NB. Increment nonzero dirs.
  rsteps=. (*dir) * (i."0 idir)   NB. Relative steps along the path,
  asteps=. (0{y) +"1 |: rsteps    NB. Absolute steps along the path.
)

NB. Count coordinates appearing two or more times.
dp=: monad define
  coords=. ;ex&.>y                NB. Expand each path to coordinates.
  rdup=. (-.~:coords) # coords    NB. Remove unique coordinates.
  cu=. #~.rdup                    NB. Count remaining set.
)

echo dp p1                        NB. Part 1
echo dp p2                        NB. Part 2

Day 6

in=. 'm' fread 'in/06.txt'
f=. +/"1 (i.9) =/ ".;._1 ',' , {. in
adv=. ((6=i.9) * {.) + 1&|. NB. Advance to next day
echo +/f80=.adv^:80 f       NB. Part 1: 80 days
echo +/adv^:(256-80) f80    NB. Part 2: 256 days

Day 7

p=.".;._1 ',' , {. 'm' fread 'in/07.txt'
echo       <./ +/          s=.|p -/ i.>./p
echo <. -: <./ +/ (*>:) M. s

Day 8

First attempt:

echo +/,-.5 6 e.~ #&> _4 {."1 in=. ;:'m' fread 'in/08.txt'

DS=: {{>x{~I.y=#&>x}} NB. Digits with y segments from set x.
I=: {{x{~I.x e. y}}   NB. Set intersection.
decode=: 3 :0"1       NB. Decode a single entry.
  S=. (10{.y)&DS      NB. Digits with y segments from current entry.
  a=. (acf=. {. S 3) -. cf=. {. S 2 
  d=. (adg=. I/S 5) I bcdf=. {. S 4
  b=. bcdf -. d,f,c=. cf -. f=. I/cf, S 6
  e=. ({. S 7) -. a,b,c,d,f,g=. adg -. a,d
  con=. /:~ each (acf,b,e,g);cf;(adg,c,e);(adg,cf);bcdf;(adg,b,f);(adg,b,e,f);acf;(bcdf,a,e,g);(a,bcdf,g)
  10 #., >con&{{I.>((/:~y)&-:) &.> x}} each _4 {.y
)
echo +/decode in

Second attempt, using a hashmap:

echo +/,-.5 6 e.~ #&> _4 {."1 in=. ;:'m' fread 'in/08.txt'
echo +/{{".'8415267903'{~>(10|49|3*[:+/[:,(;10{.y)&="0)&.>_4{.y}}"1 in

Day 9

in=:"."0 'm' fread 'in/09.txt'
echo +/,(+in&*)lp=.in<<./((,-)1 0,.0 1)|.!._  in
lows=:($in) $ (idx=.1+i.#p)  (p=.I.,lp)}(#,in)$0
extend=: {{ y+.(in<9)*+./((,-)1 0,.0 1)|.!.0 y }}
echo */3{.\:~ +/"1,"2 idx="(0 2) extend^:_ lows

Day 10

in=: 'b' fread 'in/10.txt'
reduce=: {{(-.+./(+. |.!.0"1) (4 2$'[](){}<>') E."1 y)#y}}
o=: ( >r=: reduce^:_ each in) i."1 ')]}>' NB. Occurences in reduced.
echo +/(3 57 1197 25137)*+/0<(* (l=:{:$>r)&>"0) (]*]=<./)"1 o
s=: monad define"1 NB. Calculate score for completion of line y.
  {{x + 5*y}}/ +/(>:i.4)*'([{<' ="(0 1) y
)
echo (<.-:#ss){/:~ ss=.s >(I.*./"1 (l=o)) { r

Day 11

t=:f=:0[ in=:"."0 'm' fread 'in/11.txt'
nb=: {{+/(((,-)1 0,.0 1),((,-)1 1,._1 1))|.!.0 y}}
cf=: {{(nb c) + y + __*c [f=:f ++/,c=.y>9}}
s=: {{(]*[:-.__=]) cf^:_ >:y [t=:>:t}}
echo f [[s100=:s^:100               in
echo t [[      s^:([:-.0:=[:+/,)^:_ s100

Day 14

t=:>{.in=: 'b' fread 'in/14.txt'
u=:~.t,,i ['p i'=: |:0 3 {"1 ;: >2}.in NB. unique elements, pairs, insert
pi=: {{ p -:"1 y}} NB. One-Index of given pair y in p
p2p=:(pi"1 (,.{."1 p),"1 i) + (pi"1 (i,"1 ,.{:"1 p)) NB. Transfer function: Pairs -> Pairs
iter=: {{+/p2p * y}} NB. Build next step
p2e=:u e."(1 0) {."1 p NB. One-Index of elements in given pair y
echo (>./-<./)(u e.{:t)++/p2e*"(1 0) i10=:iter^:10 (+/2 pi\ t)
echo (>./-<./)(u e.{:t)++/p2e*"(1 0)      iter^:30 i10