Advent of Golf 2018

I recently launched a small Code golf contest on the Advent of Code 2018 day 20 problem. Contestants had to submit their shortest source code which gives a correct answer, and I received 17 submissions over the four days of the contest.

Golf-specific languages

The only solution in this category, which is also by far the best solution overall, was 70 bytes long submitted by Brian Chen aka betaveros, who is also currently holding the second place on the global Advent of Code 2018 leaderbooard! His solution is in Paradoc, a golfing language that Brian made himself. Worry not, the submission is in a Paradoc version released almost a year ago so there was no way to cheat by customizing the language :)

As I promised, the golf-specific language leaderboard is kept separated from the other submissions. Since the Paradoc solution was the only one in its category, the scoreboard is a bit empty :

Rank Length Contestant Language
1 70 betaveros Paradoc

1. betaveros - 70 bytes (Paradoc)

Since Paradoc (like most golfing languages) uses non-ASCII characters, here is the hexdumped version

0000000: 6930 3a3a 8656 bb05 2228 7c29 2240 5b3a  i0::.V.."(|)"@[:
0000010: 5f29 62b7 7bb8 305c 69ab 957d ab5f 7b96  _)b.{.0\i..}._{.
0000020: 585e 42fa 373d 7c3a 955c 7b29 292b 9b71  X^B.7=|:.\{))+.q
0000030: 5c75 7d7c 585c 7d5d 3d7e 7d3b 5d3a c650  \u}|X\}]=~};]:.P
0000040: 3939 393e 6223                           999>b#

betaveros also provided a commented version of the code :

i .. Set input to read all input at once (instead of line by line or character
  .. by character). This has to be the first character of the program.

.. Here's the strategy, that fails in a million ways on the general problem,
.. but works for my input and for inputs I found online: We assume that all detours
.. with NESW steps after them give a total displacement of 0, and that every
.. NESW step brings us to a new position farther from the origin, EXCEPT steps
.. after we take a step that is exactly the reverse of the last step we took (N
.. and S, or E and W), possibly with a '(' intervening, and before the next '|'.

.. We're going to set up the stack to have a boolean 'inactive' flag, which
.. keeps track of whether we encountered a reverse step; the last NESW char, or
.. some garbage if we're at the start of the input or just saw a '|'; and an array
.. of distances (used like a stack, where the top is the "current distance";
.. we'll call this the "dist-stack"):

0   .. Push 0 onto the stack.
::  .. Duplicate it twice.
†   .. Wrap the top 0 into a length-1 array.

.. So now the stack contains 0 ("inactive" flag), 0 (last NESW char), and [0]
.. (stack of distances).

V   .. Read input.
»   .. Cut off the first character, the ^. We're going to keep the ending $ and
    .. newline, which will probably get treated as NESW steps that don't retrace
    .. anything, which often still works.
ε   .. For each character in the input after removing the ^,
    .. perform the following }-terminated block:
    .. (ε is represented by / mapped to the control character ^E or \x05
    .. in the Paradoc codepage or cp1252)
	"(|)"@ .. Find its index in the string "(|)" (or -1 if not)
	[   .. Start constructing an array of blocks; we'll run one of them:

		.. The '(' case:
		:_   .. :_ pushes the "duplicate top element" function;
		)b   .. ) modifies the rightmost element of an array with the
			 .. underlying function; b binds :_ to ). So this construct a block
			 .. that takes an array and appends its last element to itself.
		·    .. Also, store the above block to the utility Bullet variable
		     .. because this saves a byte later.

		.. The '|' case:
			¸  .. Pop the second element of the stack, the last NESW char.
			0  .. Push 0.
			\i .. Swap it inwards, to be the third element of the stack.
			.. The above three commands replace the inactive flag with 0
			.. and the last NESW char with the previous inactive flag.
			.. We don't care strongly about the last NESW char, we just want it
			.. to not be any of NEWS. This makes it 0 or 1, which we can both
			.. treat as "garbage".
			«  .. Pop the dist-stack (take all but the rightmost element).
			•  .. Run the block we storied in the bullet earlier, appending its
			   .. last element to itself.

		.. The ')' case:
		«_  .. Pop the dist-stack (take all but the rightmost element). Easy.

		.. The NESW case, by far the most involved.
			–  .. Pop and store the dist-stack into the utility Bullet variable.
			X  .. Push the loop variable: the current character of the input.
			^  .. XOR it with the top element of the stack, the last NESW char.
			Bú .. Mod 11 (because B is 11 in base 36)...
			7= .. and test if it's equal to 7.
			.. Through trial and error, the above predicate was found to be
			.. true iff the two characters were opposite directions: NS or WE
			.. in some order.

			|  .. OR the test result with the top element of the stack, the
			   .. inactive flag. This is the updated inactive flag.
			:  .. Duplicate the inactive flag.
			•  .. Push the bullet variable, which was the dist-stack.
			\  .. Swap it under the inactive flag.
			{  .. (This block will be executed if inactive is false:)
				)  .. Uncons the dist-stack, leaving all-but-last and last.
				)  .. Increment that last element.
				+  .. Concatenate it back onto the stack.
				›q .. Take the last element of the dist-stack, but don't pop
				   .. the dist-stack, and in fact put the resulting last
				   .. element under the dist-stack.
				\u .. Swap under the top of the stack, leaving that last
				   .. element under the inactive flag and the new dist-stack.
			}| .. Run the above block if the inactive flag is false.
			X .. Push the loop variable, the current character of the input.
			\ .. Swap it under the dist-stack.
	] .. This completes the list of blocks.
	= .. Index into it by the index of the current char in "(|)" (or -1 if not
	  .. found).
	~ .. Execute the block.
} .. End of for each block.
; .. Pop the dist-stack.

.. Here we ignore the inactive flag and the last NESW char, again at our peril,
.. assuming that neither will be larger than the true maximum distance from the
.. origin, and so won't affect our level 1 answer. (It's definitely true that
.. neither will be above 1000, so they won't affect our level 2 answer.)

]  .. Collect everything we left on the stack into a list. This is
   .. approximately the list of distances from the origin of every room we
   .. visited, with every single caveat mentioned above.
:Æ .. Duplicate and take the maximum.
P  .. Print that: this is the level 1 answer.
999>b .. Bind 999 to the greater-than comparison.
#  .. Then count how many elements of the list of distances satisfy this
   .. predicate: this is the level 2 answer, and is implicitly printed since
   .. it's left on the stack.

General languages

The other 16 submissions are in non-golf languages, including one non-official solution taken from Reddit comments.

Rank Length Contestant Language
1 169 Lucy Bunny C
2 171 Peter Tseng Ruby
3 178 Betaveros Python 3
3 178 Alex Cornellier Ruby
5 187 Anton Älgmyr Python 3
(6) 184+ Reddit Python 3
6 195 Cameron Aavik Python 3
7 288 kagidab JavaScript
8 298 Ruud de Rooij JavaScript
9 416 u/whosoup PHP
10 417 KeyJ Python 2
11 517 Aaron Diers Ruby
12 558 Tael Aeril C#
13 570 Janhonho Prolog
14 969 Royw Python 3
15 986 Waffle3z Lua

1. Lucy Bunny - 169 bytes (C)

The first place surprisingly goes to a C submission, which is known to be a particularly verbose language. Congratulations to Lucy Bunny for beating everyone else despite the difficulty of the language!


2. Peter Tseng - 171 bytes (Ruby)

Second place is taken by Peter Tseng, which is the only documented case in the world where Ruby is better than Python.

D={a=b=0=>0};K=->x{p,d=x;m=->n{(d=D[p+=n]||=(d>998&&b+=1;d+1))>a&&a=d};loop{(c=$<.getc)==?(?K[[p,d]]:c==?|?(p,d=x):(v=c&&'ESWN'.index(c))?m[1i**v]:break}};K[0];K[*D];p a,b

Here are a few tricks shared by Peter :

  • Assignments within assignments (See that D={a=b=0=>0} part, or things like d=D[p+=n]||=...)
  • Using ->args{body} lambda instead of def to define function
  • Using short-circuiting boolean operators as control flow. do_something if b should instead be b&&do_something
  • ?x for single-character string, not ‘x’
  • Coordinates are on the complex plane. To move, index into ESWN and take i to the power of that.
  • For the longest time, I was vexed on how to save characters for removing the ^ at start of regex. Originally it was R=$<.read.chars[1..-1], so long! Next was _,*R=$<.read.chars which was a start. But $<.getc is available. So, try $<.getc once at program start, then K can also call $<.getc to get individual characters. But that extra call to $<.getc at start takes up characters. But look, if we call K and the first character is ^, the function returns immediately! So let’s just do that. We need to call K with any arg so arbitrarily pick 0. Then call it with [0, 0] which is what we actually want, which we can get by doing *D (because D is {0 => 0} and splatting the hash turns it into an array of its kv pairs)

3 (ex aequo). betaveros - 178 bytes (Python 3)

Back at it again with a winning submission, betaveros takes the Python trophy home !

for c in input()[1:]:exec(('s=*s,d','a=0;*_,d=s;P=c','*s,d=s','a|=P+c in"NSN WEW";exec("d+=1;x=max(x,d);y+=d>999"*-~-a);P=c')['(|)'.find(c)])

3 (ex aequo). Alex Cornellier - 178 bytes (Ruby)

With a last minute Ruby submission, Alex shares a spot on the podium!

$_[1..-2]{|c|eval'q<<x x=q.pop *q,x=q o=x;x+=1i**"ESWN".index(c);d[x]=[d[x]||1e9,d[o]+1].min'.split['()|'.index(c)||3]}
p d.values.max,d.count{|_,f|f>999}

5. Anton Älgmyr - 187 bytes (Python 3)

for c in input():exec("*B,_=B#B=*B,s#*_,s=B#s=[s[:-1],s+c][s[-1:]!='SNEW'[ord(c)//5%5]];S|={s*(len(s)>1e3)}"[14-'|()'.find(c)*7:])

Anton was kind enough to explain this solution :

This uses a stack to keep track of the path taken, not much to say about that. What differs is me storing paths as strings. Backtracking is done akin to Day 5 with elimination in a string, N eliminates S and W eliminates E (and vice versa). The elimination code was my biggest nemesis here, it was initially a huge part of the code but ended up shrinking a lot over time ('SNEW'[ord(c)//5%5] was a fun thing to devise).

The reduced strings at every step are added to a set iff they are longer than 1000 characters (otherwise an empty string is added). The 1000 and not 999 is due to ^ being part of the string.

When the input string has been consumed, the answer will be the maximum of the set (minus 1, because of the ^) and the size of the set (minus 1, because of the empty string).

6 (unranked). Reddit - 184+ bytes (Python 3)

This suggestion was taken from a Reddit thread, where multiple contributors improved on an initial solution. The successive contributors are listed below, several of them have entered the contest on their own.

And the final 184 byte code is :

for c in r[1:-1]:exec('s+=p,##*s,p=s#*_,p=s#l=p;p+=1j**"ESWN".find(c);d[p]=min(d.get(p,1e9),d[l]+1)'['()|'.find(c)%4*7:])
print(max(v),sum(x>999for x in v))

This is not counted as a submission, since the code does not respect I/O formatting. I just wanted to highlight a beautiful collaboration :)

6. Cameron Aavik - 195 bytes (Python 3)

for t in input()[1:-1]:exec(q[ord(t)%9%4])
print(sum(d>999for d in v))

7. kagidab - 288 bytes (JavaScript)

e=t=>{for(o=[u=t],M=(a,z)=>a.push(z)&&z;m=q[x=-~x];u=h>2?>M(O[c]=O[c]||[],h%2?c+h*l-4*l:c+h-5)):h>1?e(u):M(o,t))if(!(h=")|(NESW".indexOf(m)))return u}
for(X of Q)O[X]&&O[X].map(P=>v[P]=v[P]||M(Q,P)&&(v[X]>l?++c:1)&&-~v[X])

8. Ruud de Rooij - 298 bytes (JavaScript)


9. u/whosoup - 416 bytes (PHP)

<?php $s=[];foreach(str_split(fgets(STDIN))as$i){@$p=$m["$x,$y"];@eval(['('=>'array_unshift($s,[$x,$y]);',')'=>'[$x,$y]=array_shift($s);','|'=>'[$x,$y]=$s[0];','N'=>'list($x,$y)=[N=>[$x,$y+1],S=>[$x,$y-1],E=>[$x+1,$y],W=>[$x-1,$y]][$i];@$q=$m["$x,$y"];$m["$x,$y"]=(!$q||$q>$p)?$p+1:$q;'][preg_replace('#[EWS]#','N',$i)]);}$l=array_values($m);echo max(...$l)."

10. KeyJ - 417 bytes (Python 2)

for c in open("a").read()[1:-2]:
 if c=='|':e|=p;p=S(s)
 elif c=='(':q+=[(s,e)];s,e=S(p),S()
 elif c==')':p|=e;s,e=q.pop()
 else:o=N[c];D|={x+o for x in p};p={x+2*o for x in p}
while q[d]:
 for x in q[d-1]:a.add(x);[q[d].add(x+2*o)for o in N.values()if x+o in D]
print d-1
print sum(len(z)for z in q[1000:])

11. Aaron Diers - 517 bytes (Ruby)

require'set';a,b,c,d,e,f,g,,[[0,0]],1,{},0,Set[],Set["0,0"],0;def a a,b,c;a[b]=Set[]if !a[b];a[b].add(c)end;while c<a.length-1;case a[c]when"(";b<<b[-1].dup;when"|";b.pop;b<<b[-1].dup;when")";b[-1]=b.pop;else;i="#{b[-1][0]},#{b[-1][1]}";case a[c]when"N";b[-1][1]-=1when"S";b[-1][1]+=1when"W";b[-1][0]-=1else;b[-1][0]+=1end;j="#{b[-1][0]},#{b[-1][1]}";a d,i,j;a d,j,i;end;c+=1end;loop{i=Set[];g.each{|j|f<<j;d[j].each{|k|i<<k if !f.member? k}};break if i.size==0;e+=1;h+=i.size if e>=1000;g=i};puts e;puts h

12. Tael Aeril - 558 bytes (C#)

This was the first submission to the contest, 9 hours after the problem was published.

using System;using System.Collections.Generic;using System.IO;using System.Linq;class M{static void Main(){var A=File.ReadAllLines("i")[0];var B=new P('0',0);var C=new List<P>();var D=new Dictionary<int, P>();var E=0;for (var i=0;++i<A.Length;){var c=A[i];if(B.O(c))while(c<99)c=A[++i];if("ENWS".Contains(c))C.Add(B=new P(c,B.G+1));if(c<41)D[E++]=B;if(c>99)B=D[E-1];if(c==41)B=D[--E];}Console.Write(C.Max(n=>n.G)+"\n"+C.Count(n=>n.G>999));}class P{public int F,G;public P(int f,int g){F=f;G=g;}public bool O(int f){var x=Math.Abs(F-f);return x== 18||x==5;}}}

13. Janhonho - 570 bytes (Prolog)

:-dynamic p/2,d/2.
m(P,D):-(P=[];E is D+1,findall(Y,(member(X,P),p(X,Y),\+d(Y,_),assert(d(X,E))),Q),m(Q,E)).
g(D,X,Y):-Y is X+D,(p(X,Y);assert(p(X,Y)),assert(p(Y,X))).
i(87,999). i(69,-999). i(83,-1). i(78,1).

14. Royw - 961 bytes (Python 3)

exec('''from collections import*
from heapq import*
def M(i,j,s,g):
def Q(t):
def I(i,j,t,g):
 if L(s)==0:{3}S([M(i,j,t,g)])
 {2}s:w,=S.union(*[I(*k,_,g)for _ in Q(t[a+1:]){0}[{4}a],g){0}w]]),
def d(f,t):
 while q:
{5}c not in n:
  {5}not n&and o+1<m.get(k,1e99):m[k]=o+1;heappush(q,(o+1,k,p))
l=[d((0,0),k)[0]{0}S(t[1]for t in e)]
print(sum(k>=1e3 {0}l))'''.format("for k in ","  p+=k=='(';p-=k==')'","for a, in ","return ","M(*k,t[+1:","  if "))

15. Waffle3z - 986 bytes (Lua)

M,T,a,b,v,r={},setmetatable,0,0,{}M.__index=function(t,k)t[k]=T({},M)return t[k]end r=T({},M)function _(y,x,c)return y+({N=1,S=-1,E=0,W=0})[c],x+({N=0,S=0,E=1,W=-1})[c]end function m(s,y,x,c)s:gsub(".",function(c)r[y][x][c],y,x=1,_(y,x,c)end)return y,x end function P(s,y,x) local p,g,A,S,s,B,h,c=0,{},2,s:match("^(%w*)(.*)")y,x=m(S,y,x)if #s==0 then return end for i=1,#s do c=s:sub(i,i)p=p+(c=="("and 1 or c==")"and-1 or 0)if c=="|"and p==1 then g[#g+1]=s:sub(A,i-1)A=i+1 end if p==0 then B=i break end end g[#g+1]=s:sub(A,B-1)for i=1,#g do if#g[i]==0 then h=1 end end for i=1,#g do local a,b=g[i],s:sub(B+1)if h and#a~=0 then local Y,X=m(a,y,x)if Y~=y or X~=x then P(a..b,y,x)else P(a,y,x)end else P(a..b,y,x)end end end P("i.txt","r"):read"*a":sub(2,-2),0,0)function f(y,x,d)if v[r[y][x]]then return end if d>=1000 then b=b+1 end v[r[y][x]]=1 a=d>a and d or a for c in next,r[y][x]do f(y+({N=1,S=-1,E=0,W=0})[c],x+({N=0,S=0,E=1,W=-1})[c],d+1)end end f(0,0,0)print(a)print(b)

Congratulations to all participants, each submission had some unique tricks and was very instructive to read !

Written on December 24, 2018