(Based on this Math.SE problem, which also provides some graphics)
I have a stick which looks kinda like this:
I want it to look kinda like this:
I'm not an expert painter, however, so before I start such an ambitious DIY project, I want to make sure that I'm not in over my head.
Your program should tell me how how many steps are involved in painting this stick. Each step involves painting a continuous area with a solid color, which covers up previous layers of paint. For the above example, I could paint the left half blue, the right half red, and then the two separate green areas for a total of 4 steps (the green is not continuously painted).
Here it is in ASCII:
------ bbb--- bbbrrr bgbrrr bgbrgr
There are a couple different ways to paint this stick and end up with the same result. I'm only interested in the time estimate, however, which is four steps.
Your program should output the minimum number of steps needed to paint a stick with a given color scheme. The paint scheme will be in the form of a string of characters, while output will be a number. This is code golf. Shortest program wins.
Your program will receive the coloring scheme for a stick in the form of a string of letters. Each unique letter (case sensitive) represents a unique color.
YRYGR grG GyRyGyG pbgbrgrp hyghgy
These numbers are the least number of steps needed to paint the sticks.
4 3 4 5 4
This is how I arrived at the above numbers. Your program does not need to output this:
----- YYY-- YRY-- YRYG- YRYGR --- g-- gr- grG ------- GGGGGGG GyyyGGG GyRyGGG GyRyGyG -------- pppppppp pbbbpppp pbbbrrrp pbgbrrrp pbgbrgrp ------ -yyyyy -ygggy hygggy hyghgy
Edit: I'll add more test cases if they prove to be more difficult test cases.