String Comparison

Question

You are given two strings \$a\$ and \$b\$ consisting of characters from a to z in lowercase. Let \$n\$ be the length of \$a\$. Let \$m\$ be the length of \$b\$. Let \$a'\$ be the string \$a\$ repeated \$m\$ times. Let \$b'\$ be the string \$b\$ repeated \$n\$ times. Check whether \$a'\$ is lexicographically less than \$b'\$.

Test cases:

a b ---> true
ac a ---> false
bekcka kwnfoe ---> true
beztbest bestbe ---> false
mcjaf mc ---> true
akboe uenvi ---> true

Shortest code wins.

Hint: there's a 13-byte JavaScript solution. Beat that!

Competitive answers use the a+b<b+a approach. A proof of this approach can be found at https://codeforces.com/blog/entry/91381?#comment-808323

Answer 1

Python, 18 bytes

lambda a,b:a+b<b+a

Attempt This Online!

How?

\$a+b \lesseqqgtr b+a \quad\Leftrightarrow\quad a+a+b \lesseqqgtr a+b+a \lesseqqgtr b+a+a \quad\cdots\quad\Leftrightarrow\quad m\times a+b \lesseqqgtr b+ m\times a \quad\Leftrightarrow\quad m\times a+b+b \lesseqqgtr b+m\times a+b \lesseqqgtr b+b+ m\times a \quad\cdots\quad\Leftrightarrow\quad m\times a+n\times b \lesseqqgtr n\times b+ m\times a \quad\Leftrightarrow\quad m\times a \lesseqqgtr n\times b\$

Answer 2

Jelly, 3 bytes

^{Let's give these strings some ooṁÞƑ :)}

ṁÞƑ

A monadic Link that accepts a pair of lists of characters, \$[b, a]\$, and yields 0 when \$a'=a\times n\$ is lexicographically less than \$b'=b\times m\$ where \$\times\$ is "repeat" or 1 if not.

i.e. takes the strings in reverse order and results in the negative.

Try it online! Or see the test-suite.

How?

We actually only need to check the first up to \$m+n\$ characters of the two augmented strings. This gets these by moulding each string like the input pair, e.g. ['ab', 'xyz'] gives ['ab', 'aba'] and ['xy', 'zxy']. There is no need to flatten these before comparing them since their relative sort order is unaffected due to them having the same shape as each other.

ṁÞƑ - Link: pair of strings, X = [b, a]
  Ƒ - is X invariant under?:
 Þ  -   sort (the elements, e, of) X by:
ṁ   -     (e) mould like (X)

Worked Example

a = 'abcdefgh' -> n = 8
b = 'pqrst' -> m = 5
X = [b, a] = ['pqrst', 'abcdefgh']
b ṁ X = ['pqrst', 'pqrstpqr']
  ...this is the first n+m=13 characters of b',
         'pqrstpqrstpqrstpqrstpqrstpqrstpqrstpqrst', split after m = 5 characters
a ṁ X = ['abcde', 'fghabcde']
  ...this is the first n+m=13 characters of a',
         'abcdefghabcdefghabcdefghabcdefghabcdefgh', split after m = 5 characters
(a ṁ X) < (b ṁ X) so the sorting, `ṁÞ`, reverses X
checking for invariance with `ṁÞƑ` therefore gives 0 indicating that a' < b'

Answer 3

JavaScript (Node.js), 13 bytes

a=>b=>a+b<b+a

Try it online!

Probably the 13 byte JS solution mentioned in the challenge. Ports loopy walt's Python answer.

Answer 4

Wolfram Language(Mathematica), 31 bytes

f=AlphabeticOrder[#<>#2,#2<>#]&

Try it online!

Answer 5

Go, 36 bytes

func(a,b string)bool{return a+b<b+a}

Attempt This Online!

Port of Loopy's Python answer.

Go, 81 bytes

import."strings"
func f(a,b string)bool{return Repeat(a,len(b))<Repeat(b,len(a))}

Attempt This Online!

A more literal interpretation of the question.

Answer 6

Vyxal, 4 bytes

₌Jp>

Try it Online!

A port of python is one byte shorter because of the niceness of parallel apply.

Explained

₌Jp>
₌  >  # check whether
J    # the joining of the two strings
  >  # is greater than
 p   # the prepending of the two strings

For a more straightforward approach:

Vyxal, 5 bytes

@Ṙ*ƒ<

Try it Online!

Takes input as a list of strings.

Explained

@Ṙ*ƒ<
@     # vectorised lengths
 Ṙ*   # reverse that, and pairwise repeat the input strings that many times
   ƒ< # reduce by lexographic less than

Answer 7

Julia 1.0, 11 bytes

a\b=a*b<b*a

Try it online!

Another port of loopy walt's Python answer.

Answer 8

Charcoal, 7 bytes

‹⁺θη⁺ηθ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if a'<b', nothing if not. Explanation: Another port of @loopywalt's Python answer.

  θ     First string
 ⁺      Concatenated with
   η    Second string
‹       Is less than
     η  Second string
    ⁺   Concatenated with
      θ First string
        Implicitly print

There are four cases:

• One of a and b is a repetition of the other. In this case, a'=b', but a+b=b+a, so the result is correct.
• One of a and b is the prefix of the other, but the other is a prefix of its repetition. In this case the tie between a' and b' can always be broken before the length of a+b. Suppose a is a prefix of b is a prefix of a', then a+b is also a prefix of a', and b+a is a prefix of b', so the result is correct.
• One of a and b is the prefix of the other. In this case the tie between a' and b' can always be broken before the length of the longer of a and b. Suppose a is a prefix of b, then a+b contains enough copies of a to break the tie with b, so the result is correct.
• Otherwise, a and b break the tie anyway before the length of the shorter of the two, so again the result is correct.

6 bytes by using JSON input:

‹ΣθΣ⮌θ

Try it online! Link is to verbose version of code. Explanation:

  θ     Input pair
 Σ      Joined
‹       Is less than
     θ  Input pair
    ⮌   Reversed
   Σ    Joined
        Implicitly print

9 bytes for the naïve version:

‹×θＬη×ηＬθ

Try it online! Link is to verbose version of code. Explanation:

  θ         First input
 ×          Repeated by
    η       Second input
   Ｌ        Length
‹           Is less than
      η     Second input
     ×      Repeated by
        θ   First input
       Ｌ    Length
            Implicitly print

Answer 9

Arturo, 18 bytes

$[a b]-><a++b b++a

Try it

Port of loopy walt's Python answer.

Answer 10

C (gcc), 82 bytes

t;*p;*q;f(a,b){for(t=3,p=a,q=b;*p==*q&&t;!*++p?--t,p=b:0)!*++q?--t,q=a:0;t=*p<*q;}

Try it online!

Based on loopy walt's Python answer

Answer 11

05AB1E (legacy), 6 5 bytes

‚J`‹

-1 byte porting @loopyWalt's Python answer, so make sure to upvote that answer well!

Try it online or verify all test cases.

Original straight-forward 6 bytes answer:

€gR×`‹

Try it online or verify all test cases.

Explanation:

Uses the legacy version of 05AB1E, built in Python, which allows for comparisons on strings.

       # Bifurcate the (implicit) input-pair; short for Duplicate & Reverse copy
 ‚      # Pair the pair with its reversed pair
  J     # Join each inner pair together to a string
   `    # Pop and push the strings to the stack
    ‹   # Check if the first is smaller than the second
        # (after which the result is output implicitly)

€g      # Get the length of each inner string of the (implicit) input-pair
  R     # Reverse this pair
   ×    # Repeat the strings in the (implicit) input-pair that many times
    `‹  # Same as above
        # (after which the result is output implicitly)

---

05AB1E, 5 bytes

Porting @JonathanAllan's Jelly answer gives an alternative 5 bytes answer, which only works in the new version of 05AB1E.

Σδ∍}Q

Try it online or verify all test cases.

Explanation:

Σ       # Sort the (implicit) input-pair by:
 δ      #  Map over the (implicit) input-pair with the current string as argument:
  ∍     #   Extend/shorten the current string of the map to the same length as the
        #   current string of the sort-by
}       # After the sort-by:
 Q      # Check if the sorted pair is equal to the (implicit) input-pair
        # (after which the result is output implicitly)

Answer 12

Excel, 12 bytes

=A1&B1<B1&A1

Input is in the cells A1 and B1. Excel uses & for concatenation.

Answer 13

Ruby, 35 b-bwytes =￣ω￣=

lambda{|a, b|"#{a}#{b}"<"#{b}#{a}"}

Yiff yiff, this is a furrendly conversion of the python tail wag!

Answer 14

Thunno D, \$ 8 \log_{256}(96) \approx \$ 6.58 bytes

rZP.JAu<

Attempt This Online! or verify all test cases

Direct port of Kevin Cruijssen's 05AB1E answer, which is a port of loopy walt's Python answer.

Explanation

rZP.JAu<  # Implicit input
rZP       # Pair with reverse
   .J     # Join each inner list
     Au   # Dump onto stack
       <  # Check if less than
          # Implicit output

Answer 15

Retina 0.8.2, 32 bytes

¶
$'¶$'$`¶$`
O`.+¶
M`(.+)¶\1$
^0

Try it online! Explanation: Based on @loopywalt's Python answer.

¶
$'¶$'$`¶$`

Create a list of a+b, b+a, a+b.

O`.+¶

Sort the first two elements of the list.

M`(.+)¶\1$
^0

Check that the last two elements are different.

Answer 16

Pyth, 5 bytes

<sQs_

Try it online!

Port of @loopyWalt's python answer. Takes the input as a list of two strings [a,b].

Explanation

<sQs_Q    # implicitly add Q
          # implicitly assign Q = eval(input())
<         # lexicographically compare
 sQ       # sum of Q
   s_Q    # sum of the reversal of Q

Answer 17

Haskell + hgl, 10 bytes

gt.*cx*^Rv

Attempt This Online!

Takes the input as a list with two values. I don't like this format so I also solved it with a good io format:

Haskell + hgl, 14 bytes

ap<gt<<fmp*^mp

Attempt This Online!

Honorable mention to:

ap~<l2 gt<<F$mp

which is 1 byte longer.

Haskell + hgl, 13 bytes

gt.*Uc mp*^Sw

Attempt This Online!

This uses a tuple with two values. It's a compromise between the two formats and is slightly shorter than the longer of the two.

Haskell + hgl, 9 bytes

cb cx*^Rv

Attempt This Online!

This outputs a comparison (3 values) instead of a boolean (2 values). This is shorter than the first answer, however the output format isn't officially permitted in the challenge (although I haven't got a "No" yet).

I actually prefer this format since it's generally more modular and fits in with the systems available in hgl (part of why this is shorter). The 14 byte answer can also be made to use this format by replacing gt with cp, but it makes no difference to the byte count.

Reflection

The 10 byte and 9 byte answers are pretty tight. The 10 byte answer (and the 13 byte answer) could potentially be shorter if on gt were given a 2 byte name (cb is the 2 byte name of on cp and the reason the 9 byte answer is shorter), however it's a bit hard to justify that. A 3 byte name might be useful anyway.

However I am really concerned with improving the 14 byte answer. The other answers are in my opinion an abuse of the format. This is a very simple challenge and if I were to encounter this challenge as a part of a larger challenge there's no way I would get the input in such a format. I'd get it in a format much more similar to what the 14 byte answer expects. The issue that blows up the size of that answer is that in order to thread through two separate arguments, both of which are used twice requires a good deal of glue. All the other answers benefit from only taking one input, making their glue much simpler.

So what's missing? Well, I have trouble coming up with a good reusable way to combine any of the existing parts. on gt doesn't actually help in this one unlike the other ones. And it's hard to make a version of on that actually does help. However there are pretty much two salient functions here gt and mp. All the glue is just a way to combine two functions, so maybe all of it should just be one function.

gt+^$mp

This would actually make things shorter (a lot shorter) and since it does combine two arguments it seems plausible that it could be reused at some point in the future. It's not a slam-dunk, it's not a clear hole in the language, but it's about the best I can do in this case.

Answer 18

Japt, 5 bytes

Takes input as an array.

¬<UÔ¬

Try it (Includes all test cases)

Answer 19

Factor, 36 bytes

[ 2dup append -rot prepend before? ]

Try it online!

         ! "ac" "a"
2dup     ! "ac" "a" "ac" "a"
append   ! "ac" "a" "aca"
-rot     ! "aca" "ac" "a"
prepend  ! "aca" "aac"
before?  ! f

Answer 20

C (gcc) -m32, 78 bytes

This is a comparison function, it outputs \$a + b \lesseqqgtr b + a\$, where \$+\$ is string concatenation.

f(a,n,b,m){int c[4][n+m];wcscmp(wcscat(wcscpy(c),b),wcscat(wcscpy(c+2,b),a));}

Try it online!