Ecrivez une fonction ou un programme qui détermine le coût d’une chaîne donnée, où

• le coût de chaque caractère est égal au nombre de fois où le caractère s'est produit jusqu'à ce point dans la chaîne, et
• le coût de la chaîne est la somme des coûts de ses personnages.

Exemple

Pour une entrée de abaacab, le coût est calculé comme suit:

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

Ainsi, le coût de la chaîne abaacabest de 14.

Règles

• Le score de votre soumission correspond au coût de votre code tel que défini ci - dessus , c'est-à-dire que votre soumission s'exécute sur son propre code source, un score inférieur étant meilleur.
• Votre soumission doit fonctionner sur des chaînes contenant des caractères ASCII imprimables, ainsi que sur tous les caractères utilisés dans votre soumission.
• Les caractères sont sensibles à la casse, c'est-à-dire aet Asont des caractères différents.

Testcases

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

Classement

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 , score 4

&=Rz

Essayez-le en ligne!

Explication

Considérez l'entrée 'ABBA'comme un exemple.

&=   % 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 , score 49

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

Essayez-le en ligne!

Il y a un onglet après in.

Score score:

• +27 pour 27 caractères uniques
• +16 pour 8 caractères doubles: ()Camnou
• +6 pour 1 caractère triplé: S

T-SQL, score 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

EDIT : laissé tomber quelques variables, compacté un peu. Avec 16 @symboles au lieu de 22, cela réduit mon score de 117 points!

Joli concours, j'aime l'exigence d'optimiser autre chose que le nombre total de caractères.

La saisie s'effectue via le champ varchar q de la table z préexistante , conformément à nos règles IO . La base de données contenant cette table d'entrée doit être définie sur un classement sensible à la casse .

Formaté:

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

Les mots-clés SQL ne sont pas sensibles à la casse. J'ai donc utilisé une casse mixte pour minimiser le nombre de lettres en double ( aaAA génère un score meilleur / inférieur à aaaa ).

La boucle principale compare la longueur avant et après suppression de toutes les occurrences du premier caractère. Cette différence n * (n + 1) / 2 est ajoutée à un total cumulé.

La LEN()fonction SQL ignore ennuyeusement les espaces de fin. Je devais donc ajouter un caractère de contrôle et soustraire 1 à la fin.

EDIT : Correction d'un calcul erroné de mon propre score de 2 points (problème de guillemets), réduit de 1 en changeant la casse d'un R. Travaillant également sur une stratégie complètement différente, je la publierai comme sa propre réponse.

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

Merci à @ugoren, @CalculatorFeline, @gastropner, @ l4m2 et @ JS1 pour leurs conseils.

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

Initialise un tableau de zéros, puis utilise les valeurs ASCII des caractères de la chaîne en tant qu'indices de ce tableau pour suivre le nombre d'instances de chaque caractère de la chaîne.

Essayez-le en ligne!

JavaScript (ES6), score 81 78

A gagné 3 points grâce à @Arnauld

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

Ma solution récursive originale score-81:

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

Haskell , score de 42

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

Essayez-le en ligne!

Anonymiser \l->donne le même score.

Gelée , score 6

;\ċ"⁸S

Essayez-le en ligne!

Rétine , score 34

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

Essayez-le en ligne!

Explication

s(O`.

Nous commençons par trier tous les caractères de l’entrée afin que les caractères identiques soient regroupés en un seul passage. Le s(active le mode ligne unique pour toutes les étapes (c.-à-d .. Fait correspondre les sauts de ligne).

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

L'objectif est de transformer une série de n caractères en T _n caractères (la n ième nombre triangulaire) parce que c'est le score des occurrences de ce caractère. Pour ce faire, nous trouvons des correspondances qui se chevauchent. En particulier, pour chaque i dans [1, n] , nous allons inclure les caractères i-1 dans la correspondance. Nous obtenons tous ces matches en raison du drapeau qui se chevauchent &. Cela nous donne n * (n-1) / 2 = T _n-1 = T _n - n caractères seulement des correspondances. Mais l’étape du match les rejoindra avec des sauts de ligne, qui sont n flux de ligne pour nallumettes. Il n'y a qu'un seul problème. Il n'y aura pas de saut de ligne après la dernière correspondance. Le nombre total de caractères dans la sortie est donc inférieur à celui dont nous avons besoin. Nous corrigeons cela en faisant également correspondre le début de l'entrée, ce qui nous donne un seul saut de ligne s'il y a au moins une autre correspondance.

.

Enfin, nous comptons simplement le nombre de caractères dans la chaîne.

Haskell, score 52 52 51

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

Il y a un onglet entre fet _.

Essayez-le en ligne!

La valeur de la chaîne vide est 0. La valeur de la chaîne s, où aest le premier caractère et ble reste de la chaîne est 1 plus les occurrences de ain bplus un appel récursif avec b.

J , note 16

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

Essayez-le en ligne!

Explication

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.

Utiliser 1#.au lieu de +/@pour la somme économise quelques points et &pourrait être utilisé au lieu de @dans un contexte monadique pour enregistrer un autre. La répétition 1me coûte un point de plus, mais je n'ai pas réussi à m'en débarrasser.

R , score: 67 83 95 128

-61 grâce aux meilleurs conseils de Giuseppe

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

Essayez-le en ligne!

La chaîne est divisée en utilisant utf8ToIntet chaque valeur ASCII est comptée table. Le résultat est calculé en utilisant une multiplication matricielle %*%sur celle + 1 et finalement divisée par deux.

05AB1E , score 6

{γ€gLO

Essayez-le en ligne!

Pyth , score 6

1 octet grâce à isaacg.

+F/V._

Suite de tests.

Comment ça fonctionne

+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 , score: 14 12 11

$+/@,2!1#.=

Essayez-le en ligne!

Gelée , score de 7

ċЀQRFS

Explication:

   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)

Essayez-le en ligne!

C, 60 octets, score 108 95

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

Essayez-le en ligne!

Généralement, les opérateurs avant et après l’incrément sont parfaits pour le golf de code, mais ils font vraiment mal à ce défi!

EDIT: En soustrayant les comptes négatifs au lieu d’en ajouter des positifs, j’ai sauvé tout un tas de points. Remplacer for()par while()un point-virgule éliminé également.

Perl 6 , score  61 56 53 46  44

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

L'essayer

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

L'essayer

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

L'essayer

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

L'essayer

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

L'essayer

C # (.NET Core) , score (je veux dire, 209)

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

Essayez-le en ligne!

Le score comprend les éléments suivants:

using System.Linq;

Gelée , score 5

ĠJ€ẎS

Essayez-le en ligne!

Merci à Leaky Nun pour -2 (précédemment sur sa réponse )

PowerShell, score 64

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

(Le score est basé sur un saut de ligne simple, ce qui n’est pas une norme Windows, mais fonctionne en mode PS).

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

• Table de hachage @{}
• Itérer à travers les lettres; $argsest un tableau de paramètres - dans ce cas, la chaîne d'entrée en fait un tableau à un seul élément; |%effectue une boucle foreach sur les éléments et utilise le getE*raccourci pour faire correspondre la GetEnumerator()méthode string et l'appeler pour transformer la chaîne en flux de caractères.
• |%boucle sur les caractères et incrémenter leur entrée hashtable, l'ajouter à un total en cours d'exécution. Le ($x+=1)formulaire avec parent modifie à la fois la variable et génère la nouvelle valeur à utiliser.
• Affiche le total cumulé.

(Quand je l'ai écrit pour la première fois, c'était $c=@{};$t=0;[char[]]"$args"|%{$c[$_]++;$t+=$c[$_]};$tavec un score de 128, et je pensais que ça ne baisserait pas beaucoup. Réduire de moitié le score à 64, c'est très agréable).

Julia 0.6 , 45 bytes, Score: 77

Inspiré par la solution MATL:

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

Essayez-le en ligne!

Une solution moins jolie, en utilisant des comptes:

Julia 0.6 , score de 82

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

Essayez-le en ligne!

Merci à Guiseppe pour avoir souligné le pointage et les conseils. Ces commentaires m'ont aidé énormément.

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

( Octets: 72 73 74 75 64 62 61 ) Les octets montent, mais le score baisse. :RÉ

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

-28 score (et -11 octets) grâce à @Nevay .
-1 score (et -2 octets) grâce à @ OlivierGrégoire .
-1 score (et -1 octet) en convertissant Java 8 en Java 10.

Explication:

Essayez ici.

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 #, score 120 118

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

-2 grâce à Kevin Cruijssen !

Essayez-le en ligne!

Prend un stringcomme une entrée. Seq.countByassocie chaque caractère distinct avec son compte ( idest la fonction identité) pour vous retrouver avec une collection comme 'a' = 4, 'b' = 2etc.

Le Seq.sumByprend le compte pour chaque lettre et additionne tous les nombres du 0compte pour cette lettre. Donc, si 'a' = 4la collection serait ce 0, 1, 2, 3, 4qui est résumé est 10. Puis Seq.sumByadditionne tous ces totaux.

APL (Dyalog) , note 15

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

Essayez-le en ligne!

⍞ obtenir la saisie de texte

∘.=⍨ table d'égalité avec soi

+\ somme cumulée sur

1 1⍉ diagonale (lit. réduit les deux dimensions en une dimension)

+/ somme

Retina , score 68 45 43

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

Essayez-le en ligne! Le lien montre le score. Edit: Merci à @MartinEnder qui a enregistré 20 octets en utilisant des correspondances superposées au lieu d’indicatifs et trois octets supplémentaires en regroupant les étapes de sorte que le sdrapeau ne doit être appliqué qu’une seule fois. A enregistré deux autres octets en calculant le nombre triangulaire différemment, en évitant le besoin d'un tri.

PHP , 45 octets, Score 78

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

Essayez-le en ligne!

PHP , 46 octets, Score 79 octets

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

Essayez-le en ligne!

PHP , 56 octets, score 92

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

Essayez-le en ligne!

Score Perl 5 91 83

Utilise le -pdrapeau qui ajoute 2 à cause du p en split.

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

Octave , 39 bytes, Score 69

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

Essayez-le en ligne!

Bien qu'il y ait une autre réponse Octave, celle-ci est entièrement la mienne et constitue une approche différente. En plus, elle marque moins :).

L’approche se résume à la première recherche du nombre (b) de chaque caractère unique, obtenu à l’aide de la fonction histogramme. Ensuite, pour chaque élément, nous calculons la somme de 1 à b qui est effectuée à l'aide de la formule(b*(b+1))/2 . Ensuite, les sommes individuelles sont toutes additionnées dans le score final.

Lors des tests, il semble que les consoles coûtent très cher car beaucoup d’entre elles sont nécessaires. J'ai optimisé le score initial d'environ 88 en réorganisant les questions afin de minimiser le nombre de crochets ouverts / fermés - nous passons donc maintenant à la valeur / 2 sur le total final plutôt qu'individuellement, et j'ai également modifié la formule pour (b^2+b)/2car cela nécessite moins de crochets.

Common Lisp, score 286 232 222

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

Score élevé en raison de la syntaxe verbeuse des opérateurs intégrés de Common Lisp.

Essayez-le en ligne!

Le code non-golfé:

(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, score 54

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

contribution

["abcdefg"]

grâce à hftf