Your challenge is to sort a string, but rather than by the normal alphabetical order (abc..xyz), you will be sorting strings by a specified alphabet.
You must write a program or function that takes two inputs: An alphabet A and an string S. Both will only contain lowercase English letters, and both will contain at least one character.
You must move letters in S so that the letter that appears first in A appears first, then whichever letter appears second in A, etc. There may be some letters in S that do not appear in A, these should be left at the end and not moved around relative to each other.
Test cases:
A S Result
axd haxuizzxaxduxha aaaxxxxdhuizzuh
a xyz xyz
abc dcba abcd
il nmiuplliu iillnmupu
asdf qwerty qwerty
Fewest bytes wins!
-
\$\begingroup\$ Can we print/return an array of singleton strings? Can we take one string and one array of singleton strings as input? \$\endgroup\$Dennis– Dennis2018年05月28日 03:47:52 +00:00Commented May 28, 2018 at 3:47
-
\$\begingroup\$ @Dennis Yes, both are fine representations of strings. \$\endgroup\$Pavel– Pavel2018年05月28日 03:56:20 +00:00Commented May 28, 2018 at 3:56
-
\$\begingroup\$ Can we take either or both inputs as an array of individual characters? \$\endgroup\$Shaggy– Shaggy2018年05月28日 12:29:34 +00:00Commented May 28, 2018 at 12:29
-
\$\begingroup\$ @Shaggy A string is a character array, so yes. \$\endgroup\$Pavel– Pavel2018年05月28日 14:45:17 +00:00Commented May 28, 2018 at 14:45
25 Answers 25
Python 3, (削除) 50 47 46 (削除ここまで) 44 bytes
-3 bytes thanks to ngn!
-1 byte thanks to mypetlion
lambda a,s:s.sort(key=lambda c:a.find(c)%27)
Takes in a string as the alphabet and a list of chars as the string and sorts the list in place.
The %27 ensures that if the character is not in the alphabet, the index returned puts it after the rest of the alphabet.
Haskell, 42 bytes
a#s=[c|c<-a,d<-s,c==d]++[c|c<-s,all(/=c)a]
a#s= -- take alphabet a and string s
c<-a -- for all c in a
d<-s -- for all d in s
[c| c==d] keep c if c equals d
++ -- append
[c|c<-s ] -- all c of s
,all(/=c)a -- that are not in a
Perl 6, (削除) 55 (削除ここまで) 43 bytes
->\A,\S{[~] S.comb.sort:{%(A.comb.antipairs){$_}//∞}}
->\A,\S{[~] S.comb.sort:{A.index($_)//∞}}
Expanded:
-> \A, \S {
[~] # reduce using &infix:«~» (shorter than `.join`)
S.comb.sort: # split into character list and sort by:
{ # bare block lambda with implicit parameter $_
A.index( $_ ) # get the position
// # if it is undefined (not in `A`)
∞ # return Inf instead (so it comes at end of result)
}
}
-
\$\begingroup\$ Since there will only be up to 26 different characters in the input, and ∞ is 3 bytes, you can replace it with 27 and it'll still work and save a byte. \$\endgroup\$Pavel– Pavel2018年11月06日 16:45:50 +00:00Commented Nov 6, 2018 at 16:45
Haskell, (削除) 40 (削除ここまで) 34 bytes
-6 bytes huge thanks to Laikoni.
foldr(\c->r(==c)<>r(/=c))
r=filter
The first line is an expression that takes two arguments: S and A.
-
1\$\begingroup\$ Nice! You can even drop
f=because anonymous functions are allowed. \$\endgroup\$Laikoni– Laikoni2018年05月29日 12:18:14 +00:00Commented May 29, 2018 at 12:18 -
1\$\begingroup\$ Furthermore
(<>)is now in Prelude, so this can be shortened tofoldr(\c->r(==c)<>r(/=c))for 34 bytes: Try it online! \$\endgroup\$Laikoni– Laikoni2018年05月29日 13:30:27 +00:00Commented May 29, 2018 at 13:30
05AB1E, 4 bytes
Rvy†
Explanation
R # Reverse the alphabet
vy # For each letter ...
† # Push S with the current letter filtered to the front
-
\$\begingroup\$ Smarter than
Σ²sk>. \$\endgroup\$Magic Octopus Urn– Magic Octopus Urn2018年05月31日 23:22:01 +00:00Commented May 31, 2018 at 23:22 -
\$\begingroup\$ Too bad about
R€†working as expected though :). Sometimes that can work as a smallervyloop. Nice answer man. \$\endgroup\$Magic Octopus Urn– Magic Octopus Urn2018年05月31日 23:28:48 +00:00Commented May 31, 2018 at 23:28
Python 2, 38 bytes
def f(a,s):s.sort(None,a[::-1].find,1)
a must be a string, s a list of strings of length 1. f sorts s in place.
Alternate version, string I/O, 48 bytes
lambda a,s:`sorted(s,None,a[::-1].find,1)`[2::5]
How it works
s.sort(None,a[::-1],1) is shorthand for s.sort(cmp=None,key=a[::-1],reverse=1).
From the docs:
reverse is a boolean value. If set to
True, then the list elements are sorted as if each comparison were reversed.
-
\$\begingroup\$ TIL sort can take 4 arguments. \$\endgroup\$Pavel– Pavel2018年05月28日 04:11:03 +00:00Commented May 28, 2018 at 4:11
-
\$\begingroup\$ Only in Python 2. Python 3 deprecated
cmpand madekeyandreversekeyword-only arguments, so itslist.sorttakes only one positional argument. \$\endgroup\$Dennis– Dennis2018年05月28日 04:19:00 +00:00Commented May 28, 2018 at 4:19
J, 5 bytes
]/:i.
Dyadic verb, taking the alphabet on its left and the string to be sorted on the right.
i. finds the indeces of string's characters in the alphabet, the alphabet length if not found.
'axd' i. 'haxuizzxaxduxha'
3 0 1 3 3 3 3 1 0 1 2 3 1 3 0
/: sorts its left agrument according to the order specified in the right one.
] the rigth argument (the string)
'haxuizzxaxduxha' /: 3 0 1 3 3 3 3 1 0 1 2 3 1 3 0
aaaxxxxdhuizzuh
APL (Dyalog Unicode), 5 bytes SBCS
Anonymous tacit prefix function, taking [string,ordering] as argument.
⍋⍨/⌷⊃
.../ Reduce by the following function:
...⍨ namely the reversed-arguments version of the following function:
⍋ grade the right string according to the left ordering (missing letters go at the end)
⌷ use that to index into...
⊃ the first element of the argument (i.e. the string)
Python 2, (削除) 35 (削除ここまで) 50 bytes
lambda a,s:sorted(s,key=lambda c:-a[::-1].find(c))
Takes a and s as strings; returns a list of singelton strings.
Note: Ouch! Gained 15 bytes to fix...
-
-
1\$\begingroup\$ @Jo King: Stop controlling my thoughts! :) \$\endgroup\$Chas Brown– Chas Brown2018年05月31日 06:06:41 +00:00Commented May 31, 2018 at 6:06
K (ngn/k), 9 bytes
{y@>-x?y}
{...} is a function with arguments x and y
x?y finds for each element in y the index of its first occurrence in x; if an element is not found in x, its index is considered 0N (-263)
- negates all indices except that it keeps the 0N-s intact, because 263≡-263 (mod 264)
> returns a sort-descending permutation
y@ indexes y with that
Charcoal, 13 bytes
×ばつιNoηιΦη¬Noθι
Try it online! Link is to verbose version of code. Explanation:
θ First input
F Loop over characters
η Second input
ι Current character
No Count matches
ι Current character
×ばつ Repeat
Implicitly print
η Second input
Φ Filter
θ First input
ι Current character
No Count matches
¬ Logical not
Implicitly print non-matching characters
Jelly, 4 bytes
fⱮ;ḟ
A dyadic link accepting the string on the left and the alphabet on the right (as lists of characters) and returning the result (also as a list of characters).
How?
fⱮ;ḟ - Link: string; alphabet e.g. smallnotxl; xl
Ɱ - map (for each character in the alphabet): 1=x; 2=l
f - filter keep (keep occurrences of this character from string) x lll -> xlll
ḟ - filter discard (discard all alphabet characters from string) smanot
; - concatenate xlllsmanot
JavaScript (SpiderMonkey), 50 bytes
Takes input in currying syntax (a)(s), where a is a string and s is an array of characters. Returns an array of characters.
a=>s=>s.sort((b,c)=>(g=c=>-1/a.search(c))(b)-g(c))
How?
We define the helper function g() as:
c => -1 / a.search(c)
which returns:
- 1 if c does not belong to the alphabet
- a float value in [-Inf, 0) based on the position of c in the alphabet otherwise (-Inf, -1, -1/2, -1/3, etc.)
We sort s[ ] by computing g(b) - g(c) for each pair of characters (b, c) passed to the callback of sort().
Because the implementation of sort() in SpiderMonkey is stable, all characters of s[ ] that do not belong to the alphabet are simply moved at the end in order of appearance and are let unchanged when they are compared with each other.
JavaScript (ES6), 61 bytes
Takes input in currying syntax (a)(s), where both a and s are arrays of characters. Returns a string.
a=>s=>a.map(C=>s=s.filter(c=>c!=C||!(o+=c)),o='')&&o+s.join``
R, (削除) 69 62 (削除ここまで) 58 bytes
function(a,s)c(rep(a,rowSums(outer(a,s,"=="))),s[!s%in%a])
Input and output are vectors of individual characters.
Explanation:
function(a,s)c( , ) #combine:
a, #[each char in a
rep( #each repeated
rowSums( ) #the number of
outer(a,s,"==") #occurrence in s]
s #with s
[ s%in%a] #all chars in a
! #omitted
Brain-Flak (BrainHack), 118 bytes
{({}(<>))<>}{}<>{<>([[]()]<{<>(({})<({}<>[({}<>)]){(<()>)}{}{}>)<>}<>({}<{({}<>)<>}<>>)>[]){({}()<(({}))>)}{}{}<>{}}<>
Input is the first string, followed by a null, followed by the second string. A version that uses a newline as the separator instead adds 24 bytes:
Brain-Flak, 142 bytes
(()){{}(({}(<>))[(()()()()()){}]<>)}{}<>{<>([[]()]<{<>(({})<({}<>[({}<>)]){(<()>)}{}{}>)<>}<>({}<{({}<>)<>}<>>)>[]){({}()<(({}))>)}{}{}<>{}}<>
Explanation
# Move A to other stack reversed
# Zeroes are pushed under each character for later.
# (This is the only part that needs to change in order to use newline as separator.)
{({}(<>))<>}{}<>
# For each character in A, starting at the end:
{
# Track current length of S.
<>([[]()]<
# For each character in S:
{
# While keeping character from A
<>(({})<
# Move character from S to second stack and push difference
({}<>[({}<>)])
# Delete character if equal
{(<()>)}{}{}
>)
<>}
# Move S back to first stack while maintaining character from A
<>({}<{({}<>)<>}<>>)
# Push difference between old and new lengths of S
>[])
# Insert character from A at beginning of S that many times
{({}()<(({}))>)}{}{}
<>{}}<>
C (gcc), 97 bytes
f(D,d,S,s,i,o)char*D,*S;{
while(d--){
for(i=o=s;i--;)S[i]-D[d]?S[--o]=S[i]:0;
while(o--)S[o]=D[d];
}
}
All whitespaces (spaces and newlines) in the code above are only for readability and should be removed.
The dictionary is passed in D and have length d, the string is passed in S and have length s. i and o should be omitted.
Pyth, (削除) 9 (削除ここまで) 5 bytes
ox+vz
ox+vz Full program. Input format: "S" \n "A". o Sort the characters of S by (variable: N)... x ... N's index in... +vz ... A + N
Java 8, 98 bytes
a->s->{for(int i=a.length;i-->0;s=s.replaceAll("[^"+a[i]+"]","")+s.replaceAll(a[i],""));return s;}
Explanation:
a->s->{ // Method with String-array and String parameters, and String return-type
for(int i=a.length;i-->0;
// Loop backwards over the alphabet
s= // Replace the current `s` with:
s.replaceAll("[^"+a[i]+"]","")
// All the current characters of `a` in `s`
+s.replaceAll(a[i],""));
// Concatted with everything else
return s;} // Return the modified `s`
-
\$\begingroup\$ Couldn't go lower, even with Java 11's new
String.repeat(int)method. Nice! :) \$\endgroup\$Olivier Grégoire– Olivier Grégoire2018年05月29日 14:34:54 +00:00Commented May 29, 2018 at 14:34 -
\$\begingroup\$ @OlivierGrégoire Oh, didn't knew early access to Java 11 was already available. That
.repeat(n)looks promising, though. :D \$\endgroup\$Kevin Cruijssen– Kevin Cruijssen2018年05月29日 14:48:37 +00:00Commented May 29, 2018 at 14:48
-
\$\begingroup\$ Isn't there a flag that gives you
$_=<>;for free? \$\endgroup\$Pavel– Pavel2018年05月28日 14:39:55 +00:00Commented May 28, 2018 at 14:39 -
\$\begingroup\$ @Pavel yeah, sorry I'm using it to populate
@F, but I didn't add it to the header! I'll do that now! Thank you! \$\endgroup\$Dom Hastings– Dom Hastings2018年05月28日 17:37:59 +00:00Commented May 28, 2018 at 17:37 -
\$\begingroup\$ You can cut 10 bytes off this and still use the same logic: Try it online! \$\endgroup\$Xcali– Xcali2019年08月16日 03:46:04 +00:00Commented Aug 16, 2019 at 3:46
Prolog (SWI), 136 bytes
X/_/[X|_].
X/Y/[Z|R]:-Y\=Z,X/Y/R.
i(_,X,[],[X]).
i(A,X,[Y|R],[X,Y|R]):-X/Y/A.
i(A,X,[Y|R],[Y|S]):-i(A,X,R,S).
A*S*T:-foldl(i(A),S,[],T).
Try it online! Example usage:
[i,l]*[n,m,i,u,p,l,l,i,u]*S.
S = [i, i, l, l, n, m, u, p, u]
Clean, 61 bytes
import StdEnv
$a s=[c\\c<-a,k<-s|k==c]++[c\\c<-s|all((<>)c)a]
Defines the function $ :: [Char] [Char] -> [Char].
Unsurprisingly, this is literally nimi's Haskell answer but longer.
APL+WIN, 12 bytes
Prompts for screen input of S then A:
s[(,⎕)⍋s←,⎕]
PynTree, 13 bytes
§yz:ṡzCæf+yxx
Port of Jo King's Python answer.
Explanation
§yz:ṡzCæf+yxx Anonymous lambda
§ lambda ,
y y
z z
: :
ṡ sorted( ,lambda x:
z z
C ( )( )
æf ( ).find
+ +
y y
x x
x x