What was the one liner? I'm fairly sure I can see how to do it but it is probably somewhat obfuscated.
4b is still running. Maybe I was unlucky.
That's not really a one-liner. It's about as much as I wrote in Python.What was the one liner? I'm fairly sure I can see how to do it but it is probably somewhat obfuscated.
https://www.reddit.com/r/adventofcode/comments/3v8roh/day_3_solutions/cxmc1h2
4b is nasty. It is taking a while to bruteforce.Do you know for a fact that bruteforce is the only way?
It appears day 3 can be solved by munging a 2D space into a 1D one using prime numbers :)
https://github.com/bjtaylor1/AdventOfCode/blob/master/Day3.ps1
It appears day 3 can be solved by munging a 2D space into a 1D one using prime numbers :)
https://github.com/bjtaylor1/AdventOfCode/blob/master/Day3.ps1(click to show/hide)
Quick - recommend me a programming language (and tools) that an old duffer can use!
A few years back (on another computer) I think I installed python (IIRC - could have been something else) and actually managed to get it to interact with Openstreetmap to draw a map with a particular bus route. IIRC, it was surprisingly easy.
Firstly, a really stupid question - how can I tell if I've already got python installed (Ubuntu is the operating sys and I've found "Terminal" gives me a Ye Olde terminal)?
VMT
user@cinelli ~ $ python -V
Python 2.7.6
(click to show/hide)
I like the fact that the second part of each day is not revealed until submitting an answer to the first. That way we are encouraged to think about solutions that might be a little more generalisable.Rule of agile: do as little work as possible. ;)
However for Day 3...(click to show/hide)
(click to show/hide)(click to show/hide)
Well, I haven't even figured out how to bring a file in a character at a time yet!http://code.activestate.com/recipes/65118-processing-a-string-one-character-at-a-time/
Still trying to work out how to do arrays.In perl? Clues to a solution included.
4b is still running. Maybe I was unlucky.
Still crunching away with this too. It's only using 15% CPU .. I'm wondering if a parallel foreach might have been better...
4b is still running. Maybe I was unlucky.
Still crunching away with this too. It's only using 15% CPU .. I'm wondering if a parallel foreach might have been better...
Day 4 (MD5)(click to show/hide)
Day 4 done. It helps when you search for the correct string. "000000" has six characters :facepalm:You and me both..
The code seems to run for me (once the filename is changed) and seems to give a credible answer. It is going round the houses a long way, looping through the data twice.
Day 4 done. It helps when you search for the correct string. "000000" has six characters :facepalm:You and me both..
Day 4 done. It helps when you search for the correct string. "000000" has six characters :facepalm:You and me both..
+1 .. :/
Just catching up. Day 5 with some regular expressions.
A bit of regex solves anything :)(click to show/hide)
I've set up a 'private leaderboard' for YACF if anyone wishes to join it. The access code is 48462-ea506236
Days 1 - 3 solved using spreadsheets.Tht sounds like masochism. Just becasue you can, doesn't mean you should. You may find Day 4 a bit hard to do on a spreadsheet.
It's not efficient and the computer struggles to run the spreadsheets.
Not necessary for completing the task, but as I like drawing pictures this is the pattern of lights for my version of Day 6 part b:
(http://staff.city.ac.uk/~jwo/acf/adventLights.jpg)
(click to show/hide)
I must be missing something obvious in 6a. It doesn't look that difficult, but I'm not getting the right answer. My code seems to work for small data sets, but fails for the full problem set.Off by one error somewhere?
I must be missing something obvious in 6a. It doesn't look that difficult, but I'm not getting the right answer. My code seems to work for small data sets, but fails for the full problem set.Off by one error somewhere?
Waiting for 10b to finish running.
Pingu, with your light instructions, I get 400410 left on.
(http://staff.city.ac.uk/~jwo/acf/adventLights2Pingu.jpg)
(which clearly shows an image of Jesus imprinted on it, so you must have a very special set of instructions)
Python on an aging mac. It took a little while, probably my fault for writing stupidly inefficient code. (Couple of minutes? - didn't matter as I was half way through a rather tedious exam invigilation).Waiting for 10b to finish running.(click to show/hide)
It was thanks for trying my data with your solution :)
I have found the reason why my code didn't work. It was because it extracted strings rather than numbers for the coordinates from the instructions :facepalm: One day I will learn ::-)
6a completed.
I've skipped day 7* and done day 8.
*Javascript does the bitwise operations on 32-bit.
Did you write code for 11? I started to think about how I would code it but had solved it by inspection before I worked out how I would code it.
class TestIt(unittest.TestCase):
# Part 1 tests
def test_01(self):
self.assertEqual(incr('aa'), 'ab')
def test_02(self):
self.assertEqual(incr('az'), 'ba')
def test_03(self):
self.assertEqual(incr('zz'), 'aaa') # my own assumption - not mentioned in TEH RULZ
def test_04(self):
self.assertFalse(pwOK('hijklmmn'))
def test_05(self):
self.assertFalse(pwOK('abbceffg'))
def test_06(self):
self.assertFalse(pwOK('abbcegjk'))
def test_07(self):
self.assertTrue(pwOK('abcdffaa'))
def test_08(self):
self.assertTrue(pwOK('ghjaabcc'))
processing.org seems to fit the billAn alternative is the python Anaconda distribution and the Spyder IDE (which is what I have done most of mine in.)
Thanks jo.
Will play after my trip to Germany.
(Thanks also Pancho for the perl suggestion.)
Finally found an answer to Day 12b (JSON parsing)(click to show/hide)
Day 7(click to show/hide)
Finally found an answer to Day 12b (JSON parsing)(click to show/hide)(click to show/hide)
Have just completed days 13 and 14, which seemed a bit easier than some of the earlier ones.
Day 13 (Table planning)(click to show/hide)
(click to show/hide)
Day 16(click to show/hide)
According to Eric Wastl (the Advent of Code author), today was the last of the "easy" ones.
Day 17 required some thought but very few lines of code.(click to show/hide)
Day 18, those blinking lights again.
I didn't use recursion. Fortunately my approach meant that part B required minimal extra coding(click to show/hide)
oaky@jarlsberg ~/Dropbox/AdventOfCode $ for i in */s*.py; do echo `grep -v '^[ ]*#' $i | wc -l` $i;done | sort -n
22 1/s1.py
26 2/s2.py
32 4/s4.py
48 17/s17.py
51 8/s8b.py
55 10/s10.py
58 12/s12.py
62 8/s8.py
71 14/s14.py
77 16/s16.py
82 3/s3.py
91 15/s15.py
95 13/s13.py
99 9/s9.py
100 6/s6.py
104 11/s11.py
137 5/s5.py
150 18/s18.py
173 7/s7.py
Eric Wastl @ericwastl 3h3 hours ago
If #AdventOfCode were a roller coaster, we're about to reach the corkscrews and loops and the part where it takes your picture.
Finally found an answer to Day 12b (JSON parsing)(click to show/hide)(click to show/hide)
[uint16]$foo = 1
[Uint16]$bar = $foo -shl 2
[Uint16]$car = $foo -shl 15
[Uint16]$har = $foo -shl 16
write-host "foo: $foo"
write-host "bar: $bar"
write-host "car: $car"
write-host "har: $har"
foo: 1
bar: 4
car: 32768
har: 0
Finally found an answer to Day 12b (JSON parsing)(click to show/hide)(click to show/hide)
I'm on 12b now. It's a bit of a bastard. I've not opened the spoilers (yet).
...
...
ETA: the spoiler below doesn't contain any info about the solution to the question, but does reveal something about part (b) of the question.(click to show/hide)
...
ETA: the spoiler below doesn't contain any info about the solution to the question, but does reveal something about part (b) of the question.(click to show/hide)(click to show/hide)
...
ETA: the spoiler below doesn't contain any info about the solution to the question, but does reveal something about part (b) of the question.(click to show/hide)(click to show/hide)(click to show/hide)
Day 25. A nice finish to the challenge.
Day 22. What a wind-up. This is the only one where the examples don't give an expected result, just an example of the steps. So all my tests passed but the answer was wrong.(click to show/hide)
(click to show/hide)
If anyone is feeling withdrawal symptoms with no more AoC, I recommend attempting the Synacor Challenge (https://challenge.synacor.com) also from Eric Wastl.
Advent of Code 2016 is imminent! :thumbsup:
Looks like jo's private leaderboard from last year carries over to 2016 too.
Day 1: I did pretty much the same as David Martin. Quite similar to one of the problems last year.
Diver300 - Initially I though your quick solution to part b was rather elegant but...(click to show/hide)
Day 1: I did pretty much the same as David Martin. Quite similar to one of the problems last year.
Diver300 - Initially I though your quick solution to part b was rather elegant but...(click to show/hide)(click to show/hide)
I think Day 2 is easier so mrs_e may have more joy today.
A bit lengthier to solve today but not hard - bit of regex processing and understanding ascii. Had to look up how to do nested sorts in python as I'd not done that before, otherwise pretty straightforward.
A bit lengthier to solve today but not hard - bit of regex processing and understanding ascii. Had to look up how to do nested sorts in python as I'd not done that before, otherwise pretty straightforward.
It was good to practice sort functions, but the best I could come up with for the checksum was(click to show/hide)
I'm sure there must be a way to create the hash anonymously on the fly, but it's eluding me.
I see where you're going with that, but the wriggly problem is to keep track of the counts for each letter.
Looking forward to tomorrow's offering.
I hope everyone has been enjoying #AdventOfCode! Today ends the warmup puzzles. It's uphill from here!
From the creator of Advent of Code this morning...Quote from: Eric WastlI hope everyone has been enjoying #AdventOfCode! Today ends the warmup puzzles. It's uphill from here!
Today was straightforward. I have then worked out how to do it in R without loops. One line to read the data in and one very long line to generate the answer.(click to show/hide)
i'm sure there is an efficient and elegant way to do it. Spent far too long trying to vectorise it in R with moderate amounts of nearly success then gave up and brute-forced it in python.(click to show/hide)
Interesting approaches.
Regular expressions seemed the obvious approach...(click to show/hide)
[–]topaz2078(AoC creator) 13 points 10 hours ago
Did you do this just to make me cry? Because it worked.
Did you look at Part 2 of that thread?
There is some pretty rank coding on display there..yep, I'm glad I don't have to support some of that ! I'm not saying mine is pretty or elegant, but at least I'm not on a mission to minimise the line count (and ergo readability)!
There is some pretty rank coding on display there..yep, I'm glad I don't have to support some of that ! I'm not saying mine is pretty or elegant, but at least I'm not on a mission to minimise the line count (and ergo readability)!
There is some pretty rank coding on display there..
I wasn't talking about the sheer brutality of the explicit regexs but some of the other code snippets that get posted.
Day 9 (decompression)(click to show/hide)
My computer is busted, trying to solve them on a phone would be a challenge too far. I'll have to catch up at the weekend
I fail to see how an infinite length string could be produced from finite input with that decompression method.
I fail to see how an infinite length string could be produced from finite input with that decompression method.(click to show/hide)
Day 12 (response to David Martin)But then you would be in 'how to write a compiler 101' territory rather than a short wee puzzle to solve.(click to show/hide)
Managed day 12 with only pencil and paper. ;D
Finally got round to day 13. Easy enough for the first part, second part is giving me a little grief for a reason I cannot fathom.
I've plotted it and worked through by hand but the answer I get appears to be too low for the site. Having checked it exhaustively by hand, I am convinced there is a bug.
[spoiler]
Input is 1350, value I get is 115. This is too low
[/spoiler]
ETA. Read the instructions. The maze bounds are 0,0 not 1,1.
Doh!
[spoiler]
ETA - new answer 122, still wrong.
[code rows=40]#X##X## ### ##### #####
#X#XXX# ## ######## # ##### # ## ##
XX##XX## ## # # ### # # ## ##
#XX#X# ## # ## # # #### #### #
#XX#X## ####### # # #### ## ### ## #
##X#XXX# # ## # # # # # # #
##XXX#X# # ## # ## # #### # #
# ##XXX# ## #### #### ## # # ## ## ##
#####XX# ### # # # # ######
####X### # #### ## ### # ## ###
# ###X##### ##### ## ## # ## # #
## #XXXX#X### ## # # # # # ## ##
#XX#XXXXX# # ##### # # # #####
## #### ####X# ##### ## # ### ### ##
## #XX###XXXX## # ## # ### ### # #
# ##XXXXX##X## # # # # # #
### #X######X##### # ## # # ### # #
XXX##X## #XXXXXX## # # ## ### ####
X#XXXXXX# #XX##X# # ## # ### # # #
XX##XX#X# #####X# ############ ####
## ##XXX### #XX## # # # ##### #
# ##X# #X# #### # ## ##
######X# ## #XX#XX####### ##### ## # ##
##XXX#X##### ##XXXXXX# # # #### ## #
#X#XXXXXX## # ##XX#XX# ## # # #
## #####X# ## ### #X# # ## # ## ## #
# # ##X### ## ##XX# ## ## ##### #
# ## # ## # ## ## # ## #
###### ## ## # ## # ### # ## # # #
# # # ## # ### # # ### ####
## ### # # # ## ## ## # #
##### ## ## ## ###### # # # # # #
(click to show/hide)
Day 14....
Hint:(click to show/hide)
Day 14....
Hint:(click to show/hide)(click to show/hide)
Day 14(click to show/hide)
Managed day 12 with only pencil and paper. ;DI've just belatedly solved day 11 similarly.
Managed day 12 with only pencil and paper. ;DI've just belatedly solved day 11 similarly.
Managed day 12 with only pencil and paper. ;DI've just belatedly solved day 11 similarly.(click to show/hide)
Managed day 12 with only pencil and paper. ;DI've just belatedly solved day 11 similarly.(click to show/hide)(click to show/hide)
Managed day 12 with only pencil and paper. ;DI've just belatedly solved day 11 similarly.(click to show/hide)(click to show/hide)
I agree.
I am not arguing that my solution is in any way robust. The example that you give is intentionally awkward, and I think that the puzzle always starts with the elevator on the ground floor, and it has to be soluble, so I don't think that real puzzles can be quite as awkward as yours, but I am sure there are some that have to start with less efficient moves.
I suspect that once the initial awkwardness is sorted, the bulk of a solution is perfectly efficient, but I haven't proved it.
We shall see if later puzzles leave me lost due to my lack of rigor in day 11
Why do you need to convert to lower case? It isn't material to the problem.
Day 15:
Straightforward.(click to show/hide)
After day 15's relatively easy problem, what's the betting day 16 is going to be a stinker?
After day 15's relatively easy problem, what's the betting day 16 is going to be a stinker?
Apparently not.(click to show/hide)
What am I going to do with the rest of my morning? Might have to do some work! ;D
After day 15's relatively easy problem, what's the betting day 16 is going to be a stinker?
for 2015, day 19 part 2 was the absolute hardest IMO.
I didn't really dig today's (Day 16). Just grinding though some standard string manipulation, which is more or less tedious depending on your language of choice.
I didn't really dig today's (Day 16). Just grinding though some standard string manipulation, which is more or less tedious depending on your language of choice.
I was wrong about this. Looking elsewhere (no links here to avoid obvious spoilers), there are some really elegant ways of processing the input that stop this being such an iterative task. If anyone's feeling like they've done too much proper work today, there's plenty of scope for thinking about some nifty optimisations. I should never have doubted Mr Wastl. What makes these challenges great is their hidden depths.
for 2015, day 19 part 2 was the absolute hardest IMO.
That's where I got stuck. This year I've skipped a second part. Maybe I should go back and look at the 2015 ones
I didn't really dig today's (Day 16). Just grinding though some standard string manipulation, which is more or less tedious depending on your language of choice.
I was wrong about this. Looking elsewhere (no links here to avoid obvious spoilers), there are some really elegant ways of processing the input that stop this being such an iterative task. If anyone's feeling like they've done too much proper work today, there's plenty of scope for thinking about some nifty optimisations. I should never have doubted Mr Wastl. What makes these challenges great is their hidden depths.
That's fine, although my viewpoint would be that if iteration works fast enough then any further optimisation is straying from science into art :)
I was hoping he was going to say that the memory would be something like many GB, not 272.for 2015, day 19 part 2 was the absolute hardest IMO.
That's where I got stuck. This year I've skipped a second part. Maybe I should go back and look at the 2015 ones
Having done 2016 day 11, 2015 day 19 part 2 wasn't that hard as it's a similar principle:(click to show/hide)
Did you manage to skip any rows, i.e. avoid having to do every single 400,000 transformations, or doesit just improve the speed at which you can generate each row from the next.
That wasn't particularly challenging - or maybe I am missing something(click to show/hide)
::-) <tries to look innocent and not childish>LOL... I just popped over to the CDC thread...and you've beaten me to it !!
Day 21 relies on realising the fact that(click to show/hide)
Day 21 relies on realising the fact that(click to show/hide)
From 5 onwards your rotation is wrong.Day 21 relies on realising the fact that(click to show/hide)(click to show/hide)
I do think that many of them are harder than this year.
I haven't found a programmatic solution to day 22 or day 23 that will work with anybody's input.
Day 22 is a perfect example of something a human is good at solving based on what they see visually but a computer isn't.(click to show/hide)
I haven't found a programmatic solution to day 22 or day 23 that will work with anybody's input.
Day 22 is a perfect example of something a human is good at solving based on what they see visually but a computer isn't.(click to show/hide)(click to show/hide)
I haven't found a programmatic solution to day 22 or day 23 that will work with anybody's input.
Day 22 is a perfect example of something a human is good at solving based on what they see visually but a computer isn't.(click to show/hide)(click to show/hide)
^--- (Ben's Day 22) Sure, but with a grid of only c. 30x30 or so cells, shouldn't it soon exhaust that bottom right corner and find a better route past the wall?maybe, yeah - I'll revisit and try and find out why it doesn't. I think the reason may be that the hash is 'too unique', i.e. it cares (too much) about the position of actual data rather than just the position of the space.(click to show/hide)
Hmm.. Just got back to this and I think my code is really inefficient compared to the times reported. Still running DFS (maybe BFS would be better?)
day 19 part 1:(click to show/hide)
2017 AoC in about 16 hours time! :)Arrgghhh!
I'm using Python again, trying to use Pandas/numpy wherever possible.Interesting - I'd not seen that.(click to show/hide)
ooh, signed up
(And going back and doing 2016 as practice...)
Ah yes, well spotted. A language that supports negative array indices is hinted by part one, and helps for part 2.I presume that is CTRL-C/CTRL-V to copy and paste the original data? And is that one part or both parts.
58 keystrokes. Anyone manage fewer?
2016 done, will move on to 2015 too.
Doing all of mine in Perl as that's what I use for quick hacks and prototypes.
That's the thing with a lot of these - if you short-circuit part 1, you find part 2 needs the data from part 1.
The second part I used a dynamic programming approach and promptly filled it so full of bugs it took a long time to wrangle out. Was there a more elegant way that I somehow missed?
That's the thing with a lot of these - if you short-circuit part 1, you find part 2 needs the data from part 1.
Or if you don't short-circuit part 1 you find that part 2 involves computing something so big that it would take the naive algorithm years to finish so you do need to short-circuit it.
Most of the time (having just gone back and done the whole of 2016 and 2015 over the last few days) whatever I do in part (a) is usually the wrong one. I guess this is no coincidence.
I used the same method.(click to show/hide)
Today's was very much a start of week 1 problem.(click to show/hide)
Day 6very similar
The debugging output for my code had basically solved part 2 by the time that I had solved part 1(click to show/hide)
Day 6very similar
The debugging output for my code had basically solved part 2 by the time that I had solved part 1(click to show/hide)(click to show/hide)
Day 6very similar
The debugging output for my code had basically solved part 2 by the time that I had solved part 1(click to show/hide)(click to show/hide)(click to show/hide)
Day 7:(click to show/hide)
(click to show/hide)
Day 7:(click to show/hide)
can you not (instead of the two cases) do:
I cannot imagine voluntarily choosing to do it that way. It makes me cringe even thinking about it.
(click to show/hide)
Day 8: Will it be another fake CPU question (I do like them) or something like a knapsack or another TSP-esque classic?
(click to show/hide)
I've written enough stuff that parses input (specifically SQL and CSV) to understand the joy of string parsing with escape characters. Even with a slightly foggy brain from a mild hangover.(click to show/hide)
...then a second one to parse the garbage free input into the groups, then a recursive function to score it all.The input was well-formed enough that it only required counting the { up and } down
I'm secretly hoping that someone attempts this with a regex and eventually learns the lesson about regular expressions and context-free grammars.
Just plough through and process it as a stream.(click to show/hide)
I did come across an interesting puzzle that was easily solved to a certain state with matrix algebra. I then have to sort a matrix to get the minimum diagonal to get the appropriate order of rows.
Day 11I must admit that trying to sort that at early morning after dealing with a frozen pipe leading to a major water leak in the house was challenging enough - I thought it should be able to be done something like that. Instead I did it the hard way.(click to show/hide)
Day 11(click to show/hide)
I am struggling to see how you come up with that matrix.
(click to show/hide)
Today was straightforward.(click to show/hide)
Still working on a more elegant solution for day 13b.
My work in progress (big spoiler):-
Today's was the first this year where part 2 didn't respond well to a simplistic approach.
You have a faster computer than me. Mine took a few minutes to run and I was completely naive with searching every possibility. The approach I had been thinking about is this:(click to show/hide)
I'll see if I can knock up an input that has an answer that is orders of magnitude larger.
Ooh. Do 4 colours suffice?
(click to show/hide)
day 16 part 2 is proving difficult.....You're not the only one stuck on that
I didn't think that would work.That is now obvious. :)(click to show/hide)
I didn't think that would work.(click to show/hide)
Day 16(click to show/hide)
Day 16(click to show/hide)(click to show/hide)
(click to show/hide)
Day 17 was quite straightforward.(click to show/hide)
(click to show/hide)
64 characters for part 2, including input data. ;D
64 characters for part 2, including input data. ;D
I can get it down to 84 in perl, but then I'm not very good at code golf.
17a was quite straightforward.
17b required minor thought but eventually succumbed to brute force(click to show/hide)
17a was quite straightforward.
17b required minor thought but eventually succumbed to brute force(click to show/hide)(click to show/hide)
Ben T:(click to show/hide)
Don't you need to increment buf_len?Yes.
64 characters for part 2, including input data. ;D
I can get it down to 84 in perl, but then I'm not very good at code golf.
I look forward to comparing line noise tomorrow!
64 characters for part 2, including input data. ;D
I can get it down to 84 in perl, but then I'm not very good at code golf.
I look forward to comparing line noise tomorrow!(click to show/hide)
First read the instructions..(click to show/hide)
First read the instructions..(click to show/hide)
Should that be Day 18 ?
Fortunately the input was well behaved, I had considered cases like two corners in consecutive steps, realised that the coding would be more involved and if it came across a not immediately tractable solution to print the local environment and ask for guidance. It didn't need to as there was at least one step between each corner.
|
B++A
++
(click to show/hide)
(click to show/hide)(click to show/hide)
(click to show/hide)(click to show/hide)(click to show/hide)
butFortunately the input was well behaved, I had considered cases like two corners in consecutive steps, realised that the coding would be more involved and if it came across a not immediately tractable solution to print the local environment and ask for guidance. It didn't need to as there was at least one step between each corner.
Not sure why this would be a problem, there are no decisions to be made at any corners. Either you can continue on in a straight line still or you have to choose left or right (and there won't be a choice).
For example:-Code: [Select]|
B++A
++
is unambiguous.
||||
++++
isn't unless you look further afield than immediately adjacent characters. I couldn't be bothered so just wrote a prompt in to look at it by eye and indicate where it should go(click to show/hide)
butCode: [Select]A|BC
isn't unless you look further afield than immediately adjacent characters. I couldn't be bothered so just wrote a prompt in to look at it by eye and indicate where it should go
++++
(click to show/hide)(click to show/hide)(click to show/hide)
(click to show/hide)
(click to show/hide)(click to show/hide)
Day 20
First part was solved with one run through the data.(click to show/hide)
True. I'm not claiming that my algorithm for part 1 would work with all possible inputs.Day 20
First part was solved with one run through the data.(click to show/hide)(click to show/hide)
Off by one in your iteration count?
Off by one in your iteration count?
Nope, more serious than that, but I got it (took me about 20 minutes to find it but I've been doing some real work for the last couple of hours). 43 minutes from submitting part (a) to submitting part (b). Ugh.(click to show/hide)
(click to show/hide)
(click to show/hide)
They have been a little bit samey. Maybe a new thread with some 'extra' puzzles on?
(click to show/hide)
(click to show/hide)
That is why it is in (ETA: now multiple) spoiler tags.(click to show/hide)
(click to show/hide)
(click to show/hide)(click to show/hide)
(click to show/hide)
(click to show/hide)
Decided to learn go so redoing 2017 in go.If you want more practice try some project euler problems, AoC is easy in comparison (mostly). :P
https://github.com/alexgreenbank/AdventOfCode
It's certainly easier when you know how to solve each one efficiently (or at least efficiently enough).
Day 5 and I finally got to the point where I wrote the complete program for part one and only had to correct typos after the first attempt at running it.
If you want more practice try some project euler problems, AoC is easy in comparison (mostly). :P
Did day 1 and 2 with perl one liners. Although the second part of day 2 was a bit long
Not sure if ICBA to carry on with this :)
For day 1 part 2 - do you need to use more than one loop of the input text? It's confusing me lots!
Day 7: That was ok. Dependencies and scheduling.
What's scary, apart from the two syntax errors (missing parens), is both parts produced the correct answer first time without needing any tweaks.
Day 8. The first part didn't take me too long. For the second part, the example given didn't find a lot of the mistakes in my code.This - took a wee while for the code to run.
(click to show/hide)
(click to show/hide)
(click to show/hide)
Part 1.
Frustrating out-by-one error gave the correct answer for all but one of the examples. Implementing the instructions as written, array-splicing all the way, ran in sub-second.
Part 2.
No idea. Times ten ran in about a minute. Times 100 - forget it. Can't see the pattern or formula.
(click to show/hide)
(click to show/hide)
I found day 10 straightforward.(click to show/hide)
(click to show/hide)
(click to show/hide)
(click to show/hide)
Day 11 part 2(click to show/hide)
position=<679, 117> velocity=<-7, -1>
position=<584, 498> velocity=<-6, -5>
position=<489, 594> velocity=<-5, -6>
position=<109, 310> velocity=<-1, -3>
position=<585, 399> velocity=<-6, -4>
position=<300, 305> velocity=<-3, -3>
position=<680, 211> velocity=<-7, -2>
position=<586, 493> velocity=<-6, -5>
position=<586, 494> velocity=<-6, -5>
position=<397, 398> velocity=<-4, -4>
position=< 18, 683> velocity=< 0, -7>
position=< 19, 18> velocity=< 0, 0>
position=<399, 399> velocity=<-4, -4>
position=< 19, 20> velocity=< 0, 0>
position=<115, 21> velocity=<-1, 0>
position=<591, 402> velocity=<-6, -4>
position=<401, 403> velocity=<-4, -4>
position=<307, 308> velocity=<-3, -3>
position=<498, 305> velocity=<-5, -3>
position=<308, 686> velocity=<-3, -7>
position=<688, 117> velocity=<-7, -1>
position=<404, 586> velocity=<-4, -6>
position=<594, 112> velocity=<-6, -1>
position=< 24, 398> velocity=< 0, -4>
position=< 24, 399> velocity=< 0, -4>
position=<215, 16> velocity=<-2, 0>
position=<216, 491> velocity=<-2, -5>
position=<121, 17> velocity=<-1, 0>
position=< 27, 588> velocity=< 0, -6>
position=< 28, 18> velocity=< 0, 0>
position=<503, 19> velocity=<-5, 0>
position=<218, 495> velocity=<-2, -5>
position=<503, 686> velocity=<-5, -7>
position=<598, 212> velocity=<-6, -2>
position=<601, 223> velocity=<-6, -2>
position=< 31, 319> velocity=< 0, -3>
position=<126, 510> velocity=<-1, -5>
position=<411, 701> velocity=<-4, -7>
position=<221, 227> velocity=<-2, -2>
position=<127, 223> velocity=<-1, -2>
position=<412, 323> velocity=<-4, -3>
position=<697, 419> velocity=<-7, -4>
position=<603, 507> velocity=<-6, -5>
position=<128, 705> velocity=<-1, -7>
position=<318, 326> velocity=<-3, -3>
position=<319, 696> velocity=<-3, -7>
position=<224, 232> velocity=<-2, -2>
position=<130, 696> velocity=<-1, -7>
position=<605, 707> velocity=<-6, -7>
position=< 36, 696> velocity=< 0, -7>
position=<226, 510> velocity=<-2, -5>
position=<606, 518> velocity=<-6, -5>
position=<322, 601> velocity=<-3, -6>
position=<702, 511> velocity=<-7, -5>
position=< 37, 139> velocity=< 0, -1>
position=<513, 601> velocity=<-5, -6>
position=<418, 511> velocity=<-4, -5>
position=<418, 140> velocity=<-4, -1>
position=< 39, 506> velocity=< 0, -5>
position=<609, 36> velocity=<-6, 0>
position=<514, 710> velocity=<-5, -7>
position=<705, 221> velocity=<-7, -2>
position=<705, 131> velocity=<-7, -1>
position=<135, 615> velocity=<-1, -6>
position=<326, 506> velocity=<-3, -5>
position=<136, 319> velocity=<-1, -3>
position=<231, 225> velocity=<-2, -2>
position=< 41, 701> velocity=< 0, -7>
position=<516, 236> velocity=<-5, -2>
position=<137, 31> velocity=<-1, 0>
position=<517, 319> velocity=<-5, -3>
position=<612, 236> velocity=<-6, -2>
position=<613, 506> velocity=<-6, -5>
position=<233, 412> velocity=<-2, -4>
position=<613, 33> velocity=<-6, 0>
position=<613, 46> velocity=<-6, 0>
position=< 50, 54> velocity=< 0, 0>
position=<145, 340> velocity=<-1, -3>
position=<525, 436> velocity=<-5, -4>
position=<620, 152> velocity=<-6, -1>
position=<525, 153> velocity=<-5, -1>
position=<240, 344> velocity=<-2, -3>
position=< 50, 155> velocity=< 0, -1>
position=<430, 156> velocity=<-4, -1>
position=<525, 442> velocity=<-5, -4>
position=<431, 624> velocity=<-4, -6>
position=<432, 624> velocity=<-4, -6>
position=<242, 245> velocity=<-2, -2>
position=< 53, 530> velocity=< 0, -5>
position=<434, 245> velocity=<-4, -2>
position=<625, 435> velocity=<-6, -4>
position=<721, 340> velocity=<-7, -3>
position=<721, 56> velocity=<-7, 0>
position=<351, 255> velocity=<-3, -2>
position=<161, 541> velocity=<-1, -5>
position=<161, 162> velocity=<-1, -1>
position=<352, 730> velocity=<-3, -7>
position=<257, 448> velocity=<-2, -4>
position=< 67, 354> velocity=< 0, -3>
position=<257, 450> velocity=<-2, -4>
position=<162, 166> velocity=<-1, -1>
position=<637, 262> velocity=<-6, -2>
position=<352, 738> velocity=<-3, -7>
position=<448, 159> velocity=<-4, -1>
position=<544, 634> velocity=<-5, -6>
position=<260, 64> velocity=<-2, 0>
position=<736, 444> velocity=<-7, -4>
position=<357, 64> velocity=<-3, 0>
position=<168, 729> velocity=<-1, -7>
position=<367, 741> velocity=<-3, -7>
position=<558, 171> velocity=<-5, -1>
position=< 83, 93> velocity=< 0, 0>
position=<274, 361> velocity=<-2, -3>
position=<369, 473> velocity=<-3, -4>
position=<465, 552> velocity=<-4, -5>
position=<180, 553> velocity=<-1, -5>
position=<370, 93> velocity=<-3, 0>
position=<181, 554> velocity=<-1, -5>
position=<561, 473> velocity=<-5, -4>
position=<752, 80> velocity=<-7, 0>
position=<372, 283> velocity=<-3, -2>
position=<468, 271> velocity=<-4, -2>
position=<373, 188> velocity=<-3, -1>
position=<184, 645> velocity=<-1, -6>
position=<469, 171> velocity=<-4, -1>
position=<279, 172> velocity=<-2, -1>
position=<754, 268> velocity=<-7, -2>
position=<659, 744> velocity=<-6, -7>
position=<184, 650> velocity=<-1, -6>
position=< 89, 81> velocity=< 0, 0>
position=<374, 747> velocity=<-3, -7>
position=<469, 83> velocity=<-4, 0>
position=<564, 559> velocity=<-5, -5>
position=<564, 750> velocity=<-5, -7>
position=<374, 656> velocity=<-3, -6>
position=<279, 562> velocity=<-2, -5>
position=<754, 373> velocity=<-7, -3>
position=<469, 374> velocity=<-4, -3>
position=<564, 565> velocity=<-5, -5>
position=<564, 186> velocity=<-5, -1>
position=<184, 472> velocity=<-1, -4>
position=< 89, 283> velocity=< 0, -2>
position=<280, 75> velocity=<-2, 0>
position=<565, 76> velocity=<-5, 0>
position=<185, 172> velocity=<-1, -1>
position=<375, 743> velocity=<-3, -7>
position=<470, 744> velocity=<-4, -7>
position=<470, 460> velocity=<-4, -4>
position=<566, 455> velocity=<-5, -4>
position=<566, 551> velocity=<-5, -5>
position=<625, 775> velocity=< 3, 2>
position=<626, 490> velocity=< 3, 5>
position=<342, 490> velocity=< 6, 5>
position=<817, 593> velocity=< 1, 4>
position=<342, 784> velocity=< 6, 2>
position=<818, 585> velocity=< 1, 4>
position=<818, 403> velocity=< 1, 6>
position=<344, 396> velocity=< 6, 6>
position=<344, 777> velocity=< 6, 2>
position=<439, 496> velocity=< 5, 5>
position=<249, 592> velocity=< 7, 4>
position=<440, 873> velocity=< 5, 1>
position=<725, 684> velocity=< 2, 3>
position=<915, 305> velocity=< 0, 7>
position=<251, 970> velocity=< 7, 0>
position=<442, 875> velocity=< 5, 1>
position=<917, 306> velocity=< 0, 7>
position=<348, 304> velocity=< 6, 7>
position=<823, 782> velocity=< 1, 2>
position=<634, 494> velocity=< 3, 5>
position=<349, 878> velocity=< 6, 1>
position=<730, 403> velocity=< 2, 6>
position=<920, 309> velocity=< 0, 7>
position=<449, 400> velocity=< 5, 6>
position=<829, 496> velocity=< 1, 5>
position=<449, 687> velocity=< 5, 3>
position=<354, 973> velocity=< 6, 0>
position=<354, 404> velocity=< 6, 6>
position=<544, 880> velocity=< 4, 1>
position=<639, 786> velocity=< 3, 2>
position=<449, 882> velocity=< 5, 1>
position=<544, 408> velocity=< 4, 6>
position=<450, 305> velocity=< 5, 7>
position=<641, 780> velocity=< 3, 2>
position=<927, 400> velocity=< 0, 6>
position=<453, 590> velocity=< 5, 4>
position=<359, 305> velocity=< 6, 7>
position=<359, 401> velocity=< 6, 6>
position=<740, 401> velocity=< 2, 6>
position=<836, 782> velocity=< 1, 2>
position=<362, 783> velocity=< 6, 2>
position=<362, 879> velocity=< 6, 1>
position=<742, 785> velocity=< 2, 2>
position=<743, 974> velocity=< 2, 0>
position=<933, 975> velocity=< 0, 0>
position=<743, 311> velocity=< 2, 7>
position=<269, 973> velocity=< 7, 0>
position=<934, 596> velocity=< 0, 4>
position=<554, 597> velocity=< 4, 4>
position=<839, 978> velocity=< 1, 0>
position=<650, 783> velocity=< 3, 2>
position=<461, 783> velocity=< 5, 2>
position=<937, 878> velocity=< 0, 1>
position=<558, 403> velocity=< 4, 6>
position=<844, 973> velocity=< 1, 0>
position=<655, 498> velocity=< 3, 5>
position=<941, 879> velocity=< 0, 1>
position=<562, 784> velocity=< 4, 2>
position=<658, 689> velocity=< 3, 3>
position=<658, 785> velocity=< 3, 2>
position=<469, 691> velocity=< 5, 3>
position=<849, 977> velocity=< 1, 0>
position=<671, 498> velocity=< 3, 5>
position=<576, 404> velocity=< 4, 6>
position=<291, 785> velocity=< 7, 2>
position=<861, 501> velocity=< 1, 5>
position=<482, 972> velocity=< 5, 0>
position=<387, 692> velocity=< 6, 3>
position=<578, 686> velocity=< 4, 3>
position=<958, 883> velocity=< 0, 1>
position=<389, 591> velocity=< 6, 4>
position=<389, 979> velocity=< 6, 0>
position=<579, 505> velocity=< 4, 5>
position=<295, 401> velocity=< 7, 6>
position=<580, 505> velocity=< 4, 5>
position=<866, 876> velocity=< 1, 1>
position=<866, 315> velocity=< 1, 7>
position=<677, 306> velocity=< 3, 7>
position=<867, 505> velocity=< 1, 5>
position=<393, 686> velocity=< 6, 3>
position=<583, 409> velocity=< 4, 6>
position=<393, 315> velocity=< 6, 7>
position=<394, 401> velocity=< 6, 6>
position=<964, 972> velocity=< 0, 0>
position=<774, 974> velocity=< 2, 0>
position=<394, 314> velocity=< 6, 7>
position=<775, 879> velocity=< 2, 1>
position=<680, 883> velocity=< 3, 1>
position=<490, 979> velocity=< 5, 0>
position=<586, 404> velocity=< 4, 6>
position=<396, 405> velocity=< 6, 6>
position=<871, 786> velocity=< 1, 2>
position=<871, 977> velocity=< 1, 0>
position=<682, 501> velocity=< 3, 5>
position=<588, 406> velocity=< 4, 6>
position=<778, 312> velocity=< 2, 7>
position=<589, 502> velocity=< 4, 5>
position=<495, 977> velocity=< 5, 0>
position=<506, 318> velocity=< 5, 7>
position=<792, 508> velocity=< 2, 5>
position=<603, 401> velocity=< 4, 6>
position=<698, 687> velocity=< 3, 3>
position=<413, 878> velocity=< 6, 1>
position=<413, 974> velocity=< 6, 0>
position=<603, 785> velocity=< 4, 2>
position=<793, 982> velocity=< 2, 0>
position=<889, 971> velocity=< 1, 0>
position=<509, 500> velocity=< 5, 5>
position=<604, 691> velocity=< 4, 3>
position=<414, 407> velocity=< 6, 6>
position=<794, 788> velocity=< 2, 2>
position=<699, 697> velocity=< 3, 3>
position=<415, 306> velocity=< 6, 7>
position=<795, 599> velocity=< 2, 4>
position=<700, 792> velocity=< 3, 2>
position=<701, 496> velocity=< 3, 5>
position=<416, 410> velocity=< 6, 6>
position=<891, 316> velocity=< 1, 7>
position=<797, 505> velocity=< 2, 5>
Day 10 extension :)
Day 10 extension :)
Excellent, found it but will need to work on an algorithm to detect when to stop as I had to manually step through once in the right area to get the exact frame.
(click to show/hide)
What does it say then? And at what time (frame)?
Day 12. Can't see why my part 2 is wrong.Nor me.
Day 12. Can't see why my part 2 is wrong.Nor me.
(click to show/hide)
(click to show/hide)
Nice.(click to show/hide)
(click to show/hide)
Nice.(click to show/hide)
(click to show/hide)
interesting idea. Will try that.(click to show/hide)
It's not the answer but it will lead you in the right direction, up to you whether you read it obviously.
Been rather busy so AoC has been on hold.interesting idea. Will try that.(click to show/hide)
It's not the answer but it will lead you in the right direction, up to you whether you read it obviously.
My code for Day 15's horrible. Lots of nested loops with break-outs, inline functions and branches. Eugh. ::-) ;D(click to show/hide)
My code for Day 15's horrible. Lots of nested loops with break-outs, inline functions and branches. Eugh. ::-) ;D(click to show/hide)(click to show/hide)
Still stuck on day 17, havent' tried any subsequent ones - have had to go out to the shops for new jelly and nails as I keep running out, and start again in a new room with a fresh ceiling.
Still stuck on day 17, havent' tried any subsequent ones - have had to go out to the shops for new jelly and nails as I keep running out, and start again in a new room with a fresh ceiling.
Ooh. What's the problem? Wrong answer, not fast enough or just can't get it to work properly at all?
I had a bug in mine where it wouldn't accept my answer for part (b), when I eventually fixed it I got the right answer for part (b) but the answer it gave for part (a) changed as well but my original (now incorrect) answer for part (a) was accepted.
FWIW, my program agrees with yours for your input. I get the same answer and I can't see anything wrong in the output.
My previous version the program also gives the same answer (even though it exhibits a bug with my input).
I'd move on.
Groan............... found it,(click to show/hide)
(click to show/hide)
Ooh, day 23 part b looks like a stinker, have ideas and not going to look anywhere for hints. Might take a while!My method was something similar but opposite results - it worked for the example but unfortunately not the real data :(
[EDIT] Got the answer for part b but not satisfied with my method at all. It doesn't work at all on the simple example given in the problem.
Ooh, day 23 part b looks like a stinker, have ideas and not going to look anywhere for hints. Might take a while!
[EDIT] Got the answer for part b but not satisfied with my method at all. It doesn't work at all on the simple example given in the problem.
Some details in this spoiler.(click to show/hide)
Finally got it.Ooh, day 23 part b looks like a stinker, have ideas and not going to look anywhere for hints. Might take a while!My method was something similar but opposite results - it worked for the example but unfortunately not the real data :(
[EDIT] Got the answer for part b but not satisfied with my method at all. It doesn't work at all on the simple example given in the problem.
Finished now (didn't get a chance to do more than a few minutes during the last 3 days).
Wasted a bit of time with a misreading of the 24th but got it in 10 minutes this morning and part 2 followed on simply. Not a big fan of big wordy plods like this, but they're quite representative of real world coding with slightly imprecise specs and long slogs of boring programming!
(click to show/hide)
It's not the answer but it will lead you in the right direction, up to you whether you read it obviously.
This year I'm doing them in C# instead of Perl. ... 174 lines of code + tests, would probably have been about ten in Perl.
This year I'm doing them in C# instead of Perl. The gains from a nice test framework and intellisense are more than cancelled out by the sheer wordiness of it all.
Delay today caused by trying to dump all the points into Lists and do a Linq intersect to pop out all the crossings. Great for the tests, way too slow for the full puzzle - didn't expect to get hit by that on day 3. So had to go back and do it again properly. 174 lines of code + tests, would probably have been about ten in Perl.
28 seconds?
Day 5 looks good, probably a recursive algorithm but haven't tried it yet
Day 5 looks good, probably a recursive algorithm but haven't tried it yet
You see the future!
(Won't post any spoilers until most people have had a go.)
That was my joke about being able to see the future!
(He can't, he's just got the day wrong.)
I might observe that Day 5 instructions include some artful misdirection(click to show/hide)
I might observe that Day 5 instructions include some artful misdirection(click to show/hide)
I don't know if it was sneaky but misintepreting 5 and 6 led to code than ran all 4 test programs and gave the correct answers, but crapped out on two of the conditions of the longer 5th test program. Most confusing.
Yeah. The instructions also said it prints "a series of diagnostic error codes which should all be zero" and then prints the answer.
Mine printed a number 3 first, then a load of zeros, then the answer. But the 3 didn't seem to indicate I had a bug, as the answer was still right.
Could the errant 3 be a hint to a future puzzle that complains of "one of the spaceships' systems not working properly", I wonder...
3,225,1,225,6,6,1100,1,238,225,104,0,1002,92,42,224,1001,224,-3444,224,4,224,102,8,223,223,101,4,224,224,1,224,223,223,1102,24,81,225,1101,89,36,224,101,-125,224,224,4,224,102,8,223,223,101,5,224,224,1,224,223,223,2,118,191,224,101,-880,224,224,4,224,1002,223,8,223,1001,224,7,224,1,224,223,223,1102,68,94,225,1101,85,91,225,1102,91,82,225,1102,85,77,224,101,-6545,224,224,4,224,1002,223,8,223,101,7,224,224,1,223,224,223,1101,84,20,225,102,41,36,224,101,-3321,224,224,4,224,1002,223,8,223,101,7,224,224,1,223,224,223,1,188,88,224,101,-183,224,224,4,224,1002,223,8,223,1001,224,7,224,1,224,223,223,1001,84,43,224,1001,224,-137,224,4,224,102,8,223,223,101,4,224,224,1,224,223,223,1102,71,92,225,1101,44,50,225,1102,29,47,225,101,7,195,224,101,-36,224,224,4,224,102,8,223,223,101,6,224,224,1,223,224,223,4,223,99,0,0,0,677,0,0,0,0,0,0,0,0,0,0,0,1105,0,99999,1105,227,247,1105,1,99999,1005,227,99999,1005,0,256,1105,1,99999,1106,227,99999,1106,0,265,1105,1,99999,1006,0,99999,1006,227,274,1105,1,99999,1105,1,280,1105,1,99999,1,225,225,225,1101,294,0,0,105,1,0,1105,1,99999,1106,0,300,1105,1,99999,1,225,225,225,1101,314,0,0,106,0,0,1105,1,99999,107,677,677,224,1002,223,2,223,1006,224,329,1001,223,1,223,1108,226,677,224,102,2,223,223,1006,224,344,101,1,223,223,1107,226,226,224,1002,223,2,223,1006,224,359,101,1,223,223,8,677,226,224,1002,223,2,223,1006,224,374,1001,223,1,223,1107,677,226,224,102,2,223,223,1005,224,389,1001,223,1,223,1008,677,677,224,1002,223,2,223,1006,224,404,1001,223,1,223,108,677,677,224,102,2,223,223,1005,224,419,1001,223,1,223,1107,226,677,224,102,2,223,223,1006,224,434,101,1,223,223,1008,226,226,224,1002,223,2,223,1006,224,449,1001,223,1,223,107,226,226,224,102,2,223,223,1006,224,464,1001,223,1,223,1007,677,226,224,1002,223,2,223,1006,224,479,1001,223,1,223,1108,226,226,224,102,2,223,223,1006,224,494,1001,223,1,223,8,226,226,224,1002,223,2,223,1005,224,509,1001,223,1,223,7,226,677,224,102,2,223,223,1005,224,524,101,1,223,223,1008,677,226,224,102,2,223,223,1005,224,539,101,1,223,223,107,226,677,224,1002,223,2,223,1006,224,554,1001,223,1,223,1108,677,226,224,102,2,223,223,1005,224,569,101,1,223,223,108,226,226,224,1002,223,2,223,1005,224,584,1001,223,1,223,7,677,226,224,1002,223,2,223,1005,224,599,1001,223,1,223,108,226,677,224,1002,223,2,223,1006,224,614,101,1,223,223,1007,677,677,224,1002,223,2,223,1006,224,629,101,1,223,223,7,677,677,224,102,2,223,223,1005,224,644,101,1,223,223,1007,226,226,224,1002,223,2,223,1006,224,659,1001,223,1,223,8,226,677,224,102,2,223,223,1005,224,674,1001,223,1,223,4,223,99,226
There seems to be several different ways he can make the puzzles non-trivial - the main ones I've seen so far are (1) making the spec fairly complicated so you have to read it thoroughly, (2) is by making the data such that the 'obvious' / brute-force solution would never complete quickly enough, and an optimization or dynamic programming is required, (3) is by introducing a reverse-engineering requirement, like when the 'machine code' is in fact doing a loop with all its jumps and you have to figure out what the loop's trying to do.
There is the other one you mention of trying to trick specific languages, integer overflows are an obvious one. I quite enjoy the challenge imposed by that to be honest.
I personally enjoy (2) most. I don't enjoy (1) quite so much, and I find (3) difficult.
Hmm, cheers - ok just tried it again and it's not printing the phantom '3' now. Must have just been a debugging line I left in...cheers anywayYeah. The instructions also said it prints "a series of diagnostic error codes which should all be zero" and then prints the answer.
Mine printed a number 3 first, then a load of zeros, then the answer. But the 3 didn't seem to indicate I had a bug, as the answer was still right.
Could the errant 3 be a hint to a future puzzle that complains of "one of the spaceships' systems not working properly", I wonder...
If you give me your input I can run it through mine and see what I get. Here's my input:-Code: [Select]3,225,1,225,6,6,1100,1,238,225,104,0,1002,92,42,224,1001,224,-3444,224,4,224,102,8,223,223,101,4,224,224,1,224,223,223,1102,24,81,225,1101,89,36,224,101,-125,224,224,4,224,102,8,223,223,101,5,224,224,1,224,223,223,2,118,191,224,101,-880,224,224,4,224,1002,223,8,223,1001,224,7,224,1,224,223,223,1102,68,94,225,1101,85,91,225,1102,91,82,225,1102,85,77,224,101,-6545,224,224,4,224,1002,223,8,223,101,7,224,224,1,223,224,223,1101,84,20,225,102,41,36,224,101,-3321,224,224,4,224,1002,223,8,223,101,7,224,224,1,223,224,223,1,188,88,224,101,-183,224,224,4,224,1002,223,8,223,1001,224,7,224,1,224,223,223,1001,84,43,224,1001,224,-137,224,4,224,102,8,223,223,101,4,224,224,1,224,223,223,1102,71,92,225,1101,44,50,225,1102,29,47,225,101,7,195,224,101,-36,224,224,4,224,102,8,223,223,101,6,224,224,1,223,224,223,4,223,99,0,0,0,677,0,0,0,0,0,0,0,0,0,0,0,1105,0,99999,1105,227,247,1105,1,99999,1005,227,99999,1005,0,256,1105,1,99999,1106,227,99999,1106,0,265,1105,1,99999,1006,0,99999,1006,227,274,1105,1,99999,1105,1,280,1105,1,99999,1,225,225,225,1101,294,0,0,105,1,0,1105,1,99999,1106,0,300,1105,1,99999,1,225,225,225,1101,314,0,0,106,0,0,1105,1,99999,107,677,677,224,1002,223,2,223,1006,224,329,1001,223,1,223,1108,226,677,224,102,2,223,223,1006,224,344,101,1,223,223,1107,226,226,224,1002,223,2,223,1006,224,359,101,1,223,223,8,677,226,224,1002,223,2,223,1006,224,374,1001,223,1,223,1107,677,226,224,102,2,223,223,1005,224,389,1001,223,1,223,1008,677,677,224,1002,223,2,223,1006,224,404,1001,223,1,223,108,677,677,224,102,2,223,223,1005,224,419,1001,223,1,223,1107,226,677,224,102,2,223,223,1006,224,434,101,1,223,223,1008,226,226,224,1002,223,2,223,1006,224,449,1001,223,1,223,107,226,226,224,102,2,223,223,1006,224,464,1001,223,1,223,1007,677,226,224,1002,223,2,223,1006,224,479,1001,223,1,223,1108,226,226,224,102,2,223,223,1006,224,494,1001,223,1,223,8,226,226,224,1002,223,2,223,1005,224,509,1001,223,1,223,7,226,677,224,102,2,223,223,1005,224,524,101,1,223,223,1008,677,226,224,102,2,223,223,1005,224,539,101,1,223,223,107,226,677,224,1002,223,2,223,1006,224,554,1001,223,1,223,1108,677,226,224,102,2,223,223,1005,224,569,101,1,223,223,108,226,226,224,1002,223,2,223,1005,224,584,1001,223,1,223,7,677,226,224,1002,223,2,223,1005,224,599,1001,223,1,223,108,226,677,224,1002,223,2,223,1006,224,614,101,1,223,223,1007,677,677,224,1002,223,2,223,1006,224,629,101,1,223,223,7,677,677,224,102,2,223,223,1005,224,644,101,1,223,223,1007,226,226,224,1002,223,2,223,1006,224,659,1001,223,1,223,8,226,677,224,102,2,223,223,1005,224,674,1001,223,1,223,4,223,99,226
This (with an input of 1) gives 9 zeroes and then my answer of 9961446. With an input of 5 it gives 742621.
You see the future!
BTW, I'm expecting INPUT and OUTPUT to go the same way that https://adventofcode.com/2017/day/18 did and you'll end up needing two copies of the 'computer' running at the same time swapping inputs/outputs and vice versa.
If you get a different answer could you please say so BUT NOT WHAT YOUR ANSWER IS. Thanks
3,8,1001,8,10,8,105,1,0,0,21,46,55,68,89,110,191,272,353,434,99999,3,9,1002,9,3,9,1001,9,3,9,102,4,9,9,101,4,9,9,1002,9,5,9,4,9,99,3,9,102,3,9,9,4,9,99,3,9,1001,9,5,9,102,4,9,9,4,9,99,3,9,1001,9,5,9,1002,9,2,9,1001,9,5,9,1002,9,3,9,4,9,99,3,9,101,3,9,9,102,3,9,9,101,3,9,9,1002,9,4,9,4,9,99,3,9,1001,9,1,9,4,9,3,9,1001,9,1,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,101,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,1,9,4,9,3,9,1001,9,2,9,4,9,99,3,9,102,2,9,9,4,9,3,9,101,2,9,9,4,9,3,9,101,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,102,2,9,9,4,9,3,9,101,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,101,1,9,9,4,9,3,9,101,2,9,9,4,9,3,9,101,2,9,9,4,9,99,3,9,101,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,101,1,9,9,4,9,3,9,101,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,101,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,101,2,9,9,4,9,99,3,9,102,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,101,1,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,101,2,9,9,4,9,3,9,101,2,9,9,4,9,3,9,1001,9,1,9,4,9,99,3,9,1002,9,2,9,4,9,3,9,101,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,101,1,9,9,4,9,3,9,101,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,1,9,4,9,3,9,102,2,9,9,4,9,99
$ ./7d.pl | sort -rn -k3 | head
57968 gives 3745599
57698 gives 3742019
75968 gives 3689151
75698 gives 3685571
57986 gives 3671647
Bum. I am stymied on Day 7 Part 2. All current and historical tests for my computer give the correct results. Day 7 Part1 was correct at the first attempt. Part 2 tests pass. But part2 input doesn't give the correct answer. Pointers to wrinkles I may have missed are most welcome.(click to show/hide)
foxed by day 8 part 2 :-\(click to show/hide)
foxed by day 8 part 2 :-\(click to show/hide)(click to show/hide)
$ cat inp | time ./12d.pl
A: *elided*
B: *elided to avoid spoilers*
0.78user 0.00system 0:00.78elapsed 100%CPU (0avgtext+0avgdata 9472maxresident)k
0inputs+0outputs (0major+631minor)pagefaults 0swaps
$ cat inp | time ./12d
A: *elided*
B: *elided to avoid spoilers*
0.00user 0.00system 0:00.00elapsed 100%CPU (0avgtext+0avgdata 2176maxresident)k
0inputs+0outputs (0major+170minor)pagefaults 0swaps
$ cat inp | ./12d 1000
*output elided to avoid spoilers*
init = 126 usec total
a = 218 usec total
calc = 8628 usec total
b = 8644 usec total
Finally completed day 10 part 2. I got stuck for a long time because I was getting the correct answer for the test case but the list of test cases only matched my output in a few places. Importantly the 200th answer in the test case was correct and when I chanced my actual input it actually delivered the correct response.
What haven't we had yet?
* Reverse engineering? (Almost certainly we'll be presented with an Intcode computer that even with the most optimal implementation will still take far too long to run in normal time, so we'll have to work out what it is doing and then optimise that)
Expecting a horror show tomorrow or Sunday though.
day 16 been grriiiiiiinnnnding away since, well, day 16. Think I might have to stop it. :-[
(I have all 250 stars, be interesting to see the stats on how many people have done that. There were 362 people with 200 stars by April 2019: https://twitter.com/ericwastl/status/1116561274379259904 )
Definitely doing something wrong as each run of my day 3 solution with the full input takes well over an hour to chug through.
Definitely doing something wrong as each run of my day 3 solution with the full input takes well over an hour to chug through.
If you can describe here in words how your algorithm works then someone here can give pointers...
Some ugly / semi-minimalist perl:-(click to show/hide)
(I know it can be code golfed to a lot less than that, but that's about as minimalist as I'd go before it starts to become a puzzle rather than recognisable code.)
Today's lesson is arrays and the modulo operator...
Day 3 done :)
I've been putting my amateur JS code efforts here: http://www.pinniped.plus.com/AoC/index.htm
Day 3 done :)
I've been putting my amateur JS code efforts here: http://www.pinniped.plus.com/AoC/index.htm
There is no source to view (firefox)
Today's lesson is arrays and the modulo operator...
Could you put hints in a Spoiler, please?
(click to show/hide)
(click to show/hide)
Still sticking with Google Sheets until they force me to stop.
Still sticking with Google Sheets until they force me to stop.
Do you have a link to your Day 1 solution?
Still sticking with Google Sheets until they force me to stop.
Do you have a link to your Day 1 solution?
He posted it elsewhere: https://docs.google.com/spreadsheets/d/1joA1oMsoGaDCwX0u8CAK7IUuMeFqyfLEYzzIWzGB1d0/edit#gid=0
Found day 4 a bit boring to be honest.
Reading arbitrary rules and writing validation code is a bit too much like actual work... :-\
Found day 4 a bit boring to be honest.
Reading arbitrary rules and writing validation code is a bit too much like actual work... :-\
(click to show/hide)
Day 5 probably the easiest spreadsheet yet:
https://docs.google.com/spreadsheets/d/1urBVcFFAz4HzJshKldFKtgobE_Zi8DGGNgY4Na5ATHw/edit?usp=sharing
Day 5 probably the easiest spreadsheet yet:
https://docs.google.com/spreadsheets/d/1urBVcFFAz4HzJshKldFKtgobE_Zi8DGGNgY4Na5ATHw/edit?usp=sharing
Day 5 probably the easiest spreadsheet yet:
https://docs.google.com/spreadsheets/d/1urBVcFFAz4HzJshKldFKtgobE_Zi8DGGNgY4Na5ATHw/edit?usp=sharing
So - your data set is different than mine - bigger even. Does that mean each participant gets their own data?
I was thinking Gödel’s incompleteness theorem and the Turing halting problem. It might inspire you to go back to your bookshelf.
I kind of like this ones.I'll usually just leave it grinding away in C++ on my old ubuntu laptop unless it's literally going to take years. :)
I end up rewriting it in something like perl and then replacing the instructions/jumps/branches with higher level constructs (while loops, for loops, etc) and then working out what the code is doing (such as painfully slowly implementing Eulers totient or phi function or similar).
I am not sure a solution that only works with a subset of the possibilities even if it happens to work for your data set is satisfactory.
I think they must deliberately generate the data to allow simpler approaches to work. Seems unnecessary to go beyond that.
It is just for fun after all.
I am not sure a solution that only works with a subset of the possibilities even if it happens to work for your data set is satisfactory.
quotebutton.
How do you do this spoiler malarkey ?[spoiler]the code[/spoiler]
Thanks. Done now. See above.How do you do this spoiler malarkey ?[spoiler]the code[/spoiler]
} while ( done = 0 )
when I mean } while ( done == 0 )
Day 9:I agree - but the fact there is a simple solution because of a quirk of the data - it would be nice if that quirk was guaranteed by the spec. It would only need one more sentence that would not really give much away.
https://docs.google.com/spreadsheets/d/1aRLwJyPDhppCY4Xuy6ciW_zAutiHcRFAGpK4CkQFyy4/edit?usp=sharing
Day 10 part 2:
https://docs.google.com/spreadsheets/d/12uXNKlJWxkxXb80ATMF3YRxS9fdXDgycL_ViGti3gu0/edit?usp=sharing
I populated the lookup tab by figuring out what numbers would make the two examples work. That was enough to make the real data work.I am not sure a solution that only works with a subset of the possibilities even if it happens to work for your data set is satisfactory.
I think they must deliberately generate the data to allow simpler approaches to work. Seems unnecessary to go beyond that.
It is just for fun after all.
Day 11 done.If you habitually write it as (0==done) then if you forget an = you get a compiler error . Personally I prefer (!done)
I keep making the mistake of writing something like:-Code: [Select]} while ( done = 0 )
when I meanCode: [Select]} while ( done == 0 )
I'll try the (0==done) route.Day 11 done.If you habitually write it as (0==done) then if you forget an = you get a compiler error . Personally I prefer (!done)
I keep making the mistake of writing something like:-Code: [Select]} while ( done = 0 )
when I meanCode: [Select]} while ( done == 0 )
As I read “!” as “not” .... while (!done) out loud is “while not done”I'll try the (0==done) route.Day 11 done.If you habitually write it as (0==done) then if you forget an = you get a compiler error . Personally I prefer (!done)
I keep making the mistake of writing something like:-Code: [Select]} while ( done = 0 )
when I meanCode: [Select]} while ( done == 0 )
Day 11 done.If you habitually write it as (0==done) then if you forget an = you get a compiler error . Personally I prefer (!done)
I keep making the mistake of writing something like:-Code: [Select]} while ( done = 0 )
when I meanCode: [Select]} while ( done == 0 )
} while ( done = 0 )
, plus a load of other warnings for things you probably need to fix too:-$ cat x.c
int main(void)
{
int x=0;
do { } while( x = 0 );
}
$ gcc x.c -o x
$ gcc -ansi -pedantic -Wall x.c -o x
x.c: In function ‘main’:
x.c:4:2: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
x.c:5:1: warning: control reaches end of non-void function [-Wreturn-type]
Day 11 Part 1 is here. It takes about 20 minutes to recalculate 100 iterations,
Really? - mine is taking about 5 seconds for 102 iterations of part one. Haven't got round to part 2 yet.
63 trillion iterations of a 100,000 by 100,000 grid might take a while.Day 11 Part 1 is here. It takes about 20 minutes to recalculate 100 iterations,
Really? - mine is taking about 5 seconds for 102 iterations of part one. Haven't got round to part 2 yet.
Really? - mine is taking about 5 seconds for 102 iterations of part one. Haven't got round to part 2 yet.
That's for a Google Sheet with two million cells running in a browser tab.
More efficient approaches are no doubt available.
So time constraints meant that I've only just completed day 11 p2.All that typing takes a while.(click to show/hide)
Code: [Select]user@cinelli ~ $ python -V
Python 2.7.6
Day 12 is oddly simple:My terse version
https://docs.google.com/spreadsheets/d/1NyEKHBwBLrFNKyLmZ63jB8CxNB6vBg3_ci3R9WBDgPM/edit?usp=sharing(click to show/hide)
Day 12 is oddly simple:I used a spreadsheet as well.
https://docs.google.com/spreadsheets/d/1NyEKHBwBLrFNKyLmZ63jB8CxNB6vBg3_ci3R9WBDgPM/edit?usp=sharing(click to show/hide)
snip
2020 day 11 done easily enough, but I haven't worked out the right trick to make it fast. (Bit busy with real work at the mo.)
Forgot the "cellular automata" item from the list of expected AoC challenges.
So time constraints meant that I've only just completed day 11 p2.All that typing takes a while.(click to show/hide)(click to show/hide)
Day 12:
I provided for calculation of arbitrary turn angles - I'm hoping tomorrow will have similar with non 90 degree turns. ;D
that is the way I am doing it (with the slight optimisation of discarding the dots from the matrix to reduce the number of elements ). It is not however an efficient way of solving the problem. You will need to get a slower computer to see the benefits.2020 day 11 done easily enough, but I haven't worked out the right trick to make it fast. (Bit busy with real work at the mo.)
Forgot the "cellular automata" item from the list of expected AoC challenges.
Really? not sure how "fast" you want it, mine takes about a seconds although that's in debug and probably includes compilation, they all take that - so I think the actual calculation, if I produced a release binary it would probably be sub-second.
my code is distinctly 'pedestrian', but reasonably efficient enough(click to show/hide)
Day 12:
I provided for calculation of arbitrary turn angles - I'm hoping tomorrow will have similar with non 90 degree turns. ;D
The reason you know it won't have is because you (probably) won't end up with integer coordinates.
Problems usually only deal in integers, full stop. They (only very occasionally) use floating point numbers, but then it will be obvious it's a "floating points" question and it will be floating points throughout.
It's very rare to have one that's mainly integers, but you might sometimes have to round off.
Day 12:
I provided for calculation of arbitrary turn angles - I'm hoping tomorrow will have similar with non 90 degree turns. ;D
Two variants then that would still be possible given care:-
a) Angles of 30, 45 or 60 degrees. You've then only got to also keep track of 1/2s, sqrt(2) and sqrt(3) as well as integers. The input would be chosen so that the end point (or answer) ends up on an integer set of co-ordinates
b) Movements along arbitrary angles that cancel out, e.g.
R47
F10
R90
F1
R90
F1
R90
F1
L90
F9
R133
Which (if I've got it right) should leave you in the initial state.
Day 12:
I provided for calculation of arbitrary turn angles - I'm hoping tomorrow will have similar with non 90 degree turns. ;D(click to show/hide)
(click to show/hide)
I seem to have smileys. How to I get rid ?
I don’t seem to have those options. I put some spaces in. Is there some [] tags you can use? Even with the extra spaces I feel I am within the 80 character limit so I can keep the source code on one punch card.I seem to have smileys. How to I get rid ?
Modify the post, expand the "Additional Options" box below it, check the "Don't use smileys" checkbox.
Yep, and so this will be one of the first days with a big drop off between 1 star and 2 stars.
As I said on our internal company #advent-of-code Slack channel, today's problem is firmly over to the right of this scale:-
<------ "Programming" ----------------- "Computer Science" ---------------- "Discrete Mathematics" ------>
There's usually a good 2 or 3 each year that require something not usually covered in general "programming" or "Comp Sci".
I don’t seem to have those options. I put some spaces in. Is there some [] tags you can use? Even with the extra spaces I feel I am within the 80 character limit so I can keep the source code on one punch card.
Does this appear as a smiley? 8)
Yep, and so this will be one of the first days with a big drop off between 1 star and 2 stars.
As I said on our internal company #advent-of-code Slack channel, today's problem is firmly over to the right of this scale:-
<------ "Programming" ----------------- "Computer Science" ---------------- "Discrete Mathematics" ------>
There's usually a good 2 or 3 each year that require something not usually covered in general "programming" or "Comp Sci".
Not sure I agree. It doesn’t require knowledge of that theorem and is quite computable with a fairly simple approach. Davef’s is a nice example of that.
We often see a similar pattern develop around the mid and later puzzles. The fastest and most experienced people spot a theory or solution from computer science or maths, share their observations on reddit. Others struggle for a bit, consult reddit, see lots of discussion on theorem X, and assume it is required for solution.
Eric is quite careful not to require such knowledge to derive a solution, even if it can help. We saw similar last year with the Slam Shuffle (day 22) that did allow solutions without detailed knowledge of modular arithmetic, even if it made spotting a solution easier.
If anyone is interested in how my simple solution to 13 day 2 works ...(click to show/hide)
The version I initially wrote sorted the numbers and worked largest first. It made little difference on the sample so I posted a simplified version.If anyone is interested in how my simple solution to 13 day 2 works ...(click to show/hide)(click to show/hide)
Sure, but my point is that in pretty much every case the solutions that people come up with (like Davef's above) are just implementing simple (and/or non-optimal) cases of the underlying theorem.
The version I initially wrote sorted the numbers and worked largest first. It made little difference on the sample so I posted a simplified version.
(click to show/hide)
(click to show/hide)(click to show/hide)
Lots of talk about theorems above, and now I've completed would be interested to learn more. Can anyone point out what theorem is applicable to day 13, and ideally a link to a primer of some sort.
If anyone is interested in how my simple solution to 13 day 2 works ...(click to show/hide)(click to show/hide)
Lots of talk about theorems above, and now I've completed would be interested to learn more. Can anyone point out what theorem is applicable to day 13, and ideally a link to a primer of some sort.
It's in this post: https://yacf.co.uk/forum/index.php?topic=94710.msg2568783#msg2568783
I did actually a version that sorted first but I stripped it out to get my solution down to 80 characters.If anyone is interested in how my simple solution to 13 day 2 works ...(click to show/hide)(click to show/hide)(click to show/hide)
Doesn’t your favourite theorem require the bus numbers to be relatively prime too ?(click to show/hide)(click to show/hide)(click to show/hide)
Doesn’t your favourite theorem require the bus numbers to be relatively prime too ?
After applying the mask, four bits are overwritten, three of which are different, and two of which are floating. Floating bits take on every possible combination of values; with two floating bits, four actual memory addresses are written:
000000000000000000000000000000011010 (decimal 26)
000000000000000000000000000000011011 (decimal 27)
000000000000000000000000000000111010 (decimal 58)
000000000000000000000000000000111011 (decimal 59)
Next, the program is about to write to memory address 26 with a different bitmask:
address: 000000000000000000000000000000011010 (decimal 26)
mask: 00000000000000000000000000000000X0XX
result: 00000000000000000000000000000001X0XX
This results in an address with three floating bits, causing writes to eight memory addresses:
000000000000000000000000000000010000 (decimal 16)
000000000000000000000000000000010001 (decimal 17)
000000000000000000000000000000010010 (decimal 18)
000000000000000000000000000000010011 (decimal 19)
000000000000000000000000000000011000 (decimal 24)
000000000000000000000000000000011001 (decimal 25)
000000000000000000000000000000011010 (decimal 26)
000000000000000000000000000000011011 (decimal 27)
The entire 36-bit address space still begins initialized to the value 0 at every address, and you still need the sum of all values left in memory at the end of the program. In this example, the sum is 208.
mask = 000000000000000000000000000000X1001X
mem[42] = 100
mask = 00000000000000000000000000000000X0XX
mem[26] = 1
My first go splurged stuff all over the place but worked. I then redid it imagining I had a quantum processor using a superposition of quantum states. I then fell back through a wormhole to day 13 part 2.Quotemask = 000000000000000000000000000000X1001X
mem[42] = 100
mask = 00000000000000000000000000000000X0XX
mem[26] = 1
The first command writes "100" to 4 different addresses. The second command writes "1" to 8 addresses, 2 of which overwrite the 100s. Therefore what's left is 2*100+8*1.
I can't see a sensible way of implementing it with a spreadsheet yet.
(click to show/hide)
Quotemask = 000000000000000000000000000000X1001X
mem[42] = 100
mask = 00000000000000000000000000000000X0XX
mem[26] = 1
The first command writes "100" to 4 different addresses. The second command writes "1" to 8 addresses, 2 of which overwrite the 100s. Therefore what's left is 2*100+8*1.
I can't see a sensible way of implementing it with a spreadsheet yet.
Quotemask = 000000000000000000000000000000X1001X
mem[42] = 100
mask = 00000000000000000000000000000000X0XX
mem[26] = 1
The first command writes "100" to 4 different addresses. The second command writes "1" to 8 addresses, 2 of which overwrite the 100s. Therefore what's left is 2*100+8*1.
I can't see a sensible way of implementing it with a spreadsheet yet.
Oh, I see...
yeah you might have to wheel a programming language out.
You can do bit operations in Google sheets. Haven’t looked at what you need to do but bit manipulation via ORs ANDs, shifts etc should not stop you using sheets.
You could have one column with memory addresses in an the values in the next. They are are just labels.You can do bit operations in Google sheets. Haven’t looked at what you need to do but bit manipulation via ORs ANDs, shifts etc should not stop you using sheets.
That's not the problem. Part 1 was straightforward enough.
The problem is storing the intermediate results of each write, and combining the overwrites to get the final total. Without hashtables or nested loops or a 2^36 array.
There's probably some clever radical simplification of the problem.
Occasionally there are 'easy' days to give people a break and let them catch up.(click to show/hide)
(click to show/hide)
$ gcc -ansi -pedantic -Wall -O4 15.c -o 15
$ time ./15 2 3 1
2020: 78
30000000: 6895259
real 0m0.813s
user 0m0.761s
sys 0m0.052s
Rewrote it in C to see how quick I could get it:-Code: [Select]$ gcc -ansi -pedantic -Wall -O4 15.c -o 15
$ time ./15 2 3 1
2020: 78
30000000: 6895259
real 0m0.813s
user 0m0.761s
sys 0m0.052s(click to show/hide)
My whopping array takes a few milliseconds
I finally wheeled out a programming language and decided to see quite how slow a naive C implementation would actually be. It's taken 45 minutes to get to 2.8 million and progress has fallen well below 1000 numbers per second.
Meanwhile I tried to use Applescript. The closest thing it has to a hashtable has keys fixed at compile time, so no good.
So in leiu of a spreadsheet or a programming language, some PHP, which does 30 million iterations in about 7 seconds:(click to show/hide)
Davef, do you want to talk us through your code a little bit? My head indirectly hurts.
Mine was specifically designed to be unreadable.I finally wheeled out a programming language and decided to see quite how slow a naive C implementation would actually be. It's taken 45 minutes to get to 2.8 million and progress has fallen well below 1000 numbers per second.
Meanwhile I tried to use Applescript. The closest thing it has to a hashtable has keys fixed at compile time, so no good.
So in leiu of a spreadsheet or a programming language, some PHP, which does 30 million iterations in about 7 seconds:(click to show/hide)
Davef, do you want to talk us through your code a little bit? My head indirectly hurts.
Here's my fast C code (it's slightly faster, and significantly more readable, than Davef's if I run both on my machine):-(click to show/hide)
I finally wheeled out a programming language and decided to see quite how slow a naive C implementation would actually be. It's taken 45 minutes to get to 2.8 million and progress has fallen well below 1000 numbers per second.Basically the same as yours but a big array instead of a dictionary And then I have pissed around to use as few characters as possible and make it as unreadable as possible!
Meanwhile I tried to use Applescript. The closest thing it has to a hashtable has keys fixed at compile time, so no good.
So in leiu of a spreadsheet or a programming language, some PHP, which does 30 million iterations in about 7 seconds:(click to show/hide)
Davef, do you want to talk us through your code a little bit? My head indirectly hurts.
I finally wheeled out a programming language and decided to see quite how slow a naive C implementation would actually be. It's taken 45 minutes to get to 2.8 million and progress has fallen well below 1000 numbers per second.
Meanwhile I tried to use Applescript. The closest thing it has to a hashtable has keys fixed at compile time, so no good.
So in leiu of a spreadsheet or a programming language, some PHP, which does 30 million iterations in about 7 seconds:(click to show/hide)
Davef, do you want to talk us through your code a little bit? My head indirectly hurts.
Here's my fast C code (it's slightly faster, and significantly more readable, than Davef's if I run both on my machine):-(click to show/hide)
In my obscure version at post 1004 above there is a ‘for’ loop after the comment that says parse inputI finally wheeled out a programming language and decided to see quite how slow a naive C implementation would actually be. It's taken 45 minutes to get to 2.8 million and progress has fallen well below 1000 numbers per second.
Meanwhile I tried to use Applescript. The closest thing it has to a hashtable has keys fixed at compile time, so no good.
So in leiu of a spreadsheet or a programming language, some PHP, which does 30 million iterations in about 7 seconds:(click to show/hide)
Davef, do you want to talk us through your code a little bit? My head indirectly hurts.
Here's my fast C code (it's slightly faster, and significantly more readable, than Davef's if I run both on my machine):-(click to show/hide)
Where I am struggling with a lot of these C implementations - I can't see where your input arrives in the code - the first 5 (or whatever) numbers.
Edit: looking at greenbanks, his input is coming in on the command line. C programs main() function are invoked with an array of arguments in char *argv[]
Once I set the same code to run to 30,000,000 numbers it was heading for all day with the computer fan running flat out, and it was slowing down.
I think you have the problem the wrong way round. It should only take 30,000,000 loopsOnce I set the same code to run to 30,000,000 numbers it was heading for all day with the computer fan running flat out, and it was slowing down.
So I've worked out that (for my data), to get to 30 million by brute force you'd need to do 71 trillion comparisons. Whereas for 1 million it only needs to do 92 billion. Which is 771, and computer science tells us that's the same as 900.
So to finish in under an hour it needs to get to a million in under 4 seconds, or 23 billion comparisons per second. It's not implausible you could get there with SIMD and/or running it on a GPU.
ETA: I've got the inner loop down to three x86 assembly instructions (load+compare, decrement pointer, conditional jump) and it still takes 45 seconds to get to a million, suggesting a 10 hour completion time. Bah.
I think you have the problem the wrong way round. It should only take 30,000,000 loops
Are you doing it with no storage then ?I think you have the problem the wrong way round. It should only take 30,000,000 loops
I have the problem the right way round, which is O(n^2), and that's how I like it. I'm trying to figure out if computers are fast enough yet to JFDI, at least for n = 30 million.
I'm storing the raw list of numbers and looking backwards until I find a matching number (or, worse, don't).Why ? The beauty of arrays is that they provide fast access via an integer key
Why ? The beauty of arrays is that they provide fast access via an integer key
Why ? The beauty of arrays is that they provide fast access via an integer key
Idle curiosity.
Clearly the question was set with the expectation that many people would create a naive O(n^2) algorithm for Part 1 and then have to replace it with something at least O(n log n) to calculate Part 2 in reasonable time. But I reckon it's possible to run an O(n^2) solution for n = 30 million in reasonable time.
$ time ./15slow 2 1 3
t=4 turn=300000
t=17 turn=600000
t=39 turn=900000
t=68 turn=1200000
t=106 turn=1500000
t=153 turn=1800000
t=208 turn=2100000
t=272 turn=2400000
t=347 turn=2700000
Have implemented what I think is the fastest O(n^2) algorithm for day 15 part 2. So far:-Code: [Select]$ time ./15slow 2 1 3
t=4 turn=300000
t=17 turn=600000
t=39 turn=900000
t=68 turn=1200000
t=106 turn=1500000
t=153 turn=1800000
t=208 turn=2100000
t=272 turn=2400000
t=347 turn=2700000
Each one of those lines represents 1% of the number of turns with the t value being the time in seconds it has been running.
Extrapolating I'd be happy if it's done in <24 hours.
[EDIT] The rate of change of the rate of change is about 10 seconds per 1%.
So extrapolating that gives 10 * 100 * 99 / 2 = 49500 seconds =~ 14h
...
t=41498 turn=28800000
t=42355 turn=29100000
t=43223 turn=29400000
t=44095 turn=29700000
I see day 17 is a 3-d Conway's Life
Have implemented what I think is the fastest O(n^2) algorithm for day 15 part 2. So far:-Code: [Select]$ time ./15slow 2 1 3
t=4 turn=300000
t=17 turn=600000
t=39 turn=900000
t=68 turn=1200000
t=106 turn=1500000
t=153 turn=1800000
t=208 turn=2100000
t=272 turn=2400000
t=347 turn=2700000
Each one of those lines represents 1% of the number of turns with the t value being the time in seconds it has been running.
Extrapolating I'd be happy if it's done in <24 hours.
[EDIT] The rate of change of the rate of change is about 10 seconds per 1%.
So extrapolating that gives 10 * 100 * 99 / 2 = 49500 seconds =~ 14h
It's exciting (and that updated prediction is looking quite accurate). Should be done inside an hour.Code: [Select]...
t=41498 turn=28800000
t=42355 turn=29100000
t=43223 turn=29400000
t=44095 turn=29700000
(The question is whether it will give the right answer! [Which should be 3544142 for the input I gave it.])
$ time ./15slow 2 1 3
t=4 turn=300000
t=17 turn=600000
t=39 turn=900000
t=68 turn=1200000
...
t=42355 turn=29100000
t=43223 turn=29400000
t=44095 turn=29700000
3544142
real 749m39.241s
user 750m18.228s
sys 0m1.734s
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int mem[30000000];
int main( int argc, char **argv) {
int turn=0;
int last=-1;
time_t start;
time(&start);
while( argv[turn+1] ) {
last=atoi(argv[turn+1]);
mem[turn]=last;
turn++;
}
while( turn < 30000000 ) {
int say=0;
int f;
if( turn % 300000 == 0 ) {
time_t now;
time(&now);
printf( "t=%d turn=%d\n", (int)(now-start), turn );
}
f=turn-2;
while( f >= 0 ) {
if( mem[f] == last )
break;
f--;
}
if( f >= 0 ) {
say = turn-f-1;
}
/* printf( "turn=%d last=%d say=%d f=%d\n", turn, last, say, f ); */
mem[turn-1]=last;
last=say;
turn++;
}
printf( "%d\n", last );
return(0);
}
Source:-Code: [Select]while( f >= 0 ) {
if( mem[f] == last )
break;
f--;
}
If you stick the value of last into mem[0] (and shuffle the other numbers up) you only need to do one comparison per loop and it will run considerably quicker. And turn and f will no longer be 1 different.
I see day 17 is a 3-d Conway's Life(click to show/hide)
So day 17:
So almost twice as fast (so far, although I don't see why that shouldn't continue). Surprised me as I would have thought the infrequent negatives would have trained the branch predictor to err on the side of looping (and then only having to occasionally buck the pipeline),
and also that it would have been mostly memory bound given the fact that a ~100MB array isn't going to be very cache friendly.
(click to show/hide)
So day 17:
That's pretty similar to mine:(click to show/hide)
I don't know if the thinning out method will always work when there is a unique solution.
Excuse my French, but Holy Hell day 18 (part 1) was a fucking BASTARD.
I could not get my head round parsing the brackets, and then calculating in parsed order.
I have to confess, 19p2 has me beat.
I'm struggling on day 19. After some effort I got an algorithm to run that produces 2^21 rules, each of 24 characters in length. The length isn't set in the algorithm, the 24 is what comes out of the data.I've just realised my counting of the matches with the messages was wrong. I've done the first part.
None of those match the messages.
I've run through the first option for each rule set and it seems to work out to the first rule that my algorithm produces.
Day 20 part 1:(click to show/hide)
(click to show/hide)
(click to show/hide)
Day 21 part 2 seemed rather trivial. Perhaps I had over-solved part 1.
Day 20 alternative input: https://gist.github.com/alexgreenbank/3a5dcb1a2854321558509247b1ed78e4
Day 20 alternative input: https://gist.github.com/alexgreenbank/3a5dcb1a2854321558509247b1ed78e4Lost on me as my solution didn’t actually rotate or stitch together the data but just kept the original data along with a list of transformations. With hindsight this was a mistake because although efficient once working it was hellish to debug. It also means I can could not visualise your data without writing some more code.
Day 22 part 1 was nice and straightforward and satisfying. Part 2 just makes my eyes glaze over.
I purposely put in just one (although the other bits of rough sea are placed at random so it another could easily appear by random) in order to be underwhelming for people who aren't printing out the final map.To make a puzzle you just start at the top left with a couple of random 10 bit numbers and then work across from there, setting the first bit of the next to be the last bit of the previous and making sure you don’t reuse a number or it’s reverse
Writing something to fake the whole input is an interesting exercise. One thing I didn't think about is that not only do the edges of adjacent tiles need to match but the 4 tiles in an inner corner all need to have the same symbol ( . or # ) at that corner, which means there's some careful selection of edge "numbers" that need to be done. Ho hum.
Day 22 part 1 was nice and straightforward and satisfying. Part 2 just makes my eyes glaze over.To see what was going on, for printing purposes I replaced the 50 odd numbers with letters A-ZA-z and ran part 1 again.
Day 22 part 1 was nice and straightforward and satisfying. Part 2 just makes my eyes glaze over.
If I had a bigger screen I would have used the proper names of the tanks from top trumps.
Day 22 part 1 was nice and straightforward and satisfying. Part 2 just makes my eyes glaze over.To see what was going on, for printing purposes I replaced the 50 odd numbers with letters A-ZA-z and ran part 1 again.
If I had a bigger screen I would have used the proper names of the tanks from top trumps.
This led to a better understanding of how to store the data and work efficiently. Then a few optimisations such as caching previous results and looking for simple cases (if there is no recursion you can see straightaway which player will win) and I left it to run on my grindingly slow laptop. It took 20 minutes which is probably 5 minutes on a decent pc. I still feel I am missing something.
(click to show/hide)
I get a lot of cache hits but I suppose it could vary with input could vary but it seems unlikely.Day 22 part 1 was nice and straightforward and satisfying. Part 2 just makes my eyes glaze over.To see what was going on, for printing purposes I replaced the 50 odd numbers with letters A-ZA-z and ran part 1 again.
If I had a bigger screen I would have used the proper names of the tanks from top trumps.
This led to a better understanding of how to store the data and work efficiently. Then a few optimisations such as caching previous results and looking for simple cases (if there is no recursion you can see straightaway which player will win) and I left it to run on my grindingly slow laptop. It took 20 minutes which is probably 5 minutes on a decent pc. I still feel I am missing something.
not seeing what the optimisation is.
Are you actually getting any cache hits?
I've implemented a cache but not getting any hits. I've checked the equality comparison and made it so that it mirrors, i.e. if player 1 won with a hand that player 2's now got, that it returns player 2 winning. But still grinding away with no cache hits.
(click to show/hide)(click to show/hide)
I get a lot of cache hits but I suppose it could vary with input could vary but it seems unlikely.Day 22 part 1 was nice and straightforward and satisfying. Part 2 just makes my eyes glaze over.To see what was going on, for printing purposes I replaced the 50 odd numbers with letters A-ZA-z and ran part 1 again.
If I had a bigger screen I would have used the proper names of the tanks from top trumps.
This led to a better understanding of how to store the data and work efficiently. Then a few optimisations such as caching previous results and looking for simple cases (if there is no recursion you can see straightaway which player will win) and I left it to run on my grindingly slow laptop. It took 20 minutes which is probably 5 minutes on a decent pc. I still feel I am missing something.
not seeing what the optimisation is.
Are you actually getting any cache hits?
I've implemented a cache but not getting any hits. I've checked the equality comparison and made it so that it mirrors, i.e. if player 1 won with a hand that player 2's now got, that it returns player 2 winning. But still grinding away with no cache hits.
The other optimisation is based on the top trump killer card theorem I just made up. There are scenarios where you can see who will win without actually playing. The other optimisation was how to store the data so that each iteration was very efficient.
Not sure what optimisations are required if you implement it as it says. Mine completes in ~5 seconds even with a relatively naive perl implementation. The only caching I do is to prevent it repeating a hand-state as per the instructions, and that's just per game.
My input meant I processed somewhere under 20,000 games and 2.1 million rounds in total.
Early on I forgot to truncate the decks for the sub-games and that meant it had no chance of returning before the heat death of the universe. Sure you aren't doing the same?
Day 25. I get an answer which passes the test case and meets all the criteria but its not the correct answer!!(click to show/hide)
My list copying is minimal as I have each players hand as string. The game state is the two strings concatenated with an * in between.Not sure what optimisations are required if you implement it as it says. Mine completes in ~5 seconds even with a relatively naive perl implementation. The only caching I do is to prevent it repeating a hand-state as per the instructions, and that's just per game.
My input meant I processed somewhere under 20,000 games and 2.1 million rounds in total.
Early on I forgot to truncate the decks for the sub-games and that meant it had no chance of returning before the heat death of the universe. Sure you aren't doing the same?
initially, yes, but have changed it to truncate now and doesn't seem any faster.
It seems to get more 'repeats' per 1,000 games than when it didn't truncate.
It's actually a lot slower per 1,000 games but I was hoping that it would mean there would be fewer to go through in total.
My only thought is it could be the list copying in order to keep the state after a sub game as it was when the subgame started that's slowing it down every time.
Day 25. I get an answer which passes the test case and meets all the criteria but its not the correct answer!!If you look at the Wikipedia articule on modular arithmetic https://en.wikipedia.org/wiki/Modular_arithmetic there is an efficient c routine for raising a to the power of b. I still had a copy from last year. That said it would would be relatively quick without it.(click to show/hide)
I did have another optimisation that gave an answer in fractions of a second. Unfortunately the wrong answer. It is has been bothering me why it didn’t work and I just realised so I now have a solution that only takes a few seconds.Not sure what optimisations are required if you implement it as it says. Mine completes in ~5 seconds even with a relatively naive perl implementation. The only caching I do is to prevent it repeating a hand-state as per the instructions, and that's just per game.
My input meant I processed somewhere under 20,000 games and 2.1 million rounds in total.
Early on I forgot to truncate the decks for the sub-games and that meant it had no chance of returning before the heat death of the universe. Sure you aren't doing the same?
initially, yes, but have changed it to truncate now and doesn't seem any faster.
It seems to get more 'repeats' per 1,000 games than when it didn't truncate.
It's actually a lot slower per 1,000 games but I was hoping that it would mean there would be fewer to go through in total.
My only thought is it could be the list copying in order to keep the state after a sub game as it was when the subgame started that's slowing it down every time.
I did have another optimisation that gave an answer in fractions of a second. Unfortunately the wrong answer. It is has been bothering me why it didn’t work and I just realised so I now have a solution that only takes a few seconds.Not sure what optimisations are required if you implement it as it says. Mine completes in ~5 seconds even with a relatively naive perl implementation. The only caching I do is to prevent it repeating a hand-state as per the instructions, and that's just per game.
My input meant I processed somewhere under 20,000 games and 2.1 million rounds in total.
Early on I forgot to truncate the decks for the sub-games and that meant it had no chance of returning before the heat death of the universe. Sure you aren't doing the same?
initially, yes, but have changed it to truncate now and doesn't seem any faster.
It seems to get more 'repeats' per 1,000 games than when it didn't truncate.
It's actually a lot slower per 1,000 games but I was hoping that it would mean there would be fewer to go through in total.
My only thought is it could be the list copying in order to keep the state after a sub game as it was when the subgame started that's slowing it down every time.
Your computer is faster than my old laptop.I did have another optimisation that gave an answer in fractions of a second. Unfortunately the wrong answer. It is has been bothering me why it didn’t work and I just realised so I now have a solution that only takes a few seconds.Not sure what optimisations are required if you implement it as it says. Mine completes in ~5 seconds even with a relatively naive perl implementation. The only caching I do is to prevent it repeating a hand-state as per the instructions, and that's just per game.
My input meant I processed somewhere under 20,000 games and 2.1 million rounds in total.
Early on I forgot to truncate the decks for the sub-games and that meant it had no chance of returning before the heat death of the universe. Sure you aren't doing the same?
initially, yes, but have changed it to truncate now and doesn't seem any faster.
It seems to get more 'repeats' per 1,000 games than when it didn't truncate.
It's actually a lot slower per 1,000 games but I was hoping that it would mean there would be fewer to go through in total.
My only thought is it could be the list copying in order to keep the state after a sub game as it was when the subgame started that's slowing it down every time.
hmm, weird. Rewrote it in c++ and it gets the correct answer in under a second, with about 14,000 games. No idea what the previous program was doing.
For day 23 part 2 my program produces the right numbers for the example input 389125467 => (934001 x 159792 = 149245887792)Your puzzle answer was 412990492266.
but wrong for my actual input.
Bloody annoying.
Definitely not overflown as I've converted to 64 bit numbers before making the product.
Struggling to see how it would be right for the example but wrong for my actual.
Would anyone who's got it right mind posting their input and the two numbers clockwise from 1 please and the product?
Runs in a second or two so easy for me to check
Weird. My code gets the right answer for your input.For day 23 part 2 my program produces the right numbers for the example input 389125467 => (934001 x 159792 = 149245887792)Your puzzle answer was 412990492266.
but wrong for my actual input.
Bloody annoying.
Definitely not overflown as I've converted to 64 bit numbers before making the product.
Struggling to see how it would be right for the example but wrong for my actual.
Would anyone who's got it right mind posting their input and the two numbers clockwise from 1 please and the product?
Runs in a second or two so easy for me to check
Both parts of this puzzle are complete! They provide two gold stars: **
At this point, all that is left is for you to admire your Advent calendar.
Your puzzle input was 963275481.
You could also test your input against my code posted a few posts above #1103
The only bit that needed 64 bit was the final multiply
Your puzzle answer was 412990492266.Weird. My code gets the right answer for your input.
Both parts of this puzzle are complete! They provide two gold stars: **
At this point, all that is left is for you to admire your Advent calendar.
Your puzzle input was 963275481.
You could also test your input against my code posted a few posts above #1103
The only bit that needed 64 bit was the final multiply
Got it now, thanks davef - was a bug in setting up the initial data.QuoteYour puzzle answer was 412990492266.Weird. My code gets the right answer for your input.
Both parts of this puzzle are complete! They provide two gold stars: **
At this point, all that is left is for you to admire your Advent calendar.
Your puzzle input was 963275481.
You could also test your input against my code posted a few posts above #1103
The only bit that needed 64 bit was the final multiply
But still claims to be wrong for my own. Oh well, I'll give your code a compile and see what it gets...
Was using a linked list and wasn't setting up the initial data correctly, so if the input was 315679824, I was setting e.g. 2.next = 4, and 4.prev = 2, and setting 4's next to 10.... but forgot to set 10's prev to 4.
Might try and create a generic linked list class, as the code is a bit of a mess and a pita to debug.
Implemented day 25 properly and got the time down to 1189usec for my input.It is a flawed security system if it can be broken by some arithmetic !
It finds the answer for the example input in 102usec.
(Note usec not msec. 1189usec is ~1.2msec.)
Late to it today as I'd been out all day at a family party. Chased a few silly bugs in a dreadful implementation but got it done.
The way I'd implemented meant it was only a very small change required to do part 2.
Loving the use of IntCode computers to provide inputs (i.e. the maze) that can't be analysed directly.(click to show/hide)
Implemented day 25 properly and got the time down to 1189usec for my input.It is a flawed security system if it can be broken by some arithmetic !
It finds the answer for the example input in 102usec.
(Note usec not msec. 1189usec is ~1.2msec.)
Can't see it mentioned anywhere but there's Project Euler too, for anyone wanting to continue with problems throughout the year.
I've made a thread for it here: https://yacf.co.uk/forum/index.php?topic=117960.0 so not to clutter up this one (which we can save for AoC).
Day 17 (2019). Another example of READ THE TEXT, then READ IT AGAIN.
The "obvious" route, of going straight across each intersection, might have led to a final set of instructions that could not be compressed to fit the input instruction rules.
Having to then go back and make the first part of part 2 output every possible permutation until one that could be compressed adequately would have been less fun.
Day 6(click to show/hide)
Day 6(click to show/hide)(click to show/hide)
Day 6(click to show/hide)(click to show/hide)(click to show/hide)
Day 8Day 6(click to show/hide)(click to show/hide)(click to show/hide)
My day job tends to call on that kind of optimization, so i had a similar predisposition :)
In contrast, my solution for today's feels quite clunky. Though coding before coffee might be an issue.
Day 6(click to show/hide)(click to show/hide)(click to show/hide)
My day job tends to call on that kind of optimization, so i had a similar predisposition :)
In contrast, my solution for today's feels quite clunky. Though coding before coffee might be an issue.
Day 14(click to show/hide)
twinBASIC is an exciting new project that aims to provide a full replacement IDE and compiler for VB6
Well day 9 pt 2 got me. The test data got the right answer, and printing out the visited points exactly matched the example, but the final answer was wrong. Only comparing the intermediates showed that I'd misunderstood the rules.I had the same.
Bah! This is not the first one this year where the tests have passed for the wrong implementation.
Advent of code 2023 has started.
Day 1(click to show/hide)
That was a bit sneaky for a day 1. Depending on your approach it would have been quite easy to pass a test on the sample but get the wrong answer on the puzzle.Only for part 2, but yes, the sample was no help at all for the difference between part 2 and part 1
I see quite a few people in the private leaderboard haven't bothered completing part 2 yet.Part 2 needs to detect several characters to get a match, while part one only needs to detect a single character.
Only for part 2, but yes, the sample was no help at all for the difference between part 2 and part 1
Advent of code 2023 has started.
Day 1(click to show/hide)
Yes, spotted the range thing later.jwo posted while I was writing this.
Day 6 was a bit easy(click to show/hide)
Pickled O: I'm not really familiar with C#. What does Select(x=> x.Ways()) do?
Day 10 part 2:-(click to show/hide)
Day 18
Total time for 2023 so far (up to and including day 18) is 0.378s, so still a few left to optimise (days 17, 16, and 14 take the longest).
a mixture of shell, C and predominantly perl. Now most of my professional coding is in Go
Wot Greenbank sed.
For me, over the years I've used AoC to improve my skills in Java, Elm, JavaScript and C++ as well as general data structures and algorithm competence. I also use it with students (from first year undergraduates to PhDs) to help them develop their algorithmic thinking, reasoning and communication. I didn't do a Comp Sci or Maths degree so AoC has been useful learning tool for me (and mostly fun).
a mixture of shell, C and predominantly perl. Now most of my professional coding is in Go
Same here