Stephan van Hulst

Well, anything that does a lookup in O(log n) should be sufficient, so you might want to go for tree based solution instead, as they're easier to implement than hash tables.

Anyway, all of this seems too complicated. I wonder what your teacher has in mind. Maybe you can ask for another hint.

The only way I can think of how to do this is to maintain a map of IDs to indices in the tree. When you want to remove an element with some ID, you look up the index in the map. Then you replace the element at that index with the last element of the heap and perform a down-heap operation to restore the heap property of the sub-tree that the removed element was the root of.

The look-up is O(1) if you use a HashMap, and the down-heap operation is O(log n), making the remove operation O(log n).

I'm pleased with how my score caught up after missing the first few days. I've managed to temporarily overtake Tim, but that will only last until he's finished today.

Mike Simmons wrote:it's fundamentally an O(N^2 ) operation to delete from the ArrayList anywhere but the end.

Removing from an ArrayList is an O(n) operation. Removing from a LinkedList is an O(1) operation, but ONLY if you already have a pointer to the node you want to remove. That's why LinkedList is rarely useful. Most of the time an ArrayList outperforms a LinkedList even when removing from the middle of the list, because moving half the elements in an array may be faster than searching for the node to remove in a chain of links.

Operation	Performance
arrayList.remove(int)	O(n)
linkedList.remove(int)	O(n)
arrayListIterator.remove()	O(n)
linkedListIterator.remove()	O(1)

You might also want to check out my Advent of Code project, but it's a bit more complex, undocumented and I'm about to overhaul it. https://github.com/Nibsi/Advent-of-Code

It has sub-sub-modules though! It also shows how I have an "executable" module that just acts to fire up the user interface and to put runtime dependencies on the class path.

All I had to do to solve part 2 of yesterday's puzzle was to swap out the ArrayList my data structure was based on for a LinkedList.

The problem was that my data structure has two constructors and I only swapped it out in one of them. I assumed I was using a LinkedList and couldn't understand why it was taking so long. I even fired up my profiler only to find out that the NetBeans profiler doesn't work with Java 9+. Eventually I let it run the entire night and this morning I found out that after running for 10(!) hours, it had given me the incorrect answer because I used int instead of long.

After thinking about it for a bit today, I couldn't imagine that the list was so slow, and that's when I found out my mistake. *Actually* using the LinkedList reduced the runtime from 10 hours to a bit over a second.

I really liked that one, because it's the first real example I've seen of a case where a LinkedList greatly outperforms an ArrayList.

Today's puzzle was also really fun. I just let it run until the bounding rectangle of the points has a height and width that fits on my screen and then I visually inspect the message. Sadly it doesn't work well with the testing framework I wrote for AoC, unless I extended my solution with some sort of optical character recognition.

If not all entities have sprites, then Entity should not have a sprite property.

If you really want to use inheritance to solve this (beware of overuse of inheritance), then you could create a SpriteEntity and a RectangularEntity and then make Ship a subclass of SpriteEntity and Wall a subclass of RectangularEntity.

You could take a look at my Game of Life project on GitHub: https://github.com/Nibsi/Evolution

It was mostly a playground for me to practice writing documentation and it's unfinished and not actively being worked on, but it might give you an idea.

It's divided in three submodules: the core Game of Life library, a generations module that provides different implementations of the Game of Life, and a swing module that allows user interaction through a Swing interface.

I lost my code to day 8. I use the Git staging area to temporarily save code that I don't want to commit yet. I deleted my day 8 code because of reasons, but apparently the Git plugin for NetBeans automatically adds changes to the staging area, so it deleted the day 8 code I had saved there as well. I will definitely have to find out how to suppress this automatic staging.

Day 9 looks tedious to me as well, but I think I'll start by writing a circular buffer class.

I solved day 7 by writing a Graph class and repeatedly removing 'roots' from it (nodes without incoming edges). For the second part, I associate a counter with each node, and decrement it each second on roots that are currently 'in progress'. Only when the counter reaches 0, the root is removed and the rest of the algo works pretty much the same as part 1.

Day07Puzzle
Graph

For those interested, my solution to day 6: https://github.com/Nibsi/Advent-of-Code/blob/master/puzzles/puzzle-year-2018/src/main/java/nl/nibsi/aoc/puzzle/y18/d06/Day06Puzzle.java

It's verbose firstly because I jammed all classes into one file and secondly because I didn't refactor to deduplicate code. It works fast though.

It's tougher than the puzzles before for sure. I battled a bit with the first part, but the second part was comparatively much easier.

I'll upload my solution later, when I get my Git repo sorted out. There's still a lot of crud there from last year.

Sorry about that. I'll mention my solutions only after the puzzle for the next day has been released.

Let us know if you get any performance benefit. :)

Huh. My day 5 solution runs in half a second.

My Polymer class encapsulates a stack, and every time I add a unit to the polymer, I push it on top of the stack, unless it's the polar opposite of the top of the stack, then I just pop the opposite from the stack instead.

For the second part, I first determine all unique types in the input string, and then for each type, I create a new string that is just the input string with all occurrences of that type replaced by the empty string. I then run each new input string through the solution to part 1 to determine the length, and keep track of the shortest.