Category: Advent Of Code

Archive for the ‘Advent Of Code’ Category

Advent Of Code 2015: Day 8

09 Dec 2015

CTF: Advent Of Code 2015
Link to challenge: http://adventofcode.com

Date Completed: 09 December 2015

Challenge

--- Day 8: Matchsticks ---
Space on the sleigh is limited this year, and so Santa will be bringing his list as a digital copy. He needs to know how much space it will take up when stored.
It is common in many programming languages to provide a way to escape special characters in strings. For example, C, JavaScript, Perl, Python, and even PHP handle special characters in very similar ways.
However, it is important to realize the difference between the number of characters in the code representation of the string literal and the number of characters in the in-memory string itself.
For example:
"" is 2 characters of code (the two double quotes), but the string contains zero characters.
"abc" is 5 characters of code, but 3 characters in the string data.
"aaa\"aaa" is 10 characters of code, but the string itself contains six "a" characters and a single, escaped quote character, for a total of 7 characters in the string data.
"\x27" is 6 characters of code, but the string itself contains just one - an apostrophe ('), escaped using hexadecimal notation.
Santa's list is a file that contains many double-quoted string literals, one on each line. The only escape sequences used are \\ (which represents a single backslash), \" (which represents a lone double-quote character), and \x plus two hexadecimal characters (which represents a single character with that ASCII code).
Disregarding the whitespace in the file, what is the number of characters of code for string literals minus the number of characters in memory for the values of the strings in total for the entire file?
For example, given the four strings above, the total number of characters of string code (2 + 5 + 10 + 6 = 23) minus the total number of characters in memory for string values (0 + 3 + 7 + 1 = 11) is 23 - 11 = 12.
Your puzzle answer was 1342.
--- Part Two ---
Now, let's go the other way. In addition to finding the number of characters of code, you should now encode each code representation as a new string and find the number of characters of the new encoded representation, including the surrounding double quotes.
For example:
"" encodes to "\"\"", an increase from 2 characters to 6.
"abc" encodes to "\"abc\"", an increase from 5 characters to 9.
"aaa\"aaa" encodes to "\"aaa\\\"aaa\"", an increase from 10 characters to 16.
"\x27" encodes to "\"\\x27\"", an increase from 6 characters to 11.
Your task is to find the total number of characters to represent the newly encoded strings minus the number of characters of code in each original string literal. For example, for the strings above, the total encoded length (6 + 9 + 16 + 11 = 42) minus the characters in the original code representation (23, just like in the first part of this puzzle) is 42 - 23 = 19.
Your puzzle answer was 2074.

--- Day 8: Matchsticks ---

Space on the sleigh is limited this year, and so Santa will be bringing his list as a digital copy. He needs to know how much space it will take up when stored.

It is common in many programming languages to provide a way to escape special characters in strings. For example, C, JavaScript, Perl, Python, and even PHP handle special characters in very similar ways.

However, it is important to realize the difference between the number of characters in the code representation of the string literal and the number of characters in the in-memory string itself.

For example:

"" is 2 characters of code (the two double quotes), but the string contains zero characters.

"abc" is 5 characters of code, but 3 characters in the string data.

"aaa\"aaa" is 10 characters of code, but the string itself contains six "a" characters and a single, escaped quote character, for a total of 7 characters in the string data.

"\x27" is 6 characters of code, but the string itself contains just one - an apostrophe ('), escaped using hexadecimal notation.

Santa's list is a file that contains many double-quoted string literals, one on each line. The only escape sequences used are \\ (which represents a single backslash), \" (which represents a lone double-quote character), and \x plus two hexadecimal characters (which represents a single character with that ASCII code).

Disregarding the whitespace in the file, what is the number of characters of code for string literals minus the number of characters in memory for the values of the strings in total for the entire file?

For example, given the four strings above, the total number of characters of string code (2 + 5 + 10 + 6 = 23) minus the total number of characters in memory for string values (0 + 3 + 7 + 1 = 11) is 23 - 11 = 12.

Your puzzle answer was 1342.

--- Part Two ---

Now, let's go the other way. In addition to finding the number of characters of code, you should now encode each code representation as a new string and find the number of characters of the new encoded representation, including the surrounding double quotes.

For example:

"" encodes to "\"\"", an increase from 2 characters to 6.

"abc" encodes to "\"abc\"", an increase from 5 characters to 9.

"aaa\"aaa" encodes to "\"aaa\\\"aaa\"", an increase from 10 characters to 16.

"\x27" encodes to "\"\\x27\"", an increase from 6 characters to 11.

Your task is to find the total number of characters to represent the newly encoded strings minus the number of characters of code in each original string literal. For example, for the strings above, the total encoded length (6 + 9 + 16 + 11 = 42) minus the characters in the original code representation (23, just like in the first part of this puzzle) is 42 - 23 = 19.

Your puzzle answer was 2074.

Solution

A fairly simple puzzle. My approach was to add up the strings together and use regular expressions to replace special characters with a * character so that the python len function would provide me with the correct result.

Script:

# Day 8 - Part 1 and Part 2
import sys, re
str = ''
eval = ''
reverseCount = 0
with open('input.txt') as f:
for line in f:
line = line.rstrip()
str += line
eval += line[1:-1] # strip quotes
reverseCount += line.count('\\') + line.count('"') + len(line) + 2 # add 2 for surrounding quotes each string has
# Lets get rid of a few things
eval = re.sub(r'\\x..|\\.', '*', eval)
# solution
print 'Part 1 answer is {0} - {1} = {2}'.format(len(str), len(eval), len(str)-len(eval))
print 'Part 2 answer is {0} - {1} = {2}'.format(reverseCount, len(str), reverseCount - len(str))

# Day 8 - Part 1 and Part 2

import sys, re

str = ''

eval = ''

reverseCount = 0

with open('input.txt') as f:

for line in f:

line = line.rstrip()

str += line

eval += line[1:-1] # strip quotes

reverseCount += line.count('\\') + line.count('"') + len(line) + 2 # add 2 for surrounding quotes each string has

# Lets get rid of a few things

eval = re.sub(r'\\x..|\\.', '*', eval)

# solution

print 'Part 1 answer is {0} - {1} = {2}'.format(len(str), len(eval), len(str)-len(eval))

print 'Part 2 answer is {0} - {1} = {2}'.format(reverseCount, len(str), reverseCount - len(str))

2 Comments

Posted Mo BeigiPersianMG in Advent Of Code 2015

Advent Of Code 2015: Day 7

08 Dec 2015

CTF: Advent Of Code 2015
Link to challenge: http://adventofcode.com

Date Completed: 07 December 2015

Challenge

# Day 7 - Part 1 and Part 2
#
# To find Part 1 answer: python day7.py | grep ' a = '
# To find Part 2 answer: Edit value of b in input.txt to result from part 1 and rerun script
import re
from z3 import *
def z3VarsAddIfMissing(wire):
if wire not in z3Vars:
z3Vars[wire] = BitVec(wire, 32) #32 bit integers
z3Vars = {}
s = Solver()
with open('input.txt') as f:
lines = f.readlines()
for line in lines:
# Get command -> store variables
res = re.search(r'(.*)\s*->\s*(.*)', line)
command, store_var = res.group(1).strip(), res.group(2)
# Store var
z3VarsAddIfMissing(store_var)
# Add logical constraints to solver
# Store other variables in commands if they don't exit on the way
# Bitwise AND
res = re.search(r'(.*?)\s*AND\s*(.*)', command)
if res and  res.group(1) != '' and res.group(2) != '':
z3VarsAddIfMissing(res.group(2))
# If first component is an integer
if res.group(1).isdigit():
s.add(z3Vars[store_var] == int(res.group(1)) & z3Vars[res.group(2)])
else:
z3VarsAddIfMissing(res.group(1))
s.add(z3Vars[store_var] == z3Vars[res.group(1)] & z3Vars[res.group(2)])
continue
# Bitwise OR
res = re.search(r'(.*?)\s*OR\s*(.*)', command)
if res and  res.group(1) != '' and res.group(2) != '':
z3VarsAddIfMissing(res.group(1))
z3VarsAddIfMissing(res.group(2))
s.add(z3Vars[store_var] == z3Vars[res.group(1)] | z3Vars[res.group(2)])
continue
# Bit LSHIFT
res = re.search(r'(.*?)\s*LSHIFT\s*(\d*)', command)
if res and  res.group(1) != '' and res.group(2) != '':
z3VarsAddIfMissing(res.group(1))
s.add(z3Vars[store_var] == z3Vars[res.group(1)] << int(res.group(2)))
continue
# Bit RSHIFT
res = re.search(r'(.*?)\s*RSHIFT\s*(\d*)', command)
if res and  res.group(1) != '' and res.group(2) != '':
z3VarsAddIfMissing(res.group(1))
s.add(z3Vars[store_var] == z3Vars[res.group(1)] >> int(res.group(2)))
continue
# Bitwise NOT
res = re.search(r'NOT\s*(.*)', command)
if res and  res.group(1) != '':
z3VarsAddIfMissing(res.group(1))
s.add(z3Vars[store_var] == (~z3Vars[res.group(1)]) & 0xFFFF ) # 0xFFFF bitwise and to constrain value to [0, 2^16)
continue
# Assign operation (variable or integer) ==
res = re.search(r'^(.*)$', command)
if res and res.group(1) != '':
if res.group(1).isdigit():
s.add(z3Vars[store_var] == res.group(1))
else:
z3VarsAddIfMissing(res.group(1))
s.add(z3Vars[store_var] == z3Vars[res.group(1)])
continue
# Print answers
set_option(max_args=10000000, max_lines=1000000, max_depth=10000000, max_visited=1000000)
print(s.check())
print(s.model())

# Day 7 - Part 1 and Part 2

# To find Part 1 answer: python day7.py | grep ' a = '

# To find Part 2 answer: Edit value of b in input.txt to result from part 1 and rerun script

import re

from z3 import *

def z3VarsAddIfMissing(wire):

if wire not in z3Vars:

z3Vars[wire] = BitVec(wire, 32) #32 bit integers

z3Vars = {}

s = Solver()

with open('input.txt') as f:

lines = f.readlines()

for line in lines:

# Get command -> store variables

res = re.search(r'(.*)\s*->\s*(.*)', line)

command, store_var = res.group(1).strip(), res.group(2)

# Store var

z3VarsAddIfMissing(store_var)

# Add logical constraints to solver

# Store other variables in commands if they don't exit on the way

# Bitwise AND

res = re.search(r'(.*?)\s*AND\s*(.*)', command)

if res and res.group(1) != '' and res.group(2) != '':

z3VarsAddIfMissing(res.group(2))

# If first component is an integer

if res.group(1).isdigit():

s.add(z3Vars[store_var] == int(res.group(1)) & z3Vars[res.group(2)])

else:

z3VarsAddIfMissing(res.group(1))

s.add(z3Vars[store_var] == z3Vars[res.group(1)] & z3Vars[res.group(2)])

continue

# Bitwise OR

res = re.search(r'(.*?)\s*OR\s*(.*)', command)

if res and res.group(1) != '' and res.group(2) != '':

z3VarsAddIfMissing(res.group(1))

z3VarsAddIfMissing(res.group(2))

s.add(z3Vars[store_var] == z3Vars[res.group(1)] | z3Vars[res.group(2)])

continue

# Bit LSHIFT

res = re.search(r'(.*?)\s*LSHIFT\s*(\d*)', command)

if res and res.group(1) != '' and res.group(2) != '':

z3VarsAddIfMissing(res.group(1))

s.add(z3Vars[store_var] == z3Vars[res.group(1)] << int(res.group(2)))

continue

# Bit RSHIFT

res = re.search(r'(.*?)\s*RSHIFT\s*(\d*)', command)

if res and res.group(1) != '' and res.group(2) != '':

z3VarsAddIfMissing(res.group(1))

s.add(z3Vars[store_var] == z3Vars[res.group(1)] >> int(res.group(2)))

continue

# Bitwise NOT

res = re.search(r'NOT\s*(.*)', command)

if res and res.group(1) != '':

z3VarsAddIfMissing(res.group(1))

s.add(z3Vars[store_var] == (~z3Vars[res.group(1)]) & 0xFFFF ) # 0xFFFF bitwise and to constrain value to [0, 2^16)

continue

# Assign operation (variable or integer) ==

res = re.search(r'^(.*)$', command)

if res and res.group(1) != '':

if res.group(1).isdigit():

s.add(z3Vars[store_var] == res.group(1))

else:

z3VarsAddIfMissing(res.group(1))

s.add(z3Vars[store_var] == z3Vars[res.group(1)])

continue

# Print answers

set_option(max_args=10000000, max_lines=1000000, max_depth=10000000, max_visited=1000000)

print(s.check())

print(s.model())

Solution

Wow this one was fun! I decided to use Z3Py, a theorem prover module for python. My solution essentially parses each command using regexp and adds the various boolean rules to a solver object. Finally, the theorem solver checks all possible values and prints out the results of every ‘wire’. Determining the answer is then very simple. To solve part 2 I simply changed the value of b in my input.txt to the answer from part a and reran the script.

# Day 7 - Part 1 and Part 2
#
# To find Part 1 answer: python day7.py | grep ' a = '
# To find Part 2 answer: Edit value of b in input.txt to result from part 1 and rerun script
import re
from z3 import *
z3Vars = {}
s = Solver()
with open('input.txt') as f:
lines = f.readlines()
for line in lines:
# Get command -> store variables
res = re.search(r'(.*)\s*->\s*(.*)', line)
command, store_var = res.group(1).strip(), res.group(2)
# Store var
if store_var not in z3Vars:
z3Vars[store_var] = BitVec(store_var, 32) #32 bit integers
# Add logical constraints to solver
# Store other variables in commands if they don't exit on the way
# Assign operation (integer) ==
res = re.search(r'^(\d*?)$', command)
if res and res.group(1) != '':
s.add(z3Vars[store_var] == res.group(1))
continue
# Bitwise AND (with integer)
res = re.search(r'(\d*)\s*AND\s*(.*)', command)
if res and  res.group(1) != '' and res.group(2) != '':
if res.group(2) not in z3Vars:
z3Vars[res.group(2)] = BitVec(res.group(2), 32)
s.add(z3Vars[store_var] == int(res.group(1)) & z3Vars[res.group(2)])
continue
# Bitwise AND
res = re.search(r'(.*?)\s*AND\s*(.*)', command)
if res and  res.group(1) != '' and res.group(2) != '':
if res.group(1) not in z3Vars:
z3Vars[res.group(1)] = BitVec(res.group(1), 32)
if res.group(2) not in z3Vars:
z3Vars[res.group(2)] = BitVec(res.group(2), 32)
s.add(z3Vars[store_var] == z3Vars[res.group(1)] & z3Vars[res.group(2)])
continue
# Bitwise OR
res = re.search(r'(.*?)\s*OR\s*(.*)', command)
if res and  res.group(1) != '' and res.group(2) != '':
if res.group(1) not in z3Vars:
z3Vars[res.group(1)] = BitVec(res.group(1), 32)
if res.group(2) not in z3Vars:
z3Vars[res.group(2)] = BitVec(res.group(2), 32)
s.add(z3Vars[store_var] == z3Vars[res.group(1)] | z3Vars[res.group(2)])
continue
# Bit LSHIFT
res = re.search(r'(.*?)\s*LSHIFT\s*(\d*)', command)
if res and  res.group(1) != '' and res.group(2) != '':
if res.group(1) not in z3Vars:
z3Vars[res.group(1)] = BitVec(res.group(1), 32)
s.add(z3Vars[store_var] == z3Vars[res.group(1)] << int(res.group(2)))
continue
# Bit RSHIFT
res = re.search(r'(.*?)\s*RSHIFT\s*(\d*)', command)
if res and  res.group(1) != '' and res.group(2) != '':
if res.group(1) not in z3Vars:
z3Vars[res.group(1)] = BitVec(res.group(1), 32)
s.add(z3Vars[store_var] == z3Vars[res.group(1)] >> int(res.group(2)))
continue
# Bitwise NOT
res = re.search(r'NOT\s*(.*)', command)
if res and  res.group(1) != '':
if res.group(1) not in z3Vars:
z3Vars[res.group(1)] = BitVec(res.group(1), 32)
s.add(z3Vars[store_var] == (~z3Vars[res.group(1)]) & 0xFFFF ) # 0xFFFF logical and to contrain value to [0, 2^16)
continue
# Assign operation (variable) ==
res = re.search(r'(.*)', command)
if res and res.group(1) != '':
if res.group(1) not in z3Vars:
z3Vars[res.group(1)] = BitVec(res.group(1), 32)
s.add(z3Vars[store_var] == z3Vars[res.group(1)])
continue
# Print answers
set_option(max_args=10000000, max_lines=1000000, max_depth=10000000, max_visited=1000000)
print(s.check())
print(s.model())

100

101

102

103

104

105

106

107

108

109

# Day 7 - Part 1 and Part 2

# To find Part 1 answer: python day7.py | grep ' a = '

# To find Part 2 answer: Edit value of b in input.txt to result from part 1 and rerun script

import re

from z3 import *

z3Vars = {}

s = Solver()

with open('input.txt') as f:

lines = f.readlines()

for line in lines:

# Get command -> store variables

res = re.search(r'(.*)\s*->\s*(.*)', line)

command, store_var = res.group(1).strip(), res.group(2)

# Store var

if store_var not in z3Vars:

z3Vars[store_var] = BitVec(store_var, 32) #32 bit integers

# Add logical constraints to solver

# Store other variables in commands if they don't exit on the way

# Assign operation (integer) ==

res = re.search(r'^(\d*?)$', command)

if res and res.group(1) != '':

s.add(z3Vars[store_var] == res.group(1))

continue

# Bitwise AND (with integer)

res = re.search(r'(\d*)\s*AND\s*(.*)', command)

if res and res.group(1) != '' and res.group(2) != '':

if res.group(2) not in z3Vars:

z3Vars[res.group(2)] = BitVec(res.group(2), 32)

s.add(z3Vars[store_var] == int(res.group(1)) & z3Vars[res.group(2)])

continue

# Bitwise AND

res = re.search(r'(.*?)\s*AND\s*(.*)', command)

if res and res.group(1) != '' and res.group(2) != '':

if res.group(1) not in z3Vars:

z3Vars[res.group(1)] = BitVec(res.group(1), 32)

if res.group(2) not in z3Vars:

z3Vars[res.group(2)] = BitVec(res.group(2), 32)

s.add(z3Vars[store_var] == z3Vars[res.group(1)] & z3Vars[res.group(2)])

continue

# Bitwise OR

res = re.search(r'(.*?)\s*OR\s*(.*)', command)

if res and res.group(1) != '' and res.group(2) != '':

if res.group(1) not in z3Vars:

z3Vars[res.group(1)] = BitVec(res.group(1), 32)

if res.group(2) not in z3Vars:

z3Vars[res.group(2)] = BitVec(res.group(2), 32)

s.add(z3Vars[store_var] == z3Vars[res.group(1)] | z3Vars[res.group(2)])

continue

# Bit LSHIFT

res = re.search(r'(.*?)\s*LSHIFT\s*(\d*)', command)

if res and res.group(1) != '' and res.group(2) != '':

if res.group(1) not in z3Vars:

z3Vars[res.group(1)] = BitVec(res.group(1), 32)

s.add(z3Vars[store_var] == z3Vars[res.group(1)] << int(res.group(2)))

continue

# Bit RSHIFT

res = re.search(r'(.*?)\s*RSHIFT\s*(\d*)', command)

if res and res.group(1) != '' and res.group(2) != '':

if res.group(1) not in z3Vars:

z3Vars[res.group(1)] = BitVec(res.group(1), 32)

s.add(z3Vars[store_var] == z3Vars[res.group(1)] >> int(res.group(2)))

continue

# Bitwise NOT

res = re.search(r'NOT\s*(.*)', command)

if res and res.group(1) != '':

if res.group(1) not in z3Vars:

z3Vars[res.group(1)] = BitVec(res.group(1), 32)

s.add(z3Vars[store_var] == (~z3Vars[res.group(1)]) & 0xFFFF ) # 0xFFFF logical and to contrain value to [0, 2^16)

continue

# Assign operation (variable) ==

res = re.search(r'(.*)', command)

if res and res.group(1) != '':

if res.group(1) not in z3Vars:

z3Vars[res.group(1)] = BitVec(res.group(1), 32)

s.add(z3Vars[store_var] == z3Vars[res.group(1)])

continue

# Print answers

set_option(max_args=10000000, max_lines=1000000, max_depth=10000000, max_visited=1000000)

print(s.check())

print(s.model())

No Comments

Posted Mo BeigiPersianMG in Advent Of Code 2015

Advent Of Code 2015: Day 6

06 Dec 2015

CTF: Advent Of Code 2015
Link to challenge: http://adventofcode.com

Date Completed: 06 December 2015

The Challenge

--- Day 6: Probably a Fire Hazard ---
Because your neighbors keep defeating you in the holiday house decorating contest year after year, you've decided to deploy one million lights in a 1000x1000 grid.
Furthermore, because you've been especially nice this year, Santa has mailed you instructions on how to display the ideal lighting configuration.
Lights in your grid are numbered from 0 to 999 in each direction; the lights at each corner are at 0,0, 0,999, 999,999, and 999,0. The instructions include whether to turn on, turn off, or toggle various inclusive ranges given as coordinate pairs. Each coordinate pair represents opposite corners of a rectangle, inclusive; a coordinate pair like 0,0 through 2,2 therefore refers to 9 lights in a 3x3 square. The lights all start turned off.
To defeat your neighbors this year, all you have to do is set up your lights by doing the instructions Santa sent you in order.
For example:
turn on 0,0 through 999,999 would turn on (or leave on) every light.
toggle 0,0 through 999,0 would toggle the first line of 1000 lights, turning off the ones that were on, and turning on the ones that were off.
turn off 499,499 through 500,500 would turn off (or leave off) the middle four lights.
After following the instructions, how many lights are lit?
Your puzzle answer was 569999.
--- Part Two ---
You just finish implementing your winning light pattern when you realize you mistranslated Santa's message from Ancient Nordic Elvish.
The light grid you bought actually has individual brightness controls; each light can have a brightness of zero or more. The lights all start at zero.
The phrase turn on actually means that you should increase the brightness of those lights by 1.
The phrase turn off actually means that you should decrease the brightness of those lights by 1, to a minimum of zero.
The phrase toggle actually means that you should increase the brightness of those lights by 2.
What is the total brightness of all lights combined after following Santa's instructions?
For example:
turn on 0,0 through 0,0 would increase the total brightness by 1.
toggle 0,0 through 999,999 would increase the total brightness by 2000000.
Your puzzle answer was 17836115.

--- Day 6: Probably a Fire Hazard ---

Because your neighbors keep defeating you in the holiday house decorating contest year after year, you've decided to deploy one million lights in a 1000x1000 grid.

Furthermore, because you've been especially nice this year, Santa has mailed you instructions on how to display the ideal lighting configuration.

Lights in your grid are numbered from 0 to 999 in each direction; the lights at each corner are at 0,0, 0,999, 999,999, and 999,0. The instructions include whether to turn on, turn off, or toggle various inclusive ranges given as coordinate pairs. Each coordinate pair represents opposite corners of a rectangle, inclusive; a coordinate pair like 0,0 through 2,2 therefore refers to 9 lights in a 3x3 square. The lights all start turned off.

To defeat your neighbors this year, all you have to do is set up your lights by doing the instructions Santa sent you in order.

For example:

turn on 0,0 through 999,999 would turn on (or leave on) every light.

toggle 0,0 through 999,0 would toggle the first line of 1000 lights, turning off the ones that were on, and turning on the ones that were off.

turn off 499,499 through 500,500 would turn off (or leave off) the middle four lights.

After following the instructions, how many lights are lit?

Your puzzle answer was 569999.

--- Part Two ---

You just finish implementing your winning light pattern when you realize you mistranslated Santa's message from Ancient Nordic Elvish.

The light grid you bought actually has individual brightness controls; each light can have a brightness of zero or more. The lights all start at zero.

The phrase turn on actually means that you should increase the brightness of those lights by 1.

The phrase turn off actually means that you should decrease the brightness of those lights by 1, to a minimum of zero.

The phrase toggle actually means that you should increase the brightness of those lights by 2.

What is the total brightness of all lights combined after following Santa's instructions?

For example:

turn on 0,0 through 0,0 would increase the total brightness by 1.

toggle 0,0 through 999,999 would increase the total brightness by 2000000.

Your puzzle answer was 17836115.

Solution

I split up the solutions for part 1 and part 2. Was almost tempted to go for a numpy and scipy sparse matrix solution but a 1000×1000 matrix is small enough for a dense matrix.

Part 1

# Day 6 - Part 1
import re
lightMatrix = [[False for x in range(1000)] for x in range(1000)] 
lightOnCounter = 0
with open('input.txt') as f:
for line in f:
# Match command
res = re.search(r'(turn on|turn off|toggle)\s*(\d*?),(\d*?)\s*through\s(\d*?),(\d*)', line)
command, lower_X, lower_Y, upper_X, upper_Y =  res.group(1), int(res.group(2)), int(res.group(3)), int(res.group(4)), int(res.group(5))
# Perform actions
toggle = False
if command == 'turn off':
data = False
elif command == 'turn on':
data = True
elif command == 'toggle':
toggle = True
# Apply action
for x_val in xrange (lower_X, upper_X + 1):
for y_val in xrange (lower_Y, upper_Y + 1):
if toggle:
lightMatrix[x_val][y_val] = not lightMatrix[x_val][y_val]
else:
lightMatrix[x_val][y_val] = data
# Get all true lights
for i in lightMatrix:
for isLightOn in i:
lightOnCounter += isLightOn #bool to int implicitly
# answer
print "Total number of lights that are on:", lightOnCounter

# Day 6 - Part 1

import re

lightMatrix = [[False for x in range(1000)] for x in range(1000)]

lightOnCounter = 0

with open('input.txt') as f:

for line in f:

# Match command

res = re.search(r'(turn on|turn off|toggle)\s*(\d*?),(\d*?)\s*through\s(\d*?),(\d*)', line)

command, lower_X, lower_Y, upper_X, upper_Y = res.group(1), int(res.group(2)), int(res.group(3)), int(res.group(4)), int(res.group(5))

# Perform actions

toggle = False

if command == 'turn off':

data = False

elif command == 'turn on':

data = True

elif command == 'toggle':

toggle = True

# Apply action

for x_val in xrange (lower_X, upper_X + 1):

for y_val in xrange (lower_Y, upper_Y + 1):

if toggle:

lightMatrix[x_val][y_val] = not lightMatrix[x_val][y_val]

else:

lightMatrix[x_val][y_val] = data

# Get all true lights

for i in lightMatrix:

for isLightOn in i:

lightOnCounter += isLightOn #bool to int implicitly

# answer

print "Total number of lights that are on:", lightOnCounter

Part 2

# Day 6 - Part 2
import re
lightMatrix = [[0 for x in range(1000)] for x in range(1000)] 
brightnessCounter = 0
with open('input.txt') as f:
for line in f:
# Match command
res = re.search(r'(turn on|turn off|toggle)\s*(\d*?),(\d*?)\s*through\s(\d*?),(\d*)', line)
command, lower_X, lower_Y, upper_X, upper_Y =  res.group(1), int(res.group(2)), int(res.group(3)), int(res.group(4)), int(res.group(5))
# Perform actions
if command == 'turn off':
data = -1
elif command == 'turn on':
data = 1
elif command == 'toggle':
data = 2
# Apply action
for x_val in xrange (lower_X, upper_X + 1):
for y_val in xrange (lower_Y, upper_Y + 1):
lightMatrix[x_val][y_val] += data if lightMatrix[x_val][y_val] + data >= 0 else 0
# Get brightness level
for i in lightMatrix:
for brightness in i:
brightnessCounter += brightness
# answer
print "Total brightness level is:", brightnessCounter

# Day 6 - Part 2

import re

lightMatrix = [[0 for x in range(1000)] for x in range(1000)]

brightnessCounter = 0

with open('input.txt') as f:

for line in f:

# Match command

res = re.search(r'(turn on|turn off|toggle)\s*(\d*?),(\d*?)\s*through\s(\d*?),(\d*)', line)

command, lower_X, lower_Y, upper_X, upper_Y = res.group(1), int(res.group(2)), int(res.group(3)), int(res.group(4)), int(res.group(5))

# Perform actions

if command == 'turn off':

data = -1

elif command == 'turn on':

data = 1

elif command == 'toggle':

data = 2

# Apply action

for x_val in xrange (lower_X, upper_X + 1):

for y_val in xrange (lower_Y, upper_Y + 1):

lightMatrix[x_val][y_val] += data if lightMatrix[x_val][y_val] + data >= 0 else 0

# Get brightness level

for i in lightMatrix:

for brightness in i:

brightnessCounter += brightness

# answer

print "Total brightness level is:", brightnessCounter

No Comments

Posted Mo BeigiPersianMG in Advent Of Code 2015

Advent Of Code 2015: Day 5

05 Dec 2015

CTF: Advent Of Code 2015
Link to challenge: http://adventofcode.com

Date Completed: 05 December 2015

The Challenge

--- Day 5: Doesn't He Have Intern-Elves For This? ---
Santa needs help figuring out which strings in his text file are naughty or nice.
A nice string is one with all of the following properties:
It contains at least three vowels (aeiou only), like aei, xazegov, or aeiouaeiouaeiou.
It contains at least one letter that appears twice in a row, like xx, abcdde (dd), or aabbccdd (aa, bb, cc, or dd).
It does not contain the strings ab, cd, pq, or xy, even if they are part of one of the other requirements.
For example:
ugknbfddgicrmopn is nice because it has at least three vowels (u...i...o...), a double letter (...dd...), and none of the disallowed substrings.
aaa is nice because it has at least three vowels and a double letter, even though the letters used by different rules overlap.
jchzalrnumimnmhp is naughty because it has no double letter.
haegwjzuvuyypxyu is naughty because it contains the string xy.
dvszwmarrgswjxmb is naughty because it contains only one vowel.
How many strings are nice?
--- Part Two ---
Realizing the error of his ways, Santa has switched to a better model of determining whether a string is naughty or nice. None of the old rules apply, as they are all clearly ridiculous.
Now, a nice string is one with all of the following properties:
It contains a pair of any two letters that appears at least twice in the string without overlapping, like xyxy (xy) or aabcdefgaa (aa), but not like aaa (aa, but it overlaps).
It contains at least one letter which repeats with exactly one letter between them, like xyx, abcdefeghi (efe), or even aaa.
For example:
qjhvhtzxzqqjkmpb is nice because is has a pair that appears twice (qj) and a letter that repeats with exactly one letter between them (zxz).
xxyxx is nice because it has a pair that appears twice and a letter that repeats with one between, even though the letters used by each rule overlap.
uurcxstgmygtbstg is naughty because it has a pair (tg) but no repeat with a single letter between them.
ieodomkazucvgmuy is naughty because it has a repeating letter with one between (odo), but no pair that appears twice.
How many strings are nice under these new rules?

--- Day 5: Doesn't He Have Intern-Elves For This? ---

Santa needs help figuring out which strings in his text file are naughty or nice.

A nice string is one with all of the following properties:

It contains at least three vowels (aeiou only), like aei, xazegov, or aeiouaeiouaeiou.

It contains at least one letter that appears twice in a row, like xx, abcdde (dd), or aabbccdd (aa, bb, cc, or dd).

It does not contain the strings ab, cd, pq, or xy, even if they are part of one of the other requirements.

For example:

ugknbfddgicrmopn is nice because it has at least three vowels (u...i...o...), a double letter (...dd...), and none of the disallowed substrings.

aaa is nice because it has at least three vowels and a double letter, even though the letters used by different rules overlap.

jchzalrnumimnmhp is naughty because it has no double letter.

haegwjzuvuyypxyu is naughty because it contains the string xy.

dvszwmarrgswjxmb is naughty because it contains only one vowel.

How many strings are nice?

--- Part Two ---

Realizing the error of his ways, Santa has switched to a better model of determining whether a string is naughty or nice. None of the old rules apply, as they are all clearly ridiculous.

Now, a nice string is one with all of the following properties:

It contains a pair of any two letters that appears at least twice in the string without overlapping, like xyxy (xy) or aabcdefgaa (aa), but not like aaa (aa, but it overlaps).

It contains at least one letter which repeats with exactly one letter between them, like xyx, abcdefeghi (efe), or even aaa.

For example:

qjhvhtzxzqqjkmpb is nice because is has a pair that appears twice (qj) and a letter that repeats with exactly one letter between them (zxz).

xxyxx is nice because it has a pair that appears twice and a letter that repeats with one between, even though the letters used by each rule overlap.

uurcxstgmygtbstg is naughty because it has a pair (tg) but no repeat with a single letter between them.

ieodomkazucvgmuy is naughty because it has a repeating letter with one between (odo), but no pair that appears twice.

How many strings are nice under these new rules?

Solution

Another quick and simple Python solution!

# Day 5 - Parts 1 and 2
import re
nice_counter = 0
improved_nice_counter = 0
naughty_list = ['ab', 'cd', 'pq', 'xy']
def nice_string(str):
if len(re.sub(r'[^aeiou]', '', str)) < 3:
return False
# Appear twice
if not re.search(r'(.)\1', str):
return False
# No naughty words
for nw in naughty_list:
if nw in str:
return False
return True
def improved_nice_string(str):
# Check for double pair
if not re.search(r'(.)(.).*\1\2', str): #some wild boobies appear
return False
# letter repeat
if not re.search(r'(.).\1', str):
return False
return True
with open('input.txt') as f:
for line in f:
if nice_string(line):
nice_counter += 1
if improved_nice_string(line):
improved_nice_counter += 1
# answer
print "Total number of nice strings:", nice_counter
print "Improved total number of nice strings:", improved_nice_counter

# Day 5 - Parts 1 and 2

import re

nice_counter = 0

improved_nice_counter = 0

naughty_list = ['ab', 'cd', 'pq', 'xy']

def nice_string(str):

if len(re.sub(r'[^aeiou]', '', str)) < 3:

return False

# Appear twice

if not re.search(r'(.)\1', str):

return False

# No naughty words

for nw in naughty_list:

if nw in str:

return False

return True

def improved_nice_string(str):

# Check for double pair

if not re.search(r'(.)(.).*\1\2', str): #some wild boobies appear

return False

# letter repeat

if not re.search(r'(.).\1', str):

return False

return True

with open('input.txt') as f:

for line in f:

if nice_string(line):

nice_counter += 1

if improved_nice_string(line):

improved_nice_counter += 1

# answer

print "Total number of nice strings:", nice_counter

print "Improved total number of nice strings:", improved_nice_counter

No Comments

Posted Mo BeigiPersianMG in Advent Of Code 2015

Advent Of Code 2015: Day 4

04 Dec 2015

CTF: Advent Of Code 2015
Link to challenge: http://adventofcode.com

Date Completed: 04 December 2015

The Challenge

--- Day 4: The Ideal Stocking Stuffer ---
Santa needs help mining some AdventCoins (very similar to bitcoins) to use as gifts for all the economically forward-thinking little girls and boys.
To do this, he needs to find MD5 hashes which, in hexadecimal, start with at least five zeroes. The input to the MD5 hash is some secret key (your puzzle input, given below) followed by a number in decimal. To mine AdventCoins, you must find Santa the lowest positive number (no leading zeroes: 1, 2, 3, ...) that produces such a hash.
For example:
If your secret key is abcdef, the answer is 609043, because the MD5 hash of abcdef609043 starts with five zeroes (000001dbbfa...), and it is the lowest such number to do so.
If your secret key is pqrstuv, the lowest number it combines with to make an MD5 hash starting with five zeroes is 1048970; that is, the MD5 hash of pqrstuv1048970 looks like 000006136ef....
Your puzzle answer was 346386.
--- Part Two ---
Now find one that starts with six zeroes.

--- Day 4: The Ideal Stocking Stuffer ---

Santa needs help mining some AdventCoins (very similar to bitcoins) to use as gifts for all the economically forward-thinking little girls and boys.

To do this, he needs to find MD5 hashes which, in hexadecimal, start with at least five zeroes. The input to the MD5 hash is some secret key (your puzzle input, given below) followed by a number in decimal. To mine AdventCoins, you must find Santa the lowest positive number (no leading zeroes: 1, 2, 3, ...) that produces such a hash.

For example:

If your secret key is abcdef, the answer is 609043, because the MD5 hash of abcdef609043 starts with five zeroes (000001dbbfa...), and it is the lowest such number to do so.

If your secret key is pqrstuv, the lowest number it combines with to make an MD5 hash starting with five zeroes is 1048970; that is, the MD5 hash of pqrstuv1048970 looks like 000006136ef....

Your puzzle answer was 346386.

--- Part Two ---

Now find one that starts with six zeroes.

Solution

Because speed was not an issue in this case, I simply used python again to solve the problem. The script is a little slow taking ~10 seconds to compute the answer in my case. A C/C++ solution would be orders of magnitude faster.

# Day 4 - Parts 1 and 2
import hashlib
key = 'iwrupvqb'
i = 0 #counter
five_zero_index = six_zero_index =  0
# Loop until criteria met
while True:
i += 1
hash = hashlib.md5(key + str(i)).hexdigest()
if not five_zero_index and hash.startswith('0' * 5):
five_zero_index = i
if not six_zero_index and hash.startswith('0' * 6):
six_zero_index = i
# exit
if (five_zero_index and six_zero_index):
break
# Print answers
print "Five zero index is:", five_zero_index
print "Six zero index is:", six_zero_index

# Day 4 - Parts 1 and 2

import hashlib

key = 'iwrupvqb'

i = 0 #counter

five_zero_index = six_zero_index = 0

# Loop until criteria met

while True:

i += 1

hash = hashlib.md5(key + str(i)).hexdigest()

if not five_zero_index and hash.startswith('0' * 5):

five_zero_index = i

if not six_zero_index and hash.startswith('0' * 6):

six_zero_index = i

# exit

if (five_zero_index and six_zero_index):

break

# Print answers

print "Five zero index is:", five_zero_index

print "Six zero index is:", six_zero_index

No Comments

Posted Mo BeigiPersianMG in Advent Of Code 2015

Advent Of Code 2015: Day 3

04 Dec 2015

CTF: Advent Of Code 2015
Link to challenge: http://adventofcode.com

Date Completed: 03/12/2015

The Challenge

--- Day 3: Perfectly Spherical Houses in a Vacuum ---
Santa is delivering presents to an infinite two-dimensional grid of houses.
He begins by delivering a present to the house at his starting location, and then an elf at the North Pole calls him via radio and tells him where to move next. Moves are always exactly one house to the north (^), south (v), east (>), or west (<). After each move, he delivers another present to the house at his new location.
However, the elf back at the north pole has had a little too much eggnog, and so his directions are a little off, and Santa ends up visiting some houses more than once. How many houses receive at least one present?
For example:
> delivers presents to 2 houses: one at the starting location, and one to the east.
^>v< delivers presents to 4 houses in a square, including twice to the house at his starting/ending location.
^v^v^v^v^v delivers a bunch of presents to some very lucky children at only 2 houses.
--- Part Two ---
The next year, to speed up the process, Santa creates a robot version of himself, Robo-Santa, to deliver presents with him.
Santa and Robo-Santa start at the same location (delivering two presents to the same starting house), then take turns moving based on instructions from the elf, who is eggnoggedly reading from the same script as the previous year.
This year, how many houses receive at least one present?
For example:
^v delivers presents to 3 houses, because Santa goes north, and then Robo-Santa goes south.
^>v< now delivers presents to 3 houses, and Santa and Robo-Santa end up back where they started.
^v^v^v^v^v now delivers presents to 11 houses, with Santa going one direction and Robo-Santa going the other.

--- Day 3: Perfectly Spherical Houses in a Vacuum ---

Santa is delivering presents to an infinite two-dimensional grid of houses.

He begins by delivering a present to the house at his starting location, and then an elf at the North Pole calls him via radio and tells him where to move next. Moves are always exactly one house to the north (^), south (v), east (>), or west (<). After each move, he delivers another present to the house at his new location.

However, the elf back at the north pole has had a little too much eggnog, and so his directions are a little off, and Santa ends up visiting some houses more than once. How many houses receive at least one present?

For example:

> delivers presents to 2 houses: one at the starting location, and one to the east.

^>v< delivers presents to 4 houses in a square, including twice to the house at his starting/ending location.

^v^v^v^v^v delivers a bunch of presents to some very lucky children at only 2 houses.

--- Part Two ---

The next year, to speed up the process, Santa creates a robot version of himself, Robo-Santa, to deliver presents with him.

Santa and Robo-Santa start at the same location (delivering two presents to the same starting house), then take turns moving based on instructions from the elf, who is eggnoggedly reading from the same script as the previous year.

This year, how many houses receive at least one present?

For example:

^v delivers presents to 3 houses, because Santa goes north, and then Robo-Santa goes south.

^>v< now delivers presents to 3 houses, and Santa and Robo-Santa end up back where they started.

^v^v^v^v^v now delivers presents to 11 houses, with Santa going one direction and Robo-Santa going the other.

Solution

A rather interesting challenge. I wasn’t too happy with my solution but it works.
I split up parts 1 and parts 2 so the code can be read more easily.

Part 1 – Santa Solo Trip

# Day 3 - Part 1
from itertools import product
X = Y = 0
visited = [(0,0)] #(0,0) always visited
unique_houses_visited = 1 #house at (0,0)
with open('input.txt') as f:
for c in f.read():
if c == '^':
Y += 1
elif c == '<':
X -= 1
elif c == 'v':
Y -= 1
elif c == '>':
X += 1
# Check if new house
if (X, Y) not in visited:
# New house
unique_houses_visited += 1
visited.append((X, Y))
#answer      
print "Unique houses visited:", unique_houses_visited

# Day 3 - Part 1

from itertools import product

X = Y = 0

visited = [(0,0)] #(0,0) always visited

unique_houses_visited = 1 #house at (0,0)

with open('input.txt') as f:

for c in f.read():

if c == '^':

Y += 1

elif c == '<':

X -= 1

elif c == 'v':

Y -= 1

elif c == '>':

X += 1

# Check if new house

if (X, Y) not in visited:

# New house

unique_houses_visited += 1

visited.append((X, Y))

#answer

print "Unique houses visited:", unique_houses_visited

Part 2 – Santa + Robo Santa

I didn’t like the use of the santasTurn boolean here too much but couldn’t think of a nicer way to complete the task (in the 15 minutes before I went to sleep!).

# Day 3 - Part 1
from itertools import product
santaX = santaY = 0
roboX = roboY = 0
visited = [(0,0)] #(0,0) always visited
unique_houses_visited = 1 #house at (0,0) visited by Santa and Robo-santa
santasTurn = True
def is_new_house(X, Y, visited):
if (X, Y) not in visited:
# New house
visited.append((X, Y))
return 1
return 0
with open('input.txt') as f:
for c in f.read():
if c == '^':
santaY += int(santasTurn)
roboY += int(not santasTurn)
elif c == '<':
santaX -= int(santasTurn)
roboX -= int(not santasTurn)
elif c == 'v':
santaY -= int(santasTurn)
roboY -= int(not santasTurn)
elif c == '>':
santaX += int(santasTurn)
roboX += int(not santasTurn)
# Check if new house
if santasTurn:
unique_houses_visited += is_new_house(santaX, santaY, visited)
else:
unique_houses_visited += is_new_house(roboX, roboY, visited)
# Swap turns!
santasTurn = not santasTurn
#answer      
print "Unique houses visited:", unique_houses_visited

# Day 3 - Part 1

from itertools import product

santaX = santaY = 0

roboX = roboY = 0

visited = [(0,0)] #(0,0) always visited

unique_houses_visited = 1 #house at (0,0) visited by Santa and Robo-santa

santasTurn = True

def is_new_house(X, Y, visited):

if (X, Y) not in visited:

# New house

visited.append((X, Y))

return 1

return 0

with open('input.txt') as f:

for c in f.read():

if c == '^':

santaY += int(santasTurn)

roboY += int(not santasTurn)

elif c == '<':

santaX -= int(santasTurn)

roboX -= int(not santasTurn)

elif c == 'v':

santaY -= int(santasTurn)

roboY -= int(not santasTurn)

elif c == '>':

santaX += int(santasTurn)

roboX += int(not santasTurn)

# Check if new house

if santasTurn:

unique_houses_visited += is_new_house(santaX, santaY, visited)

else:

unique_houses_visited += is_new_house(roboX, roboY, visited)

# Swap turns!

santasTurn = not santasTurn

#answer

print "Unique houses visited:", unique_houses_visited

No Comments

Posted Mo BeigiPersianMG in Advent Of Code 2015

Advent Of Code 2015: Day 2

02 Dec 2015

CTF: Advent Of Code 2015
Link to challenge: http://adventofcode.com

Date Completed: 02/12/2015

The Challenge

--- Day 2: I Was Told There Would Be No Math ---
The elves are running low on wrapping paper, and so they need to submit an order for more. They have a list of the dimensions (length l, width w, and height h) of each present, and only want to order exactly as much as they need.
Fortunately, every present is a box (a perfect right rectangular prism), which makes calculating the required wrapping paper for each gift a little easier: find the surface area of the box, which is 2*l*w + 2*w*h + 2*h*l. The elves also need a little extra paper for each present: the area of the smallest side.
For example:
A present with dimensions 2x3x4 requires 2*6 + 2*12 + 2*8 = 52 square feet of wrapping paper plus 6 square feet of slack, for a total of 58 square feet.
A present with dimensions 1x1x10 requires 2*1 + 2*10 + 2*10 = 42 square feet of wrapping paper plus 1 square foot of slack, for a total of 43 square feet.
All numbers in the elves' list are in feet. How many total square feet of wrapping paper should they order?
--- Part Two ---
The elves are also running low on ribbon. Ribbon is all the same width, so they only have to worry about the length they need to order, which they would again like to be exact.
The ribbon required to wrap a present is the shortest distance around its sides, or the smallest perimeter of any one face. Each present also requires a bow made out of ribbon as well; the feet of ribbon required for the perfect bow is equal to the cubic feet of volume of the present. Don't ask how they tie the bow, though; they'll never tell.
For example:
A present with dimensions 2x3x4 requires 2+2+3+3 = 10 feet of ribbon to wrap the present plus 2*3*4 = 24 feet of ribbon for the bow, for a total of 34 feet.
A present with dimensions 1x1x10 requires 1+1+1+1 = 4 feet of ribbon to wrap the present plus 1*1*10 = 10 feet of ribbon for the bow, for a total of 14 feet.
How many total feet of ribbon should they order?

--- Day 2: I Was Told There Would Be No Math ---

The elves are running low on wrapping paper, and so they need to submit an order for more. They have a list of the dimensions (length l, width w, and height h) of each present, and only want to order exactly as much as they need.

Fortunately, every present is a box (a perfect right rectangular prism), which makes calculating the required wrapping paper for each gift a little easier: find the surface area of the box, which is 2*l*w + 2*w*h + 2*h*l. The elves also need a little extra paper for each present: the area of the smallest side.

For example:

A present with dimensions 2x3x4 requires 2*6 + 2*12 + 2*8 = 52 square feet of wrapping paper plus 6 square feet of slack, for a total of 58 square feet.

A present with dimensions 1x1x10 requires 2*1 + 2*10 + 2*10 = 42 square feet of wrapping paper plus 1 square foot of slack, for a total of 43 square feet.

All numbers in the elves' list are in feet. How many total square feet of wrapping paper should they order?

--- Part Two ---

The elves are also running low on ribbon. Ribbon is all the same width, so they only have to worry about the length they need to order, which they would again like to be exact.

The ribbon required to wrap a present is the shortest distance around its sides, or the smallest perimeter of any one face. Each present also requires a bow made out of ribbon as well; the feet of ribbon required for the perfect bow is equal to the cubic feet of volume of the present. Don't ask how they tie the bow, though; they'll never tell.

For example:

A present with dimensions 2x3x4 requires 2+2+3+3 = 10 feet of ribbon to wrap the present plus 2*3*4 = 24 feet of ribbon for the bow, for a total of 34 feet.

A present with dimensions 1x1x10 requires 1+1+1+1 = 4 feet of ribbon to wrap the present plus 1*1*10 = 10 feet of ribbon for the bow, for a total of 14 feet.

How many total feet of ribbon should they order?

Solution

This challenge was very simple. I whipped up a short python script that solves it. The use of sorted to get the second smallest integer is not pretty but insignificant with such small numbers.

# Day 2 - Part 1 and 2
with open('input.txt') as f:
lines = f.readlines()
totalPaper = 0
totalRibbon = 0
for line in lines:
l,w,h = map(int, line.split('x'))
totalPaper += (2*l*w + 2*w*h + 2*h*l) + min(l*w, w*h, h*l)
totalRibbon += min(l,w,h)*2 + sorted([l,w,h])[1] * 2 + (l*w*h)
# answers
print "Total wrapping paper needed:", totalPaper
print "Total ribbon needed:", totalRibbon

# Day 2 - Part 1 and 2

with open('input.txt') as f:

lines = f.readlines()

totalPaper = 0

totalRibbon = 0

for line in lines:

l,w,h = map(int, line.split('x'))

totalPaper += (2*l*w + 2*w*h + 2*h*l) + min(l*w, w*h, h*l)

totalRibbon += min(l,w,h)*2 + sorted([l,w,h])[1] * 2 + (l*w*h)

# answers

print "Total wrapping paper needed:", totalPaper

print "Total ribbon needed:", totalRibbon

No Comments

Posted Mo BeigiPersianMG in Advent Of Code 2015

Advent Of Code 2015: Day 1

02 Dec 2015

CTF: Advent Of Code 2015
Link to challenge: http://adventofcode.com

Date Completed: 01/12/2015

The Challenge

--- Day 1: Not Quite Lisp ---
Santa was hoping for a white Christmas, but his weather machine's "snow" function is powered by stars, and he's fresh out! To save Christmas, he needs you to collect fifty stars by December 25th.
Collect stars by helping Santa solve puzzles. Two puzzles will be made available on each day in the advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!
Here's an easy puzzle to warm you up.
Santa is trying to deliver presents in a large apartment building, but he can't find the right floor - the directions he got are a little confusing. He starts on the ground floor (floor 0) and then follows the instructions one character at a time.
An opening parenthesis, (, means he should go up one floor, and a closing parenthesis, ), means he should go down one floor.
The apartment building is very tall, and the basement is very deep; he will never find the top or bottom floors.
For example:
(()) and ()() both result in floor 0.
((( and (()(()( both result in floor 3.
))((((( also results in floor 3.
()) and ))( both result in floor -1 (the first basement level).
))) and )())()) both result in floor -3.
To what floor do the instructions take Santa?
--- Part Two ---
Now, given the same instructions, find the position of the first character that causes him to enter the basement (floor -1). The first character in the instructions has position 1, the second character has position 2, and so on.
For example:
) causes him to enter the basement at character position 1.
()()) causes him to enter the basement at character position 5.
What is the position of the character that causes Santa to first enter the basement?

--- Day 1: Not Quite Lisp ---

Santa was hoping for a white Christmas, but his weather machine's "snow" function is powered by stars, and he's fresh out! To save Christmas, he needs you to collect fifty stars by December 25th.

Collect stars by helping Santa solve puzzles. Two puzzles will be made available on each day in the advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!

Here's an easy puzzle to warm you up.

Santa is trying to deliver presents in a large apartment building, but he can't find the right floor - the directions he got are a little confusing. He starts on the ground floor (floor 0) and then follows the instructions one character at a time.

An opening parenthesis, (, means he should go up one floor, and a closing parenthesis, ), means he should go down one floor.

The apartment building is very tall, and the basement is very deep; he will never find the top or bottom floors.

For example:

(()) and ()() both result in floor 0.

((( and (()(()( both result in floor 3.

))((((( also results in floor 3.

()) and ))( both result in floor -1 (the first basement level).

))) and )())()) both result in floor -3.

To what floor do the instructions take Santa?

--- Part Two ---

Now, given the same instructions, find the position of the first character that causes him to enter the basement (floor -1). The first character in the instructions has position 1, the second character has position 2, and so on.

For example:

) causes him to enter the basement at character position 1.

()()) causes him to enter the basement at character position 5.

What is the position of the character that causes Santa to first enter the basement?

Solution

Before part 2 of the problem was revealed I decided to tackle the problem using the command line. I cam up with the following command:

# Day 1 - Part 1
echo $((`cat input.txt | tr -d '\)' | wc -c` - `cat input.txt | tr -d '\(' | wc -c`))

1 2	# Day 1 - Part 1 echo $((`cat input.txt \| tr -d '\)' \| wc -c` - `cat input.txt \| tr -d '\(' \| wc -c`))

We echo the input and remove the ) symbol which leaves only ( and we use wc to count the number of ( symbols which tells us how many times we went to a higher floor. We then subtract his number from the number of times we went to a lower floor (using bash arithmetic) which gives us our answer.

Part 2 of the problem would be annoying to do on the command line so I decided to write a quick python script to solve it. The solution also solves the first part of the problem (lol).

counter = 0
level = 0
basement_pos = 1
basement_found = False
with open("input.txt", "r") as file:
for line in file:
for c in line:
if c == ')':
level -= 1
elif c == '(':
level += 1
counter += 1
# Check if in basement
if (level < 0 and not basement_found):
basement_pos = counter
basement_found = True
# Conclusion (we did part 1 too lol)
print "Final level:", level
print "First basement level position:", basement_pos

counter = 0

level = 0

basement_pos = 1

basement_found = False

with open("input.txt", "r") as file:

for line in file:

for c in line:

if c == ')':

level -= 1

elif c == '(':

level += 1

counter += 1

# Check if in basement

if (level < 0 and not basement_found):

basement_pos = counter

basement_found = True

# Conclusion (we did part 1 too lol)

print "Final level:", level

print "First basement level position:", basement_pos

No Comments

Posted Mo BeigiPersianMG in Advent Of Code 2015

Mo Beigi

Archive for the ‘Advent Of Code’ Category

Advent Of Code 2015: Day 8

Challenge

Solution

Advent Of Code 2015: Day 7

Challenge

Solution

Advent Of Code 2015: Day 6

The Challenge

Solution

Part 1

Part 2

Advent Of Code 2015: Day 5

The Challenge

Solution

Advent Of Code 2015: Day 4

The Challenge

Solution

Advent Of Code 2015: Day 3

The Challenge

Solution

Part 1 – Santa Solo Trip

Part 2 – Santa + Robo Santa

Advent Of Code 2015: Day 2

The Challenge

Solution

Advent Of Code 2015: Day 1

The Challenge

Solution

Pages

Recent Posts

Recent Comments

My Networks

Site Stats