That's right, I'm back for more. Last year, I colored all the dinosaurs by intuition: keep the backgrounds purple, keep the larger regions yellow or pink, and try to confine gray to the smallest detail regions. This time, I've got the power of computer science on my side.
Game objectives
- Color all 16 dinosaurs such that no two adjacent regions are the same color
- Do so using the smallest number of colors (which is 4)
Table of contents
What is the Four-color Theorem?
The four color theorem is kind of like a game. You have an area divided into discrete regions--say, a map of the world, or a picture of a dinosaur--and you have to color all the regions in. There's only one rule: two adjacent regions cannot be the same color. You could trivially color any dinosaur by this rule if you picked a different color for every single region, but that's no fun! Therefore, the goal of this game is to get a low score: what's the fewest number of colors you can use? The four color theorem states that, for any given dinosaur, you will never need more than four colors... as long as your dinosaurs aren't too weird.
The particular weirdness we dinosaur colorers have to deal with is exclaves, or separate island regions that are forced to be the same color. If Alaska has to be the same color as the continental U.S., then you could contrive a scenario where more than four colors are required. This doesn't actually cause problems for the run, as evidenced by last year's submissions, but it could have. More on this in the relevant dinosaurs' sections.
The Algorithm
In standard graph colorings, we don't care which colors are used, or where. In dinosaur coloring, however, not all regions and colors are created equal. Pink and yellow take 1 pass to fill, purple obviously takes 0 passes because it's already there, and gray takes 2 passes because it has to put down a layer of pink primer. Therefore, the dinosaur coloring problem is a layer on top of typical graph coloring where you have to find an optimal solution based on the weights of the colors and regions.
Modeling
Each dinosaur is modeled as an undirected graph, in typical fashion (with exclaves treated as one merged vertex). Each vertex and each color has a weight; these weights are multiplied together when computing the overall score of a solution.
I determined the vertex weights empirically by manually TASing a frame perfect fill of each region using pink (picture this but pinker). So by definition, pink has a weight of 1. I've observed subtle, inexplicable variations
(miracle frames) when using yellow, but I've chosen to ignore these and treat yellow as also having a weight of 1. Purple obviously has a weight of 0, and the two-pass gradient fill of gray would seem to have a weight of 2. But through further testing, I found that it's 2N - 1 (miracle frames notwithstanding), which I've captured by adding a constant addend as part of each color's definition.
So the weight of a vertex v colored with color c is Wv[v] * Wc[c] + Cc[c], where:
V is the number of vertices in the graph
C is the number of colors (always 4 in this case)
Wv is the list of vertex weights, from 0 to V - 1
Wc is the list of color weights, from 0 to C - 1
Cc is the list of color constants, from 0 to C - 1
C is the number of colors (always 4 in this case)
Wv is the list of vertex weights, from 0 to V - 1
Wc is the list of color weights, from 0 to C - 1
Cc is the list of color constants, from 0 to C - 1
It would be more accurate to measure a separate yellow, pink, and gray fill, and make the weights a V x C matrix.
Determining adjacencies was the hardest part. I didn't do this algorithmically, but by hand. For most regions, the adjacencies are obvious, but for many others, the black outlines
and pixel art aesthetic make it difficult to determine. For these cases, I invented the knight's move heuristic - if the two colored regions can be reached by a knight's move, then they are adjacent.
These results lined up with FractalFusion's writeup[1] and the community consensus during the toenail incident.
These drawings also contain solid black pupil regions with small specular highlights. I considered the specular highlight to take up the entire black border region, just to be safe--and keep things interesting!
Here is an example of a dinosaur that has been modified to show you how I see the adjacencies. It gives me the willies, so this is the only one you get.
Core
The core algorithm is rather crude. It just tries all possible combinations with some basic pruning. It is surprising that it runs as fast as it does.
The theoretical runtime is O(CV), which would be on the order of 430 = 1,152,921,504,606,846,976 (1 quintillion) for these graphs.
The reasons it runs as fast as it does are twofold:
- The graphs have clear outliers in terms of weight and degree which eliminate lots of possibilities.
- I iterate the vertices in decreasing order of degree to best take advantage of this.
The stegosaurus in particular needs this degree-based ordering. It went from making no progress overnight to running in less than 100 ms.
jgrapht has a coloring algorithm called LargestDegreeFirstColoring[2], which evidently dates back to the 60's. Therefore, this degree-based ordering is not a new idea, even if it's in a different context.
With certain negative weights or constants, a region could have negative multiplied score, which would render my pruning incorrect.
However, this situation is unrealistic, so I've ignored it.
A solution threshold is already in place to account for the fuzzy magic of TASing. It may be possible to include in this threshold a minimum potential negative value
from the node and color weights to ensure correctness.
Execution
This is where the automation ends and the gamer intuition begins. The core algorithm has no notion whatsoever of pen movement; the colorings output by the core are considered goals to be achieved with frame perfect movement. But sometimes, a coloring just doesn't work out, and you lose 10 to 20 frames to meandering movement. For this reason, I added a solution threshold to the core; maybe a slower coloring would be more conducive to fast pen movement and save some frames. This indeed happened on several dinosaurs.
Conclusion
The algorithm is crude, but effective on the given dataset. However, based on what I see in jgrapht, even regular graph coloring is either try all the possibilities with some basic pruning, or weird special cases and heuristics[3]. Therefore, I don't think this approach can be substantially improved.
If you'd like to double check my work or play around with other graphs,[4] my code can be found on GitHub.[5] Go easy on me, now!
[1] Forum/Posts/523096
[2] https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/color/LargestDegreeFirstColoring.html
[3] https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/color/package-summary.html
[4] https://www.romhacking.net/hacks/5126/
[5] https://github.com/warmCabin/dino-coloring/
[2] https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/color/LargestDegreeFirstColoring.html
[3] https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/color/package-summary.html
[4] https://www.romhacking.net/hacks/5126/
[5] https://github.com/warmCabin/dino-coloring/
Comments
As a refresher, there are two coloring modes: point-to-point (p2p) and freehand, which you access by pressing A and B respectively. Freehand lets you move the pen during the fill, while the p2p pen gets stuck in place; this means freehand is faster, ceteris paribus. However, the freehand pen moves 2 pixels at a time, so certain tiny regions may be inaccessible. These are accounted for in my code with "freeze" constraints in the input files, so I can spit out colorings for both modes. A few of them were close enough that I had to try both.
p2p Optimization
When I run my algorithm, I get an output that looks something like this:
Pink: [1, 14, 16, 33, 39, 41, 42, 43, 45, 47, 49, 54] Yellow: [5, 7, 9, 10, 11, 12, 13, 15, 17, 34, 37, 38, 40, 44, 46, 50, 51] Purple: [0, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 35, 52] Gray: [2, 3, 4, 6, 8, 36, 48, 53]
From there, I can sort of color by numbers without really thinking about the picture. "OK, my pen starts at 1, but 14 is a bit of a trek, so let's try looping back to 54 through 33. Yellow's on 34, so now I can switch and hopefully come back to 14 and 16 later. So now we'll do 48 through 51, wrap back to 5 through 17, and... I guess I gray is on 8, so let's go back 9 and..." You get the idea. And once I do this, I get a feel for the patterns and bottlenecks, and realize that maybe I can swap pink and yellow for a more optimal pattern. That's basically the process for p2p colorings.
Freehand Optimization
You want the region where the pen starts to be pink, or at least something very close by. You want to pair long movements with long waits, and do the tiny regions of each color at the end of that pass.
Miracle Frames
I believe in miracles, I swear I've seen a few.
This is something that has plagued blessed me throughout the run. I built each graph on a prototype movie that fills out each section frame perfectly.
This has been 99% accurate, but sometimes, a given section takes a few frames more or less to fill in. This doesn't seem to be based on framerules, or whether you just loaded a new color,
or if you waited X amount of time, or anything predictable. It seems to be based on where you click with the pen, what color you have selected, and what colors are around you[citation needed].
Upper left corners seem to be good for this.
These are only applicable to big regions, particularly gray ones. I don't think it affects any overall colorings, though.
Because these are completely unpredictable, I'm choosing to ignore them. Or I guess, I'm assuming that all colorings are equally affected. I encourage anyone reading this to download my run and check for miracle frames. I'll make you a coauthor and I'll DM you a fun fact about Mega Man 2.
Definitions
- Meander Frames
- How many frames were wasted meandering with the pen after I could have pressed A. The absolute theoretical minumum is 0 for freehand dinos, and V-1 (V=number of regions) for p2p dinos.
- Miracle Frames
- Unpredictable timesave that pops up based on where in the region you started the fill. Especially affects large gray regions.
- Miracle Pixels
- Pixels that grant you miracle frames.
- Dual colorings
- Since yellow and pink are identical (mostly), any coloring has a twin where the yellows and pinks are all swapped. I chose the mathy word "dual" to refer to this.
Dino by dino comments
#1 - Stegosaurus
Regions: 54 Frames saved: 106 Meander frames: 111
| p2p | freehand |
 |  |
Wow, that's a lot of regions! 20 more than the next lowest. I wish I could ease you into this discussion with one or two easy examples, but nope! We're diving straight in, baby. Like the first level of Sokoban.
This dinosaur gave me the most trouble out of the bunch by far. This was not the first dinosaur I colored, so by this point my code and workflow were well established. Most of these colorings took, at the absolute worst, 200 ms to find, but something about this dinosaur absolutely wrecked my code. I left it running overnight, and no progress. I tried having it iterate the nodes in decreasing order of degree to help with the pruning, but still no luck. I then plugged the graph into a real computer science graph theory library, and it told me it takes 5 colors!! I have checks for that in my code, but I don't spit it out until I've already churned through all eleventy billion possibilities. So that's now implemented as a precondition before I attempt any colorings.
After removing some of my evidently impossible adjacencies (don't worry, your favorite toenails are still touching), I got an answer in about 1 second. Turns out the iteration order optimization is necessary, as it still takes the lifetime of the universe if I turn that off. I think this is caused by those 15 spot regions that can be independently colored yellow or pink if the body is purple.
Compared to my old coloring, it kind of swaps the legs and belly regions from gray to pink. In freehand, the eye would be next to the sky, so the coloring ends up way different. It would allegedly be 199 frames slower, so I didn't try it--p2p churn usually only costs 30-60 frames. What good is this code if I'm not going to trust it, anyway?
Now, onto the execution phase. The purple spots are like a desert. In my menuing, I avoided crossing them at all costs.
Except that's not true. I tried a bunch of different routes, and it turns out that crossing the desert and even doing a bit of backtracking
was baaarely worth it over a solution that avoids crossing the desert by cycling the color selection back to pink.
There are 111 meander frames. If I set the algorithm threshold to 111 frames, the thing churns for a couple minutes before running out of heap space. So I'm happy with this coloring...
#2 - Spinosaurus
Regions: 31 Frames saved: 76 Meander frames: 18
This is the first dinosaur with an exclave (0 and 31* on the picture), although you wouldn't know it because I leave it blank. Everything the exclave touches is already touching the sky, so it has no effect on the coloring, for better or for worse.
Compared to the pure output, I swapped regions 23 and 24. It loses 2 frames of fill time, but saves travel time.
My initial coloring had 24 meander frames. I put that as my search threshold, which helped me find an alternate solution with a gray arm that was 4 frames faster overall.
#3 - Brontosaurus
Regions: 27 Frames saved: 177 Meander frames: 0
The first dino I tested my nascent code on. It's one of the most substantial timesaves, and one of the only meander-free ones! It's also the first dinosaur that benefits from a filled background and blank body.
#4 - Viktor
Regions: 27 Frames saved: 40 Meander frames: 1
AINTNOWAY. The algorithm came up with the EXACT same coloring as my manual one! All of this timesave comes from pen movement. Surprisingly, this is not the smallest difference, either.
Tweaking it so the thumb (region 3) is gray is conducive to good pen movement. Saves 35 frames.
#5 - Triceratops
Regions: 26 Frames saved: 181 Meander frames: 1
Compared to the optimal coloring, I swapped which eye is gray and which eye is yellow (regions 18 and 19). Since 25 is so far away, the benefit of the faster eye coloring would lost. Better to be closer.
#6 - Vinnie
Regions: 25 Frames saved: 61 Meander frames: 0
| p2p | freehand |
 |  |
This is the first exclave we actually get to see. Once again, everything it touches already touches the sky, so no effect.
The right eye spot (22) cannot be colored in freehand, but it's adjacent to the sky, so freehand and p2p have two very different solutions. However, Coloring the background and leaving the dino purple is only 7 frames slower than the other way around (according to the algorithm), which is wild. Since this doesn't take pen movement into account, the freehand solution is faster by far.
#7 - Pterodactyl
Regions: 26 Frames saved: 77 Meander frames: 11
This coloring is almost identical to my old one. The only (nontrivial) difference is the major derpage on regions 7 and 8. It's pretty obvious those can be purple. I lose 7 frames at the beginning as I navigate to region 6, which made me wonder if forcing the background pink could have a positive outcome, but it loses 32 frames. Which is surprisingly little...
#8 - Crested
Regions: 29 Frames saved: 45 Meander frames: 1
Compared to the old one: The chest is gray and the arm is pink. I also didn't noticed that you can totally make one of the eyes purple.
Funny story: as I started work on this dino, I had some code in place that attempted to eliminate dual colorings, but it was totally jank and would reject valid solutions. I noticed this by looking at the output for the crested dinosaur and saying I don't believe you. Just raw intuition.
#9 - Duckbill
Regions: 33 Frames saved: 135 Meander frames: 7
21 is unreachable in freehand, but the optimal coloring makes it purple anyway, so it's fine. The eyes are supposed to be yellow, but it takes so long to mash back to yellow that it's 2 frames faster to just use gray.
#10 - Vern (Virgin's own!)
Regions: 32 Frames saved: 21 Meander frames: 75
| p2p | freehand |
|---|---|
 |  |
Still not the smallest timesave!
This one needs to be p2p. Region 27 is untouchable, so regions 0 and 2 need to be colored to accommodate it.
For the record, the old coloring has 80 meander frames, so this coloring is probably only 16 frames faster ceteris paribus.
#11 - Crested Duckbill
Regions: 28 Frames saved: 133 Meander frames: 43
| p2p | freehand |
 |  |
It's a bit of a hot take, but I still consider region 0 and 23 to be adjacent, which leads to another major p2p/freehand difference. The optimal freehand coloring would be 139 frames slower. Not worth it.
I'm actually quite surprised that it's faster to fill region 2 and not leave it purple. I mean, it twists around the beak, the eyebrows, all those spines... I tried freezing region 2 as purple and my code spit out a coloring 84 frames slower.
#12 - Vera
Regions: 30 Frames saved: 33 Meander frames: 58
| p2p | freehand |
 |  |
Lots of very annoying tiny regions here. Not as bad as the stegosaurus, though.
p2p saves 661 frames over freehand here, which is huge. None of that "maybe I should try it..." attitude here!
58 frames seems like a lot of meandering, but upping the threshold isn't usually very productive on p2p drawings. I didn't bother.
It wanted me to make region 22 gray, but I'm not comfortable doing that on a 1-pixel region. It's a gradient, you wouldn't be able to tell! So I forced it pink and lost maybe 5 frames.
For the record, the loss counter reads 79 on the old run. 79 - 58 = 21 frames due to movement, and 12 frames due to the coloring.
#13 - Mini Stegosaurus
Regions: 29 Frames saved: 153 Meander frames: 1
I managed to color all the tiny regions at the bottom and lose 0 frames! This gave me trouble last time. I only lost 1 frame in total to reach the tail (region 6) from the start. Ain't no way to save that frame unless you make the body pink, which is a big no no.
Sometimes, things just work out :)
Sometimes, things just work out :)
I foresee a judging problem here. I now consider regions 18 and 20 to be adjacent, but I didn't last time. Does that invalidate the old run...? Luckily, this is the favorable arrangement of regions 20 and 21, so even under the old interpretation, this coloring is still optimal. I guess you can just pretend this isn't an issue. In fact, you can pretend I didn't even bring it up. Just forget it. It's fine.
#14 - The Mighty T-Rex
Regions: 34 Frames saved: 16 Meander frames: 82
Behold, the smallest timesave of the bunch!
The new coloring is a little bit faster in some of the detail regions, which don't contribute much. Apparently I only save 9 meander frames from last time.
We have another harmless exclave here. I'm also continuing with the hot take that regions 0 and 27 are touching, which forces me to use p2p if I want to keep the background purple.
I tried searching within an 82 frame threshold and got like 100,000 results (including duals). I managed to salvage a few from the spew of console output, and they were just silly. Just random obvious mistakes.
#15 - Torosaur
Regions: 30 Frames saved: 191 Meander frames: 15
| freehand | p2p | freehand, yellowbod |
 |  |  |
My old friend, the forgotten pixel! In case you forgot, too: it can't be reached in p2p mode, but it can in freehand. It's really funny.
These are the two rival colorings, plus one that's freehand but region 0 is forced purple as an added bonus. p2p is considered 147 frames slower, and p2p is already the naturally slower mode.
I tried a 15-frame threshold, and nothing promising came up. One of them has one of the eyes gray, which might be able to serve as a little pit stop.
#16 - Protoceratops
Regions: 22 Frames saved: 261 Meander frames: 9
Behold, the greatest timesave of the bunch!
Just watch the old movie and you'll see. The protoceratops' body is a 767 frame slog. Other than that, regions 4, 5, and 16 (leg, belly, and third appendage) are in the same sort of triplet scenario where you can either make the belly gray, or the other two.
Totals
1724 frames saved in all. This is the actual real life frame count. I occasionally had to move the p2p pen a couple of regions aside to reveal the delicate features it was hiding, which I specifically factored out of the dino-by-dino notes, so this number may be a few frames off from what you expect.
The rerecord count may seem a bit low after reading all of this. A big part of that, I think, is this utility I wrote that can tell me when the next region is ready to be filled. Guessing when the pencil was ready honestly could've taken up half my rerecords in the first movie. Maybe I'll make a test file and see if that's true...
FAQ
More like, anticipated asked questions. Or, a framing device to help me express miscellaneous thoughts.
FDHMEMT?
- Why do you switch palettes? Isn't that slow?
Yep; it's a time/entertainment tradeoff. I just think it's easier on the eyes. This run would sync on any palette;
even though I can move the pen during the palette swaps, I chose not to so that it could sync on the first America palette.
I might make a version that uses that palette.
- Can't you do anything about all that waiting?
Uh, yes? I just saved 30 seconds of it. Besides, you're not playing, you're just watching. It's ALL waiting to YOU.
- I mean, can't you do anything funny with the pencil during the flood fills?
There's not a whole lot I can do. There's no music to jam to, and I'm unable to create sound effects of my own.
In the p2p dinos, I can't even move my pencil, so I am TRULY stuck!
In a couple of freehand dinos, I had to modify a coloring halfway through; in those cases, I implemented the change as a last
second juke. I also tried to put the pen somewhere cute at the end of each freehand coloring. I could always do more, but
would it really make a difference?
- Does it matter what order you do them in?
Nope! Since you have to end each coloring by pressing start, you can't end input early on a long region.
- It's kind of bogus that the background regions count. Aren't those like the oceans in a map?
Fair point. Apparently the RTA community calls that Any%, whereas my interpretation is 100%.
I think the 100% version is more interesting.
- Can't you just reset instead of listening to that stupid jingle?
The title screen is slow. This would lose exactly 200 frames each time.
- This algorithm of yours... may I see it?
Yes!
Final Thoughts
Last year, I assumed there would be very little interest in this run. So I rushed out the submission in one night, making some glaring mistakes in the process, and abandoned the thread. Why dwell on a joke that wasn't gonna land, right? Boy was I wrong. Thank you and apologies to everyone, especially FractalFusion for the graphs, and Randomno for picking up my slack and fixing the movie. Hopefully this can make up for it.
nymx: Claiming for judging.
nymx: I remember the debacle of this submission last year. I wasn't sure if it was a joke or not. Well, it has turned out to be a phenomenon. This time around, the science behind this is even more fascinating than ever. The idea of a "four color theorem", actually is very amusing. Having 7 votes...all yes (me included :) ), I see no other option than to continue the trend of "Alternative" ..as this is very good work. Congrats on the computations. This is amazing to see how far this concept can go.
Accepting over [5436] NES Color a Dinosaur "four color theorem" by warmCabin & Randomno in 08:09.93 to Alternative.
despoa: Processing...