TASVideos' favorite game is back, and it's badder than ever. In this movie, I color not just one, but all sixteen dinosaurs, in order to demonstrate a famous mathematical theorem.

Game objectives

  • Color all 16 dinosaurs such that no two adjacent regions are the same color
  • Do so the smallest number of colors
  • Optimize for time

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: never, ever let it cool 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.
I hate to invoke Wikipedia on another one of these things, but... here you go.

Comments

The goal of this movie is to demonstrate the four color theorem on each dinosaur in the popular Color a Dinosaur game for the NES. There are many valid colorings for each dinosaur, but I'm not satisfied with just any of them. I want to show the fastest ones I can find! My colors of choice for this run are purple, pink, yellow, and a dither pattern forming what colorhexa calls "grayish blue," but I just call "ugly."

Techniques

Obviously, it's fastest to leave a region blank.
Solid colors are better than patterns, because patterns need two passes to fill in.
The bigger the region, the longer it takes to fill in. The background does count as a region, so I had to leave those alone.
No, the black outlines don't count as a region.
So, based on these properties, I tried to keep as many things blank (purple) as possible, and leave the ugly gradient color to tiny regions like toenails and fingers. I also tried to make sure the region where the cursor starts is pink, and pair long movements with long waits.
Sometimes it's hard to tell whether two regions are really touching with these black outlines. I erred on the side of caution in these cases. Remember, no possible interpretation of the borders could possibly require a fifth color.
Not many people know this, but you can press B to load each picture in freehand mode instead of the default point-to-point mode. Freehand is faster, because you can move the cursor during the fill sequence; in point-to-point mode, you're stuck in place. However, the freehand cursor moves two pixels at a time, meaning tiny regions can be inaccessible! Affected dinos:
  • stegosauraus (Level 1)
  • Vinnie (Level 6)
  • Duckbill (Level 9)
  • Vern (Level 10)
  • Crested Duckbill (Level 11)
  • Vera (Level 12)
  • T-Rex (Level 14)
  • Toro (Level 15)
For most of them, I couldn't find colorings that left the tiny spots and the background blank, so I was forced to lose some time and use point-to-point mode on those levels. But for the Duckbill, I was able to find a coloring that left the specular highlight purple. For T-Rex, it's the left eye (his right eye) that can't be colored, and it's kind of borderline whether or not it's touching the sky.
In point-to-point mode, you can alternate right and up (or left and down) to move every frame.

Drawing by drawing comments

I made some test drawings in paint.net before TASing all but the first two stages. Enjoy.

Bronotsaurus (Drawing 3)

Victor (Drawing 4)

Triceratops (Drawing 5)

This one was interesting. I originally colored those titular three horns at the top ugly, but I realized they could be yellow. I simply switched back to yellow at the end and saved 43 frames. Then I redid the whole thing as I would have done if I had originally planned to make those yellow, and it was 15 frames slower. There's lots of room for optimization in this game...

Vinnie (Drawing 6)

Pterodactyl (Drawing 7)

Even though there's a horizon line here, it doesn't go all the way to the right. The background is one region if you fill it.

Crested Dinosaur (Drawing 8)

Duckbill (Drawing 9)

Vern (Drawing 10)

Crested Duckbill (Drawing 11)

This one was actually a bit of a challenge to find a coloring for. The large pink section (with the tail and the right arm) cannot be the same color as the ground.

Vera (Drawing 12)

Another fake-out horizon line.

Mini Stegosaurus (Drawing 13)

This is supposed to be a dinosaur? Interestingly, I forgot the lower half of the background had to be a different color until I finished coloring the whole thing, then I was able to repair it with surprisingly few changes.

T-Rex (Drawing 14)

Another fake-out horizon line.

Torosaurus (Drawing 15)

There is a forgotten pixel between the two hind legs of this dino. It is skipped in point-to-point mode, so you can never color it there. However, you can hit it with the freehand pencil. Lucky! Unfortunately, the eye highlights are not accessible with the freehand pencil, so you can never fill every single region in this dinosaur. I decided that the right pixel is surrounded by the sclera and doesn't touch the sky, which means I get to show off the forgotten pixel.
This coloring was kind of weird to implement. The pink regions are kinda far apart, so I ended up switching back and forth to avoid a long walk from the background sliver to the toenail.
I filled it in yellow so the big leg could be purple.

Protoceratops (Drawing 16)

The final boss. Your security is his motto. I know that's supposed to be a plant in the background, but it looks like a weird appendage, doesn't it? It is not present in the manual.
It contains another fake-out horizon line.
Can you spot the mistake in the first image? Try crossing your eyes and letting the images merge, it's fun.

Time/entertainment tradeoffs

I chose palette 3 because I'm the TASer, I get to pick. It's possible to move the freehand cursor during palette changes, but I opted not to do this so my inputs could theoretically sync on palette 0. I recommend the judges consider future improvements to this category on an IL basis.
I sacrificed 4 frames in the Vera drawing to show what the eyes look like.
I sacrificed 2 frames on the T-rex drawing to show what the teeth look like.

Tidbits

The manual says you can't override gradients, but in freehand mode, you can overwrite them one pixel at a time. Weird, huh? Equally weird, you can also attempt to fill in the black outline as a region, which makes the sound but does nothing.
In the manual art, Vera is not holding a tree branch.
The manual describes Vern as "Virgin's Own" (Virgin being the publisher), implying that all the rest of these dinosaurs really existed. Even the Mini Stegosaurus.
The crested duckbill lets you start pressing buttons 1 frame earlier. Why?? Good thing I'm constantly doubting myself and checking things like that.

nymx: Claiming for judging.

nymx: What a headache! The conversation, sparked up by myself in the judges thread, has really brought light and confusion simultaneously. This might have been a joke submission, but there are points that actually make this a legitimate run; however, #8258: Samsara's NES Color a Dinosaur in 02:07.46 has thrown a wrench in judging this. It is faster...which is what we are all about. So are we thinking this should be an "Alternative" classification? Not sure.
The confusion comes from an analogy of "Photoshop"...
Photoshop is a game. It gives you tools and the goal is that you use its title as a command. You just have to photoshop. Once you've photoshopped, you've completed the game. Can we have a community consensus on this one please? Wait we first need a community agreement on what is considered actually photoshopping...
Here is the other issue...
  • A video game poses a virtual task. It requires the player to accomplish some in-game job.
In this case, I was awaken to the fact that this game doesn't really monitor or provide feedback that "coloring" has been accomplished.
I don't believe I'm the person to figure this out. If it deserves publication, then it would have to meet some entertaining goal in "Alternative", since #8258: Samsara's NES Color a Dinosaur in 02:07.46 does it faster.
Dropping out.

feos: Hoo boy...
Game choice for standard publications is limited to computer programs that meet our definition of a video game. Some programs will miss some of those traits, in which case we decide their acceptance based on a community consensus. If a program is not considered eligible for the standard class, it may still be acceptable for Alternative if its TAS is entertaining.
#8257: Samsara's NES Color a Dinosaur "fastest dinosaur" in 00:10.67 #8258: Samsara's NES Color a Dinosaur in 02:07.46 aimed for fastest completion and we were unable to agree on what constitutes completion, nor whether it could even be called a game. But this movie aims for entertainment, and quite unexpectedly the audience did like it. This is not a playaround, but a demonstration kinda goal that we never had before. But since it excited people, and it's well done, it's a nice thing to have published.
Accepting to Alt.
fsvgm777: Oh man, we've come a long way. Processing.
Also changed the branch to "four color theorem" to better represent what's being demonstrated here.


TASVideoAgent
They/Them
Moderator
Joined: 8/3/2004
Posts: 15626
Location: 127.0.0.1
Alyosha
He/Him
Editor, Emulator Coder, Expert player (3827)
Joined: 11/30/2014
Posts: 2834
Location: US
Very creative use of dinosaur coloring, nice work. Although the actual video is too slow to be entertaining.
Banned User
Joined: 1/6/2023
Posts: 263
Singlehandedly brought dinosaurs back from extinction
Published TASes: #1, #2, #3, #4, #5, #6, #7, #8, #9, #10, #11, #12 Please consider voting for me as Rookie TASer Of 2023 - Voting is in December 2023 My rule is quality TASes over quantity TASes... unless I'm bored.
Sand
He/Him
Player (143)
Joined: 6/26/2018
Posts: 175
Great concept.
Moderator, Senior Ambassador, Experienced player (907)
Joined: 9/14/2008
Posts: 1014
This was bearable at 2x :)
I was laid off in May 2023 and became too ill to work this year and could use support via Patreon or onetime donations as work on TASBot Re: and TASBot HD is stalled. I'm dwangoAC, TASVideos Senior Ambassador and BDFL of the TASBot community; when healthy, I post TAS content on YouTube.com/dwangoAC based on livestreams from Twitch.tv/dwangoAC.
Editor, Expert player (2080)
Joined: 6/15/2005
Posts: 3284
While browsing the Workbench, I didn't even realize this was about the 4-coloring theorem until I looked very closely at the branch name the 3rd/4th time around, upon which my interest immediately went from 0 to 100. Nice to see there are mathematicians on this site.
dart193
He/Him
Player (35)
Joined: 1/20/2013
Posts: 63
MAThVideos: Math demonstrating game movies. When TASing skills are just not enough. Awesome idea. I like how these AFD submissions go into totally different dimensions than you would imagine.
adelikat
He/Him
Emulator Coder, Site Developer, Site Owner, Expert player (3576)
Joined: 11/3/2004
Posts: 4754
Location: Tennessee
Dang, didn't notice this one during the festivities, thanks for the submission. Unfortunately, I think we have officially gone too far with this gag. Fortunately, I live for going too far with gags.
It's hard to look this good. My TAS projects
Alyosha
He/Him
Editor, Emulator Coder, Expert player (3827)
Joined: 11/30/2014
Posts: 2834
Location: US
drawing 14 contains an error. Between the T'rex's legs the background is the same color above and below the horizon.
Dimon12321
He/Him
Editor, Reviewer, Experienced player (597)
Joined: 4/5/2014
Posts: 1227
Location: Romania
If the painting speed for big parts wasn't so long, I'd vote "yes". And, on this regard, the entertainment value is bigger at Samsara's submission.
TASing is like making a film: only the best takes are shown in the final movie.
lexikiq
She/Her
Active player (458)
Joined: 8/13/2018
Posts: 109
Location: United States of America
For what it's worth, this is my favorite of the 3 TASes of this game submitted within the past month. It is a much more interesting concept with much more technical skill and produces a much more entertaining result (even if it's a bit unbearably slow to get there at times). Per site rules it might technically be unpublishable or whatever (I'm not convinced, just call it a playaround or something idk) but of the three I'd most like to see this one published, maybe alongside "100%" "(baseline)".
Site Admin, Skilled player (1255)
Joined: 4/17/2010
Posts: 11495
Location: Lake Char­gogg­a­gogg­man­chaugg­a­gogg­chau­bun­a­gung­a­maugg
So far it's getting pretty decent feedback! Maybe it doesn't look all that enjoyable directly, but the technical marvel seems to really amuse people.
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting.
Post subject: Movie published
TASVideoAgent
They/Them
Moderator
Joined: 8/3/2004
Posts: 15626
Location: 127.0.0.1
This movie has been published. The posts before this message apply to the submission, and posts after this message apply to the published movie. ---- [5332] NES Color a Dinosaur "four color theorem" by warmCabin in 08:11.72
lexikiq
She/Her
Active player (458)
Joined: 8/13/2018
Posts: 109
Location: United States of America
Alyosha wrote:
drawing 14 contains an error. Between the T'rex's legs the background is the same color above and below the horizon.
This is addressed in the submission notes, by the way:
warmCabin wrote:
T-Rex (Drawing 14) Another fake-out horizon line.
See also:
warmCabin wrote:
Pterodactyl (Drawing 7) Even though there's a horizon line here, it doesn't go all the way to the right. The background is one region if you fill it.
Joined: 6/13/2023
Posts: 1
Oops... 😅
Patashu
He/Him
Joined: 10/2/2005
Posts: 4045
yxkalle wrote:
Oops... 😅
It looks like you could swap the yellow belly and the gray crotch's colours and you'd be fixed again?
My Chiptune music, made in Famitracker: http://soundcloud.com/patashu My twitch. I stream mostly shmups & rhythm games http://twitch.tv/patashu My youtube, again shmups and rhythm games and misc stuff: http://youtube.com/user/patashu
Masterjun
He/Him
Site Developer, Expert player (2047)
Joined: 10/12/2010
Posts: 1185
Location: Germany
The eyes being the same color seems also wrong here. Or is it that they can't be independently colored by the game?
Warning: Might glitch to credits I will finish this ACE soon as possible (or will I?)
Editor, Active player (459)
Joined: 2/11/2018
Posts: 240
Fixed the two drawings. I hope. For the record I did this because there was a lengthy discussion about the mistakes in Discord. It's likely improvable time-wise.
Joined: 1/14/2016
Posts: 100
lexikiq wrote:
Alyosha wrote:
drawing 14 contains an error. Between the T'rex's legs the background is the same color above and below the horizon.
This is addressed in the submission notes, by the way:
warmCabin wrote:
T-Rex (Drawing 14) Another fake-out horizon line.
See also:
warmCabin wrote:
Pterodactyl (Drawing 7) Even though there's a horizon line here, it doesn't go all the way to the right. The background is one region if you fill it.
It's a bit confusing since Drawing 7 does have a small bit of background above the horizon line (between the tail and the wing) that is gray instead of blue, but in Drawing 14 the bit between the legs gets coloured with the rest of the background. So it's impossible to have the bit between the legs be a different colour.
Editor, Active player (459)
Joined: 2/11/2018
Posts: 240
Had another look through These eyes in dino 2 are definitely touching. This was discussed (for far too long) on Discord whether the pink segments are touching. I think we concluded that they are as they share an adjacent pixel, with adjacent including diagonals (or, there are other ways to come to that conclusion). If anyone has a rigorous method to determine this I'd like to know. I think it's somewhat unanswerable, as the four color theorem applies to abstract shapes, rather than pixels, especially pixel art with an outline.
Editor, Expert player (2080)
Joined: 6/15/2005
Posts: 3284
Maybe: Two separately colorable regions A and B are deemed to be touching if there is a colorable pixel in A and a colorable pixel in B where the distance between their centers is less than 2.5 pixel lengths. The goal is to consider minimum(-distance) offsets (±1,±1), (0,±2), (±2,0), (±1,±2) and (±2,±1) as touching/adjacent, but (±2,±2), (0,±3) or (±3,0) as NOT touching/adjacent (so as to avoid the problem of "corner adjacency" which is not a valid interpretation of adjacency in the four-color theorem). The former offsets all have distance sqrt(5)≈2.236 or less, and the latter ones have distance sqrt(8)≈2.828 or greater. Possible issues: Colorable regions could have minimum offsets of (0,±1) or (±1,0), which may lead to "crowding" (but I'm not aware of any cases so far). Colorable regions could also have minimum offsets of (±2,±2), (0,±3) or (±3,0) and should be considered touching by common sense (but I'm also not aware of any cases so far). Using this metric, the pink segments have a minimum offset of (±2,±1) and so are deemed touching. Around the 2x2 black square in the same image near the top center, the outside and inside blue segments are not touching, and the left yellow and right pink segments are also not touching, because the minimum offsets are (0,±3) and (±3,0), respectively.
Editor, Active player (459)
Joined: 2/11/2018
Posts: 240
Can you explain this like I'm the intended demographic for Color a Dinosaur? Thanks though, seems sufficient for an answer.
Editor, Expert player (2080)
Joined: 6/15/2005
Posts: 3284
Randomno wrote:
like I'm the intended demographic for Color a Dinosaur?
lol Though I realized shortly after my post that I could have just used overlapping rectangles. So like (words in [square brackets] are optional): Two [colorable] regions are deemed to be touching if there is a 2x3 pixel rectangle [in any position and orientation] that overlaps both of them. In case of certain edge (no pun intended) cases, we could include/replace with a slightly larger rectangle with an additional restriction: Two [colorable] regions are deemed to be touching if there is a 2x3[ and/or 3x3 and/or 3x4] pixel rectangle [in any position and orientation] that overlaps both of them, and no other [colorable] regions.
Editor, Expert player (2080)
Joined: 6/15/2005
Posts: 3284
(very large; recommended to view image in new tab) Here is a PNG that I labelled showing what I believe are all the colorable regions (let me know if I missed any!). The only purpose of this PNG is to identify the colorable regions by labels 1..9a..zA..V (excluding l and I). Generally I let 1 be the background, 2 the ground if separately colorable, and 2/3 the largest region of the dino. Beyond that, there is no rule to the labelling. I tried to keep labels relatively close together, and the sclera usually has an earlier label than the eye itself (sorry for the mediocre positioning). #2, #6 and #14 were the only ones I found that have phantom bounded regions that are forced to be the same color as the background "1" (they are indicated in the PNG). Using 2x3 or 3x2 overlapping rectangles as the basis for when regions touch each other, I made a list of adjacencies. Each pair of regions that touches each other by this rule is specified, with the earlier label (that comes earlier in the ordering 1..9a..zA..V) on the left of ":" and the later label on the right. I have also included a number of possibly debatable "touches" that are not covered by the above rule. All of them concern the eyes. The debatable ones are in brackets () and also has a question mark somewhere in there. #3, #9, #10, #11, #12, #13 and #16 are affected.
#1

1:23456789abcdefghijmnopqrstuvwxyzABDEF
2:347cgopqrstuvwyABDEGHJKLMNOPQRSTUV
3:4
4:5678
7:8abc
8:9
9:a
a:b
c:degh
d:e
e:f
g:h
h:ijk
j:km
k:m
m:n
o:p
q:r
w:x
y:z
B:C
D:EF

#2

1:23456789abmnprtuv
2:34567bcjnprstuw
4:5
6:7
7:89aw
8:9
9:a
b:cdefghijkm
e:f
n:ov
p:qv
s:t
t:u

#3

1:23456789abcdefghijkmnopq(s?)
2:37beijkmnopqrs
3:456
4:5
5:6
7:89abc
8:9
9:a
a:c
b:cd
c:d
e:fgh
f:g
g:h
(r:s?)

#4

1:23456789acdefghijkopqs
2:3567bcdefghijkmnopqrs
3:45
6:7
7:89abc
8:9
9:a
c:d
d:e
f:g
g:h
j:k
k:mno

#5

1:234bcdefghijkmr
2:3579a
3:4569abcdefghmnor
5:67
6:789
7:89
8:9
9:a
i:m
j:m
k:m
m:no
n:op
o:q

#6

1:2345679acegijmnopq
2:36
3:45689abcdefghijmopq
4:56
j:km
k:m
m:n

#7

1:23456789cdhiknopq
2:34569abcdfhjkmqr
3:4
4:5
6:7
7:8
d:ef
f:g
h:ijr
j:k
k:mnopq

#8

1:23456789abcdefghijps
2:36
3:456789abcdefkmnopqsu
5:6u
d:e
f:gkm
g:hm
h:imn
i:jno
j:op
k:m
m:n
n:o
o:p
q:rs
s:t

#9

1:2368efghijkmnoptvy
2:3589abcdg
3:456789abfghijkmntxy
4:5
6:78
7:8
8:bcd
9:a
a:b
c:d
e:f
g:hijkmnt
h:i
i:j
j:k
k:m
m:n
o:p(q?)rt
p:q
r:st
t:uvwx
v:wy
w:xy
x:y

#10

1:23eijkmnopqrvx
2:3456789dfghi
3:456adejkmnopqrsuvwx
4:56
5:6
6:789ab
7:8
8:9
9:bd
a:bcd
b:cd
c:d
d:efg
e:ghi
f:g
g:h
h:i
k:m
m:n
o:p
p:q
q:r
s:tu
t:u
(u:v?)

#11

1:234589bcegiknqst
2:59a
3:458cdefghijkmnopqrst
4:5
5:6789
6:79
7:9
8:9
9:a
b:c
o:(p?)q
(q:r?)
s:t

#12

1:23456789abcdefgmnopq
2:789acdefghikmnopqrst
3:6
4:6
5:67
6:7
7:8t
8:t
a:bc
b:c
c:d
f:ghi
(g:h?)
h:jk
i:jk
(j:k?)
m:n
n:o
o:p
p:q

#13

1:2345fghinopqrstu
2:356789bcdeg
3:5abcdefghiknoprst
4:5
5:6a
6:789ab
7:8
8:9
b:c
c:d
f:g
h:i
i:(j?)k
(k:m?)
n:o
p:q
s:t
t:u

#14

1:23456789abcdefghijprtuvwxyz
2:5bghijkmnoprv
3:4
4:5
5:6b
6:9ab
7:8
8:9a
9:a
b:cdefvwxy
c:d
d:e
h:j
i:k
j:k
k:mn
m:n
n:o
p:qrz
r:sz

#15

1:23defghijkmnopsuv
2:3457bde
3:4789abcdghijkmnopqsuv
4:567
5:7
6:7
7:89
8:9
a:b
c:d
d:e
g:h
m:n
n:o
q:rs
s:t

#16

1:2345689cdejmn
2:3abcdefghijkmn
3:45789a
4:57
5:678
6:8
8:9
9:ab
a:b
(f:g?)
(h:i?)
j:k
From discussion so far, it seems that the eyes should be deemed touching whichever regions make up the sclera? Or anything nearby? In that case, the rule would need a bit of updating. (The goal is to have a rule that aligns with common sense.)
Editor, Active player (459)
Joined: 2/11/2018
Posts: 240
Great list
FractalFusion wrote:
From discussion so far, it seems that the eyes should be deemed touching whichever regions make up the sclera? Or anything nearby? In that case, the rule would need a bit of updating. (The goal is to have a rule that aligns with common sense.)
I'm not sure what discussion you're referring to. I've only been considering the inner eye, but I suppose if you ignore the sclera, you're starting to treat black as a fifth colour.