Advent of Code 2016

For the impatient: jump to versions of my code:

final version
second version
first version

So, I was introduced to this website called “Advent of Code” http://adventofcode.com just the other day, it’s pretty cool. The purpose of the website is to solve two programming puzzles each day ’til christmas. My programming language of choice is Matlab and it seems to suite well with the problems I’ve seen so far.

Note: The versions are stacked, so the latest version is on top, with comments, then the previous etc.

Day 1: No Time for a Taxicab

http://adventofcode.com/2016/day/1


Version 2 (inlined) (10/12)

This version is an inlined version of the previous version (second versionm see below). I like that it is short, but it is kind of difficult to follow at times, but here it is. The code calculates the distance from the first point to the last (calculation is made in one row of code) the intersection is tricky, because of the vectorized code and thus takes two rows to accomplish.

dRel      = textscan(fopen('input-Day-1.txt'), '%c%d', 'Delimiter', ',');
coords    = cumsum( exp(1i*(repelem(cumsum( 2*(dRel{1} == 'L') - 1 ), dRel{2}))*pi*.5) );
[vS, vI]  = sort(coords);
intsctn   = min( vI(~[abs(diff(vS)); 0]) );

fprintf(1,'Distance from first to last coordinate: %d\n', real(coords(end)) + imag(coords(end)) )
fprintf(1,'Distance to first intersection: %d\n', real(coords(intsctn)) + imag(coords(intsctn)) ) 

In total: 6 rows

I realised that I could inline a bunch of things such as rot, angles, C2R and the file handle, they are only used once.


Version 2 (10/12)

The biggest change between the versions was the realisation that I could use a complex numbers \(x+iy\) to represent a 2d coordinate, instead of using [x,y]. This makes some steps redundant so I can get to the answer quicker. Also, I can use diff on complex numbers to find the intersection point, which is nice. I also made rotation shorter by using the Euler formula

\(e^{i\theta} = \cos \theta + i \sin \theta\).

which simply is a direction in the complex plane.

fd        = fopen('input-Day-1.txt', 'r');
dRel      = textscan(fd, '%c%d', 'Delimiter', ',');
rot       = @(rad)   exp(1i*rad*pi*0.5);
C2R       = @(coord) real(coord) + imag(coord);
angles    = 2*(dRel{1} == 'L') - 1;
tmp       = repelem(cumsum(angles), dRel{2});
coords    = cumsum( rot(tmp) );
[vS, vI]  = sort(coords);
intsctn   = min(vI(~[abs(diff(vS)); 0]));

fprintf(1,'Distance from first to last coordinate: %d\n', C2R(coords(end)))
fprintf(1,'Distance to first intersection: %d\n', C2R(coords(intsctn)))

In total: 11 rows


I made a few changes from the first version (see below):
1. Closing the file handle is not necessary
2. Using the variable dRel and not storing extra variables, makes the code more obfuscated but that could be remedied by comments
3. Using complex numbers instead of 2-vectors made the code much more concise because I don’t need the two conversion function
4. Added a convert from complex to coordinates (only used for output, I could have inlined it)
5. Using Euler formula for rotating the direction

First version (8/12)

%scan file and put into cell 'dirs'
fd = fopen('input-Day-1.txt', 'r');
dirs = textscan(fd, '%c%d', 'Delimiter', ',');
fclose(fd);

scale       = 10000;
% anon functions for conversion and rotation of vectors
co2map      = @(co) double( co(:,1)*scale + co(:,2) );
map2co      = @(map) [fix(map/scale), map-scale*fix(map/scale)];
rot         = @(dir, rad) [dir(1)*cos(rad)-dir(2)*sin(rad),...
               dir(1)*sin(rad)+dir(2)*cos(rad)];

rotRel      = dirs{1};
stepsRel    = double(dirs{2});
startDir    = [1,0];

angles      = ( 2*(rotRel == 'L') - 1 )*pi*0.5;
tmp         = repelem( cumsum(angles), stepsRel );
rotAbs      = fix( rot(startDir, tmp) );
coords      = cumsum(rotAbs);

[vecS, vecI]= sort(co2map(coords));
differ      = diff(vecS);
intsctn     = min(vecI(~[differ; 0]));

fprintf(1,'Distance from first to last coordinate: %d\n', sum(coords(end, :)))
fprintf(1,'Distance to first intersection: %d\n', sum(coords(intsctn, :)))

In total: 19 rows (excluding comments)
Ok, so I should probably explain what I’m doing here. The first functions are used to switch coordinate systems from 2d to indices. I did this because I had to solve the second question for day 1, which forced me to step (instead of jumping between instructions). So I had a solution in mind already and by using diff on the sorted vector, I can find the indices of the coordinates that had been travelled to twice. In order to do that I needed a way to jump between coordinates to numbers, a way to do that was to use a scaling constant to map the coordinates to a number.

The rotation function is simply the rotation matrix multiplied by a point. I get the rotations angles by

angles      = (2*(rotRel == 'L')-1)*pi*0.5; 

By taking the relative rotation rotRel and comparing it to ‘L’ we get a binary vector, which I flip and element wise multiply by pi/2 to get the relative rotations for each point on my travel. To get the absolute position, we need the cumulative sum of the rotations and I also use repelem, which was actually new to me. The function expands the absolute angle vector, using a given number of repetitions, which we already have.

By using cumsum for rotAbs, we get the absolute coordinates where we have travelled. In my first solution I didn’t use this, I simply jumped between the instructions, I didn’t need the intermediary points, but for the second question I had to.

For the last part I simply pick out the diff, as I mentioned in the beginning. The hard part was to realize how to do the second solution when my mind was fixed on my first solution. I had to use repelem instead and defer the rotation calculation because I needed a n-by-1 vector.

Anyway, fun exercise.

Leave a Reply

Your email address will not be published. Required fields are marked *