Learn to Code via Tutorials on Repl.it!

← Back to all posts
Advent of Code 1 Walkthrough
h
MatthewDoan3 (19)

Intro

Hey guys! This is Matthew. You might know me from my old Repl.it account, MatthewDoan1, but sadly I can't log into it anymore because my school deleted my email pepeHands. Anyways here I'll walk you all through how to solve the first AOC challenge!

Setup

Ok so the first step is to do some basic setting up. You can get the puzzle input from here. I'll be doing the tutorial in Python. After creating your repl, you can add a new file. Give it some name, like my_dank_input.txt. I just called it input.txt because I'm a normie because it'll make it easier for me. Now copy-paste the puzzle input into your input.txt file.

The next step is to actually read from the puzzle file in your Python script. Go to your main.py and set up the list that will contain the numbers:

numbers = []

with open('input.txt') as f:
    for line in f:
        print(line.rstrip())

So the block of code above creates a list to store the numbers from the puzzle input, and then reads in every line of the file and prints it out. Run it to make sure everything's working properly.

Let's move on. It's great that we can see the lines of the input, but we need to move it into the numbers list so we can process it. We can do that with list comprehension:

numbers = []

with open('input.txt') as f:
    numbers = [int(line.rstrip()) for line in f]

print(numbers)

This takes every line from the file, strips the whitespace from the end, and converts it to an integer so we can put it in the array. If you don't understand list comprehension, well, there are a lot of good tutorials online. Here is a good one. I'll summarize it here: it's a way to go through a list and get results for each element in 1 line. The code above goes through the list and converts each line, and puts it in the list.

Now comes the fun part -- we get to search for the two numbers that add up to 2020!

Part 1

There are many ways to solve this problem. The easiest, brute-force solution is to loop through the list, and, for each value in the list, loop again to see if there were any other values in the list that would add up to 2020. However, you might notice that this solution is pretty slow; for each value in the list, you loop through the list again! There's a far more efficient and faster solution which I hope I'll be able to teach you by the end of this tutorial, and you can apply it in different problems.

So what's the goal? Our goal is to find a pair of numbers in the list that add to 2020 in as few steps as possible. You can do this in 1 loop. How? Try to take a guess before you read on.

Ready for the answer? It's to use a dictionary. For every number numbers[i] in the list, you check in the dictionary to see if the difference exists as well. If it doesn't, then you add it to the dictionary. So, for example, say you come across the number 2019. You check in the dictionary, "Hey, is there a 1 in here as well?" and if there is, then great! You've found the pair. If there isn't, then you add the 2019 to the dictionary, so that if you do encounter a 1 later on, you'll know that you have found a valid pair.

Now let's do this in Python:

numbers = []

with open('input.txt') as f:
    numbers = [int(line.rstrip()) for line in f]

def searchForPair(target):
    diff = {}

    for i in range(len(numbers)):
        current_number = numbers[i]

        if (target - current_number) in diff:
            return current_number * (target - current_number)

        diff[current_number] = True

So searchForPair is going to accept a target number and look for a pair containing that target number in the numbers list. Now the last step is just to search for 2020.

print(searchForPair(2020))

I'm not gonna put the answer here, but I'll leave it for you to write the code and find out.

Part 2

Great! If you're here, you should have finished the program, found the solution, and put it into the Advent of Code page, allowing you to move onto Part 2!

Reading the problem description, you'll notice that the only difference between Parts 1 and 2 is that this time you need 3 numbers instead of just two. Unfortunately, there's no ingenious solution like before, where you pull out a dictionary and put your values in. Nope; instead the solution is actually really easy. That's your hint; now before reading on try to think of what the method will be.

If you're here, then I assume that you took a guess and are ready to move on. The answer is, you just iterate over the list, and for number numbers[i], you look for a pair that adds up to 2020 - numbers[i]. So (2020 - numbers[i]) + numbers[i]) = 2020. quick maths

First we need to modify the searchForPair function. You'll see why in a second:

def searchForPair(start, target):
    diff = {}

    for i in range(start, len(numbers)):
        current_number = numbers[i]

        if (target - current_number) in diff:
            return current_number * (target - current_number)

        diff[current_number] = True

print(searchForPair(0, 2020)) # Answer for Part 1

If you have a keen eye, you'll notice that I added a new arg to the function called start. This is because when we're looking for a pair to complement the value we're currently looking at, we don't want to go backwards in the list. Like if you're on the 3rd index and looking for a pair that will add up to 2020 - numbers[2], you don't want to look at indices 0 or 1. This is to increase efficiency; if these values are behind you, that means you've already looked at them and moved on, so there's no reason to process them again.

So now let's dive into the code. My explanation might be hard to understand, so just take a look and you'll see how simple it is

for i in range(len(numbers)):
    complement = numbers[i]

    result = searchForPair(i, 2020 - complement) # Search for a pair to make everything add up to 2020
    
    if result:
        print(result * complement) # Answer to Part 2

And voila! You have completed the Advent of Code Challenge #1. Make sure to SMASH the like button, HIT subscribe, TURN ON notifications! and have a good one y'all

P.S. if there's anything I can clarify, feel free to tell me in the comments.

P.P.S. if you want to learn more about these types of problems, I highly recommend this resource

Comments
hotnewtop
grrlic (2)

I like your approach for the part 2!

MatthewDoan3 (19)

@grrlic Thank you! (Also btw, I checked your Advent of Code repl, and it's great! I didn't know how to make sets in python, and my lazy butt decided to use a dict instead haha, but I learned something new! ty)

grrlic (2)

@MatthewDoan3 hahah cool! anyway GLHF for day two poggg

gwood5901 (22)

Heh, you did it the smart way. I just brute forced it.

MatthewDoan3 (19)

@gwood5901 thanks hehe, I made this post to help teach people about this method of solving the problem specifically instead of brute-forcing it

JBloves27 (1504)

Pretty cool bro! very sad that your other account got deleted :(

JBloves27 (1504)

Sry, I just thought it would be rude to say it out loud @MatthewDoan3

MatthewDoan3 (19)

@JBYT27 lol are you talking to yourself?

badst (667)

Smart of you, my solution was just to bruteforce the array for part 2 LOL

import random
nums=open('day1.txt').read().splitlines()
final=[int(x)for x in nums]
product=1
# Day 1 - Part 1
for x in final:
  if 2020-x in final:
    print((2020-x)*x)
    break
# Day 1 - Part 2
while True:
  arr=[]
  for x in range(3):
    arr.append(random.choice(final))
  if sum(arr)==2020:
    for x in arr:
      product*=x
    print(product)
    break;
MatthewDoan3 (19)

@pepelaugh no way im seeing this right now, did you actually just take random choices? haha omg

ahh the duality of man

badst (667)

@MatthewDoan3 yep, for in would be much better but keep in mind i did this at 12am cause i wanted to be "first" ;)

also me do c# and js me make lot excuse

MatthewDoan3 (19)

@pepelaugh me do java mainly, no excuse for my sins :(

badst (667)

@MatthewDoan3 Yeah c# = java clone tbh.

MatthewDoan3 (19)

@pepelaugh yep I've never learned C# before and I can already understand most of the code lmao

gwood5901 (22)

@pepelaugh The only difference is Unity uses c#, so it's better :)

RayhanADev (1389)

Nice! I did it quite similarly except in JS last night:

let expenses = [long list of expenses];

function part1() {
	let cash = 0;
	expenses.forEach(expense => {
		let cash = 2020 - expense;
		if (expenses.includes(cash)) {
			console.log(`Pair Found: ${cash} & ${expense}`);
			console.log(`Product is: ${cash * expense}`);
		}
	});
}

function part2() {
	let cash = 0;
	expenses.forEach(expense => {
		expenses.forEach(expense2 => {
			let cash = 2020 - expense - expense2;
			if (expenses.includes(cash)) {
				console.log(`Trio Found: ${cash}, ${expense}, & ${expense2}`);
				console.log(`Product is: ${cash * expense * expense2}`);
			}
		});
	});
}
MatthewDoan3 (19)

@RayhanADev That works! I just wanted to share my efficient solution hehe

RayhanADev (1389)

@MatthewDoan3 yeah, your solution is awesome! Great use of Python btw, I love that you didn’t just bruteforce it!

MatthewDoan3 (19)

@RayhanADev Thank you! if only Advent of Code rewarded faster solutions :/

Bookie0 (5618)

add syntax highlighting with pyafter the 3 backslashes (`):


;)

MatthewDoan3 (19)

@Bookie0 oh bruh i put python3 :( that explains it ty