66
\$\begingroup\$

The other day we were writing sentences with my daughter with a fridge magnet letter. While we were able to make some(I love cat), we didn't have enough letters to make the others (I love you too) due to an insufficient amount of letters o (4)

I then found out that while one set included 3 e letters it had only 2 o letters. Probably inspired by http://en.wikipedia.org/wiki/Letter_frequency this would still not reflect the actual situation "on the fridge".

Problem

Given the text file where each line contains a "sample sentence" one would want to write on the fridge, propose an alphabet set with minimum amount of letters but still sufficient to write each sentence individually.

Note: ignore cases, all magnet letters are capitals anyway.

Input

The file contain newline separated sentences:

hello
i love cat
i love dog
i love mommy
mommy loves daddy

Output

Provide back sorted list of letters, where each letter appears only as many times to be sufficient to write any sentence:

acdddeghillmmmoostvyy

(thanks, isaacg!)

Winner

Shortest implementation (code)

UPDATED: Testing

I have created an extra test and tried with various answers here:

https://gist.github.com/romaninsh/11159751

\$\endgroup\$
  • 2
    \$\begingroup\$ There should be a letter v in the output ;) \$\endgroup\$ – Antonio Ragagnin Apr 10 '14 at 6:35
  • 40
    \$\begingroup\$ Are we allowed / required to substitute an upside-down M for a W, or a sideways N for a Z? ;-) \$\endgroup\$ – Ilmari Karonen Apr 10 '14 at 11:42
  • 4
    \$\begingroup\$ Basically you can construct any letter using Is. \$\endgroup\$ – swish Apr 10 '14 at 11:53
  • 7
    \$\begingroup\$ More seriously, when you say "ignore cases", do you mean that we can assume that the input is already all in the same case, or that we must convert it all into the same case? Also, is it OK for the output to include some leading spaces? \$\endgroup\$ – Ilmari Karonen Apr 10 '14 at 12:01
  • 3
    \$\begingroup\$ @Doorknob: _\¯ \$\endgroup\$ – Ilmari Karonen Apr 10 '14 at 13:37

50 Answers 50

1
\$\begingroup\$

JavaScript, 199 characters

function(n){for(s in p=n.toUpperCase(t=[]).split("\n"))for(i in p[k={},s])t[l=p[s][i]]=Math.max(t[l]||0,k[l]=k[l]+1||1);for(l in t)t.push(new Array(t[l]+1).join(l));return t.sort().join('').trim()}
\$\endgroup\$
  • \$\begingroup\$ In Chrome 33, doing for(..in..) on a string results in function properties being accessed. It breaks this solution. The example input from OP gives this result: "ACDDDEGHILLMMMOOSTVYYfunction (){var e=this.toString();if(!arguments.length)return e;var t=typeof arguments[0],n="string"==t||"number"==t?Array.prototype.slice.call(arguments):arguments[0];for(var i in n)e=e.replace(new RegExp("\\{"+i+"\\}","gi"),n[i]);return e}function (e){return this.indexOf(e)>-1}function (e){var t=this.lastIndexOf(e);return 0>t?[this]:[this.substr(0,t),this.substr(t)]}function (e,t){var n=this.toString();re... \$\endgroup\$ – nderscore Apr 10 '14 at 19:56
1
\$\begingroup\$

C++, 264 characters.

Reads lowercase text from standard input.

#include<algorithm>
#include<iostream>
#include<map>
using namespace std;main(){string s;map<int,long> m;while(getline(cin,s)){int c='`';while(c++<'z')m[c]=max(m[c],count_if(begin(s),end(s),[c](int d){return d==c;}));}for(auto i:m)cout<<string(i.second,i.first);}

C++ function, 205 characters.

string a(istream&i){string s;map<int,long> m;while(getline(i,s)){int c='`';while(c++<'z')m[c]=max(m[c],count_if(begin(s),end(s),[c](int d){return d==c;}));}for(auto i:m)s.append(i.second,i.first);return s;}
\$\endgroup\$
1
\$\begingroup\$

JavaScript - 244

Accepts a parameter of string with newlines.

function s(z){n=m="",y=[];z.toLowerCase().split("\n").map(function(g){a=[];g.replace(/ /g,n).split(n).map(function(e,i){if((+y[e]|0)<(a[e]=(+a[e]|0)+1))y[e]=a[e];});});for(var b in y){m+=Array(y[b]+1).join(b);}return m.split(n).sort().join(n);}

Not happy with the sorting and preparation of the output.

Edit: case-insensitive regex unnecessary! Thanks @Bergi

\$\endgroup\$
  • 2
    \$\begingroup\$ Upper- and lowercase spaces in that regex? \$\endgroup\$ – Bergi Apr 10 '14 at 23:59
1
\$\begingroup\$

Lua - 206 Chars

g=string
f,t,b,e=io.lines(({...})[1]),{},g.byte,g.char
for s in f do for c=b"a",b"a" do _,d=s:lower():gsub(e(c),"");t[c]=t[c]and(t[c]>d and t[c])or d end end for c=b"a",b"z" do io.write(g.rep(e(c),t[c]))end

Reads from the file passed via command line, then creates a table with the maximum number of occurences per letter. Finally outputs the occuring letters.

\$\endgroup\$
1
\$\begingroup\$

Julia, 159

My objective is help understand/improve the expressiveness of Julia. Here's a first attempt.

a='a'-1;print(foldl((c,n)->(global a+=1;"$c"*"$a"^n),"",int(mapreduce(s->hist(int({s...}),0:255)[2],(S,T)->max(S,T),zeros(255),readlines(STDIN))[97:122]))"\n")

Here's my crazy idea.

Using mapreduce, foldl, and hist (builtin histogram) were advantageous, but having to deal assembling an array from a string and then back to a string from an array and globals expanded the length.

Program reads from STDIN. Required foldl which is new in Julia 0.30.

Sample Input

alskdja
flkjaslakjd
asa
as
g
alkdjaslkajsd
Output
aaaddfgjjkkllss
\$\endgroup\$
1
\$\begingroup\$

Java, 335

Here is the executable code in java in a more readable form. Once all the unnecessary white spaces are removed, you will see 335 characters in all. The output is:

ACDDDEGHILLMMMOOSTVYY

It gets a filename as input and reads each character from the file, converts it to uppercase and stores the count of it's occurrence in an array. For every new line, the maximum occurrence of each character is updated. At last it is printed. Pre-requiste: The file should end with a newline.

class F {
    public static void main(String[] a) throws Exception {
        java.io.FileInputStream f = new java.io.FileInputStream(a[0]);
        int j, r, l = 256;
        int[] i = new int[l], t = new int[l];
        while ((r = f.read()) > 0) {
            r = r > 96 ? r - 32 : r;
            if (r == 10)
                for (j = 0; j < l; j++) {
                    i[j] = i[j] < t[j] ? t[j] : i[j];
                    t[j] = 0;
                }
            else
                t[r]++;
        }
        for (j = 65; j < 91; j++)
            while (i[j]-- > 0)
                System.out.print((char) j);
    }
}

After removing the white spaces the code will look like the following:

class F{public static void main(String[] a)throws Exception{java.io.FileInputStream f=new java.io.FileInputStream(a[0]);int j,r,l=256;int[] i=new int[l],t=new int[l];while((r=f.read())>0){r=r>96?r-32:r;if(r==10)for(j=0;j<l;j++){i[j]=i[j]<t[j]?t[j]:i[j];t[j]=0;}else t[r]++;}for(j=65;j<91;j++)while(i[j]-->0)System.out.print((char)j);}}
\$\endgroup\$
1
\$\begingroup\$

C#, 265 characters

Assuming input is in variable s, here's a C# Expression, using mainly LINQ (Enumerable.cs):

string.Join("",s.ToLower().Split('\n').Select(e=>e.Where(l=>l!=' '&&l!='\r')
.GroupBy(l=>l).ToDictionary(k=>k.Key,v=>v.Count())).SelectMany(u=>u).GroupBy(l=>l.Key)
.Select(g=>new String(Enumerable.Range(1,g.Max(v=>v.Value)).Select(i=>g.Key).ToArray()))
.OrderBy(l=>l))
\$\endgroup\$
1
\$\begingroup\$

Japt v1.4.5, 11 bytes

;CËpUmèD rw

Try it online!

Unpacked & How it works

;CmDEF{DpUmèD rw

;                 Use an alternative set of predefined variables
 C                "abc...z"
  mDEF{           Map over each char and form a string...
         UmèD       Map over input array into char count
              rw    Reduce with max
       Dp           Repeat the char this number of times
\$\endgroup\$
0
\$\begingroup\$

C# - 146 Bytes

var x="";foreach(var l in File.ReadAllLines(t))foreach(var p in l)if(x.Count(c=>c==p)<l.Count(c=>c==p))x+=p;string.Concat(x.OrderBy(o=>o)).Trim();

Well, I think this is as short as C# can get. This code expects a path to the text file in the variable t.

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

Kotlin, 189 bytes

lines().map{it.filter{it.isLetter()}.groupingBy{it}.eachCount()}.fold(mutableMapOf<Char,Int>()){r,i->i.map{(t,u)->r[t]=maxOf(r[t] ?:0,u)}
r}.flatMap{(k,v)->(0..v-1).map{k}}.joinToString("")

Beautified

lines()
    .map { it.filter { it.isLetter() }.groupingBy { it }.eachCount() }
    .fold(mutableMapOf<Char, Int>()) { r, i ->
        i.map { (t, u) -> r[t] = maxOf(r[t] ?: 0, u)}
        r
    }
    .flatMap { (k, v) -> (0..v-1).map { k } }
    .joinToString("")

Test

fun String.f() =

lines().map{it.filter{it.isLetter()}.groupingBy{it}.eachCount()}.fold(mutableMapOf<Char,Int>()){r,i->i.map{(t,u)->r[t]=maxOf(r[t] ?:0,u)}
r}.flatMap{(k,v)->(0..v-1).map{k}}.joinToString("")

fun main(args: Array<String>) {
    val i = """hello
i love cat
i love dog
i love mommy
mommy loves daddy"""
    println(i.f().map { it }.sorted().joinToString(""))
    println("acdddeghillmmmoostvyy")
}

TIO

TryItOnline

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

Haskell, 41 bytes

f s=do c<-['a'..];maximum$filter(==c)<$>s

Try it online! f takes a list of lines as input.

Add main=interact$f.lines to get a full program for a total of 63 bytes.

Explanation

f s=                -- input s is the list of lines
 do c<-['a'..];     -- for each char c starting at c='a', concatenate the following strings
    filter(==c)<$>s -- for each line in s remove all characters except for the current c
   maximum$         -- take the longest of those strings
\$\endgroup\$
0
\$\begingroup\$

C# / LINQPad, 181 bytes

In C# Expression mode; assumes input file is named a (and probably in the LINQPad Program Files folder)

string.Join("",File.ReadAllLines("a").SelectMany(s=>s.ToUpper().Where(c=>c>64&&c<91).GroupBy(c=>c)).GroupBy(g=>g.Key).Select(g=>new string(g.Key,g.Max(x=>x.Count()))).OrderBy(s=>s))

Ungolfed

string.Join("",                                                     // concat all substrings, with no separator
    File.ReadAllLines("a")                                          // read all lines from text file called 'a'
        .SelectMany(                                                // apply function to each subset and union into a single set
            s => s.ToUpper()                                        // convert strings to uppercase
                  .Where(c => c > 64 && c < 91)                     // shorter than char.IsLetter(c) for all uppercase
                  .GroupBy(c => c)                                  // group on each character in the string
         )                            
        .GroupBy(g => g.Key)                                        // group again on each character (I'd love to get rid of this...)
        .Select(g => new string(g.Key, g.Max(x => x.Count())))      // string(char, count) constructor build repeating-char string
        .OrderBy(s => s)                                            // sorted set required
)

Input (text file called a)

Hello
I love cat
I love dog
I love mommy
Mommy loves daddy

Output

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

C, 298 bytes

(242 bytes by not counting newlines)

Array D keeps tally of letters in each line, then the maximum count of each letter is copied into array C.

char c;
int j,n;
char C[26];
char D[26];
int main()
{
char a='a';
while((c=getchar())>=0)
{
c=tolower(c);
if(c>=a&&c<='z'){j=c-a;D[j]++;}
if(c=='\n'){
for(j=0;j<26;j++){
if(D[j]>C[j])
{C[j]=D[j];}
D[j]=0;
}
}
}
for(j=0;j<26;j++)
{
n=C[j];
while(n--)
{
putchar(a+j);
}
}
}

Note: I just discovered Notepad++ which gives my character count, counts newlines as 2 chars. Should these be subtracted?

\$\endgroup\$
  • \$\begingroup\$ That's because you use CRLF (Windows) line terminators. You should tell Notepad++ to use LF (Unix), then they will only count as one character. \$\endgroup\$ – nyuszika7h Apr 21 '14 at 20:00
0
\$\begingroup\$

Stax, 8 bytes

ü2lLÜ▀⌂æ

Run and debug it

  1. Reduce the array of inputs using a multiset union operation.
  2. Sort the resulting characters.
  3. Remove spaces.
\$\endgroup\$
0
\$\begingroup\$

Jelly, 7, 6, 5 or 4 bytes

ỴŒuœ|/Ṣ

Try it online!

Function submission. Depending on how you interpret the I/O rules, it may be possible to drop the leading (which would then require input to be the data structure "list of strings", as opposed to a single string that was divided using newlines); and it may be possible to drop the Œu (which would then require the input to use a consistent case for the output to be correct).

Explanation

ỴŒuœ|/Ṣ
Ỵ        Split on newlines
 Œu      Uppercase each resulting string
     /   Combine the resulting strings using…
   œ|      …multiset union
      Ṣ  Sort
\$\endgroup\$
  • \$\begingroup\$ Many answers interpret ignore cases, all magnet letters are capitals anyway as that we don't have to handle input with different cases. The fact that the test case uses lowercase letters supports this interpretation. \$\endgroup\$ – Dennis Dec 13 '18 at 19:04
  • \$\begingroup\$ I interpreted the question as requiring you to standardise case (although it didn't matter whether you used uppercase or lowercase). Without that, you can obviously drop the Œu for a 5 or 4 byte solution. \$\endgroup\$ – ais523 Dec 13 '18 at 19:06
0
\$\begingroup\$

PHP, 116 bytes

foreach(file(T)as$y=>$s)for($i=0;~$c=ucfirst($s[$i++]);)$$c[$y]++;for($c=A;!$c[1];$c++)echo str_repeat($c,max($$c));

assumes filename T. Run with -nr.

breakdown

foreach(file(T)as$y=>$s)            # loop through lines of file
    for($i=0;~$c=ucfirst($s[$i++]);)    # loop through line characters
        $$c[$y]++;							# increment counter ($A..$Z)
	for($c=A;!$c[1];$c++)				# loop $c through uppercase letters
		echo str_repeat($c,max($$c));      # get max from $A, $B etc, use as multiplier for str_repeat
\$\endgroup\$
0
\$\begingroup\$

Powershell, 118 116 87 bytes

-join($args|%{$_|% t*y|group|%{-join$_.Group}}|sort|group{$_[0]}|%{$_.Group[-1]})|% t*m

Less golfed test script:

$f = {

$x=$args|%{$_|% t*y|group|%{-join$_.Group}} # unsorted groups of the same letters for each sentence: (h,e,ll,o), (...), (...), (i, ,l,oo,v,e,d,g),...
$y=$x|sort|group{$_[0]}                     # sort all groups and group it again by the first letter (( , , , ), (a,a), (c), (d,ddd), ... (y,yy))
$z=$y|%{$_.Group[-1]}                       # get a last item (maximum item) from each group
-join($z)|% t*m                             # join it and trim spaces

}

@(
    ,("acdddeghillmmmoostvyy",
      "hello",
      "i love cat",
      "i love dog",
      "i love mommy",
      "mommy loves daddy")

    ,("AAAAAAAAAAAAAAAABBBCCCCDDDDDEEEEEEEEEFFGGGGHHHHHHIIIIIIIIIIJJKKLLLLMMMMMMMNNNNNNNNNNNNNOOOOOOOOOPPPPPPPQRRRRRRSSSSSSSTTTTTTUUUUUVWWXYYY",
      "I SAW THE MAN WITH THE BINOCULARS",
      "THEY ARE HUNTING DOGS",
      "FREE WHALES",
      "POLICE HELP DOG BITE VICTIM",
      "HE SAW THAT GAS CAN EXPLODE",
      "TURN RIGHT HERE",
      "WE SAW HER DUCK",
      "IN ANIMAL CRACKERS GROUCHO MARX AS CAPTAIN RUFUS T SPAULDING QUIPPED ONE MORNING I SHOT AN ELEPHANT IN MY PAJAMAS HOW HE GOT IN MY PAJAMAS I DONT KNOW",
      "SHIP SAILS TOMORROW",
      "BOOK STAYS IN LONDON",
      "WANTED A NURSE FOR A BABY ABOUT TWENTY YEARS OLD",
      "THE GIRL IN THE CAR THAT NEEDED WATER IS WAITING",
      "DID YOU EVER HEAR THE STORY ABOUT THE BLIND CARPENTER WHO PICKED UP HIS HAMMER AND SAW",
      "THOSE PROSECUTORS HAVE BEEN TRYING TO LOCK HIM UP FOR TEN YEARS",
      "FLYING PLANES CAN BE DANGEROUS",
      "I ONCE SAW A DEER RIDING MY BICYCLE",
      "TOILET OUT OF ORDER PLEASE USE FLOOR BELOW",
      "LOOK AT THE DOG WITH ONE EYE")
) | %{
    $expected,$s = $_
    $result = &$f @s
    "$($result-eq$expected): $result"
}

Output:

True: acdddeghillmmmoostvyy
True: AAAAAAAAAAAAAAAABBBCCCCDDDDDEEEEEEEEEFFGGGGHHHHHHIIIIIIIIIIJJKKLLLLMMMMMMMNNNNNNNNNNNNNOOOOOOOOOPPPPPPPQRRRRRRSSSSSSSTTTTTTUUUUUVWWXYYY
\$\endgroup\$
0
\$\begingroup\$

05AB1E, 12 bytes

εAS¢}ø€àAS×J

I have the feeling this can be golfed by at least a few bytes..

Input taken as a list of lowercase strings. If taking the input as a newline-delimited string and with mixed case is mandatory, two more bytes should be added.

Try it online.

Explanation:

ε   }         # Map each string in the (implicit) input-list to:
 A            #  Push the lowercase alphabet
  S           #  as a list of characters
   ¢          #  And get the count of each letter in the map-string
              #   i.e. ["hello","i love cat","i love dog","i love mommy","mommy loves daddy"]
              #    → [[0,0,0,0,1,0,0,1,0,0,0,2,0,0,1,0,0,0,0,0,0,0,0,0,0,0],[1,0,1,0,1,0,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,1,0,0,0,0],[0,0,0,1,1,0,1,0,1,0,0,1,0,0,2,0,0,0,0,0,0,1,0,0,0,0],[0,0,0,0,1,0,0,0,1,0,0,1,3,0,2,0,0,0,0,0,0,1,0,0,1,0],[1,0,0,3,1,0,0,0,0,0,0,1,3,0,2,0,0,0,1,0,0,1,0,0,2,0]]
     ø        # Zip/transpose; swapping rows/columns
              #  → [[0,1,0,0,1],[0,0,0,0,0],[0,1,0,0,0],[0,0,1,0,3],[1,1,1,1,1],[0,0,0,0,0],[0,0,1,0,0],[1,0,0,0,0],[0,1,1,1,0],[0,0,0,0,0],[0,0,0,0,0],[2,1,1,1,1],[0,0,0,3,3],[0,0,0,0,0],[1,1,2,2,2],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,1],[0,1,0,0,0],[0,0,0,0,0],[0,1,1,1,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,1,2],[0,0,0,0,0]]
      ۈ      # Leave the maximum of each
              #  → [1,0,1,3,1,0,1,1,1,0,0,2,3,0,2,0,0,0,1,1,0,1,0,0,2,0]
        AS×   # Repeat each the letters of the alphabet amount of times
              #  → ["a","","c","ddd","e","","g","h","i","","","ll","mmm","","oo","","","","s","t","","v","","","yy",""]
           J  # And join everything together (which is output implicitly)
              #  → "acdddeghillmmmoostvyy"
\$\endgroup\$
0
\$\begingroup\$

JavaScript, 105 104 bytes

Takes input as an array of character arrays and returns a string.

a=>[...new Set(a+``)].sort().map(c=>c.repeat(a.map(r=w=>r=w.map(l=>o+=c>{}&c==l,o=0)|o<r?r:o)|r)).join``

Try it online

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

Pyth, 14 10 bytes

smeS@Ld.zG

Accepts input as lowercase strings. Try it online here.

smeS@Ld.zG   Implicit: .z=input as list of strings, G=lowercase alphabet
 m       G   Map each letter in G, as d, using:
     L .z      In each string in .z ...
    @ d        ... keep only those characters which match d
   S           Sort by length
  e            Take the last element (i.e. longest)
s            Concatenate into string, implicit print

Edit: golfed 3 bytes. Previous version: sm*deSml@dk.zG

\$\endgroup\$

Your Answer

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

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