{"id":2757,"date":"2021-01-02T13:00:00","date_gmt":"2021-01-02T13:00:00","guid":{"rendered":"https:\/\/chewett.co.uk\/blog\/?p=2757"},"modified":"2021-01-02T11:06:08","modified_gmt":"2021-01-02T11:06:08","slug":"advent-of-code-2020-review","status":"publish","type":"post","link":"https:\/\/chewett.co.uk\/blog\/2757\/advent-of-code-2020-review\/","title":{"rendered":"Advent of Code 2020 Review"},"content":{"rendered":"\n
\"\"<\/figure>\n\n\n\n

Today I am talking about the Advent of Code 2020 and what I have learnt doing it this year.<\/p>\n\n\n\n\n\n\n\n

Advent of Code 2020<\/h2>\n\n\n\n

Advent of Code<\/a> is a set of programming puzzles with one problem released each day during Advent. Each problem has two parts, the second normally being an expansion on the first.<\/p>\n\n\n\n

For most of this year, the second problem expands the first by making it infeasible to brute-force the solution and requires clever algorithm design or datastructures. All problems should be able to run within a few seconds as long as your solution is somewhat efficient.<\/p>\n\n\n\n

Like last year I participated in the Advent of code and thoroughly enjoyed it. This year it provided a similar level of challenge while keeping the problems interesting and fun to work on.<\/p>\n\n\n\n

This year two of the highlights were implementing a linked list (not something I have done since University) and learning about the Chinese Remainder theorem.<\/p>\n\n\n\n

Implemented a linked list<\/h3>\n\n\n\n

One of the problems required moving segments of an array around and inserting it into other positions in the array. Originally I was using an array and re-composing it every time I needed to slice and move the elements. This worked for the smaller part one but for part two it was too slow.<\/p>\n\n\n\n

In addition to the slowness of re-creating the array, part of the problem required you to find a specific entry in the array. This meant that you were a O(n) search every loop iteration which was slowing down my solution.<\/p>\n\n\n\n

Initially I was going to use a Java linked list however I encounted some issues with it. The main one was that it isn’t a “true” linked list implementation. Since it is generic it doesn’t provide any methods to move the tail pointer to another element and “quickly” alter the list.<\/p>\n\n\n\n

By implementing a simple linked list this allowed me to have custom methods to slice out a set of elements and insert them anywhere just updating the tail pointers of the involved elements.<\/p>\n\n\n\n

It was a fun little challenge which sped up the problem considerably and reminded me of the benefits of understanding your data structures.<\/p>\n\n\n\n

Chinese Remainder Theorem<\/h3>\n\n\n\n

The Chinese remainder theorem is not something I had previously read about in my number theory work. For one of the days it was noted as a possible solutions instead of brute forcing the solution (which depending on your solution might take days). My initial solution unoptimized solution was going to take a couple days to solve the problem.<\/p>\n\n\n\n

Reading up on the theorem<\/a> proved interesting as it was able to be used as Advent of Code had helpfully ensured all numbers were pairwise coprime. This allowed solving it relatively quickly as it is one of the requirements of using it.<\/p>\n\n\n\n

As with all Advent of Code problems, using this required a little manipulation of the problem but once done the solution was pretty quick to implement.<\/p>\n\n\n\n

Personal Stats<\/h2>\n\n\n\n

This year I managed to finish most puzzles by the end of each day. Over time as the puzzles increased in complexity I was no longer able to complete them before work and instead did them during lunch or after work.<\/p>\n\n\n\n

<\/td>Part 1<\/em><\/td><\/td>Part 2<\/em><\/td><\/td><\/tr>
Day<\/strong><\/td>Time<\/strong><\/td>Rank<\/strong><\/td>Time<\/strong><\/td>Rank<\/strong><\/td><\/tr>
25<\/td>>24h<\/td>12028<\/td>>24h<\/td>8983<\/td><\/tr>
24<\/td>09:40:33<\/td>9306<\/td>10:12:32<\/td>8098<\/td><\/tr>
23<\/td>16:27:38<\/td>11842<\/td>18:39:33<\/td>8776<\/td><\/tr>
22<\/td>15:28:39<\/td>14006<\/td>18:07:56<\/td>11522<\/td><\/tr>
21<\/td>>24h<\/td>13068<\/td>>24h<\/td>12838<\/td><\/tr>
20<\/td>11:03:32<\/td>8161<\/td>15:06:20<\/td>4551<\/td><\/tr>
19<\/td>12:24:15<\/td>10415<\/td>14:49:24<\/td>8442<\/td><\/tr>
18<\/td>13:05:28<\/td>15086<\/td>18:10:58<\/td>15560<\/td><\/tr>
17<\/td>13:36:03<\/td>14385<\/td>14:08:18<\/td>13796<\/td><\/tr>
16<\/td>12:48:24<\/td>19872<\/td>16:34:40<\/td>17374<\/td><\/tr>
15<\/td>14:41:00<\/td>22592<\/td>14:42:57<\/td>20548<\/td><\/tr>
14<\/td>03:54:35<\/td>10759<\/td>15:23:43<\/td>18138<\/td><\/tr>
13<\/td>07:43:35<\/td>20453<\/td>10:33:59<\/td>12396<\/td><\/tr>
12<\/td>05:49:53<\/td>15215<\/td>06:47:20<\/td>13700<\/td><\/tr>
11<\/td>03:39:10<\/td>11740<\/td>04:06:21<\/td>9322<\/td><\/tr>
10<\/td>03:25:26<\/td>17566<\/td>12:32:58<\/td>21742<\/td><\/tr>
9<\/td>02:54:49<\/td>15600<\/td>03:04:23<\/td>14076<\/td><\/tr>
8<\/td>04:16:49<\/td>20703<\/td>05:10:44<\/td>18689<\/td><\/tr>
7<\/td>05:25:59<\/td>17473<\/td>05:51:41<\/td>14514<\/td><\/tr>
6<\/td>03:59:15<\/td>18884<\/td>04:04:30<\/td>17054<\/td><\/tr>
5<\/td>05:15:30<\/td>20994<\/td>05:18:31<\/td>19532<\/td><\/tr>
4<\/td>03:40:47<\/td>20678<\/td>03:59:20<\/td>14769<\/td><\/tr>
3<\/td>03:46:47<\/td>21022<\/td>03:53:13<\/td>19277<\/td><\/tr>
2<\/td>02:36:21<\/td>14321<\/td>02:42:47<\/td>13419<\/td><\/tr>
1<\/td>16:49:51<\/td>61909<\/td>16:53:57<\/td>57241<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Final Comments<\/h2>\n\n\n\n

Again this has been an incredibly enjoyable experience working on the problems. Part 1 is normally simple enough to quickly code a solution which part two typically requiring optimisation of your solution.<\/p>\n\n\n\n

I highly recommend trying Advent of Code as the puzzles are novel and allow you to learn about optimisation of problems. Part one is normally simple enough for someone learning to program and then offers <\/p>\n\n\n\n

In addition to being fun, the community around Advent of Code also are very happy to help out and discuss the problem. This means you can read about other peoples solutions and get help if you are stuck.<\/p>\n\n\n\n

All my code for this year and previous years is on Github so feel free to have a look through how I solved the problems.<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Today I am talking about the Advent of Code 2020 and what I have learnt doing it this year.<\/p>\n","protected":false},"author":1,"featured_media":2762,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"Today I talk about my #AdventOfCode 2020 Review and the fun I had solving the problems!","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[5],"tags":[362,395],"class_list":["post-2757","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-informational","tag-advent-of-code","tag-logic-puzzles"],"wppr_data":{"cwp_meta_box_check":"No"},"jetpack_publicize_connections":[],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2020\/12\/advent_of_code_2020_OUTPUT.png?fit=1161%2C618&ssl=1","jetpack_shortlink":"https:\/\/wp.me\/p2toWX-It","jetpack_sharing_enabled":true,"jetpack-related-posts":[{"id":2375,"url":"https:\/\/chewett.co.uk\/blog\/2375\/im-participating-in-advent-of-code-2019\/","url_meta":{"origin":2757,"position":0},"title":"I’m Participating in Advent of Code 2019","author":"Chewett","date":"December 14, 2019","format":false,"excerpt":"This post talks about my participation in the Advent of Code competition 2019. What is Advent of Code Advent of code is a set of programming puzzles that slowly increase in complexity. Every day during advent a new puzzle is released which has two parts. The first part is typically\u2026","rel":"","context":"In "Informational"","block_context":{"text":"Informational","link":"https:\/\/chewett.co.uk\/blog\/category\/informational\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/12\/advent_of_code_2019-1.jpg?fit=800%2C800&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/12\/advent_of_code_2019-1.jpg?fit=800%2C800&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/12\/advent_of_code_2019-1.jpg?fit=800%2C800&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/12\/advent_of_code_2019-1.jpg?fit=800%2C800&ssl=1&resize=700%2C400 2x"},"classes":[]},{"id":2267,"url":"https:\/\/chewett.co.uk\/blog\/2267\/creating-a-talos-principle-puzzle-solver\/","url_meta":{"origin":2757,"position":1},"title":"Creating a Talos Principle Puzzle Solver","author":"Chewett","date":"July 6, 2019","format":false,"excerpt":"This blog post talks about the Talos Principle puzzle solver I wrote to help solve the Sigil puzzles. The game \"The Talos Principle\" has points where you need to place a series of Tetris pieces, called sigils in the game, onto a puzzle board to move onto the next area.\u2026","rel":"","context":"In "Software"","block_context":{"text":"Software","link":"https:\/\/chewett.co.uk\/blog\/category\/software\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/07\/talos_principle_solver.jpg?fit=800%2C800&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/07\/talos_principle_solver.jpg?fit=800%2C800&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/07\/talos_principle_solver.jpg?fit=800%2C800&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/07\/talos_principle_solver.jpg?fit=800%2C800&ssl=1&resize=700%2C400 2x"},"classes":[]},{"id":689,"url":"https:\/\/chewett.co.uk\/blog\/689\/common-cathode-rgb-led-review-code-examples\/","url_meta":{"origin":2757,"position":2},"title":"Common Cathode RGB LED Review and Code examples","author":"Chewett","date":"October 7, 2017","format":false,"excerpt":"Today I am reviewing a basic RGB LED. This includes schematics for using it with an Arduino and code examples. What can the RGB Light Emitting Diode Do The RGB common cathode light emitting diode works just like a standard LED but there is one small difference. Instead of having\u2026","rel":"","context":"In "Electronics"","block_context":{"text":"Electronics","link":"https:\/\/chewett.co.uk\/blog\/category\/electronics\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2017\/10\/post_icon_rgb.jpg?fit=800%2C800&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2017\/10\/post_icon_rgb.jpg?fit=800%2C800&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2017\/10\/post_icon_rgb.jpg?fit=800%2C800&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2017\/10\/post_icon_rgb.jpg?fit=800%2C800&ssl=1&resize=700%2C400 2x"},"classes":[]},{"id":881,"url":"https:\/\/chewett.co.uk\/blog\/881\/raspberry-pi-cluster-node-02-packaging-common-functionality\/","url_meta":{"origin":2757,"position":3},"title":"Raspberry Pi Cluster Node \u2013 02 Packaging common functionality","author":"Chewett","date":"November 29, 2017","format":false,"excerpt":"This post builds on the first step to create a Raspberry Pi Cluster node to package the common functionality that will be shared between master and clients. Packaging common functionality With the Raspberry Pi Cluster project there will be a number of things all nodes will do. This can lead\u2026","rel":"","context":"In "Raspberry Pi Cluster"","block_context":{"text":"Raspberry Pi Cluster","link":"https:\/\/chewett.co.uk\/blog\/category\/raspberry-pi-cluster\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2017\/11\/rpi_cluster_02_packaging.jpg?fit=800%2C800&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2017\/11\/rpi_cluster_02_packaging.jpg?fit=800%2C800&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2017\/11\/rpi_cluster_02_packaging.jpg?fit=800%2C800&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2017\/11\/rpi_cluster_02_packaging.jpg?fit=800%2C800&ssl=1&resize=700%2C400 2x"},"classes":[]},{"id":558,"url":"https:\/\/chewett.co.uk\/blog\/558\/ttp223b-capacitive-touch-sensor-review-code\/","url_meta":{"origin":2757,"position":4},"title":"TTP223B Capacitive Touch Sensor Review and Code","author":"Chewett","date":"September 13, 2017","format":false,"excerpt":"The TTP223B Capacitive touch sensor is a button type sensor that allows you to detect when it is being pressed. In this post I review the sensor and provide code and a wiring diagram to use such a sensor. What can a Capacitive Touch Sensor do? The sensor is essentially\u2026","rel":"","context":"In "Electronics"","block_context":{"text":"Electronics","link":"https:\/\/chewett.co.uk\/blog\/category\/electronics\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2017\/08\/TTP223B_touch_sensor_article_image.jpg?fit=800%2C800&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2017\/08\/TTP223B_touch_sensor_article_image.jpg?fit=800%2C800&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2017\/08\/TTP223B_touch_sensor_article_image.jpg?fit=800%2C800&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2017\/08\/TTP223B_touch_sensor_article_image.jpg?fit=800%2C800&ssl=1&resize=700%2C400 2x"},"classes":[]},{"id":2680,"url":"https:\/\/chewett.co.uk\/blog\/2680\/raspberry-pi-cluster-node-16-python-3-codebase-refactor\/","url_meta":{"origin":2757,"position":5},"title":"Raspberry Pi Cluster Node \u2013 16 Python 3 Codebase Refactor","author":"Chewett","date":"October 24, 2020","format":false,"excerpt":"This post builds on\u00a0my previous posts in the Raspberry Pi Cluster series\u00a0by improving the codebase for Python 3. Moving to Python 3 Python 2 was marked end of life on January 1st, 2020 and therefore applications should ideally be no longer using Python 2. There will still be a lot\u2026","rel":"","context":"In "Raspberry Pi Cluster"","block_context":{"text":"Raspberry Pi Cluster","link":"https:\/\/chewett.co.uk\/blog\/category\/raspberry-pi-cluster\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2020\/10\/raspi_cluster_16_python3refactor_posticon_OUTPUT.png?fit=1200%2C628&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2020\/10\/raspi_cluster_16_python3refactor_posticon_OUTPUT.png?fit=1200%2C628&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2020\/10\/raspi_cluster_16_python3refactor_posticon_OUTPUT.png?fit=1200%2C628&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2020\/10\/raspi_cluster_16_python3refactor_posticon_OUTPUT.png?fit=1200%2C628&ssl=1&resize=700%2C400 2x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2020\/10\/raspi_cluster_16_python3refactor_posticon_OUTPUT.png?fit=1200%2C628&ssl=1&resize=1050%2C600 3x"},"classes":[]}],"_links":{"self":[{"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/posts\/2757","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/comments?post=2757"}],"version-history":[{"count":6,"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/posts\/2757\/revisions"}],"predecessor-version":[{"id":2765,"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/posts\/2757\/revisions\/2765"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/media\/2762"}],"wp:attachment":[{"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/media?parent=2757"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/categories?post=2757"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/tags?post=2757"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}