17
\$\begingroup\$

Given a list of two or more spelled-out serial numbers of equal length greater than two, e.g.

[[ "three" , "one"  , "four"  ],
 [ "one"   , "five" , "nine"  ],
 [ "two"   , "six"  , "five"  ],
 [ "three" , "five" , "eight" ]]

sort the list by the numbers that the words represent:

[[ "one"   , "five" , "nine"  ],
 [ "two"   , "six"  , "five"  ],
 [ "three" , "one"  , "four"  ],
 [ "three" , "five" , "eight" ]]

You may require the numbers to be spelled in lower or upper, but not mixed, case.

Test cases

[["three","one","four"],["one","five","nine"],["two","six","five"],["three","five","eight"]]
gives
[["one","five","nine"],["two","six","five"],["three","one","four"],["three","five","eight"]]

[["two","seven"],["one","eight"],["two","eight"],["one","eight"],["two","eight"],["four","five"]]
gives
[["one","eight"],["one","eight"],["two","seven"],["two","eight"],["two","eight"],["four","five"]]

[["one","four","one","four","two"],["one","three","five","six","two"],["three","seven","three","zero","nine"]]
gives
[["one","three","five","six","two"],["one","four","one","four","two"],["three","seven","three","zero","nine"]]

[["zero","six","one"],["eight","zero","three"],["three","nine","eight"],["eight","seven","four"],["nine","eight","nine"],["four","eight","four"]]
gives
[["zero","six","one"],["three","nine","eight"],["four","eight","four"],["eight","zero","three"],["eight","seven","four"],["nine","eight","nine"]]

\$\endgroup\$
  • \$\begingroup\$ Not sure if I got this correctly, does ["three","one","four"] === 314? \$\endgroup\$ – Nit Apr 9 '18 at 20:05
  • \$\begingroup\$ @Nit Yes, that's right. \$\endgroup\$ – Adám Apr 9 '18 at 20:06
  • \$\begingroup\$ @Nit By the numbers they spell out. E.g. [314,159,265,358][159,265,314,358]. \$\endgroup\$ – Adám Apr 9 '18 at 20:09
  • \$\begingroup\$ Can we assume a certain arbitrary capitalization of the numbers? \$\endgroup\$ – dylnan Apr 9 '18 at 20:27
  • \$\begingroup\$ @dylnan You may require the numbers to be spelled in lower or upper, but not mixed, case. \$\endgroup\$ – totallyhuman Apr 9 '18 at 20:28

23 Answers 23

14
\$\begingroup\$

Husk, 9 8 bytes

Ö†€¨tfṡn

Try it online!

Algorithm "inspired" by recursive's Stax answer (I've just changed the lookup string a bit), go upvote him!

The trick is mapping each letter to its position in the string tfsen (compressed at the end of this program). Husks lists are 1-based, and missing items return 0, so we get this mapping:

"one"        [0,5,4]
"two"        [1,0,0]
"three"      [1,0,0,4,4]
"four"       [2,0,0,0]
"five"       [2,0,0,4]
"six"        [3,0,0]
"seven"      [3,4,0,4,5]
"eight"      [4,0,0,0,1]
"nine"       [5,0,5,4]

As you can see, the lists are perfectly ordered.


In order to be clear, here's how list comparison works in Husk (and in many other languages):

  1. If one of the two lists is empty, that's the smaller one.
  2. If the first elements of the two lists are different, the one with the smaller first element is the smaller list.
  3. Otherwise, discard the first element from both lists and go back to point 1.
\$\endgroup\$
  • \$\begingroup\$ If I'm not mistaken, the "w" can be dropped also, since it's only useful comparing "two" to "three", but you already have "h". Not sure if that helps you. I haven't figured out how to integrate this fact into a stax program that's actually smaller yet. \$\endgroup\$ – recursive Apr 9 '18 at 21:53
  • \$\begingroup\$ ...if it were just the letters it could be tfrsen but I'm guessing having words like with and sen in there helps compression. \$\endgroup\$ – Jonathan Allan Apr 9 '18 at 22:22
  • \$\begingroup\$ Thank you guys, you inspired me to find an even shorter string :D \$\endgroup\$ – Leo Apr 10 '18 at 4:36
  • \$\begingroup\$ So, it's like replacing the commas with a decimal point after the first comma? \$\endgroup\$ – Strawberry Apr 11 '18 at 11:03
  • \$\begingroup\$ @Strawberry Not really, [1,0,0] is considered smaller than [1,0,0,0] (but for this program it wouldn't make a difference) \$\endgroup\$ – Leo Apr 11 '18 at 11:44
10
\$\begingroup\$

Stax, 24 22 17 16 14 bytes

▄Ωφ▐╧Kìg▄↕ñ▼!█

Run and debug it

This program takes arrays of lowercase spelled digits for input. The output is newline-separated like so.

one five nine
two six five
three one four
three five eight

This program sorts the inputs using the ordering obtained under a specific transformation. Each character in each word is replaced by its index in the string "wo thif sen". The original arrays are sorted by this ordering. Then the results are printed after joining with a space.

The spaces serve no purpose, but actually allow greater compression in the string literal.

\$\endgroup\$
  • \$\begingroup\$ What encoding does Stax use? This is 32 bytes in UTF-8. \$\endgroup\$ – OldBunny2800 Apr 9 '18 at 22:00
  • 5
    \$\begingroup\$ Modified CP437, like the "bytes" hyperlink explains. \$\endgroup\$ – recursive Apr 9 '18 at 22:06
  • \$\begingroup\$ Is there some standard algorithm/method of coming up with such a string? Does the concept have a name? \$\endgroup\$ – Itai Apr 10 '18 at 12:15
  • \$\begingroup\$ @Itai: It seems like it would, but I'm not aware what it is. \$\endgroup\$ – recursive Apr 10 '18 at 12:54
6
\$\begingroup\$

Jelly, 12 bytes

OḌ%⁽Т%147µÞ

A monadic link.

Try it online! ...or see the test-suite

How?

Converting the digits to ordinals and then from base 10 then taking modulos by 4752 then 147 gives an ascending order:

 zero            , one         , two         , three               , four
[122,101,114,111],[111,110,101],[116,119,111],[116,104,114,101,101],[102,111,117,114]
 133351          , 12301       , 12901       , 1276511             , 114384
 295             , 2797        , 3397        , 2975                , 336
 1               , 4           , 16          , 35                  , 42

 five            , six         , seven               , eight               , nine
[102,105,118,101],[115,105,120],[115,101,118,101,110],[101,105,103,104,116],[110,105,110,101]
 113781          , 12670       , 1263920             , 1126456             , 121701
 4485            , 3166        , 4640                , 232                 , 2901
 75              , 79          , 83                  , 85                  , 108

This can then be used as a key function by which to sort:

OḌ%⁽Т%147µÞ - Link: list of lists of lists of characters
          µÞ - sort (Þ) by the mondadic chain to the left (µ):
O            -   ordinals of the characters
 Ḍ           -   convert from base 10
   ⁽Т       -   literal 4752
  %          -   modulo
      %147   -   modulo by 147
\$\endgroup\$
  • \$\begingroup\$ That's some wonderful modulos you have found right there, I assume that was painstaking. \$\endgroup\$ – Erik the Outgolfer Apr 9 '18 at 22:33
  • \$\begingroup\$ Not all that painstaking - I did look at binary first though. \$\endgroup\$ – Jonathan Allan Apr 9 '18 at 22:37
  • \$\begingroup\$ Like, you brute-forced the modulos, no? \$\endgroup\$ – Erik the Outgolfer Apr 9 '18 at 22:39
  • \$\begingroup\$ Yeah, but it was quick. \$\endgroup\$ – Jonathan Allan Apr 9 '18 at 23:10
6
\$\begingroup\$

Python, 62 bytes

lambda m:sorted(m,key=lambda r:[int(s,36)%6779%531for s in r])

Try it online! ...or see the test-suite

Note:

lambda m:sorted(m,key=lambda r:[map("trfsen".find,s)for s in r])

which works in Python 2 (but not 3) is longer by two bytes.

\$\endgroup\$
  • 1
    \$\begingroup\$ How did you discover the magic numbers? \$\endgroup\$ – mbomb007 Apr 10 '18 at 19:59
  • 1
    \$\begingroup\$ Just a nested loop checking for strict increasing over the results. Although I possibly restriced the digit length of the inner given the outer. \$\endgroup\$ – Jonathan Allan Apr 10 '18 at 20:04
5
\$\begingroup\$

APL (Dyalog Classic), 12 bytes

'nesft'∘⍒⌷¨⊂

Try it online!

This is how I found a suitable left argument for dyadic (I tried and length 6 first):

A←⊖a←↑'zero' 'one' 'two' 'three' 'four' 'five' 'six' 'seven' 'eight' 'nine'
{(a≡a[⍵⍒a;])∧A≡a[⍵⍒A;]:⎕←⍵}¨,⊃∘.,/5⍴⊂∪∊a
\$\endgroup\$
3
\$\begingroup\$

Perl 6, 37 bytes

*.sort:{('digit 'X~$_)».parse-names}

Try it

Expanded:

*\     # WhateverCode lambda (this is the parameter)
.sort:
{  # block with implicit parameter 「$_」
  (
    'digit ' X~ $_  # concatenate 'digit ' to each named digit
  )».parse-names    # call .parse-names on each
}

The code block will take a value of the form ("three","one","four") and translate it to ("3","1","4") which is a value that .sort can easily use.

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

APL (Dyalog), 38 bytes

{⍵[⍋(531∘⊥⍤1)(531|6779|36⊥9+⎕A⍳⊢)¨↑⍵]}

Try it online!

Based of Jonathan Allan's awesome solution.

\$\endgroup\$
  • 1
    \$\begingroup\$ @JonathanAllan I edited a credit during the initial changetime.. I have no idea why it was unchanged. fixed now \$\endgroup\$ – Uriel Apr 9 '18 at 21:28
  • 1
    \$\begingroup\$ 31: ⊂⌷¨⍨∘⍋(531⊥531|6779|36⊥9+⎕A⍳⊢)¨, but you can do this much simpler in less than half of your current byte count. \$\endgroup\$ – Adám Apr 9 '18 at 21:36
  • \$\begingroup\$ @Adám so, you tolerate input and output in different formats (mixed vs unmixed)? \$\endgroup\$ – ngn Apr 9 '18 at 23:06
  • \$\begingroup\$ @ngn Sure. But the solution I have in mind has fully mixed I/O. \$\endgroup\$ – Adám Apr 9 '18 at 23:21
3
\$\begingroup\$

Ruby, 48 bytes

->x{x.sort_by{|y|y.map{|s|s.to_i(35)**2%47394}}}

Abuses the fact that "zero".to_i(35) is 0 (since 'z' isn't a valid digit in base 35), so it's that much easier to brute-force a formula for the other nine digits.

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

K (ngn/k), 14 bytes

{x@<"tfsen"?x}

Try it online!

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

JavaScript (Node.js), 70 bytes

a=>a.sort((a,b)=>(g=a=>a.map(c=>99+parseInt(2+c,34)%607%292))(a)>g(b))

Try it online!

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

Ruby, 47 bytes

->x{x.sort_by{|y|y.map{|s|s.to_i(32)%774%538}}}

Try it online!

Utilises the fact that using a base less than the maximum digit yields a result of zero (as pointed out by histocrat in their answer)

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

Python 2, 85 81 80 bytes

Simply uses the first two letters of each word to determine the number, then sorts each list using that indexing function as the key.

lambda _:sorted(_,key=lambda L:['zeontwthfofisiseeini'.find(s[:2])/2for s in L])

Try it online!

Saved 4 bytes, thanks to Jonathan Allan

\$\endgroup\$
  • \$\begingroup\$ A for loop list comprehension in the key function is 4 bytes shorter. \$\endgroup\$ – Jonathan Allan Apr 9 '18 at 21:00
1
\$\begingroup\$

Ruby, 49 bytes

->x{x.sort_by{|y|y.map{|s|s.to_i(36)**4%463595}}}

Try it online!

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

05AB1E, 27 bytes

Σ“¡×€µ‚•„í†ìˆÈŒšï¿Ÿ¯¥Š“#skJ

Try it online!


Σ                           # Sort input by...
 “¡×€µ‚•„í†ìˆÈŒšï¿Ÿ¯¥Š“     # "zero one two three four five size seven eight nine"
                       #    # Split on spaces.
                        sk  # Find index of each input...
                          J # Join up.
\$\endgroup\$
  • \$\begingroup\$ 25 bytes \$\endgroup\$ – Kaldo Apr 10 '18 at 7:38
  • \$\begingroup\$ @Kaldo ah... encoding the starting 2 letters of each? I feel like that should be its own answer. \$\endgroup\$ – Magic Octopus Urn Apr 10 '18 at 16:32
1
\$\begingroup\$

Haskell, 133 122 109 107 106 bytes

import Data.List
sortOn$abs.read.(>>=show.head.(`elemIndices`words"ze on tw th fo fi si se ei ni").take 2)

Ungolfed:

import Data.List

nums = ["ze","on","tw","th","fo","fi","si","se","ei","ni"]

lookup' :: Eq a => a -> [a] -> Int
lookup' v = head . elemIndices v

wordToInt :: String -> Int
wordToInt (x:y:_) = lookup' [x,y] nums

wordsToInt :: [String] -> Int
wordsToInt = read . concatMap (show . wordToInt)

sortN :: [[String]] -> [[String]]
sortN = sortOn wordsToInt
\$\endgroup\$
1
\$\begingroup\$

Python 2, 59 bytes

lambda m:sorted(m,key=lambda r:[hash(s)%2249518for s in r])

Try it online!

Riffing on Jonathan Allan's Python 3 solution...

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

Java (JDK 10), 132 bytes

l->{l.sort((a,b)->s(a)-s(b));}
int s(String[]a){int v=0;for(var s:a)v=v*99+"zeontwthfofisiseini".indexOf(s.substring(0,2));return v;}

Try it online!

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

Ruby, 64 bytes

->a{a.sort_by{|b|b.map{|n|"zeontwthfofisiseeini".index n[0,2]}}}

Try it online!

A lambda accepting a 2D array of strings and returning a 2D array of strings.

Piggybacking off of mbomb007's Python 2 answer for -26 bytes off of what I was about to post.

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

Perl 5, 103 bytes

sub c{pop=~s%(..)\w+\s*%zeontwthfofisiseeini=~/$1/;$`=~y///c/2%ger}say s/\R//gr for sort{c($a)<=>c$b}<>

Try it online!

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

Retina 0.8.2, 38 bytes

T`z\o\wit\hfsen`d
O`
T`d`z\o\wit\hfsen

Try it online! Link includes test suite. Works by temporarily replacing the letters zowithfsen with their position in that string, which allows the numbers to be sorted lexically.

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

Jelly, 30 28 27 bytes

w@€“¡¦ẇṆb~ṇjṚØ%ĖġṘḥḞṾṇJḌ»µÞ

Try it online!

-1 thanks to Jonathan Allan.

Finds the index of each digit in the string ‘onetwo...nine’ then sorts using this as a key function with Þ. Don't need to include 'zero' at the beginning because the search for the first two characters of 'zero' will fail and 0 will be returned instead of an index, making 'zero' lexicographically "early".

\$\endgroup\$
  • \$\begingroup\$ Using a compression of 'one two ...nine' is one byte less \$\endgroup\$ – Jonathan Allan Apr 9 '18 at 21:20
  • \$\begingroup\$ @JonathanAllan Ah, thanks. I hadn't thought to check that. Compressing 'zeontw...ni' ended up being longer. \$\endgroup\$ – dylnan Apr 9 '18 at 21:24
  • \$\begingroup\$ ...no longer "...the first two letters". \$\endgroup\$ – Jonathan Allan Apr 9 '18 at 23:09
0
\$\begingroup\$

Python 3, 141 bytes

print(sorted(eval(input()),key=lambda l:int(''.join([str("zero one two three four five six seven eight nine".split().index(i))for i in l]))))

Try it online!

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

C (clang), 229 bytes

y,j,k,t[9];char *s="zeontwthfofisiseeini";r(char **x){for(j=y=k=0;k+1<strlen(*x);k+=j,y=y*10+(strstr(s,t)-s)/2)sscanf(*x+k,"%2[^,]%*[^,]%*[,]%n",t,&j);return y;}c(*x,*y){return r(x)-r(y);}f(*x[],l){qsort(&x[0],l,sizeof(x[0]),c);}

Try it online!

There is no straightforward way of sending array of array of strings to C functions, so in spirit of code-golf, I have taken a minor liberty in input format.

f() accepts an array of pointers to strings, where each string is a number, represented by comma separated spelled-out-digits in lower-case. Additionally, it needs number of strings in array in second parameter. I hope this is acceptable.

f() replaces the pointers in place in sorted order using qsort().
r() reads input number from comma-separated number string. It only compares first two characters to identify number.
c() is comparison function

\$\endgroup\$
  • 1
    \$\begingroup\$ 207 bytes \$\endgroup\$ – ceilingcat Jan 22 at 21:16
  • \$\begingroup\$ @ceilingcat Can you please explain strstr("i"-19,t)-"zeontwthfofisiseeini"? Is it compiler-specific or standard? \$\endgroup\$ – GPS Feb 22 at 10:25
  • \$\begingroup\$ That relies on there being no other patterns in .rodata that look like 0x69 0x00 and the compiler placing the address of "i" at the end of "zeo..." \$\endgroup\$ – ceilingcat Feb 22 at 10:31
  • \$\begingroup\$ thought so.. is there a way to ensure compiler does that? I know rules here would allow this but, could I depend on this in real wold? \$\endgroup\$ – GPS Feb 22 at 10:41
  • \$\begingroup\$ My instinct is to avoid this in the "real world" but this will probably work well if your string fragments are sufficiently unique. There may actually be some legitimate use case perhaps related to stack canaries but I also might just be hallucinating. \$\endgroup\$ – ceilingcat Feb 22 at 10:48

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.