Programming Update for April 2021
EricMesa
- 10 minutes read - 2005 wordsI had a lot less variety in my programming month, but still had a lot of fun doing it. In fact, Programming consumed most of my leisure thoughts. More about why I was doing it below, but I’ve been reading Programming Perl as well as skimming through Introducing Go and Learn You A Haskell for Great Good!. Ever since some folks used Haskell during last year’s Advent of Code and this guy’s videos that I mentioned in an early 2021 blog post, I’ve been very curious about the language. In fact, at this point I’ve decided that Go and Haskell will be the next two languages I learn.
Python
I continued working on the Django app I’m making for a friend. I finally started to get the hang of how Django works, especially when passing information around in the app. I got to a minimal viable product (MVP) in April, but I’m hoping to finally get a 1.0 that meets all his needs within the first couple weeks of May.
Advent of Code 2015 Problem Set
So the activity that gave me the most fun in April was working through the 2015 Advent of Code problem set. I chose to use it to cement my understanding of Ruby, which I learned in 2020. But that wasn’t enough for me on its own. I decided to also solve each problem with Perl. I tried learning Perl for the second time about a decade ago. I ended up abandoning it for Python when I wanted to contribute to GRAMPS, which was written in Python. So I had some understanding of the strange sigils before the different types of variables, but I didn’t have a great understanding of the more complicated things that could be done with Perl. There’s also something I haven’t mentioned in this blog in a long time, but I think sometimes we come across knowledge before we’re ready for it. This isn’t some mystical woo-woo thing. It’s just a fact, sometimes you don’t have the underlying knowledge necessary to take advantage of new knowledge that you’re being presented with. A great example is hashes. I just couldn’t truly get my mind around it at the time (10 years or so ago). But now that I’ve done a ton of work with Python dictionaries, I realize they’re the same thing and hashes make sense to me now.
I’ve been extra happy in the fact that, by the end of April I had reached Advent of Code Day 10 and hadn’t had to skip any days. Yes, there were a couple days during the 2020 event where I skipped an entire problem or part 2 of a problem because I ran out of time, but I also had to skip a few problems because I had no idea how to solve them. So far that hasn’t happened with the 2015 problem set. I wanted to draw attention to some of the things I learned so far thanks to AoC 2015.
require "../../input_parsing/parse_input"
def parse_directions(parenthesis)
floor = 0
parenthesis.each do |paren|
if paren == "("
floor += 1
elsif paren == ")"
floor -= 1
end
end
return floor
end
input_text = input_per_line('../input.txt')
puts parse_directions(input_text[0].split(//))
For my Day 1 entry to Ruby, I just practiced going over arrays with each. I also used string.split(//) to split the text into an array of each character. I made a comment on Reddit and someone suggested a more Rubyist solution:
require "../../input_parsing/parse_input"
def parse_directions(parenthesis)
parenthesis.reduce(0) do | floor, paren |
if paren == "("
floor + 1
elsif paren == ")"
floor - 1
end
end
end
input_text = input_per_line('../input.txt')
puts parse_directions(input_text[0].split(//))
This simplifies the code by eliminating the need to initialize the floor variable to sum things up. Instead it becomes the input for an array that is reduced. (I would make more use of reduce later in 2015)
Day 2
Just last year I started learning about what map and reduce mean in computer science. Such is the situation for someone who is primarily self-taught. Turns out that a pretty big chunk of Advent of Code (and other programming challenges) solutions can be summed up as map, filter, reduce. Of course, that hides the fact that figuring out the map and filter functions is often the whole point of the challenge. Day 2’s Ruby code was the first time I explicitly used map (see line 5 where I convert all the array members to integers) in any language (although a Python list comprehension is almost always an implicit map or filter)
require "../../input_parsing/parse_input"
def get_dimensions(dimension_line)
dimensions = dimension_line.split('x')
dimensions.map(&:to_i)
end
def calculate_box_area(dimensions)
2*dimensions[0]*dimensions[1] + 2*dimensions[1]*dimensions[2] + 2*dimensions[0]*dimensio
ns[2]
end
def calculate_small_area(dimensions)
sorted_dimensions = dimensions.sort
small_area = sorted_dimensions[0] * sorted_dimensions[1]
end
input_text = input_per_line('../input.txt')
all_box_areas = []
all_small_areas = []
input_text.each do |box|
all_box_areas.append(calculate_box_area(get_dimensions(box)))
all_small_areas.append(calculate_small_area(get_dimensions(box)))
end
summed_box_areas = all_box_areas.reduce(0) {|sum, num| sum + num}
summed_small_areas = all_small_areas.reduce(0) {|sum, num| sum + num}
puts "The Elves need #{summed_box_areas+summed_small_areas} square feet of wrapping paper!"
Day 2’s Perl code was the beginning of learning how to use groups in regular expressions to get values for variables in line 13. (This would become important in many future 2015 puzzles) Also the first time I used sorting on line 17
#!/usr/bin/perl
use v5.14;
open(PRESENTDIMENSIONS, , "../input.txt") || die "Can't open input.txt: $!\n";
my @present_dimension_list = <PRESENTDIMENSIONS>;
my @accumulated_areas;
for my $present_dimension (@present_dimension_list){
my($length, $width, $height) = $present_dimension =~ /(\d+)x(\d+)x(\d+)/;
push (@accumulated_areas, 2*$length*$width+2*$width*$height+2*$height*$length);
my @temp_dimensions = sort{ $a <=> $b }($length, $width, $height);
push (@accumulated_areas, $temp_dimensions[0] * $temp_dimensions[1]);
}
# reduce is not in the standard Perl library
my $total_area = 0;
for my $area (@accumulated_areas){
$total_area += $area;
}
say "The Elves need $total_area square feet of wrapping paper"
Day 4
Day 4 was pretty interesting for showing how a regular expression could make code very simple. Compare my Python and Perl code for that day:
import hashlib
def calculate_hash(text_to_hash):
return hashlib.md5(text_to_hash.encode('utf-8')).hexdigest()
def does_it_lead_with_five_zeroes(hash_string):
zero_count = 0
for character in hash_string:
if character == "0":
zero_count += 1
if character != "0":
break
return zero_count >= 5
def find_special_number(puzzle_text):
decimal_number = 1
found_it = False
while not found_it:
decimal_number += 1
calculated_hash = calculate_hash(puzzle_text + str(decimal_number))
found_it = does_it_lead_with_five_zeroes(calculated_hash)
return decimal_number
if __name__ == "__main__":
puzzle_input = "iwrupvqb"
answer = find_special_number(puzzle_input)
print(f"The number to add is {answer}")
#!/usr/bin/perl
use v5.14;
use Digest::MD5 qw(md5_hex);
my $puzzle_input = "iwrupvqb";
my $number = 0;
my $hex_test = md5_hex("$puzzle_input$number");
until ($hex_test =~ /^00000/){
$number++;
$hex_test = md5_hex("$puzzle_input$number");
}
say "Santa's magic number is $number";
It’s pretty incredible how much simpler that is, right? It’s not that I couldn’t have done that with Python, it’s just that I didn’t have the idea until I was thinking about how I’d do the problem with Perl.
Day 7
Last year during the 2020 AoC I learned about memoization, but had trouble implementing it. This time I finally figured it out. It was built-in to Python via lrucache, but I had to implement it manually in Ruby. That really helped me prove to myself that I had learned how to do it.
from datetime import datetime
from functools import lru_cache
import re
import sys
sys.path.insert(0, '../../input_parsing')
import parse_input
all_wires = {}
def create_dictionary(instructions):
"""Take in instructions and place the connections into a dictionary entry for the wire.
eg: 123 -> x would lead to a key of x and a value of 123.
"""
wires = {}
for instruction in instructions:
pattern = re.compile(r'(.*) -> (\w+)')
regex = re.findall(pattern, instruction)
connection = regex[0][0]
wire = regex[0][1]
wires[wire] = connection
return wires
def break_up_equation(equation):
"""Figure out the operand(s) and operation and return them."""
two_operand_regex = re.compile(r'(\w+) ([A-Z]*) (\w+)')
one_operand_regex = re.compile('([A-Z]*) ([a-z]+)')
if re.match(two_operand_regex, equation):
result = re.findall(two_operand_regex, equation)
return result[0][0], result[0][1], result[0][2]
elif re.match(one_operand_regex, equation):
result = re.findall(one_operand_regex, equation)
return result[0][0], result[0][1]
else:
print(f"{equation=}")
return [equation]
@lru_cache()
def find_value_on_line(wire_to_find):
"""Figure out what the final value is on a wire."""
if all_wires[wire_to_find].isnumeric():
return int(all_wires[wire_to_find])
equation = break_up_equation(all_wires[wire_to_find])
if len(equation) == 3:
if equation[0].isnumeric():
operand_left = int(equation[0])
else:
operand_left = find_value_on_line(equation[0])
if equation[2].isnumeric():
operand_right = int(equation[2])
else:
operand_right = find_value_on_line(equation[2])
operation = equation[1]
if operation == "AND":
return operand_left & operand_right
elif operation == "LSHIFT":
return operand_left << operand_right
elif operation == "OR":
return operand_left | operand_right
elif operation == "RSHIFT":
return operand_left >> operand_right
elif len(equation) == 2:
return find_value_on_line(equation[1]) ^ 65535
else:
print("one went straight through")
return find_value_on_line(equation[0])
if __name__ == "__main__":
print(f"Starting at {datetime.now().strftime('%d-%b-%Y %H:%M:%S')}")
bobby_instructions = parse_input.input_per_line('../input.txt')
all_wires = create_dictionary(bobby_instructions)
wire_a = find_value_on_line('a')
print(f"The value on wire a is {wire_a}")
print(f"Ended at {datetime.now().strftime('%d-%b-%Y %H:%M:%S')}")
require "../../input_parsing/parse_input"
def create_dictionary(instructions)
wires = Hash.new
instructions.each do |instruction|
match_results = instruction.scan(/(.*) -> (\w+)/)
connection = match_results[0][0]
wire = match_results[0][1]
wires[wire] = connection
end
wires
end
def break_up_equation(equation)
if equation.match?(/(\w+) ([A-Z]*) (\w+)/)
broken_equation = equation.scan(/(\w+) ([A-Z]*) (\w+)/)
#puts "A 3 way match: #{broken_equation[0][0]}, #{broken_equation[0][1]}, #{broken_e
quation[0][2]}"
return broken_equation[0][0], broken_equation[0][1], broken_equation[0][2]
elsif equation.match?(/([A-Z]*) ([a-z]+)/)
broken_equation = equation.scan(/([A-Z]*) ([a-z]+)/)
#puts "A 2 way match: #{broken_equation[0][0]}, #{broken_equation[0][1]}"
return broken_equation[0][0], broken_equation[0][1]
else
return [equation]
end
end
@all_wires = Hash.new
@cache = Hash.new
def for_cache(wire_to_find)
#def find_value_on_line(wire_to_find)
int = Integer(@all_wires[wire_to_find], exception: false)
return int if int
#puts "#{@all_wires[wire_to_find]}"
equation = break_up_equation(@all_wires[wire_to_find])
#puts "equation is #{equation[0]} #{equation[1]} #{equation[2]}"
if equation.length() == 3
operand_left = Integer(equation[0], exception: false)
if operand_left
#puts "L: #{operand_left} is a number"
else
#puts "L: #{equation[0]} is not a number"
operand_left = find_value_on_line(equation[0])
#puts "Now operand_left is #{operand_left}"
end
operand_right = Integer(equation[2], exception: false)
if operand_right
#puts "R: #{operand_right} is a number"
else
#puts "R: #{equation[2]} is not a number"
operand_right = find_value_on_line(equation[2])
#puts "Now operand_right is #{operand_right}"
end
operation = equation[1]
case operation
when "AND"
return operand_left & operand_right
when "LSHIFT"
return operand_left << operand_right
when "OR"
return operand_left | operand_right
when "RSHIFT"
return operand_left >> operand_right
end
elsif equation.length() == 2
return find_value_on_line(equation[1]) ^ 65535
else
return find_value_on_line(equation[0])
end
end
def find_value_on_line(wire_to_find)
#puts "Cache value is #{@cache[wire_to_find]}"
@cache[wire_to_find] ||= for_cache(wire_to_find)
end
if $PROGRAM_NAME == __FILE__
instructions = input_per_line('../input.txt')
#instructions = ['123 -> x', '456 -> y', 'x AND y -> d', 'x OR y -> e', 'x LSHIFT 2 -> f
', 'y RSHIFT 2 -> g','NOT x -> h', 'NOT y -> i']
@all_wires = create_dictionary(instructions)
answer = find_value_on_line('a')
#answer = for_cache('a')
puts answer
end
Day 9
Solving Day 9 was an oddessy that took me a couple days to fully solve. When I first read the problem, it reminded me of something I remembered from undergrad. I couldn’t remember if it was from the second semester of programming or discrete math, but I knew that once upon a time I’d been taught the algorithm to solve this problem. Some searching revealed that it was Djikstra’s Algorithm that I’d been thinking of. That turned out not quite to be what I wanted because Djikstra is for when you have a specified start and end node. So I did a little more sleuthing and thought perhaps what I wanted to solve for was a Hamiltonian Walk. That tells you if there’s a path that will reach every node and what the length is. So that got me most of the way there, but what I wanted was the shortest path. So that could be accomplished via the Traveling Salesman solution except that the Traveling Salesman comes back home and in this problem, Santa was only supposed to visit each city once. The solution in that case is to create a fake city that has 0 distance to all other cities. (basically, take the matrix that defines the city distances and add an extra row and column of zeroes to the bottom and right side).
My AoC code for all years can be found at this Github repo.
Microsoft MakeCode
Stella wanted a little wheeled bot of her own so I got her some assorted pieces to build a similar bot to Sam’s without it being exactly the same. I also wanted to take advantage of the Circuit Playground Express and Cricket we already had. Unfortunately, I haven’t been able to figure out the ultrasonic sensor yet. But I hope to have her robot working in May.