How long does it take to paint a stick?

Question

(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.

Goal

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.

Input

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

Output

These numbers are the least number of steps needed to paint the sticks.

4

3

4

5

4

Explanations

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.

Answer 1

Python 3, 60 59 bytes

p=lambda s:len(s)and-~min(sum(map(p,s.split(c)))for c in s)

Try it online!

Ungolfed:

def paint(stick):
    if not stick:
        return 0
    return 1 + min(
        sum(paint(part) for part in stick.split(c))
        for c in stick
    )

Answer 2

GolfScript, 82 72 67 characters

.,n*{:c,,{[).2$1<*\c>+1$.,,{).2$<\3$<=},,.@>@@>]}%\;{~S)}%$0+0=}:S~

Reasonably fast for a GolfScript program, examples:

> hyghgy
4

> pbgbrgrp
5

The algorithm used works through the colors left-to-right recursively, according to the following statements:

• Ignore all parts from the left which already have the required color. Overpainting them again will not provide a better answer.

• If the complete stick already has the desired color, return 0 steps as result.

• Otherwise, take the target color of the now leftmost part (i.e. the first not in the desired color).

  • Paint 1 part with the target color and recurse.
  • Paint 2 parts with this color and recurse.

  ...

  • Paint the whole remaining stick with this color and recurse.

  Take the minimum of all those numbers and add 1 (for the current step). Return this as the optimal number of steps.

This algorithm works, because the leftmost part has to be painted at one time anyways, so why not do it immediately - in any possible fashion.

.,n*         # prepare the initial situation (target stick, unpainted stick)
             # used n instead of '-' for the unpainted parts, because it is shorter
{            # Define the operator S which does t c S -> n
             #   - t: the desired target colors
             #   - c: the stick as it is colored currently
             #   - n: minimum number of steps required to go from c to t
  :c         # Assign the current configuration to the variable c
  ,,{[       # Map the list [0 1 2 .. L-1]
             # We will build a list of all possible configurations if we paint
             # the stick with the 0th part's color (either 1 or 2 or 3 or ... parts)
    ).       # Increase the number, i.e. we paint 1, 2, 3, ... L parts, copy
    2$1<     # Take the first color of the target configuration
    *        # ...paint as many parts
    \c>+     # ...and keep the rest as with the current stick
    1$       # take the target configuration
             # Top of stack now e.g. reads
             #    h----- hyghgy (for i=0)
             #    hh---- hyghgy (for i=1)
             # Next, we strip the common leading characters from both strings:
    .,,      # Make list [0 1 2 ... L-1]
    {        # Filter {}, all the numbers for which the first j+1 parts are the same
      ).     # incr j
      2$<    # take leftmost j parts of stick A
      \3$<   # take leftmost j parts of stick B
      =      # are they equal?
    },,      # The length of the result is the number of common parts.
    .@>      # cut parts from A
    @@>      # cut parts from B
  ]}%
  \;         # Remove the target from the stack (not needed anymore)               
             # We now have a list of possible paintings where 1, 2, ..., L parts were
             # painted from the left with the same color.
             # All configurations were reduced by the common parts (they won't be
             # painted over anyways)
  {~S)}%     # Call the method S recursively on the previously prepared configurations
  $0+0=      # $0= -> sort and take first, i.e. take the minimum, 0+ is a workaround
             # if the list was empty (i.e. the operator was called with a stick of length 0).
}:S
~            # Execute S

Answer 3

JavaScript: 187 Bytes

Assuming we're allowed to just have the input and output to a function (please)!

function p(w){var j,l,s=-1,i,m=i=w.length;if(m<2)return m;for(;i--;){l = 1;for(var k=-1;(j=k)!=m;){if((k=w.indexOf(w[i],++j))==-1)k=m;l+=p(w.substring(j,k));}if(s==-1||l<s)s=l;}return s;}

157 Bytes by doing further ugly optimization (Which is part of the point, and I found incredibly fun):

function p(w){var j,l,s=-1,i,m=i=w.length;if(m<2)return m;for(;i--;s<0|l<s?s=l:1)for(l=1,j=0;~j;)l+=p(w.substring(j,(j=w.indexOf(w[i],j))<0?m:j++));return s}

135 Bytes I realised that the length of the input is an upper bound and I don't need to handle trivial cases separately now.

function p(w){var j,l,s,i,m=s=i=w.length;for(;i--;l<s?s=l:1)for(l=1,j=0;~j;)l+=p(w.substring(j,~(j=w.indexOf(w[i],j))?j++:m));return s}

Test cases:

p("YRYGR")
4
p("grG")
3
p("GyRyGyG")
4
p("pbgbrgrp")
5
p("hyghgy")
4

Expanded version:

function paint(word) {
    var smallest = -1;
    if(word.length < 2) return word.length;
    for(var i = word.length; i-->0;) {
        var length = 1;
        for(var left, right = -1;(left = right) != m;) {
            if((right = word.indexOf(word[i],++left)) == -1) right = word.length;
            if(left != right) length += paint(word.substring(left , right));
        }
        if(smallest == -1 || length < smallest) smallest = l;
    }
    return smallest;
}

For every character of the input, calculate the length of the pattern if we paint that colour first. This is done by pretending we paint that colour and then making sub sections out of the bits that aren't that colour, and recursively calling the paint method on them. The shortest path is returned.

Example (YRYGR):

Initially, try R. This gives us the sub groups Y and YG. Y is trivially painted in one go.

For YG: Try G, Y is trivial, length 2. Try Y, G is trivial, length 2. YG is therefore length 2.

Painting R first therefore gives us 1 + 1 + 2 = 4

Then try G. This gives us the sub groups YRY and R. R is trivial.

For YRY:

Try Y: R is trivial, length 2. Try R: Y and Y are the two groups, length 3.

YRY is length 2.

Painting G first gives 1 + 1 + 2 = 4

Then try Y. This gives the sub groups R and GR. R trivial, GR is length 2. Y is length 4

This implementation would then check R and Y again to reduce code length. The result for YRYGR is therefore 4.

Answer 4

Python, 149 chars

D=lambda s:0 if s=='?'*len(s)else min(1+D(s[:i]+'?'*(j-i)+s[j:])for i in range(len(s))for j in range(i+1,len(s)+1)if set(s[i:j])-set('?')==set(s[i]))

I use ? to mark an area that may be any color. D picks a contiguous region of the stick that contains only a single color (plus maybe some ?s), colors that region last, replaces that region with ?s, and recurses to find all the previous steps.

Exponential running time. Just barely fast enough to do the examples in a reasonable time (a few minutes). I bet with memoization it could be much faster.

Answer 5

Python 3 - 122

def r(s,a):c=s[0];z=c in a;return s[1:]and min([1+r(s[1:],a+c)]+[r(s[1:],a[:a.rfind(c)+1])]*z)or(1-z)
print(r(input(),''))

It seems to work, but I'm still not 100% sure that this method will always find the minimum number of steps.

Answer 6

CoffeeScript - 183 247 224 215 207

x=(s,c='')->return 0if !s[0]?;return x s[1..],c if s[0]is c;l=s.length;return x s[1...l],c if s[l-1]is c;i=s.lastIndexOf s[0];1+(x s[1...i],s[0])+x s[i+1..],c
y=(z)->z=z.split "";Math.min (x z),x z.reverse()

Demo on JSFiddle.net

Ungolfed version including debug code and comments:

paintSubstring = (substring, color = '####') ->
  console.log 'Substring and color', substring, color, substring[0]
  # no need to color here
  if !substring[0]?
    return 0
  # no need to recolor the first part
  if substring[0] is color
    return paintSubstring (substring[1..]), color
  l = substring.length
  # no need to recolor the last part
  if substring[l-1] is color
    return paintSubstring substring[0...l], color
  # cover as much as possible
  index = substring.lastIndexOf substring[0]
  part1 = substring[1...index]
  part2 = substring[index+1..]
  console.log 'Part 1:', part1
  console.log 'Part 2:', part2
  # color the rest of the first half
  p1 = paintSubstring part1, substring[0]
  # color the rest of the second half, note that the color did not change!
  p2 = paintSubstring part2, color
  # sum up the cost of the substick + this color action
  return p1+p2+1
paintSubstringX=(x)->Math.min (paintSubstring x.split("")), paintSubstring x.split("").reverse()
console.clear()
input = """YRYGR
grG
GyRyGyG
pbgbrgrp
aaaaaaaa
hyghgy""".split /\n/
for stick in input
  console.log paintSubstringX stick

Answer 7

Haskell, 118 86 characters

p""=0
p(a:s)=1+minimum(map(sum.map p.words)$sequence$map(a%)s)
a%b|a==b=b:" "|1<3=[b]

Test runs:

λ: p "YRYGR"
4

λ: p "grG"
3

λ: p "GyRyGyG"
4

λ: p "pbgbrgrp"
5

λ: p "hyghgy"
4

λ: p "abcacba"
4

This method isn't even all that inefficient!

Answer 8

Haskell, 143 chars

f s=g(r n ' ')0where{r=replicate;n=length s;g p l=minimum$n:[0|p==s]++[1+g(take i p++r(j-i)(s!!i)++drop j p)(l+1)|l<n,i<-[0..n-1],j<-[i+1..n]]}

This tries all possible rewritings up to the length of the string, and goes until it finds one that constructs the input pattern. Needless to say, exponential time (and then some).

Answer 9

A simple breadth first search. It doesn't put anything on the queue that's already been seen. It works in under a second for all of the examples but 'pbgbrgrp' which actually takes a full minute :(

Now that I have something that works I'll be working on finding something faster and shorter.

Python - 300 296

def f(c):
 k=len(c);q=['0'*99];m={};m[q[0]]=1
 while q:
  u=q.pop(0)
  for x in ['0'*j+h*i+'0'*(k-j-i) for h in set(c) for j in range(1+k) for i in range(1,1+k-j)]:
   n=''.join([r if r!='0' else l for l,r in zip(u,x)])
   if n == c:
     return m[u]
   if not n in m:
    m[n]=m[u]+1;q.append(n)