Learn how to program with Python #3 - Solving Puzzles from Advent of Code 2018

banner.png


Repository

https://github.com/python

What will I learn

  • Findall
  • 2D list
  • Sets

Requirements

Difficulty

  • basic

Tutorial

Preface

This tutorial is part of a course where solutions to puzzles from Advent of Code 2018 are discussed to explain programming techniques using Python. Each puzzle contains two parts and comes with user specific inputs. It is recommended to try out the puzzle first before going over the tutorial. Puzzles are a great and fun way to learn about programming.

While the puzzles start of relatively easy and get more difficult over time. Basic programming understanding is required. Such as the different type of variables, lists, dicts, functions and loops etc. A course like Learn Python2 from Codeacademy should be sufficient. Even though the course is for Python two, while Python 3 is used.

This tutorial will look at puzzle 3

The code for this tutorial can be found on Github!

Part one

How many square inches of fabric are within two or more claims?

This puzzle comes with a list claims that come with a x, y coordinates and the size of a grid.

#1 @ 1,3: 4x4
#2 @ 3,1: 4x4
#3 @ 5,5: 2x2

These claims can be plotted in a grid. An x represents a field with multiple claims.

........
...2222.
...2222.
.11XX22.
.11XX22.
.111133.
.111133.
........


The whole piece of fabric they're working on is a very large square - at least 1000 inches on each side.

This puzzle can be solved by creating a grid of at least 1000x1000 and going over the claims. Then going over each field to see if there are more than 1 claims.

findall

The input for this puzzle is more complicated than seen so far. Te retrieve all the numbers from each line a regular expression can be used in combination with findall(). A regular expression defines a search pattern, in this case to search for any numbers of any length r'\d+' is used. Where \d represents a digit and + specifies any length, r in front of the string makes it a regular expression. More information about regular expressions can be found here.

# read input file and convert to list
import re

with open('input.txt', 'r') as file:
    lines = list(file)

    for line in lines:
        id, x, y, w, h = map(int, re.findall(r'\d+', line))

2D list

The field can be represented by a two dimensional list. Which is a list of lists. Accessing the list is done by using both indexes. For example list[x][y]. Creating the list is done by using a list comprehension. In this example an empty list is set for each field in the grid.

# create 2d list of empty lists
field_w, field_h = 1000, 1000
field = [[[] for x in range(field_w)] for y in range(field_h)]



The 2D list is then filled by going over each line from the input. The coordinates for the the fields inside the grid are calculated by taking the start coordinates x and y and adding the height h and width w to them.

# go over each input line, extracts numbers
# by using a regular expression.
for line in lines:
    id, x, y, w, h = map(int, re.findall(r'\d+', line))

    # use starting coordinates x, y with grid
    # size w, h to add the id to the correct field
    for a in range(y, y + h):
        for b in range(x, x + w):
            field[a][b].append(id)

The amount of fields that contain more than one id is calculated by going over each field in the grid.

# loop through entire 2d list to count 
# which fields hold more than 1 id
multiple_claims = 0
for a in range(0, field_h):
    for b in range(0, field_h):
        if len(field[a][b]) > 1:
            multiple_claims += 1

This can also be achieved with a one liner by using a list comprehension.

sum([sum([len(field[x][y]) > 1 for x in range(field_w)]) for y in range(field_h)]))



This list comprehension creates a list with Booleans for each x value. From this list the sum is taken and put into a list for each y value. Again the sum is taken returning the total. True has the value of 1 and False of 0 when taking the sum of Booleans.

Part two

What is the ID of the only claim that doesn't overlap?

This puzzle can be solved by using sets. One set that contains all the ids and another set that invalid ids. That is for fields that contain more than one id. Subtracting the invalid ids set from the all ids set results in the valid id.

Sets

Sets are unordered collections of unique variables. This means that adding a variable to a set that already contains this variable does not expand the set. Also different sets with the same variables but a different order are equal. Furthermore - operations work on sets.

Apr-08-2019 04-33-39.gif

# sets
all = set()
invalid = set()

# loop through all fields in the grid
for a in range(0, len(field)):
    for b in range(0, len(field[0])):
        # add each id to all set
        for id in field[a][b]:
            all.add(id)
        # for each field that contains more than
        # 1 id add id to invalid set
        if len(field[a][b]) > 1:
            for id in field[a][b]:
                invalid.add(id)

# subtracts invalid ids set from all ids set
return (all-invalid)

Running the code

Run the code with: python main.py

if __name__ == "__main__":
    # read input file and convert to list
    with open('input.txt', 'r') as file:
        lines = list(file)

    field = create_field(lines)

    print(f'Part 1 Answer: {part_1(field)}')
    print(f'Part 2 Answer: {part_2(field)}')

Apr-08-2019 04-50-41.gif

Curriculum

Part 1, Part 2


The code for this tutorial can be found on Github!

This tutorial was written by @juliank.

Sort:  

Thank you for your contribution!

  • It is always intriguing to try and solve puzzles with coding. Thumbs up for that!
  • A short intro about the puzzle itself would have helped, in addition to the link to the puzzle original source. It disrupts the reader a bit.
  • I liked how low level your explanations were. Very helpful for starters.
  • A short description about the results prior to displaying your output would have been helpful as well.
  • You had few minor typos across your text. Titles could have been slightly more elaborate, such as your use of just findall and Sets.
    Overall, good job!

Your contribution has been evaluated according to Utopian policies and guidelines, as well as a predefined set of questions pertaining to the category.

To view those questions and the relevant answers related to your post, click here.


Need help? Chat with us on Discord.

[utopian-moderator]

Thanks for the feedback @mcfarhat

Thank you for your review, @mcfarhat! Keep up the good work!

Hi @steempytutorials!

Your post was upvoted by @steem-ua, new Steem dApp, using UserAuthority for algorithmic post curation!
Your post is eligible for our upvote, thanks to our collaboration with @utopian-io!
Feel free to join our @steem-ua Discord server

Hi, @steempytutorials!

You just got a 0.42% upvote from SteemPlus!
To get higher upvotes, earn more SteemPlus Points (SPP). On your Steemit wallet, check your SPP balance and click on "How to earn SPP?" to find out all the ways to earn.
If you're not using SteemPlus yet, please check our last posts in here to see the many ways in which SteemPlus can improve your Steem experience on Steemit and Busy.

Hey, @steempytutorials!

Thanks for contributing on Utopian.
We’re already looking forward to your next contribution!

Get higher incentives and support Utopian.io!
Simply set @utopian.pay as a 5% (or higher) payout beneficiary on your contribution post (via SteemPlus or Steeditor).

Want to chat? Join us on Discord https://discord.gg/h52nFrV.

Vote for Utopian Witness!