Jak długo trwa namalowanie patyka?

(Na podstawie tego problemu Math.SE , który zapewnia również grafikę)

Mam patyk, który wygląda trochę tak:

Chcę, żeby wyglądało to tak:

Nie jestem jednak specjalistą od malowania, więc zanim rozpocznę tak ambitny projekt DIY, chcę się upewnić, że nie będę się nad tym zastanawiać.

Twój program powinien mi powiedzieć, ile kroków wymaga malowanie tego kija. Każdy krok polega na pomalowaniu ciągłego obszaru jednolitym kolorem, który zakrywa poprzednie warstwy farby. W powyższym przykładzie mogłem pomalować lewą połowę koloru niebieskiego, prawą połówkę koloru czerwonego, a następnie dwa osobne zielone obszary w sumie 4 kroki (kolor zielony nie jest stale malowany).

Oto w ASCII:

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

Istnieje kilka różnych sposobów na pomalowanie tego kija i uzyskanie tego samego rezultatu. Interesuje mnie jednak tylko szacunkowy czas, który składa się z czterech kroków.

Cel

Twój program powinien wypisać minimalną liczbę kroków potrzebnych do namalowania kija o danym schemacie kolorów. Schemat malowania będzie miał postać ciągu znaków, a wynikiem będzie liczba. To jest kod golfowy. Najkrótszy program wygrywa.

Wejście

Twój program otrzyma schemat kolorowania kija w postaci ciągu liter. Każda unikalna litera (wielkość liter ma znaczenie) reprezentuje unikalny kolor.

YRYGR

grG

GyRyGyG

pbgbrgrp

hyghgy

Wynik

Te liczby to najmniejsza liczba kroków potrzebnych do pomalowania patyczków.

4

3

4

5

4

Objaśnienia

Tak doszedłem do powyższych liczb. Twój program nie musi generować tego:

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

 ---
 g--
 gr-
 grG

 -------
 GGGGGGG
 GyyyGGG
 GyRyGGG
 GyRyGyG

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

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

Edycja: Dodam więcej przypadków testowych, jeśli okażą się trudniejsze.

GolfScript, 82 72 67 znaków

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

Dość szybko jak na program GolfScript, przykłady:

> hyghgy
4

> pbgbrgrp
5

Zastosowany algorytm działa rekurencyjnie w kolorach od lewej do prawej, zgodnie z następującymi instrukcjami:

• Zignoruj ​​wszystkie części od lewej, które mają już wymagany kolor. Ponowne pomalowanie ich nie zapewni lepszej odpowiedzi.
• Jeśli cały kij ma już żądany kolor, zwróć 0 kroków w wyniku.

• W przeciwnym razie wybierz kolor docelowy najbardziej wysuniętej w lewo części (tj. Pierwszej nie w pożądanym kolorze).

  • Pomaluj 1 część kolorem docelowym i powtórz.
  • Pomaluj 2 części tym kolorem i powtórz.

  ...

  • Pomaluj cały pozostały kij tym kolorem i powtórz.

  Weź minimum wszystkich tych liczb i dodaj 1 (dla bieżącego kroku). Zwróć to jako optymalną liczbę kroków.

Ten algorytm działa, ponieważ i tak najbardziej lewa część musi być pomalowana jednocześnie, więc dlaczego nie zrobić tego natychmiast - w jakikolwiek możliwy sposób.

.,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 bajtów

Zakładając, że możemy mieć tylko wejście i wyjście do funkcji (proszę)!

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 bajtów , wykonując dalszą brzydką optymalizację (co jest częścią tego, i znalazłem niesamowitą zabawę):

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 Bajtów Zdałem sobie sprawę, że długość danych wejściowych jest górną granicą i nie muszę teraz osobno obsługiwać trywialnych przypadków.

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}

Przypadki testowe:

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

Wersja rozszerzona:

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

Dla każdego znaku wejściowego oblicz długość wzoru, jeśli najpierw pomalujemy ten kolor. Odbywa się to przez udawanie, że malujemy ten kolor, a następnie tworzenie podsekcji z bitów, które nie są w tym kolorze, i rekurencyjne wywoływanie na nich metody malowania. Zwracana jest najkrótsza ścieżka.

Przykład ( YRYGR):

Początkowo spróbuj R. To daje nam podgrupy Yi YG. Yjest trywialnie pomalowany za jednym razem.

Dla YG: Spróbuj G, Yjest banalna, długość 2. Spróbuj Y, Gjest trywialne, długość 2. YGjest zatem długością 2.

Malowanie jako Rpierwsze daje nam zatem1 + 1 + 2 = 4

Więc spróbuj G. To daje nam podgrupy YRYi R. Rjest banalny.

Dla YRY:

Spróbuj Y: Rjest banalna, długość 2. Spróbuj R: Yi Ysą dwie grupy, długość 3.

YRYjest długością 2.

Malarstwo Gnajpierw daje1 + 1 + 2 = 4

Więc spróbuj Y. To daje podgrupom Ri GR. Rbanalna, GRto długość 2. Yjest długością4

Ta implementacja sprawdzi następnie R i Y ponownie, aby zmniejszyć długość kodu. Wynik YRYGRjest zatem 4.

Python, 149 znaków

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

Używam ?do zaznaczania obszaru, który może być dowolnego koloru. Dwybiera ciągły obszar sztyftu, który zawiera tylko jeden kolor (plus może trochę ?s), kolory tego regionu trwają, zastępuje ten obszar ?s, i powraca, aby znaleźć wszystkie poprzednie kroki.

Wykładniczy czas działania. Tylko ledwo wystarczająco szybko, aby wykonać przykłady w rozsądnym czasie (kilka minut). Założę się, że z zapamiętywaniem może być znacznie szybciej.

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

Wydaje się, że działa, ale wciąż nie jestem w 100% pewien, że ta metoda zawsze znajdzie minimalną liczbę kroków.

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

Wersja bez golfa, w tym kod debugowania i komentarze:

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 znaki

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

Spróbuje wszystkich możliwych przepisań do długości łańcucha i przechodzi do znalezienia takiego, który konstruuje wzorzec wejściowy. Nie trzeba dodawać, że wykładniczy czas (a potem trochę).

Proste pierwsze wyszukiwanie. Nie umieszcza niczego w kolejce, która już była widoczna. Działa w niecałą sekundę dla wszystkich przykładów, ale „pbgbrgrp”, co w rzeczywistości zajmuje pełną minutę :(

Teraz, gdy mam coś, co działa , będę pracować nad znalezieniem czegoś szybszego i krótszego.

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 znaków

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

Przebiegi testowe:

λ: p "YRYGR"
4

λ: p "grG"
3

λ: p "GyRyGyG"
4

λ: p "pbgbrgrp"
5

λ: p "hyghgy"
4

λ: p "abcacba"
4

Ta metoda nie jest wcale taka nieefektywna!