Napisz funkcję lub program, który określa koszt danego ciągu, gdzie

• koszt każdego znaku jest równy liczbie przypadków, w których znak wystąpił do tego momentu w ciągu, oraz
• koszt ciągu jest sumą kosztów jego znaków.

Przykład

abaacabKoszt wejściowy obliczany jest w następujący sposób:

a b a a c a b
1   2 3   4    occurrence of a
  1         2  occurrence of b
        1      occurrence of c
1+1+2+3+1+4+2 = 14

Zatem koszt ciągu abaacabwynosi 14.

Zasady

• Wynik przesłania jest kosztem kodu zdefiniowanego powyżej , to znaczy, że przesyłanie odbywa się na własnym kodzie źródłowym, przy czym niższy wynik jest lepszy.
• Twoje zgłoszenie powinno działać na ciągach zawierających drukowalne znaki ASCII oraz wszystkie znaki użyte w przesłaniu.
• W znakach rozróżniana jest wielkość liter, tzn. aI Asą to różne znaki.

Przypadki testowe

input -> output
"abaacab" -> 14
"Programming Puzzles & Code Golf" -> 47
"" -> 0
"       " -> 28
"abcdefg" -> 7
"aA" -> 2

Tabela liderów

var QUESTION_ID=127261,OVERRIDE_USER=56433;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px} /* font fix */ body {font-family: Arial,"Helvetica Neue",Helvetica,sans-serif;} /* #language-list x-pos fix */ #answer-list {margin-right: 200px;}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Score</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

MATL , wynik 4

&=Rz

Wypróbuj online!

Wyjaśnienie

Rozważ dane wejściowe 'ABBA'jako przykład.

&=   % Implicit input. Matrix of all equality comparisons
     % STACK: [1 0 0 1;
               0 1 1 0;
               0 1 1 0;
               1 0 0 1]
R    % Upper triangular part
     % STACK: [1 0 0 1;
               0 1 1 0;
               0 0 1 0;
               0 0 0 1]
z    % Number of nonzeros. Implicitly display
     % STACK: 6

Python , wynik 49

lambda S:sum(1+S.count(C)for[C]in	S)/2

Wypróbuj online!

Po tym jest zakładka in.

Podział punktacji:

• +27 za 27 unikalnych znaków
• +16 za 8 podwójnych znaków: ()Camnou
• +6 za 1 potrójny znak: S

T-SQL, wynik 775 579! 580

declaRe @ char(876),@x int,@v int=0Select @=q+CHAR(9)from z X:seleCT @x=len(@),@=REPLACE(@,LEFT(@,1),''),@v+=(@x-LEN(@))*(@x-LEN(@)+1)/2IF LEN(@)>0GOTO X prINT @v-1

EDYCJA : Upuściłem kilka zmiennych, trochę zagęściłem. Zejście do 16 @symboli zamiast 22, co samo w sobie zmniejsza mój wynik aż o 117 punktów!

Fajny konkurs, podoba mi się wymaganie optymalizacji czegoś oprócz całkowitej liczby postaci.

Dane wejściowe są poprzez pole varchar q w istniejącej tabeli z , zgodnie z naszymi regułami IO . W bazie danych zawierającej tę tabelę wejściową należy ustawić sortowanie z rozróżnianiem wielkości liter .

Sformatowany:

declaRe @ char(876), @x int, @v int=0
Select @=q+CHAR(9)from z
X:
    seleCT @x=len(@)
          ,@=REPLACE(@,LEFT(@,1),'')
          ,@v+=(@x-LEN(@))*(@x-LEN(@)+1)/2
IF LEN(@)>0 GOTO X
prINT @v-1

W słowach kluczowych SQL nie jest rozróżniana wielkość liter, więc użyłem mieszanych liter, aby zminimalizować liczbę zduplikowanych liter ( aaAA generuje lepszy / niższy wynik niż aaaa ).

Główna pętla porównuje długość przed i po usunięciu wszystkich wystąpień pierwszego znaku. Ta różnica n * (n + 1) / 2 jest dodawana do sumy bieżącej.

Irytująca LEN()funkcja SQL ignoruje końcowe spacje, więc musiałem dodać znak kontrolny i odjąć 1 na końcu.

EDYCJA : Naprawiono błędne obliczenie mojego własnego wyniku o 2 punkty (problem z cytowaniem cudzysłowów), zmniejszone o 1 przez zmianę obudowy o jeden R. Pracując również nad zupełnie inną strategią, opublikuję to jako własną odpowiedź.

C (gcc) , wynik:  113  103 100   96  91

Dzięki @ugoren, @CalculatorFeline, @gastropner, @ l4m2 i @ JS1 za wskazówki.

g(char*s){int y[238]={};while(*s)*y-=--y[*s++];*y/=1;}

Inicjuje tablicę zer, a następnie wykorzystuje wartości ASCII znaków w ciągu jako indeksy dla tej tablicy, aby śledzić liczbę wystąpień każdego znaku w ciągu.

Wypróbuj online!

JavaScript (ES6), wynik 81 78

Zaoszczędź 3 punkty dzięki @Arnauld

s=>s.replace(d=/./g,z=>q+=d[z]=-~d[z],q=0)&&q

Moje oryginalne rozwiązanie rekurencyjne score-81:

f=([c,...s],d={})=>c?(d[c]=-~d[c])+f(s,d):0

Haskell , wynik 42

f l=sum[1|c<-l,d<-c:l,d==c]/2

Wypróbuj online!

Anonimizacja \l->daje ten sam wynik.

Galaretka , ocena 6

;\ċ"⁸S

Wypróbuj online!

Siatkówka , ocena 34

s(O`.
M&!`^|(?<=(.))\1*
.

Wypróbuj online!

Wyjaśnienie

s(O`.

Zaczynamy od sortowania wszystkich znaków na wejściu, aby identyczne znaki były zgrupowane w jednym przebiegu. s(Aktywuje tryb SingleLine na wszystkich etapach (tj sprawia .karetki meczu).

M&!s`^|(?<=(.))\1*

Celem jest przekształcenie ciągu n znaków w T _n znaków ( n- ta liczba trójkątna), ponieważ jest to wynik występowania tej postaci. Aby to zrobić, znajdujemy nakładające się mecze. W szczególności dla każdego i w [1, n] dołączymy do meczu znaki i-1 . Wszystkie te mecze otrzymujemy z powodu nakładającej się flagi &. To daje nam n * (n-1) / 2 = T _n-1 = T _n - n znaków tylko z dopasowań. Ale etap dopasowania połączy je z liniami, które są n liniami dla nmecze. Jest tylko jeden problem. Po ostatnim dopasowaniu nie będzie podawania linii, więc ogólna liczba znaków na wyjściu jest o jeden mniejsza niż potrzebujemy. Naprawiamy to, dopasowując również początek danych wejściowych, co daje nam jeden wiodący kanał, jeśli istnieje co najmniej jedno dopasowanie.

.

Wreszcie, po prostu liczymy, ile znaków jest w ciągu.

Haskell, wynik 52 51

f(a:b)=1+sum[1|c<-b,c==a]+f b;f _=0

Istnieje zakładka pomiędzy fi _.

Wypróbuj online!

Wartość pustego ciągu wynosi 0. Wartość ciągu s, gdzie ajest pierwszym znakiem, a breszta ciągu to 1 plus wystąpienia ain bplus wywołanie rekurencyjne z b.

J , wynik 16

1#.,@(*+/\"1)&=

Wypróbuj online!

Wyjaśnienie

1#.,@(*+/\"1)&=
              =  Self-classify: bit matrix of equality between input
                 and its unique elements.
     (      )&   Apply verb in parentheses to it:
       +/\         running sums
          "1       of each row
      *            multiplied with original matrix.
                 This causes the i'th 1 on each row to be replaced by i.
   ,@            Flatten the resulting matrix
1#.              and interpret as a base-1 number, computing its sum.

Użycie 1#.zamiast +/@sumy pozwoliło zaoszczędzić kilka punktów i &może być użyte zamiast @w kontekście monadycznym, aby zaoszczędzić jeszcze jeden. Powtarzanie 1kosztuje mnie jeden dodatkowy punkt, ale nie byłem w stanie się go pozbyć.

R , wynik: 67 83 95 128

-61 dzięki najlepszym wskazówkom Giuseppe

function(x,y=table(utf8ToInt(x)))y%*%{y+1}/2

Wypróbuj online!

Ciąg jest dzielony za pomocą utf8ToInti każda wartość ascii jest liczona table. Wynik jest obliczany przy użyciu mnożenia macierzy %*%ponad to samo w sobie + 1 i ostatecznie o połowę.

05AB1E , wynik 6

{γ€gLO

Wypróbuj online!

Pyth , ocena 6

1 bajt dzięki isaacg.

+F/V._

Zestaw testowy.

Jak to działa

+F/V._
+F/V._QQ  implicit input
  /V      vectorize count: for each element in the first argument,
                           count the number of occurrences of the
                           second argument:
    ._Q       all prefixes of input
       Q      input
+F        fold (reduce) on +, base case 0.

J , wynik: 14 12 11

$+/@,2!1#.=

Wypróbuj online!

Galaretka , wynik 7

ċЀQRFS

Wyjaśnienie:

   Q    get unique letters
ċЀ     count the occurences of each letter in the original string
    R   [1..n] for n in list of frequencies
     F  flatten list
      S sum
        (implicit output)

Wypróbuj online!

C, 60 bajtów, wynik 108 95

g(char*s){int y[256]={},z=0;while(*s)z-=--y[*s++];return z;}

Wypróbuj online!

Zwykle operatorzy przed i po inkrementacji są świetni do gry w golfa kodowego, ale naprawdę bolą w tym wyzwaniu!

EDYCJA: Odejmując liczby ujemne zamiast dodatnich, zapisałem całą masę wyników. Wymiana for()z while()wyeliminowane średnik jako dobrze.

Perl 6 , wynik  61 56 53 46  44

(1 X..*.comb.Bag.values).flat.sum

Spróbuj

{sum flat 1 X.. .comb.Bag.values}

Spróbuj

{sum flat 1 X.. values(.comb.Bag)}

Spróbuj

{[+] flat	1	X.. values(.comb.Bag)}

Spróbuj

{[+] flat	1	X.. values(bag
.comb)}

Spróbuj

C # (.NET Core) , wynik ∞ (mam na myśli, 209)

b=>b.Distinct().Select(z=>{var w=b.Count(p=>p==z);return w*(w+1)/2;}).Sum()

Wypróbuj online!

Wynik obejmuje:

using System.Linq;

Galaretka , ocena 5

ĠJ€ẎS

Wypróbuj online!

Dzięki Leaky Nun za -2 (poprzednio w odpowiedzi )

PowerShell, wynik 64

$z=@{}
$ARGS|% getE*|%{$u+=($Z.$_+=1)};$U

(Wynik oparty jest na nowej linii nowego wiersza, która nie jest standardem Windows, ale działa w PS).

PS C:\> D:\unique-is-cheap.ps1 (gc D:\unique-is-cheap.ps1 -raw)
64

• Licznik haszowany @{}
• Iteruj po literach; $argsjest tablicą parametrów - w tym przypadku łańcuch wejściowy czyni go tablicą pojedynczego elementu; |%wykonuje pętlę foreach nad elementami i używa getE*skrótu, aby dopasować GetEnumerator()metodę ciągu i wywołać ją, aby przekształcić ciąg w strumień znaków.
• |%zapętlaj znaki i zwiększaj ich hashtable, dodaj go do bieżącej sumy. ($x+=1)Forma z parens zarówno modyfikuje zmienną i wysyła nową wartość do użycia.
• Podaj sumę bieżącą.

(Kiedy napisałem to po raz pierwszy, było to $c=@{};$t=0;[char[]]"$args"|%{$c[$_]++;$t+=$c[$_]};$tz wynikiem 128 i czułem, że nie obniżyłby się znacznie. Zmniejszenie do 64 jest całkiem przyjemne).

Julia 0,6 , 45 bajtów, wynik: 77

Zainspirowany rozwiązaniem MATL:

f(w)=sum(UpperTriangular([z==j for z=w,j=w]))

Wypróbuj online!

Mniej ładne rozwiązanie, używając liczby:

Julia 0.6 , wynik: 82

F(w)=sum(l->[l+1]l/2,count(x->x==i,w)for i=Set(w))

Wypróbuj online!

Dzięki Guiseppe za wskazanie punktacji i wskazówki. Te komentarze pomogły mi ładować.

Java 10, wynik: 149 138 137 134 133 130 103 102 101 100

( Bajty: 72 73 74 75 64 62 61 ) Bajty rosną, ale wynik spada. :RE

x->{int j=0,q[]=new int[256];for(var    C:x)j+=++q[C];return
j;}

Wynik -28 (i -11 bajtów) dzięki @Nevay .
-1 wynik (i -2 bajty) dzięki @ OlivierGrégoire .
Wynik -1 (i -1 bajt) poprzez konwersję Java 8 na Java 10.

Wyjaśnienie:

Wypróbuj tutaj.

x->{                     // Method with character-array parameter and integer return-type
  int j=0,               //  Result-integer, starting at 0
      q[]=new int[256];  //  Integer-array with 256 times 0
  for(var   C:x)         //  Loop over the characters of the input array
    j+=++q[C];           //   Raise the value in the array by 1,
                         //   and then add it to the result-integer
  return                 //  Return 
  j;}                    //         the result

F #, wynik 120 118

let j z=Seq.countBy id z|>Seq.sumBy(fun x->List.sum[0..snd x])

-2 dzięki Kevin Cruijssen !

Wypróbuj online!

Pobiera stringjako dane wejściowe. Seq.countByparuje każdy odrębny znak z jego liczbą ( idjest funkcją tożsamości), dzięki czemu otrzymujesz kolekcję podobną do 'a' = 4, 'b' = 2itp.

Seq.sumByTrwa odliczanie do każdego listu i sumuje wszystkie numery od 0do zliczania dla danej litery. Więc jeśli 'a' = 4kolekcja byłaby 0, 1, 2, 3, 4sumą, która jest razem 10. Następnie Seq.sumBysumuje wszystkie te sumy.

APL (Dyalog) , wynik 15

+/1 1⍉+\∘.=⍨⍞

Wypróbuj online!

⍞ uzyskać wprowadzanie tekstu

∘.=⍨ tabela równości z jaźnią

+\ skumulowana suma w poprzek

1 1⍉ przekątna (dosł. zwiń oba wymiary do wymiaru pierwszego)

+/ suma

Siatkówka , wynik 68 45 43

s`(.)(?<=((\1)|.)+)
$#3$*
1

Wypróbuj online! Link pokazuje wynik. Edycja: Dzięki @MartinEnder, który zaoszczędził 20 bajtów, używając nakładających się dopasowań zamiast oczekujących, i kolejne trzy bajty, grupując etapy, tak aby sflaga mogła być zastosowana tylko raz. Zaoszczędzono kolejne dwa bajty, obliczając liczbę trójkątną inaczej, unikając potrzeby sortowania.

PHP , 45 bajtów, wynik 78

WHILE($x=ORD($argn[$v++]))$y+=$$x-=-1;echo$y;

Wypróbuj online!

PHP , 46 bajtów, Wynik 79 bajtów

WHILE(~$xy=$argn[$vz++])$su-=-$$xy+=1;echo$su;

Wypróbuj online!

PHP , 56 bajtów, wynik 92

FOREAch(COUNT_CHARS($argn)as$z)WHILE($z)$y+=$z--;echo$y;

Wypróbuj online!

Wynik Perla 5 91 83

Używa -pflagi, która dodaje 2 z powodu pw podziale.

$x=$_;$b+=++$a{$_}for(split//,$x);$_=$b

Oktawa , 39 bajtów, wynik 69

@(a)sum((b=hist(a,unique(1*a))).^2+b)/2

Wypróbuj online!

Chociaż istnieje inna odpowiedź Octave, ta jest całkowicie moja i ma inne podejście, a ponadto ma mniej punktów :).

Podejście sprowadza się do pierwszego znalezienia liczby (b) każdego unikalnego znaku, którą uzyskuje się za pomocą funkcji histogramu. Następnie dla każdego elementu obliczamy sumę 1 do b, która odbywa się za pomocą wzoru (b*(b+1))/2. Następnie poszczególne sumy są sumowane do końcowego wyniku.

W testach wydaje się, że nawiasy są bardzo kosztowne w ocenie, ponieważ wiele jest potrzebnych. Zoptymalizowałem od początkowego wyniku wynoszącego około 88, zmieniając układ pytań, aby zminimalizować liczbę nawiasów otwierających / zamykających - dlatego teraz wykonujemy / 2 na końcowej sumie, a nie indywidualnie, a także zmodyfikowałem formułę, aby (b^2+b)/2ponieważ wymaga to mniejszej liczby nawiasów.

Common Lisp, wynik 286 232 222

(loop with w =(fill(make-list 128)0)as z across(read)sum(incf(elt w(char-code z))))

Wysoko ceniony wynik ze względu na mylną składnię wbudowanych operatorów Common Lisp.

Wypróbuj online!

Nieskluczony kod:

(loop with w = (fill (make-list 128) 0)  ; create a list to count characters
   as z across (read)                   ; for each character of input
   sum (incf (elt w (char-code z))))     ; increase count in list and sum

Mathematica, ocena 54

Total[#(#+1)/2&@Counts@Characters@#]&

Wejście

[„abcdefg”]

dzięki hftf