Quanto tempo leva para pintar um palito?

(Com base neste problema Math.SE , que também fornece alguns gráficos)

Eu tenho um stick que fica assim:

Eu quero que fique assim:

No entanto, não sou um pintor especialista, portanto, antes de iniciar um projeto tão ambicioso de bricolage, quero ter certeza de que não estou enlouquecendo.

Seu programa deve me dizer quantas etapas estão envolvidas na pintura desse bastão. Cada etapa envolve pintar uma área contínua com uma cor sólida, que cobre as camadas anteriores de tinta. No exemplo acima, pude pintar a metade esquerda azul, a metade direita vermelha e as duas áreas verdes separadas por um total de 4 etapas (a verde não é pintada continuamente).

Aqui está em ASCII:

------
bbb---
bbbrrr
bgbrrr
bgbrgr

Existem algumas maneiras diferentes de pintar esse bastão e acabar com o mesmo resultado. No entanto, estou interessado apenas na estimativa de tempo, que é de quatro etapas.

Objetivo

Seu programa deve produzir o número mínimo de etapas necessárias para pintar um pedaço de pau com um determinado esquema de cores. O esquema de pintura será na forma de uma sequência de caracteres, enquanto a saída será um número. Isso é código de golfe. O programa mais curto vence.

Entrada

Seu programa receberá o esquema de cores para um bastão na forma de uma sequência de letras. Cada letra exclusiva (diferencia maiúsculas de minúsculas) representa uma cor única.

YRYGR

grG

GyRyGyG

pbgbrgrp

hyghgy

Resultado

Esses números são o menor número de etapas necessárias para pintar os palitos.

4

3

4

5

4

Explicações

Foi assim que cheguei aos números acima. Seu programa não precisa produzir isso:

 -----
 YYY--
 YRY--
 YRYG-
 YRYGR

 ---
 g--
 gr-
 grG

 -------
 GGGGGGG
 GyyyGGG
 GyRyGGG
 GyRyGyG

 --------
 pppppppp
 pbbbpppp
 pbbbrrrp
 pbgbrrrp
 pbgbrgrp

 ------
 -yyyyy
 -ygggy
 hygggy
 hyghgy

Editar: adicionarei mais casos de teste se eles se revelarem mais difíceis.

GolfScript, 82 72 67 caracteres

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

Razoavelmente rápido para um programa GolfScript, exemplos:

> hyghgy
4

> pbgbrgrp
5

O algoritmo usado funciona através das cores da esquerda para a direita recursivamente, de acordo com as seguintes instruções:

• Ignore todas as peças da esquerda que já tenham a cor necessária. Pintar demais de novo não fornecerá uma resposta melhor.
• Se o bastão completo já tiver a cor desejada, retorne 0 etapas como resultado.

• Caso contrário, pegue a cor alvo da parte agora mais à esquerda (ou seja, a primeira não na cor desejada).

  • Pinte 1 parte com a cor alvo e repita.
  • Pinte 2 peças com esta cor e repita.

  ...

  • Pinte todo o palito restante com esta cor e repita.

  Pegue o mínimo de todos esses números e adicione 1 (para a etapa atual). Retorne isso como o número ideal de etapas.

Esse algoritmo funciona, porque a parte mais à esquerda precisa ser pintada de uma só vez, então porque não fazê-lo imediatamente - de qualquer maneira possível.

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

JavaScript: 187 bytes

Supondo que nos é permitido ter apenas a entrada e a saída de uma função (por favor)!

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 , fazendo uma otimização ainda mais feia (que faz parte do ponto, e eu achei incrivelmente divertido):

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 Percebi que o comprimento da entrada é um limite superior e não preciso lidar com casos triviais separadamente agora.

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}

Casos de teste:

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

Versão expandida:

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;
}

Para cada caractere da entrada, calcule o comprimento do padrão se pintarmos essa cor primeiro. Isso é feito fingindo que pintamos essa cor e, em seguida, criando sub-seções com os bits que não são dessa cor e chamando recursivamente o método de pintura neles. O caminho mais curto é retornado.

Exemplo ( YRYGR):

Inicialmente, tente R. Isso nos dá os subgrupos Ye YG. Yé trivialmente pintado de uma só vez.

Para YG: Tente G, Yé trivial, comprimento 2. Tente Y, Gé trivial, o comprimento 2. YGé, portanto, o comprimento 2.

Pintar Rprimeiro, portanto, nos dá1 + 1 + 2 = 4

Então tente G. Isso nos dá os subgrupos YRYe R. Ré trivial.

Para YRY:

Tente Y: Ré trivial, comprimento 2. Tente R: Ye Ysão os dois grupos, comprimento 3.

YRYé comprimento 2.

Pintura Gprimeiro dá1 + 1 + 2 = 4

Então tente Y. Isso fornece os subgrupos Re GR. Rtrivial, GRé comprimento 2. Yé comprimento4

Essa implementação verificaria R e Y novamente para reduzir o comprimento do código. O resultado para YRYGRé, portanto 4.

Python, 149 caracteres

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]))

Eu uso ?para marcar uma área que pode ser de qualquer cor. Dseleciona uma região contígua do stick que contém apenas uma única cor (mais talvez alguns ?s), as cores dessa região por último, substitui a região por ?s e se repete para encontrar todas as etapas anteriores.

Tempo de execução exponencial. Mal é rápido o suficiente para fazer os exemplos em um tempo razoável (alguns minutos). Aposto que com memorização poderia ser muito mais rápido.

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(),''))

Parece funcionar, mas ainda não tenho 100% de certeza de que esse método sempre encontrará o número mínimo de etapas.

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 no JSFiddle.net

Versão não destruída, incluindo código de depuração e comentários:

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

Haskell, 143 caracteres

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]]}

Isso tenta todas as reescritas possíveis até o comprimento da string e vai até encontrar uma que construa o padrão de entrada. Escusado será dizer que o tempo exponencial (e depois alguns).

Uma primeira pesquisa de largura simples. Não coloca nada na fila que já foi vista. Ele funciona em menos de um segundo para todos os exemplos, mas 'pbgbrgrp', que na verdade leva um minuto inteiro :(

Agora que tenho algo que funciona, trabalharei para encontrar algo mais rápido e mais curto.

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)

Haskell, 118 86 caracteres

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

Execuções de teste:

λ: p "YRYGR"
4

λ: p "grG"
3

λ: p "GyRyGyG"
4

λ: p "pbgbrgrp"
5

λ: p "hyghgy"
4

λ: p "abcacba"
4

Este método nem é tão ineficiente!