mitja

mitja

Day 11 seemed almost too easy to do :slight_smile: I cheated a bit and the code works only for the supplied input since I saw that there are a lot more north moves. It would be easy to make it work for the general case though.

0
Post #31
sasajuric

sasajuric

Author of Elixir In Action

That code doesn’t work for my input, and I’m not quite sure how would you generalize it, since you completely ignore se/nw movements. I’d be curious to see the generalized solution.

I never worked with hex grids before, so after some pondering, I concluded it’s better to search for the algorithm :slight_smile: I was able to find an excellent site here, with distances explained here. My solution based on that is available here.

1
Post #32
NobbZ

NobbZ

Thanks for the link @sasajuric! The provided information about using “cube coordinates” on a hex grid helped me a lot.

I think I was able to use the informations to build my solution in a robust way which works with any input:

1
Post #33
mitja

mitja

@sasajuric Does everyone get a different input? I didn’t know that :grin:

I’ll take some time and make a general solution in the afternoon. The gist of it is this:

  1. The order of the moves does not matter. n,n,n,s,s,s is identical to n,s,n,s,n,s. This holds even if you have other moves. So the order of the moves does not matter, just the number of moves in particular directions.
  2. You can always change n and s moves to only n or only s moves. For example n,s,n,s,n is identical to n. So you just subtract the number of both to get how many moves you make. This is why I have this line.
  3. You can always change ne and sw moves to only ne or only sw moves. For example ne,sw,ne sw,ne is identical to ne. Again, you just subtract the number of occurrences of the two. This is why I have this line.
  4. Just as in 3. you can do the same for nw and se. I’m not using this at all, but this is particular for my input. You would need to handle this as well. Why I’m not using this is explained below.

With the above rules you are only left with 3 moves. For my input these three were n, nw, ne. In general it could be any combination.

But you can also cancel out nw and ne like this:

  1. ne,nw,ne,nw,ne is identical to n,n,ne. As you can see the total number of moves in the shortened case is exactly the same as the number of ne moves. In general the number of moves is equal to the max of the number of occurrences.
  2. You can do something similar for all the possible combination of the three moves that you are left with. My input is easy because everything we north, but you can do the same for other directions. For example:
    sw,nw,sw,nw,sw is identical to w,w,sw.
  3. You are now left with just moves that you cannot shorten and you can just sum them up, since there are in someway orthogonal to each other. This is why I have this line.

PS: Can you send me your input, it’ll help me write the general solution

2
Post #34
NobbZ

NobbZ

As far as I know, everyone gets different input from a set of possible inputs, as the input given needs to be validated to be solveable without any ambiguity.

For some days this set is larger, for others it is smaller, for some days it may even be complete random data for everyone, because its easily verifiable.

Mine is available in my repo.

0
Post #35
sasajuric

sasajuric

Author of Elixir In Action

You can get my input here.

I started out with the same idea as you described (which is IMO significantly more involved than the code you linked, where you merely cancel out n/s ne/sw pairs), and I do feel that this might lead to the solution. However, while thinking about the problem, my thought was that this will end up being somwhat complicated, since we have to do iterative substitutions, since once you blend two instructions, you need to recheck the blended instructions against all the other ones (even the previously checked ones). I do feel that this should converge into the outcome with minimal steps, but it felt like too much work. Perhaps it was too early in the morning for me to properly think it through :slight_smile:.

So instead, I did some research and found the linked article. I find the approach in that article quite elegant, as we need to pass through the input once, keeping only the current position as the state, and we don’t need to do any post-processing. Based on that property, I was able to build a purely streaming, forward-only solution with constant memory usage :slight_smile:

2
Post #36
petecorey

petecorey

I did the same for day 10. The restriction that each length can never surpass the length of your loop meant that we could pretty easily implement the knot algorithms with some well placed splits, reverses, and concatenations.

I kludged my way through day 11. I didn’t realize you could do Manhattan distance on hexagonal grids, so I retraced the shortest path to the final destination and counted its length. TIL.

0
Post #37
mitja

mitja

I made a generalized version of my Day 11 solution. You can find it here.

0
Post #38
NobbZ

NobbZ

Yeah! Today is day 12, and again the exercise felt relatively simple.

No new things to learn, just using a map as unidirectional graph (the text promised that each side of the pipe will report it in the input!).

For the first part I simply started at pid 0, did a depth first search and inserting all childs of the current node to a set, removing the current node and then continuing the search. I cancelled depth search when a given link pointed to a node that was already removed and continued searching in breadth then. At the end I counted the elements in the resulting set.

The second part used that way as well, but ignorig the set, only using the updated map in each iteration until it was empty. Each iteration incremented a counter by 1. I used Enum.at/2 to actually get a pid to start the search from.

Solution | Input

0
Post #39
NobbZ

NobbZ

And day 13 is solved as well.

Part 1 was is straight forward. Walk down the list, accumulate the severity, and do not forget to update the list when on an empty field :wink:

Part 2 is easy as well, I thought… Well, in fact the theory is easy: generate a stream of all possible firewall configurations, attach the delay that fits this config, reject those where we were caught on the first field, and then find one where we have a severity of 0 with the walker from part 1.

This would probably work, but didn’t get me any result after about 10 minutes (went downstairs with co-workers and we talked while they were having a cigarette). So I cancelled the run and added a second walker, which does not keep book about severity but cancels as soon as it is caught and returns false then, true if it reaches the end. I used that to filter the stream of all firewalls, took the first one and returned its delay.

PS: my current solution to part 2 does still take 25 to 30 seconds on my office VM with MIX_ENV=prod. My laptop at home running the code natively and on a current OTP (20 vs 19) is doing it in 20 to 25 seconds.

NB: Office host has an i5-6600K @ 3.50GHz, laptop at home an i5-4210M @ 2.60, I’m wondering if OTP version or running native has a bigger impact on those times…

Solution | Input

0
Post #40