93
\$\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\$
  • 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 Jun 19 '17 at 20:20
  • 2
    \$\begingroup\$ @ValueInk Yes, I think counting the n is the fairest option. \$\endgroup\$ – Laikoni Jun 19 '17 at 20:34
  • 1
    \$\begingroup\$ I really wish there was a brainfuck solution to this challenge. \$\endgroup\$ – Peter1807 Jun 21 '17 at 12:16
  • 10
    \$\begingroup\$ +1 for The score of your submission is the cost of your code \$\endgroup\$ – luizfzs Jun 22 '17 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\$ – undergroundmonorail Jan 19 '18 at 19:33

83 Answers 83

1
\$\begingroup\$

R, 349

Here is my R solution bit of tidy

s=function(x) {c=0
for (i in unique(strsplit(x,"")[[1]])) {
c=c(c,sum(1:sum(charToRaw(x)==charToRaw(i))))}
sum(c)
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to PPCG! The point of this challenge is to make the score (the output of running your code on your code) as small as possible. This would have quite a large score! I would be more than happy to help you reduce the score. \$\endgroup\$ – Giuseppe Mar 17 '18 at 15:34
  • \$\begingroup\$ Thanks @Giuseppe will work to improve it! Cheers \$\endgroup\$ – Riccardo Camon Mar 17 '18 at 15:38
  • \$\begingroup\$ This answer still has a lot of unnecessary whitespace and long variable names it. Also, in order to be a valid solution, you'll need to provide the current byte count. (which is currently 174) \$\endgroup\$ – DJMcMayhem Mar 19 '18 at 17:24
  • 1
    \$\begingroup\$ While in the counting part you use charToRaw(), better use it instead strsplit() too. Score 195 \$\endgroup\$ – manatwork Mar 20 '18 at 13:16
  • \$\begingroup\$ @manatwork thanks for your advice but it is not quite clear when you would use strsplit() \$\endgroup\$ – Riccardo Camon Mar 21 '18 at 11:27
1
\$\begingroup\$

SHELL ( 67 bytes)

Last Solution : ( 68 bytes)

 f(){ bc<<<`echo -n "$1"|od -bAn|sed "s/\([^ ]\+\)/s+=++v\1;/g"`s;}

Old solutions :

Old Solution 1 : by creating function f (83 bytes ) :

f(){ bc<<<`echo "$1"|sed "s/./ss+=++&;/g"|sed "s/[A-Z]/\L&_/g"|sed "s/ /bb/g"`ss;}

Old Solution 2 : by creating alias f ( 81 bytes )

alias f='bc<<<`cat -|sed "s/./ss+=++&;/g"|sed "s/[A-Z]/\L&_/g"|sed "s/ /bb/g"`ss'

Explanations :
I used ( sed "s/./ss+=++&;/g" ) to replace any char a by ( ss+=++a; ); where ss is the sum to calculate, then concatenate with ss, and calculate all expression by the command bc :

echo "a" | sed "s/./ss+=++&;/g"
ss+=++a;

for a string in input :

echo "aab" | sed "s/./ss+=++&;/g"
ss+=++a;ss+=++a;ss+=++b;

step by step :

ss+=++a;    // a=1  -->  ss=1
ss+=++a;    // a=2  -->  ss=3
ss+=++b;    // b=1  -->  ss=4

for lowercase only input, the simpler function need only ( 47 bytes ) to define :

f(){ bc<<<`echo "$1"|sed "s/./ss+=++&;/g"`ss;}

to take uppercase in consideration, Without spaces ( 68 bytes) :

f(){ bc<<<`echo "$1"|sed "s/./ss+=++&;/g"|sed "s/[A-Z]/\L&_/g"`ss;}

Complete Solution ( 83 bytes):

f(){ bc<<<`echo "$1"|sed "s/./ss+=++&;/g"|sed "s/[A-Z]/\L&_/g"|sed "s/ /bb/g"`ss;}

fuction tests :

f "abaacab"
14

f "abcdefg"
7

f "       "
28

f "Aa"
2

using an alias instead the function, we can reduce code size to ( 68 bytes )

alias f='bc<<<`cat -|sed "s/./ss+=++&;/g"|sed "s/[A-Z]/\L&_/g"|sed "s/ /bb/g"`ss'

alias tests :

echo "       " | f
28

echo "Ab" | f
2
\$\endgroup\$
  • 1
    \$\begingroup\$ The score of your submission is the cost of your code, that is 241 for the 84-byte version and 232 for the 81 byte version. \$\endgroup\$ – Laikoni Mar 17 '18 at 15:10
  • \$\begingroup\$ Since this challenge is not scored by length, you should list the scores instead of byte counts. \$\endgroup\$ – Ørjan Johansen Mar 23 '18 at 2:37
1
\$\begingroup\$

JavaScript, 150 141 133

f=(g,i=[])=>g?(i[j=g.charCodeAt()]=(i[j]|0)+1)+f(g.substr(1),i):0

Ungolfed:

f=(g,i=[])=>                                                       //function declaration, a is list of appearance of characters so far.
            g?                                                     //check if string is empty
              (i[j=g.charCodeAt()]=                                //update appearance list
                                    (i[j]|0)+1)+                   //handle undefined, then increment
                                                f(g.substr(1),i)   //next character
                                                                :0 //base case for the empty string

150->141 - -6 for renaming variables to unique characters (thanks to Ørjan Johansen), and -3 for removing implicit 0 in charCodeAt.

141->133 - -8 for using actual unique variable names(thanks again to Ørjan Johansen).

\$\endgroup\$
  • \$\begingroup\$ The variable names s,a,c give you a higher score than necessary because they're used as characters in charCodeAt and subStr. \$\endgroup\$ – Ørjan Johansen Apr 28 at 10:45
  • \$\begingroup\$ @Ørjan Johansen Hmm, then let's see if I can do better \$\endgroup\$ – Naruyoko Apr 28 at 17:11
  • \$\begingroup\$ b and d are still not unique. I think i and j are the first vacant ones. \$\endgroup\$ – Ørjan Johansen Apr 29 at 0:33
  • \$\begingroup\$ @Ørjan Johansen Oh yeah true \$\endgroup\$ – Naruyoko Apr 29 at 0:50
1
\$\begingroup\$

C++ (gcc), Score: 209 196

98 96 bytes

#include<map>
long	F(std::string	S){int I=0;for(auto&C:S){++I;for(char&D:S)I+=C==D;}return I/2;}

C++-specific tricks:

  • #include<map> instead of #include<string>
  • Returning long instead of int to use more different characters
  • Using auto instead of char in one of the loops has the same effect
  • References (&) inside range-for save whitespace

Common tricks:

  • Evenly use both tabs and blanks
  • Upper case variables to be distinct from keyword characters

Try it online!

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

JavaScript (Firefox 30+), score 68

S=>[for(C of(T=0,S))T+=S.split(C).length]&&T/2

This uses array comprehensions which were originally planned for ES7, but were dropped late in the process. Firefox had implemented them anyway.

\$\endgroup\$
  • \$\begingroup\$ I thought those were ES6...? \$\endgroup\$ – CalculatorFeline Jun 20 '17 at 1:55
  • \$\begingroup\$ @CalculatorFeline No, they didn't make it in favour of map/filter with arrow functios \$\endgroup\$ – Bergi Jun 22 '17 at 0:08
  • \$\begingroup\$ *planned for ES6 \$\endgroup\$ – CalculatorFeline Jun 22 '17 at 2:26
0
\$\begingroup\$

Python 2, score 108

lambda S:sum(S.count(Q)*(S.count(Q)+1)/2for Q in set(S))

Still golfing :)

\$\endgroup\$
  • \$\begingroup\$ I think you missed the scoring system. \$\endgroup\$ – Leaky Nun Jun 19 '17 at 17:31
  • \$\begingroup\$ @LeakyNun Oh shoot you're right –– and that was fast \$\endgroup\$ – Daniel Jun 19 '17 at 17:31
  • \$\begingroup\$ S.count(Q)*(S.count(Q)+1)/2for Q in set(S) should be the same as (S.count(Q)+1)/2for Q in S \$\endgroup\$ – movatica Apr 27 at 21:54
0
\$\begingroup\$

QBIC, score: 128

dim x(126)[_l;||i=asc(_sA,a,1|)┘x(i)=x(i)+1][126|[x(b)|p=p+c}?p

Nice round score of 128.

Explanation

dim x(126)      Create an array of 126 elements (one for each ASCII element)
[_l;||          Read cmd line input, loop over its length
i=asc(_sA,a,1|) Read the next char's ascii value
┘               (Syntactic linebreak)
x(i)=x(i)+1     Raise the count of this ASCII char by 1
]               NEXT
[126|           Loop over the ASCII array again
[x(b)|          Read the count and start a loop that runs from 1 to that count
p=p+c           Add to running total p the loop counter
}               Close both loops
?p              PRINT p
\$\endgroup\$
0
\$\begingroup\$

Ruby, score 63 60

Uses the -n flag which ends up adding 2 points due to the presence of another n within the code.

-3 points from Alexis Anderson.

i=x=0
gsub(/./){x+=$_[0,i+=1].count$&};p x

Try it online!

\$\endgroup\$
  • \$\begingroup\$ why not use a different variable than s since s is in gsub. It would save you 3 points, I believe. \$\endgroup\$ – Alexis Andersen Jun 21 '17 at 17:06
  • \$\begingroup\$ @AlexisAndersen wow I can't believe I missed that \$\endgroup\$ – Value Ink Jun 21 '17 at 19:35
0
\$\begingroup\$

Swift 3, 153 bytes, score = 637

var u:(String)->Int={var d = Dictionary<Character,Int>()
for c in $0.characters{d[c] = (d[c] ?? 0) + 1}
return d.values.reduce(0,{$0 + $1 * ($1 + 1) / 2})}

Legible version plus explanation

func unique(_ string: String) -> Int {
    var dict = Dictionary<Character, Int>()
    for char in string.characters { dict[char] = (dict[char] ?? 0) + 1 }
    return dict.values.reduce(0, { $0 + $1 * ($1 + 1) / 2 })
}

My solution takes the string, iterates over the characters and tracks each unique character in a dictionary, counting the occurrences per character. Once that's done, it reduces the dictionary's values using the triangle number formula ( n(n+1) / 2 ) and returns the result.

Comments

Swift obviously isn't the best language for golfing, but it was fun to see where I could save bytes despite its rigid syntax. This is my first Swift submission - be gentle!

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

CJam, score 18

q_,{)W$<}%.e=0+:+

Try it online!

Explanation

q                  e# Read the input.
 _,                e# Copy it, get its length.
   {               e# Map over the range from 0 .. length-1:
    )              e#  Increment the current number.
     W$            e#  Push the input.
       <           e#  Get the first <current number> characters of it.
        }%         e# (end map)
          .e=      e# Count the occurrences of each character in the corresponding slice.
             0+    e# Append a 0 to the result (because you can't reduce and empty list).
               :+  e# Reduce by addition (sum).
\$\endgroup\$
  • \$\begingroup\$ You can replace 0+:+ with 1b (convert from base 1, which handles empty list and doesn't have the duplicated character), which gets you a score of 15. \$\endgroup\$ – Esolanging Fruit Jan 19 '18 at 5:20
0
\$\begingroup\$

><> (Fish), score 133

!<01-0&i:2(:?&:?n?;&1+&:}}:3(00@@?.~~:{=&+&{$}8e+0.>.!06}~{ 

This code reads the input per character, adds a point and loops through all the read characters, adding an extra point for every equal character.

You can try it out here

Explanation

!<01-0&         // Initialize (put -1 on the stack and 0 in the register)
i:2(:?$:?n?;    // Read the next input. If it's -1, print the register and end the program.
&1+&            // Add one to the register
:}}:            // Duplicate both the input and the check value
3(00@@?.~~      // If the check value is -1, jump the instruction pointer to 0,0 (line 0)
:{=&+&          // Compare the input to the check value and add the result to the register
{$}8e+0.        // Move the checked value to the bottom of the stack and jump to 22,0 (line 4)
>.!06}~{        // Clean up the stack and jump to 0,6 (line 2)
\$\endgroup\$
0
\$\begingroup\$

Factor, 2435

(o god my score)

"" over [ 2dup swap in? [ drop ] [ suffix ] if ] each { } swap swapd [ dupd 0 swap swapd swap [ over = swap [ [ 1 + ] [ ] if ] dip ] each drop swap [ suffix ] dip ] each drop [ dup 1 + * 2 / ] map sum (wrong formatting on purpose for multi-line span)

Wow, Factor is hard. Or I'm just bad. Probably a little bit of both.

\$\endgroup\$
  • \$\begingroup\$ Could you tell me what needs to be added in order to test this code on Try it online? \$\endgroup\$ – Laikoni Jul 18 '17 at 10:11
  • \$\begingroup\$ @Laikoni add the string to the beginning of the code. So, for abaacab, the code will read "abaacab" "" over [ 2dup ... \$\endgroup\$ – Quelklef Jul 23 '17 at 0:26
  • \$\begingroup\$ @Laikoni Come to think of it, you'd have to add USING: kernel sequences sets math ; to the beginning, too, (they're libraries). Also, it's working on my local machine but not on TIO, and IDK why. Never used Factor on TIO. \$\endgroup\$ – Quelklef Jul 23 '17 at 0:32
0
\$\begingroup\$

Pyt, 6 bytes

ĐỤ⇹ɔ△Ʃ

Explanation:

              Implicit input
Đ             Duplicate top of stack
 Ụ            Get unique characters
  ⇹           Swap top two items on stack
   ɔ          Count number of times each unique character occurs in the input
    △         Calculates the total score for each character
     Ʃ        Sum count
              Implicit output

Try it online!

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

JavaScript, 49 bytes, score 88

b={};s=0;for(j in a=prompt())s+=b[a[j]]=-~b[a[j]]
\$\endgroup\$
  • \$\begingroup\$ The score of each submission is not the byte count, but the cost of the submission, that is the program run on its own source code. This means your score is 88 instead of 49. \$\endgroup\$ – Laikoni Jul 17 '17 at 13:07
0
\$\begingroup\$

jq, score 60

(40 characters code + 3 characters command line option)

[./""|group_by(.)[]|range(length+1)]|add

Sample run:

bash-4.4$ jq -R '[./""|group_by(.)[]|range(length+1)]|add' <<< 'Programming Puzzles & Code Golf'
47

Try it online!

jq, score 63

[./""|group_by(.)[]|range(length+1)]|add+0

In case the result for empty string must be numeric 0. There are a few other solutions that use alternative representation of nothing.

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

Stax, 8 6

ç╕┌α▒'

Run and debug online!

Saved 2 points by using runs per comment by @recursive.

Explanation

Uses the unpacked version to explain.

o:GF:T+
o          Sort array
 :G        Run lengths
   F       For each run length `n`
    :T     The nth triangular number
      +    Add to accumulator
           Implicit output
\$\endgroup\$
  • 1
    \$\begingroup\$ run-length is good here. 6 \$\endgroup\$ – recursive Mar 17 '18 at 0:02
0
\$\begingroup\$

Kotlin, score 93

{it.foldIndexed(0){z,q,v->q+it.take(z+1).count{it==v}}}

Try it online!

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

Reticular, score 56

iSd:A=>ddV@c~dc$:A=+:A`L0EQ6jj+1*37_$O;

Try it online!

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

Perl 6, Score: 34

{sum [\+](^∞)[.comb.Bag{*}]}

Try it online!

Takes advantage of the unicode operator to save on characters.

Explanation

{                          }  # Anonymous code block
              .comb           # Split the input string into characters
                   .Bag{*}    # Get the count of each character
             [            ]   # And inded each into
         (^∞)                 # The infinite list of integers
     [\+]                     # Triangularly summed (0,0+1,0+1+2...)
 sum                          # And return the sum total
\$\endgroup\$
0
\$\begingroup\$

05AB1E (legacy), score: 4 (4 bytes)

Ù¢LO

Input as a list of characters.

Try it online or verify all test cases.

Explanation:

Ù     # Get all unique characters of the (implicit) input-list
 ¢    # For each, count the amount of times it occurs in the (implicit) input-list
  L   # Create a list of each of these counts
      # (which implicitly flattens in the legacy version of 05AB1E)
   O  # Take the sum of all those integers
      # (which is output implicitly as result)
\$\endgroup\$
0
\$\begingroup\$

Zsh, 36 bytes, score 52

for	p (${(s..)1})$[j+=++a[#p]]
<<<$j

Try it online!

One tab, one space, one newline. This will fill up the debug log with "command not found". If that must be avoided, 38 bytes, score 55.

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

Haskell, 150 133 points

(79 75 bytes)

import Data.List
c=foldr(\x->	\y->y+(x*(x+1)`div`2))0.map length.group.sort

Try it online!

  • -17 points by removing some parentheses (thanks to @Laikoni)
\$\endgroup\$
  • 1
    \$\begingroup\$ You can drop the parenthesis around the foldr expression and just write map length instead of (map$length) for a score of 133. \$\endgroup\$ – Laikoni Sep 5 at 10:15
0
\$\begingroup\$

Gaia, score: 11

$:uC¦ₔ┅¦_Σ

Try it online!

For some reason, _ is necessary else this spits out garbage answers. But the language is defined by its implementation, so what are ya gonna do.

$		| split into characters
 :		| dup
  u		| get unique
   C¦ₔ		| get counts of uniques into original
      ┅¦	| sequence: 1..count
        _Σ	| sum
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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