6
\$\begingroup\$

this challenge was based on a sandboxed post by @dmckee

Old fashioned cell phones were and are used heavily as texting platforms, unfortunately the keyboard has only 12 + a few buttons, and is therefor ill-suited to naive text entry.

Common solutions make use of the traditional telephone coding (generally with a modest extension for 'q' and 'z'):

2: a,b,c
3: d,e,f
4: g,h,i
5: j,k,l
6: m,n,o
7: p(,q),r,s
8: t,u,v
9: w,x,y(,z)

In this case we are interested in the one-press-per-letter schemes that offer up words matching words on a frequency basis. That is if the user type "4663" the phone will offer up words like "good", "home", "gone", "hood", "hoof", etc that code to 4663 in order of their frequency.

Your task is to read one or more input files and generate a frequency sorted dictionary that could be used to implement this scheme.

Inputs

  • All input will be plain ASCII text.
  • You may accept input from named files, the standard input, or other conventional source supported by your implementation language, but there must be some mechanism to process several files in a single run.
  • Non-letter, non-whitespace characters should be stripped from the input, this means that contractions will be coded without their apostrophe: "don't" --> "dont" --> 3668
  • Words are a sequence of letters separated surrounded by whitespace
  • All whitespace (space, tab, newline, beginning-of-file, end-of-file) is equivalent.
  • Input will be all lowercase or caps your preference.

Output

  • The output consists of a ASCII text stream
  • You may direct this to a file, the standard output, or any other conventional destination supported by your implementation language
  • The output should consist of one line for each string of digits corresponding to at least one word in the input.
  • Each line should consist of the digit string and a list of all corresponding words sorted by frequency with the most frequent coming first. A sample line of output would be

    4663 good home gone hood hoof
    
  • Tokens (digit strings and corresponding words) should be separated by a single space.

  • Equally frequent words may be sorted in any order.

The winner is the shortest code.

Test Cases

potato, potato, damd, fjefje, djfaejri

Top 1000 words used.

The potato was a down goat goat down game gill pont pint point.

More actual test cases will be given in about a week to prevent any sort of hard-coding action.

\$\endgroup\$
  • \$\begingroup\$ What should functionality be when there is nothing of the correct length in the input file(s)? \$\endgroup\$ – Stephen May 31 '17 at 17:33
  • \$\begingroup\$ @StephenS you can bug out. \$\endgroup\$ – Christopher May 31 '17 at 17:33
  • \$\begingroup\$ in the bigO notation, O(n) = O(2n) \$\endgroup\$ – Felipe Nardi Batista May 31 '17 at 17:34
  • 2
    \$\begingroup\$ Can you provide a better explanation of "Big O"? I'm left wondering how you accurately measure efficiency across different languages and machines. \$\endgroup\$ – Shaggy May 31 '17 at 17:39
  • 2
    \$\begingroup\$ "Top 1000 words will be used with each word repeated x times based on the position on the list (word one is put 1000 times two is 999... ect [sic])." is this regarding the test case or the input file, and what does it mean exactly? \$\endgroup\$ – Jonathan Allan May 31 '17 at 17:43
2
+50
\$\begingroup\$

Jelly, 42 41 bytes

>”q+91N+O:3«9µ€Ḍ’0x
ċ@Þ³ṚQµÇ€⁸ṭ"Zḟ€0Ėṛ/Ðf

Try it online!

Monadic link take a list of strings as argument.

The footer is for formatting the output to a form suitable for outputting. Without it, the monadic link returns:

[[3, ["d", "f", "e"]], [4628, ["goav", "goat"]], [6346, ["mego", "mdim"]]]

(that is, a list, each has the format [number, list of words]).

The "Zḟ€0 idea was taken from this answer.


Explanation:

The first link, which given a string and output its telephone number, is mostly a port from my Python answer.

>”q+91N+O:3«9µ€Ḍ’0x     Link.
                        Implicit input, call it (st).
             µ€         Monadic link map for each character (ch):
>”q                     Larger than character 'q'? If yes, get 1, else get 0.
   +91N                 add 91, and then negate. Current value = -((ch>'q')+91)
       +O               Add the ord (ASCII value) of ch. Get ch-(ch>'q')-91.
         :3             Integer division by 3.
           «9           If the result is larger than 9, set it to 9. (« : min)
                        With the list of digits obtained by 
                        mapping the previous chain to characters:
               Ḍ        Convert from decimal digits to number.
                ’       Decrement.
                 0x     Repeat that many digits of zero.

Then, the second link:

  Þ                         Sort by...
ċ@                            count. (frequency)
   ³                        I have no idea what is this used for.
    Ṛ                       Reverse. (so that words with max count appear first)
     Q                      Unique.
      µ                     With that value,
       Ç                    Map the previous link over this word list.
         ṭ"                 Vectorize tack with...
        ⁸                     the word list.
           Z                Zip (transpose).
            ḟ€0             Filter out 0 from each element.
               Ė            Enumerate.
                  Ðf        Filter, keep elements with truthy...
                ṛ/            last element.
\$\endgroup\$
5
\$\begingroup\$

Mathematica, 202 bytes

{g[#],##}~r~" "&@@@GatherBy[#&@@@SortBy[Tally@StringReplace[StringSplit@#,x_/;!LetterQ@x->""],-Last@#&],g=""<>ToString/@(\[LeftFloor]If[#<113,(#-91)/3,(#-88.2)/3.4]\[RightFloor]&/@ToCharacterCode@#)&]~(r=Riffle)~"
"<>""&

Note that \[LeftFloor] and \[RightFloor] are 3 bytes each.

\$\endgroup\$
  • \$\begingroup\$ Well since nobody answered besides you :/ \$\endgroup\$ – Christopher Jul 19 '17 at 1:25
4
\$\begingroup\$

C++, 566 533 bytes

-33 bytes thanks to Zacharý ( about 20 bytes ) and user202729 ( about 12 bytes )

#include<map>
#include<string>
#include<fstream>
#include<regex>
#include<set>
using namespace std;using s=string;struct z{s d;int f;int operator<(z a)const{return f<=a.f&&d<a.d;}};regex r("[^a-z]");void g(){fstream e("a"),o("d",ios::out);map<s,int>m;while(!e.eof()){s t;e>>t;t=regex_replace(t,r,"");++m[t];}map<s,set<z>>t;for(auto a:m){s k;for(auto c:a.first)k+="22233344455566677778889999"[c-97];t[k].insert({a.first,a.second});}for(auto&a:t){o<<'\n'<<a.first<<' ';for(auto m=a.second.rbegin();m!=a.second.rend();++m)o<<m->d<<' ';}}

Uses a set to ensure that the words in the z struct are ordered, so a reverse iterator loop can be done.

\$\endgroup\$
  • \$\begingroup\$ If you are using g++ you can use import and bits/stdc++.h. \$\endgroup\$ – user202729 Dec 14 '17 at 11:46
  • \$\begingroup\$ Also I think s("...")[k-97] can be replaced by "..."[k-97] (indexing a char[] also works); and there is a redundant space. / Why is const z& necessary? Just z is enough (although the performance would be bad) \$\endgroup\$ – user202729 Dec 14 '17 at 11:49
  • \$\begingroup\$ You don't need a a space here: return (f<=a.f&&d<a.d);=>return(f<=a.f&&d<a.d); \$\endgroup\$ – Zacharý Dec 14 '17 at 13:19
  • \$\begingroup\$ Also, using namespace std should save a few bytes if you get rid of all the std::s \$\endgroup\$ – Zacharý Dec 14 '17 at 13:22
  • \$\begingroup\$ @user202729 I use MSVC++. For the const required, see this answer. I can change it to a non constant value parameter though. \$\endgroup\$ – HatsuPointerKun Dec 14 '17 at 15:19
3
\$\begingroup\$

Perl 5, 123 bytes + 1 (-a) = 124 bytes

y/A-Z//dc&$k{y/A-Z/22233344455566677778889999/r}{$_}++for@F}{$,=$";say$_,sort{$k{$_}{$b}-$k{$_}{$a}}keys%{$k{$_}}for keys%k

Try it online!

Takes input as uppercase.

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

Clean, 245 ... 214 210 bytes

import StdEnv
r=removeDup
$s=toString[48+min((toInt c-91-toInt c/113)/3)9\\c<-:s]
?f=foldr(\s-> \l=[(a+if(s==b)1 0,b)\\(a,b)<-l])(zip([0,0..],r f))f
@f=r[(s,reverse(map snd(sort(?[l\\l<-f| $l==s]))))\\s<-map$f]

Try it online!

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

Röda, 218 bytes

{g={|n|chars n|[("2223334445556667777888999"/"")[ord(_)-97]]|concat}m=new map
replace`[^\w\s]|_`,""|(_/`\s+`)|sort|count|m[g(_)]+=[-_,_1]if m[g(_1)]=[]unless[m[g(_1)]?]
keys m|sort|{|k|[k];m[k]|sort|_|[` $_2`];[`
`]}_}

Try it online!

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

PHP, 273 bytes

<?$f=str_split;$w=explode(" ",preg_replace(['/\s+/','/[^a-z ]/is'],[' ',''],$argv[1]));$l=$f('22233344455566677778889999');foreach($w as$x){$z='';foreach($f($x)as$y){$z.=$l[ord($y)-97];}$a[$z][$x]++;}foreach($a as$n=>$b){arsort($b);echo$n." ".join(" ",array_keys($b))."
";}

Try it online!

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

Java 8, 480 + 19 = 499 bytes

A Runnable lambda. Byte count includes lambda and required import. Input and output are as specified through standard in/out. Input is in all lowercase. Dictionary items are not printed in any particular order.

import java.util.*;

()->{Map<String,Integer>f=new HashMap();new Scanner(System.in).useDelimiter("\\s+").forEachRemaining(n->f.put(n=n.replaceAll("[^a-z]",""),f.getOrDefault(n,0)+1));Map<String,Set>n=new HashMap();f.forEach((k,v)->{String c=k;for(int i=0;i<8;)c=c.replaceAll("["+"abc def ghi jkl mno pqrs tuv wxyz".split(" ")[i]+"]",++i+1+"");n.putIfAbsent(c,new HashSet());n.get(c).add(k);});n.forEach((k,v)->System.out.println(v.stream().sorted((y,z)->f.get(z)-f.get(y)).reduce(k,(y,z)->y+" "+z)));}

Try It Online

Ungolfed lambda

() -> {
    Map<String, Integer> f = new HashMap();
    new Scanner(System.in)
        .useDelimiter("\\s+")
        .forEachRemaining(
            n -> f.put(
                n = n.replaceAll("[^a-z]", ""),
                f.getOrDefault(n, 0) + 1
            )
        )
    ;

    Map<String, Set> n = new HashMap();
    f.forEach((k, v) -> {
        String c = k;
        for (int i = 0; i < 8;)
            c = c.replaceAll(
                "[" + "abc def ghi jkl mno pqrs tuv wxyz".split(" ")[i] + "]",
                ++i + 1 + ""
            );
        n.putIfAbsent(c, new HashSet());
        n.get(c).add(k);
    });

    n.forEach((k, v) ->
        System.out.println(
            v.stream()
                .sorted((y, z) -> f.get(z) - f.get(y))
                .reduce(k, (y, z) -> y + " " + z)
        )
    );
}

f is my frequency map, and n collects words based on their numeric encoding. As usual with programs this long, this is probably far from optimal. Improvements are welcome.

I could have replaced ++i+1+"" in the number encoding step with ""+-~++i for the same number of bytes. But I respect you all too much to do that.

\$\endgroup\$
  • \$\begingroup\$ this does not handle uppercase or capitalized words \$\endgroup\$ – Setop Dec 13 '17 at 12:22
  • 1
    \$\begingroup\$ @Setop Taking just uppercase or just lowercase was allowed in the challenge specification. \$\endgroup\$ – Xcali Dec 13 '17 at 14:09
1
\$\begingroup\$

Python 3, 179 156 155 bytes

Thanks Rod for -23 bytes!
Thanks anonymous user suggestion for -1 byte!

def f(l):
	d={}
	for w in l:k=(*[min(27,ord(x)-91-(x>'q'))//3for x in w],);d[k]=k in d and{w}|d[k]or{w}
	for k in d:print(k,sorted(d[k],key=l.count)[::-1])

Try it online!

\$\endgroup\$
  • \$\begingroup\$ what is the purpose of min(27,...) ? \$\endgroup\$ – Setop Dec 13 '17 at 12:34
  • \$\begingroup\$ @Setop Otherwise z will become 10, not 9. \$\endgroup\$ – user202729 Dec 13 '17 at 12:54
  • \$\begingroup\$ Based on your solution, I had a try with defaultdict(Counter). I expected to save some bytes by avoiding count, but ended up spending a lot of bytes printing the result. \$\endgroup\$ – Setop Dec 13 '17 at 14:14

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.