Сколько времени нужно, чтобы нарисовать палку?

(На основе этой проблемы Math.SE , которая также предоставляет некоторую графику)

У меня есть палка, которая выглядит примерно так:

Я хочу, чтобы это выглядело примерно так:

Однако я не опытный художник, поэтому, прежде чем я начну такой амбициозный проект «Сделай сам», я хочу убедиться, что я не над головой.

Ваша программа должна сказать мне, сколько этапов задействовано в рисовании этой флешки. Каждый шаг включает в себя рисование сплошной области сплошным цветом, который покрывает предыдущие слои краски. Для приведенного выше примера я мог бы нарисовать левую половину синим, правую половину красным, а затем две отдельные зеленые области в общей сложности на 4 шага (зеленый не непрерывно окрашивается).

Вот это в ASCII:

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

Есть пара разных способов покрасить эту палку и в итоге получить тот же результат. Однако меня интересует только оценка времени, которая составляет четыре шага.

Цель

Ваша программа должна вывести минимальное количество шагов, необходимых для рисования флешки с заданной цветовой схемой. Схема рисования будет иметь вид строки символов, а на выходе будет число. Это код гольф. Кратчайшая программа выигрывает.

вход

Ваша программа получит схему раскраски палки в виде цепочки букв. Каждая уникальная буква (с учетом регистра) представляет уникальный цвет.

YRYGR

grG

GyRyGyG

pbgbrgrp

hyghgy

Выход

Эти цифры являются наименьшим количеством шагов, необходимых для рисования палочек.

4

3

4

5

4

Пояснения

Вот так я и пришел к вышеприведенным цифрам. Ваша программа не должна выводить это:

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

 ---
 g--
 gr-
 grG

 -------
 GGGGGGG
 GyyyGGG
 GyRyGGG
 GyRyGyG

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

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

Изменить: я добавлю больше тестов, если они окажутся более сложными.

GolfScript, 82 72 67 символов

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

Разумно быстро для программы GolfScript, примеры:

> hyghgy
4

> pbgbrgrp
5

Используемый алгоритм рекурсивно обрабатывает цвета слева направо в соответствии со следующими утверждениями:

• Игнорируйте все части слева, которые уже имеют требуемый цвет. Перекрасить их снова не даст лучшего ответа.
• Если полный стик уже имеет желаемый цвет, верните 0 шагов в качестве результата.

• В противном случае возьмите целевой цвет самой левой части (т. Е. Первую, не нужного цвета).

  • Нарисуйте 1 часть с целевым цветом и восстановите.
  • Нарисуйте 2 части этим цветом и восстановите.

  ...

  • Покрасьте всю оставшуюся палку этим цветом и восстановите.

  Возьмите минимум всех этих чисел и добавьте 1 (для текущего шага). Верните это как оптимальное количество шагов.

Этот алгоритм работает, потому что крайняя левая часть в любом случае должна быть нарисована одновременно, так почему бы не сделать это немедленно - любым возможным способом.

.,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 байт

Предполагая, что нам разрешено иметь только вход и выход для функции (пожалуйста)!

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 байт , выполняя дальнейшую уродливую оптимизацию (что является частью вопроса, и я нашел невероятно забавным):

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 байт. Я понял, что длина входных данных является верхней границей, и теперь мне не нужно обрабатывать тривиальные случаи отдельно.

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}

Тестовые случаи:

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

Расширенная версия:

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

Для каждого символа ввода вычислите длину шаблона, если мы сначала закрасим этот цвет. Это делается, притворяясь, что мы рисуем этот цвет, а затем делая подразделы из битов, которые не того цвета, и рекурсивно вызывая метод рисования для них. Кратчайший путь возвращается.

Пример ( YRYGR):

Изначально попробуйте R. Это дает нам подгруппы Yи YG. Yтривиально нарисован за один раз.

Для YG: попробуй G, Yбанально, длина 2. Попробуйте Y, Gтривиально, длина 2. YGследовательно, длина 2.

Картина Rпервая поэтому дает нам1 + 1 + 2 = 4

Тогда попробуй G. Это дает нам подгруппы YRYи R. Rтривиально

Для YRY:

Попробуйте Y: Rтривиально, длина 2. Попробуйте R: Yи Yдве группы, длина 3.

YRYэто длина 2.

Картина Gсначала дает1 + 1 + 2 = 4

Тогда попробуй Y. Это дает подгруппы Rи GR. Rтривиально, GRэто длина 2. Yдлина4

Эта реализация будет затем проверять R и Y снова, чтобы уменьшить длину кода. Результат для YRYGRпоэтому 4.

Питон, 149 символов

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

Я использую, ?чтобы отметить область, которая может быть любого цвета. Dвыбирает непрерывную область флешки, которая содержит только один цвет (плюс, может быть, несколько ?s), цвета, которые последняя в этой области, заменяет эту область на ?s и рекурсивно находит все предыдущие шаги.

Экспоненциальное время работы. Просто достаточно быстро, чтобы сделать примеры за разумное время (несколько минут). Бьюсь об заклад, с запоминанием это может быть намного быстрее.

Питон 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(),''))

Кажется, это работает, но я все еще не уверен на 100%, что этот метод всегда найдет минимальное количество шагов.

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

Демо на JSFiddle.net

Ungolfed версия, включая отладочный код и комментарии:

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 символа

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

Это пробует все возможные перезаписи вплоть до длины строки и продолжается до тех пор, пока не найдет тот, который создает шаблон ввода. Излишне говорить, экспоненциальное время (а затем и некоторые).

Простой поиск в ширину. Это не помещает ничего в очередь, которая уже была замечена. Он работает менее чем за секунду для всех примеров, но 'pbgbrgrp', что на самом деле занимает целую минуту :(

Теперь, когда у меня есть что-то, что работает, я буду искать что-то быстрее и короче.

Питон - 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)

Хаскелл, 118 86 персонажей

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

Тестовые прогоны:

λ: p "YRYGR"
4

λ: p "grG"
3

λ: p "GyRyGyG"
4

λ: p "pbgbrgrp"
5

λ: p "hyghgy"
4

λ: p "abcacba"
4

Этот метод даже не настолько неэффективен!