105
\$\begingroup\$

Write a function or program that determines the cost of a given string, where

  • the cost of each character equals the number of how many times the character has occurred up to this point in the string, and
  • the cost of the string is the sum of its characters' costs.

Example

For an input of abaacab, the cost is computed as follows:

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

Thus the cost for the string abaacab is 14.

Rules

  • The score of your submission is the cost of your code as defined above, that is your submission run on its own source code, with a lower score being better.
  • Your submission should work on strings containing printable ASCII-characters, plus all characters used in your submission.
  • Characters are case-sensitive, that is a and A are different characters.

Testcases

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

Leaderboard

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>

\$\endgroup\$
12
  • 2
    \$\begingroup\$ How do program flags such as -n for Perl count towards the score? It traditionally counts as 1 byte because the edit distance between the standard perl -e and perl -ne is 1, but for this challenge, will the n count for the purposes of counting duplicates? \$\endgroup\$
    – Value Ink
    Commented Jun 19, 2017 at 20:20
  • 2
    \$\begingroup\$ @ValueInk Yes, I think counting the n is the fairest option. \$\endgroup\$
    – Laikoni
    Commented Jun 19, 2017 at 20:34
  • 1
    \$\begingroup\$ I really wish there was a brainfuck solution to this challenge. \$\endgroup\$
    – Peter1807
    Commented Jun 21, 2017 at 12:16
  • 11
    \$\begingroup\$ +1 for The score of your submission is the cost of your code \$\endgroup\$
    – luizfzs
    Commented Jun 22, 2017 at 15:21
  • 1
    \$\begingroup\$ cost of a character is defined as how often this character has already occurred in the string, i'd probably changing to how many times the character has occurred up to this point to make it clearer that the first use costs 1, not 0 \$\endgroup\$ Commented Jan 19, 2018 at 19:33

92 Answers 92

84
\$\begingroup\$

MATL, score 4

&=Rz

Try it online!

Explanation

Consider input 'ABBA' as an example.

&=   % 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
\$\endgroup\$
6
  • 15
    \$\begingroup\$ Are you a linear algebra professor? \$\endgroup\$ Commented Jun 20, 2017 at 18:53
  • 4
    \$\begingroup\$ @carusocomputing Actually a mobile communications professor. My tendency to use matrices comes from years of programming in Matlab \$\endgroup\$
    – Luis Mendo
    Commented Jun 20, 2017 at 18:57
  • \$\begingroup\$ Neat! Is Matlab big in that area? I've never really looked into GSM or anything like it. \$\endgroup\$ Commented Jun 20, 2017 at 19:27
  • 3
    \$\begingroup\$ I joined this community just to commend you on this brilliant solution! \$\endgroup\$
    – Wboy
    Commented Jun 21, 2017 at 5:21
  • 1
    \$\begingroup\$ @carusocomputing Matlab is a very common tool/language in engineering in general. It's good at numerical computation: linear algebra, signal processing, and the like. And being an interpreted language it's very easy to use \$\endgroup\$
    – Luis Mendo
    Commented Jun 21, 2017 at 8:29
17
\$\begingroup\$

Python, score 49

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

Try it online!

There's a tab after in.

Score breakdown:

  • +27 for 27 unique chars
  • +16 for 8 double chars: ()Camnou
  • +6 for 1 tripled char: S
\$\endgroup\$
9
  • 13
    \$\begingroup\$ Use a tab instead of a space to save a byte. \$\endgroup\$
    – mbomb007
    Commented Jun 19, 2017 at 17:20
  • 1
    \$\begingroup\$ @mbomb007 Just had the same idea :-) \$\endgroup\$
    – xnor
    Commented Jun 19, 2017 at 17:21
  • 1
    \$\begingroup\$ @mbomb007 Hah, that's a genius trick :-) \$\endgroup\$ Commented Jun 19, 2017 at 17:21
  • 14
    \$\begingroup\$ @mbomb007 that's just tabs vs. spaces war inside golfed code \$\endgroup\$ Commented Jun 19, 2017 at 17:23
  • 2
    \$\begingroup\$ I was going to suggest using a form feed (which is also permitted whitespace in Python syntax), but you don't have any more whitespace to replace. \$\endgroup\$ Commented Jun 19, 2017 at 23:39
8
\$\begingroup\$

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: Dropped a couple of variables, compacted a bit. Down to 16 @ symbols instead of 22, that by itself reduces my score by a whopping 117 points!

Nice contest, I like the requirement to optimize for something besides total character count.

Input is via varchar field q in pre-existing table z, per our IO rules. The database containing this input table must be set to a case-sensitive collation.

Formatted:

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

SQL keywords aren't case sensitive, so I used mixed case to minimize the count of duplicate letters (aaAA generates a better/lower score than aaaa).

The main loop compares the length before and after stripping all instances of the first character out. That difference n*(n+1)/2 is added to a running total.

The SQL LEN() function annoyingly ignores trailing spaces, so I had to append a control character and subtract 1 at the end.

EDIT: Fixed a miscalculation of my own score by 2 points (issue with quoting quotes), reduced by 1 by changing casing of one R. Also working on a completely different strategy, I'll be posting that as its own answer.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ At first I thought your score was 579! ≈ 8.22 x 10^1349 \$\endgroup\$ Commented Jul 17, 2017 at 12:54
8
\$\begingroup\$

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

Thanks to @ugoren, @CalculatorFeline, @gastropner, @l4m2, and @JS1 for their tips.

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

Initializes an array of zeros, then uses the ASCII values of the characters in the string as indices to that array to keep track of the number of instances of each character in the string.

Try it online!

\$\endgroup\$
16
  • 3
    \$\begingroup\$ Suggestion: Use variable names that aren't used in keywords, like z,x,c. \$\endgroup\$ Commented Jun 19, 2017 at 17:02
  • \$\begingroup\$ @CalculatorFeline char includes c... \$\endgroup\$
    – Neil
    Commented Jun 19, 2017 at 17:27
  • 3
    \$\begingroup\$ Also, you only need a 127 element array (\x7f is not printable) and please add an explanation. \$\endgroup\$ Commented Jun 19, 2017 at 17:42
  • 1
    \$\begingroup\$ Late to the party, but this should be 96: z;g(char*s){int y[238]={z=0};while(*s)z+=--y[*s++];z/=~0;} \$\endgroup\$
    – gastropner
    Commented Mar 15, 2018 at 10:07
  • 1
    \$\begingroup\$ g(char*s){int y[238]={};while(*s)*y+=--y[*s++];*y/=~0;} \$\endgroup\$
    – l4m2
    Commented Jan 6, 2019 at 11:07
7
\$\begingroup\$

JavaScript (ES6), score 81 78

Saved 3 points thanks to @Arnauld

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

My original score-81 recursive solution:

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

Haskell, score 42

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

Try it online!

Anonymizing \l-> gives the same score.

\$\endgroup\$
7
\$\begingroup\$

Jelly, score 6

;\ċ"⁸S

Try it online!

\$\endgroup\$
0
7
\$\begingroup\$

Retina, score 34

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

Try it online!

Explanation

s(O`.

We start by sorting all the characters in the input so that identical characters are grouped together into a single run. The s( activates singleline mode for all stages (i.e. makes . match linefeeds).

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

The goal is to turn a run of n characters into Tn characters (the nth triangular number) because that's the score of the occurrences of this character. To do so, we find overlapping matches. In particular, for each i in [1,n], we're going to include i-1 characters in the match. We get all those matches due to the overlapping flag &. That gives us n*(n-1)/2 = Tn-1 = Tn - n characters just from the matches. But the match stage will join these with linefeeds, which are n linefeeds for n matches. There's only one problem. There won't be a linefeed after the last match, so the overall number of characters in the output is one less than we need. We fix this by also matching the beginning of the input, which gives us a single leading linefeed if there is at least one other match.

.

Finally, we just count how many characters there are in the string.

\$\endgroup\$
0
6
\$\begingroup\$

Haskell, score 52 51

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

There's a tab between f and _.

Try it online!

The value of the empty string is 0. The value of the string s, where a is the first char and b the rest of the string is 1 plus the occurrences of a in b plus a recursive call with b.

\$\endgroup\$
0
5
\$\begingroup\$

J, score 16

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

Try it online!

Explanation

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.

Using 1#. instead of +/@ for the sum saved a few points, and & could be used instead of @ in a monadic context to save one more. The repeated 1 costs me one extra point, but I haven't been able to get rid of it.

\$\endgroup\$
4
  • \$\begingroup\$ "later" waits a quarterday \$\endgroup\$ Commented Jun 20, 2017 at 1:56
  • 2
    \$\begingroup\$ @CalculatorFeline 10 hours later is still later. :P \$\endgroup\$
    – Zgarb
    Commented Jun 20, 2017 at 6:35
  • \$\begingroup\$ Let's make it a sesquisemiday now. \$\endgroup\$ Commented Jun 20, 2017 at 15:24
  • \$\begingroup\$ I personally use this format for TIO answers in order to reflect an accurate byte count in the code section, maybe you would want to use it \$\endgroup\$ Commented Jun 21, 2017 at 22:29
5
\$\begingroup\$

R, score: 67 83 95 128

-61 thanks to top tips from Giuseppe

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

Try it online!

The string is split using utf8ToInt and each ascii value is counted table. The the result is calculated using doing a matrix multiplication %*% over that at itself + 1 and finally halfed.

\$\endgroup\$
5
  • \$\begingroup\$ use table instead of rle; you can get rid of the sort as well (and you don't have to index [[1]] into the result of strsplit) \$\endgroup\$
    – Giuseppe
    Commented Jun 19, 2017 at 20:36
  • \$\begingroup\$ @Giuseppe Thanks a lot. I didn't even think of table, will incorporate soon. \$\endgroup\$
    – MickyT
    Commented Jun 19, 2017 at 20:44
  • 2
    \$\begingroup\$ I think you can save a few more bytes by using a different variable name instead of n (since it's in function twice) and also changing (n+1) to {n+1} \$\endgroup\$
    – Giuseppe
    Commented Jun 19, 2017 at 21:02
  • \$\begingroup\$ score:67. Some variation on this might make it possible to reduce the score further. \$\endgroup\$
    – Giuseppe
    Commented Jan 18, 2018 at 17:54
  • \$\begingroup\$ @Giuseppe ... I should have re read it . whoops \$\endgroup\$
    – MickyT
    Commented Jan 18, 2018 at 18:51
4
\$\begingroup\$

05AB1E, score 6

{γ€gLO

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Jelly, score 5

ĠJ€ẎS

Try it online!

Thanks to Leaky Nun for -2 (previously on his answer)

\$\endgroup\$
5
  • \$\begingroup\$ Ahhh I didn't notice this question fast enough. \$\endgroup\$
    – Leaky Nun
    Commented Jun 19, 2017 at 17:00
  • \$\begingroup\$ @LeakyNun p.s. you're not always a ninja, nor anyone is \$\endgroup\$ Commented Jun 19, 2017 at 17:01
  • \$\begingroup\$ Really? I don't think so. \$\endgroup\$ Commented Jun 19, 2017 at 17:03
  • 1
    \$\begingroup\$ Score 5: ĠJ€ẎS \$\endgroup\$
    – Leaky Nun
    Commented Jun 19, 2017 at 17:30
  • \$\begingroup\$ @LeakyNun As promised...yeah, the credit is there :) \$\endgroup\$ Commented Jun 19, 2017 at 17:36
4
\$\begingroup\$

Pyth, score 6

1 byte thanks to isaacg.

+F/V._

Test suite.

How it works

+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.
\$\endgroup\$
4
  • \$\begingroup\$ s+0 is the same as +F. \$\endgroup\$
    – isaacg
    Commented Jun 19, 2017 at 19:27
  • \$\begingroup\$ Good! The best I could do is usaShHGrScQ1 8Z for 16. Can you add an explanation? \$\endgroup\$ Commented Jun 19, 2017 at 22:27
  • 1
    \$\begingroup\$ @DigitalTrauma I've added an explanation. \$\endgroup\$
    – Leaky Nun
    Commented Jun 20, 2017 at 3:47
  • \$\begingroup\$ s/LQ is score 4, does this use features that postdates the challenge? \$\endgroup\$
    – Dave
    Commented Jan 19, 2018 at 3:31
4
\$\begingroup\$

J, score: 14 12 11

$+/@,2!1#.=

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ Clever use of $. \$\endgroup\$
    – cole
    Commented Jan 18, 2018 at 20:31
  • \$\begingroup\$ Nice. Slight 11 byte variation: 1#.2!1+1#.= \$\endgroup\$
    – Jonah
    Commented Apr 28, 2019 at 5:12
  • \$\begingroup\$ @Jonah Reusing glyphs results in a penalty \$\endgroup\$
    – FrownyFrog
    Commented Apr 28, 2019 at 12:24
  • \$\begingroup\$ ah, missed that part. \$\endgroup\$
    – Jonah
    Commented Apr 28, 2019 at 14:32
4
\$\begingroup\$

Jelly, score of 7

ċЀQRFS

Explanation:

   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)

Try it online!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$
    – Laikoni
    Commented Jan 23, 2018 at 1:31
4
\$\begingroup\$

C, 60 bytes, score 108 95

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

Try it online!

Usually pre- and post-increment operators are great for code golf, but they really hurt on this challenge!

EDIT: By subtracting negative counts instead of adding positive ones, I saved a whole bunch of score. Replacing for() with while() eliminated a semicolon as well.

\$\endgroup\$
0
3
\$\begingroup\$

Perl 6, score  61 56 53 46  44

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

Try it

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

Try it

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

Try it

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

Try it

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

Try it

\$\endgroup\$
3
\$\begingroup\$

C# (.NET Core), score ∞ (I mean, 209)

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

Try it online!

The score includes the following:

using System.Linq;
\$\endgroup\$
4
  • \$\begingroup\$ I know it's been a while, but you can change return w*(w+1)/2 to return-~w*w/2 (score 196). EDIT: You can create a port of my Java 8 answer for a score of 149: using System.Linq;b=>{int[]x=new int[256];return\nb.Select(z=>++x[z]).Sum();} Try it online. \$\endgroup\$ Commented Jan 22, 2018 at 13:24
  • 1
    \$\begingroup\$ @KevinCruijssen: I got your solution down to a score of 111: b=>{var x=new int[256];return\nb.Sum(z=>++x[z]);} \$\endgroup\$
    – raznagul
    Commented Mar 15, 2018 at 11:07
  • \$\begingroup\$ @raznagul (*half year old response incoming*) 109 if you change the second space to a tab. ;) Try it online. \$\endgroup\$ Commented Sep 21, 2018 at 15:26
  • 1
    \$\begingroup\$ @KevinCruijssen (another half year old response incoming) 49 with the interactive compiler, and I think it won't ever get below 48. I find it odd how the more golfed C# answers get, the more readable they always seem to become. Try it online! \$\endgroup\$ Commented Apr 28, 2019 at 4:47
3
\$\begingroup\$

PowerShell, score 64

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

(Score is based on a single linefeed newline, which isn't Windows standard but does work in PS).

PS C:\> D:\unique-is-cheap.ps1 (gc D:\unique-is-cheap.ps1 -raw)
64
  • Hashtable counter @{}
  • Iterate through the letters; $args is an array of parameters - in this case the input string makes it a single item array; |% does a foreach loop over the items, and uses the getE* shortcut to match the GetEnumerator() string method and call it to turn the string into a character stream.
  • |% loop over the characters and increment their hashtable entry, add it to a running total. The ($x+=1) form with parens both modifies the variable and outputs the new value for use.
  • Output the running total.

(When I first wrote it, it was $c=@{};$t=0;[char[]]"$args"|%{$c[$_]++;$t+=$c[$_]};$t with a score of 128, and felt like it wouldn't go much lower. Halving it to 64 is quite pleasing).

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 61 pts/ 38 bytes by messing with the increment \$\endgroup\$
    – Veskah
    Commented Jan 3, 2019 at 4:34
  • \$\begingroup\$ 59 pts/36 bytes \$\endgroup\$
    – mazzy
    Commented Apr 29, 2019 at 7:29
3
\$\begingroup\$

Julia 0.6, 45 bytes, Score: 77

Inspired by the MATL solution:

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

Try it online!

A less pretty solution, using counts:

Julia 0.6, score: 82

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

Try it online!

Thanks to Guiseppe for pointing out the scoring and for tips. These comments helped me loads.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ The score of your submission is the cost of your code, which I think is 135. \$\endgroup\$
    – Giuseppe
    Commented Mar 14, 2018 at 15:45
  • 1
    \$\begingroup\$ I don't know Julia very well but I think you can reduce the score to 110 by switching some variable names and removing a set of parentheses. If returning a single-element vector is allowed, then you can replace (x+1) with [x+1] to further reduce the score. \$\endgroup\$
    – Giuseppe
    Commented Mar 14, 2018 at 17:09
  • \$\begingroup\$ You can save a score by changing the second space to a tab or new-line: score 104. And @Giuseppe tip of using [x+1] instead of (x+1) lowers it to a score of 98. \$\endgroup\$ Commented Mar 15, 2018 at 9:32
  • \$\begingroup\$ The second approach doesn't accept the empty string. It could be reduced to 63 points in Julia 0.7. \$\endgroup\$ Commented Nov 16, 2023 at 22:13
  • \$\begingroup\$ Adding a special case for the empty string brings the score to 83. \$\endgroup\$ Commented Nov 16, 2023 at 22:15
3
\$\begingroup\$

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

(Bytes: 72 73 74 75 64 62 61) Bytes go up, but score goes down. :D

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

-28 score (and -11 bytes) thanks to @Nevay.
-1 score (and -2 bytes) thanks to @OlivierGrégoire.
-1 score (and -1 byte) by converting Java 8 to Java 10.

Explanation:

Try it here.

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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ You can remove the ~ if you use j=0 and return-j; (133). \$\endgroup\$
    – Nevay
    Commented Sep 14, 2017 at 13:23
  • 1
    \$\begingroup\$ 103: x->{int[]q=new int[256];return\nx.chars().map(v->++q[v]).sum();} \$\endgroup\$
    – Nevay
    Commented Sep 14, 2017 at 13:34
  • 1
    \$\begingroup\$ @Nevay 103 actually, when I use j instead of u (return contains u) and a new-line and tab instead of the spaces. EDIT: Hehe, you've edited right when I made this comment. :) \$\endgroup\$ Commented Sep 14, 2017 at 13:34
3
\$\begingroup\$

F#, score 120 118

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

-2 thanks to Kevin Cruijssen!

Try it online!

Takes a string as an input. Seq.countBy pairs each distinct character with its count (id is the identity function) so you end up with a collection like 'a' = 4, 'b' = 2 etc.

The Seq.sumBy takes the count for every letter and sums all the numbers from 0 to the count for that letter. So if 'a' = 4 the collection would be 0, 1, 2, 3, 4 which summed together is 10. Then Seq.sumBy sums all those totals.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ You can lower your score by 2 by changing let q to let j, since the q is already used in both Seq. \$\endgroup\$ Commented Sep 21, 2018 at 15:17
3
\$\begingroup\$

BQN, Score: 4

≠+´⊒

Run online!

The occurrence count builtin calculates the cost of each character decremented by 1. To adjust for that we can either add 1 to each cost or add the length to the sum. The latter turns out to be a byte shorter.

\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog), score 15

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

Try it online!

 get text input

∘.=⍨ equality table with self

+\ cumulative sum across

1 1⍉ diagonal (lit. collapse both dimensions into dimension one)

+/ sum

\$\endgroup\$
2
\$\begingroup\$

Retina, score 68 45 43

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

Try it online! Link shows score. Edit: Thanks to @MartinEnder who saved 20 bytes by using overlapping matches instead of lookaheads and a further three bytes by grouping the stages so that the s flag only needs to be applied once. Saved a further two bytes by calculating the triangular number differently, avoiding the need for a sort.

\$\endgroup\$
0
2
\$\begingroup\$

PHP, 45 bytes, Score 78

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

Try it online!

PHP, 46 bytes, Score 79 Bytes

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

Try it online!

PHP, 56 bytes, Score 92

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Perl 5 score 91 83

Uses the -p flag which adds 2 because of the p in split.

$x=$_;$b+=++$a{$_}for(split//,$x);$_=$b
\$\endgroup\$
3
  • \$\begingroup\$ Welcome to PPCG! \$\endgroup\$
    – Laikoni
    Commented Jun 20, 2017 at 21:22
  • 1
    \$\begingroup\$ Using your answer as a base and applying some techniques from the tips page, I managed to get your score down to 31: Try it online!. $` is automatically printed after each call so we can use that to store the score and /./g` returns a list of all chars in $_, which is cheaper than split//. \$\endgroup\$ Commented Jul 17, 2017 at 15:16
  • \$\begingroup\$ I know this is an old challenge, but you can cut the score even further: Try it online! \$\endgroup\$
    – Xcali
    Commented Mar 13, 2018 at 14:41
2
\$\begingroup\$

Octave, 39 bytes, Score 69

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

Try it online!

While there is another Octave answer, this one is entirely my own and a different approach, plus it scores less :).

The approach boils down to first finding the count (b) of each unique character, which is achieved using the histogram function. Then for each element we calculate the sum of 1 to b which is done using the formula (b*(b+1))/2. Then the individual sums are all summed into the final score.

In testing it seems brackets are really costly in the scoring because many are needed. I've optimised down from an initial score of about 88 by rearranging the questions to minimise the number of open/close brackets - hence we now do the /2 on the final total rather than individually, and also I've modified the formula to (b^2+b)/2 as that requires fewer brackets.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Unfortunately this appears to fail on the empty string: error: hist: subscript indices must be either positive integers less than 2^31 or logicals \$\endgroup\$
    – Laikoni
    Commented Jun 21, 2017 at 22:29
2
\$\begingroup\$

Octave , score 77 31 bytes

*same as @LuisMendo 's MATL answer.

@(a)nnz(triu(a==a'))

Try it online!

Previous answer:

@(d,g=accumarray(+d',1)-(0:254))sum(g(g>0));

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ You could probably save a point by ditching the semicolon. Couldn't test it as it doesn't seem to work with TIO. \$\endgroup\$ Commented Jun 21, 2017 at 22:05
  • \$\begingroup\$ @TomCarpenter Without ; doesn't work. however such a lambda cab be used in arrayfun. \$\endgroup\$
    – rahnema1
    Commented Jun 22, 2017 at 2:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.