iBug niedawno dostał długi pasek wykonany z kompozytowych, ale cennych materiałów. Pasek jest tak długi, że iBug nie może łatwo sprzedać go za kredyty, więc chce go zmniejszyć. Pręt jest wykonany z tak delikatnych i magicznych materiałów, że jeśli część zostanie złamana, wszystkie części pręta wykonane z tego samego materiału również pękną, co utrudni dowolne cięcie.

iBug chce pokroić pasek na jak najwięcej elementów. Uwielbia także bardzo krótkie programy i grę w golfa, więc dokonał abstrakcyjnej analizy swojego problemu.

Magiczny pasek iBuga jest reprezentowany jako ciąg (lub tablica lub sekwencja znaków, jeśli wolisz):

aaabbccccccbbbaaacccccaabbbaaaaa

Każda litera w ciągu reprezentuje jeden magiczny materiał. Pasek zawsze odpowiada RegEx ^\w*$, więc w pasku może znajdować się do 63 materiałów. „Część” to kolejna sekwencja dowolnych znaków, które nie są oddzielone spacjami.

iBug chce, abyś napisał program, który oblicza maksymalną liczbę części, jakie mógłby uzyskać, jeśli zero lub więcej zestawów znaków zostanie całkowicie usuniętych (zastąpionych spacjami), i powie iBug tę liczbę.

Przykład 1:

In:  aaabbccccccbbbaaacccccaabbbaaaaa
Out: 4

Opis: Jeśli bzostanie całkowicie usunięty z paska, iBug może uzyskać 4 części. Może również zdobyć 4 części, usuwając bi c, jak pokazano poniżej

aaabbccccccbbbaaacccccaabbbaaaaa  # Original string
aaa  cccccc   aaacccccaa   aaaaa  # Remove 'b'
aaa           aaa     aa   aaaaa  # Remove 'b' and 'c'

I to jest maksymalna liczba części, które iBug może uzyskać z tego paska

Przykład 2:

In:     111aa___9999____aaa99111__11_a_aa999
Result: 111aa   9999    aaa99111  11 a aa999
Out:    6

Opis: Usuwając tylko podkreślenie, iBug może uzyskać 6 części z paska i to jest maksimum.

Przykład 3:

In:  __________
Out: 1

Opis: Co? Chcesz to wyciąć? Można uzyskać tylko 1 część, jeśli w ogóle jej nie wycinasz.

Przykład 4:

In:  
Out: 0

Opis: Nie ma co wycinać, więc zero.

Istnieją również pewne zasady, które iBug chce, aby programy były przestrzegane:

1. iBug nie lubi standardowych luk i są one zabronione.

2. Tak długo, jak działa, nie musi być pełnym programem. Akceptowana jest również funkcja, która pobiera dane wejściowe z parametru i podaje dane wyjściowe za pomocą wartości zwracanej.

3. Dozwolone są elastyczne wejścia i wyjścia. Twój program lub funkcja może przyjmować ciąg znaków, tablicę znaków lub cokolwiek, co uważasz za najłatwiejsze w obsłudze. Możesz podać dane wyjściowe, drukując numer lub zwracając go.

Przykładowe przypadki testowe (ale nie tylko)

aaabbbaaa           = 2
123456789           = 5
AaAaAaAa            = 4
aaabcccdedaaabefda  = 6
________            = 1
(empty)             = 0

Ponieważ jest to golf golfowy , wygrywa najkrótszy program (w bajtach) w każdym języku!

Dodatkowy

iBug bardzo docenia, czy możesz wyjaśnić swój program, nawet jeśli nie wpływa to na twoją punktację (nadal ma długość w bajtach).

Haskell , 73 71 70 bajtów

x#z|z==x=' '|1<2=z
f x=maximum$length(words x):[f$(c#)<$>x|c<-x,c>' ']

^{Dzięki Laikoni za uratowanie 1 bajtu!}

Wypróbuj online!

JavaScript (ES6), 109 90 bajtów

f=s=>Math.max((s.match(/\s+/g)||[]).length,...[...s].map(c=>c>` `&&f(s.split(c).join` `)))

<input oninput=o.textContent=/\s/.test(this.value)?``:f(this.value)><pre id=o>0

Nieco powolny w 123456789przypadku testowym. Poprzednia 109-bajtowa odpowiedź nie była ograniczona do !/\s/:

f=
s=>(g=a=>Math.max(a.filter(s=>s).length,...[...a.join``].map(c=>g([].concat(...a.map(s=>s.split(c)))))))([s])

<input oninput=o.textContent=f(this.value)><pre id=o>0

Python 2 , 111 93 72 bajty

-21 bajtów dzięki Kirill L.

f=lambda s:max([len(s.split())]+[f(s.replace(c,' '))for c in s if'/'<c])

Wypróbuj online!

Galaretka ,  13  11 bajtów

^{Zbyt wiele 2-bajtowych instrukcji}
-2 dzięki Zgarb (użyj produktu zewnętrznego szybkoþ>. <)

eþŒPŒr¬S€ṀḢ

Monadyczny link akceptujący listę znaków i zwracający nieujemną liczbę całkowitą.

Wypróbuj online!

W jaki sposób?

Dla każdego podsekwencji danych wejściowych (zestawy, które możemy usunąć plus zbędne ekwiwalenty) pobiera listę istnienia, aby zidentyfikować, które są usuwane, a następnie skutecznie określa liczbę pozostałych zer i daje maksimum. Ostatnia część działa w nieco dziwny sposób, ponieważ uważam, że jest bardziej golfowa niż bardziej naiwne alternatywy - wyszukuje przebiegi jako [element, count]pary, neguje identyfikowanie zer jako jedności, sumy wyszukuje maksimum, a następnie bierze głowę (suma elementów zamiast liczb ).

eþŒPŒr¬S€ṀḢ - Link: list of characters        e.g. "aabcde"
  ŒP        - power-set - gets all subsequences    ["","a","a","b",...,"bd",...,"aabcde"]
 þ          - outer-product with:
e           -   exists in?                         [[0,0,0,0,0,0],[1,1,0,0,0,0],[1,1,0,0,0,0],[0,0,1,0,0,0],..,[0,0,1,0,1,0]...,[1,1,1,1,1,1]]
    Œr      - run-length encode                    [[[0,6]],[[1,2],[0,4]],[[1,2],[0,4]],[[0,2],[1,1],[0,3]],...,[[0,2],[1,1],[0,1],[1,1],[0,1]],...,[[1,6]]]
      ¬     - NOT                                  [[[1,0]],[[0,0],[1,0]],[[0,0],[1,0]],[[1,0],[0,0],[1,0]],...,[[1,0],[0,0],[1,0],[0,0],[1,0]],...,[[0,0]]]
        €   - for €ach:
       S    -   sum                                [[1,0],[1,0],[1,0],[2,0],...,[3,0],...,[0,0]]
         Ṁ  - maximum                              [3,0]
          Ḣ - head                                 3

Ruby , 98 89 75 64 61 bajtów

f=->s{[s.split.size,*s.scan(/\w/).map{|c|f[s.tr c,' ']}].max}

Wypróbuj online!

_{^{mniejszy i wolniejszy niż wcześniej!}}

Zasadniczo port odpowiedzi JavaScript na @ Neil

Nieoznaczony i opatrzony adnotacjami

def f(input_string)
    # splits by / +/ by default
    size0 = input_string.split.size
    # an array of all non-space characters in input_string
    characters = input_string.scan(/\w/)
    size1 = characters.map {|i|
        # all letters and digits and _ are "bigger" than /, space isn't
        if i > '/'
            # tr replaces every occurrence of i in input_string with space
            next_string = input_string.tr(i, ' ')
            f(next_string) # recursive call
        else
            0
        end
    }
    # max value between size0 and any element in size1
    return [size0, *size1].max
end

Wypróbuj online!

Łuska , 12 11 bajtów

▲mȯ#€0gM€¹Ṗ

Wypróbuj online! Działa to brutalną siłą i jest dość wolne. Dodaj udo prawego końca, aby działał szybciej, bez zmiany semantyki.

Wyjaśnienie

▲mȯ#€0gM€¹Ṗ  Implicit input, say S = "abddccbdcaab"
          Ṗ  Powerset of S: P = ["","a","b","ab","d","ad"...,"abddccbdcaab"]
 m           Map this function over P:
              Argument is a subsequence, say R = "acc"
       M ¹    Map over S
        €     index of first occurrence in R: [1,0,0,0,2,2,0,0,2,1,1,0]
      g       Group equal elements: [[1],[0,0,0],[2,2],[0,0],[2],[1,1],[0]]
  ȯ#          Count the number of groups
    €0        that contain 0: 3
▲            Take maximum of the results: 4

Perl 5 , (starsze wersje) -p -I., 52 49 43 bajtów

Liczenie w starym stylu: +3dla -p: 46bajtów (ponieważ musi być w programie, nie można go uruchomić przy użyciu -e)

barsplit.pl:

#!/usr/bin/perl -pI.
$G[split]+=s%\S%do$0for s/$&/ /rg%eg;$_=$#G

Uruchom z ciągiem na STDIN:

echo aaabcccdedaaabefda | ./barsplit.pl; echo

Wypróbuj online!

-I.Opcja jest tam do tej pracy także na ostatnich perls gdzie domyślnie .nie jest bardziej w @INC. W starszych wersjach perla ta opcja nie jest potrzebna. Przetestowałem to na starszym komputerze, który wciąż miał perl 5.20, więc wynik jest oparty na tym (w przeciwnym razie należy również liczyć się .argument -I)

Wersja szybka ( 49bajty):

#!/usr/bin/perl -pI.
$G[split]+=s%.%$$_++||do$0for s/$&/ /rg%eg;$_=$#G

Wolfram Language (Mathematica) , 77 bajtów

Max@Table[Tr[1^StringSplit[#,(##|##)..&@@s]],{s,Subsets@Union@Characters@#}]&

Wypróbuj online!