10
\$\begingroup\$

Your challenge today is to implement a t9-like functionality.

You will implement a function that will only have 2 parameters.
You will receive 1 phone number in a string and the content of a text file with a list of words (don't assume a specific newline style).
You can use the link https://raw.githubusercontent.com/eneko/data-repository/master/data/words.txt to test the functionality, or use /usr/share/dict/words (check A text file with a list of words [closed] for more information).

You can assume that you will always receive at least 2 numbers.

Given the number, you will read from a list of words and returns the words starting with the letters mapping to those words. This means that the input should be only numbers from 2 to 9.
You can do whatever you want if you receive invalid input.

If no match is found, you can return an empty list, null/nil or 0.

Remember that the cellphone keys are mapped to their equivalent chars:

  • 0 and 1 are invalid
  • 2 matches [abc]
  • 3 matched [def]
  • 4 matches [ghi]
  • 5 matches [jkl]
  • 6 matches [mno]
  • 7 matches [pqrs]
  • 8 matches [tuv]
  • and 9 matches [wxyz]

Examples:

f('52726')
//returns ["Japan","japan","Japanee","Japanese","Japanesque"...,"larbowlines"]

f('552')
//returns ["Kjeldahl","kjeldahlization","kjeldahlize"...,"Lleu","Llew"]

f('1234')
//makes demons fly out your nose or divide by 0

f('9999')
//returns ["Zyzzogeton"]

f('999999')
//returns [] or null/nil or 0

After you run your function, you can print it in any way you wish.

Rules:

  • Standard loopholes are INVALID
  • You must return something, even if it is null/nil
    Javascript will return undefined if you don't return something, therefore this rule.
  • You cannot use or re-implement other's answers or copy my implementation.
  • You can assume, for Javascript, that the browser will be already opened and that the innerText/textContent of the automatic element will be passed as the 2nd parameter
  • For compiled languages, you cannot pass special arguments to the compiler
  • You can receive the file name over compiler arguments
  • Variables, macros, global variables, constants, non-standard classes and all the sort passing other values inside the function will be considered invalid.
  • In Javascript, variables without the keyword var render your code invalid
  • Your function will be named f
  • You can only and only have 2 arguments on your function
  • Try to keep your code under 500 seconds to run.
  • You don't have to worry about whitespace
  • You must use only ASCII printable characters.
    Exceptions are languages that only use non-printable characters (APL and whitespace are 2 examples).

Scoring:

  • Lowest number of bytes win
  • Having invalid ASCII printable characters in your answer, will count as the answer being encoded in UTF-32
    The exception to the encoding will make your answer be count by characters.
  • Only the function body counts, don't count anything else you do outside it
  • Bonus of -30% if you make a prediction system based on the neighborhood or most common words
  • Bonus of -20% in size if you only return the first 5 matches for each letter corresponding to the first number (e.g.: 245 would returns 5 words starting with 'a', 5 starting with 'b' and 5 starting with 'c').

Here is an example of an implementation, using Javascript:

function f(phone, words)
{
    var keypad=['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz'];
    var regex='';

    for(var i=0,l=phone.length;i<l;i++)
    {
        regex+='['+keypad[phone[i]]+']';
    }

    var regexp=new RegExp('\\s('+regex+'[a-z]*)\\s','gi');

    return words.match(regexp);
}

To run it, open the list link and run, for example:

f('9999',document.getElementsByTagName('pre')[0].innerText);
//returns [" Zyzzogeton "]

This example was tested and works under Opera 12.17 64bits on Windows 7 Home Edition 64bits.

\$\endgroup\$
  • \$\begingroup\$ Is the second argument to the program a file name containing the words or the list of words itself ? \$\endgroup\$ – Optimizer Dec 6 '14 at 20:54
  • \$\begingroup\$ @MartinBüttner UTF-8 isn't unfair (it still counts ASCII chars as being 1 byte), but I changed the rule. \$\endgroup\$ – Ismael Miguel Dec 6 '14 at 20:57
  • \$\begingroup\$ @Optimizer The 2nd argument is a list of the words. You can pass the filename over a compiler argument and read the file, if you want to. But the only thing that counts is the function body. \$\endgroup\$ – Ismael Miguel Dec 6 '14 at 20:58
  • \$\begingroup\$ @MartinBüttner By counting as ASCII, it is being counted as bytes. You want me to say that APL code will have 1 byte having the size of 8 bits? \$\endgroup\$ – Ismael Miguel Dec 6 '14 at 21:00
  • 2
    \$\begingroup\$ -1 for inappropriate restrictions \$\endgroup\$ – AJMansfield Dec 8 '14 at 3:47
3
\$\begingroup\$

CJam, 28 bytes

q~{el{'h-_9/-D+3/}%s1$#!},p;

Takes input in the form of "<number>" [<list of words>]

Example:

"52726" ["Japan" "japan" "Japanee" "Japanese" "Japanesque" "larbowlines" "ablution" "ablutionary" "abluvion" "ably" "abmho" "Abnaki" "abnegate"]

Output:

["Japan" "japan" "Japanee" "Japanese" "Japanesque" "larbowlines"]

Not going for any bonus for now.

Try the code online here but for actual time measurements, run it on the Java compiler

Note that CJam represents empty lists like ""

To convert the raw wordlist into CJam list use the following code with the wordlist as input:

qN/p
\$\endgroup\$
  • \$\begingroup\$ "You will receive 1 phone number in a string and the content of a text file with a list of words" -> can you implement, on a different block, the needed code to read the file into an usable list? \$\endgroup\$ – Ismael Miguel Dec 6 '14 at 21:22
  • \$\begingroup\$ @IsmaelMiguel You mean not the part of this code, but just a helper code to convert the list to correct format ? \$\endgroup\$ – Optimizer Dec 6 '14 at 21:22
  • \$\begingroup\$ Exactly. Which your code isn't enough to prove it can use a list of words as the provided examples. But I upvoted anyway, I just wanted that helper code. \$\endgroup\$ – Ismael Miguel Dec 6 '14 at 21:24
  • \$\begingroup\$ Can you add it to the answer? As an edit, in a different part \$\endgroup\$ – Ismael Miguel Dec 6 '14 at 21:26
  • \$\begingroup\$ Exactly. That's what I'm talking about! Lets see if you can optimize it even further \$\endgroup\$ – Ismael Miguel Dec 6 '14 at 21:28
2
\$\begingroup\$

Java: 395

This forms a regex pattern based on the letters that are allowed for each number, and then tacks on a .* at the end to match any following characters.

Here is the golfed version:

static ArrayList<String> f(String n,ArrayList<String> d){String[] k={"","","([A-Ca-c])","([D-Fd-f])","([G-Ig-i])","([J-Lj-l])","([M-Om-o])","([P-Sp-s])","([T-Vt-v])","([W-Zw-z])"};String r="";for(int i=0;i<n.length();++i)r+=k[n.charAt(i)-'0'];r += ".*";Pattern p=Pattern.compile(r);ArrayList<String> a=new ArrayList<String>();for(String w:dictionary)if(p.matcher(w).matches())a.add(w);return a;}

And here is the ungolfed version for read-ability

public static ArrayList<String> f(String phoneNumber, ArrayList<String> dictionary) {

    String[] KEY_VALUES = {"", "", "([A-Ca-c])", "([D-Fd-f])", "([G-Ig-i])",
                                            "([J-Lj-l])", "([M-Om-o])", "([P-Sp-s])",
                                            "([T-Vt-v])", "([W-Zw-z])"};

    String regex = "";
    for (int i = 0; i < phoneNumber.length(); ++i) {
        regex += KEY_VALUES[phoneNumber.charAt(i) - '0'];
    }
    regex += ".*";
    Pattern p = Pattern.compile(regex);
    ArrayList<String> answers = new ArrayList<String>();
    for (String word : dictionary) {
        if (p.matcher(word).matches()) {
            answers.add(word);
        }
    }
    return answers;
}
\$\endgroup\$
  • \$\begingroup\$ Your code goes against rule number 7: "Variables, macros, global variables, constants, non-standard classes and all the sort passing other values inside the function will be considered invalid." and it kinda goes against rule number 3: "You cannot use or re-implement other's answers or copy my implementation.", but on your code it is kinda debatable. And it also goes against the rule 9: "Your function will be named f". \$\endgroup\$ – Ismael Miguel Dec 7 '14 at 7:24
  • \$\begingroup\$ @IsmaelMiguel Oops. Rule 7 can be easily fixed by moving the constant inside the function. I was just pulling it outside the function for better programming style. Rule 9 is also an easy fix. I confess I didn't read your answer, so I didn't intentionally try to copy it. I can remove my answer if you think it is too close for the contest. \$\endgroup\$ – Brian J Dec 7 '14 at 18:37
  • \$\begingroup\$ Your answer is alright. You have a bug on your code. On the last constant (([W-Zw-z)]) it should be ([W-Zw-z]). And on Code-golf you don't have to worry about programming styles and good practices: your code must simply do it's thing withing the required parameters. If you check my answer, you will see this line: $s=[2=>abc,def,ghi,jkl,mno,pqrs,tuv,wxyz];. This is an awful 'crime' in PHP. Basically I am forcing PHP to convert non-existing constants into strings. This is perfectly acceptable. You will also see that I'm not even setting the variable $t to an array before using it as such \$\endgroup\$ – Ismael Miguel Dec 8 '14 at 1:21
  • \$\begingroup\$ @IsmaelMiguel Good catch on the regex error. Thanks for pointing it out. I'll try to actually golf it tomorrow; maybe find some Java examples on this site. \$\endgroup\$ – Brian J Dec 8 '14 at 1:53
  • \$\begingroup\$ I'm not a java programmer, but I tell you some things. You can check codegolf.stackexchange.com/questions/6671/… to get some tips. General tips include removing useless whitespace (newlines, spaces, tabs), one-letter-long variable names and do all that you can to reduce the code size as much as possible. \$\endgroup\$ – Ismael Miguel Dec 8 '14 at 3:15
1
\$\begingroup\$

C# .NET 4.5 235

This should work:

IEnumerable<string>F(string n,string d){IEnumerable<string>w=d.Split(null).ToList();string[]a={"","","abc","def","ghi", "jkl","mno","pqrs","tuv","wxyz"};foreach(var i in n){w=w.Where(x=>x.IndexOfAny(a[i-'0'].ToArray())>0);}return w;}
\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG. Your code will work, but you still need to reduce it a lot more. By removing all useless whitespace (spaces, tabs, newlines) I have managed to reduce your code to 167 bytes. This code can be reduced a lot more, I'm sure of it. I recommend reading codegolf.stackexchange.com/questions/173/… to shorten even more your code. To help you a little, the word list is a string separated by newlines, and you seem to assume it is already possible to use a foreach in it. If you expect it to already be IEnumerable, include the code used outside \$\endgroup\$ – Ismael Miguel Dec 8 '14 at 13:04
  • \$\begingroup\$ @IsmaelMiguel TY I will look at it. List are a IEnumerable there is no code outside what I posted. \$\endgroup\$ – Chaossie Dec 8 '14 at 18:03
  • \$\begingroup\$ If you look at the specification of the function, you will see the 2nd parameter is also a string. (Quoting: "You will receive 1 phone number in a string and the content of a text file with a list of words (don't assume a specific newline style).") And you have 1 useless whitespace on your a var. \$\endgroup\$ – Ismael Miguel Dec 8 '14 at 21:45
  • \$\begingroup\$ I've noticed the improvements on your question, and I gave you an upvote. But you still can save a byte on your a var. But I really see noticeable improvements! Keep up the good work. \$\endgroup\$ – Ismael Miguel Dec 9 '14 at 13:46
1
\$\begingroup\$

Python 2 (155 bytes)

Should also work in Python 3 with the appropriate replacements (string->bytes, b prefix on strings, etc.).

I wasn't sure if having the maketrans call outside the function is considered "fair"; if not, the function is 134 bytes with it moved inside.

EDIT: Dropped one byte from a stupid oversight.

With prepared maketrans, 67 bytes:

from string import maketrans
t=maketrans('abcdefghijklmnopqrstuvwxyz','22233344455566677778889999')

def f(n,w):
    return[x for x in w.split()if x.lower().translate(t).startswith(n)]

With maketrans in body, 134 bytes:

from string import maketrans

def f(n,w):
    return[x for x in w.split()if x.lower().translate(maketrans('abcdefghijklmnopqrstuvwxyz','22233344455566677778889999')).startswith(n)]

With import and maketrans in body, 155 bytes:

def f(n,w):
    return[x for x in w.split()if x.lower().translate(__import__('string').maketrans('abcdefghijklmnopqrstuvwxyz','22233344455566677778889999')).startswith(n)]

Test call:

print f('9999',open('words.txt','rt').read())
\$\endgroup\$
  • \$\begingroup\$ The maketrans is part of the function body. You should move it. I don't know if it is even possible, but you can try to directly use the import. I think I saw it somewhere... But your code is really nice! \$\endgroup\$ – Ismael Miguel Dec 10 '14 at 22:17
  • \$\begingroup\$ Do you mean to move the import and call into the body? Yes, I think that can be done, too. \$\endgroup\$ – criptych Dec 11 '14 at 13:52
  • \$\begingroup\$ I was thinking about t=(from stirng import maketrans)([...]). I have no idea if it is even possible. But maybe you can use from string import as x t=x([...]) which I'm not sure if it is possible too :/ \$\endgroup\$ – Ismael Miguel Dec 11 '14 at 13:58
  • \$\begingroup\$ The correct version is the last one. But the answer as-is is acceptable in my opinion. +1 for __import__('string').maketran. \$\endgroup\$ – Ismael Miguel Dec 11 '14 at 14:45
  • \$\begingroup\$ OK, thanks. I've removed the invalid answers. \$\endgroup\$ – criptych Dec 11 '14 at 20:08
0
\$\begingroup\$

PHP 5.4+ (171 186-20% = 148.8 bytes):

Well, this is quite a huge answer, but well.

I hope this brings more people to answer.

This function expects the raw content being read.

Here is the code:

function f($_,$a){$s=[2=>abc,def,ghi,jkl,mno,pqrs,tuv,wxyz];$a=preg_split('@\r\n|\r|\n@',$a);for($i=0;$c=$_[$i];++$i)foreach($a as$k=>$v)if(!strpos(1..$s[$c],$v[$i])||$t[$v[0]]++>4)unset($a[$k]);return$a;}

This works by verifying that the letter is in the list of allowed letters.

Example: the input 36 would make to check if 1abc has the first letter of the word and that 1def has the 2nd letter.

I append 1 so it doesn't check if the letter is in the 1st position (which would return 0 and that would evaluate to false). if(!strpos(1..$s[$c],$v[$i])) or if(!strpos($c.$s[$c],$v[$i])) will have the same effect, but the 1st confuses more and I like it.

Failing to do so, will remove the word.

With no words left, it returns an empty array.

To test this online, go to http://writecodeonline.com/php/ and create a simple variable with a word for line.

A testable example:

function f($_,$a)
{
    $s=array(2=>abc,def,ghi,jkl,mno,pqrs,tuv,wxyz);
    $a=preg_split('@\r\n|\r|\n@',$a);

    for($i=0;$c=$_[$i];++$i)
        foreach($a as$k=>$v)
            if(!strpos(1..$s[$c],$v[$i]) || $t[$v[0]]++>4)
                unset($a[$k]);
    return$a;
}

$lines=<<<WORDS
one
two
three
four
five
six
seven
eight
nine
ten
WORDS;

var_dump(f('36',$lines));

This should output:

array(1) {
    [3]=>
      string(4) "four"
}

To work on older php versions, replace $s=[2=>abc,def,ghi,jkl,mno,pqrs,tuv,wxyz]; by $s=array(2=>abc,def,ghi,jkl,mno,pqrs,tuv,wxyz);


For the 20% bonus:

To reduce the code I simply added ||$t[$v[0]]++>4, which checks how many times the first letter was used.

In php, $t doesn't need to be defined, helping to reduce a big chunk of 37.2 bytes.

To see this effect, use the following variable as the 2nd argument:

$lines=<<<WORDS
one
two
three
four
five
six
seven
eight
nine
ten
twelve
time
tutor
test
truth
WORDS;
\$\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.