10
\$\begingroup\$

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
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Can we assume the triple back tick at the end of your test cases are meaningless and the result of a typo? \$\endgroup\$ – Abigail Jun 5 '20 at 11:18
  • 1
    \$\begingroup\$ I'd suggest adding aaa as a truthy test-case. \$\endgroup\$ – Jonathan Allan Jun 5 '20 at 11:36
  • \$\begingroup\$ I guess I know why this has a downvote... the challenge is too easy for golfing languages. \$\endgroup\$ – user92069 Jun 6 '20 at 8:19
  • 1
    \$\begingroup\$ I think this challenge would be better if the input was guaranteed to have positive even length, rather than imposing the somewhat arbitrary specification that “splitting should make the first half longer” for odd-length inputs. I didn't vote down, though. \$\endgroup\$ – Lynn Jun 9 '20 at 18:16

13 Answers 13

1
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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).

\$\endgroup\$
2
  • \$\begingroup\$ @dingledooper Thanks, I might have done something wrong when trying it for the first time. \$\endgroup\$ – Surculose Sputum Jun 5 '20 at 17:52
  • \$\begingroup\$ Using undefined behaviour in Python (modifying a sequence during iteration over said sequence). Thanks, I hate it! +1 \$\endgroup\$ – David Foerster Jun 7 '20 at 14:35
5
\$\begingroup\$

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?
\$\endgroup\$
1
  • 1
    \$\begingroup\$ /:~ to save 1 byte \$\endgroup\$ – Jonah Jun 6 '20 at 13:42
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ You can shave a byte off your score by using splice@F,0,.5+@F/2 instead of splice@F,0,(@F+1)/2, methinks. \$\endgroup\$ – msh210 Jun 7 '20 at 19:28
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
7
  • \$\begingroup\$ You always used s to swap up an input; what makes you change your style all of a sudden? \$\endgroup\$ – user92069 Jun 5 '20 at 11:00
  • \$\begingroup\$ @Λ̸̸ I did? A lot of other people do that for 05AB1E answer, but I usually use the input. Actually, you might be right I did so in the past, so the TIO and test suite use the same code section. In this case I could also use 2äRJD{Q or 2ä`ìD{Q to accomplish that I guess. :) \$\endgroup\$ – Kevin Cruijssen Jun 5 '20 at 11:02
  • \$\begingroup\$ Hmm I was wondering if there would be a way to and check the index of the input string but I can't seem to find the equation easily for the position of the half sorted string in this (although it should be constant right?) \$\endgroup\$ – Expired Data Jun 5 '20 at 13:53
  • 1
    \$\begingroup\$ @ExpiredData So it starts with {œIk and you then want to check whether that value equals a certain value based on the input-length? It certainly won't be shorter than 7 bytes, but I also can't find this sequence on oeis.org unfortunately. \$\endgroup\$ – Kevin Cruijssen Jun 5 '20 at 14:03
  • 1
    \$\begingroup\$ @ExpiredData And using the sorted input as index in the permutations of the input, unfortunately also cannot be found on oeis.org. \$\endgroup\$ – Kevin Cruijssen Jun 5 '20 at 14:05
3
\$\begingroup\$

Charcoal, 22 bytes

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

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

≔⪫⮌⪪θ⊘⊕Lθωθ

Split the string into half, reverse, and join.

¬⊙θ∧κ‹ι§θ⊖κ

Check whether any characters are less than their predecessor.

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

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
\$\endgroup\$
2
\$\begingroup\$

C (gcc), 82 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!

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

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I think the consensus is that character array is an acceptable form of string. \$\endgroup\$ – Surculose Sputum Jun 5 '20 at 16:01
2
\$\begingroup\$

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.

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

Clojure, 48 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy