17
\$\begingroup\$

Let \$ A \$ represent the alphabet, such that \$ A_1 = \$ a and \$ A_{26} = \$ z.

Let's define that a word \$ W = w_1 w_2 ... w_n \$ (where \$ w_c \in A\$) is in standard order if and only if:

  • \$ w_1 = A_1 \$, and
  • for \$ 2 \le i \le n \$, if \$ w_i = A_x \$ then \$ w_j = A_{x-1} \$ for some \$ j < i \$ and some \$x\$.

In other words, the word must start with a and each other letter can only appear in a word if the preceding letter in the alphabet has already appeared. Equivalently, if we take only the first appearance of each unique letter in the word, the resulting word is a prefix of the alphabet.

For example, ac is not in standard order, because there is no b before the c.

The following relationships exist between the property of standard order and some others (this list is mainly here for searchability):

Task

Given a string of letters, determine if it is in standard order according to the Latin alphabet.

Test cases

Truthy:

a
aaa
abab
aabcc
abacabadabacaba
abcdefghijklmnopqrstuvwxyzh

Falsey:

b
ac
bac
abbdc
bcdefghijklmnopqrstuvwxyza
abracadabra

Rules

  • You should represent true and false outputs using any two distinct values of your choice
  • You may assume the input is non-empty and only contains lowercase ASCII letters
  • Alternatively, you may accept input as a list of integers representing alphabet indices (in either \$ [0, 25] \$ or \$ [1, 26] \$, at your option)
  • You may use any standard I/O method
  • Standard loopholes are forbidden
  • This is , so the shortest code in bytes wins
\$\endgroup\$
1
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – pxeger
    Jan 20 at 18:21

24 Answers 24

5
\$\begingroup\$

JavaScript (Node.js), 27 bytes

a=>a.every(n=>a[-n]=a[1-n])

Try it online!

Input as an array of 1~26 integers.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ How on earth does this work‽ \$\endgroup\$
    – pxeger
    Jan 21 at 6:48
  • \$\begingroup\$ @pxeger I think it's something to do with JS letting you actually set negative indices (rather than having wrap-around indexing like Python), so as it encounters letters it sets the corresponding negative index to undefined if the previous one hasn't been seen and... some truthy thing? if it has. Feel like there might be a counterexample bvut it's still clever as fuck \$\endgroup\$ Jan 21 at 7:04
  • 1
    \$\begingroup\$ @UnrelatedString The truthy thing is a[0], the first letter of input. \$\endgroup\$
    – tsh
    Jan 21 at 10:24
4
\$\begingroup\$

x86 32-bit machine code, 13 bytes

b0 61 38 02 7f 05 1c ff 42 e2 f7 d6 c3

Try it online!

Following the fastcall calling convention, this takes the length of the string in ECX and the address of the string in EDX, and returns in AL, -1 for standard order and 0 for not standard order.

Assembly:

f:  mov al, 0x61    # 'a' -- AL will hold the highest acceptable letter.
r:  cmp [edx], al   # Compare -- Letting c be the current letter, calculate c - AL.
    jg b            # If c > AL, the word is not in standard order; jump out.
    sbb al, 0xFF    # Here, the carry flag CF is 1 if c < AL and 0 if c = AL.
                    # Subtract 255+CF from AL. This leaves AL unchanged if c < AL
                    #  while increasing it by 1 if c = AL.
    inc edx         # Advance the pointer.
    loop r          # Loop, counting down from the length in ECX.
b:  .byte 0xD6      # Undocumented SALC instruction -- sets AL to -CF.
                    #  If the word is not in standard order, CF = 0 from the CMP.
                    #  If it is in standard order, CF = 1 from the SBB,
                    #   as INC and LOOP leave CF unchanged.
    ret             # Return.
\$\endgroup\$
4
\$\begingroup\$

Jelly, 3 bytes

QJƑ

Try It Online!

Takes input as one-indexed alphabet indices.

QJƑ    Main Link
Q      Uniquify
 JƑ    Is it equal to [1, 2, 3, ..., len]?
\$\endgroup\$
1
  • \$\begingroup\$ Ha, even our explanations are almost exactly the same. \$\endgroup\$
    – Jonah
    Jan 20 at 18:48
4
\$\begingroup\$

Vyxal, 4 bytes

U:ż⁼

Try it Online!

Takes a list of nonnegative integers.

U    # Uniquify
   ⁼ # Is equal to
 :ż  # 1...length?
\$\endgroup\$
4
\$\begingroup\$

Python 3, 39 32 bytes

Thanks @xnor for saving 2 bytes by proposing this approach (going from right to lefft)
Thanks @loopy walt for golfing a further 3 bytes

def f(L):len({*L})>L.pop()!=f(L)

Try it online!

Takes in a list of integers from 0 to 25. Throws exception if the numbers are in standard order, otherwise terminates without exception (aka returns through exit code).

Check if the last element is less than the number of unique elements in the list:

  • If true, recurs on the remaining list (after the last element has been removed). If the list is in order, then we'll eventually run out of elements after some recursions, throwing an exception on L.pop().
  • If false, then that last element must not be in order, in which case the comparison short circuited and the function terminates.
\$\endgroup\$
4
  • 2
    \$\begingroup\$ I don't think terminating by exit code per se is allowed for functions because they must be reusable, but anyway you're covered by the more direct rule allowing exceptions for boolean outputs. \$\endgroup\$
    – pxeger
    Jan 20 at 20:40
  • 1
    \$\begingroup\$ 37 bytes by going from right to left \$\endgroup\$
    – xnor
    Jan 21 at 2:20
  • 1
    \$\begingroup\$ 34 \$\endgroup\$
    – loopy walt
    Jan 21 at 3:21
  • \$\begingroup\$ best one yet surculose! \$\endgroup\$
    – DialFrost
    Jan 21 at 13:10
3
\$\begingroup\$

JavaScript (V8), 35 bytes

a=>[...new Set(a)].some((x,i)=>x^i)

Try it online!

takes input as an array with integers representing 0-indexed alphabet indices. returns false for valid words, and true for invalid words

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

JavaScript (ES6), 30 bytes

Expects a list of 0-based indices. Returns false for valid or true for invalid.

a=>a.some(c=>c*!a[a[-c-2]=~c])

Try it online!

Commented

a =>            // a[] = input array, re-used as an object to keep track of
                //       characters that have already appeared in the list
a.some(c =>     // for each code c in a[]:
  c *           //   return true if c is not equal to 0
  !a[           //   and the following entry is defined:
    a[-c - 2] = //     set a[-c - 2] to a non-zero value
    ~c          //     use -c - 1 as the lookup value
  ]             //   end of test
)               // end of some()
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 26 bytes

(l=#)&@@@Tally@#==Range@l&

Try it online!

Input a list of alphabet indices, 1-indexed.

   # &@@@Tally@#            deduplicate
(l= )           ==Range@l   equal to (1...(last unique value))?
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 3 bytes

ÙāQ

Input as a 1-based integer-list.

Try it online or verify all test cases.

If we take the actual lowercase letters as input, it would have been 5 bytes instead:

AIÙÅ?

Try it online or verify all test cases.

Explanation:

Ù     # Uniquify the (implicit) input-list
 ā    # Push a list in the range [1,length] (without popping)
  Q   # Check if both lists are equal
      # (after which the result is output implicitly)

A     # Push the lowercase alphabet
 I    # Push the input-string
  Ù   # Uniquify this input-string
   Å? # Check if the lowercase alphabet starts with this uniquified input
      # (after which the result is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

Haskell + hgl, 9 bytes

fsw β<nb

Explanation

nb takes the string and removes all but the first occurrence of every character. fsw takes two lists and determines if the first one starts with the second. β is the lowercase alphabet. So all in all this asks if the first occurrence of every character forms a prefix of the alphabet.

You can replace β with nn for numbers 0 through 25 and nN for numbers 1 through 26.

Reflections

This does well. For once there's not too much to say here.

  • An "is this sorted" builtin might be nice but because the string must start with a it would require that as a second check and it wouldn't save anything on this challenge.
  • I also noticed there is no upper case alphabet builtin, which there should probably be. It doesn't make a difference to this answer though.
\$\endgroup\$
2
\$\begingroup\$

Factor, 31 30 bytes

[ members 26 iota swap head? ]

Try it online!

Explanation

Get the unique elements of the input, preserving order, and check whether that is a prefix of the alphabet(ic indices).

          ! { 0 1 0 1 }
members   ! { 0 1 }
26 iota   ! { 0 1 } { 0 1 2 ... 25 }
swap      ! { 0 1 2 ... 25 } { 0 1 }
head?     ! t
\$\endgroup\$
2
\$\begingroup\$

Nibbles, 5 bytes (9 nibbles)

==;`$_,,@

Verbose

==   # Equals?
  ; `$ _   #   Uniq of input, save it
  , , @   # Range from 1 to length of saved value

Variant with alphabet (8 bytes / 15 nibbles)

==.;`$@-$'`',,@

Verbose

==   # Equals?
  .   # Map
    ; `$ @   #   Uniq of input, save it
    - $ '`'   #   Subtract '`'
  , , @   # Range from 1 to length of saved value
\$\endgroup\$
2
\$\begingroup\$

R, 35 bytes

function(W)any(seq(u<-unique(W))-u)

Try it online!

Takes input as a vector of integers from 1 to 26. Outputs FALSE for truthy and TRUE for falsey.

\$\endgroup\$
2
  • \$\begingroup\$ Can't R compare vectors for equality directly, rather than using any + not-equal? \$\endgroup\$
    – pxeger
    Jan 20 at 21:09
  • \$\begingroup\$ @pgexer, nope, it's elementwise with recycling if necessary (unfortunately in this problem). \$\endgroup\$
    – pajonk
    Jan 20 at 21:10
2
\$\begingroup\$

Brachylog, 3 bytes

d~⟦

Try it online!

Takes 0-indices into the alphabet.

d      The nub of the input
 ~⟦    is the range from 0 to something.

Brachylog, 5 bytes

d~a₀Ạ

Try it online!

Takes a string of lowercase letters.

d        The nub of the input
 ~a₀     is a prefix of
    Ạ    the lowercase alphabet.
\$\endgroup\$
2
\$\begingroup\$

Shue, 67 65 bytes

Shue confirmed less verbose than Java ????

Takes input as a list of unary numbers (1-26) separated by ",", with a trailing ",". Returns "LR" for yes, and "FR" for no.

=L
=R
L1,=L>,
L,=L
>1=1>
>,1=,>
,,=,
>,R=,R
LR
L11=F
F1=F
F,=F
FR

Try it online!

Explanation

=L      - Left edge
=R      - Right edge
L1,=L>, - Decrement the first element, which is 1, create triangle
L,=L    - Remove a 0 without creating a triangle
>1=1>   - Triangle passes trough ones
>,1=,>  - Triangle decrements the next element
,,=,    - Remove zeros since they don't affect the result
>,R=,R  - Delete triangle when it reaches the end
LR      - Success
L11=F   - Failure, the first element is 2 or greater
F1=F    - Propagate failure
F,=F    - Propagate failure
FR      - Failure

Rough pseudocode

def is_valid(array):
    if array == []:
        return True
    if array[0] == 0:
        return is_valid(array[1:])
    elif array[0] == 1:
        return is_valid(array[1:]-1)
    else:
        return False
\$\endgroup\$
2
\$\begingroup\$

BQN, 3 bytesSBCS

Takes input as a list in \$[0, 25]\$.

≡⟜⊐

Run online!

BQN's primitive Classify basically converts a sequence to "standard order" in non-negative integers. As the input uses the same domain we can simply check if the result of that matches the input.

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

J, 9 bytes

(-:#\)@~.

Try it online!

Input is 1-based indices of the alphabet letters.

  • @~. Take the unique (preserves order) and...
  • (-:#\) Check if it equals 1 2 3 ... <length of uniq>.
\$\endgroup\$
0
1
\$\begingroup\$

SNOBOL4 (CSNOBOL4), 90 bytes

	I =INPUT
N	I LEN(1) . X	:F(O)
	O =O X
	&LCASE O	:F(END)
R	I X =	:S(R)F(N)
O	OUTPUT =1
END

Try it online!

Same "check if unique characters are a prefix of the alphabet" algorithm others have posted.

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

Retina 0.8.2, 30 bytes

D`.
^
$'¶
T`l`@l`^.+
^@(.*)¶\1

Try it online! Link includes test cases. Explanation:

D`.

Remove duplicate letters.

^
$'¶

Duplicate the remaining letters.

T`l`@l`^.+

Shift the letters in the first copy back by 1, e.g. abcd becomes @abc.

^@(.*)¶\1

Check that the second copy starts with the tail of the first copy, which is only possible if this is a prefix of the alphabet.

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

Charcoal, 10 bytes

¬⌕βΦθ⁼κ⌕θι

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for standard order, nothing if not. Explanation:

 ⌕          Index of
    θ       Input string
   Φ        Filtered where
      κ     Current index
     ⁼      Equals
       ⌕    First index of
         ι  Current letter
        θ   In input string
  β         In predefined variable lowercase alphabet
¬           Equals zero
            Implicitly print
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 66 63 62 bytes

r;m;f(char*s){for(r=0,m=96;*s;++s)r|=*s-m==1?m=*s,0:*s>m;m=r;}

Try it online!

Inputs a word as a string.
Returns \$0\$ if the word is in standard order or \$1\$ otherwise.

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

Java, 68 bytes

l->{int[]x={0};return l.stream().distinct().allMatch(i->i==x[0]++);}

Takes input as a List of alphabet indices.

Try it online!

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

Python 3 - 47 bytes

Thanks to @pxeger and @m90

lambda a:[*range(len(u:={}.fromkeys(a)))]==[*u]

Input is a list of integers from [0,25]. All it does is remove duplicates and makes sure that each integer is equal to its position. Output is inverted, which is allowed.

Attempt it online!

Python 3.8 - 50 bytes

Thanks to @pxeger for -12 bytes here.

lambda a,i=0:any(k^(i:=i+1)for k in{}.fromkeys(a))

Input is a list of integers from [1,26]. All it does is remove duplicates and makes sure that each integer is equal to its position. Output is inverted, which is allowed.

Try it online! (Function output is inverted, but I inverted it back in the footer of the interpreter)

Python 3 - 58 bytes

Thanks to @m90.

lambda a:0in map(int.__eq__,{}.fromkeys(a),range(len(a)))

Input is a list of integers from [0,25]. All it does is remove duplicates and makes sure that each integer is equal to its position. Outputs are inverted, which is allowed.

Try it online!

\$\endgroup\$
8
  • 2
    \$\begingroup\$ dict.fromkeys can be {}.fromkeys: see this tip of mine \$\endgroup\$
    – pxeger
    Jan 20 at 19:45
  • 1
    \$\begingroup\$ If you change i==j to i^j and change all to any, you can save a byte (output becomes inverted, but that's allowed) \$\endgroup\$
    – pxeger
    Jan 20 at 19:50
  • 1
    \$\begingroup\$ Improvement to 58: lambda a:all(map(int.__eq__,{}.fromkeys(a),range(len(a)))) \$\endgroup\$
    – m90
    Jan 20 at 19:54
  • 1
    \$\begingroup\$ I just realised you can remove both sets of [] from your original answer, which makes it shorter overall: lambda a:any(i^j for i,j in enumerate({}.fromkeys(a))) \$\endgroup\$
    – pxeger
    Jan 20 at 20:07
  • 3
    \$\begingroup\$ down to 47 bytes by combining both answers \$\endgroup\$
    – pxeger
    Jan 20 at 20:49
1
\$\begingroup\$

Dyalog APL, 7 bytes

⍳∘≢∘∪≡∪

Takes input as integers from 1 to 26.

Try it online!

\$\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.