15
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ Can I take input as a list of two strings? \$\endgroup\$
    – lyxal
    Apr 12, 2023 at 2:35
  • \$\begingroup\$ Of course that's reasonable \$\endgroup\$ Apr 12, 2023 at 2:35
  • 7
    \$\begingroup\$ @lyxal That is actually a default since 2 days ago \$\endgroup\$
    – mousetail
    Apr 12, 2023 at 7:33
  • \$\begingroup\$ @mousetail thanks for pointing that out! \$\endgroup\$ Apr 12, 2023 at 13:45
  • 2
    \$\begingroup\$ Is it permissible to instead return a comparison function? e.g. instead of returning two values for less than and not less than to return three values one for less than, one for greater than and one for equal? \$\endgroup\$
    – Wheat Wizard
    Apr 14, 2023 at 3:43

20 Answers 20

14
\$\begingroup\$

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

\$\endgroup\$
3
  • 3
    \$\begingroup\$ It took me a minute to realize why this works! \$\endgroup\$ Apr 12, 2023 at 2:56
  • \$\begingroup\$ Great explanation. However, I believe it is not appropriate to use the \$\Leftrightarrow\$ symbol here as many of the steps are not reversible. You have to use a separate, albeit very straightforward, argument to prove \$m \times a < n \times b \Rightarrow a + b < b + a\$. \$\endgroup\$ Apr 20, 2023 at 6:43
  • 3
    \$\begingroup\$ @HuỳnhTrầnKhanh It works both ways as we always cover all possibilities. If we have l.h.s.1 < or = or > r.h.s.1 => l.h.s.2 < or = or > r.h.s.2 then, e.g., l.h.s.2 < r.h.s.2 => l.h.s.1 < r.h.s.1 because otherwise l.h.s.1 = or > r.h.s.1 from which as established first => l.h.s.2 = or > r.h.s.2, contradiction. \$\endgroup\$
    – loopy walt
    Apr 20, 2023 at 8:01
7
\$\begingroup\$

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'
\$\endgroup\$
0
6
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

Wolfram Language(Mathematica), 31 bytes

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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

Julia 1.0, 11 bytes

a\b=a*b<b*a

Try it online!

Another port of loopy walt's Python answer.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
9
  • \$\begingroup\$ Is the import required? It seems to work without it. \$\endgroup\$
    – The Thonnu
    Apr 12, 2023 at 19:47
  • \$\begingroup\$ When I "Attempt This Online" for the first one (the second one works) I just get errors:../code.go:12:21: undefined: Split ../code.go:13:12: undefined: Fields \$\endgroup\$
    – Noodle9
    Apr 14, 2023 at 9:55
  • \$\begingroup\$ @Noodle9 runner was missing some boilerplate, it's fixed now \$\endgroup\$
    – bigyihsuan
    Apr 14, 2023 at 14:20
  • \$\begingroup\$ @bigyihsuan If you have to import modules for your answer to work you must include that code as part of your answer, you can't just tuck them away in the header. \$\endgroup\$
    – Noodle9
    Apr 14, 2023 at 15:40
  • 1
    \$\begingroup\$ @Noodle9 string is the built-in Golang type for a string of characters. strings (note the plural) is the name of a string-handling package in the standard library. They are not the same. \$\endgroup\$
    – bigyihsuan
    Apr 14, 2023 at 22:33
3
\$\begingroup\$

Arturo, 18 bytes

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

Try it

Port of loopy walt's Python answer.

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

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

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

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:

‹×θLη×ηLθ

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

  θ         First input
 ×          Repeated by
    η       Second input
   L        Length
‹           Is less than
      η     Second input
     ×      Repeated by
        θ   First input
       L    Length
            Implicitly print
\$\endgroup\$
0
3
\$\begingroup\$

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

Excel, 12 bytes

=A1&B1<B1&A1

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

Screenshot

\$\endgroup\$
2
  • \$\begingroup\$ this is quite the answer.. Excel!? I have respect for you! :D such a marvelous idea! \$\endgroup\$ Apr 14, 2023 at 12:15
  • \$\begingroup\$ I'd say this is more VBA than Excel, but this is nice, anyway. \$\endgroup\$
    – ysap
    Apr 15, 2023 at 10:28
3
\$\begingroup\$

Ruby, 35 b-bwytes = ̄ω ̄=

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

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

\$\endgroup\$
2
  • \$\begingroup\$ Well that just happened \$\endgroup\$
    – lyxal
    Apr 16, 2023 at 2:07
  • 1
    \$\begingroup\$ Welcome to Co...wait I know you! \$\endgroup\$ Apr 16, 2023 at 2:36
2
\$\begingroup\$

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

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.

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

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

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.

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

Japt, 5 bytes

Takes input as an array.

¬<UÔ¬

Try it (Includes all test cases)

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

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

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.