18
\$\begingroup\$

This challenge is essentially identical to this one with just one difference: it is now allowed to shuffle letters anywhere in the string.

Scenario

John has an important number, and he doesn't want others to see it.

He decided to encrypt the number, using the following steps:

His number is always a non-decreasing sequence (ie. "1123")

He converted each digit into English words. (ie. "123" -> "ONETWOTHREE")

And then, rearrange the letters randomly. (ie. "ONETWOTHREE" -> "EEWOOHRNTET")

John felt that his number were safe in doing so. In fact, such encryption can be easily decrypted :(


Task

Given the encrypted string s, your task is to decrypt it and return the original number.


Rules

  • This is code golf, so the shortest answer in bytes wins
  • You can assume that the input string is always valid
  • The input string only contains uppercase letters
  • The original numbers are always arranged in ascending order
  • You may return the number in string or integer format
  • The letters will only be shuffled between one word, not between the whole string. The letters can be shuffled anywhere in the string.
  • The numbers will only be from 1 to 9 inclusive (ONE to NINE)

Possible Unscrambled String

Here is a list of the strings just after they have been converted to strings from the numbers:

 1 -> ONE 
 2 -> TWO
 3 -> THREE
 4 -> FOUR
 5 -> FIVE
 6 -> SIX
 7 -> SEVEN
 8 -> EIGHT
 9 -> NINE

Examples

"NEO" -> 1

"NWEOOT" -> 12

"TOEERWNEHOT" -> 123

"IHNEVGENNEISTE" -> 789

"WEETVTRFSVUHNEEFRHIXEOINSNIEGTOONIEE" -> 123456789

"EWHEWROETOTTON" -> 1223

"ONEWESTV" -> 27 (thanks, ETHproductions!)

\$\endgroup\$
  • 7
    \$\begingroup\$ Suggested test case: something like "ONEWESTV" -> 27 (includes a number that doesn't actually appear) \$\endgroup\$ – ETHproductions Aug 28 '17 at 15:52
  • \$\begingroup\$ @ETHproductions Great idea! Added. \$\endgroup\$ – Cristian Lupascu Aug 28 '17 at 16:58
  • \$\begingroup\$ Why there is not the "ZERO"? \$\endgroup\$ – RosLuP Aug 29 '17 at 20:33
  • \$\begingroup\$ @RosLuP John hates leading zeroes... \$\endgroup\$ – Cristian Lupascu Aug 29 '17 at 20:42

12 Answers 12

9
\$\begingroup\$

Python 2, 123 bytes

c=map(input().count,"OWHUFXSGIQ")
i=4
for j in"71735539994":c[i*2]-=c[int(j)];i=-~i%5
s=""
for n in c:i+=1;s+=`i`*n
print s

A full program taking quoted input and printing John's number.

Try it online! or see a test-suite

How?

Let's work with the example "NEONSEXTOWNII" (to yield 1269, and be somewhat Leisure Suite Larry-esque!)

First c=map(input().count,"OWHUFXSGIQ") takes input and counts the number of each of OWHUFXSGIQ - these are letters that appear in each number in ascending order, with 2,4,6, and 8 having their "own" letters (WUXG), plus an extra letter, Q to append a zero to the the end and make the length of the resulting list even. For the example:

[2,1,0,0,0,1,1,0,2,0] <- c
 O W H U F X S G I Q  <- is the counts of these letters
 1 2 3 4 5 6 7 8 9 0  <- which "relate to" these digits in John's number
   2   4   6   8   0  <- these will be correct as the letters are unique to their words

The entries for 1, 3, 5, 7, and 9 need adjusting to correct the abundance of the other letters. This is performed by the next loop:

i=4
for j in"71735539994":c[i*2]-=c[int(j)];i=-~i%5

Note that the entries to adjust are alternate ones (1,3,5,7,9,1,3,5,...), so we can add two to an index variable at each step and modulo by 10 to stay in range if we need to traverse more than once (which we do). To save some bytes we can increment by one and modulo by 5 and use double the index.
Since the adjustments for 9 require the most work we start there - it resides at index 8 so we start at i=4. The string "71735539994" then gives the indexes, j, of the values to remove at each stage (where we have ensured the ninth index will contain zero by using "Q" when creating c); c[i*2]-=c[int(j)] performs each individual adjustment and i=-~i%5 moves i to the next index (where -~i is -(-1-i) or i+1 saving parentheses (i+1)%5) keeping i*2 within the bounds of c.
Thus we first subtract the number at index j=7 from that at index i*2=8, subtracting the number of "G"s counted from the number of "I"s, adjusting the "NINE" count down by the (correct) number of "EIGHT"s (which also has an "I"). We then move onto i=0 (-~4%5 = (4+1)%5 = 0), referencing index i*2 = 0 which is for "ONE" and subtract the value found at index j=1 the entry counting "W" and hence "TWO", adjusting the count of "O"s down. By the end of the loop we have the corrected counts:

[1,1,0,0,0,1,0,0,1,0] <- c   (for 1223333448 it would be: [1,2,4,2,0,0,0,1,0,0])
 1 2 3 4 5 6 7 8 9 0

so all that remains is to print out what c now represents (1269). i is now back at 0, so we increment it at the start of the loop and use it as our digit:

s=""
for n in c:i+=1;s+=`i`*n
print s

The back ticks, `i`, are Python2 shorthand for repr(i) which gets a string representation of an object (the digit character in question as a string) and multiplying a string by a number creats a new string of that many repeats (here we only show n=0 turning `i` from say "5" to "" and n=1 turning keeping say "6" as "6", but it also works for larger positive integers, so "3"*4 becomes "3333" for example.)

\$\endgroup\$
8
\$\begingroup\$

05AB1E, 31 bytes

[{‘Z€µ‚•„í†ìˆÈŒšï¿Ÿ¯¥Š‘#NSèJ{Q#

Try it online!

Explanation

[                                   # start loop
 {                                  # sort input
  ‘Z€µ‚•„í†ìˆÈŒšï¿Ÿ¯¥Š‘#            # push the list ['Z','ONE','TWO','THREE','FOUR','FIVE','SIX','SEVEN','EIGHT','NINE']
                        N           # push the current iteration counter
                         S          # split to list of digits
                          è         # index into the list with each
                           J{       # join to string and sort
                             Q#     # if the strings are equal, exit loop
                                    # implicitly print iteration counter

Very inefficient for large input.

\$\endgroup\$
  • \$\begingroup\$ ‘Z€µ‚•„í†ìˆÈŒšï¿Ÿ¯¥Š‘# # push the list ['Z','ONE','TWO','THREE','FOUR','FIVE','SIX','SEVEN','EIGHT','NINE'] : can you explain a little, I struggle to understand how any string can be generated. \$\endgroup\$ – Cyril Gandon Aug 31 '17 at 13:58
  • 1
    \$\begingroup\$ @CyrilGandon: delimits an upper-case compressed string of space separated words. Z means Z. All other 2-symbol pairs denote a compressed word from 05AB1E's dictionary. So for example €µ translates as ONE. \$\endgroup\$ – Emigna Aug 31 '17 at 14:01
  • \$\begingroup\$ Nice, how do you compress a string contains in the dictionary? Something with the unicode value of the pair? \$\endgroup\$ – Cyril Gandon Aug 31 '17 at 14:05
  • 1
    \$\begingroup\$ @CyrilGandon: You take the line number of the word in the dict (2420 for hello) and subtract 1. This gives us 2419. The symbols we need are the symbols which are followed by 24 and 19 in the docs. In our case this is 24=Ÿ and 19=™, so HELLOwould be ‘Ÿ™‘ \$\endgroup\$ – Emigna Aug 31 '17 at 14:11
  • 1
    \$\begingroup\$ There is also a compressor written by Adnan you can use in most instances. The link is a bit long, but you can find it in the 05AB1E chat room. That is also a good place to ask if have any further questions :) \$\endgroup\$ – Emigna Aug 31 '17 at 14:14
8
\$\begingroup\$

Retina, 112 97 bytes

O`.
}`GH
8
X
6
H
3
+`F(.*)O(.*)U
4$1$2
+`O(.*)W
2$1
+`F(.*)V
5$1
+`N(.*)V
7$1
}`NO
1
NN
9
T`L
O`.

Try it online!

-12 bytes thanks to @Neil

-3 bytes by use of L character classes in transposition

How it Works

Basically, this relies on the fact that letters are only used in certain number names. For example SIX is the only name which contains an X. This gets trickier with the fact that some words overlap in letters, such as both FIVE and SEVEN using V. This could be corrected for by identifying FIVE with F(.*)V.

\$\endgroup\$
  • 1
    \$\begingroup\$ @RickHitchcock Fixed. The recursion on conversion to 8 was not working properly \$\endgroup\$ – fireflame241 Aug 28 '17 at 18:27
  • 1
    \$\begingroup\$ @RickHitchcock. Fixed the recursion for all of them. \$\endgroup\$ – fireflame241 Aug 28 '17 at 18:33
  • \$\begingroup\$ Annoyingly GH and NO would be adjacent, except for any previous 8 or 1 from a prior substitution... \$\endgroup\$ – Neil Aug 28 '17 at 20:04
  • \$\begingroup\$ Perhaps }`GH 8 would work for 8 - the } would cause the characters to be sorted again, thus placing any remaining G and H together. \$\endgroup\$ – Neil Aug 28 '17 at 20:07
  • \$\begingroup\$ @Neil Nice idea. I was also able to do that for NO -> 1, which was convenient. \$\endgroup\$ – fireflame241 Aug 28 '17 at 20:33
5
\$\begingroup\$

Kotlin 1.1, 359 352 331 327 325 bytes

Submission

fun r(r:String):String{var s=""
val f=r.split(s).groupingBy{it}.eachCount()
val c=Array(10,{0})
c[8]=f["G"]?:0
c[6]=f["X"]?:0
c[4]=f["U"]?:0
c[2]=f["W"]?:0
c[1]=(f["O"]?:0)-c[2]-c[4]
c[3]=(f["R"]?:0)-c[4]
c[7]=(f["S"]?:0)-c[6]
c[5]=(f["V"]?:0)-c[7]
c[9]=((f["N"]?:0)-c[1]-c[7])/2
for(i in 1..9)for(x in 1..c[i])s+=i
return s}

Does not work on TryItOnline due to Kotlin 1.1 not being supported

Test

fun r(r:String):String{
val f=r.split("").groupingBy{it}.eachCount()
val c=Array(10,{0})
c[8]=f["G"]?:0
c[6]=f["X"]?:0
c[4]=f["U"]?:0
c[2]=f["W"]?:0
c[1]=(f["O"]?:0)-c[2]-c[4]
c[3]=(f["R"]?:0)-c[4]
c[7]=(f["S"]?:0)-c[6]
c[5]=(f["V"]?:0)-c[7]
c[9]=((f["N"]?:0)-c[1]-c[7])/2
var s=""
for(i in 1..9)for(x in 1..c[i])s+=i
return s}

data class TestData(val input: String, val output: String)

fun main(vararg args:String) {
    val items = listOf(
    TestData("NEO" , "1"),
    TestData("NWEOOT" , "12"),
    TestData("TOEERWNEHOT" , "123"),
    TestData("IHNEVGENNEISTE" , "789"),
    TestData("WEETVTRFSVUHNEEFRHIXEOINSNIEGTOONIEE" , "123456789"),
    TestData("EWHEWROETOTTON" , "1223")
    )
    for (item in items) {
        val out = r(item.input)
        if (out != item.output) {
            throw AssertionError("Bad result: $item : $out")
        }
    }
}

Logic

Crib sheet

I used the sheet above to work out the simplest way to solve each letter

  • Green = Solve by itself
  • Blue = Needs greens to solve
  • Orange = Needs blues to solve
  • Red = Needs oranges to solve

Edits

  • -7 - Whitespace changes by w0lf
  • -21 - Shrank listOf to Array
  • -4 - Removed unneeded brackets
  • 0 - Added logic in
  • -2 - Re-using empty string thanks to kevin-cruijssen
\$\endgroup\$
  • 1
    \$\begingroup\$ Just noticed I'm exactly tied with you with my Java 8 answer (127 bytes), using a similar approach. ;) But one question: can't you change var s="" and return s to r="" and return r by reusing the input-String, which you no longer need at that point? I never programmed in Kotlin before, so it could be that I talk nonsense here. ;p \$\endgroup\$ – Kevin Cruijssen Aug 29 '17 at 13:45
  • 1
    \$\begingroup\$ Unfortunately not > discuss.kotlinlang.org/t/… \$\endgroup\$ – jrtapsell Aug 29 '17 at 14:38
  • 1
    \$\begingroup\$ Ah yes, that was of course a possibility; parameters being final by default. Hmm, one other thing you might be able to golf: Place the var s="" as the first thing in the method, and replace val f=r.split(""). with val f=r.split(s).. Again, no idea if it works. Too bad TIO doesn't support v1.1 yet, otherwise I would try these suggestions myself before I make myself sound stupid.. \$\endgroup\$ – Kevin Cruijssen Aug 29 '17 at 15:07
4
\$\begingroup\$

Jelly, 37 bytes

1ðDị“©ȯ¿w¶&ÇhṆỌƘ#Ȯʋ~¢CNẓ_»ŒuḲ¤ẎŒ!ċð1#

Try it online!

-1 thanks to Jonathan Allan.

\$\endgroup\$
  • \$\begingroup\$ This times out for some inputs larger than 7 characters (ex: NINEFIVE, THREEFIVE). Is it a bug, or is the code just inefficient? \$\endgroup\$ – Cristian Lupascu Aug 28 '17 at 17:08
  • \$\begingroup\$ @w0lf the latter (Œ! means "permutations") \$\endgroup\$ – Erik the Outgolfer Aug 28 '17 at 17:12
  • \$\begingroup\$ Save a byte using "AA" rather than "!": ...“©ȯ¿w¶&ÇhṆỌƘ#Ȯʋ~¢CNẓ_»... \$\endgroup\$ – Jonathan Allan Aug 28 '17 at 17:12
  • \$\begingroup\$ @JonathanAllan oh is AA a word? \$\endgroup\$ – Erik the Outgolfer Aug 28 '17 at 17:13
  • \$\begingroup\$ It's the first word in the short dictionary, yes. \$\endgroup\$ – Jonathan Allan Aug 28 '17 at 17:13
3
\$\begingroup\$

Java 8, 248 234 bytes

s->{int x=0,a[]=new int[10];for(String t:"2WO;4UORF;6XSI;8GI;5FI;7S;3R;1O;9I".split(";"))for(;s.indexOf(t.charAt(1))>=0;a[t.charAt(0)-48]++)for(String z:t.split(""))s=s.replaceFirst(z,"");for(s="";x++<9;)for(;a[x]-->0;)s+=x;return s;}

Code Explanation:

s->{
    // Array to count how often which number appears
    int a[]=new int[10];
    // The first character behind the number serves the identification
    // the other characters get removed to identify the other numbers later
    for(String t:"2WO;4UORF;6XSI;8GI;5FI;7S;3R;1O;9I".split(";"))
        // Check if the string contains the id 
        for(;s.indexOf(t.charAt(1))>=0;a[t.charAt(0)-48]++)
            // Remove the relevant charcters
            for(String z:t.split(""))
                s=s.replaceFirst(z,"");
    // Clear the string to write the output
    s="";
    // write the numbers sequential into the output 
    for(int x=0;x++<9;)
        for(;a[x]-->0;)
            s+=x;
    return s;
}

-14 Thanks to Olivier Grégoire

\$\endgroup\$
2
\$\begingroup\$

Java 8, 346 345 344 336 327 bytes

s->{int g=c(s+=" ","G"),u=c(s,"U"),w=c(s,"W"),x=c(s,"X"),f=c(s,"F")-u,h=c(s,"H")-g,v=c(s,"V")-f,o=c(s,"O")-u-w,i=c(s,"I")-f-x-g;return d(s=d(s=d(s=d(s=d(s=d(s=d(s=d(s=d("",o,1),w,2),h,3),u,4),f,5),x,6),v,7),g,8),n,9);}int c(String...s){return~-s[0].split(s[1]).length;}String d(String s,int i,int n){for(;i-->0;s+=n);return s;}

Try it here.

General explanation:

I've looked at the occurrences of each character in the alphabet:

E 13357789
F 45
G 8
H 38
I 5689
N 1799
O 124
R 34
S 67
T 238
U 4
V 57
W 2
X 6
  • I first counted all occurrences of the single-matches characters: G=8; U=4; W=2; X=6.
  • Then all occurrences of two-matched characters, which also match one of the four above, which I can subtract from their counts: F=5; H=3.
  • Then I did the same again for V=7 (by subtracting F=5).
  • Then the same for all three-matches characters that were left: O=1; N=9.
    • But because N has two occurrences in NINE, I had to do an additional -1 for every occurrence of N, so I've used I=9 instead (by subtracting three previous matches instead of two).

Code Explanation:

s->{                    // Method with String as parameter and return-type
  int g=c(s+=" ","G"),  //  Amount of 8s (and append a space to `s` first, for the .split)
      u=c(s,"U"),       //  Amount of 4s
      w=c(s,"W"),       //  Amount of 2s
      x=c(s,"X"),       //  Amount of 6s
      f=c(s,"F")-u,     //  Amount of 5s
      h=c(s,"H")-g,     //  Amount of 3s
      v=c(s,"V")-f,     //  Amount of 7s
      o=c(s,"O")-u-w,   //  Amount of 1s
      i=c(s,"I")-f-x-g; //  Amount of 9s
  return d(             //  Return the result by:
   s=d(
    s=d(
     s=d(
      s=d(
       s=d(
        s=d(
         s=d(
          s=d("",       //   Making the input String `s` empty, since we no longer need it
                 o,1),  //   Append all 1s to `s`
         w,2),          //   Append all 2s to `s`
        h,3),           //   Append all 3s to `s`
       u,4),            //   Append all 4s to `s`
      f,5),             //   Append all 5s to `s`
     x,6),              //   Append all 6s to `s`
    v,7),               //   Append all 7s to `s`
   g,8),                //   Append all 8s to `s`
  i,9);                 //   And then returning `s` + all 9s
}                       // End of method

int c(String...s){  // Separate method with String-varargs parameter and int return-type
                    //  `s[0]` is the input-String
                    //  `s[1]` is the character to check
  return~-s[0].split(s[1]).length;
                    //  Return the amount of times the character occurs in the String
}                   // End of separated method (1)

String d(String s,int i,int n){
               // Separate method with String and two int parameters and String return-type
  for(;i-->0;  //  Loop from the first integer-input down to 0
      s+=n     //   And append the input-String with the second input-integer
  );           //  End of loop
  return s;    //  Return the resulting String
}              // End of separated method (2)
\$\endgroup\$
  • 1
    \$\begingroup\$ Damn, I would have thought that adding to a list then sorting it would be shorter (it's not). Well done! \$\endgroup\$ – Olivier Grégoire Aug 29 '17 at 13:17
  • 1
    \$\begingroup\$ Well, in the end, I outgolfed you, but not by much ;) \$\endgroup\$ – Olivier Grégoire Aug 29 '17 at 14:18
2
\$\begingroup\$

Perl 5, 100 bytes

99 bytes code + 1 byte for -n switch.

${$_}++for/./g;@a=($O-$W-$U,$W,$H-$G,$U,$F-$U,$X,$S-$X,$G,$I-$F+$U-$X-$G);print$_ x$a[$_-1]for 1..9

Try it online!

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

Python 3, 225 bytes

def f(s):
	r=[]
	for i,w in zip([2,4,6,8,3,5,7,1,9],["WTO","UFOR","XSI","GEIHT","HTREE","FIVE","VSEEN","ONE","NINE"]):
		while s.count(w[0]):
			r+=[i]
			for l in w:s="".join(s.split(l,1))
	return "".join(sorted(map(str,r)))

Try it online!

Straightforward: remove the digits which are identified by a specific letter first.

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

Python 3, 125 bytes

lambda s:''.join(min(w)*(2*sum(map(s.count,w[:2]))-sum(map(s.count,w)))for w in"O1WU W2 H3G U4 F5U X6 S7X G8 IUFXG9".split())

Try it online!

After reading the linked challenge I realized this is a variation on mdahmoune's Python solution, which is itself based on Draco18s's ES6 solution, but hey, at least we golfed off two bytes.

Like that solution, we compute the answer through a linear combination of the number of occurrences of certain letters. We encode the linear combinations briefly by writing them as words where the first two letters are to be added and everything afterwards is to be subtracted. Sometimes a character is needed to pad the first two characters; we use this to hide the digit we want to output (which will never occur in the input, so won't affect our algorithm), which we extract with min.

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

R, 154

u=utf8ToInt(s)-71
m=sum
b=m(u==16)
d=m(u==14)
f=m(u==17)
a=m(u==8)-b-d
g=m(u==12)-f
cat(rep(1:9,c(a,b,m(u==11)-d,d,m(u==15)-g,f,g,m(!u),(m(u==7)-a-g)/2)))

Try it online!

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

Axiom, 351 bytes

s:="GXUWRFVIONETHS";e:EqTable(CHAR,INT):=table();v:=[8,6,4,2,3,5,7,9,1];z:=[k for k in 1..46|prime?(k)];F(x,y)==>for i in 1..#x repeat y;F(z,e.(s.i):=z.i);t:=[1787026,2451,16445,5957,16036207,130169,20372239,495349,20677];h(a)==(r:=1;F(a,r:=r*e.(a.i));j:=[];F(v,while r rem z.i=0 repeat(r:=r quo t.i;j:=cons(v.i,j)));j:=sort j;k:=0;F(j,k:=k*10+j.i);k)

ungolfed commented results

s:="GXUWRFVIONETHS" -- tutte le lettere di ONE..NINE in ordine di importanza 
e:EqTable(Character,Integer):=table()
v:=[8,6,4,2,3,5,7,9,1]              -- numeri da controllare in quell'ordine di apparizione di v
z:=[k for k in 1..46|prime?(k)]     -- 14 numeri primi da associare a s
F(x,y)==>for i in 1..#x repeat y 
F(z,e.(s.i):=z.i)                   -- riempie la tavola associando numeri primi alle lettere "GXUW..."
t:=[1787026,2451,16445,5957,16036207,130169,20372239,495349,20677]  -- prodotto di numeri primi 1787026 dovrebbe essere HEIGHT
h(a)==
     r:=1 ;F(a,r:=r*e.(a.i))        -- calcola il numero associato alla stringa a
     j:=[];F(v,while r rem z.i=0 repeat(r:=r quo t.i;j:=cons(v.i,j)));j:=sort j  -- leva il nome dei numeri che man mano trova, aggiunge a j
     k:=0 ;F(j,k:=k*10+j.i)         -- costruisce il numero decimale k, da j vettore ordinato
     k                              -- ritorna tale numero k
------------------------------------------------------
(8) -> h("IHNEVGENNEISTE")
   (8)  789
                                                    Type: PositiveInteger
\$\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.