Example: nieignhtesevfouenr ans: 9874
Someone please answer this question. Thank You.
3 Answers
You can apply this algorithm:
First count the occurrence of each letter in the input string. For example, the example input string has these occurrences:
{ "e": 4, "f": 1, "g": 1, "h": 1, "i": 2, "n": 3, "o": 1, "r": 1, "s": 1, "t": 1, "u": 1, "v": 1, "w": 0, "x": 0, "z": 0 }I also included unused letters, as they would play a role in "two", "six" and "zero", but they are not represented in this example input.
Now we can observe that:
- Every "z" in the input belongs to a "zero";
- Every "w" belongs to a "two";
- Every "u" belongs to a "four";
- Every "x" belongs to a "six";
- Every "g" belongs to an "eight"
If you find the number of "z" in the input string, you can deduct there are that many occurrences of "zero", and you can deduct that count from "z", "e", "r", and "o". That many "0" should be recorded for the output.
Once we have done that for the above, we can continue with the following:
- Every remaining "o" belongs to a "one" (since all "zero", "two", "four" were already accounted for by this time).
- Every remaining "h" belongs to a "three"
- Every remaining "f" belongs to a "five"
- Every remaining "s" belongs to a "seven"
And after those have been accounted for, we can finally conclude that:
- Every remaining "i" belongs to a "nine"
We can simplify a bit, because some letters don't really play a role in deciding which digits are represented. For instance, in the above logic, we don't care about the number of "n" or "e", so we might as well not reduce their count when we detect a "one", ...etc. The only 10 letters we care about are listed above.
Finally we use the counts for each digit to build the sorted string.
Here is an implementation in JavaScript. It runs the algorithm for the example input. There is no input validation... It is assumed to be a valid combination of digit names:
// reference data. The identifying letter is put at the front,
// and the letters that still matter for another digit
// follow it.
let map = [
["zo", "0"],
["wo", "2"],
["ufo", "4"],
["xis", "6"],
["gih", "8"],
["o", "1"],
["h", "3"],
["fi", "5"],
["s", "7"],
["i", "9"]
];
// The algorithm
function decimals(s) {
// Count occurrences of letters
let charCount = {};
for (let c of "efghinorstuvwxz") charCount[c] = 0;
for (let c of s) charCount[c]++;
// Recognise digits by their identifying letter
let digitCount = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
for (let [name, digit] of map) {
let frequency = charCount[name[0]];
for (let letter of name) charCount[letter] -= frequency;
digitCount[digit] = frequency;
}
// Build the result string
let result = "";
for (let digit of "9876543210") result += digit.repeat(digitCount[digit]);
return result;
}
// Example run
let result = decimals("nieignhtesevfouenr");
console.log(result);@trincot fired the first shot with a clever algorithm in javascript.
Here is an adaptation in python, with mostly the same logic:
def unscramble(s):
sc = collections.Counter(s)
return list(itertools.chain.from_iterable(
[[9]*(sc['i'] - sc['x'] - sc['g'] - (sc['f']-sc['u'])),
[8]*sc['g'],
[7]*(sc['s']-sc['x']),
[6]*sc['x'],
[5]*(sc['f']-sc['u']),
[4]*sc['u'],
[3]*(sc['h'] - sc['g']),
[2]*sc['w'],
[1]*(sc['o'] - sc['z'] - sc['w'] - sc['u']),
[0]*sc['z']]))
For comparison, here is a bruteforce method in python, which tries every combination of numbers (with some checks to avoid iterating through combinations which obviously wouldn't have the correct length). The bruteforce solution is about 100 times slower on the input string 'nieignhtesevfouenr'.
import itertools
def unscramble_bruteforce(s):
s = ''.join(sorted(s))
for r in range(len(unscramble.d)):
if unscramble.min_lengths[r] <= len(s) <= unscramble.max_lengths[r]:
for c in itertools.combinations(unscramble.d, r):
if sum(len(n) for n in c) == len(s):
if ''.join(sorted(''.join(c))) == s:
return sorted([unscramble.d[n] for n in c], reverse=True)
return None
unscramble.d = { ''.join(sorted(n)): i for i,n in enumerate(['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine', 'ten', 'eleven', 'twelve']) }
unscramble.max_lengths = [max(sum(len(n) for n in c) for c in itertools.combinations(unscramble.d, r)) for r in range(len(unscramble.d))]
unscramble.min_lengths = [min(sum(len(n) for n in c) for c in itertools.combinations(unscramble.d, r)) for r in range(len(unscramble.d))]
print(unscramble('nieignhtesevfouenr'))
# [9, 8, 7, 4]
To compare a combination such as ['eight', 'seven', 'four', 'nine'] with the scrambled input string 'nieignhtesevfouenr', we sort both strings alphabetically: ''.join(sorted(s)) is compared with ''.join(sorted(''.join(c))). Alternatively, we could have compared two multisets / collections.Counter objects, counting the occurrences of every distinct character in both string and checking that they correspond. Asymptotically, this should be more efficient, but in practice on the input string 'nieignhtesevfouenr', it turned out to be about 40% slower.
Here is my approach based on the count of the frequency of characters & greedily check unique letters like "z" for "zero" & also consider that 2 "n" are required for "nine", etc.
#include<bits/stdc++.h>
using namespace std;
// Problem : Derive Telephone Number
void solve(string s)
{
unordered_map<char,int> mp;
for(int i=0;i<s.length();i++){
if(s[i]>='A' && s[i]<='Z') s[i]+=32;
mp[s[i]]++;
}
int ans[11]={};
ans[6] += min(mp['s'],min(mp['i'],mp['x']));
mp['s']-=ans[6];mp['i']-=ans[6];mp['x']-=ans[6];
ans[8] += min(mp['e'],min(mp['i'],min(mp['g'],min(mp['h'],mp['t']))));
mp['e']-=ans[8];mp['i']-=ans[8];mp['g']-=ans[8];mp['h']-=ans[8];mp['t']-=ans[8];
ans[2] += min(mp['t'],min(mp['w'],mp['o']));
mp['t']-=ans[2];mp['w']-=ans[2];mp['o']-=ans[2];
ans[4] += min(mp['f'],min(mp['o'],min(mp['u'],mp['r'])));
mp['f']-=ans[4];mp['o']-=ans[4];mp['u']-=ans[4];mp['r']-=ans[4];
ans[0]+=min(mp['z'],min(mp['e'],min(mp['r'],mp['o'])));
mp['z']-=ans[0];mp['e']-=ans[0];mp['r']-=ans[0];mp['o']-=ans[0];
ans[3] += min(mp['t'],min(mp['h'],min(mp['r'],mp['e']/2)));
mp['t']-=ans[3];mp['h']-=ans[3];mp['r']-=ans[3];mp['e']-=2*ans[3];
ans[7] += min(mp['s'],min(mp['e']/2,min(mp['v'],mp['n'])));
mp['s']-=ans[7];mp['e']-=2*ans[7];mp['v']-=ans[7];mp['n']-=ans[7];
ans[5] += min(mp['f'],min(mp['i'],min(mp['v'],mp['e'])));
mp['f']-=ans[5];mp['i']-=ans[5];mp['v']-=ans[5];mp['e']-=ans[5];
ans[1] += min(mp['o'],min(mp['n'],mp['e']));
mp['o']-=ans[1];mp['n']-=ans[1];mp['e']-=ans[1];
ans[9] += min(mp['n']/2,min(mp['i'],mp['e']));
mp['n']-=2*ans[9];mp['e']-=ans[9];mp['i']-=ans[9];
for(int i=9;i>=0;i--){
while(ans[i]--) cout<<i;
}
cout<<endl;
}
int main(){
string s = "OfNTiWenINeOVE";
solve(s);
s = "zWRoTeorzeo";
solve(s);
s = "FISEVENVETHNINEREONEE"; // 97531
solve(s);
s = "ninenineninesevensevensevensevenfivefivethreethreethreethreeoneoneoneoneoneoneoneone"; //999777755333311111111
solve(s);
}
Related