Category: What I’m Up To

Categories
Programming Tampa Bay What I’m Up To

Tampa iOS Meetup is changing its name to “Programmers of Portables” (or PoP for short)!

It’s been way too long since I’ve held a Tampa iOS Meetup. Between the pandemic and all sorts of employment issues arising thanks to the pandemic, I managed to hold just one Tampa iOS Meetup in 2020. It’s a shame, especially since Tampa iOS Meetup made the list of Tampa’s top ten tech meetup groups for 2019.

At the same time, while I’ve wanted to keep covering iOS, I also wanted to expand into other portable platforms, namely programming Android, smart watches, Raspberry Pi, and Arduino devices.

I’m going to scratch these two itches by re-tooling Tampa iOS Meetup into a new meetup called Programmers of Portables, or PoP for short. If you want to know what kind of platforms and programming this meetup will cover, just read its motto: “If it fits in your hand, it’s on-brand!”

Some of the topics I’m planning for this year:

  • iOS and watchOS programming with Swift
  • Android programming with Kotlin
  • Cross-platform mobile programming with Flutter
  • Raspberry Pi programming with Python
  • Arduino programming with Arduino’s C-like programming language
  • Wearables (after all, “portable” is related to the French verb porter, which means “to wear”)

I’m going to keep the beginner-friendly focus with this revamped meetup, but don’t let “beginner-friendly” fool you into thinking that it means “simple”! In some  of my “beginner-friendly” classes, we wrote:

  • Our own version of Frogger,
  • the iPhone version of Google’s Tilt Brush, the 3-D AR “paint” application
  • our own version of the IKEA Place AR app,
  • a machine learning app that tried to identify common objects,
  • a machine learning app that tried to identify the kind of room your were in, and
  • a machine learning app that could identify various members of the Avengers.

My plan is to return to regular meetups, which will be Zoom-based until the pandemic gets under control.

I’ll announce the first meetup shortly. In the meantime, let me know what topics you’d like me to cover at PoP. You can do it in the comments for this post, or on my Twitter or LinkedIn accounts.

Categories
Programming What I’m Up To

My solution to Advent of Code 2020’s Day 8 challenge, in Python

Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!

In this installment, I share my Python solution to Day 8 of Advent of Code, titled Handheld Halting.

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 8 challenge.

The Day 8 challenge, part one

The Kittenbot Meowbit handheld game console. Tap to find out more.

The challenge

Here’s the text from part one of the challenge:

Your flight to the major airline hub reaches cruising altitude without incident. While you consider checking the in-flight menu for one of those drinks that come with a little umbrella, you are interrupted by the kid sitting next to you.

Their handheld game console won’t turn on! They ask if you can take a look.

You narrow the problem down to a strange infinite loop in the boot code (your puzzle input) of the device. You should be able to fix it, but first you need to be able to run the code in isolation.

The boot code is represented as a text file with one instruction per line of text. Each instruction consists of an operation (acc, jmp, or nop) and an argument (a signed number like +4 or -20).

  • acc increases or decreases a single global value called the accumulator by the value given in the argument. For example, acc +7 would increase the accumulator by 7. The accumulator starts at 0. After an acc instruction, the instruction immediately below it is executed next.
  • jmp jumps to a new instruction relative to itself. The next instruction to execute is found using the argument as an offset from the jmp instruction; for example, jmp +2 would skip the next instruction, jmp +1 would continue to the instruction immediately below it, and jmp -20 would cause the instruction 20 lines above to be executed next.
  • nop stands for No OPeration – it does nothing. The instruction immediately below it is executed next.

For example, consider the following program:

These instructions are visited in this order:

First, the nop +0 does nothing. Then, the accumulator is increased from 0 to 1 (acc +1) and jmp +4 sets the next instruction to the other acc +1 near the bottom. After it increases the accumulator from 1 to 2, jmp -4 executes, setting the next instruction to the only acc +3. It sets the accumulator to 5, and jmp -3 causes the program to continue back at the first acc +1.

This is an infinite loop: with this sequence of jumps, the program will run forever. The moment the program tries to run any instruction a second time, you know it will never terminate.

Immediately before the program would run an instruction a second time, the value in the accumulator is 5.

Run your copy of the boot code. Immediately before any instruction is executed a second time, what value is in the accumulator?

Importing the data

Every Advent of Code participant gets their own set of data. I copied my data and went through my usual process of bringing it into a Jupyter Notebook running a Python kernel.

This involves pasting it into a triple-quoted string and then assigning its value to the variable main_raw_input:

Building the data structure

With the data imported, the next step was to build an appropriate data structure. Since today’s puzzle was based on simplified microprocessor instructions, I thought that the data structure should do the same.

I wanted my data structure to look like the table below, which shows the instructions from extracted from the first five lines of the data given to me:

Index Opcode Operand
0 acc 37
1 acc -4
2 nop 405
3 jmp 276
4 acc 39

Here’s the function that I wrote to convert the input data into the data structure:

With the function defined, here’s how I used it to create the data structure, which I assigned to a variable named instructions:

I then wrote accumulator_value_at_first_repeat(), the function that would use the data structure contained within instructions to solve the first challenge:

When run, it sets up the following variables:

  • program_length: The number of instructions in the data structure.
  • program_counter: The program’s equivalent of the “program counter (PC)” register in a microprocessor; contains the index the instruction to be executed.
  • accumulator: The program’s equivalent of an accumulator in a microprocessor. For those of you who aren’t familiar with what happens at the microprocessor level, think of the accumulator as a “scratchpad” variable where you do all the math.
  • executed_instructions: A set (which means that every value in it is unique) of the indices of all the instructions that have already been executed. We use it to determine if a given instruction has already been run, at which point we should stop the program and see what the value in the accumulator is.
  • repeat_instruction_encountered: A flag that should be set to True when an instruction is about to be executed a second time.

The function’s main loop performs a greatly simplified version of a microprocessor’s “fetch-decode-execute” cycle:

  1. Fetch the current instruction, which is the one whose index is specified by program_counter.
  2. See if the instruction has been executed before. If this is the case, exit the loop; otherwise, recording this instruction as having been executed.
  3. Decode the current instruction:
    • If the instruction is jmp, add the operand value to program_counter and go back to the start of the loop.
    • If the instruction is acc, add the operand value to accumulator.
    • If the instruction is nop, do nothing.
    • If the instruction is anything else, display an error message.
  4. After the loop is done, if the repeat_instruction_encountered flag is set, we’ve found the value we’re looking for — display it! Otherwise, display a message saying that we’ve reached the end of the instructions without ever repeating one.

I ran the function…

…and got my result: 1801.

The Day 8 challenge, part two

The TinkerGen GameGo programmable handheld game console. Tap to find out more!

The challenge

After some careful analysis, you believe that exactly one instruction is corrupted.

Somewhere in the program, either a jmp is supposed to be a nop, or a nop is supposed to be a jmp. (No acc instructions were harmed in the corruption of this boot code.)

The program is supposed to terminate by attempting to execute an instruction immediately after the last instruction in the file. By changing exactly one jmp or nop, you can repair the boot code and make it terminate correctly.

For example, consider the same program from above:

If you change the first instruction from nop +0 to jmp +0, it would create a single-instruction infinite loop, never leaving that instruction. If you change almost any of the jmp instructions, the program will still eventually find another jmp instruction and loop forever.

However, if you change the second-to-last instruction (from jmp -4 to nop -4), the program terminates! The instructions are visited in this order:

After the last instruction (acc +6), the program terminates by attempting to run the instruction below the last instruction in the file. With this change, after the program terminates, the accumulator contains the value 8 (acc +1, acc +1, acc +6).

Fix the program so that it terminates normally by changing exactly one jmp (to nop) or nop (to jmp). What is the value of the accumulator after the program terminates?

Here’s the function I wrote to solve this challenge:

The function, accumulator_value_and_halt_at_first_repeat(), is an expanded version of the function from part one, accumulator_value_at_first_repeat().

In addition to a set of instructions, it takes an additional parameter: the address of an instruction that should be changed — either from jmp to nop, or from nop to jmp.

The function still performs the “fetch-decode-execute” loop, and it exits the loop if it’s about to execute an instruction that’s already been executed. The main difference is that if the current instruction is the one flagged for change, it changes the instruction appropriately.

I wrote the accumulator_value_and_halt_at_first_repeat() function to be used by the function below:

This function goes through all the instructions in the set, looking for any jmp or nop instructions. When it finds one, it runs the program using accumulator_value_and_halt_at_first_repeat(), marking the jmp or nop instruction as the one to be changed.

This lets us modify the program, one jmp or nop instruction at a time, in order to find which change to a jmp or nop instruction is the one that allows the program to reach the end of the instructions.

Here’s an abridged version of what happened when I ran the function:

I entered 2060 as my answer, and step two was complete.

Solutions for other days in Advent of Code 2020

Categories
Programming What I’m Up To

My solution to Advent of Code 2020’s Day 7 challenge, in Python

Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!

In this installment, I share my Python solution to Day 7 of Advent of Code, titled Handy Haversacks.

The Day 7 challenge, part one

The challenge

Here’s the text from part one of the challenge:

You land at the regional airport in time for your next flight. In fact, it looks like you’ll even have time to grab some food: all flights are currently delayed due to issues in luggage processing.

Due to recent aviation regulations, many rules (your puzzle input) are being enforced about bags and their contents; bags must be color-coded and must contain specific quantities of other color-coded bags. Apparently, nobody responsible for these regulations considered how long they would take to enforce!

For example, consider the following rules:

These rules specify the required contents for 9 bag types. In this example, every faded blue bag is empty, every vibrant plum bag contains 11 bags (5 faded blue and 6 dotted black), and so on.

You have a shiny gold bag. If you wanted to carry it in at least one other bag, how many different bag colors would be valid for the outermost bag? (In other words: how many colors can, eventually, contain at least one shiny gold bag?)

In the above rules, the following options would be available to you:

  • A bright white bag, which can hold your shiny gold bag directly.
  • A muted yellow bag, which can hold your shiny gold bag directly, plus some other bags.
  • A dark orange bag, which can hold bright white and muted yellow bags, either of which could then hold your shiny gold bag.
  • A light red bag, which can hold bright white and muted yellow bags, either of which could then hold your shiny gold bag.

So, in this example, the number of bag colors that can eventually contain at least one shiny gold bag is 4.

How many bag colors can eventually contain at least one shiny gold bag? (The list of rules is quite long; make sure you get all of it.)

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 7 challenge.

Importing the data

Every Advent of Code participant gets their own set of data. I copied my data and went through my usual process of bringing it into a Jupyter Notebook running a Python kernel.

This involves pasting it into a triple-quoted string and then using Python’s splitlines() method to break it up into a list of strings. The result is main_raw_input:

Creating the data structure

I feel that I can never stress this enough: A key part of coming up with solutions to Advent of Code challenges is to come up with good structures for the input data.

Here’s my function that takes the initial, somewhat-massaged input data, currently living in main_raw_input, and turns it into a data structure that I could do some problem-solving with:

The create_data_structure() function creates a table that makes it easy to look up a given bag and see what bags it contains.

It takes each line in the input, which follows this general form:

[adjective and color] bags contain [one or more of
([number][adjective and color]bag(s)).

It first makes use of this regular expression…

…to separate the line into two parts:

  • The containing bag, which is captured by the (\w+ \w+) group, and
  • The contained bag(s), which are captured by the (.*) group.

The contained bag(s) are further parsed using this regular expression…

…to create a list of tuples of the form:

Here’s how I used create_data_structure() to create the data structure:

Here’s a sample of the what the structure looked like for my data:

With the data structure built, it was now possible to write a function to determine how many shiny gold bags a given bag would contain:

It’s the return of our friend:

This function checks the contents of the given bag. If there are bags in the given bag, it checks the contents of those bags and counts the shiny gold ones. If there are bags in those bags, it checks the contents of those bags and counts the shiny gold ones. And so on…

Now that I had the shiny_gold_bag_count() function, I could write another function — bags_containing_at_least_one_shiny_gold_bag() — that would apply the shiny_gold_bag_count() function to all the bags in the collection, giving me the answer to the part one:

In my case, the count was 326.

The Day 7 challenge, part two

Creative Commons photo by “Sunnya343”. Tap to view the source.

The challenge

Here’s the text of part two:

It’s getting pretty expensive to fly these days – not because of ticket prices, but because of the ridiculous number of bags you need to buy!

Consider again your shiny gold bag and the rules from the above example:

  • faded blue bags contain 0 other bags.
  • dotted black bags contain 0 other bags.
  • vibrant plum bags contain 11 other bags: 5 faded blue bags and 6 dotted black bags.
  • dark olive bags contain 7 other bags: 3 faded blue bags and 4 dotted black bags.

So, a single shiny gold bag must contain 1 dark olive bag (and the 7 bags within it) plus 2 vibrant plum bags (and the 11 bags within each of those): 1 + 1*7 + 2 + 2*11 = 32 bags!

Of course, the actual rules have a small chance of going several levels deeper than this example; be sure to count all of the bags, even if the nesting becomes topologically impractical!

Here’s another example:

In this example, a single shiny gold bag must contain 126 other bags.

How many individual bags are required inside your single shiny gold bag?

My solution was the following function:

Once again, my solution was a recursive one. This function checks the contents of the given bag. If there are bags in the given bag, it counts them and then checks their contents. If there are bags in those bags, it counts them and checks their contents. And so on…

Getting the solution was a matter of calling the function:

And for my data, the answer was 5635.

Solutions for previous days in Advent of Code 2020

Categories
Programming What I’m Up To

My solution to Advent of Code 2020’s Day 6 challenge, in Python

Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!

In this installment, I share my Python solution to Day 6 of Advent of Code, titled Custom Customs.

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 6 challenge.

The Day 6 challenge, part one

The challenge

Here’s the text from part one of the challenge:

As your flight approaches the regional airport where you’ll switch to a much larger plane, customs declaration forms are distributed to the passengers.

The form asks a series of 26 yes-or-no questions marked a through z. All you need to do is identify the questions for which anyone in your group answers “yes”. Since your group is just you, this doesn’t take very long.

However, the person sitting next to you seems to be experiencing a language barrier and asks if you can help. For each of the people in their group, you write down the questions for which they answer “yes”, one per line. For example:

In this group, there are 6 questions to which anyone answered “yes”: a, b, c, x, y, and z. (Duplicate answers to the same question don’t count extra; each question counts at most once.)

Another group asks for your help, then another, and eventually you’ve collected answers from every group on the plane (your puzzle input). Each group’s answers are separated by a blank line, and within each group, each person’s answers are on a single line. For example:

This list represents answers from five groups:

  • The first group contains one person who answered “yes” to 3 questions: a, b, and c.
  • The second group contains three people; combined, they answered “yes” to 3 questions: a, b, and c.
  • The third group contains two people; combined, they answered “yes” to 3 questions: a, b, and c.
  • The fourth group contains four people; combined, they answered “yes” to only 1 question, a.
  • The last group contains one person who answered “yes” to only 1 question, b.

In this example, the sum of these counts is 3 + 3 + 3 + 1 + 1 = 11.

For each group, count the number of questions to which anyone answered “yes”. What is the sum of those counts?

Importing the data

Every Advent of Code participant gets their own set of data. I copied my data and went through my usual process of bringing it into a Jupyter Notebook running a Python kernel.

This involves pasting it into a triple-quoted string and assigning it to the variable raw_input, and then splitting it using two newline characters in a row as a delimiter, producing a list named split_input: