# Question
Title: Display number of occurrences for every character in an input string
The code should take a string as input from keyboard:

```
The definition of insanity is quoting the same phrase again and again and not expect despair.

```

The output should be like this(not sorted in any particular order):

```
  :  15
. :  1
T :  1
a :  10
c :  1
e :  8
d :  4
g :  3
f :  2
i :  10
h :  3
m :  1
o :  4
n :  10
q :  1
p :  3
s :  5
r :  2
u :  1
t :  6
y :  1
x :  1

```

All ASCII characters count unicode is not a requirement, spaces, quotes,etc and input should come from keyboard / not constants, attributes, output should be printed with new line after each character like in the above example, it should not be returned as string or dumped as hashmap/dictionary etc, so `x : 1` and `x: 1` are ok, but `{'x':1,...` and `x:1` are not.

Q: Function or complete program taking stdin and writing stdout?
A: Code needs to be a program taking input using standard in and display the result via standard out.

# Scoreboard:

Shortest overall: 5 bytes

~~Shortest overall: 7 bytes~~

# Answer
> 3 votes
# APL (Dyalog Unicode), 5 bytesSBCS

Full program body. Prompts for a string from STDIN and prints newline separated table to STDOUT. Leftmost column is the input characters, and counts are right-aligned with the largest number separated from its character by a single space.

```
,∘≢⌸⍞

```

Try it online!

prompt for text input from STDIN

create a keys' table consisting of
`,` the unique element followed
by
the tally of the indices of its occurrence (i.e how many times it occurs)

# Answer
> 15 votes
## PHP - 68 (or 39) bytes

```
<?foreach(count_chars(fgets(STDIN),1)as$k=>$v)echo chr($k)." : $v
";

```

Output for the example text:

```
  : 15
. : 1
T : 1
a : 10
c : 1
d : 4
e : 8
f : 2
g : 3
h : 3
i : 10
m : 1
n : 10
o : 4
p : 3
q : 1
r : 2
s : 5
t : 6
u : 1
x : 1
y : 1

```

If the exact output is not required, this would work for **39 bytes**:

```
<?print_r(count_chars(fgets(STDIN),1));

```

Sample output:

```
Array
(
    [32] => 15
    [46] => 1
    [84] => 1
    [97] => 10
    [99] => 1
    [100] => 4
    [101] => 8
    [102] => 2
    [103] => 3
    [104] => 3
    [105] => 10
    [109] => 1
    [110] => 10
    [111] => 4
    [112] => 3
    [113] => 1
    [114] => 2
    [115] => 5
    [116] => 6
    [117] => 1
    [120] => 1
    [121] => 1
)

```

where each numerical index refers the ordinal value of the character it represents.

I suspect very strongly that using an in-built function that does exactly what the problem states will soon be disallowed.

# Answer
> 14 votes
# k (~~8~~ 7)

```
#:'=0:0

```

Example

```
k)#:'=:0:0
The definition of insanity is quoting the same phrase again and again and not expect despair.
T| 1
h| 3
e| 8
 | 15
d| 4
f| 2
i| 10
n| 10
t| 6
o| 4
s| 5
a| 10
y| 1
q| 1
u| 1
g| 3
m| 1
p| 3
r| 2
x| 1
c| 1
.| 1

```

edit: Down to seven, H/T Aaron Davies

## Explanation

Take a String from keyboard :

```
k)0:0
text
"text"

```

Group the distinct elements and return a map containing key as distinct characters and values are the indices where the distinct elements occur.

```
k)=0:0
text
t| 0 3
e| ,1
x| ,2

```

Now count values of each entry in the map.

```
k)#:'=0:0
text
t| 2
e| 1
x| 1

```

# Answer
> 13 votes
# GNU core utils - 29 22 20 chars (53 with formatting)

Wumpus's improvement (20 chars):

```
fold -1|sort|uniq -c

```

Firefly's improvement (22 chars):

```
grep -o .|sort|uniq -c

```

joeytwiddle's original (29 chars):

```
sed 's+.+\0\n+g'|sort|uniq -c

```

Originally I used `sed` to simply add a newline after each character. Firefly improved on that with `grep -o .`, since `-o` displays every matched pattern on its own line. Wumpus pointed out a further improvement using `fold -1` instead. Nice work!

`uniq` does the real work, although it only applies to sorted lists.

Note that the output format does not exactly match the example in the question. That requires a final run through `sed` to swap the arguments. (Waiting on an answer to Jan Dvorak's question to see if this is required...)

Reformatting with sed is "only" another 33 characters! (**Total 53**)

```
|sed 's/ *\(.*\) \(.\)/\2 :  \1/'

```

Awk can *almost* do the job whilst adding only 25 chars, but it hides the first space. Silly awk!

```
|awk '{print $2" :  "$1}'

```

I wonder if improvements can be made in the reformatting stage...

# Answer
> 7 votes
# Python 3: 76 characters

## 76

```
import collections as c
for x,y in c.Counter(input()).items():print(x,':',y)

```

### 44

(print same characters many times, see Wasi's answer for a valid version)

```
a=input()
for x in a:print(x,':',a.count(x))

```

# Answer
> 7 votes
# Ruby 1.9.3: 53 characters

(Based on @shiva's and @daneiro's comments.)

```
gets.split("").uniq.map{|x|puts x+" : #{$_.count x}"}

```

Sample run:

```
bash-4.1$ ruby -e 'a=gets;a.split("").uniq.map{|x|puts"#{x} : #{a.count x}"}' <<< 'Hello world'
H : 1
e : 1
l : 3
o : 2
  : 1
w : 1
r : 1
d : 1

 : 1

```

## Ruby: 44 characters

Not respecting the output format:

```
s=Hash.new 0;gets.chars{|c|s[c]+=1};pp s

```

Sample run:

```
bash-4.1$ ruby -rpp -e 's=Hash.new 0;gets.chars{|c|s[c]+=1};pp s' <<< 'Hello, world!'
{"H"=>1,
 "e"=>1,
 "l"=>3,
 "o"=>2,
 ","=>1,
 " "=>1,
 "w"=>1,
 "r"=>1,
 "d"=>1,
 "!"=>1,
 "\n"=>1}

```

# Answer
> 7 votes
## Perl 6: 21 chars

```
.say for get.comb.Bag

```

```
(REPL)
> .say for get.comb.Bag
The definition of insanity is quoting the same phrase again and again and not expect despair.
"T" => 1
"h" => 3
"e" => 8
" " => 15
"d" => 4
"f" => 2
"i" => 10
"n" => 10
"t" => 6
"o" => 4
"s" => 5
"a" => 10
"y" => 1
"q" => 1
"u" => 1
"g" => 3
"m" => 1
"p" => 3
"r" => 2
"x" => 1
"c" => 1
"." => 1
```

# Answer
> 5 votes
## APL (15)

```
M,⍪+⌿Z∘.=M←∪Z←⍞

```

If you really need the `:`, it's **19** (but there's others who aren't including it):

```
M,':',⍪+⌿Z∘.=M←∪Z←⍞

```

Output:

```
      M,⍪+⌿Z∘.=M←∪Z←⍞
The definition of insanity is quoting the same phrase again and again and not expect despair.
T  1
h  3
e  8
  16
d  4
f  2
i 10
n 10
t  6
o  4
s  5
a 10
y  1
q  1
u  1
g  3
m  1
p  3
r  2
x  1
c  1
.  1

```

# Answer
> 5 votes
### R, 30 characters

```
table(strsplit(readline(),""))

```

Example usage:

```
> table(strsplit(readline(),""))
The definition of insanity is quoting the same phrase again and again and not expect despair.

    .  a  c  d  e  f  g  h  i  m  n  o  p  q  r  s  t  T  u  x  y
15  1 10  1  4  8  2  3  3 10  1 10  4  3  1  2  5  6  1  1  1  1

```

# Answer
> 5 votes
## Perl 5, 54 characters

```
map{$h{$_}++}split//,<>;print"$_ : $h{$_}\n"for keys%h

```

# Answer
> 5 votes
# JavaScript

1. **~~66~~ 53 bytes:**

```
prompt(a={}).replace(/./g,function(c){a[c]=-~a[c]}),a

```
2. **~~69~~ 56 bytes:**

```
b=prompt(a={});for(i=b.length;i--;){a[b[i]]=-~a[b[i]]};a

```
3. **~~78~~ 65 bytes:**

```
prompt().split('').reduce(function(a,b){return a[b]=-~a[b],a},{})

```

**N.B.:** In all cases deleted number of bytes refer to extra `console.log()` call which is pointless if run in the console. Big thanks to @imma for the great catch with `-~a[b]` and `prompt(a={})`. This definitely saved some more bytes.

# Answer
> 5 votes
# **Python 2, correctly (58)**

```
s=raw_input()
for l in set(s):print l+" : "+str(s.count(l))

```

**Output:**

```
python count.py
The definition of insanity is quoting the same phrase again and again and not expect despair.
  : 15
. : 1
T : 1
a : 10
c : 1
e : 8
d : 4
g : 3
f : 2
i : 10
h : 3
m : 1
o : 4
n : 10
q : 1
p : 3
s : 5
r : 2
u : 1
t : 6
y : 1
x : 1

```

# **Python 2, cheetah style (41)**

```
s=input()
print {l:s.count(l) for l in s}

```

**Output:**

```
python count.py
"The definition of insanity is quoting the same phrase again and again and not expect despair."
{' ': 15, '.': 1, 'T': 1, 'a': 10, 'c': 1, 'e': 8, 'd': 4, 'g': 3, 'f': 2, 'i': 10, 'h': 3, 'm': 1, 'o': 4, 'n': 10, 'q': 1, 'p': 3, 's': 5, 'r': 2, 'u': 1, 't': 6, 'y': 1, 'x': 1}

```

# Answer
> 5 votes
## Mathematica, 61 bytes

```
Map[{#[[1]], Length@#} &, Gather@Characters[Input[]]] // TableForm

```

It then pops up this dialog box,

and for the sample sentence, produces as output

# Answer
> 4 votes
## python 3, 49

Stealing idea from evuez

```
t=input()
for i in set(t):print(i,':',t.count(i))

```

input:

```
The definition of insanity is quoting the same phrase again and again and not expect despair.

```

output:

```
  :  15
. :  1
T :  1
a :  10
c :  1
e :  8
d :  4
g :  3
f :  2
i :  10
h :  3
m :  1
o :  4
n :  10
q :  1
p :  3
s :  5
r :  2
u :  1
t :  6
y :  1
x :  1

```

# Answer
> 4 votes
# JavaScript (~~69~~ 68 characters):

*Expects `s` to hold the string.*

```
_={};for(x in s)_[a=s[x]]=-~_[a];for(x in _)console.log(x+': '+_[x])

```

*This follows the new rules perfectly.*

**Note:** *This presumes a clean environment, with no custom properties on any standard object prototypes.*

**Edit:** 1 character less!

## Console output:

```
T: 1
h: 3
e: 8
 : 15
d: 4
f: 2
i: 10
n: 10
t: 6
o: 4
s: 5
a: 10
y: 1
q: 1
u: 1
g: 3
m: 1
p: 3
r: 2
x: 1
c: 1
.: 1

```

---

# Old answer (44 characters):

```
r={};[].map.call(s,function(e){r[e]=-~r[e]})

```

*This was valid before the rules changed.*

`r` contains the output.

# Answer
> 3 votes
# F# (66 59 49, 72 with prescribed formattting)

```
let f s=s|>Seq.countBy(id)|>Seq.iter(printfn"%A")

```

Output:

```
> f The definition of insanity is quoting the same phrase again and again and not expect despair.
(' ', 15)
('.', 1)
('T', 1)
('a', 10)
('c', 1)
('d', 4)
('e', 8)
('f', 2)
('g', 3)
('h', 3)
('i', 10)
('m', 1)
('n', 10)
('o', 4)
('p', 3)
('q', 1)
('r', 2)
('s', 5)
('t', 6)
('u', 1)
('x', 1)
('y', 1)

```

With the prescribed formatting, it becomes:

```
let f s=s|>Seq.countBy(id)|>Seq.iter(fun(a,b)->printfn"\"%c\" :  %d"a b)

```

# Answer
> 3 votes
# Haskell, 93

```
import Data.List
main=getLine>>=mapM(\s->putStrLn$[head s]++" : "++show(length s)).group.sort

```

# Answer
> 3 votes
**PowerShell (49)**

```
[char[]](read-host)|group|%{$_.Name+":"+$_.Count}

```

# Answer
> 3 votes
# Bash (20 15 characters)

```
 ptx -S.|uniq -c
 10                                        a
  1                                        c
  4                                        d
  8                                        e
  2                                        f
  3                                        g
  3                                        h
 10                                        i
  1                                        m
 10                                        n
  4                                        o
  3                                        p
  1                                        q
  2                                        r
  5                                        s
  6                                        t
  1                                        T
  1                                        u
  1                                        x
  1                                        y

```

ASCII encoding now supported

# Bash (23 characters):

```
xxd -p -c1|sort|uniq -c

  1 0a
 15 20
  1 2e
  1 54
 10 61
  1 63
  4 64
  8 65
  2 66
  3 67
  3 68
 10 69
  1 6d
 10 6e
  4 6f
  3 70
  1 71
  2 72
  5 73
  6 74
  1 75
  1 78
  1 79

```

ASCII formatting not supported

# Answer
> 3 votes
# C# (178 220 chars)

Based on @Spongeman's comment I changed it up a bit:

```
using C=System.Console;using System.Linq;class P{static void Main()
{C.WriteLine(string.Join("\n",C.ReadLine().GroupBy(x=>x)
.OrderBy(x=>x.Key).Select(g=>g.Key+":"+g.Count())));}}

```

---

```
Line breaks added for readability, my first feeble attempt at code golf! :)

class P {static void Main(){var d=new Dictionary<char,int>();
Console.ReadLine().ToList().ForEach(x=>{ if(d.ContainsKey(x))
{d[x]++;}else{d.Add(x,1);}});Console.WriteLine(string
.Join("\n",d.Keys.Select(x=>x+":" +d[x])));}}

```

# Answer
> 3 votes
# Sclipting, 19 characters

```
梴要⓶銻꾠⓷❸虛變梴❶⓺減負겠⓸⓸終丟

```

## Output

```
T:1
h:3
e:8
 :15
d:4
f:2
i:10
n:10
t:6
o:4
s:5
a:10
y:1
q:1
u:1
g:3
m:1
p:3
r:2
x:1
c:1
.:1

```

If you want the spaces around the `:`, change  to `긃똠`, making it 20 characters.

## Explanation

```
Get length of input string.
梴
Stack is now [ input, length ]
While {
要
    Get first character of string and push ":"
    ⓶銻꾠
    Stack is now [ length, input, firstchar, ":" ]
    Replace all occurrences of that character with empty string
    ⓷❸虛變
    Stack is now [ length, firstchar, ":", reducedinput ]
    Get the length of that, calculate difference to previous length, push "\n"
    梴❶⓺減負겠
    Stack is now [ firstchar, ":", reducedinput, newlength, diff, "\n" ]
    Move the input string and length back up, leaving output below it
    ⓸⓸
    Stack is now [ firstchar, ":", diff, "\n", reducedinput, newlength ]
                   `------------------------'                `-------'
                   Every iteration of the               The length provides
                   While loop generates                 the While loop's
                   a bit like this                      terminating condition
} End While
終
Discard the length which is now 0
丟

```

# Answer
> 3 votes
# Mathematica, ~~34~~ 29 bytes

Not sure why the other Mathematica answer is so complicated... ;)

```
Grid@Tally@Characters@Input[]

```

# Answer
> 3 votes
# Java 8, ~~273~~ ~~253~~ ~~249~~ ~~246~~ ~~239~~ 200 bytes

```
interface I{static void main(String[]a){int m[]=new int[999],i=0;for(int c:new java.util.Scanner(System.in).nextLine().getBytes())m[c]++;for(;++i<999;)if(m[i]>0)System.out.printf("%c: %d%n",i,m[i]);}}

```

-24 bytes thanks to *@Poke*.
-7 bytes thanks to *@OlivierGrégoire*.

**Explanation:**

Try it here.

```
interface I{                        // Class
  static void main(String[]a){      //  Mandatory main-method
    int m[]=new int[999],           //  Integer-array to count the occurrences
        i=0;                        //  Index-integer, starting at 0
    for(int c:new java.util.Scanner(System.in).nextLine().getBytes())
                                    //   Loop over the input as bytes:
      m[c]++;                       //    Increase the occurrence-counter of the char by 1
    for(;++i<999;)                  //   Loop over the array:
      if(m[i]>0)                    //    If the current character occurred at least once:
        System.out.print("%c: %d%n",//     Print with proper formatting:
         i,                         //      The character
         m[i]);}}                   //      and the occurrence-count

```

# Answer
> 3 votes
# JavaScript, ~~44~~ 37 bytes

```
s=>[...s].map(x=>o[x]=-~o[x],o={})&&o

```

---

## Try it

```
o.innerText=JSON.stringify((f=
s=>[...s].map(x=>o[x]=-~o[x],o={})&&o
)(i.value="The definition of insanity is quoting the same phrase again and again and not expect despair."));oninput=_=>o.innerText=JSON.stringify(f(i.value))
```

```
<input id=i><pre id=o></pre>
```

# Answer
> 2 votes
# Befunge 98 - 31 to 42 chars

This does not print the spaces, and only prints for characters in the string (once for each character, even duplicates). So an input of `aa` will produce an output of:

```
a:2
a:2

```

### 31 chars

```
~::1g1+\1p;,a.- 'g1,:',:@j`0:;#

```

---

The following seems to match almost exactly. It outputs only one time for each character, in the order they appear in the string. An input of `Bbaa` gives an output of

```
B:1
b:1
a:2

```

### 38 chars

```
~:1g' `j::1g1+\1p;,a.- 'g1,:',:@j`0:;#

```

---

The following prints the spaces exactly as in the output example. It also outputs every single ascii character's count, which, since it is not clearly specified, I'll say is valid.

### 42 chars

```
~:1g1+\1p;,a+1.- 'g1:,,:,," : ",:@j!`~':;#

```

# Answer
> 2 votes
## Powershell, 63

```
$a=@{};[char[]](read-host)|%{$a[$_]++};$a.Keys|%{"$_ :"+$a[$_]}

```

# Answer
> 2 votes
## Windows Command Script - 72 Bytes

```
set/p.=
:a
set/a\%.:~,1%=\%.:~,1%+1
set.=%.:~1%
%.%goto:b
goto:a
:b
set\

```

**Outputs:**

```
\=15 (space)
\.=1
\a=10
\c=1
\d=4
\e=8
\f=2
\g=3
\h=3
\i=10
\m=1
\n=10
\o=4
\p=3
\q=1
\r=2
\s=5
\T=7
\u=1
\x=1
\y=1

```

# Answer
> 2 votes
## J, 23 chars

```
(~.;"0+/@|:@=)/:~1!:1]1

```

Slightly different output format (line 2 is stdin):

```
   (~.;"0+/@|:@=)/:~1!:1]1
Mississippi
┌─┬─┐
│M│1│
├─┼─┤
│i│4│
├─┼─┤
│p│2│
├─┼─┤
│s│4│
└─┴─┘

```

# Answer
> 2 votes
C#

```
string str = Console.ReadLine(); // Get Input From User Here
char chr;
for (int i = 0; i < 256; i++)
{
    chr = (char)i; // Use The Integer Index As ASCII Char Value --> Convert To Char
    if (str.IndexOf(chr) != -1) // If The Current Char Exists In The Input String
    {
        Console.WriteLine(chr + " : " + str.Count(x => x == chr)); // Count And Display
    }
}
Console.ReadLine(); // Hold The Program Open.

```

In Our Case, If The Input Will Be "**The definition of insanity is quoting the same phrase again and again and not expect despair.**"

The Output Will Be:

```
  : 15
. : 1
T : 1
a : 10
c : 1
d : 4
e : 8
f : 2
g : 3
h : 3
i : 10
m : 1
n : 10
o : 4
p : 3
q : 1
r : 2
s : 5
t : 6
u : 1
x : 1
y : 1

```

# Answer
> 2 votes
# J, 22 characters

```
(~.;"0+/@(=/~.))1!:1]1

```

Example:

```
   (~.;"0+/@(=/~.))1!:1]1
The definition of insanity is quoting the same phrase again and again and not expect despair.
+-+--+
|T|1 |
+-+--+
|h|3 |
+-+--+
|e|8 |
+-+--+
| |15|
+-+--+
|d|4 |
+-+--+
|f|2 |
+-+--+
|i|10|
+-+--+
|n|10|
+-+--+
|t|6 |
+-+--+
|o|4 |
+-+--+
|s|5 |
+-+--+
|a|10|
+-+--+
|y|1 |
+-+--+
|q|1 |
+-+--+
|u|1 |
+-+--+
|g|3 |
+-+--+
|m|1 |
+-+--+
|p|3 |
+-+--+
|r|2 |
+-+--+
|x|1 |
+-+--+
|c|1 |
+-+--+
|.|1 |
+-+--+

```

# Answer
> 2 votes
## C#: 129

This is Avivs answer but shorter:

```
var s=Console.ReadLine();for(int i=0;i<256;i++){var ch=(char)i;Console.Write(s.Contains(ch)?ch+":"+s.Count(c=>c==ch)+"\r\n":"");}

```

This is mine:

## C#: 103

```
foreach(var g in Console.ReadLine().OrderBy(o=>o).GroupBy(c=>c))Console.WriteLine(g.Key+":"+g.Count());

```

# Answer
> 2 votes
# Python 2 (90 chars)

```
import collections as c;print"\n".join("%s %s"%i for i in c.Counter(raw_input()).items())

```

Output when run on its own source:

```
  8
" 4
% 3
) 4
( 4
. 3
; 1
C 1
\ 1
_ 1
a 2
c 4
e 3
f 1
i 9
j 1
m 2
l 2
o 6
n 7
p 3
s 5
r 5
u 2
t 6
w 1

```

# Answer
> 2 votes
## GolfScript ~~30~~ 27

```
:x.|{.{=}+x\,,`': '\n]''+}/

```

Explanation:

```
:x #Assign the input string to a variable x
.| #Copy the input string, and then OR it with itself to get the unique characters

```

Now, for each distinct character, we will perform the `{.{=}+x\,,``': '\n]''+}` block. For example, for the first iteration, the character will be 'T'.

```
.{=}+ #Generate the equality checking block.  {'T'=} is left on the stack
x #Put the input string on the stack.
\ #Flip the top elements  So the stack is now the input strick followed by the equality checking block.
, #Filter the input string by the equality checking block.
, #Count the number of equal characters.
`': '\n #Format the string and add a newline character
] #Collect the elements into an array
''+ #Convert the array into a string

```

# Answer
> 2 votes
# newLISP - 76 characters

```
(bayes-train(explode(read-line))'D)(map(fn(f)(println(f 0) ": "(f 1 0)))(D))

```

Reads from keyboard, builds a Bayes-trained context namespace, then outputs entries. It's hard to golf with the handicap of readable function names... :)

# Answer
> 2 votes
**Scala, 64 chars**

```
readLine.groupBy(y=>y).foreach(g=>println(g._1+" : "+g._2.size))

```

# Answer
> 2 votes
# J, 17 bytes

(Outputs the result exactly in the expected format.)

```
({.,': ',".@#)/.~

```

Example:

```
      (({.,': ',":@#)/.~) 'The definition of insanity is quoting the same phrase again and again and not expect despair.'
T: 1
h: 3
e: 8
...

```

## Shorter alternatives:

9 bytes:

```
  ({.;#)/.~

  (({.;#)/.~) 'The definition of insanity is quoting the same phrase again and again and not expect despair.'
┌─┬──┐
│T│1 │
├─┼──┤
│h│3 │
├─┼──┤
│e│8 │
...

```

7 bytes:

```
      ~.;#/.~

      (~.;#/.~)'The definition of insanity is quoting the same phrase again and again and not expect despair.'
┌──────────────────────┬───────────────────────────────────────────────┐
│The dfintosayqugmprxc.│1 3 8 15 4 2 10 10 6 4 5 10 1 1 1 3 1 3 2 1 1 1│
└──────────────────────┴───────────────────────────────────────────────┘

```

Here the output is a list of characters (i.e. string) and a list of occurrences of the corresponding characters.

# Answer
> 2 votes
# Pascal (FPC), 145 bytes

```
var c:char;a:array[0..255]of word;i:word;begin repeat read(c);Inc(a[ord(c)])until eof;for i:=0to 255do if a[i]>0then writeln(chr(i),':',a[i])end.

```

Try it online!

# Answer
> 2 votes
# SuperMarioLang, 449 bytes

```
     >++++)
    >^====+  (+++<
>,[!^= (< +======"          *-<
"==#=  =" +      )      ======"
   >%+>[!%+      )         >&[!
   "====# +            )   "==#=====================
!        <>+++(-[!))+(%> [!!
#================#====="==##
                          >          (((++*)+*)&+)[!
                          "========================#
                       !)*-&)*-&)*-&)*-&.(((:)).(.(<
                       #==========================="

```

Try it online!

# Answer
> 2 votes
# Stax, 5 bytes

```
═#8¼K

```

Run and debug it

# Answer
> 2 votes
# Python, 46 bytes

```
s=input()
for c in{*s}:print(c,":",s.count(c))

```

Attempt it Online!

# Answer
> 2 votes
# Pip `-S`, 16 bytes

```
{[a':aNy]}MUQ Yq

```

Attempt This Online!

### Explanation

```
{[a':aNy]}MUQ Yq
               q  ; Read a line of stdin
              Y   ; Yank it into the global variable y
           UQ     ; Remove duplicates
{        }M       ; Map this function to each character:
 [      ]         ;  Return a list containing:
  a               ;   The character
   ':             ;   A colon
     aNy          ;   The number of times the character appears in y
                  ; The result is a list of lists; the -S flag joins each sublist
                  ; on spaces and then joins the whole thing on newlines before
                  ; printing it

```

---

With looser I/O requirements, this could be **12 bytes**:

```
_AE(_Na)MUQa

```

Attempt This Online!

# Answer
> 1 votes
## JavaScript, 80

```
  // 80
  t=prompt(n={});for(i=0;c=t[i++];)n[c]=-~n[c];for(k in n)console.log(k+': '+n[k])

  // 47 - wrong format, no prompt
  for(i in a=t.split('').sort())console.log(a[i])

```

# Answer
> 1 votes
# Smalltalk, 71

```
Stdin nextLine asBag valuesAndCountsDo:[:c :n|(c,' : ')print.n printNL]

```

# Answer
> 1 votes
# Swift 3: ~~122~~ ~~120~~ 118 chars

```
_=readLine()!.characters.reduce([Character:Int]()){var r=$0;r[$1]=($0[$1] ?? 0)+1;return r}.map{print("\($0): \($1)")}

```

After running, it waits for user input.

## Input

> The definition of insanity is quoting the same phrase again and again and not expect despair.

## Result

```
p: 3
n: 10
.: 1
f: 2
o: 4
u: 1
q: 1
d: 4
t: 6
x: 1
a: 10
i: 10
T: 1
m: 1
r: 2
c: 1
s: 5
e: 8
 : 15
g: 3
y: 1
h: 3

```

## Explanation

* `_=` is necessary otherwise you'll get a warning: `result of call to 'map' is unused`
* removing whitespace from `($0[$1] ?? 0)` will result in an error, because swift recognizes `?` as an optional chaining operator.

Thanks to @ais523 for pointing out that there are too many whitespace characters left

# Answer
> 1 votes
# Tcl, 77 bytes

```
lmap c [split [gets stdin] ""] {dict inc D $c}
dict ma k\ v $D {puts $k:\ $v}

```

Try it online!

# Answer
> 1 votes
# C (gcc), 115 109 bytes

-6 bytes from @ceilingcat

```
a[256];main(c,v)char**v;{for(;--c;)for(;*v[c];)a[*v[c]++]++;for(;c<256;)a[++c]&&printf("%c :  %d\n",c,a[c]);}

```

Try it online!

Takes input as command line argument.

# Answer
> 1 votes
# Japt, 12 bytes

```
q
â ®+S+Uè¥Z

```

Try it online!

## Explanation:

```
q
â ®+S+Uè¥Z
            | Set U to:
q           |   Input, split into an array of chars
â           | Return all unique items in U
  ®         | Map through the items; Z = iterative item
   +S+      |   Z + " " +
      Uè¥Z  |   Number of times where Z appears in U

```

# Answer
> 1 votes
# Python 3, 46 bytes

```
i=input()
for c in{*i}:print(c,':',i.count(c))

```

Try it online!

# Answer
> 1 votes
# Add++, 35 bytes

```
D,g,@@#,€=b+": "$J
D,f,@,qdA€gBcBJn

```

Try it online!

Defines a function `f`, which takes the input as an argument, and returns the complete formatted string.

## Explanation

```
D,g,		; Define a helper function, g
	@@#,	;   that takes 2 arguments		Stack: ['l' 'Hello World']
	€=	; Compare each letter to argument	Stack: [[0 0 1 1 0 0 0 0 0 1 0]]
	b+	; Sum					Stack: [3]
	": "$	; Prepend ': '				Stack: [': ' 3]
	J	; Join together				Stack: [': 3']
		; Return: ': 3'

D,f,		; Define a main function, f
	@,	;   that takes 1 argument		Stack: ['Hello World']
	qd	; Push two copies of unique letters	Stack: [['H' 'e' 'l' 'o' ' ' 'W' 'r' 'd'] ['H' 'e' 'l' 'o' ' ' 'W' 'r' 'd']]
	A	; Push the argument			Stack: [['H' 'e' 'l' 'o' ' ' 'W' 'r' 'd'] ['H' 'e' 'l' 'o' ' ' 'W' 'r' 'd'] 'Hello World']
	€g	; Apply g to each unique letter		Stack: [['H' 'e' 'l' 'o' ' ' 'W' 'r' 'd'] [': 1' ': 1' ': 3' ': 2' ': 1' ': 1' ': 1' ': 1']]
	Bc	; Zip together				Stack: [['H' ': 1'] ['e' ': 1'] ['l' ': 3'] ['o' ': 2'] [' ' ': 1'] ['W' ': 1'] ['r' ': 1'] ['d' ': 1']]
	BJn	; Join all togther, then with newlines
		; Return the full string

```

# Answer
> 1 votes
# JavaScript (Node.js), 64 bytes

```
e=>(d={},e.replace(/\S/g,e=>d[e]=d[e]+1||1),[Object.entries(d)])

```

Try it online!

# JavaScript (Node.js), 59 bytes

```
e=>(d={},[...e].map(e=>d[e]=d[e]+1||1),[Object.entries(d)])

```

Try it online!

# Answer
> 1 votes
# Oracle SQL, 103 bytes

```
select substr(x,level,1),count(*)from t connect by level<=length(x)group by substr(x,level,1)order by 1

```

Test in SQL\*PLus

```
SQL> set pages 100
SQL> set heading off
SQL> with t(x) as (select 'The definition of insanity is quoting the same phrase again and again and not expect despair.' from dual)
  2  select substr(x,level,1),count(*)from t connect by level<=length(x)group by substr(x,level,1)order by 1
  3  /

              15
    .          1
    T          1
    a         10
    c          1
    d          4
    e          8
    f          2
    g          3
    h          3
    i         10
    m          1
    n         10
    o          4
    p          3
    q          1
    r          2
    s          5
    t          6
    u          1
    x          1
    y          1

    22 rows selected.

```

# Answer
> 1 votes
# Pip, 48 bytes

```
a:qFi32,128{b:0Fj,#a{a@jQ Ci?++bx}b?P Ci.":".bx}

```

I assume you meant printable ascii

Try it online!

# Answer
> 1 votes
# Julia 1.0, 53 bytes

```
s=readline()
Set(s).|>c->println(c,": ",sum(==(c),s))

```

Try it online!

# Answer
> 1 votes
# Stax (31 bytes)

```
âpWhuÉñ♫∩Ω╝YT>ⁿë╘Æ↨»╧óPÜ≤♪Ñû1♫à

```

Try it online here: https://staxlang.xyz/#p=837057687590a40eefeabc59543efc89d49217afcfa2509af30da596310e85&a=1

It has some limitations. No uppercase letters, and it shows all letters, even if they have zero occurences

Unpacked version:

```
0]6{c+}*,""/{|3b@^&FVw""/{[cp':p|3@PF
^a      ^b  ^c      ^d

```

Section A prepares a list to put the values in. Section B Gets user input. Section C counts letters, and section D outputs the result

# Answer
> 1 votes
# Japt `-R`, 9 bytes

```
ü ®Î+S+Zl

```

Try it

# Answer
> 1 votes
# Vyxal, 11 bytes

```
Ċ⟑`%: %`$%,

```

Try it Online!

# Answer
> 1 votes
# Excel, 78 bytes

```
=LET(c,CHAR(ROW(1:255)),q,LEN(A1)-LEN(SUBSTITUTE(A1,c,)),FILTER(c&": "&q,q>0))

```

Input is in cell `A1`. Output is wherever the formula is.

* `LET(~)` stores values as variables that can be referenced later. The last term is the output.
* `c,CHAR(ROW(1:255))` stores the extended ASCII table as `c`.
* `q,LEN(A1)-LEN(SUBSTITUTE(A1,c,))` stores a list `q` of how much shorter the input would be if you removed each ASCII character in turn.
* `FILTER(c&": "&q,q>0)` combines `c` and `q` into the desired output format and then filters the list to just show those that actually appear in the input.

# Answer
> 1 votes
# PowerShell Core, 42 bytes

```
$input|% t*y|group|%{$_.Name+":"+$_.Count}

```

Try it online!

Converts the input into an array of characters
Group them and builds a string like `<char>:<count>` for each of them

# Answer
> 1 votes
# Arturo, 41 bytes

```
loop tally input""[x,y]->print~"|x|: |y|"

```

# Answer
> 1 votes
# JavaScript (Node.js), 50 bytes

Heavily inspired by @Shaggy 's work.
Would be **34 bytes** if it were acceptable to have an unwanted string `[Function: g]` contained in the output ( by having `&&g` at the end instead of `&&Object.entries(g)` ).

```
s=>[...s].map(g=c=>g[c]=-~g[c])&&Object.entries(g)

```

Try it online!

# Answer
> 0 votes
# 05AB1E, 10 bytes

```
ÙvyD¹s¢‚})

```

Try it online!

> The definition of insanity is quoting the same phrase again and again and not expect despair.

```
[['T', 1], ['h', 3], ['e', 8], [' ', 15], ['d', 4], ['f', 2], ['i', 10], ['n', 10], ['t', 6], ['o', 4], ['s', 5], ['a', 10], ['y', 1], ['q', 1], ['u', 1], ['g', 3], ['m', 1], ['p', 3], ['r', 2], ['x', 1], ['c', 1], ['.', 1]]

```

# Answer
> 0 votes
# Factor, 47 bytes

```
readln histogram [ "%c %d\n"printf ] assoc-each

```

Try it online!

# Answer
> 0 votes
# Pascal, 208 B

See also Free Pascal. This is a *complete* `program` according to ISO standard 10206 “Extended Pascal” though. Note, this `program` does not count newlines. The variable `input` possesses the built-in data type `text`, which automatically converts any newline indicator (sometimes it’s CR, sometimes LF, sometimes CR+LF, other times something completely differently) into a single space character (`' '`). In order to distinguish between a space character as part/payload of a line vs. a space character *terminating* a line you’ll have to query `EOLn`.

```
program p(input,output);var c:char;s:array[char]of integer value[otherwise 0];begin while not EOF do begin read(c);s[c]:=s[c]+ord(not EOLn)end;for c:=chr(0)to maxChar do if 0<s[c]then writeLn(c:2,s[c]:9)end.

```

Ungolfed and annotated version:

```
program characterCount(input, output);
    var
        c: char;
        spreadsheet: array[char] of integer value [otherwise 0];
    begin
        { `EOF` is shorthand for `EOF(input)`. }
        while not EOF do
        begin
            { `read(c)` is shorthand for `read(input, c)`. }
            read(c);
            { If we are `read`ing from a `text` file like `input`,
              newlines are converted to a single space character.
              This is avoiding the drama of LF vs. CR vs. CR+LF.
              Therefore we’ll need to check `EOLn` so we aren’t
              counting line-terminating spaces (the value of `c`). }
            spreadsheet[c] := spreadsheet[c] + ord(not EOLn)
        end;

        { Note, in Pascal `for`-loop limits are inclusive.
          The constant `maxChar` is introduced in Extended Pascal. }
        for c := chr(0) to maxChar do
        begin
            if 0 < spreadsheet[c] then
            begin
                writeLn(c:2, spreadsheet[c]:9)
            end
        end
    end.

```

See also RosettaCode’s *Letter frequency* task.

# Answer
> 0 votes
# Thunno 2 `N`, 4 bytes

```
ƈıðj

```

Attempt This Online!

Uses  as the separator, like a lot of the other answers.

# Thunno 2 `N`, 6 bytes

```
ƈı`: j

```

Attempt This Online!

Uses `:`  as the separator, like the challenge asks.

#### Explanation

```
ƈıðj  # Implicit input
ƈ     # Produce a list of [item, count] pairs for
      # each unique character in the input string
 ı    # Map over this list of pairs:
  ðj  #  Join the pair by a space
      # Implicit output, joined by newlines

ƈı`: j  # Implicit input
ƈı      # As above
  `: j  #  Join the pair by ": "
        # Implicit output, joined by newlines

```

# Answer
> 0 votes
# Vyxal `j`, 20 bitsv1, 2.5 bytes

```
ĊvṄ

```

Try it Online!

Given that any character can be used, I figured I'd add an answer that doesn't have strict IO.

## Explained

```
ĊvṄ
Ċ   # Counts of characters
 vṄ # each joined on spaces

```

# Answer
> 0 votes
# Clojure, 54 bytes

```
(doseq[[k v](frequencies(read-line))](println k": "v))

```

Try it online!

---
Tags: code-golf, string, counting
---


title: Counting Letters in a String

text:
# Question
Title: Counting Letters in a String
Write a program or function that takes in a string and outputs a count of each modern English alphabet letter in the string, case-insensitive.

Input: A string consisting of printable ASCII characters (code points 32-126).

Output: A list of pairs, where each pair consists of a letter and its count in the string. The list should be sorted in alphabetical order by letter. The list shall omit letters occurring zero times.

## Test Cases

```
Input: "hello world"
Output: [('d', 1), ('e', 1), ('h', 1), ('l', 3), ('o', 2), ('r', 1), ('w', 1)]

Input: "The quick brown fox jumps over the lazy dog"
Output: [('a', 1), ('b', 1), ('c', 1), ('d', 1), ('e', 3), ('f', 1), ('g', 1), ('h', 2), ('i', 1), ('j', 1), ('k', 1), ('l', 1), ('m', 1), ('n', 1), ('o', 4), ('p', 1), ('q', 1), ('r', 2), ('s', 1), ('t', 2), ('u', 2), ('v', 1), ('w', 1), ('x', 1), ('y', 1), ('z', 1)]

```

Code Golf Specifics:

Your goal is to write the shortest possible code in bytes that correctly solves the problem. Your code must be able to handle any valid input within the given constraints. Note that your code should treat uppercase and lowercase letters as equivalent.

Good luck!

# Answer
> 6 votes
# Vyxal, 4 bytes

```
ǍɽĊs

```

Try it Online!

**How it works**:

```
ǍɽĊs
Ǎɽ    Remove non-alphabetical chars and lowercase
  Ċ   Count of each element
   s  Sorted

```

# Answer
> 6 votes
# Python, 60 bytes

```
lambda s:{c:s.lower().count(c)for c in s.lower()if'`'<c<'{'}

```

Attempt This Online!

Returns a dictionary. Suggested by *@JonathanAllan*.

## Python, 70 bytes

```
lambda s:sorted((c,s.lower().count(c))for c in{*s.lower()}if'`'<c<'{')

```

Attempt This Online!

Returns a sorted list of tuples.

## Python, 75 bytes

```
lambda s:sorted({*zip(x:=[*filter(str.isalpha,s.lower())],map(x.count,x))})

```

Attempt This Online!

Returns a sorted list of tuples.

#### Commented

```
lambda s: sorted(          # Define an anonymous function which takes a string, s,
                           # and returns a sorted version of the following:
  (c, s.lower().count(c))  #  a tuple of the character, c, and its count
                           #  in the lowercase version of s
  for c in {*s.lower()}    #  for each character, c, in the lowercase version of s uniquified
  if '`' < c < '{' )       #  but only keep it if it is between the characters
                           #  '`' (right before 'a') and '{' (right after 'z')
                           #  i.e., it's alphabetic

```

```
lambda s: sorted(          # Define an anonymous function which takes a string, s,
                           # and returns a sorted version of the following:
  {*zip(                   #  a uniquified version of two iterables zipped together:
    x := [*filter(         #   filter by
      str.isalpha,         #   is the character in the alphabet
      s.lower()            #   apply to a lowercase version of s
    )],                    #   and store in x
    map(x.count, x) )})    #   the counts of each character in x

```

# Answer
> 5 votes
# Java (JDK), ~~151~~ ~~142~~ 135 bytes

```
s->{var m=new java.util.TreeMap();for(var c:s.replaceAll("[^a-zA-Z]","").toCharArray())m.merge(c|=32,1,(a,b)->(int)a+(int)b);return m;}

```

Try it online!

Saved 15 bytes thanks to Kevin Cruijssen.

# Answer
> 5 votes
# jq, 66 bytes

```
ascii_downcase|reduce match("[a-z]";"g").string as $c({};.[$c]+=1)

```

Try it online!

`reduce` is just too good.

# Answer
> 5 votes
# C (gcc), ~~97~~ ~~94~~ 87 bytes

* -3 thanks to Unrelated String
* -7 thanks to c--

Uses uppercase as the challenge only states case-insensitive.

```
f(char*s){for(int a[96]={},i=64;i<90;)*s?a[*s++&95]++:a[++i]&&printf("%c:%d ",i,a[i]);}

```

Try it online!

Ungolfed:

```
f(char*s){
  for(int a[96]={},i=64;
      i<90;) // for all characters in string, then from 'A' to 'Z':
    *s? // done processing string?
      a[*s++&95]++: // no, uppercase letter and increment count
      a[++i]&&printf("%c:%d ",i,a[i]); // yes, print counts
}

```

# Answer
> 5 votes
# Perl 5 -n, 37 bytes

```
for$l(a..z){/$l/i&&say"$l ".s/$l//gi}

```

Try it online!

# Answer
> 5 votes
# Excel, ~~85~~ 82 bytes

Saved 3 bytes thanks to JvdV

```
=LET(c,CHAR(ROW(65:90)),q,LEN(A1)-LEN(SUBSTITUTE(UPPER(A1),c,)),FILTER(c&"="&q,q))

```

The `LET()` function allows you to assign variables to values and reference them by name later. Every term is a pair except the last which is the output.

* `c,CHAR(ROW(65:90))` creates an array of the strings `A` through `Z`.
* `q,LEN(a)-LEN(SUBSTITUTE(UPPER(a),c,))` creates an array of how many times each letter appears by measuring the length of the input vs. the length if we replace that letter with nothing. `SUBSTITUTE()` is case-sensitive so we transform the input to uppercase.
* `FILTER(c&"="&q,q)` combines the array of letters with the count of each character and then filter for just those where the count (`q`) was truthy (anything not zero).

# Answer
> 5 votes
# PowerShell Core, 62 bytes

```
$args-match'[a-z]'|%{"$_"|% *l*r}|group|%{,($_.Name,$_.Count)}

```

Try it online!

```
$args-match'[a-z]'        # For each character argument, exclude non letters characters
|%{"$_"|% *l*r}           # Converts to lowercase
|group                    # Groups them
|%{,($_.Name,$_.Count)}   # build pairs of letters and counts

```

# Answer
> 4 votes
# Retina 0.8.2, ~~38~~ 29 bytes

```
T`Llp`ll_
O`.
(.)\1*
$1, $.&¶

```

Try it online! Output includes trailing newlines. Saved 9 bytes thank to @FryAmTheEggman. Explanation:

```
T`Llp`ll_

```

Convert letters to lower case and delete all other printable ASCII.

```
O`.

```

Sort the characters.

```
(.)\1*
$1, $.&¶

```

Output the count of each letter.

Previous 38-byte version worked with any input, not just printable ASCII:

```
T`L`l
O`.
M!`([a-z])\1*
(.)\1*
$1, $.&

```

Try it online! Explanation:

```
T`L`l

```

Lowercase the input string.

```
O`.

```

Sort the characters.

```
M!`([a-z])\1*

```

Extract the runs of identical letters.

```
(.)\1*
$1, $.&

```

Output the count of each letter.

~~31~~ 30 bytes in Retina 1:

```
.
$L
O`.
L$`([a-z])\1*
$1, $.&

```

Try it online! Explanation:

```
.
$L

```

Lowercase the input.

```
O`.

```

Sort the characters.

```
L$`([a-z])\1*

```

For each run of identical letters...

```
$1, $.&

```

... output the count of each letter.

# Answer
> 4 votes
# JavaScript, 68 bytes

```
s=>s.toLowerCase(m={}).match(/[a-z]/g).sort().map(l=>m[l]=-~m[l])&&m

```

Try it:

```
f=s=>s.toLowerCase(m={}).match(/[a-z]/g).sort().map(l=>m[l]=-~m[l])&&m

;[
  'hello world',
  'The tuick brown fox jumps over the lazy dog'
].forEach(s=>console.log(f(s)))
```

## UPD 73 -\> 68

Thanks to Shaggy for the tips (one, two) to reduce bytes count

# Answer
> 4 votes
# 05AB1E, ~~9~~ 6 bytes

```
álÐ¢øê

```

Try it online!

Input as a list of characters.

**Alternative 6 bytes answer with input as a string:** (suggested by *@KevinCruijssen*)

```
ál{Åγø

```

Try it online!

*-3 thanks to @KevinCruijssen*

#### Explanation

```
á       # Filter for alphabetic characters only
 lÐ     # Convert to lowercase and triplicate
   ¢    # Count the occurences of each character
    øê  # Zip, sort, and uniquify

```

```
á       # Filter for alphabetic characters only
 l{     # Convert to lowercase and sort
   Åγ   # Run-length encode the string
     ø  # Zip

```

# Answer
> 4 votes
# Pascal (FPC), ~~185~~ ... 134 bytes

```
var c,d:char;s:string;i:word;begin;read(s);for c:=^to^do begin;i:=0;for d in upcase(s)do i+=ord(c=d);if i>0then writeln(c,i)end;end.

```

Try it online! (134b, courtesy of @michael-tkach)

~~150b~~ ~~155b~~ ~~160b~~ ~~161b~~ ~~162b~~ ~~185b~~

Iterates over the alphabet and the input string `s`, comparing chars `d` and `c`. The `for <char> in <string>` syntax was handy. Implemented some of the Pascal golfing tips.

# Answer
> 4 votes
# Pip, ~~21~~ 23 bytes

```
YSSLCaFiUQy@XL;Pi.(iNy)

```

How?

```
YSSLCaFiUQy@XL;Pi.(iNy)  : One arg; str
     a                   : First input
   LC                    : To lowercase
 SS                      : Sort
Y                        : Yank
      Fi                 : For i in
        UQy              : Unique values of y
           @XL           : Only lowercase alphabet characters
               P           : Print
                i          : Letter
                 .         : Concatenated with
                   iN      : Letter in
                     y     : Input

```

Try It Online!

# Answer
> 3 votes
## Mathematica (Wolfram Language), 34 bytes

```
KeySort@*LetterCounts@*ToLowerCase

```

TIO.run is in the comments below. Edited to save 4 bytes thanks to a suggestion from ZaMoC.

# Answer
> 3 votes
# Arturo, 34 bytes

```
$=>[match lower&{/\pL}|tally|sort]

```

Try it

# Answer
> 3 votes
# JavaScript (ES6), 82 bytes

Probably takes *a list of pairs* a bit too literally... ¯\\\_(ツ)\_/¯

```
s=>[...s.toLowerCase()].sort().join``.match(/([a-z])\1*/g).map(s=>[s[0],s.length])

```

Try it online!

# Answer
> 3 votes
# Charcoal, 15 bytes

```
⭆¹ΦＥβ⟦λ№↧θλ⟧§λ¹

```

Try it online! Link is to verbose version of code. Explanation:

```
    β           Predefined variable lowercase alphabet
   Ｅ            Map over letters
      λ         Current letter
     ⟦     ⟧    Make into tuple with
       №        Count of
          λ     Current letter in
         θ      Input string
        ↧       Lowercased
  Φ             Filtered where
            §λ¹ Count was nonzero
⭆¹              Pretty-print

```

# Answer
> 3 votes
# J9.4, 35 bytes

```
'\pL'(~.,:<@#/.~)@/:~@rxall tolower

```

# J903, 37 bytes

```
'[a-z]'(~.,:<@#/.~)@/:~@rxall tolower

```

Attempt This Online!

Explanation is the same, but the PCRE engine was updated which makes the regex 2 bytes shorter.

```
'\pL'(~.,:<@#/.~)@/:~@rxall tolower
                            tolower  NB. lowercase the input
'\pL'                 rxall          NB. match every letter
                  /:~@               NB. then sort
     (          )@                   NB. then invoke a monadic fork
            #/.~                     NB. count the occurrences of each letter
          <@                         NB. then box each result
      ~.                             NB. uniquify the matches
        ,:                           NB. stack matches on top of counts

```

# Answer
> 3 votes
# Thunno, \\$18\log\_{256}(96)\approx\\$ 14.82 bytes

```
UgAzsAqkztcsZZZUz:

```

Attempt This Online!

#### Explanation

```
U           # Lowercase
 gAzsAqk    # Alphabetic characters only
        zt  # Triplicate
cs          # Counts of each
  ZZ        # Zip
    ZU      # Uniquify
      z:    # Sort

```

# Answer
> 3 votes
# , 32 bytes

```
(u:97+i.26)(e.#[;"+1#.=/)tolower

```

Attempt This Online!

`u:97+i.26` A character vector of all lowercase letters.
`tolower` Input converted to lowercase.
`(u:97+i.26)(...)tolower` Apply inner function with lowercase alphabet as left argument and lowercased string as right argument.
`=/` Equality table.
`1#.` Sum each row. This gives a vector of length 26 with the count of each letter in the input.
`[;"+` Pair up each letter with its count.
`e.#` Only keep the pairs where the letter is an element of the input.

# Answer
> 3 votes
# Japt v2.0a0, ~~15~~ 13 bytes

```
v r\L ü ËÎ+DÊ

```

Try it

-2 by Shaggy

Outputs a list of “ab” strings where a is the character and b is the number of occurrences

## Japt, 7 bytes

```
ü ËÎ+DÊ

```

Try it

Doesn’t remove non-letters

Made on My iPhone

```
ü ËÎ+DÊ # input string
ü       # list of same characters grouped together
  Ë     # map each string of same char to:
   Î    #   the character
    +DÊ #   append length of group

```

# Answer
> 3 votes
# Jelly, 8 bytes

```
ŒlḟŒuṢŒr

```

Try it online!

At least slightly less boring than if I'd used `Øa`. Feels ever so vaguely beatable, still...

```
Œl          The lowercased input,
  ḟŒu       with elements of the uppercased input filtered out.
     ṢŒr    Sort and run-length encode.

```

# Answer
> 3 votes
## Pascal, ~~590~~ 358 bytes

This full `program` requires a processor supporting features of ISO standard 10206 “Extended Pascal”. Furthermore,

* the *implementation-dependent* behavior of the selection order in a `for … in` set member iteration statement must be *ascending*,
* the *implementation-defined* default `TotalWidth` for `integer`-type `write` arguments must be sufficiently large in order to leave some space between a character and the number, and
* the *implementation-defined* set of available characters contains both upper and lowercase characters.

The GPC (GNU Pascal Compiler) fulfills these conditions on an x86‑64 Linux system if compiling with the `‑‑extended-pascal` option.

```
program p(input,output);var c:char;f:array[char]of integer value[otherwise 0];begin while not EOF do begin read(c);c:=(c+'ABCDEFGHIJKLMNOPQRSTUVWXYZ')[index('abcdefghijklmnopqrstuvwxyz',c)+1];f[c]:=f[c]+1 end;for c in['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']do if 0<f[c]then writeLn(c,f[c])end.

```

Ungolfed:

```
program letterFrequency(input, output);
    var
        c: char;
        letterFrequency: array[char] of integer value [otherwise 0];
    begin
        while not EOF(input) do
        begin
            { `read(input, c)` is equivalent to `c := input^; get(input)`. }
            read(input, c);

            { There is no built-in “change case” function as Pascal does not
              guarantee the coexistence of lower and uppercase letters. The EP
              function `index(source, pattern)` returns the index of the first
              occurence of `pattern` in `source`. If `pattern` is not found,
              zero is returned. Remember, `string` indices are 1-based, thus
              add `1` to select the prepended value of `c`. }
            c := (c + 'ABCDEFGHIJKLMNOPQRSTUVWXYZ')
                [index('abcdefghijklmnopqrstuvwxyz', c) + 1];

            letterFrequency[c] := letterFrequency[c] + 1;
        end;

        for c in ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
            'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'] do
        begin
            if letterFrequency[c] > 0 then
            begin
                writeLn(c, letterFrequency[c]);
            end;
        end;
    end.

```

See also FreePascal implementation.

# Answer
> 3 votes
# Ruby, 48 bytes

```
->s{[*s.upcase.chars.tally.slice(*?A..?Z).sort]}

```

Attempt This Online!

# Answer
> 3 votes
## Common Lisp, 110 bytes

```
(lambda(s)(reduce(lambda(s c &aux(e(assoc c s)))(if e(prog1 s(incf(cdr e)))(acons c 1 s)))s :initial-value()))

```

The ungolfed version is:

```
(defun frequencies (string)
  (reduce (lambda (map char)
            (let ((entry (assoc char map)))
              (if entry
                  (prog1 map
                    (incf (cdr entry)))
                  (acons char 1 map))))
          string
          :initial-value nil))

```

For example:

```
> (frequencies "abcbad")
((#\d . 1) (#\c . 1) (#\b . 2) (#\a . 2))

```

# Answer
> 3 votes
# CJam, 19 bytes

```
el_'{,97>--$e`{W%}%

```

Try it online!

Returns strings in the form of `{char}{count}`

# Explanation

```
el_'{,97>--$e`{W%}% # a function taking an input string
el_      --         # remove all elements of the input which do not occur in
   '{,97>           # the character range lowercase a-z
           $        # sort
            e`      # run-length encode (1h1e2l as an example)
              {W%}% # to meet the output specification of {char}{count} and not {count}{char}
                    # we reverse each of the arrays in this sorted array

```

# Answer
> 3 votes
# Haskell, ~~75~~ 71 bytes

*-4 bytes thanks to Lynn*

```
f s=[(l,n)|(u,l)<-zip['A'..'Z']['a'..],n<-[sum[1|c<-s,l==c||u==c]],n>0]

```

Attempt This Online!

### Explanation

List comprehensions seem to be shorter than `map` and `filter`.

```
f s=

```

Define our function, `f`, which takes a string `s`.

```
zip['A'..'Z']['a'..]

```

Create a list of (uppercase letter, lowercase letter) tuples.

```
(u,l)<-___

```

For each uppercase letter `u` and lowercase letter `l` in that list...

```
,n<-sum[1|c<-s,l==c||u==c]

```

Let `n` be the number of characters `c` in `s` for which `c` equals one of `l` and `u`...

```
[(l,n)|____,n>0]

```

Return a list of tuples of `l` and the corresponding `n` where `n` is greater than `0`.

---

A solution using `toLower` from `Data.Char` comes in at **76 bytes**:

```
import Data.Char
f s=[(l,n)|l<-['a'..'z'],n<-[sum[1|c<-s,l==toLower c]],n>0]

```

# Answer
> 3 votes
# Julia 1.0, 51 bytes

```
~s=(x='A':'Z';y=@.sum(in(x=>x+32),s);(x.=>y)[y.>0])

```

Try it online!

* Thanks to MarcMush for the following:
    1. replace `sum(==(x),uppercase(s))` with `sum(in(x=>x+32),s)`
    2. replace Tuples with Pairs (e.g., `(a,b)` vs. `a=>b`).

## 54 byte solution

```
~s=(y='A':'Z'.|>x->x=>sum(in(x=>x+32),s))[@.last(y)>0]

```

Try it online!

## 55 byte solution

```
~s=[x=>y for x='A':'Z' for y=sum(in(x=>x+32),s) if y>0]

```

Try it online!

# Answer
> 2 votes
# Excel (ms365), 87 bytes

Formula in `B1`:

```
=LET(x,CHAR(ROW(97:122)),y,LEN(A1)-LEN(SUBSTITUTE(LOWER(A1),x,)),FILTER(HSTACK(x,y),y))

```

And 83 bytes if you don't want tupples, but a concatenation would do:

```
=LET(x,CHAR(ROW(97:122)),y,LEN(A1)-LEN(SUBSTITUTE(LOWER(A1),x,)),FILTER(x&"-"&y,y))

```

# Answer
> 2 votes
And any other shell that supports `${var,,}` to downcase.

# Bash, 35 bytes

```
grep -o [a-z]<<<${*,,}|sort|uniq -c

```

Try it online!

# Answer
> 2 votes
# Java 16+ (JDK), 166 bytes

Tried to use only inline stream as a different approach, but couldn't beat the best Java answer.

```
s->s.toLowerCase().chars().distinct().filter(e->e>96&e<123).sorted().mapToObj(e->new String[]{(char)e+"",s.toLowerCase().chars().filter(o->o==e).count()+""}).toList()

```

JDoodle (because TIO currently only supports Java up to v12)

# Answer
> 2 votes
# Scala, ~~112~~ 108 bytes

Saved 4 bytes thanks to the comment of @Kirill L.

---

Golfed version. Try it online!

```
def f(s:String)=s.toUpperCase.filter(c=>c>='A'&&c<='Z').groupBy(x=>x).mapValues(_.length).toSeq.sortBy(_._1)

```

Ungolfed version. Try it online!

```
import scala.collection.mutable

object Main {
  def main(args: Array[String]): Unit = {
    println(frequency("hello world"))
    println(frequency("The quick brown fox jumps over the lazy dog"))
  }

  def frequency(s: String): Seq[(Char, Int)] = {
    val uppercaseChars = s.toUpperCase
    val counts = mutable.Map.empty[Char, Int].withDefaultValue(0)

    uppercaseChars.foreach(c => {
      if (c >= 'A' && c <= 'Z') {
        counts(c) += 1
      }
    })

    counts.toSeq.sortBy(_._1)
  }
}

```

# Answer
> 1 votes
# Raku, 21 bytes

```
*.lc.comb(/<:L>/).Bag

```

Try it online!

* `.lc` converts the input string to lowercase.
* `.comb(/<:L>/)` produces a list of all non-overlapping matches for the regex `<:L>` (a letter) in that string.
* `.Bag` converts that list to a Bag, a set with multiplicity, which is also an associative mapping and thus allowed as a return value per comments added to the challenge.

# Answer
> 1 votes
# Pyth, 29 bytes

```
FNS{rzZI&<"`"N <N"{"(N /rzZN)

```

Try it online!

#### Explanation

Used a for loop `F` to iterate over the letters which are valid by **I&\<"\`"N \<N"{"** which checks if a letter in the string is within *backtick* and *open curly bracket*.

**rzZ** \- converts the input string in lower i.e. `input().lower()` in Python.

**S{** \- used to sort the string.

# Answer
> 1 votes
# Lua, 77 bytes

```
s=...for i=65,90 do c=s.char(i)_,n=s:upper():gsub(c,c)f=n>0 and print(c,n)end

```

Try it online!

```
s=...                        -- Take argument as input
for i=65,90 do
    c=s.char(i)              -- Get the char represented by charcode i
    _,n=s:upper():gsub(c,c)  -- n stores the number of occurrences of char c
    f=n>0 and print(c,n)     -- if n>0, print char/count pair
end

```

# Answer
> 1 votes
# , 56 bytes

```
\(s,a=el(strsplit(tolower(s),"")))table(a[a%in%letters])

```

Attempt This Online!

# Answer
> 1 votes
# Nibbles, 8.5 bytes (17 nibbles)

```
=~|.@`($\$a$~/$$,

```

Attempt This Online!

I could save 0.5 bytes by returning (count, letter) pairs instead of (letter, count).

### Explanation

There's probably a better way to do this.

```
=~|.@`($\$a$~/$$,$
    @               First line of stdin
   .                Map to each character:
     `($             Lowercase
  |                 Filter by this function:
        \$a          Is the character a letter?
=~                  Group and sort by:
           $         Each letter
                    We now have the lowercase letters from the input, grouped
                    by letter (giving a list of strings) and sorted
                    For each string of identical letters (implicit):
            ~        Return a tuple of:
             /$$      The first character of the string
                ,$    The length of the string

```

The `/ ... $` idiom used in `/$$` means "right-fold on the identity function," which yields the leftmost element of a list.

# Answer
> 1 votes
# Thunno 2, 4 bytes

```
ỊLƈṠ

```

Attempt This Online!

#### Explanation

```
ỊLƈṠ  # Implicit input
Ị     # Remove non-alphabets
 L    # Lowercase
  ƈ   # Counts
   Ṡ  # Sort
      # Implicit output

```

# Answer
> 1 votes
# JavaScript (Node.js), 116 bytes

I re-did this challenge differently by trying to do the "lowering case" and "filtering special characters" parts only by messing with the ASCII codes.
It has become quite long for a JS solution, but now i can legitimate the use of the fun `Object.entries(...)` because i'm forced to use it for the `sort` part :)

```
s=>[...Buffer(s)].map(g=c=>(c=(c-64)%32+96)>96&c<123?g[c=String.fromCharCode(c)]=-~g[c]:0)&&Object.entries(g).sort()

```

Try it online!

# Answer
> 0 votes
# Clojure, 47 bytes

```
#(frequencies(re-seq #"[a-z]"(.toLowerCase %)))

```

Try it online!

Returns a Map as allowed by OP in the comments. To obtain a sorted colllection this should be additionally wrapped with `sort`.

# Answer
> 0 votes
# Racket -- 180 bytes

```
#!racket
(let([s hash-set])(foldl(λ(c a)(if(hash-has-key? a c)(s a c(+ 1(hash-ref a c)))(s a c 1)))#hasheq()(map char-downcase(filter char-alphabetic?(string->list(read-line))))))

```

Try it online!

---

## Explanation

This program returns a hash table of key-value pairs. The keys in the hash table are the characters and the values are the number of occurences in the string.

Characters are represented by a `#\` prefix. So the string "Apple" can be thought of as:

```
(display "Apple")
(display (string #\A #\p #\p #\l #\e))

```

The pseudo-code of my answer (algorithm?) is:

1. Read user input.
2. Filter only the alphabetic characters.
3. Convert all left-over characters into lowercase.
4. Iterate left-to-right using a hash table.
    1. If the hash table has the character as a key, increment the key's value.
    2. Otherwise, add a new key representing the character and set the value to 1.
5. Return the resulting hash table.

```
#lang racket

(foldl (lambda (char acc)
         (if (hash-has-key? acc char)
             (hash-set acc char (add1 (hash-ref acc char)))
             (hash-set acc char 1)))
       #hasheq()
       (map char-downcase
            (filter char-alphabetic?
                    (string->list (read-line)))))

```

---
Tags: code-golf, string, array
---


# Question
Title: Integer goes back and forth through time
**Input:**

An integer.

**Output:**

1. First convert the integer to it's equivalent Roman Numeral.
2. Then convert each capital letter of that Roman Numeral to their ASCII/UNICODE decimal value.
3. And output the sum of those.

**Example:**

```
1991 -> MCMXCI -> 77+67+77+88+67+73 -> 449
^ input                                ^ output

```

***Roman Numerals:***
Here is a perhaps useful Roman Numeral Converter.

**Challenge rules:**

* Standard Roman Numeral rules are applied, so no alternative forms like `IIII` or `VIIII` instead of `IV` and `IX`.\*
* The Macron lines above the Roman Numerals past 1,000 are `¯` (UNICODE nr. 175). So one line counts as `+175` and two as `+350`.
* You are allowed to use any kind of input and output type, as long as it represents the integers.
* The test cases will be in the range of `1 - 2,147,483,647`.

* Roman Numeral rules (quote from Wikipedia):

> Numbers are formed by combining symbols and adding the values, so `II` is two (two ones) and `XIII` is thirteen (a ten and three ones). Because each numeral has a fixed value rather than representing multiples of ten, one hundred and so on, according to position, there is no need for "place keeping" zeros, as in numbers like 207 or 1066; those numbers are written as `CCVII` (two hundreds, a five and two ones) and `MLXVI` (a thousand, a fifty, a ten, a five and a one).
>
> Symbols are placed from left to right in order of value, starting with the largest. However, in a few specific cases, to avoid four characters being repeated in succession (such as `IIII` or `XXXX`), subtractive notation is often used as follows:
>
> * `I` placed before `V` or `X` indicates one less, so four is `IV` (one less than five) and nine is `IX` (one less than ten)
> * `X` placed before `L` or `C` indicates ten less, so forty is `XL` (ten less than fifty) and ninety is `XC` (ten less than a hundred)
> * `C` placed before `D` or `M` indicates a hundred less, so four hundred is `CD` (a hundred less than five hundred) and nine hundred is `CM` (a hundred less than a thousand)
> For example, `MCMIV` is one thousand nine hundred and four, 1904 (`M` is a thousand, `CM` is nine hundred and `IV` is four).
>
> Some examples of the modern use of Roman numerals include:
> 1954 as `MCMLIV`; 1990 as `MCMXC`; 2014 as `MMXIV`
> SOURCE

**General rules:**

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code.
* Also, please add an explanation if necessary.

**Test cases:**

```
100          ->   67
1            ->   73
4            ->   159
22           ->   322
5000         ->   261
2016         ->   401
1000000000   ->   427
1991         ->   449
9999         ->   800
1111111111   ->   2344
2147483647   ->   5362

```

# Answer
> 4 votes
# Mathematica, 181 173 166 151 bytes

## Golfed

```
(q=Select[ToCharacterCode@#,64<#<99&]&/@StringSplit[RomanNumeral[#],"_"];p=PadLeft;l=Length;Total[p[q,4]+p[{350,350*Mod[l@q,2],175,0}[[-l@q;;]],4],2])&

```

## Ungolfed

```
(
q = Select[
     ToCharacterCode@#,
     64<#<99&
    ]&/@StringSplit[RomanNumeral@#,"_"];
p=PadLeft;
l=Length;
Total[
   p[q,4]+
   p[{350,350*Mod[l@q,2],175,0}[[-l@q;;]],4]
   ,2]
)&

```

Mathematica's `RomanNumeral` implementation gives (IX)CMXCIX for 9999, and so the program returns 971 for that number.

As written, a roman numeral of the type ((...))(...)... returns a nested list of the ASCII codes for the roman numerals of length 4, ((...))... returns a list of length 3, (...)... returns a list of length 2, and ... returns a list of length 1. The final line converts those rules into the appropriate number of macrons for each section of the list, adds those macrons in, and then sums the entire nested list to return the output.

# Answer
> 10 votes
# Python 3, ~~281~~ ~~278~~ ~~273~~ 269 bytes

My first attempt at codegolf, here we go. Tried to do it without looking at the linked question, so it's probably terrible :)

```
def f(n):d=len(str(n))-1;l=10**d;return 0if n<1else(n<l*4and[73,88,67,77,263,242,252,438,417,427][d]+f(n-l))or(l<=n//9and[161,155,144,340,505,494,690,855,844][d]+f(n-9*l))or(n<l*5and[159,164,135,338,514,485,688,864,835][d]+f(n-4*l))or[86,76,68][d%3]+(d//3*175)+f(n-5*l)

```

8 bytes smaller, thanks to Gábor Fekete

Ungolfed:

```
def f(n):
d = len(str(n)) - 1 # number of digits minus one
l = 10 ** d         # largest power of 10 that is not larger than parameter
if n == 0:
    return 0
elif n < 4 * l: # starts with X, C, M, ...
    return [
        ord('I'),
        ord('X'),
        ord('C'),
        ord('M'),
        ord('X') + 175,
        ord('C') + 175,
        ord('M') + 175,
        ord('X') + 350,
        ord('C') + 350,
        ord('M') + 350
    ][d] + f(n - l)
elif n // 9 * 10 >= 10 * l: # starts with IX, XC, ...
    return [
        ord('I') + ord('X'),
        ord('X') + ord('C'),
        ord('C') + ord('M'),
        ord('M') + ord('X') + 175,
        ord('X') + ord('C') + 350,
        ord('C') + ord('M') + 350,
        ord('M') + ord('X') + 525,
        ord('X') + ord('C') + 700,
        ord('C') + ord('M') + 700
    ][d] + f(n - 9*l)
elif n < 5 * l: # starts with IV, XL, CD, ...
    return [
        ord('I') + ord('V'),
        ord('X') + ord('L'),
        ord('C') + ord('D'),
        ord('M') + ord('V') + 175,
        ord('X') + ord('L') + 350,
        ord('C') + ord('D') + 350,
        ord('M') + ord('V') + 525,
        ord('X') + ord('L') + 700,
        ord('C') + ord('D') + 700
    ][d] + f(n - 4 * l)
else: # starts with V, L, D, ...
    return [
        ord('V'),
        ord('L'),
        ord('D'),
        ord('V') + 175,
        ord('L') + 175,
        ord('D') + 175,
        ord('V') + 350,
        ord('L') + 350,
        ord('D') + 350
    ][d] + f(n - 5 * l)

```

# Answer
> 3 votes
# Mathematica, 198 bytes

```
Tr[Tr@Flatten[ToCharacterCode/@#]+Length@#*Tr@#2&@@#&/@Partition[Join[SplitBy[Select[Characters@#/."\&"->1,MemberQ[Join["A"~CharacterRange~"Z",{1}],#]&],LetterQ]/. 1->175,{{0}}],2]]&@RomanNumeral@#&

```

Unfortunately, the builtin doesn't help here much, though I'm sure this can be golfed far more.

Note: Evaluates `9999 -> 971` as per here.

# Answer
> 3 votes
# Ruby, 188 bytes

An adaptation based on my old Ruby answer for Roman numeral conversion. Try it online!

```
f=->x,i=0{k=0;(x<t=1e3)?"CM900D500CD400C100XC90L50XL40X10IX9V5IV4I1".gsub(/(\D+)(\d+)/){v=$2.to_i;s=x/v;x%=v;($1*s).bytes.map{|c|k+=c==73&&i>0?77+175*~-i:c+175*i}}:k=f[x/t,i+1]+f[x%t,i];k}

```

# Answer
> 2 votes
## Batch, 373 bytes

```
@echo off
set/an=%1,t=0,p=1
call:l 73 159 86 161
call:l 88 164 76 155
call:l 67 135 68 144
call:l 77 338 261 340
call:l 263 514 251 505
call:l 242 485 243 494
call:l 252 688 436 690
call:l 438 864 426 855
call:l 417 835 418 844
call:l 427 0 0 0
echo %t%
exit/b
:l
set/ad=n/p%%10,p*=10,c=d+7^>^>4,d-=9*c,t+=%4*c,c=d+3^>^>3,d-=5*c,t+=%3*c+%2*(d^>^>2)+%1*(d^&3)

```

Works by translating each digit of the number according to a lookup table for the values 1, 4, 5 and 9. Uses `M(V)`, `M(X)`, `(M(V))` and `(M(X))`. If you prefer `(IV)`, `(IX)`, `((IV))` and `((IX))` then use `call:l 77 509 261 511` and `call:l 252 859 436 861` respectively.

# Answer
> 2 votes
# R, 115 bytes

So... I'm posting my solution because I find the question pretty interesting. I did my best with **R**'s capacities to deal with roman numbers without packages : you can only input numbers between `1` and `3899`, as the `as.roman`'s documentation explains.

That's why I cheated a bit by giving range between `1` to ~~`11`~~ `14` in the `for` loop : ~~it's the lenght of `as.roman(3899)`'s output (`MMMDCCCXCIX`)~~.
In fact, according to this website, the longest roman number is `MMDCCCLXXXVIII` (14 characters), which corresponds to `2888`.

Furthermore, you can't compute the `length` of the output of this function.

```
a=scan();v=0;for(i in 1:14){v=c(v,as.numeric(charToRaw(substring(as.character(as.roman(a)),1:14,1:14)[i])))};sum(v)

```

If anyone sees a solution to deal with the above problems, please feel free to comment.

# Answer
> 2 votes
# 05AB1E, 31 bytes

```
RƵêS£í.XÇεNĀi73¬Ć:Ny73Q-Ƶм*+]˜O

```

Try it online or verify all test cases.

**Explanation:**

05AB1E does have a builtin to convert from/to Roman numbers. Unfortunately, \\$M=1000\\$ is the highest supported Roman digit, so it would convert something like `9999` to `MMMMMMMMMCMXCIX`. Because of this we'll split the input into parts at the 1000 separators, and convert each part separately. This results in the following code:

```
R                       # Reverse the (implicit) input-integer
 Ƶê                     # Push compressed integer 334
   S                    # Convert it to a list of digits: [3,3,4]
    £                   # Split the reversed input into parts of that size
     í                  # Reverse each individual part back
      .X                # Convert it from an integer to a Roman number string
        Ç               # Convert each string to a list of codepoint integer
         ε              # Map over each list of codepoints:
          NĀi           #  If the (0-based) map-index is NOT 0:
             73         #   Push 73
               ¬        #   Push its first digit (without popping): 7
                Ć       #   Append its own head: 77
                 :      #   Replace all 73 with 77 (replaces all "I" with "M")
              y         #   Push the list of codepoints again
               73Q      #   Check for each if it's equal to 73 ("I")
             N    -     #   Subtract those checks from the (0-based) map-index
                   Ƶм*  #   Multiply each by the compressed integer 175
                      + #   Add those to the list of codepoints (with 73 as 77)
         ]˜             # After the if-statement and map: flatten the list
           O            # And sum this list of integers
                        # (after which it is output implicitly as result)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `Ƶм` is `175`.

# Answer
> 1 votes
## JavaScript (ES6), 183 bytes

```
f=(n,a=0)=>n<4e3?[256077,230544,128068,102535,25667,23195,12876,10404,2648,2465,1366,1183,329].map((e,i)=>(d=e>>8,c=n/d|0,n-=c*d,r+=c*(e%256+a*-~(i&1))),r=0)|r:f(n/1e3,a+175)+f(n%1e3)

```

Note: not only prefers `(IV)` to `M(V)`, but also prefers `(VI)` to `(V)M`; in fact it will only use M at the very start of the number.

# Answer
> 1 votes
# Python, 263 bytes

```
def g(m):x=0;r=[73,86,88,76,67,68,77,261,263,251,242,243,252,436,438,426,417,418,427,0,0];return sum([b%5%4*r[i+(i*1)]+((b==9)*(r[i+(i*1)]+r[(i+1)*2]))+((b==4)*(r[i+(i*1)]+r[i+1+(i*1)]))+((b in [5,6,7,8])*r[i+1+(i*1)])for i,b in enumerate(map(int,str(m)[::-1]))])

```

# Answer
> 1 votes
# Python 3, 315 bytes

```
def p(n=int(input()),r=range):return sum([f*g for f,g in zip([abs(((n-4)%5)-1)]+[t for T in zip([((n+10**g)//(10**g*5))%2for g in r(10)],[(n%(10**g*5))//(10**g*4)+max((n%(10**g*5)%(10**g*4)+10**(g-1))//(10**g),0)for g in r(1,10)])for t in T],[73,86,88,76,67,68,77,261,263,251,242,243,252,436,438,426,417,418,427])])

```

**Ungolfed version:**

```
def p(n=int(input()),r=range):
    return sum([f*g for f,g in zip(
        [abs(((n-4)%5)-1)]+
        [t for T in zip(
            [((n+10**g)//(10**g*5))%2for g in r(10)],
            [(n%(10**g*5))//(10**g*4)+max((n%(10**g*5)%(10**g*4)+10**(g-1))//(10**g),0)for g in r(1,10)]
        )for t in T],
        [73,86,88,76,67,68,77,261,263,251,242,243,252,436,438,426,417,418,427])])

```

**Explanation:** This version uses a different approach, it counts occurrences of roman numerals in the number.

`[abs(((n-4)%5)-1)]` is the number of **`I`**s in the roman numeral.

`[((n+10**g)//(10**g*5))%2for g in r(10)]` is the number of **`V,L,D,(V),(L),(D),((V)),((L)),((D))`**s in the number.

`[(n%(10**g*5))//(10**g*4)+max((n%(10**g*5)%(10**g*4)+10**(g-1))//(10**g),0)for g in r(1,10)]` is the number of the **`X,C,M,(X),(C),(M),((X)),((C)),((M))`**s in the number.

It then multiplies the occurrences with the value of the character and returns the sum of it.

# Answer
> 1 votes
I don't know if I understood the challenge correctly but I leave here a first contribution.

First I did a good research on Roman numerals on this site in Spanish and this other very interesting site in English

And then I dedicated myself to preparing the following code:

```
get_ascii_sum = functools.partial(lambda f, n: sum([ord(c) for c in f(n)]), lambda n: functools.reduce(lambda r, vg: (r[0] + vg[1] * vg[2], r[1] - vg[1] * vg[2]), zip((lambda v, s: (v, [s[i] * ((n + 10 ** i) // (10 ** i * 5)) % 2 for i in range(len(s))], [((n % (10 ** i * 5)) // (10 ** i * 4)) + max(((n % (10 ** i * 5) % (10 ** i * 4)) + 10 ** (i - 1)) // (10 ** i), 0) for i in range(1, len(s))]))(values, symbols)), (0, num)))

```

---
Tags: code-golf, integer, roman-numerals
---


title: Golf an LZW encoder

text:
# Question
Title: Golf an LZW encoder
Given an alphabet and a string, your job is to create the Lempel–Ziv–Welch compression of the string. Your implementation can either be a function with two parameters and a return value, or a full program that uses stdin and stdout.

## Input

* **The alphabet**, in the form of a string, from which you will have to create the initial dictionary: Each character should be mapped to its index in the string, where the first index is 0. You will be expanding this dictionary as you iterate through the algorithm.
* **The string** to be compressed.

## Output

* **The compressed string** in the form of dictionary keys. This must be an array of integers if you're creating a function, or printed integers separated by either whitespace or newline (and nothing else) if you're making a full program.

## Algorithm

After you have initialized the dictionary, the algorithm goes something like this:

* Find the longest string *W* in the dictionary that matches the current input.
* Emit the dictionary index for *W* to output and remove *W* from the input.
* Add *W* followed by the next symbol in the input to the dictionary.
* Repeat

## Examples

```
"ABC", "AABAACABBA"  ==>  [0,0,1,3,2,4,5]
"be torn", "to be or not to be"  ==> [3,4,2,0,1,2,4,5,2,6,4,3,2,7,9,1]

```

## Rules

* No use of external resources
* No predefined built-in functions or libraries of any kind that solves the problem for you.
* Fore!

# Answer
## GolfScript (52 51 chars)

```
{[\1/\{\.{.,3$<=},-1=.2$?@@,:L)[3$<]+@L>.}do;;]}:C;

```

Online demo

### Dissection

```
{  }:C;

```

is standard function boilerplate.

```
# Wrap the values we compute in an array
[
    # Stack: alphabet uncompressed-string
    # Split the alphabet from a string into an array of 1-char strings
    \1/\
    # Stack: dictionary uncompressed-string
    {
        # Stack: ... dictionary uncompressed-string-suffix
        # Find the dictionary elements which are prefixes of uncompressed-string-suffix
        \.{.,3$<=},
        # The last of them must be the longest by construction
        -1=
        # Stack: ... uncompressed-string-suffix dictionary prefix
        # Find the index of prefix in dictionary
        .2$?
        # Stack: ... uncompressed-string-suffix dictionary prefix index
        # Push index down the stack
        @@
        # Stack: ... uncompressed-string-suffix index dictionary prefix
        # Assign len(prefix) to L and append a 1-char-longer prefix to dictionary
        ,:L)[3$<]+
        # Fetch up the uncompressed-string-suffix and chop off the first L chars
        @L>
        # Stack: ... index dictionary' uncompressed-string-suffix'
        # Duplicate uncompressed-string-suffix' for the do-loop condition test
        .
    }do
    # Stack: index0 index1 ... indexN dictionary' ""
    # Pop the last two to leave just the indexes
    ;;
]

```
> 4 votes

# Answer
# Python (141 Characters)

```
def a(b,c,r=[]):
    if c:l,i,d=max((len(d),i,d) for i,d in enumerate(b) if c.find(d)==0)
    return a(list(b)+[c[:l+1]],c[l:],r+[i]) if c else r

```

Not golfed very small, but no chance of beating any of the golfscript solutions anyway.
> 3 votes

# Answer
# Racket/R5RS Scheme: 359 bytes

```
(define(l d i)(let*((h(make-hash))(s string->list)(r(λ(x)(hash-ref h x #f)))(i(s i))(s(let l((s 0)(d(s d)))(if(null? d)s
(and(hash-set! h(car d)s)(l(+ s 1)(cdr d)))))))(let l((i(cdr i))(c(r(car i)))(o'())(s s))(if(null? i)(reverse(cons c o))
(let*((q(cons(car i)c))(n(r q)))(if n(l(cdr i) n o s)(and(hash-set! h q s)(l(cdr i)(r(car i))(cons c o)(+ s 1)))))))))

```

Usage:

```
(l "ABC" "AABAACABBA")             ; ==> (0 0 1 3 2 4 5)
(l "be torn" "to be or not to be") ; ==> (3 4 2 0 1 2 4 5 2 6 4 3 2 7 9 1)

```
> 2 votes

# Answer
## PHP 220

implemented as a function

```
<? function l($d,$s){@$n=strlen;@$r=substr;$d=str_split($d);$o=[];while($s){$l=0;foreach($d as$k=>$v){$b=$n($v);if($b<=$n($s)&&!strncmp($s,$v,$b)&&$b>$l){$l=$b;$i=$k;}}$o[]=$i;$d[]=$r($s,0,$l+1);$s=$r($s,$l);}return $o;}

```
> 2 votes

# Answer
## **Perl, ~~188~~ ~~177~~ ~~156~~ ~~145~~ ~~137~~ 112**

```
sub l{($_,$s,@o)=@_;@d=split'';while($s){$s=~s/^$d[$_](.?)/push@o,$_;push@d,$&;$1/e&&last for reverse 0..$#d}@o}

```

i.e.

```
sub l {
    ($_,$s,@o)=@_;
    @d=split'';
    while($s){
        $s=~s/^$d[$_](.?)/push@o,$_;push@d,$&;$1/e
            && last for reverse 0..$#d
    }
    @o
}

```

Can be **109** if global `@o` is expected undefined or empty when entering sub. And yes, global variables are modified. Below is properly un-golfed version with lexicals.

```
use strict;
use warnings;

sub lzw {
    my ($alphabet, $string, @out) = @_;
    my @dict = split '', $alphabet;
    LOOP: while ($string) {
        for my $k (reverse 0..$#dict) {
            if ($string =~ s/^$dict[$k](.?)/$1/) {
                push @out, $k;
                push @dict, $&;
                next LOOP
            }
        }
        die "we shouldn't be here!\n"
    }
    return @out
}

print qq/@{[lzw("ABC", "AABAACABBA")]}\n/;
print qq/@{[lzw("be torn", "to be or not to be")]}\n/;

```

.

```
perl lzw.pl
0 0 1 3 2 4 5
3 4 2 0 1 2 4 5 2 6 4 3 2 7 9 1

```
> 2 votes

# Answer
# PHP: 176

Just making it return a function would require one byte less. It utilizes PHP arrays (`$d`)as Trie trees:

```
<? function l($d,$s){@$S=str_split;$o=[];$d=array_flip($S($d));foreach($S($s)AS$v){if(null===$t=@$d[$c.$v]){$d[$c.$v]=count($d);$o[]=$c;$c=$d[$v];}else$c=$t;}$o[]=$c;return$o;}

```

Usage:

```
print_r(l("ABC","AABAACABBA")) ; ==> array(0, 0, 1, 3, 2, 4, 5)

```
> 2 votes

# Answer
# SWI-Prolog, ~~313~~ 244

The list of alphabet is no longer reversed. And it uses `nth0` to brute force index + prefix pair.

```
b([],[]).
b([H|T],[[H]|R]):-b(T,R).
l(A,W,O):-b(A,B),r(B,W,O).
r(A,W,[I|T]):-m(A,W,I,E,0),append(E,R,W),(R=[N|_],!,append(E,[N],C),append(A,[C],B),r(B,R,T);T=[]).
m(A,W,I,E,N):-nth0(J,A,F),prefix(F,W),length(F,L),L>N,!,(m(A,W,I,E,L),!;I=J,E=F).

```

Usage:

```
l("be torn", "to be or not to be",O).
O = [3,4,2,0,1,2,4,5,2,6,4,3,2,7,9,1].

```

### Old version

**313 chars**

Working on a reversed list of alphabet, which is convenient when I need to add new alphabet, but it is more roundabout to get the index.

This should do less work than the 244 chars version, but more code.

```
b([],O,O).
b([H|T],O,A):-b(T,O,[[H]|A]).
l(A,W,O):-b(A,B,[]),r(B,W,O).
r(A,W,[I|T]):-m(A,W,I,E,_),I>=0,append(E,R,W),(R=[N|_],!,append(E,[N],C),r([C|A],R,T);T=[]).
m([],_,-1,_,0).
m([H|T],W,I,E,M):-prefix(H,W),!,length(H,L),m(T,W,J,F,N),(N>L,!,M=N,I=J,E=F;M=L,length(T,D),I=D,E=H).
m([_|T],W,I,E,M):-m(T,W,I,E,M).

```
> 2 votes

# Answer
# Wolfram Language(Mathematica), 245 bytes

Golfed version. Try it online!

```
f[a_,s_]:=(d=AssociationThread[Characters@a->Range[0,StringLength@a-1]];r={};i=1;c="";While[i<=StringLength@s,h=StringTake[s,{i}];n=c<>h;If[d~KeyExistsQ~n,c=n,r~AppendTo~d@c;AssociateTo[d,n->Max[Values@d]+1];c=h];i++];If[c!="",r~AppendTo~d@c];r)

```

Ungolfed version. Try it online!

```
LZWCompress[alphabet_String, input_String] := Module[
  {dict, current, next, result, i, ch},

  (* Initialize the dictionary with the alphabet *)
  dict = AssociationThread[Characters[alphabet] -> Range[0, StringLength[alphabet]-1]];
  result = {};
  current = "";
  i = 1;

  While[i <= StringLength[input],
    ch = StringTake[input, {i}];
    next = current <> ch;

    (* If the new string exists in the dictionary, update the current string *)
    If[KeyExistsQ[dict, next],
      current = next,

      (* Else, append the dictionary value of the current string to the result,
         add the new string to the dictionary, and reset the current string *)
      AppendTo[result, dict[current]];
      AssociateTo[dict, next -> Max[Values[dict]]+1];
      current = ch;
    ];

    i++;
  ];

  (* Handle the last remaining string *)
  If[current != "", AppendTo[result, dict[current]]];

  result
];

LZWCompress["ABC", "AABAACABBA"] //Print
LZWCompress["be torn", "to be or not to be"] //Print

```
> 2 votes

# Answer
### GolfScript, 53 characters

```
n%~\1/\{.,,{)1$<2$?}%{)},-1=.p@.@=,:^)2$[<]+\^>.}do;;

```

The input must be given as two lines, first alphabet, second string to compress. The second example can be tested online.
> 1 votes

# Answer
## **Postscript, ~~388~~ 267**

It's my Perl answer re-written, just for fun:

```
/lzw {
    10 dict begin
    /str exch def
    /alphabet exch def
    /concat
        {dup length 2 index length add string dup dup 4 index length
        5 -1 roll putinterval 0 4 -1 roll putinterval}
    def
    /push
        {1 index load dup length /_n exch def
        [exch aload pop _n 2 add -1 roll]def}
    def

    /dict [-1 alphabet length {
        1 add dup alphabet exch 1 getinterval exch
    } repeat pop] def
    [
    {
        str length 0 eq {exit} if
        dict length dup {
            1 sub dup
            dict exch get
            str exch anchorsearch
            {
                1 index
                dup length 0 ne {0 1 getinterval} if concat
                /dict exch push
                /str exch def
                exit
            } {pop} ifelse
        } repeat
    } loop
    ]

    end
} def

(ABC)(AABAACABBA) lzw
{10 string cvs print( )print} forall
(\n)print
(be torn)(to be or not to be) lzw
{10 string cvs print( )print} forall

```

and

```
gs -dBATCH -q lzw.ps
0 0 1 3 2 4 5
3 4 2 0 1 2 4 5 2 6 4 3 2 7 9 1

```

Procedure expects 2 strings on stack and returns an array. Not sure about quality of my Postscript, but with little help of 'binarization' (binary tokens), compression (LZW 4 bytes more efficient than Deflate) and encoding, it can be golfed to something like that:

```
/l<~J.+mR+f\'O00,h`aW[%a_[;,+b\+;Ei?VkM,`<7VO9Ho+MT&&IW4:>B/Jt:Fkp+9b5W"\IAS74n7,WEV`lsSZ&A6g1)4'7^,a$SAD@f9&15SkO))[/:$Z^e$4N0:?`F7fk8MV#<6.'Dr'AOkP"!5De'2kXm`>,I(@^ERI/e\Tneg#0M3_7tOQWJ$Y0n%F-#bWHFEC6hWX'hBaBu?;D~>/LZWDecode filter 500 string readstring pop cvx def

```

And that's **267** bytes procedure of pure ASCII code -- still not the longest of the answers :-)
> 1 votes

# Answer
# Extended BrainFuck: 490 bytes

I know I won't win here, but I love compression algorithms. It was fun writing, not too difficult and shorter than I imagined :)

```
{l[>>]}{k[<<]}{j&k +&l }{i]>>[-<<+>>]}{h,10-[22-[-}{g&k>>[->>]}{f>]3<[-3>+3<]}{e>+3>&l+<<&k}{d&k>[-3<+4>&l}{c 48+[-<+<+>>]<[.[-]<]10+.[-]}{a 10+<[->-[>+>>]>[+[-<+>]>+>>]5<]>[-]}{b 5<&k&f>>&g}192>&h 4<&j>>]<[-3<&k>+>&l>>+<]3<&g>>+[-<+>],10-]<[-<+>]<[->+>+<<]3>,32-[-5<&j 3>]5<&d 3>+&b 4>&h 6<&j 4>]<5<&d 4>+<&b>[-<+3>[->&e 3<&i 4<]<[->+<]4>+[-&e<<]>-[-<+>]3>&l<[-3>+4<&k<+3>&l<]3>[-3<+3>]4<&k+<[<<[-&i>-<]>[-<<[-4<+4>]4>-4<&a 4>+<&c<<[->+5>&l<+<&k 4<]>+[-<+&f 6>]>>&l<<[-<<]<<[-],10-]&a 3>&c

```

Usage:

```
$ bf ebf.bf < lzw.ebf > lzw.bf
$ bf lzw.bf <<eof
> ABC
> AABAACABBA
> eof
00
00
01
03
02
04
05

```

To support codes above 99 I need to add a stack structure. Doable, but since both test cases don't even use the second digit I though I'd stop here. Here's the resulting BrainFuck code (1096):

```
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>,----------[----------------------[-<<<<[<<]+[>>
]>>]<[-<<<[<<]>+>[>>]>>+<]<<<[<<]>>[->>]>>+[-<+>],----------]<[-<+>]<[->+>+<<]>>
>,--------------------------------[-<<<<<[<<]+[>>]>>>]<<<<<[<<]>[-<<<+>>>>[>>]>>
>+<<<<<[<<]>]<<<[->>>+<<<]>>[<<]>>[->>]>>>>,----------[----------------------[-<
<<<<<[<<]+[>>]>>>>]<<<<<<[<<]>[-<<<+>>>>[>>]>>>>+<<<<<<[<<]>]<<<[->>>+<<<]>>[<<]
>>[->>]>[-<+>>>[->>+>>>[>>]+<<[<<]<<<]>>[-<<+>>]<<<<]<[->+<]>>>>+[->+>>>[>>]+<<[
<<]<<]>-[-<+>]>>>[>>]<[->>>+<<<<[<<]<+>>>[>>]<]>>>[-<<<+>>>]<<<<[<<]+<[<<[-]>>[-
<<+>>]>-<]>[-<<[-<<<<+>>>>]>>>>-<<<<++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>[-
]>>>>+<++++++++++++++++++++++++++++++++++++++++++++++++[-<+<+>>]<[.[-]<]++++++++
++.[-]<<[->+>>>>>[>>]<+<[<<]<<<<]>+[-<+>]<<<[->>>+<<<]>>>>>>]>>[>>]<<[-<<]<<[-],
----------]++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>[-]>>>+++++++++++++++++++++
+++++++++++++++++++++++++++[-<+<+>>]<[.[-]<]++++++++++.[-]

```

Keep in mind that I have aimed for short EBF code, not BF code. Here's the ungolfed EBF source code source code (3,5kB):

```
;; The data type for the lookup array
:lc the crumble for lookup array
:lv the value for this byte
:lz always zero

;; macros for lookup
;; move to open area
{to_lookup $lc(@lz)}

;; move back
{from_lookup $lz(@lc)}

{open_lookup (- &to_lookup+
                @lz &from_lookup)
}

{close_lookup &to_lookup
              $lz(-@lc)
}

;; makes a move to a higher
;; crumble and increments it
{lookup_backup
   $lc@lz
   $lc+$lz@lc
}

;; restore backup
{lookup_restore
    $lc@lz
    $lc(-$lz@lc^0+$lc@lz)
    $lz@lc
}

;; opens the lookup with the
;; index of the current register
;; and replaces it with the
;; code representing that
{lookup_value
    &open_lookup
    &to_lookup
    $lv(- &lookup_backup
          &from_lookup
          ^0+
          &to_lookup)
    &lookup_restore
    &close_lookup
}

;; We have a possible alphabet of ASCII 32-126=94 and
;; we need an empty as well *  2 slots/element = 190
190> @lz

;; The variables we use
:lec  lookup element count
:ndv  next dictionary value
:prev previos match
:cur  current index
:ax   general purpose register a

;; The trie tree data structure
:tz  the empty element
:tv  the value of this node
:tc  the crumble of this node

;; macros for the trie structure
{to_trie $tc(@tz)}

{from_trie $tz(@tc)}

;; makes a move to a higher
;; crumble and increments it
{trie_backup
   $tc@tz
   $tc+$tz@tc
}

;; restore backup
{trie_restore
    $tc@tz
    $tc(-$tz@tc^0+$tc@tz)
    $tz@tc
}

{open_trie
  ;; we take prev times lec first
  ;; we use %lz as temporary for lec
  ;; and
  $lec(-
        $lz+              ; backup lec
        $prev(-
               $ax+       ; backup prev
               &to_trie+
               &from_trie
             )
        $ax(-$prev+)      ; restore backup
      )
  $lz(-$lec+)             ; restore lec
  $cur+(-
          $ax+
          &to_trie+
          &from_trie)
  $ax-(-$cur+)
}

{trie_close &to_trie $tz(-@tc)}

;; divmod divides ^0 with ^1
;; leaving remainder in ^2
;; and quotient in ^3
;; Needs up to ^5 for working area
{divmod
  (-^1-
      [^2+^4]
      ^5[*-3+[-^1+^2]^3+^5])
}

;; First we need to fill our lookup
;; we'll use ndv
$ndv,10-
( ; while not lf
  22-
  &open_lookup
  $lec(- &to_lookup $lv+
         &from_lookup $ndv+)
  &close_lookup
  $ndv+(-$lec+)
  %ndv , 10-
)

;; Now that we have all symbols we make a copy
$lec(-$lz+)
$lz(-$lec+$ndv+)
#

$prev, 32- &lookup_value
$cur, 10-
(
  22-
  #&lookup_value
  #
  &open_trie

  ;; somehow if tv is we copy it to ax and reset prev
  ;; if prev is set we copy it to tv and
  &to_trie
  $tv(-
        &trie_backup
        &from_trie
        $ax+
        &to_trie
     )
  &trie_restore
  &from_trie
  $tz+
  $ax( $prev(-)$ax(-$prev+)$tz-)
  $tz(-
      $cur(-$lz+) ; make copy of cur
      $tc-
      $cur 10+ $prev &divmod
      $cur(-)
      $tc+
      $tv 48+(-$tz+$ax+)
      $tz[.(-)<]@cur
      10+.(-)
      $ndv(- $prev+
             &to_trie $tv+
             &from_trie
          )
      $prev+(-$ndv+)
      $lz(-$prev+)
   )
   &trie_close
   $cur(-), 10-
)
#$cur 10+ $prev &divmod
$cur(-)
$tv 48+(-$tz+$ax+)
$tz[.(-)<]@cur
10+.(-)

```
> 1 votes

# Answer
# Ruby, 104 bytes

Only lightly golfed. Very similar to user2846289's Perl solution. I'm not sure why this straightforward challenge saw so few attempts; maybe we can revive it.

```
->a,s,*o{d=a.chars
(d.size-1).downto(0){(o<<_1
d<<$&
break)if s.gsub! /^#{d[_1]}(.?)/,'\1'}while s[0]
o}

```

Attempt This Online!
> 1 votes

---
Tags: code-golf, string, compression
---


title: Solve a meta-knowledge puzzle

text:
# Question
Title: Solve a meta-knowledge puzzle
Alice and Bob are perfect logicians trapped on an island with a puzzle generator. Although they can instantly solve the Riemann hypothesis and P=NP just by thinking about it, rather than doing anything useful, they amuse themselves by giving each other puzzles. The setup is as follows: a positive integer *n* is chosen by the puzzle generator, and is told to Alice and Bob. The puzzle generator also chooses a secret integer *k*, with `0 <= k < n`. Next, the puzzle generator gives information about *k* to Alice and Bob in alternating turns. Whenever either one learns *k*, they immediately yell out "I know the number!" Furthermore, Alice and Bob both know this setup. Your task is, given the puzzle generator's output, determine when each one learns the number, if they ever do.

# Input

You will receive *n*, *k* and a list of list of integers, with each list being length *n*. These lists are all public knowledge and indicate what the person would have received for every hypothetical value of *k*. Only the person whose turn it is actually receives the hint (the *k*th value of the array), but both players know what hint would have been received for any particular value of *k*. The first clue is given to Alice, the next to Bob, then Alice etc. An example is more illuminating than text:

```
n=5 k=0 [[1, 1, 2, 2, 2], [1, 2, 1, 1, 1], [0, 0, 0, 0, 0]] --> (2, 2)

```

Let's walk through the example. Alice first receives the number 1, because *k=0* and the 0th element of `[1, 1, 2, 2, 2]` is 1. Both Alice and Bob receive the information about what Alice would have gotten had *k* been something else, so Alice now knows that either *k=0* or *k=1* and Bob knows that Alice knows whether *k=0 or 1* or *k=2, 3, or 4*. Since Alice doesn't yet know *k*, she says nothing.

Next, Bob receives the number 1, because *k=0*. Thus, Bob learns that *k=0, 2, 3, or 4*. In addition, the fact that Bob says nothing lets Alice rule out the possibility that *k=1*, since if *k=1*, Bob would have gotten *2* and would have learned it, so now Alice knows that *k=0* and says that she knows *k*. Bob knows that if *k=2, 3, or 4*, this would not be possible, because the fact that he said nothing only rules out *k=1* for Alice, which she would have already ruled out anyway. Thus, Bob also learns that *k=0*. Thus, they both require 2 clues to learn *k*, so the output is *(2, 2)*. Note that all clues after both Alice and Bob learn *k* don't matter; in particular, `[0, 0, 0, 0, 0]` doesn't give any information anyway, but regardless of what it is, you can essentially ignore it.

# Output

Output or return two integers, the number of clues for Alice to learn *k* and the number of clues for Bob to learn *k* respectively. In the special case where `n=1`, the output is always `(0, 0)` since both Alice and Bob immediately know, without any clues, that `k=0` just upon learning `n`. If one of the two never learns *k*, output `-1`, `Infinity`, `None`, `NaN`, or something else that makes it clear that they do not learn *k*.

Your code only has to work in theory; if in practice it results in a Stack Overflow error, that is fine, as long as you can show that your code would work given unlimited resources and an infinite call stack size.

# Test cases

```
n=2 k=1 [[0, 1], [1, 1], [0, 0], [1, 0]] --> (1, 4)
n=3 k=1 [[0, 1, 1], [0, 1, 1], [1, 2, 2]] --> (-1, -1)
n=5 k=2 [[1, 1, 2, 2, 2], [1, 1, 1, 2, 2], [1, 1, 3, 1, 2]] --> (3, 3)
n=4 k=0 [[0, 1, 2, 3], [0, 0, 0, 0], [0, 0, 0, 0]] --> (1, -1)
n=6 k=5 [[0, 1, 1, 1, 1, 1], [1, 0, 1, 1, 1, 1], [1, 1, 0, 1, 1, 1], [1, 1, 1, 0, 1, 1], [1, 1, 1, 1, 0, 1]] --> (5, -1)
n=5, k=2, [[1, 1, 2, 2, 2], [1, 2, 2, 3, 3]] -> (2,2)

```

That last one is a bit tricky so here's a step-by-step: First, Alice receives 2, so she knows either `k=2`, `k=3`, or `k=4`. Then, on the second step, Bob learns that either `k=1` or `k=2`. Since he doesn't know what it is, he says nothing, so Alice learns that `k` is not `0`, and moreover, Bob now knows Alice knows this. However, Alice still doesn't say anything (in fact she already knew that `k` was not 0). The fact that Alice doesn't say anything lets Bob eliminate the case `k=1`, since if `k=1`, Alice would have received `1` as her first input, so eliminating `k=0` would let her know that `k=1`. Hence, Bob knows that `k=2`, and says so. Now, Alice knows that what just happened is consistent with `k=2`. Is it consistent with `k=3` or `k=4`? If `k=3` or `k=4`, Bob would have gotten 3 as his clue, and there haven't been any clues so far that distinguish between `k=3` and `k=4` for anyone, so Bob couldn't know which one it is. Therefore, Alice also learns that `k=2`.

This is code golf, so shortest code wins!

# Answer
> 4 votes
# JavaScript (ES7), 300 bytes

Takes input as `(n, k, clues)`. Returns a pair in the format used in the challenge.

```
(n,k,a)=>n>1?a.map((c,t)=>[...m,...m].map((_,p)=>m.map(M=m=>!(v=m[p])|v&~-v?0:m[M|=v,p]=0,(x=~R[p&=1]|!(v=m[k][p])|v&~-v)?0:R[p]=t+1)|x?m.map(m=>m[p^1]&=~M):M&~-M&m[k][p^=1]?0:m[k][p]&=M,m.map((m,i)=>m[t&1]&=c.map(o=(v,j)=>o|=(v==c[i])<<j)|o)),m=[...Array(n)].map(_=>[x=2**n-1,x]),R=[-1,-1])&&R:[0,0]

```

Try it online!

### How?

We first build an array \\$m\[\\;\]\\$ of \\$n\\$ pairs of bitmasks:

```
m = [...Array(n)].map(_ => [x = 2**n - 1, x])

```

The bitmask \\$m\[i\]\[p\]\\$ represents the possible answers from the perspective of player \\$p\\$, assuming that the identifier of the \\$i\\$-th clue was received so far.

In the main loop, we iterate on each list \\$c\[\\;\]\\$ of clues at position \\$t\\$ and then \\$n\\$ times on each player \\$p\\$, alternately:

```
a.map((c, t) => [...m, ...m].map((_, p) => ...))

```

For each list of clues, we update \\$m\[\\;\]\\$ for the player that will receive the clue at this turn:

```
m.map((m, i) =>
  m[t & 1] &=
    c.map(o = (v, j) => o |= (v == c[i]) << j) | o
)

```

For each player iteration, we test:

* whether there's only one possible remaining answer given what was actually received (i.e. from this player's perspective)
* whether there would be only one possible remaining answer if another clue was received so far (i.e. from the other player's perspective)

This is performed in the following loop:

```
m.map(M = m =>
  !(v = m[p]) | v & ~-v ?
    0
  :
    m[M |= v, p] = 0,
  (x = ~R[p &= 1] | !(v = m[k][p]) | v & ~-v) ?
    0
  :
    R[p] = t + 1
)

```

If the current player doesn't say that he knows the answer (\\$x\neq0\\$), we remove all hypotheses where an answer is found at this point from the bitmasks of the other player:

```
m.map(m => m[p ^ 1] &= ~M)

```

If the current player says he knows the answer (\\$x=0\\$), we update the bitmask of the other player accordingly:

```
M & ~-M & m[k][p ^= 1] ?
  0
:
  m[k][p] &= M

```

# Answer
> 1 votes
# Python3, 956 bytes:

```
E=enumerate
def f(n,k,h):
 m,o,c,r,I=[[],[]],[[],[]],0,[-1,-1],[[],[]]
 while h:
  if-1not in r:return r
  H=h.pop(0);V=[i for i,a in E(H)if a==H[k]and i not in I[c%2]and(m[c%2]==[]or i in m[c%2])];I[c%2]+=[i for i in m[c%2]if i not in V];m[c%2]=V;d={}
  for i,a in E(H):d[a]=d.get(a,[])+[i]
  if r[not c%2]==-1:o[not c%2]=[*d.values()]
  A,F,P=0,1,not c%2
  if len(m[c%2])==1 and r[c%2]==-1:r[c%2]=c+1;A=1
  while F:
   F=0
   if A==0:
    for i in o[P]:
     if len(i)==1:
      m[P]=[j for j in m[P]if j!=i[0]];I[P]+=i
      if(N:=[J for j in o[not P]if(J:=[u for u in j if u!=i[0]])])!=o[not P]:o[not P]=N;F=1;P=not P
   else:
    for i in o[not P]:
     if len(i)==1:
      if len(K:=[J for j in o[P]if(J:=[u for u in j if u!=i[0]and u in m[P]])and len(J)==1])==1:m[P]=K[0]
    if len(K:=[J for j in o[P]if len(J:=[u for u in j if u in m[P]])==1])==1:m[P]=K[0]
   for i,a in E(m):
    if r[i]==-1and len(a)==1:r[i]=c+1;F=1;A=1;P=not i
  c+=1
 return r

```

Try it online!

---
Tags: code-golf, puzzle-solver
---