Skip to content

Instantly share code, notes, and snippets.

@jaroslawjanas

jaroslawjanas/aoc-2023-day-3.ipynb

Created December 9, 2023 02:32
Show Gist options
  • Save jaroslawjanas/2d8bf44532796e5f95f1de7b9c42c116 to your computer and use it in GitHub Desktop.
Save jaroslawjanas/2d8bf44532796e5f95f1de7b9c42c116 to your computer and use it in GitHub Desktop.
Download ZIP
AoC 2023 - Day 3.ipynb
Display the source blob
Display the rendered blob
Raw
aoc-2023-day-3.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"provenance": [],
"toc_visible": true,
"authorship_tag": "ABX9TyP4l94KuFTJyVt6RHzoL8Lt",
"include_colab_link": true
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
},
"language_info": {
"name": "python"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "view-in-github",
"colab_type": "text"
},
"source": [
"<a href=\"https://colab.research.google.com/gist/jaroslawjanas/2d8bf44532796e5f95f1de7b9c42c116/aoc-2023-day-3.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
]
},
{
"cell_type": "markdown",
"source": [
"# Advent of Code 2023"
],
"metadata": {
"id": "MC7RbRHFJeBz"
}
},
{
"cell_type": "markdown",
"source": [
"# Puzzle - part 1\n",
"\n",
"**--- Day 3: Gear Ratios ---**\n",
"\n",
"You and the Elf eventually reach a **gondola lift** station; he says the gondola lift will take you up to the **water source**, but this is as far as he can bring you. You go inside.\n",
"\n",
"It doesn't take long to find the gondolas, but there seems to be a problem: they're not moving.\n",
"\n",
"_\"Aaah!\"_\n",
"\n",
"You turn around to see a slightly-greasy Elf with a wrench and a look of surprise. _\"Sorry, I wasn't expecting anyone! The gondola lift isn't working right now; it'll still be a while before I can fix it.\"_ You offer to help.\n",
"\n",
"The engineer explains that an engine part seems to be missing from the engine, but nobody can figure out which one. If you can **add up all the part numbers** in the engine schematic, it should be easy to work out which part is missing.\n",
"\n",
"The engine schematic (your puzzle input) consists of a visual representation of the engine. There are lots of numbers and symbols you don't really understand, but apparently **any number adjacent to a symbol**, even diagonally, is a \"part number\" and should be included in your sum. (Periods (`.`) do not count as a symbol.)\n",
"\n",
"Here is an example engine schematic:\n",
"\n",
"```\n",
"467..114..\n",
"...*......\n",
"..35..633.\n",
"......#...\n",
"617*......\n",
".....+.58.\n",
"..592.....\n",
"......755.\n",
"...$.*....\n",
".664.598..\n",
"```\n",
"\n",
"In this schematic, two numbers are not part numbers because they are not adjacent to a symbol: `114` (top right) and `58` (middle right). Every other number is adjacent to a symbol and so is a part number; their sum is `4361`.\n",
"\n",
"Of course, the actual engine schematic is much larger.\n",
"\n",
"**What is the sum of all of the part numbers in the engine schematic?**"
],
"metadata": {
"id": "dY39ti5IJ4u9"
}
},
{
"cell_type": "markdown",
"source": [
"## Input"
],
"metadata": {
"id": "Svtn1_7KKXyH"
}
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"id": "C-ZQZ0GkJZE6"
},
"outputs": [],
"source": [
"txt_input = \\\n",
"\"\"\".479........155..............944.....622..............31.........264.......................532..........................254.........528.....\n",
"..............-...............%.....+...................=....111*.................495.......+.......558..................../..........*.....\n",
"....................791*..62.....$.............847........&........-..........618.*...........818....&..642.........................789.....\n",
"....520.58......405......#....542.../587.............*....198.......846.........*..............*.......*....................647.............\n",
".........*........./.964..........................474.302.....................786...43..............505..436...................*.....#51....\n",
"......832....@..........*.951*....984*111..801................../.....................-.......@............%.198......322.186...262.........\n",
"..........490........690......346.........................702&.566.%....................192...190.87............*.....-....=..%.........344.\n",
"....*.........................................816*588..............152..535................*.......*...........425...........53.............\n",
"..36.290.831....374................579.536.....................408.......*..733....998....169...146.....%179..........658...............260.\n",
"...........+..../...........795/.....*.*.....................%........776......*..............................790.871./.............281*....\n",
"....................78.............716..400....319........167.................399..@.............................*.........$...599..........\n",
"............719.......*........640................%..376...............800........211......#478......326*93........889..684....*.....285....\n",
".....852.......-.......462..................374/....%..................*........$..............................603..*..........369..&.......\n",
"[email protected]..................................*...........966.321...925............926...................*.947..&.............574..\n",
"..............%.....$.........$......*.......479....909.339..........*..............803........*17......284$...657.......587......*.........\n",
"...........772............&....345..93...465*................419......676...............-.@521.....-...........................399.662......\n",
".................17+..2..531.......................79........*...589......198*734....534.........614..................109...................\n",
".......301............=............................&..321..895..*..........................344.................694............717...511*....\n",
"..........%...707*370.....................473.428........*.....509......=889.....353%.........*................*.......299.......*..........\n",
"........................973.....................*.......877............................&[email protected]..\n",
"................314....*....504*352........602...468..............688.....10-....................#.......*...........306*.............*.....\n",
".....................987.......................5.............811..*...../.......515..217...........705....462..880.......374......16...42...\n",
"....#......402.$............804..295...406.....&..150........*....22..429...268............324........-.....................................\n",
".....270..*.....982...644.../.....+....*.........%.............................-..........#.............-...87.......................505....\n",
"938.................=...*.....=98.......370................19@[email protected]...*......760.......627.#...*......\n",
"..........593.....793....503.........34...............................406.....456...............+.........303........*...........142.432....\n",
"...........*..........&........707..*................563.....837.........+......*.....230..169.......................138....420.............\n",
"..572....689..........503.......#...................*...........*449..........39.........*./......77.......%....404......#..$............739\n",
"...............137...................#.....624.....883..../[email protected].*.....404...................\n",
"...287.......*..%............*[email protected]$................$.......531.72.......424............766..........\n",
"...*......476......316....722............780........613........../533...............96......553.91*......*.835*........*690...*.............\n",
".350...........%...............470.950...*.............*......................%.....*...728............359.....141..326.......658..832...330\n",
"..........772...127..................-...335......./...539........362......101.....959.............221..................512.........*.......\n",
"..........*..........798.......138..............207.....................................999...574.....*..........484....&............364....\n",
"[email protected].........*......*.....202.971...............488.................@349........*......*..........404...=........&..448..$........\n",
".....246........211...426......206...*.....*557..........*[email protected]...*..........583.....*..280.....\n",
"...........724.....*......324*.....788..........685....788......@........*....532.................85.......*.139....75.........196..........\n",
"[email protected]................./[email protected]...*.....................*810.214........*.....-........490......\n",
"......................................&....679.........776....447...457......25..............................467..173....241................\n",
"................43........898.412...742......%....*540.*.............*..............825..259...997.514.........*............................\n",
".......%775..52*...........*..*.........809....871.....384.....295..470............$.......-.....*....*..&.....114.....................=....\n",
"...147...........69=...........914..144*....=..............%.....*......$875.....+............=......278.441.........859.346.281........40..\n",
"......*....................-...............89...........578....519.............676..........473..361..................*....*..+.............\n",
"..78+..42......$...750..465.....218...833.......137...=.............538.783...........*962.........*............*...421.502....../..42......\n",
"..............457.....*.........+........*.....*....825.....26*....-.........238...205.....539.109.348........837..............842...*......\n",
"........#..............175..............925....399.............560.......88.*..............*.....*.................................636......\n",
"......693.......................447.................137............-679......479........619...283...............$458.544.-802.848@..........\n",
"...%.........................&...$....&.+39............*.........................%..618..................*141........+......................\n",
"....471...502....252....663..986...633..............530..117............598.....220...................542......568.......#219..532..15......\n",
".........*.....-........-...........................................840.$.............717..$...................../............#......*......\n",
".......351......993......................................573...865...*....$......848.......239.....134....826........409..338...$64..231....\n",
"...........................................=...809.925..*.........*[email protected].=........................................\n",
"..........+698..355.....-...594....%...#.55.......*......847..409...............@...............*.....*78..........................#363.497.\n",
"...................#..261.......591..695....-....................=.....678.......714.......364.804.156...................676...605..........\n",
"587.881.....356............192.............957...963.447.................#...63.............*................344.....373........*...........\n",
"..................524..568....&...691...........*.......*...169*218..10....................10.........399.46*............../488.491.16......\n",
"[email protected]..$.....&..........*.265...............964............#...............................*........359...556............=.897..\n",
".............*................293.345.*...161*.....................671.............%414.726.347.....564....................420..............\n",
".............155.......483....................546........-.....794....*......968.........*...............591.......................$........\n",
".....806.../.......120.*.......813....................481...........593.........*....667.815.....682........*.%579.......#298....668.188....\n",
".......*.718.......*....469...*.........251...52*919.......846..................887....*......../........637...........................*....\n",
".....81.......132.51..........236........-................*.......$.167....338......963..258......844.........884.......*980........#...816.\n",
"..........475.........150..........316........389......590......291..-.....*....662......*...........................143..........284.......\n",
".......................&.......*..*....390.......+.559..................116.............926........779..................................233.\n",
"500...%......................821..594....*.........*................220...........830*...............*..........89...915.......230.363......\n",
"...*...623....337.......................40..........827..............*................828....$294....392....*....*.....%..............*.....\n",
".993............*....565........................638...............307.............95.......#..............535.105.........632..938.166..$939\n",
"[email protected]...*.......4...283...971@.......*...................689..937...*[email protected]..@....*...........\n",
"....639....../.....886...........*..............668...88........472...+...*....742...493.........674....*......#........*.....*.78..-350....\n",
"...........290.........*.....%...110........447.......#....-.......*....838..........................167..911.487.....880..493..............\n",
"199...745......189=.389.....676......+........*..=........442....810........................................*.......................795.....\n",
"...................................337........76..728..=......61.....769.............................386.....627..604............$.....*623.\n",
"....=925................................=...............282.............*...597.....851..841...............2......*..........991..139.......\n",
".......................443....=..........829....................524...816......*......*.*.....752....=468..*...805.....388@[email protected]...\n",
"....14...........*........*...325.................676..............-.........192...859..712....+..........585...............................\n",
"....*.............892...513..........286.984...................301....859.....................................900.................788%......\n",
"[email protected]/....155..*...........124.....*......844.......693.......*.............................\n",
"......469..................706.786.............67........*.............115*.....631.164..#............*..852..277.960.................11....\n",
"[email protected]..........*..................354...471.......................................152.........................870...*...824\n",
"................*....*....832..822..............................=114.....881....-.........357*.....................................606..*...\n",
"..574............956.124........................943....278..................&.163...................=199................................761.\n",
"........329.623............308.....210..........*.........*....#...3........................792...........11...676..........................\n",
".795.68....*........................@.......280..........965.943...............814.....182.*.....454..202*..............971.47.704.....444..\n",
"....*.........407..............558.............#.........................913.....%....%.....801.................652......*....*.....-..*....\n",
"..........552*.................*.........487......321.......852.217.......+..........................=.943..628.......303..........350.288..\n",
"[email protected]..................*.....$......*....*..............806*.......&....190...&.................806.235...........\n",
".......264.538......729.................997....688..435....510......82.285............316.639....................246.......%...*.......#....\n",
"....@.........+.964...............795..+.......................862...............................945.726-....../..../...........210.....700.\n",
"..452.............*...201.....891*.............49.............*........182......483.399.847.......*.............868....204.220.......-......\n",
".................466..*.............819...=.......184....$...114........+..........*........619....974....603................*.....854......\n",
".......................624.........*.....42...499*......743.........586.................950....-.............................927............\n",
"........$........379&.......855..252..#.....................120%......*..$...618.......*..................619..........636..................\n",
"....408.462.............528*...........869....145.15.606............581..297...*.....35..-...........218...*.......4*....%.......175........\n",
".....*........................$20................*..............................901......388...........$.............25...........*......157\n",
"..904........659............$.....762........808...%..........*18.............................#.878..........44..693............611..566*...\n",
"......977.......*.=.......597..-.*..........*.....538.209..............+.....$703......#....347....*652........*..........504...............\n",
".............668...462........59.2...370...587........*.............819..............152......................919.......+..*................\n",
".....817................688&.......................848..................639...347...........*671.......240........900..122.951..............\n",
"....*..........268/..........*821...........449..........817........86...*...............431......404..&...660....*..................691....\n",
"....611.............661....59........256.........$.......*...........+.548.........746.............+...........975...669.577...353....*.....\n",
"580.........307......&................*...........634.100....339......................*.................................*..........387......\n",
".....594.......*........&445...........675....+.............*......857......*........192.251..........504...................../.........534.\n",
".923..........954.............329.150......727....80.......474........$..385.............=...515*97..#......876.573...199.....921...........\n",
"...*.....236...............74........*..............*..............................919.........................*.......*..803....../460.....\n",
".94......*[email protected]............&.........%........349..752/.%.....735...........838.....*..............\n",
"...............425.*............985*........%......&........77....653....622...659.964..*.........147.-....................-.671............\n",
"......252...........898.....640.....841.........988..........*.............*.......*...805....................=...&.....410..........$743...\n",
".........*.....................*985.........407........$756..506.........-.332....934..................253..972...903........887.199........\n",
"......#...548........608*471.........142.....*...685...............729.172......-............................................&....#.....-558\n",
".....855..........%...........82.......*..729.......*.509.....850..@......./.910.......202........447..#........481......908........*.......\n",
".............$.641...758..846.*.....225...............*...374...........158........231.......775....*..837...............$...........549....\n",
".......587.615.......*.........844.......59......135..88.....*................437...*...........*.374................186....%829.167........\n",
"...691*............573..............293.*...........*.....940....105..38..........98........%.64.........432*737........*...........*.......\n",
"[email protected]........=....50......324................*.......446...........51.....360....................175....227..426.....\n",
"566..186./......*277..18....*779..*.........+...........226..........184.....=......696..........+............344...550...........*.....65..\n",
".......*..................&........728....521.....277.........&.123........+........*....+......................*[email protected]....*....\n",
".....85........37....=....438.442.............522...*...757.248....*577.27..466..862...503.406*767........*736...164.......*...........233..\n",
".................#....640.....*........834...........23...*...............*............................404...........-......785.............\n",
".........*..................89..877*....#..572..........22............891..........295.354*864...875............=..&..706.........-.........\n",
".......307............59............510...*....187.*247............+........#..741*..............$.......$608.316.355......*.....916....858.\n",
"..................745......705*[email protected]...=..742........843.*44.......718.................309.............*...\n",
"....................*............................*888.......%[email protected]*.........797..$366..................95..\n",
"......890....*96.894......765......170/.......260.......149.......................759........................*.................940..........\n",
".......*....................*..#...................57*....-.........................&..858................312......881.........$.......627..\n",
"....149......392..633.....581.947.#...955...151*......44.................942..............+..........14........210*.....................*...\n",
"............/......*..889.........792...........201............#.....450*............................*...*................127.........921...\n",
"....567#........253...*......................................817...........85*106......239*.......920..16.969......%......*...............76\n",
".........*537..........583.512*...............*393.43...............513#...........906..............................562.681....*713.........\n",
"......260.....48..560..........376.........140............................151......*........823*.....921..........&.........224.............\n",
"...............*...%......=.................................716.........*[email protected]......\n",
".............61..........836..&29......357............106......*199...996.......*[email protected]*.........\n",
"....#...........#487.433...............#....81........*.......................488........382.....&.............#............................\n",
"..33............................908$........*........133....470&......-...........894...%......70..............626........253.*915..........\n",
"..................139*134.185...........49..142..../...............685..312...95..+..................985...#.......831.....@................\n",
"........*..................&.....................487..........822*........@....*.....................*....919......*...................*....\n",
"98......931......*[email protected]$...................522...915.583.72......592..........169.......353....365.678.\n",
"..............559......570...........................485..............#....582.......*.......*............*..................*....=.........\n",
".......+...38..........*...506.........811.....+188......766...623..363....*......*.914............#[email protected].........../...694..312..156..\n",
"........59...*.......405...*..........*......%..........&.........*[email protected]...........*....\n",
"....737.....608..........362...336....642....606..................262......................................209.........................617..\"\"\""
]
},
{
"cell_type": "markdown",
"source": [
"## Data Builder\n",
"Since we have to check neighbouring symbols I am going to use a 2D grid, where each cell contains a single symbol."
],
"metadata": {
"id": "b1vDPUjwVQH3"
}
},
{
"cell_type": "code",
"source": [
"def grid_builder(txt):\n",
" lines = txt.split(\"\\n\")\n",
"\n",
" grid = []\n",
" for line in lines:\n",
" grid.append([*line]) # the * unpacks the string\n",
"\n",
" return grid"
],
"metadata": {
"id": "ZH2jIq2vKdyw"
},
"execution_count": 11,
"outputs": []
},
{
"cell_type": "code",
"source": [
"grid_txt = grid_builder(txt_input)\n",
"\n",
"print(f\"Size of y dimension: {len(grid_txt)}\")\n",
"print(f\"Size of x dimension: {len(grid_txt[0])}\")\n",
"print(grid_txt[0])"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "eLS-24-iY4Bk",
"outputId": "e3c7e2df-ae29-4af7-fe35-6e32284df0ad"
},
"execution_count": 12,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"Size of y dimension: 140\n",
"Size of x dimension: 140\n",
"['.', '4', '7', '9', '.', '.', '.', '.', '.', '.', '.', '.', '1', '5', '5', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '9', '4', '4', '.', '.', '.', '.', '.', '6', '2', '2', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '3', '1', '.', '.', '.', '.', '.', '.', '.', '.', '.', '2', '6', '4', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '5', '3', '2', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '2', '5', '4', '.', '.', '.', '.', '.', '.', '.', '.', '.', '5', '2', '8', '.', '.', '.', '.', '.']\n"
]
}
]
},
{
"cell_type": "markdown",
"source": [
"## Parts Identifications\n",
"\n",
"Here is the idea so far, we loop over the grid horizontally. Each time we check if the symbol we are on is a number, if it's a number we check if it's neighbours are either \"not a number\" or \"not a `.`\". If so then we add it to a list of parts. So far so good.\n",
"\n",
"One problem is that our part-checker (I am calling it that for now), looks at a single number at a time, what if we encounter a multi-digit part number that has a neighbouring symbol on the last digit? The solution is to build/cache the number as we go, then we empty the cache if the next symbol is not a number, however if it is a number we add it to the cache. Each time we'll check if the number has a symbol, if so we **mark** it as a part number and **building** the number until a `.` is encountered, only then do we check if it was an engine part and add it to the list if necessary.\n",
"\n",
"Notice that encountering either a `.` or a symbol will always be the end of the number caching/building process."
],
"metadata": {
"id": "3V3x8B9NdES5"
}
},
{
"cell_type": "code",
"source": [
"def mechamaru(grid):\n",
" found_mecha_parts = []\n",
"\n",
" number_builder = \"\"\n",
"\n",
" for y, row in enumerate(grid):\n",
"\n",
" # resets every new row\n",
" is_a_part = False\n",
" number_builder = \"\"\n",
"\n",
" for x, char in enumerate(row):\n",
"\n",
" numbers = \"0123456789\"\n",
" # if a number\n",
" if char in numbers:\n",
" number_builder += char\n",
"\n",
" # is it a part?\n",
" not_parts = f\"{numbers}.\" # add the \".\"\n",
" for dy in [-1, 0, 1]:\n",
" for dx in [-1, 0, 1]:\n",
"\n",
" xx = max(x + dx, 0)\n",
" yy = max(y + dy, 0)\n",
"\n",
" xx = min(xx, len(row)-1)\n",
" yy = min(yy, len(grid)-1)\n",
"\n",
" if yy == 0 and xx == 0:\n",
" continue\n",
"\n",
" neighbour = grid[yy][xx]\n",
" # print(f\"{char}, {neighbour}\")\n",
" # not not parts == parts\n",
" if neighbour not in not_parts:\n",
" # print(\"is a part\")\n",
" is_a_part = True\n",
"\n",
" # if not a number or last in row\n",
" if char not in numbers or x == len(row)-1:\n",
" # if so far the numbers where parts\n",
" if is_a_part == True:\n",
" found_mecha_parts.append(int(number_builder))\n",
"\n",
" # reset we are on not-a-number\n",
" # if it was a part it was added\n",
" number_builder = \"\"\n",
" is_a_part = False\n",
"\n",
" return found_mecha_parts"
],
"metadata": {
"id": "JFEZpVdWdLgL"
},
"execution_count": 13,
"outputs": []
},
{
"cell_type": "markdown",
"source": [
"### Test"
],
"metadata": {
"id": "GsIzQcO74E9s"
}
},
{
"cell_type": "code",
"source": [
"test =\\\n",
"[\"12....*412....99....#25\",\n",
" \"[email protected]\",\n",
" \"32......&&............4\",\n",
" \"..90........7.........!\"]\n",
"\n",
"found_parts = mechamaru(test)\n",
"print(found_parts)\n",
"# 12, 412, 25, 34, 32, 4"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "NLTqr3vP0Bs1",
"outputId": "019b05a7-6849-4066-95d8-0a4a355f3834"
},
"execution_count": 14,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"[12, 412, 25, 34, 32, 4]\n"
]
}
]
},
{
"cell_type": "markdown",
"source": [
"## Identify Parts"
],
"metadata": {
"id": "v4fXtrOe9TUQ"
}
},
{
"cell_type": "code",
"source": [
"found_parts = mechamaru(grid_txt)\n",
"\n",
"print(f\"The sum of all parts is {sum(found_parts)}\")"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "Wdf-JB9Y49Uj",
"outputId": "81aafd46-bcba-4b61-9ff5-c569ab4aab02"
},
"execution_count": 15,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"The sum of all parts is 528819\n"
]
}
]
},
{
"cell_type": "markdown",
"source": [
"# Puzzle - part 2\n",
"\n",
"**--- Part Two ---**\n",
"\n",
"The engineer finds the missing part and installs it in the engine! As the engine springs to life, you jump in the closest gondola, finally ready to ascend to the water source.\n",
"\n",
"You don't seem to be going very fast, though. Maybe something is still wrong? Fortunately, the gondola has a phone labeled \"help\", so you pick it up and the engineer answers.\n",
"\n",
"Before you can explain the situation, she suggests that you look out the window. There stands the engineer, holding a phone in one hand and waving with the other. You're going so slowly that you haven't even left the station. You exit the gondola.\n",
"\n",
"The missing part wasn't the only issue - one of the gears in the engine is wrong. **A gear** is any `*` symbol that is adjacent to **exactly two part numbers**. Its **gear ratio** is the result of multiplying those two numbers together.\n",
"\n",
"This time, you need to find the gear ratio of every gear and add them all up so that the engineer can figure out which gear needs to be replaced.\n",
"\n",
"Consider the same engine schematic again:\n",
"\n",
"```\n",
"467..114..\n",
"...*......\n",
"..35..633.\n",
"......#...\n",
"617*......\n",
".....+.58.\n",
"..592.....\n",
"......755.\n",
"...$.*....\n",
".664.598..\n",
"```\n",
"\n",
"In this schematic, there are two gears. The first is in the top left; it has part numbers `467` and `35`, so its gear ratio is `16345`. The second gear is in the lower right; its gear ratio is `451490`. (The * adjacent to `617` is not a gear because it is only adjacent to one part number.) Adding up all of the gear ratios produces `467835`.\n",
"\n",
"**What is the sum of all of the gear ratios in your engine schematic?**"
],
"metadata": {
"id": "yl-xvjcPC4Sc"
}
},
{
"cell_type": "markdown",
"source": [
"## Parts Identification\n",
"\n",
"At first glance this just requires a minor adjustment to the `mechamaru()` function. As we iterate over the grid we want to check for `*` instead of numbers.\n",
"\n",
"If the `*` neighbours two numbers we jump to the numbers and check for their **horizontal** neighbours and insert into the number builder accordingly - if we went to he left, in front of the number; if we went to the right, at the end of the number.\n",
"\n",
"There is one potential problem.\n",
"\n",
"```\n",
"467..114..\n",
".*........\n",
"..35..633.\n",
"```\n",
"\n",
"Notice that in the above example the `*` has five neigbouring digits `4`, `6`, `7`, `3`. We cannot treat them indepedently, we should somehow group them.\n",
"\n",
"How about we do something similar to a search, then? Once we encounter `*` we find all neighbouring numbers and for each of them (`4`, `6`, `7`, `3`) we search to the left and right for more numbers and join them together accordingly. This will produce the following set of numbers\n",
"```\n",
"{467, 467, 467, 35}\n",
"```\n",
"then we just have to remove duplicates.\n",
"\n",
"But then what if the schematic looks like this.\n",
"\n",
"```\n",
"467..114..\n",
".*........\n",
".467..633.\n",
"```\n",
"\n",
"We would end up with\n",
"```\n",
"{467, 467, 467, 467, 467}\n",
"```\n",
"which would translate to just `467`. This is no good.\n",
"\n",
"To fix this let us track the left most position of each part number in a format like this `(part number, y, x)`.\n",
"So then we end up with\n",
"```\n",
"{(467, 0, 0), (467, 0, 0), (467, 0, 0), (467, 2, 1), (467, 2, 1)}\n",
"```\n",
"and we can easily remove duplicates leaving us with\n",
"```\n",
"{(467, 0, 0), (467, 2, 1)}\n",
"```\n",
"\n",
"Notice that if use Python sets `{}` the duplicated take care of themselves."
],
"metadata": {
"id": "Uej1zfyKILaE"
}
},
{
"cell_type": "code",
"source": [
"test_set = {(467, 0, 0), (467, 0, 0), (467, 0, 0), (467, 2, 1), (467, 2, 1)}\n",
"print(test_set)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "vURjujLhOS6t",
"outputId": "a56ddd6b-1229-49ce-abeb-e89082d9d4da"
},
"execution_count": 16,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"{(467, 2, 1), (467, 0, 0)}\n"
]
}
]
},
{
"cell_type": "markdown",
"source": [
"The all that is left is to check the size of the set, if it equal to **two**, we can either add the numbers to the list (as a group) or multiply them out and add the result."
],
"metadata": {
"id": "2FkRPltdSe6V"
}
},
{
"cell_type": "code",
"source": [
"def mechamaru_gear_candidates(grid):\n",
" found_gear_parts = []\n",
"\n",
" all_gear_parts = []\n",
"\n",
" for y, row in enumerate(grid):\n",
" for x, char in enumerate(row):\n",
"\n",
" # if a number\n",
" if char == \"*\":\n",
" gear_parts = set()\n",
"\n",
" # iterate over neighbours\n",
" for dy in [-1, 0, 1]:\n",
" for dx in [-1, 0, 1]:\n",
"\n",
" xx = max(x + dx, 0)\n",
" yy = max(y + dy, 0)\n",
"\n",
" xx = min(xx, len(row)-1)\n",
" yy = min(yy, len(grid)-1)\n",
"\n",
" # skip current pos\n",
" if yy == 0 and xx == 0:\n",
" continue\n",
"\n",
" numbers = \"0123456789\"\n",
" neighbour = grid[yy][xx]\n",
"\n",
" if neighbour in numbers:\n",
" # start with xx since we could already be\n",
" # on the first digit\n",
" xx_gear_part_pos = xx\n",
" gear_part = f\"{neighbour}\"\n",
"\n",
" # build the number to the left (finds part position)\n",
" for dlxx in range(1, xx + 1):\n",
" xxx = xx - dlxx\n",
" # if beggining of row\n",
" if xxx < 0:\n",
" break\n",
"\n",
" num_candidate = grid[yy][xxx]\n",
"\n",
" # if a number\n",
" if num_candidate in numbers:\n",
" gear_part = f\"{num_candidate}{gear_part}\"\n",
" # update first digit position\n",
" xx_gear_part_pos = xxx\n",
" # if a symbol\n",
" else:\n",
" break\n",
"\n",
"\n",
" # do the same but go right now\n",
" for drxx in range(1, len(row)-1):\n",
" xxx = xx + drxx\n",
" # if end of row\n",
" if xxx > len(row) - 1:\n",
" break\n",
"\n",
" num_candidate = grid[yy][xxx]\n",
"\n",
" # if a number\n",
" if num_candidate in numbers:\n",
" gear_part = f\"{gear_part}{num_candidate}\"\n",
" # if a symbol\n",
" else:\n",
" break\n",
"\n",
" # add to the set of parts\n",
" gear_part = int(gear_part)\n",
" gear_parts.add((gear_part, yy, xx_gear_part_pos))\n",
"\n",
" all_gear_parts.append(list(gear_parts))\n",
"\n",
" return all_gear_parts"
],
"metadata": {
"id": "fWvcWO3i9i9q"
},
"execution_count": 72,
"outputs": []
},
{
"cell_type": "markdown",
"source": [
"### Test"
],
"metadata": {
"id": "eaX_MZImIuEu"
}
},
{
"cell_type": "code",
"source": [
"test =\\\n",
"[\"12....*412....99....#25\",\n",
" \"[email protected]\",\n",
" \"32......&&..*77.....4*4\",\n",
" \"..90........77........!\",\n",
" \"$.......531.72.........\",\n",
" \"......553.91*......*.8.\",\n",
" \"...#.32......#......&..\",\n",
" \".......*.....!.....42..\",\n",
" \"........1192..........1\",\n",
" \"1111*13..............*1\",]\n",
"\n",
"found_gears_like_parts = mechamaru_gear_candidates(test)\n",
"\n",
"for gear_like_part in found_gears_like_parts:\n",
" print(gear_like_part)\n",
"\n",
"# 412\n",
"# 66, 4, 4\n",
"# 77, 77\n",
"# 72, 91\n",
"# 32 1192\n",
"# 1111, 13\n",
"# 1, 1"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "IBvsRAgzIvC-",
"outputId": "0f2d171d-5c6e-4e35-e8ea-b259e37f0be3"
},
"execution_count": 73,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"[(412, 0, 7)]\n",
"[(77, 3, 12), (77, 2, 13)]\n",
"[(4, 2, 20), (4, 2, 22), (66, 1, 21)]\n",
"[(72, 4, 12), (91, 5, 10)]\n",
"[]\n",
"[(32, 6, 5), (1192, 8, 8)]\n",
"[(1111, 9, 0), (13, 9, 5)]\n",
"[(1, 9, 22), (1, 8, 22)]\n"
]
}
]
},
{
"cell_type": "markdown",
"source": [
"## Identify Gears and Calculate Ratio"
],
"metadata": {
"id": "Iq10JDCDI8Zi"
}
},
{
"cell_type": "code",
"source": [
"found_gear_candidates = mechamaru_gear_candidates(grid_txt)\n",
"\n",
"print(found_gear_candidates[0])"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "M4gz1qeiI6mB",
"outputId": "991a90be-f372-4d25-b2f6-cdca628d5c99"
},
"execution_count": 74,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"[(264, 0, 65), (111, 1, 61)]\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"gears_ratios = []\n",
"\n",
"for gear_candidate in found_gear_candidates:\n",
" if len(gear_candidate) == 2:\n",
" ratio = gear_candidate[0][0] * gear_candidate[1][0]\n",
" gears_ratios.append(ratio)\n",
"\n",
"print(gears_ratios[:5])"
],
"metadata": {
"id": "WtfvE8MOJEIc",
"colab": {
"base_uri": "https://localhost:8080/"
},
"outputId": "6eabc25d-540b-4073-b70a-1d993be03451"
},
"execution_count": 75,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"[29304, 416592, 143148, 485748, 324210]\n"
]
}
]
},
{
"cell_type": "markdown",
"source": [
"## Sum of Ratios"
],
"metadata": {
"id": "lyckAXNxAwt-"
}
},
{
"cell_type": "code",
"source": [
"print(f\"The sum of all gears (* with 2 part numbers) is {sum(gears_ratios)}\")"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "68SIiQM7ANUj",
"outputId": "9c940c66-91e6-4bfe-a899-5bd4467cfad0"
},
"execution_count": 76,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"The sum of all gears (* with 2 part numbers) is 80403602\n"
]
}
]
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment