12 Apr 2020
Since starting my current job I have been using a Macbook (15 inch 2018 model)
as my daily work machine.
Previously I made use of an Ubuntu Dell XPS in my last job and before that a
Windows 7 Dell Latitude (I think) which I also often used a Linux VM on.
This post is written after spending quite a few months using my Macbook and
represents my thoughts and opinions on it from a software developer’s
standpoint, specifically from someone who does (and has done) a lot of Data
Engineering tasks, and Java/JVM focussed development on both Windows and Linux
machines.
I have quite a few criticisms of the Macbook and it’s Operating System in
general. Do bear in mind that these are my own opinions and based on what I like
and what works for me, I am sure many many developers can get by and be very
productive within the Mac and Apple ecosystem and have worked with several in my
career who absolute adore their Macbooks and desktop Macs as development
machines. Also some of these these criticisms are quite nitpicky and approach
the category of “first world problems” in some of their pettiness. I am overall
happy to continue using my Mac.
So without further preamble here are some of my criticisms and things I find
annoying about using a Macbook for work:
- Different shortcut keys to both Linux and Microsoft, even for the same
software and common shortcuts. One that is quite annoying to me is the use of
the Command instead of the Control for many shortcuts.
- Non UK ISO keyboard layout. Mainly it is the
"
, @
, |
and a few other
keys in odd places that irks me. Or the weird paragraph symbol I had never
seen on a keyboard before using a Mac. The Macbook I use also lacks a real
escape key and uses the touch bar instead, this is minor though as I don’t
really have a problem with the touch bar and the key is in a logic place.
- My Macbook sometimes sounds like it is taking off when doing tasks that to my
eyes should not be all that intensive. This isn’t necessarily an issue with
the Mac itself though as I have used other laptops in the past (e.g. the Dell
XPS) that have definitely had similar issues, which may well be due to form
factor and built in fans getting clogged up.
- The App Store. In general it’s a mess, full of overpriced useless apps that
make it difficult to find any useful applications.
- Any “extra” functionality to customize my experience seems to always cost a
bit more than I’d personally be willing to pay.
I understand and to an extent agree with the philosophy of paying for good
tools to do a good job but some of these seem like incredibly basic features
that the OS itself should include, or simple third party tools that should at
most cost a couple of £’s not pushing £20!
- Finder is one of the worst file managers I have ever used.
The fact that the delete key will not send a file to the trash is insane,
return does not open a file but instead allows you to rename it, it’s not
simple to show hidden files, backspace does not take you back up the file
tree, I can’t copy a path to a file, easily open a terminal in a folder etc.
- Native zip file support is awful. There is no obvious way to view the contents
of a compressed file without extracting it, this is built in functionality in
Windows!
- The equivalent of ALT-TAB, CMD-TAB, does not work between windows, but rather
applications and can be annoying when dealing with multiple windows for the
same application spread across different workspaces.
- Lack of full sized USB ports. I appreciate the newer USB-C ports, they are
an awesome design but in general very few peripherals are using this standard
right now.
- Lack of other useful ports. Luckily my Macbook still has a 3.5mm headphone
jack but it lacks Ethernet, DisplayPort or HDMI ports requiring Mac friendly
adapters.
- Siri. Unsure why I’d want this on my laptop let alone touch bar, thankfully
you can remove it from the latter.
- The extra cost for a lot of the peripherals, less of an issue for me as it is
a work machine, but I did have to fork out ~£25 for a USB adapter for working
from home so I could plug in my normal PC equipment.
Generally though Mac hardware is a tad on the pricey side, >£100 for a touch
pad, £80 for a mouse that lacks useful buttons and can’t be used while being
charged… The external keyboard too seems a tad expensive.
- Speaking of mice, for some reason lots of Mac software cannot work out how to
handle mouse buttons 4 and 5 on my personal mouse; generally used for back
and forward, especially annoying in Firefox.
- While I don’t hate it, I do not understand why the options for minimizing,
closing and maximising are to the left instead of right, that is rather
nitpicky though and a non-issue in the grand scheme of things.
What I actually dislike is why I have to hold Option down to make me able to
maximize but not full screen a window, it feels backwards.
That’s a longish list of, some admittedly petty, annoyances and criticisms. So
here are a few things that I do like about the Macbook and Mac OS:
- It seems fairly stable. I have not seen it really crash very often, my Dell
XPS had a habit of silently filling up all it’s memory and pretending to work
while it slowly stopped responding.
- It has enough memory and CPU resources for basically any task I have needed
it to do. Honestly though 16GB of RAM is a huge amount for most situations.
- The launcher/Spotlight Search is a great tool for running programs. It reminds
me of the Linux program
dmenu
but is much more user friendly.
- The way you install software (outside of the app store), while slightly
different to most other platforms is relatively easy to do and understand.
- Homebrew seems to be a great package manager, easy to use and understand.
- The touch bar is pretty neat, a good way to keep functionality on a limited
sized keyboard, although I rarely use it.
- The touch pad and gestures on it are excellent! Probably one thing I
absolutely love. I am still not the biggest fan of using 2 fingers for a
“right click” functionality but it works. I still loath the Mac mouse however.
- Workspaces aren’t as great as alternatives I have used on Linux but they are
good and a nice way of organising your work.
- A lot of terminal software is kept pretty up to date, this might be due to
using Homebrew however, when using Ubuntu I always found that a lot of the
available packages were pretty out of date.
- It’s kind of pretty, as an OS and laptop, I guess.
- The keyboard, peripheral and attached is pretty quiet, which is nice for an
office setting, it isn’t the most comfy to type on for extending periods of
time however and the layouts still drive me up the wall.
- Power over USB. As much as I dislike the lack of USB-A ports power over USB-C
is a good innovation and makes for easy to use charging cables.
- The battery life is good, and general power profiles make sense.
- The way it handles monitors being unplugged and plugged back in is great,
restoring workspaces etc. this is something that was always terrible on my
Linux laptop.
- It has some excellent software, although I don’t really use anything Mac
specific, I know people rave about Keynote etc.
- The screen and it’s colours are great, not something a less visual person
like me can really appreciate but if you do a lot of photography or video
editing it really helps.
And there it is; some of my likes and dislikes of the Macbook I have been using.
It may seem like I dislike working on it but it is definitely not the worst
development experience I have had and is a lot nicer than trying to develop
on some corporate Windows machines I have used in the past.
A lot of my criticisms probably stem from my habit of tinkering with Linux
desktops over the last few years to get a customized experience and workflow
going.
Originally when I was starting at my current job I was given the choice of what
development machine I would like with Surface Pro being the Windows equivalent
and there being no Linux option. And overall I am happy with the choice I made.
05 Dec 2019
This year I have decided to try and do the code challenges on the
Advent of Code website in Scala and possibly Spark
if needed (or an interesting solution arises).
These are simple little coding challenges given once per day like an Advent
Calendar before Christmas.
This challenge is relatively short so I will include the whole thing below:
— Day 4: Secure Container —
You arrive at the Venus fuel depot only to discover it’s protected by a
password. The Elves had written the password on a sticky note, but someone
threw it out.
However, they do remember a few key facts about the password:
- It is a six-digit number.
- The value is within the range given in your puzzle input.
- Two adjacent digits are the same (like
22
in 122345
).
- Going from left to right, the digits never decrease; they only ever
increase or stay the same (like
111123
or 135679
).
Other than the range rule, the following are true:
111111
meets these criteria (double 11
, never decreases).
223450
does not meet these criteria (decreasing pair of digits 50
).
123789
does not meet these criteria (no double).
How many different passwords within the range given in your puzzle input meet
these criteria?
Your puzzle input is 136760-595730
.
So we need to crack that password! Or at least work out how many combinations
there are.
This is a nice and simple thing to do in Scala:
val min = 136760
val max = 595730
val fullRange = min to max
First we define the minimum and maximum and create a range between them.
Next I want to extract each digit inside each item in the range into a single
number. I actually use a bit of a short-cut to do this:
def charToInt(char: Char): Int = char.toInt - '0'
This method will take a character and assuming it is a number character will
convert it into a matching integer. Combined with a string version of a
candidate password this lets me produce an array of digits with ease like so:
fullRange
.map(n => n.toString)
.map(string => string.map(char => charToInt(char)))
Now all we need to do is filter down this big collection of digits to match
the criteria described:
First lets find all the combinations with repeating digits:
def hasRepeatedDigit(number: IndexedSeq[Int]): Boolean = {
for (index <- 0 until number.size - 1) {
val digit = number(index)
val nextDigit = number(index + 1)
if (digit == nextDigit) {
return true
}
}
false
}
That’s pretty simple and easy.
Next let us filter to just those digits with incrementing or remaining the same
digits:
def isIncrementingOrSame(number: IndexedSeq[Int]): Boolean = {
var index: Int = 0
while (index < number.size - 1) {
val digit = number(index)
for (i <- index + 1 until number.size) {
val testDigit = number(i)
if (testDigit < digit) {
return false
}
}
index += 1
}
true
}
A little more complex but not hard.
Putting these together like so:
val validPasswords = fullRange
.map(n => n.toString)
.map(string => string.map(char => charToInt(char)))
.filter(hasRepeatedDigit)
.filter(isIncrementingOrSame)
println(validPasswords.size)
Will print out the amount of valid values asked for in part 1!
Day 4: Part 2
Now part 2 modifies one of the conditions slightly:
— Part Two —
An Elf just remembered one more important detail: the two adjacent matching
digits are not part of a larger group of matching digits.
Given this additional criterion, but still ignoring the range rule, the
following are now true:
112233
meets these criteria because the digits never decrease and all
repeated digits are exactly two digits long.
123444
no longer meets the criteria (the repeated 44
is part of a
larger group of 444
).
111122
meets the criteria (even though 1
is repeated more than twice,
it still contains a double 22
).
How many different passwords within the range given in your puzzle input
meet all of the criteria?
Now we can add an extra filter to cover this.
There’s a few ways of writing this filter, one slightly hacky way is to convert
the digits back to a string and use a Regular Expression to find all the
repeating digits:
val pattern = Pattern.compile("(?<=(.))(?!\\1)")
def repeatDigitsNotPartOfLargerGroup(number: IndexedSeq[Int]): Boolean = {
val asString = number.map(digit => digit.toString).mkString
val repeatedDigits = pattern.split(asString).toSeq
repeatedDigits.exists(repeat => repeat.length == 2)
}
The pattern does a positive lookbehind and negative lookahead. Kind of hard to
understand unless you use Regular Expressions a lot.
You could do a similar thing with a Java Scanner
too.
But if we wanted to do this properly without converting to a string we really
only need 2 nested loops to perform the same logic on the digits:
def repeatDigitsNotPartOfLargerGroup(number: IndexedSeq[Int]): Boolean = {
val groupCounts = mutable.Buffer[(Int, Int)]()
var start = 0
while (start < number.length - 1) {
val digit = number(start)
var count = 1
var i = start + 1
var changed = false
while (i < number.length && !changed) {
val nextDigit = number(i)
if (digit != nextDigit) {
changed = true
} else {
count += 1
i += 1
}
}
val group = (digit, count)
groupCounts += group
start += count
}
groupCounts.exists(group => group._2 == 2)
}
And with either of these filters added we get our result for part 2!
05 Dec 2019
This year I have decided to try and do the code challenges on the
Advent of Code website in Scala and possibly Spark
if needed (or an interesting solution arises).
These are simple little coding challenges given once per day like an Advent
Calendar before Christmas.
I did complete this challenge on the day but am only now managing to write
about it!
Today’s challenge is again slightly more difficult than previous days.
I will again only try to paste the relevant parts of the challenge here.
We are presented with input that describes 2 wires coming out of a port and
snaking around a grid.
Specifically, two wires are connected to a central port and extend outward
on a grid.
You trace the path each wire takes as it leaves the central port, one wire
per line of text (your puzzle input).
And our job is to find the closest point they cross:
To fix the circuit, you need to find the intersection point closest to the
central port. Because the wires are on a grid, use the Manhattan distance for
this measurement. While the wires do technically cross right at the central
port where they both start, this point does not count, nor does a wire count
as crossing with itself.
Manhattan distance is a common distance metric used when dealing with grids and
is also known as “Taxicab Geometry”
because of the fact you measure the same way as a taxi would navigate through a
city like Manhattan (a grid based city).
That means you measure your distance in each axis and add them up.
For example if you are at position (0, 1)
and want to get to (10, 9)
you
take the x
components and find the difference, 0 to 10 = 10
, and do the same
with the y
components, 1 to 9 = 8
, and add those results together,
8 + 10 = 18
, and that is your Manhattan distance.
The wire paths are describe using what are essentially commands, for example:
For example, if the first wire’s path is R8,U5,L5,D3
, then starting from the
central port (o), it goes right 8, up 5, left 5, and finally down 3:
...........
...........
...........
....+----+.
....|....|.
....|....|.
....|....|.
.........|.
.o-------+.
...........
Then, if the second wire’s path is U7,R6,D4,L4
, it goes up 7, right 6,
down 4, and left 4:
...........
.+-----+...
.|.....|...
.|..+--X-+.
.|..|..|.|.
.|.-X--+.|.
.|..|....|.
.|.......|.
.o-------+.
...........
These wires cross at two locations (marked X), but the lower-left one is
closer to the central port: its distance is 3 + 3 = 6.
So to begin we will need to be able to read and represent the wires in the text
file.
I begin by creating some data structures to do this:
import scala.collection._
object Direction extends Enumeration {
type Direction = Value
val UP = Value("U")
val RIGHT = Value("R")
val DOWN = Value("D")
val LEFT = Value("L")
}
import Direction.Direction
case class Command(direction: Direction, distance: Int)
type Wire = Seq[Command]
Here I have defined the direction as an enumerated type and commands as being a
combination of directions and distance, with a wire simply being an ordered
sequence of commands.
Now for parsing and reading I will again be using the Scala Source class and
split this into several function to make it easier to read and think about the
code:
def parseCommand(command: String): Option[Command] = {
if (command.length < 2) {
return None
}
try {
val direction = Direction.withName(command.substring(0, 1))
val distance = command.substring(1).toInt
Some(Command(direction, distance))
} catch {
case _: Exception =>
println(s"Unhandled command: $command")
None
}
}
First up I think about how I want to handle parsing a single command from the
file I am given. These will be in forms similar to U1
, R12
, D3
and L23
,
basically a letter denoting direction followed by an integer denoting distance.
In my Direction enumerated object I defined each direction to have a name
corresponding to the letters used in the input. I take the first character of
the command and attempt to match it, then take the remainder and attempt to
convert it to an integer.
If something goes wrong with the parsing I return a None
that I can handle
later and log the bad command.
def parseLine(line: String): Option[Wire] = {
if (line == null || line.isEmpty) {
return None
}
val commands: Seq[Option[Command]] = line.split(',')
.map(part => parseCommand(part))
if (commands.forall(item => item.isDefined)) {
Some(commands.flatten)
} else {
println(s"Unhandled line: $line")
None
}
}
import scala.io.Source
def readInput(filename: String): Seq[Wire] = {
val source = Source.fromFile(filename)
val wires = source.getLines()
.map(line => line.trim)
.filter(line => line.nonEmpty)
.map(line => parseLine(line))
wires.flatten.toSeq
}
The next function is for parsing a whole line.
It splits the line up on the comma separator and uses the first function to
extract a command from it.
It then checks all the results of parsing and sees if there were any errors with
the command parsing. If there were it returns a None
and logs an error,
otherwise it flattens out all the Some[Command]
instances into Command
instances.
Finally there is the readInput
function that actually opens the file, reads
it line by line and uses the parseLine
method to generate whole wires.
With all that done we can now represent our wires in a way we can easily
manipulate. It’s now time to consider how to determine where on a grid the
wires actually live!
For this we need to represent positions somehow:
type Position = (Int, Int)
For now this simple tuple will suffice.
Now we need to convert the commands that make up a wire and convert them into
all the positions they sit on a grid.
With our data structures this can be relatively simple:
def addCommand(start: Position, command: Command): Position = {
val Command(direction: Direction, distance: Int) = command
if (distance == 0) {
return start
}
val (x, y) = start
direction match {
case Direction.UP => (x, y + distance)
case Direction.DOWN => (x, y - distance)
case Direction.RIGHT => (x + distance, y)
case Direction.LEFT => (x - distance, y)
}
}
The way this function works is that given a starting position and command it
will determine where the command would cause the position to move to and return
that as a result.
Of course if I used just this method I would only end up with positions where
the wire changed direction (or got a new command), not all the points in between
these positions.
For this reason I need a method of getting all the points between the starting
position and the ending position of a command:
def pointsBetween(start: Position, end: Position): Seq[Position] = {
val results = mutable.Buffer[Position]()
val (x0, y0) = start
val (x1, y1) = end
val xStep = if (x0 > x1) -1 else 1
val yStep = if (y0 > y1) -1 else 1
for (x <- x0.to(x1, xStep)) {
for (y <- y0.to(y1, yStep)) {
val pos: Position = (x, y)
// Don't add the start to the results
if (x != x0 || y != y0) {
results += pos
}
}
}
results
}
This method is relatively simple again, it’s basic interpolation between the
two points.
I make use of a mutable Scala Buffer
here to make things easier to read.
Now that I can get the points between 2 points I can bring this altogether to
get all the points in a wire:
def getPositions(wire: Wire, origin: Position = (0, 0)): Seq[Position] = {
val positions = mutable.Buffer[Position]()
var lastPosition: Position = origin
for (command <- wire) {
val firstPosition: Position = lastPosition
lastPosition = addCommand(firstPosition, command)
// add all points between start (exclusive) and end (inclusive)
positions ++= pointsBetween(firstPosition, lastPosition)
}
positions
}
This function starts at an origin and executes each command, using the start
and end points of each, adding them all to a buffer and returning them all.
Now we can get all the points in a wire we need a way of finding out when wires
intersect each other.
This is actually pretty simple:
def findIntersections(paths: Seq[Seq[Position]]): Seq[Position] = {
val positionCounts: Map[Position, Int] =
paths.flatMap(path => path.distinct)
.groupBy(identity)
.mapValues(_.size)
positionCounts.filter(entry => entry._2 > 1).keys.toSeq
}
Since each path a wire takes now contains all the positions a wire can be in we
just need to find where a position exists in both wires paths.
I have done this using some standard Scala code;
- First I get a distinct list of all positions in each path, that way I can
avoid counting a wire crossing itself.
- Then I use flatmap to combine the paths into one list.
- Then I group them all by themselves (that’s the
identity
method I use) and
convert the list into a Map[Position, Int]
with the values being the count
of occurrences of a given position.
This resulting map contains all the positions in both paths, if I then filter
it down to only those that have a count greater than 1 I can find any
intersections.
I can use the above methods to get me this far like so:
val wires = readInput("day3.input.txt")
val wireToPositions = wires.map(wire => (wire, getPositions(wire))).toMap
val intersections = findIntersections(wireToPositions.values.toSeq)
Now I need to actually use the manhattan distance to find out which of the
intersections is the closest.
The code fot the manhattan distance in Scala is simple:
def manhattanDistance(origin: Position, other: Position): Int = {
val x: Int = math.abs(origin._1 + other._1)
val y: Int = math.abs(origin._2 + other._2)
x + y
}
I can then find the closest intersection like so:
def findClosestIntersection(
origin: Position,
intersections: Seq[Position]
): (Position, Int) = {
val withDistances =
intersections.map(pos => (pos, manhattanDistance(origin, pos)))
withDistances.minBy(f => f._2)
}
What this does is similar to finding the intersections initially; it takes each
position and gets it’s distance from the origin, then simply returns the one
with the smallest distance.
I can then use this command like so to answer part 1:
val closest = findClosestIntersection(
(0, 0),
intersections
)
println(s"Closest intersection ${closest._1} distance=${closest._2}")
Day 3: Part 2
Finally onto part 2.
We now need to use a different measurement on the intersections:
To do this, calculate the number of steps each wire takes to reach each
intersection; choose the intersection where the sum of both wires’ steps is
lowest. If a wire visits a position on the grid multiple times, use the
steps value from the first time it visits that position when calculating the
total value of a specific intersection.
The number of steps a wire takes is the total number of grid squares the wire
has entered to get to that location, including the intersection being
considered. Again consider the example from above:
...........
.+-----+...
.|.....|...
.|..+--X-+.
.|..|..|.|.
.|.-X--+.|.
.|..|....|.
.|.......|.
.o-------+.
...........
In the above example, the intersection closest to the central port is
reached after 8+5+5+2 = 20 steps
by the first wire and 7+6+4+3 = 20 steps
by the second wire for a total of 20+20 = 40 steps
.
However, the top-right intersection is better: the first wire takes only
8+5+2 = 15
and the second wire takes only 7+6+2 = 15
, a total of
15+15 = 30 steps
.
With our code this is actually pretty easy.
Since we have a list of all the positions in a wire we can use it with the
intersections we uncovered before to find out their distances by simply counting
the steps it takes to get to them:
val wireToIntersectionDistances: Map[Wire, Map[Position, Int]] =
wireToPositions.map(entry => {
val wire = entry._1
val positions = entry._2
val positionsToDistance = intersections.map(
// remember to +1 as we excluded the origin from our original list
intersection => (intersection, positions.indexOf(intersection) + 1)
).toMap
(wire, positionsToDistance)
})
Then with this map of wires to their intersections and their distances we can
do some more calculations to find out the total steps taken from both wires for
each intersection and then find the lowest:
val intersectionsToTotalDistances: Map[Position, Int] =
wireToIntersectionDistances.foldLeft(Map[Position, Int]())((sum, map) => {
val otherMap = map._2
(sum.keySet ++ otherMap.keySet).map { key: Position =>
(key, sum.getOrElse(key, 0) + otherMap.getOrElse(key, 0))
}.toMap
})
val minDistanceIntersection = intersectionsToTotalDistances.minBy(f => f._2)
println(s"Min distance intersection at ${minDistanceIntersection._1} distance=${minDistanceIntersection._2}")
Now admittedly that foldLeft
block of code does look quite complex but what
it does is fairly simple:
- The first set of arguments contains the initial, empty, value for what we
want to eventually return, a map of positions to the total amount of steps
taken.
- The next set of arguments contains the function that keeps the running
summarized map and the current map being processed from the
wireToIntersectionDistances
map entries.
- The rest of the code then sums up the maps values within based on their keys,
which are the positions.
- Finally we get the minimum entry like before.
And that’s part 2 of Day 3 done!
03 Dec 2019
This year I have decided to try and do the code challenges on the
Advent of Code website in Scala and possibly Spark
if needed (or an interesting solution arises).
These are simple little coding challenges given once per day like an Advent
Calendar before Christmas.
I am starting a day late on the 2nd of December, but this hopefully means my
solutions will not spoil it for anyone else!
This days challenge is quite different to Day 1 and involves creating a simple
interpreter or emulator for processing a simple input program and set of
opcodes.
I have decided not to copy and paste the whole challenge here for brevity’s sake
but I will refer back to parts. I encourage you to read the
whole challenge before continuing.
We are tasked with building a “computer” to interpret “Intcode” programs:
An Intcode program is a list of integers separated by commas
(like 1,0,0,3,99
).
To run one, start by looking at the first integer (called position 0).
Here, you will find an opcode - either 1
, 2
, or 99
.
The opcode indicates what to do; for example, 99
means that the program is
finished and should immediately halt.
Encountering an unknown opcode means something went wrong.
We are provided with 3 opcodes in this part of the task, 1
, 2
, and 99
.
Opcode 1
does the following:
Opcode 1 adds together numbers read from two positions and stores the result
in a third position.
The three integers immediately after the opcode tell you these three
positions - the first two indicate the positions from which you should read
the input values, and the third indicates the position at which the output
should be stored.
And opcode 2
does:
Opcode 2 works exactly like opcode 1, except it multiplies the two inputs
instead of adding them. Again, the three integers after the opcode indicate
where the inputs and outputs are, not their values.
With opcode 99
halting the program.
We are also told how to move on to the next operation when done calculating the
current opcode:
Once you’re done processing an opcode, move to the next one by stepping
forward 4 positions.
It is useful to note that all opcodes and data in this task appears to be
integers.
It is also useful to realise that from the description of this task we are
actually implementing a very simple computer with
Von Neumann architecture,
that is, a computer where program input and output and program instructions are
stored within the same space, and is the basis of most common computers in use
today.
An interesting side-effect of this architecture is that code can be self
modifying.
As part of this task we are given some example inputs and their eventual outputs
which will be useful when testing our implementation:
Here are the initial and final states of a few more small programs:
1,0,0,0,99
becomes 2,0,0,0,99
(1 + 1 = 2).
2,3,0,3,99
becomes 2,3,0,6,99
(3 * 2 = 6).
2,4,4,5,99,0
becomes 2,4,4,5,99,9801
(99 * 99 = 9801).
1,1,1,4,99,5,6,0,99
becomes 30,1,1,4,2,5,6,0,99
.
Our overall task is given at the end as:
Once you have a working computer, the first step is to restore the gravity
assist program (your puzzle input) to the “1202 program alarm” state it had
just before the last computer caught fire.
To do this, before running the program, replace position 1
with the
value 12
and replace position 2
with the value 2
.
What value is left at position 0
after the program halts?
Implementing the Computer
We first need to read in the input program and convert it into a structure our
program can use.
import scala.io.Source
val filename = "day2.input.txt"
// Open the input file
val bufferedSource = Source.fromFile(filename)
// Convert the contents into our opcodes
val originalOpcodes: Array[Int] = bufferedSource.mkString
.trim
.split(',')
.map(string => string.toInt)
// Close the input file
bufferedSource.close()
This code will convert the input file into an array of integers ready for us
to work with.
The mkString
method will load the whole contents of the file into a string
then the trim
method removes any trailing spaces, with the split
and map
methods dividing the string up on the commas and converting that output to
integers.
Now with our 3 given opcodes we should define some kind of structure to make
calculating them easier.
Since this is a quick puzzle I will opt for defining a simple functions and will
also use the scala type
keyword to try and make my code easier to understand.
I will be making use of Scala’s mutable indexed type mutable.IndexedSeq
to
store the working memory of the program that will be read and modified by each
operation:
type Memory = Array[Int]
type Position = Int
type Opcode = Int
// Simple Operation type:
// Taking in the current memory state and position and outputting the new
// state and position
type Operation = (Memory, Position) => (Memory, Position)
Now I can create a simple lookup table of opcodes and their operations:
type Memory = mutable.IndexedSeq[Int]
type Opcode = Int
// Simple Operation type:
// Taking in the current position in memory and memory itself and outputting
// the new position and whether this operation should halt or not.
type Operation = (Int, Memory) => (Int, Boolean)
// The add operation
val addOp: Operation = (pos: Int, memory: Memory) => {
val inputAddress1 = memory(pos + 1)
val inputAddress2 = memory(pos + 2)
val outputAddress = memory(pos + 3)
memory(outputAddress) = memory(inputAddress1) + memory(inputAddress2)
(pos + 4, false)
}
// The multiply operation
val multiplyOp: Operation = (pos: Int, memory: Memory) => {
val inputAddress1 = memory(pos + 1)
val inputAddress2 = memory(pos + 2)
val outputAddress = memory(pos + 3)
memory(outputAddress) = memory(inputAddress1) * memory(inputAddress2)
(pos + 4, false)
}
// The simple halting operation
val haltOp: Operation = (pos: Int, memory: Memory) => {
(pos, true)
}
// The map of opcodes to their operations
val opcodeMap = Map[Opcode, Operation](
(1, addOp),
(2, multiplyOp),
(99, haltOp)
)
Now we have a simple map of opcodes to their operations we need to write the
code to execute them:
val errorOp: Operation = (pos: Int, memory: Memory) => {
val opcode = memory(pos)
println(s"Unknown opcode encountered at $pos: $opcode")
(pos, true)
}
@scala.annotation.tailrec
def iterate(pos: Int, memory: Memory): Unit = {
val opcode = memory(pos)
val operation = opcodeMap.getOrElse(opcode, errorOp)
val (newPos, shouldHalt) = operation(pos, memory)
if (shouldHalt) {
return
}
iterate(newPos, memory)
}
This method will take in a position in memory and the memory itself and execute
opcodes on it until it reaches an operation that will cause it to halt.
I have done this using the Tail Recursion support in Scala to make it easy to
read. This will avoid stack overflow issues.
I have also added an error operation that will be executed upon hitting an
unknown opcode.
We can test one of the examples:
val mainMemory: Memory = mutable.IndexedSeq(2,4,4,5,99,0)
iterate(0, mainMemory)
val finalOutput = mainMemory.mkString(",")
println(finalOutput)
This will output: 2,4,4,5,99,9801
We can run this with the file contents my copying the original code to the
memory variable:
val mainMemory: Memory = mutable.IndexedSeq(originalOpcodes: _*)
Of course the task also instructs us to fix the program:
To do this, before running the program, replace position 1
with the
value 12
and replace position 2
with the value 2
.
mainMemory(1) = 12
mainMemory(2) = 2
Then execute it.
And we have the answer to the puzzle in index 0.
Day 2: Part 2
The second part of the day requires us to figure out the inputs to the program
that will result in an expected value.
“With terminology out of the way, we’re ready to proceed.
To complete the gravity assist, you need to determine what pair of inputs
produces the output 19690720
.”
Something important noted in the puzzle is that opcodes can move the position
in memory a variable amount of steps depending on what instructions there are:
The address of the current instruction is called the instruction pointer;
it starts at 0.
After an instruction finishes, the instruction pointer increases by the
number of values in the instruction; until you add more instructions to the
computer, this is always 4 (1 opcode + 3 parameters) for the add and multiply
instructions. (The halt instruction would increase the instruction pointer
by 1, but it halts the program instead.)
This actually means our halt instruction should technically look like:
val haltOp: Operation = (pos: Int, memory: Memory) => {
(pos + 1, true)
}
The following extra details are provided to narrow down the search:
The inputs should still be provided to the program by replacing the values at
addresses 1 and 2, just like before.
In this program, the value placed in address 1 is called the noun, and the
value placed in address 2 is called the verb.
Each of the two input values will be between 0 and 99, inclusive.
This narrows down our search somewhat.
To repeat what we need to do is:
Find the input noun and verb that cause the program to produce the output
19690720
. What is 100 * noun + verb
?
(For example, if noun=12
and verb=2
, the answer would be 1202.)
It is also suggested that we should make sure to reset the memory to the
original opcodes before each attempt.
To this end we can write a function to make it easier to test various inputs:
def decode(noun: Int, verb: Int, originalMemory: IndexedSeq[Int]): Int = {
val mainMemory: Memory = mutable.IndexedSeq(originalMemory: _*)
mainMemory(1) = noun
mainMemory(2) = verb
iterate(0, mainMemory)
mainMemory(0)
}
This will execute for the given noun and verb pair and output the result.
We can then brute force the answer to the puzzle:
val random = scala.util.Random
var output: Int = 0
var noun: Int = 0
var verb: Int = 0
while (output != 19690720) {
noun = random.nextInt(100)
verb = random.nextInt(100)
output = decode(noun, verb, originalOpcodes)
}
println(s"noun=$noun verb=$verb")
val answer = 100 * noun + verb
println(answer)
And this will output the solution to part 2!
02 Dec 2019
This year I have decided to try and do the code challenges on the
Advent of Code website in Scala and possibly Spark
if needed (or an interesting solution arises).
These are simple little coding challenges given once per day like an Advent
Calendar before Christmas.
I am starting a day late on the 2nd of December, but this hopefully means my
solutions will not spoil it for anyone else!
The first challenge is a simple one, I will copy the whole challenge below:
— Day 1: The Tyranny of the Rocket Equation —
Santa has become stranded at the edge of the Solar System while delivering
presents to other planets! To accurately calculate his position in space,
safely align his warp drive, and return to Earth in time to save Christmas,
he needs you to bring him measurements from fifty stars.
Collect stars by solving 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!
The Elves quickly load you into a spacecraft and prepare to launch.
At the first Go / No Go poll, every Elf is Go until the Fuel Counter-Upper.
They haven’t determined the amount of fuel required yet.
Fuel required to launch a given module is based on its mass.
Specifically, to find the fuel required for a module, take its mass,
divide by three, round down, and subtract 2.
For example:
- For a mass of 12, divide by 3 and round down to get 4, then subtract 2 to
get 2.
- For a mass of 14, dividing by 3 and rounding down still yields 4, so the
fuel required is also 2.
- For a mass of 1969, the fuel required is 654.
- For a mass of 100756, the fuel required is 33583.
The Fuel Counter-Upper needs to know the total fuel requirement.
To find it, individually calculate the fuel needed for the mass of each
module (your puzzle input), then add together all the fuel values.
What is the sum of the fuel requirements for all of the modules on your
spacecraft?
As I said this is simple enough; we need to calculate the fuel requirement
based on the given formula for each module and sum them all together for our
answer.
The formula given is: fuel = floor(mass / 3) - 2
(floor is just a function
that rounds down the input).
We are given a puzzle input of a text file where each line is a number denoting
the mass of a single module e.g.
86870
94449
119448
53472
140668
64989
112056
88880
131335
94943
We can load this into Scala and apply the formula to each line then sum the
answer using code similar to the following:
import scala.io.Source
import scala.math.floor
val filename = "input.txt"
// Open the input file
val bufferedSource = Source.fromFile(filename)
// For each line:
val total = bufferedSource.getLines()
// Convert it to a Long
.map(line => line.toLong)
// Apply the formula we were given
.map(mass => floor(mass / 3) - 2)
// Sum all results together
.sum
// Display the total
println(s"Total: $total")
// Close the resource
bufferedSource.close()
Once we have a result it’s on to part 2 of Day 1.
Day 1: Part 2
The puzzle reads as:
— Part Two —
During the second Go / No Go poll, the Elf in charge of the Rocket Equation
Double-Checker stops the launch sequence.
Apparently, you forgot to include additional fuel for the fuel you just added.
Fuel itself requires fuel just like a module - take its mass, divide by three,
round down, and subtract 2.
However, that fuel also requires fuel, and that fuel requires fuel, and
so on.
Any mass that would require negative fuel should instead be treated as if it
requires zero fuel; the remaining mass, if any, is instead handled by
wishing really hard, which has no mass and is outside the scope of this
calculation.
So, for each module mass, calculate its fuel and add it to the total.
Then, treat the fuel amount you just calculated as the input mass and repeat
the process, continuing until a fuel requirement is zero or negative.
For example:
What is the sum of the fuel requirements for all of the modules on your
spacecraft when also taking into account the mass of the added fuel?
(Calculate the fuel requirements for each module separately, then add them
all up at the end.)
This is a little harder than Part 1.
Now for each module we need to calculate the fuel required for not just the
module but the fuel to carry the additional fuel!
Luckily the way we structure our Scala code makes this easy to do.
We can replace our simple fuel calculation with a call to a more complex
function before our sum
function call:
def calculateFuel(mass: Long): Long = {
// define the fuel function we will be using
val fuelFunction = (mass: Long) => (floor(mass / 3) - 2).toLong
// calculate the initial fuel we need for the given mass
val initialFuel: Long = fuelFunction(mass)
var total: Long = initialFuel
// Loop round adding any additional fuel required until it reaches 0 or less
var additional: Long = fuelFunction(initialFuel)
while (additional > 0) {
total += additional
additional = fuelFunction(additional)
}
// return the total
total
}
// For each line:
val total = bufferedSource.getLines()
// Convert it to a Long
.map(line => line.toLong)
// Apply the formula we were given
.map(mass => calculateFuel(mass))
// Sum all results together
.sum
This will return us our result, applying that function to all the masses we are
given before totalling up.
This completes Day 1 of Advent of Code 2019!