Let’s continue the analysis of Advent Of Code 2018!
Some string manipulation entering the scene, and more data structures we will need in the future!
Day 3 - Finally some 2D action!
Part 1 - Overlapping rectangles
This time our input is a series of rectangles on a 2D grid, specified with their top-left corner and their width and size, in the following format:
#1 @ 1,3: 4x4
#2 @ 3,1: 4x4
#3 @ 5,5: 2x2
We can visualize them like this on a 0-index grid:
........
...2222.
...2222.
.11XX22.
.11XX22.
.111133.
.111133.
........
Where cells marked with X are those belonging to two or more rectangles. The output of our program should be the amount of such cells.
My solution is, as usual, on my Github repository, and most of its lines of code deal with input parsing, so I’ll focus here on a few lines:
std::map<coords,int> m;
As I said in last Thursday’s post, I make heavy use of std::map throughout all the challenges, and it this cases m will hold, for every cell, the number of rectangle that occupy that cell.
This makes everything easy; once we have the coordinates (i,j) of the top-left corner, the height a and the width b, we can easily fill the map m like this:
for (int k=0; k<a; ++k)
for (int l=0; l<b; ++l)
m[coords(i+k,j+l)]++;
Then, the way I extracted the solution in my original solve was like this:
int overlap = 0;
for (auto const & [key,val] : m)
{
if (val>1)
overlap++;
}
std::cout << overlap << std::endl;
But, we can all clearly see that there is a much nicer way to do that, right?
And it looks a bit like this:
std::cout << std::count_if(m.begin(),m.end(),[]( const std::pair<coords,int>& pair)
{
return pair.second>1;
}) << std::endl;
With a single line of code, using built-in features such as std::count_if , and a very simple lamdba expression, we removed the need for the overlap variable and we got rid of an ugly manually written for-loop.
Part 2 - The only non-overlapping rectangle!
After finding out everywhere rectangles overlap, we have the opposite task: find out the only rectangle that does not overlap with any of the others.
The way I’ve done it makes use, once again, of a std::map , which I called claim, that stores every index of every rectangle that overlaps with another one.
As before, for the rectangle number index, with coordinates (i,j), heighta and width b, this time we fill the values as it follows:
for (int k=0; k<a; ++k)
for (int l=0; l<b; ++l)
if(m.find(coords(i+k,j+l))==m.end())
m[coords(i+k,j+l)]=(index);
else
claims[index]=claims[m[coords(i+k,j+l)]]=true;
What we basically do now is just checking whether there was already a rectangle in a specific cell (the call to std::map::find): if there was not, we just mark that now one exists; otherwise, we mark that both the rectangle index and the one found inside the map, overlap.
At the end, everything we need to do to find out the only non-overlapping rectangle, is the following:
for (int i=1; i<index; ++i) /* Index is the number of rectangles */
if (claims.find(i)==claims.end())
cout << i << endl;
You could probably see that here, too, something could have done better.
Particularly, there is no need to use a map for claims, since we do not actually need to map each rectangle to a value (which, indeed, is always true). Instead, we should have just used a std::set. I won’t post a fixed version of this code here, but it takes just a few changes to implement it.
Day 4 - It’s time to move!
Part 1 - Sleeping guard
A bit of lore around this: you are trying to sneak past a bunch of guards. Luckily, this guards are not really good at their job and they fall asleep often. The timetable of when they begintheir shift and fall asleep looks like this:
[1518-11-01 00:00] Guard #10 begins shift
[1518-11-01 00:05] falls asleep
[1518-11-01 00:25] wakes up
[1518-11-01 00:30] falls asleep
[1518-11-01 00:55] wakes up
[1518-11-01 23:58] Guard #99 begins shift
[1518-11-02 00:40] falls asleep
[1518-11-02 00:50] wakes up
[1518-11-03 00:05] Guard #10 begins shift
[1518-11-03 00:24] falls asleep
[1518-11-03 00:29] wakes up
[1518-11-04 00:02] Guard #99 begins shift
[1518-11-04 00:36] falls asleep
[1518-11-04 00:46] wakes up
[1518-11-05 00:03] Guard #99 begins shift
[1518-11-05 00:45] falls asleep
[1518-11-05 00:55] wakes up
Extracted from the original statement of the problem:
The guard falling asleep or waking up is always the one whose shift most recently started. Because all asleep/awake times are during the midnight hour (00:00 - 00:59), only the minute portion (00 - 59) is relevant for those events.
Which means we can represent when they are asleep (#) and when they are awake (.) as follows:
Date ID Minute
000000000011111111112222222222333333333344444444445555555555
012345678901234567890123456789012345678901234567890123456789
11-01 #10 .....####################.....#########################.....
11-02 #99 ........................................##########..........
11-03 #10 ........................#####...............................
11-04 #99 ....................................##########..............
11-05 #99 .............................................##########.....
Our goal is to find the guards that spends most time asleep (in our case #10) and output in which minute he is asleep the most (in this case, 24) and then output the product of the two numbers.
Let’s go and find out how I solved it: as usual, most of the code is for splitting the input strings (not an easy task in plain C++), so let’s focus on the important tasks:
minutes=stoi(s.substr(s.find(":")+1,2));
event=s.substr(s.find(":")+5,s.find("#")-s.find(":")-5);
Here we extract the time of the action and the type of event (in our case, it can either by Guard , falls asleep or wakes up); in case the event is Guard , we also extracts its ID. Since the guard falling asleep/waking up is always the one whose shift most recently started, we just need to keep track of the last guard we encounter.
If the event is falls asleep, we mark at which minute this happened:
last_asleep=minutes;
If it is wakes up, we store in a map<int, int> the total amount of minute spent asleep:
ts[curGuard]+=(minutes-last_asleep);
this will make possible to determine which guard slept the most; then we increment in a map<int,vector<int>> which minutes inside the hour (represented by a vector<int>(60)) he spent asleep:
for (int i=last_asleep; i<minutes; ++i) /* For every minute spent asleep */
{
if (ms.find(curGuard)==ms.end()) /* Initialize the vector with 60 entries at 0 */
ms[curGuard]=std::vector<int> (60,0);
ms[curGuard][i]+=1; /* Increment the time slept on that minute */
}
What is missing is finding out which guard slept the most and in which minute it was asleep most of time. You can look at the original solution but here I want to show a better version of it:
auto max_slept = (std::max_element(ts.begin(),ts.end(),[](const std::pair<int,int> & p1,const std::pair<int,int> & p2){ return p1.second<p2.second;}))->first;
std::cout << max_slept*(-std::distance(max_element(ms[max_slept].begin(), ms[max_slept].end()),ms[max_slept].begin())) << std::endl;
Instead of the 12 lines of code of the original solution, here we can use just two lines to solve it!
In the first one, we just extract from the map<int,int> ts the pair with the maximum value (the guard which slept the most) and then just the first element of it (the ID# of the guard), while in the second one we extract the max_element from the vector of its minutes asleep and then use std::distance to get its index.
Part 2 - Who sleeps most frequently at the same minute?
In our case, we can see that Guard #99 spent minute 45 asleep for three times, while all other guards were asleep in any minute at most twice.
Our output should be the guard ID multiplied by the chosen minute (in the example, that would be 99 * 45 = 4455).
Most of the solve is the same as before, but in this case we added a simple for-loop to extract the needed information (I changed two lines from the code you see on GitHub to avoid recomputing the same value twice):
/* All this variables, when valid, are positive integer,
so initializing them to -1 is safe */
int most_asleep_guard=-1;
int most_asleep_min=-1;
int most_asleep_freq=-1;
/* Loop through all the entries in the map */
for( auto const& [key, val] : ms )
{
/* Find the minute in which this guard has slept the most */
auto timesAsleepIterator = max_element(val.begin(), val.end());
int his_minute=(-std::distance(timesAsleepIterator,val.begin()));
/* How many times was he asleep at this minute */
int times_asleep=*(timesAsleepIterator);
/* If it is a new maximum, save it */
if (times_asleep>most_asleep_freq)
{
most_asleep_guard=key;
most_asleep_freq=times_asleep;
most_asleep_min=his_minute;
}
}
cout << most_asleep_guard* most_asleep_min << "\n";
That’s all for today!
Thanks for following me down this trip on memory lane and be prepared, the most interesting challenges are yet to come! As usual, feel free to comment, I’d like to have some feedback!
