Advent of Code 2016 Day 9 (Factor)
Advent of Code 2016 Day 8 (c++)
Advent of Code 2016 Day 7 (Javascript)
Advent of Code 2016 – Day 6 (Julia)
Advent of Code 2016 – Day 5( Java 8)
Advent of Code 2016 – Day 4 (Perl 6)
Advent of Code 2016 – Day 3 (Clojure)
Advent of Code – Day 2 (Python 3)
Advent Of Code 2016 – Day 1(Haskell)
Day 11
Start: 12/14/2016
Finish 12/18/2016
Language: Groovy
SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST. DO NOT LOOK AT MY GITHUB PROJECT. It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer. This blog post is not to give away the answer, but instead, is there for people to learn from.
As always, the following code is in my GitHub: https://github.com/pviafore/AdventOfCode2016
The Challenge
So I decided to go to the JVM ecosystem and try out the scripting language Groovy. While the language itself didn’t boggle me (I had one big hang-up, but more on that later), but the problem took a long time (and I took two days off as well).
This challenge was an elaborate riff on the Farmer, Wolf, Goat and Cabbage crossing the river problem. We had to move machine parts up and down floors, with incompatible configurations on a floor bricking your machines.
One of my favorite classes of problems are Constraint Satisfaction Problem, so I thought I’d tackle it with Branch-and-Prune with Backtracking. But man, was I in for some unexpectedness.
Part 1
I wrote up all my code, and tried it out on the sample problem. It got it no problem. So then I loaded the bigger problem in, and after thirty minutes of runtime, I ran out of memory on my JVM. This was my first sign of trouble. I threw 16 gigs of RAM at the problem, but that didn’t help either. The code ran all night with barely inching forward. Hooray exponential big-O time. One thing to remember with Branch and Prune is the more you can prune, the better off you will be, so I started pruning. I found cases where it didn’t make sense to move pairs of machines, as it would always result in incompatibilities. I figured out once a floor below is empty, you never need to go back to it. But still, runtimes were killing me. There was no way the code would finish in a century, let alone in the few minutes that I wanted it.
I looked up some hints on the Reddit thread, as I felt my code would work, just was too long. Unfortunately , all the hints they gave are ones I had already considered myself. The big hint was to skip over equivalent building structures, and I thought I had done that. But, it turns out, my custom equals() method was never called. The indexOf and contains methods I was using in Groovy were checking object equality, not calling my equals() method (or at least, that’s what I suppose). Once I changed that, I had an answer in thirty minutes.
Let’s look at the code
class Floor implements Cloneable
{
def microchips;
def generators;
def Floor(String floorInfo)
{
this.microchips = getEquipmentOnFloor floorInfo, "microchip"
this.generators = getEquipmentOnFloor floorInfo, "generator"
this.microchips = this.microchips.collect { new String(it.charAt(0))+"m" }
this.generators = this.generators.collect { new String(it.charAt(0))+"g" }
}
private Floor() { }
def clone()
{
def c = new Floor()
c.microchips = this.microchips.collect { new String(it) }
c.generators = this.generators.collect { new String(it) }
c
}
def print()
{
this.microchips.each { println "Microchip $it" }
this.generators.each { println "Generator $it" }
}
def isEmpty()
{
return this.microchips.isEmpty() && this.generators.isEmpty()
}
def remove(option)
{
option.each{ op ->
if (op.charAt(1) == 'm') {
this.microchips.remove(this.microchips.indexOf(op))
}
else if (op.charAt(1) == 'g')
{
this.generators.remove(this.generators.indexOf(op))
}
}
}
def add(option)
{
option.each {
op ->
if (op.charAt(1) =='m'){
this.microchips.add(op)
}
else
{
this.generators.add(op)
}
}
}
def get_safely_removable_combos()
{
def safely_removable = []
def combos = this.microchips.clone()
combos.addAll(this.generators)
combos.each { c1 ->
combos.each { c2 ->
if(!c1.equals(c2) && this.isSafeToLeave(this.microchips.grep {!it.equals(c1) && !it.equals(c2)}, this.generators.grep {!it.equals(c1) && !it.equals(c2)} ))
{
if(c1.charAt(1) == c2.charAt(1) || c1.charAt(0) == c2.charAt(0))
{
safely_removable << [c1, c2].sort()
}
}
}
if (this.isSafeToLeave(this.microchips.grep { !it.equals(c1)}, this.generators) ){
safely_removable << [c1]
}
if (this.isSafeToLeave(this.microchips, this.generators.grep { !it.equals(c1)}) ){
safely_removable < generators.isEmpty() || generators.any {gen -> mc.charAt(0) == gen.charAt(0)} }
}
def isSafe()
{
return isSafeToLeave(this.microchips, this.generators)
}
def getEquipmentOnFloor(String floorInfo, String type)
{
def words = floorInfo.split(" ");
def output = []
for(int i =0; i < words.length; ++i)
{
if(words[i].startsWith(type))
{
output < new Floor(it)}
this.elevator = 0;
}
private Building()
{ }
def clone() {
def blding = new Building()
blding.floors = this.floors.collect { it.clone() }
blding.elevator = this.elevator
blding.lastBuilding = this
return blding
}
def equals(Building bldg) {
return this.getPairs() == bldg.getPairs()
}
def getPairs()
{
def pairs = [:]
(0..3).each {
this.floors[it].microchips.every {mc ->
if (pairs[mc.charAt(0)] == null) {
pairs[mc.charAt(0)] = [-1, -1]
}
pairs[mc.charAt(0)][0] = it
}
this.floors[it].generators.every {gen ->
if (pairs[gen.charAt(0)] == null) {
pairs[gen.charAt(0)] = [-1, -1]
}
pairs[gen.charAt(0)][1] = it
}
}
pairs.values().sort()
}
def print(){
this.floors.eachWithIndex { it, index->
print "Floor -> "
println index
it.print();
}
println ""
}
def get_possible_things_to_remove()
{
this.floors[elevator].get_safely_removable_combos()
}
def makeMove(new_floor, option)
{
this.floors[this.elevator].remove(option)
this.elevator = new_floor
this.floors[this.elevator].add(option)
}
def isFinished()
{
return this.floors[0].isEmpty() && this.floors[1].isEmpty() && this.floors[2].isEmpty()
}
def isGood(lastFloor) {
return this.floors[this.elevator].isSafe() && this.floors[lastFloor].isSafe()
}
def areFloorsBelowEmpty()
{
(0..(this.elevator-1)).every { this.floors[it].isEmpty()}
}
}
def find_solution(building)
{
def buildings = [building]
def time
def seenBuildings = [0:[building], 1:[], 2:[], 3:[]]
for(time = 0; buildings.size()!=0 && !buildings.any { it.isFinished() }; ++time)
{
def newBuildings = []
buildings.each {
bldg ->
getBuildingCandidates(bldg).each
{ candidate ->
if(seenBuildings[candidate.elevator].every { !it.equals(candidate) } )
newBuildings << candidate
seenBuildings[candidate.elevator] << candidate
}
}
buildings = newBuildings
println buildings.size()
}
time
}
def getBuildingCandidates(bldg)
{
def candidates = []
def options = bldg.get_possible_things_to_remove()
if (bldg.elevator 0 && !bldg.areFloorsBelowEmpty())
{
candidates.addAll(getCandidatesOnNewFloor(bldg, bldg.elevator-1, options.grep{it.size() == 1}))
}
candidates
}
def getCandidatesOnNewFloor(bldg, newFloor, options)
{
def candidates = []
options.each { option ->
candidate = apply_move(newFloor, option, bldg)
if(candidate.isGood(bldg.elevator)) {
candidates << candidate
}
}
candidates
}
def apply_move(floor, option, building)
{
clonedBuilding = building.clone()
clonedBuilding.makeMove(floor, option)
clonedBuilding
}
def fileContents = new File("day11.txt").text.split("\n")
def building = new Building(fileContents)
println find_solution(building)
First I’ll highlight the Floor class. This takes in a string and figures out what microchips and generators are on that floor. I provide clone methods, and ways to print, remove, and add equipment to the floor.
class Floor implements Cloneable
{
def microchips;
def generators;
def Floor(String floorInfo)
{
this.microchips = getEquipmentOnFloor floorInfo, "microchip"
this.generators = getEquipmentOnFloor floorInfo, "generator"
this.microchips = this.microchips.collect { new String(it.charAt(0))+"m" }
this.generators = this.generators.collect { new String(it.charAt(0))+"g" }
}
private Floor() { }
def clone()
{
def c = new Floor()
c.microchips = this.microchips.collect { new String(it) }
c.generators = this.generators.collect { new String(it) }
c
}
def print()
{
this.microchips.each { println "Microchip $it" }
this.generators.each { println "Generator $it" }
}
def isEmpty()
{
return this.microchips.isEmpty() && this.generators.isEmpty()
}
def remove(option)
{
option.each{ op ->
if (op.charAt(1) == 'm') {
this.microchips.remove(this.microchips.indexOf(op))
}
else if (op.charAt(1) == 'g')
{
this.generators.remove(this.generators.indexOf(op))
}
}
}
def add(option)
{
option.each {
op ->
if (op.charAt(1) =='m'){
this.microchips.add(op)
}
else
{
this.generators.add(op)
}
}
}
def get_safely_removable_combos()
{
def safely_removable = []
def combos = this.microchips.clone()
combos.addAll(this.generators)
combos.each { c1 ->
combos.each { c2 ->
if(!c1.equals(c2) && this.isSafeToLeave(this.microchips.grep {!it.equals(c1) && !it.equals(c2)}, this.generators.grep {!it.equals(c1) && !it.equals(c2)} ))
{
if(c1.charAt(1) == c2.charAt(1) || c1.charAt(0) == c2.charAt(0))
{
safely_removable << [c1, c2].sort()
}
}
}
if (this.isSafeToLeave(this.microchips.grep { !it.equals(c1)}, this.generators) ){
safely_removable << [c1]
}
if (this.isSafeToLeave(this.microchips, this.generators.grep { !it.equals(c1)}) ){
safely_removable < generators.isEmpty() || generators.any {gen -> mc.charAt(0) == gen.charAt(0)} }
}
def isSafe()
{
return isSafeToLeave(this.microchips, this.generators)
}
def getEquipmentOnFloor(String floorInfo, String type)
{
def words = floorInfo.split(" ");
def output = []
for(int i =0; i < words.length; ++i)
{
if(words[i].startsWith(type))
{
output << (words[i-1]);
}
}
output;
}
}
The big piece is the get_safely_removable_combos. This tells me what I can safely remove from the floor without invalidating what is on it. I check all pairs and only move two of the same type (such as two microchips or two generators) or a matching pair. Then I check each microchip and generator independently.
def get_safely_removable_combos()
{
def safely_removable = []
def combos = this.microchips.clone()
combos.addAll(this.generators)
combos.each { c1 ->
combos.each { c2 ->
if(!c1.equals(c2) && this.isSafeToLeave(this.microchips.grep {!it.equals(c1) && !it.equals(c2)}, this.generators.grep {!it.equals(c1) && !it.equals(c2)} ))
{
if(c1.charAt(1) == c2.charAt(1) || c1.charAt(0) == c2.charAt(0))
{
safely_removable << [c1, c2].sort()
}
}
}
if (this.isSafeToLeave(this.microchips.grep { !it.equals(c1)}, this.generators) ){
safely_removable << [c1]
}
if (this.isSafeToLeave(this.microchips, this.generators.grep { !it.equals(c1)}) ){
safely_removable << [c1]
}
}
safely_removable.unique()
}
Next up was modelling the entire building. You’ll find clone methods and equals() methods. Instead of checking strict equality, we’re instead checking that the pairs of equipment match up (So that a plutonium microchip and a plutonium generator on the first floor is the same as a dilithium microchip and a dilithium generator on the first floor).
I also provide a way to check if things are safe and if we are at a finished state (everything on the fourth floor)
class Building implements Cloneable
{
def floors;
def elevator;
def lastBuilding = null
Building(String[] buildingInfo)
{
this.floors = buildingInfo.collect {it -> new Floor(it)}
this.elevator = 0;
}
private Building()
{ }
def clone() {
def blding = new Building()
blding.floors = this.floors.collect { it.clone() }
blding.elevator = this.elevator
blding.lastBuilding = this
return blding
}
def equals(Building bldg) {
return this.getPairs() == bldg.getPairs()
}
def getPairs()
{
def pairs = [:]
(0..3).each {
this.floors[it].microchips.every {mc ->
if (pairs[mc.charAt(0)] == null) {
pairs[mc.charAt(0)] = [-1, -1]
}
pairs[mc.charAt(0)][0] = it
}
this.floors[it].generators.every {gen ->
if (pairs[gen.charAt(0)] == null) {
pairs[gen.charAt(0)] = [-1, -1]
}
pairs[gen.charAt(0)][1] = it
}
}
pairs.values().sort()
}
def print(){
this.floors.eachWithIndex { it, index->
print "Floor -> "
println index
it.print();
}
println ""
}
def get_possible_things_to_remove()
{
this.floors[elevator].get_safely_removable_combos()
}
def makeMove(new_floor, option)
{
this.floors[this.elevator].remove(option)
this.elevator = new_floor
this.floors[this.elevator].add(option)
}
def isFinished()
{
return this.floors[0].isEmpty() && this.floors[1].isEmpty() && this.floors[2].isEmpty()
}
def isGood(lastFloor) {
return this.floors[this.elevator].isSafe() && this.floors[lastFloor].isSafe()
}
def areFloorsBelowEmpty()
{
(0..(this.elevator-1)).every { this.floors[it].isEmpty()}
}
}
Finally, there is the bulk of the CSP solution – how to find a solution.
I keep track of what I’ve seen per floor so that I don’t repeat previously seen states (again, trying to prune as much as possible) and then I just iterate through all possible options, adding all safe options to a queue, and then looping back over the queue
def find_solution(building)
{
def buildings = [building]
def time
def seenBuildings = [0:[building], 1:[], 2:[], 3:[]]
for(time = 0; buildings.size()!=0 && !buildings.any { it.isFinished() }; ++time)
{
def newBuildings = []
buildings.each {
bldg ->
getBuildingCandidates(bldg).each
{ candidate ->
if(seenBuildings[candidate.elevator].every { !it.equals(candidate) } )
newBuildings << candidate
seenBuildings[candidate.elevator] << candidate
}
}
buildings = newBuildings
println buildings.size()
}
time
}
def getBuildingCandidates(bldg)
{
def candidates = []
def options = bldg.get_possible_things_to_remove()
if (bldg.elevator 0 && !bldg.areFloorsBelowEmpty())
{
candidates.addAll(getCandidatesOnNewFloor(bldg, bldg.elevator-1, options.grep{it.size() == 1}))
}
candidates
}
def getCandidatesOnNewFloor(bldg, newFloor, options)
{
def candidates = []
options.each { option ->
candidate = apply_move(newFloor, option, bldg)
if(candidate.isGood(bldg.elevator)) {
candidates << candidate
}
}
candidates
}
def apply_move(floor, option, building)
{
clonedBuilding = building.clone()
clonedBuilding.makeMove(floor, option)
clonedBuilding
}
Part 2
No change here, as I just had to run with 4 extra pieces of equipment. The solution took 2 hours to compute (still too long in my mind) but I am a few days behind now and got to catch up.
Wrap-up
Grade: A big fat “F”errooni. I took 5 days. I looked up hints. My Groovy code is sprawling. I got the wrong answer a few times. This was not pleasant. The problems are getting harder. I learned a lot, and I feel comfortable in Groovy now, but my ultimate feeling was that it was too Java-ish for Ruby town, and too Ruby-ish for Java town. It sat in the middle of the two for me, which was nice, but I could feel the influences seeping in (like object equality vs object equivalence).
Next up, it looks like I’m writing a simple assembler, and I think I’ll try it out in my first .NET language ever, C#.
Pat Viafore 
10 thoughts on “Advent of Code 2016 Day 11 (Groovy)”