Is this a half-sort?

Question

The problem over here introduces an new type of strings: if you split the string into equal halfs and swap the pairs, it produces the same output as sorting the string. We call that a half-sort.

Given a purely ASCII string, check if the string is in a half-sort.

An example of a half-sort string

The string node is a half-sort string, because if you sort by codepoints (note that the codepoints are in decimal, not binary):

n 110
o 111
d 100
e 101

That gets turned into:

d 100
e 101
n 110
o 111

You'll see that the node to deno conversion is exactly moving the right half to the left position.

Specification

• For odd-length strings, splitting should make the first half longer.
• Sorting a string means sorting the string based on the codepoints of the characters.

Reference program & test cases

Here is the reference program I made for checking my test cases.

node -> True
rum  -> True
aaa  -> True

deno -> False
rim  -> False

Answer 1

Python 3, 45 42 bytes

-3 bytes thanks to @dingledooper

lambda s:sorted(s)==s+[s.pop(0)for c in s]

Try it online!

Takes input as a list of characters. Returns True if the list is half-sorted, False otherwise.

How

[s.pop(0)for c in s] gets the first half of the list. After this is evaluated, s only has the later half left.

Thus s+[s.pop(0)for c in s] is the list with the 2 halves swapped. Note that this works because Python evaluates anything inside square brackets first.

I then check if the swapped list is sorted, aka compare it with sorted(s).

Answer 2

J, ^{20 18 15} 14 bytes

-1 thanks to Jonah.

Goes the other way around: sorts the string ('node' -> 'deno'), rotates it back ('deno' -> 'node') and checks if this equals the input. Fits better J trains.

-:<.@-:@#|./:~

Try it online!

How it works

-:<.@-:@#|./:~
           /:~  sort input
  <.@-:@#       length of input, halved and floored
         |.     rotate sorted input by that amount
-:              input equal to that?

Answer 3

Pyth, 8 bytes

qSzs_c2z

Try it online!

---

Luckily, Pyth offers most of what we need out of the box, so we just need to call the operations necessary.

 Sz       # Sort the input
     c2z  # Chop the input into two equal pieces (first longer if needed)
    _     # Reverse the chopped elements
   s      # Join them back together
q         # Check for equality

Answer 4

perl -plF//, 49 bytes

push@F,splice@F,0,(@F+1)/2;$_="@F"eq"@{[sort@F]}"

Try it online!

Splits a line of input into characters, which are placed in @F. We remove the first half and tag it to the end. We then check whether the array is the same if we sort it -- if the result is the same, the string was a half sort, if not, it wasn't.

Outputs 1 for a half sort, the empty string when not.

Answer 5

Jelly, 6 bytes

ŒHṚFṢƑ

A monadic Link accepting a list of characters which yields 1 (truthy) if a half-sort and 0 (falsey) otherwise.

Try it online!

How?

Fairly straightforward in Jelly, pretty much just implements the challenge specification directly...

ŒHṚFṢƑ - Link: list of characters (full Unicode, but works with ASCII only too)
ŒH     - split it into two halves (first half 1-longer if odd in length)
  Ṛ    - reverse
   F   - flatten back to a list of characters
     Ƒ - is invariant under?:
    Ṣ  -   sort

Answer 6

05AB1E, 7 bytes

{I2äRJQ

Try it online or verify all test cases.

Explanation:

{        # Sort the characters in the (implicit) input
 I       # Push the input again
  2ä     # Split it into 2 equal-sized parts (first part will be longer for odd lengths)
    R    # Reverse this pair
     J   # Join them back together to a string
      Q  # And check if both strings are equal
         # (after which the result is output implicitly)

Answer 7

Charcoal, 22 bytes

≔⪫⮌⪪θ⊘⊕Ｌθωθ¬⊙θ∧κ‹ι§θ⊖κ

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

≔⪫⮌⪪θ⊘⊕Ｌθωθ

Split the string into half, reverse, and join.

¬⊙θ∧κ‹ι§θ⊖κ

Check whether any characters are less than their predecessor.

Answer 8

APL+WIN, 39 36 bytes

Prompts for input of string:

(⍴s)=+/1,2≤/⎕av⍳(-⍴s)↑s,(⌈.5×⍴s)↑s←⎕

Try it online! Courtesy of Dyalog Classic

Explanation:

(⌈.5×⍴s)↑s take the front half of the string rounding up for odd number length

(-⍴s)↑s,prepend the original string and take trailing characters up to
the original length of string

⎕av⍳ get code points

(⍴s)=+/1,2≤/ check that successive code points are ascending, sum the
 result and compare to length of string; equal = 1 = true, not equal = 0 = false

Answer 9

C (gcc), ⁸² 81 bytes

i;e;r;l;f(char*s){l=strlen(s);for(r=1,e=i=~-l/2;++i%l-e;)r&=s[-~i%l]/s[i%l];e=r;}

Try it online!

Answer 10

Python 3.8,  68  46 bytes

lambda s:sorted(s)==s[(h:=-~len(s)//2):]+s[:h]

An unnamed function accepting a list of characters which yields True if a half-sort and False otherwise.

Try it online!

---

Turns out the straightforward way is terser!

Original 68 byter in Python 2:

lambda s:all(i==~-len(s)/2for i in range(len(s))if(s[1:]+s)[i]<s[i])

Try it online!

Answer 11

Ruby, 33 bytes

->a{a.rotate(-~a.size/2)==a.sort}

Try it online!

Takes input as an array of characters (which feels like cheating). Simply rotates the array by half its length and checks whether this is equal to the sorted array.

Answer 12

Clojure, 48 bytes

#(=(sort %)(flatten(reverse(partition-all 2%))))

Try it online!

Answer 13

Vyxal, 5 bytes

s½Ṙ∑=

Try it Online!

s     # Input Sorted
 ½    # Split into two halves
  Ṙ∑  # And concatenated reversed
    = # Equals original input?

Answer 14

Brachylog, 5 bytes

oḍ↔c?

Try it online!

Outputs through success or failure.

o        The input sorted
 ḍ       and split in half (with the *second* half longer if the length is odd),
  ↔      with those halves reversed
   c     and concatenated,
    ?    is the input.