43
\$\begingroup\$

A "simple circular" word is a word whose chords do not intersect. The chords of a word may be seen by laying out the alphabet in a circle, and then connecting the word's consecutive letters.

Examples of Simple Circular Words

ROLE

ROLE

LAKE

LAKE

BALMY

BALMY

Failing Example

A word fails to be simple circular if any of its chords intersect:

BONES

The Challenge

Write a program or function that takes a word and returns true if it's simple circular, false otherwise.

  • Code golf, fewest bytes wins.
  • Standard rules.
  • You may assume there are no repeated letters in the word.
  • You may assume every word has at least 2 letters
  • You may assume the word is all uppercase, or all lowercase, whichever you prefer.
  • You may output any two consistent values for true and false.

Test Cases

True

ROLE, LAKE, BALMY, AEBDC, ABZCYDXE, AZL, ZA

False

BONES, ACDB, ALBZ, EGDF

\$\endgroup\$
  • 9
    \$\begingroup\$ After around 1 hour of struggling, I've concluded that this cannot be done visually in Scratch. \$\endgroup\$ – Lyxal Jan 27 at 7:41
  • 4
    \$\begingroup\$ @AZTECCO "You may assume there are no repeated letters in the word." \$\endgroup\$ – Kevin Cruijssen Jan 27 at 8:25
  • 1
    \$\begingroup\$ @Kevin Cruijssen ah yes, sorry I skipped that. Although this rule makes the challenge simple it's common for words to have repeated letters, plus ngn answer seems to work for repeated letters too. Maybe we can have a 2nd challenge later based on this.. \$\endgroup\$ – AZTECCO Jan 27 at 9:41
  • 3
    \$\begingroup\$ @AZTECCO I'll be posting a more difficult sequel to this question later this week. Re: repeated letters specifically, I wanted to avoid dealing with doubles like GOON, where the only sensible interpretation is to add a pre-processing step that removes them, which felt uninteresting to me. I'll grant it might have been better to prohibit only contiguous repeats, rather than repeats altogether. \$\endgroup\$ – Jonah Jan 27 at 13:14

11 Answers 11

12
\$\begingroup\$

Perl 6, 46 bytes

{!/[(.).*]**4<?{[+^] $0 Xeq[...] ~<<$0[^2]}>/}

Try it online!

A regex solution that finds if there are four characters in the string such that the two later characters are in different sections of the circle, as defined by the first two characters.

Explanation

{                                           }   # Anonymous code block returning
 !/                                        /    # If the input does not match
   [(.).*]**4                                     # Any 4 characters
             <?{                          }       # Where
                           [...]                    # The range from
                                 ~<<$0[^2]          # The first character to the second
                        Xeq                         # Contains which of  
                     $0                             # The four characters
                [+^]                                # Reduce the list of booleans by xor
                 # Effectively, if only one of the 3rd or 4th character is in that range
\$\endgroup\$
10
\$\begingroup\$

K (ngn/k), 26 24 bytes

{&/|/x=&\'x:-:\|26!x-*x}

Try it online!

*x first letter of the argument x

x- subtract it from each of x as ascii code

26! mod 26

| reverse

-:\ make a pair of the list and its negation

x: assign to x

&\' cumulative minima and maxima (max is min under negation)

|/x= boolean mask for where x[i] is the current minimum or maximum

&/ all (and-reduce)

\$\endgroup\$
7
\$\begingroup\$

05AB1E, 14 13 bytes

Fixed a bug thanks to NickKennedy

Ç.sεć-ć/ï_Ë}P

Try it online!

Ç               # convert each letter to its codepoint
 .s             # suffixes of this list
   ε       }    # for each suffix:
    ć-          #  subtract first from others: [b-a, c-a, d-a, ...]
      ć/        #  divide others by first: [(c-a)/(b-a), (d-a)/(b-a), ...]
        ï       #  round down
         _      #  compare with 0
          Ë     #  all equal?
            P   # after the loop, product (1 iff the list is all 1s)
\$\endgroup\$
  • 2
    \$\begingroup\$ I knew a completely different approach would be shorter. Nice answer. Btw, -1 by using ÷ instead of , which you funnily and consequently enough suggested yourself 2 days ago. :) \$\endgroup\$ – Kevin Cruijssen Jan 27 at 14:48
  • 1
    \$\begingroup\$ @KevinCruijssen no, that doesn't work. Try EGDF. ÷ rounds towards 0 while rounds down. \$\endgroup\$ – Grimmy Jan 27 at 14:48
  • \$\begingroup\$ Ah, you're right, due to the -0.5. With the challenge I linked above where you suggested this golf, the challenge didn't cared about how you rounded. Point taken. :) Maybe EGDF is also a good test case for OP, or does it only apply to your formula and not so much to the approaches used in other answers. (PS: consequently=coincidentally in my comment above; I'm unable to edit it.) \$\endgroup\$ – Kevin Cruijssen Jan 27 at 14:52
  • 1
    \$\begingroup\$ @NickKennedy thanks, fixed (i just had to revert my 13 => 12 optimization, which was to use prefixes instead of suffixes). \$\endgroup\$ – Grimmy Jan 27 at 16:31
  • \$\begingroup\$ This is a really nice approach. Well done. \$\endgroup\$ – Jonah Jan 28 at 13:58
6
\$\begingroup\$

JavaScript (Node.js), 91 bytes

Returns \$false\$ for simple circular, or \$true\$ for non-simple circular.

s=>Buffer(s).some((o,i,a,j=i)=>a.some(_=>((g=i=>x=(a[i]-o%26)%26)(j)-g(i+1))*(x-g(++j))>0))

Try it online!

Commented

s =>                            // s = input string
  Buffer(s)                     // turn s into a Buffer
  .some((o, i, a,               // for each ASCII code o at position i in a[]
                  j = i) =>     // and starting with j = i:
    a.some(_ =>                 //   for each entry in a[]:
      (                         //
        ( g = i =>              //     g is a helper function taking a position i
            x = (a[i] - o % 26) //       return (a[i] - (o mod 26)) mod 26
                % 26            //       and assign the result to x
                                //       NB: if a[i] is undefined, this gives NaN
                                //           and forces the forthcoming test to fail
        )(j) -                  //     compute the difference between g(j)
        g(i + 1)                //     and g(i + 1)
      ) * (                     //     multiply it by the difference
        x - g(++j)              //     between g(i + 1) and g(j + 1) (and increment j)
      ) > 0                     //     if it's positive, the chords are intersecting
                                //     inside the circle (i.e. s is not simple circular)
    )                           //   end of inner some()
  )                             // end of outer some()
\$\endgroup\$
6
\$\begingroup\$

05AB1E, 21 20 bytes

Ask¬-₂%.sD€ß¥s€à¥+ĀP

Port of @ngn's K (ngn/k) answer, so make sure to upvote them!!

Input as a lowercase list of characters.

Try it online or verify all test cases.

Explanation:

A          # Push the lowercase alphabet: "abcdefghijklmnopqrstuvwxyz"
 sk        # Get the (0-based) index of each characters of the input-list in this alphabet
           #  i.e. ["b","a","l","m","y"] → [1,0,11,12,24]
¬          # Push the first index (without popping)
 -         # And subtract it from each index
           #  i.e. [1,0,11,12,24] - 1 → [0,-1,10,11,23]
  ₂%       # Then take modulo-26 to make the negative values positive
           #  i.e [0,-1,10,11,23] → [0,25,10,11,23]
.s         # Take the suffices of this list
           #  i.e. [0,25,10,11,23] → [[23],[11,23],[10,11,23],[25,10,11,23],[0,25,10,11,23]]
  D        # Duplicate it
   ۧ      # Take the minimum of each suffix
           #  i.e. [[23],[11,23],[10,11,23],[25,10,11,23],[0,25,10,11,23]]
           #   → [23,11,10,10,0]
     ¥     # And take the deltas (forward differences) of those
           #  i.e. [23,11,10,10,0] → [-12,-1,0,-10]
  s        # Swap to get the suffices again
   ۈ      # Take the maximum of each suffix this time
           #  i.e. [[23],[11,23],[10,11,23],[25,10,11,23],[0,25,10,11,23]]
           #   → [23,23,23,25,25]
     ¥     # And take the deltas (forward differences) of those as well
           #  i.e. [23,23,23,25,25] → [0,0,2,0]
      +    # Add the values at the same indices in the two lists together
           #  i.e. [-12,-1,0,-10] + [0,0,2,0] → [-12,1,2,-10]
       Ā   # Python-style truthify each (0→0; everything else → 1)
           #  i.e. [-12,1,2,-10] → [1,1,1,1]
        P  # And take the product of that to check if all are truthy
           #  i.e. [1,1,1,1] → 1
           # (after which this is output implicitly as result)
\$\endgroup\$
  • \$\begingroup\$ I think you forgot the and wait part. :P \$\endgroup\$ – Lyxal Jan 27 at 10:09
  • 1
    \$\begingroup\$ @Lyxal fixed ;p \$\endgroup\$ – Kevin Cruijssen Jan 27 at 10:10
  • \$\begingroup\$ Well played ;P. I wish I could up vote this twice! \$\endgroup\$ – Lyxal Jan 27 at 10:13
4
\$\begingroup\$

Charcoal, 29 bytes

⬤θ⬤…θκ⬤…θμ⬤…θξ⁼⁼‹ιν‹νλ⁼‹ιπ‹πλ

Try it online! Takes input in consistent case and outputs a Charcoal boolean (- for true, nothing for false). This has a rare use of the p variable. Explanation:

 θ                              Input string
⬤                               All characters satisfy
    θ                           Input string
   …                            Truncated to
     κ                          Current index
  ⬤                             All characters satisfy
        θ                       Input string
       …                        Truncated to
         μ                      Current index
      ⬤                         All characters satisfy
            θ                   Input string
           …                    Truncated to
             ξ                  Current index
          ⬤                     All characters satisfy
                 ι              Fourth character
                ‹               Is less than
                  ν             Second character
               ⁼                Equals
                    ν           Second character
                   ‹            Is less than
                     λ          Third character
              ⁼                 Equals
                        ι       Fourth character
                       ‹        Is less than
                         π      First character
                      ⁼         Equals
                           π    First character
                          ‹     Is less than
                            λ   Third character

For each subsequence of four characters in the input word, the first two comparisons check whether the second character is between the third and fourth while the other comparisons check whether the first character is between the third and fourth. If the results of these comparisons is different then it means that the chord between the first two characters crosses the chord between the third and fourth characters and the whole expression therefore evaluates to false.

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

Jelly, 12 bytes

O_Ṫ$:Ṫ$¬EƲƤẠ

Try it online!

A Jelly translation of Grimy’s 05AB1E answer; be sure to upvote that one too! A monadic link taking a Jelly string as its argument and returning a Jelly boolean.

Explanation

O            | Convert to Unicode codepoints
         ƲƤ  | Following applied to each prefix:
 _Ṫ$         | - Subtract tail (after popping tail)
    :Ṫ$      | - Integer divide by tail (after popping tail)
       ¬     | - Not
        E    | - All equal
           Ạ | All
\$\endgroup\$
2
\$\begingroup\$

J, 40 36 33 bytes

10(e.,)[:(/:~@,#.@e.])"1/~2]\3&u:

Try it online!

Decided to play my own game.

Still golfing...

But the idea is just to try all possible combinations of pairs of points, and check if their lines intersect, which, if the segements are AB and CD, happens when the letters' numerical values are arranged like:

      _____
     /     \
A...C...B...D
\______/
\$\endgroup\$
  • \$\begingroup\$ I recommend holding off for a week before answering your own challenges. \$\endgroup\$ – Adám Jan 28 at 13:31
  • 1
    \$\begingroup\$ Just FYI for the future. \$\endgroup\$ – Adám Jan 28 at 14:52
2
\$\begingroup\$

Haskell, 135 99 bytes

Thanks @JoKing for saving 36 bytes!

Almost certain its not the optimal way to go, so please feel free to improve it.

x(a:b:c:d:_)|s<- \z->min a b>z||z>max a b=s c/=s d;x _=1<0;y s=or$map(x.concat)$mapM(\a->[[a],[]])s

Explanation

However, I loved doing some propositional calculus. First, x tests if a given sequence of four letters form a non-circular word. Let \$I\$ be the interval defined by \$a\$ and \$b\$, so \$a,b,c\$ and \$d\$ form a circular word only if:

$$ p\equiv(c\in I)\iff q\equiv(d\in I)\\ (p\Rightarrow q)\wedge(q\Rightarrow p)\\ (\neg p\lor q)\wedge(\neg q\lor p)\\ \left[(\neg p\lor q)\wedge \neg q\right]\lor\left[(\neg p\lor q)\wedge p\right]\\ \left[(\neg p\wedge\neg q)\lor(q\wedge\neg q)\right]\lor\left[(\neg p\wedge p)\lor(q\wedge p)\right]\\ (\neg p\wedge\neg q)\lor(q\wedge p)\\ \neg(p\lor q)\lor(q\wedge p) $$

Negating this proposition gives us

$$ (p\lor q)\wedge\neg(q\wedge p) $$

which is equivalent to \$p\veebar q\$, in haskell p/=q. Finally, y tests if any subsequence with length 4 from the original word is non-circular.

Here's a spaned version:

import Data.List

-- x
cuts (a:b:c:d:rest)
 | s <- \z-> min a b > z || z > max a b
 = s c /= s d
x _ = False

-- y
isNonCircular word = or $ map (cuts . concat) $ mapM (\a -> [[a],[]]) word
```
\$\endgroup\$
  • \$\begingroup\$ and gofled to 97 bytes (though I'm no Haskell golfer) \$\endgroup\$ – Jo King Jan 30 at 0:51
  • \$\begingroup\$ @JoKing how did i not think of that!? I thoutgh about using xor, but didn't find any simple implamentation and didn't even considered using /=, thank you. \$\endgroup\$ – Leonardo Moraes Jan 30 at 15:08
  • \$\begingroup\$ @JoKing I tried running your code on my computer, but it didn't compile, even though I see how it would work. \$\endgroup\$ – Leonardo Moraes Jan 30 at 15:11
  • 1
    \$\begingroup\$ You need the header, with the comment, and I believe that it must be compiled in GHC since -Xcpp is a GHC flag. Either that or add the v= before the or. Also lambdas are usually a bad idea. The lambda in @JoKing's golf can be eliminated for one more byte. \$\endgroup\$ – Post Rock Garf Hunter Jan 31 at 1:46
  • 1
    \$\begingroup\$ Additionally or + a map is the same as the function any, so instead of or.(x.concat<$>) you can do any(x.concat). \$\endgroup\$ – Post Rock Garf Hunter Jan 31 at 1:50
1
\$\begingroup\$

Ruby -nl, 70 bytes

An adaptation of the Perl answer, but Perl is apparently black magic with... whatever they're doing that lets them tersely get any 4 characters.

p$_.chars.combination(4).all?{|*m,c,d|(c=~r=/[#{m.sort*?-}]/)==(d=~r)}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Can you explain the regex part? \$\endgroup\$ – Jonah Jan 29 at 4:37
  • 1
    \$\begingroup\$ @Jonah I take the first two characters selected, sort them, and join them with -. Then this is interpolated into the regex. So if the input is BONES, the program will eventually reach the combination ['B', 'O', 'E', 'S'], so m=['B', 'O']; c='E', d='S'. So it will check if 'E' is in the regex /[B-O]/, and then do the same for 'S', and find that the result for each of them is not the same, so it returns false. \$\endgroup\$ – Value Ink Jan 31 at 2:30
  • \$\begingroup\$ That’s very clever. Similar idea to my solution but the regex twist is quite fun. \$\endgroup\$ – Jonah Jan 31 at 3:52
  • \$\begingroup\$ We have to do what's necessary to make things shorter. The next best solution AFAIK a,b=m.sort;(a<c&&c<b)==(a<d&&d<b) is 2 bytes longer. \$\endgroup\$ – Value Ink Jan 31 at 6:17
1
\$\begingroup\$

C (clang), 119 114 bytes

c,n,b,j,o;g(char*w){for(int l[92]={j=o=c=0};n=*w;c=l[*w++])for(b=l[n],o|=b|c-j++&&c+~b&&b-c;n;)l[n--]++;return!o;}

Try it online!

We use an array representing the circle points ( we start from \0 instad of 'A' because it doesn't care)

We increment by 1 each point from current letter to 0.

The next point is valid if
 next == curr or
 next == curr - 1 or 
 next == 0 and curr == j( iteration / left value )

LAKE
ABCDEFGHIJKLMN.. j   curr  next
00000000000000.. 0   0     L 0
11111111111*00.. 1   1     A 1
*1111111111100.. 2   2     K 2
3222222222*100.. 3   2     E 2
4333*222222100.. 

Thanks to @ceilingcat for saving 5

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