13
\$\begingroup\$

The input is a string made of the letters a,b,c only. The output is an integer representing the degree of the sequence. The degree of a sequence is computed as follows:

  • Assume that each of the letters a,b,c is the vertex of a triangle.
  • Assume that you start a walk on the first letter, and keep walking towards the next letter, until the end of the sequence.
  • The degree is the net number of times that you walk around the center of the triangle clockwise.

To clarify the definition, here are some examples:

  • abca -> 1: single round clockwise. Similarly, bcab->1 and cabc->1.
  • accbbbaa -> -1: single round counter-clockwise.
  • abcacba -> 0: one round clockwise and one round counter-clockwise (1-1=0).
  • abcabcab -> 2: two complete rounds clockwise (plus one partial round which does not count).
  • abababababababcababababababab -> 1: many partial rounds, but only one complete round.
  • abcbca -> 1: a complete round, even though there are moves back and forth along the way.
  • abcabcacb -> 1: two rounds and then two steps back, which leaves us with fewer than two complete rounds.

The shortest code in byte wins. Please explain your solutions.

\$\endgroup\$
19
  • 2
    \$\begingroup\$ Does the input always start with a? \$\endgroup\$
    – att
    Commented May 17 at 7:32
  • 4
    \$\begingroup\$ That's gonna break most existing answers unfortunately I think. \$\endgroup\$ Commented May 17 at 12:55
  • 2
    \$\begingroup\$ FWIW it's a nice question, just could have done with a little more thought prior to posting. (Yeah it broke all five existing answers, have commented to authors, hopefully not too difficult for them to handle...) \$\endgroup\$ Commented May 17 at 13:11
  • 3
    \$\begingroup\$ @xnor Each letter "forward" is 0.333... winds. So abc is 1.0 "winds". In the test case "abcabcacb -> 1", it winds forwards abc = 1.0, and a second abc=1.0, then another a = 0.33, for a total of 2.33. But then it winds backwards, cb is back -0.66, giving a total winding of 1.66. Finally, round down to nearest int, to get the answer 1. \$\endgroup\$ Commented May 17 at 18:35
  • 2
    \$\begingroup\$ Suggest test case acb to assure flooring towards 0 rather than towards -inf. \$\endgroup\$ Commented May 17 at 23:52

13 Answers 13

13
\$\begingroup\$

JavaScript (ES6), 38 bytes

Straightforward formula

Expects an array of ASCII codes.

a=>a.map(t=c=>t=-~t-(a+4-[a=c])%3)|t/3

Try it online!


JavaScript (ES6), 39 bytes

Chained modulos on ASCII code concatenation

Expects an array of ASCII codes.

a=>a.map(t=c=>t=~-t+(a+[a=c])%80%3)|t/3

Try it online!

Method

Move types are identified by computing the concatenation of the ASCII codes of the previous and current characters and reducing it modulo \$80\$ and modulo \$3\$. This gives \$0\$ for counter-clockwise, \$1\$ for no move and \$2\$ for clockwise.

previous char. current char. concat. of ASCII codes mod 80 mod 3 move type
a a 9797 37 1 no move
a b 9798 38 2 clockwise
a c 9799 39 0 counter-clockwise
b a 9897 57 0 counter-clockwise
b b 9898 58 1 no move
b c 9899 59 2 clockwise
c a 9997 77 2 clockwise
c b 9998 78 0 counter-clockwise
c c 9999 79 1 no move

Search code

The following code was used to brute-force the modulo values.

let A = [ 97, 98, 99 ];
for(let m0 = 1; m0 < 1000; m0++) {
  for(let m1 = 1; m1 <= m0; m1++) {
    if(A.every(p =>
      A.every(c => {
        let r = p - c ? c == p + 1 || c == 97 && p == 99 ? 1 : -1 : 0;
        let v = (p + [c]) % m0 % m1 - 1;
        return v == r;
      })
    )) {
      console.log(m0, m1);
    }
  }
}

Try it online!

\$\endgroup\$
2
  • 2
    \$\begingroup\$ This is slick, but... why does it work? What is the significance of mod-7 and mod-2? How did you come up with this? Inquiring minds want to know! \$\endgroup\$ Commented May 17 at 11:06
  • 2
    \$\begingroup\$ @JeffZeitlin I've added the updated search code to my answer. \$\endgroup\$
    – Arnauld
    Commented May 17 at 14:36
9
\$\begingroup\$

Cubical Agda, 1134 bytes

Uses Agda 2.6.4.3, the cubical library 0.7 and the standard library 2.0.

{-# OPTIONS --cubical #-}
open import Cubical.Data.Int
open import Cubical.Data.Int.Divisibility
open import Cubical.Data.Nat
open import Cubical.Foundations.Everything
open import Data.List
open import Data.List.NonEmpty as L⁺

data 𝟛 : Type where
  a b c : 𝟛

data △ : Type where
  inc : 𝟛 → △
  ab : inc a ≡ inc b
  bc : inc b ≡ inc c
  ca : inc c ≡ inc a

infix 40 _⇒_
_⇒_ : (x y : 𝟛) → inc x ≡ inc y
a ⇒ a = refl
a ⇒ b = ab
a ⇒ c = sym ca
b ⇒ a = sym ab
b ⇒ b = refl
b ⇒ c = bc
c ⇒ a = ca
c ⇒ b = sym bc
c ⇒ c = refl

🏃 : ∀ s → inc (L⁺.head s) ≡ inc (L⁺.last s)
🏃 s with snocView s
... | ys ∷ʳ′ y = go ys
  where
    go : ∀ ys → inc (L⁺.head (ys L⁺.∷ʳ y)) ≡ inc y
    go [] = refl
    go (v ∷ vs) = v ⇒ _ ∙ go vs

🧬 : △ → Type
🧬 (inc _) = ℤ
🧬 (ab i) = sucPathℤ i
🧬 (bc i) = sucPathℤ i
🧬 (ca i) = sucPathℤ i

_/3 : ℤ → ℤ
n@(pos _) /3 = quotRem 3 n (snotz ∘ injPos) .QuotRem.div
n@(negsuc _) /3 = - quotRem 3 (- n) (snotz ∘ injPos) .QuotRem.div

d : List⁺ 𝟛 → ℤ
d s = subst 🧬 (🏃 s) 0 /3

A straightforward winding number computation, slightly complicated by the fact that the string doesn't have to start and end on the same character.

We define the triangle as a higher inductive type generated by three points and three paths, as well as a covering space with fibre that looks like a "triple helix":

triple helix cover of a triangle

To get the degree/winding number of a string of vertices, we transport 0 along a path in the triangle generated by taking the "shortest" path from each vertex to the next, and divide the resulting integer by 3 towards zero.

There is no compiler for Cubical Agda (yet!), but we can check that the test cases compute correctly:

open import Agda.Builtin.Char
open import Agda.Builtin.FromString
open import Agda.Builtin.String
open import Data.Bool
open import Data.List.Effectful as List
open import Data.Maybe
open import Data.Maybe.Effectful as Maybe

parse1 : Char → Maybe 𝟛
parse1 'a' = just a
parse1 'b' = just b
parse1 'c' = just c
parse1 _   = nothing

parse : List Char → Maybe (List⁺ 𝟛)
parse s = mapA parse1 s >>= fromList
  where open List.TraversableA Maybe.applicative

instance
  IsString-vertices : IsString (List⁺ 𝟛)
  IsString-vertices .IsString.Constraint s = T (is-just (parse (primStringToList s)))
  IsString-vertices .IsString.fromString s ⦃ j ⦄ = to-witness-T _ j

_ : d "abca" ≡ 1
_ = refl
_ : d "bcab" ≡ 1
_ = refl
_ : d "cabc" ≡ 1
_ = refl
_ : d "accbbbaa" ≡ -1
_ = refl
_ : d "abcacba" ≡ 0
_ = refl
_ : d "abcabcab" ≡ 2
_ = refl
_ : d "abababababababcababababababab" ≡ 1
_ = refl
_ : d "abcbca" ≡ 1
_ = refl
_ : d "abcabcacb" ≡ 1
_ = refl
\$\endgroup\$
1
  • \$\begingroup\$ I'm glad to see Agda, but you could definitely shorten this a bunch by stripping the excess whitespace and shortening the variable names to a single character. \$\endgroup\$
    – Wheat Wizard
    Commented May 21 at 13:01
7
\$\begingroup\$

Python 3.8 (pre-release), 50 bytes

lambda a,*s:int(sum(-(a+~(a:=b))%3-1for b in s)/3)

Try it online!

-5 bytes thanks to Neil

-5 bytes thanks to Albert.Lang

Port of Arnauld's JavaScript answer.

Alternative solution:

Python 3, 69 bytes

lambda s:int(sum('aabbccabca'.count(x+y)-1for x,y in zip(s,s[1:]))/3)

Try it online!

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

Rust, 67 66 bytes

|a|a[1..].iter().fold((0,a[0]%3),|(b,c),d|(b-(c+!d)%3-1,*d%3)).0/3

Attempt This Online!

Now handles repeats

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

Jelly, 12 bytes

_ƝNA¡€ṠS÷3r`

A monadic Link that accepts a list of the walked vertices' ASCII codes/byte values and yields a singleton list containing the net number of rounds.

Try it online! Or see the test-suite.

How?

The ASCII codes of the characters in the input are [97, 98, 99] for "abc", respectively.

The instructions are the substrings of length two of the input.

Each instruction has an expected direction, \$1\$ for clockwise, \$-1\$ for anticlockwise, or \$0\$ for no movement.

For most instructions, the direction is just the forward difference of the instruction's values (\$-d\$ below), the only time this is not the case is when the ordinals have an absolute difference of two. The code coerces these by repeated negation and finally extracts the result's sign:

instruction expected direction \$d\$ \$|d|\$ \$v = (-1)^{|d|} d\$ \$\mathrm{sgn}(v)\$
ab clockwise (\$1\$) $$97-98=-1$$ \$1\$ \$1\$ \$1\$
bc clockwise (\$1\$) $$98-99=-1$$ \$1\$ \$1\$ \$1\$
ca clockwise (\$1\$) $$99-97=2$$ \$2\$ \$2\$ \$1\$
cb anticlockwise (\$-1\$) $$99-98=1$$ \$1\$ \$-1\$ \$-1\$
ba anticlockwise (\$-1\$) $$98-97=1$$ \$1\$ \$-1\$ \$-1\$
ac anticlockwise (\$-1\$) $$97-99=-2$$ \$2\$ \$-2\$ \$-1\$
aa no movement (\$0\$) $$97-97=0$$ \$0\$ \$0\$ \$0\$
bb no movement (\$0\$) $$98-98=0$$ \$0\$ \$0\$ \$0\$
cc no movement (\$0\$) $$99-99=0$$ \$0\$ \$0\$ \$0\$
O_ƝNA¡€ṠS÷3r` - Link: list of characters from "abc", S
O             - ordinals {S}
  Ɲ           - for neighbouring pairs:
 _            -   {first} subtract {second}
      €       - for each {d in that}:
     ¡        -   repeat...
    A         -   ...times: absolute value {d}
   N          -   ...action: negate
       Ṡ      - signs
        S     - sum
         ÷3   - divide by three -> FractionalRounds
           r` - inclusive range with self -> [int(FractionalRounds)]

Also with the same method:

INNA¡€ṠS÷3r`
INA¡€ṠNS÷3r`
_Ɲ-*×ƊṠS÷3r`
etc.
\$\endgroup\$
0
4
\$\begingroup\$

05AB1E, 13 11 bytes

ÇÔ¥3%É·<O3÷

-2 bytes porting @LuisMendo's MATL answer, so make sure to upvote that answer as well!

Input as a string.
(If we're allowed to take the input as a list of codepoint-integers, the leading Ç can be removed for -1 byte.)

Try it online or verify all test cases.

Explanation:

Ç           # Convert the (implicit) input-string to a list of codepoint-integers
 Ô          # Connected uniquify it to remove non-moving cases
  ¥         # Pop and get the forward-differences (deltas) of this list
   3%       # Modulo-3 each difference
     É      # Modulo-2 each of those
      ·<    # Double and subtract 1 to convert the 0s to -1s (and 1s remain 1s)
        O   # Sum this list of 1s and -1s
         3÷ # Integer-divide it by 3
            # (after which the result is output implicitly)
\$\endgroup\$
0
2
\$\begingroup\$

Google Sheets, 100 bytes

=sort(let(a,mid(A1,row(A:A),2),int(sum(countif(a,{"ab","bc","ca"})-countif(a,{"ba","cb","ac"}))/3)))

Put the string in cell A1 and the formula in B1.

Counts instances of advancing and regressing letter pairs and divides by 3 à la Jonathan Allan's answer.

screenshot

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

MATL, 13 bytes

dXzI\oEqsI/Zo

Try it online! or verify all test cases.

Explanation

d    % Implicit input. Consecutive differences (of ASCII codes)
Xz   % Remove zeros
I\   % Modulo 3 (element-wise)
o    % Modulo 2 (element-wise)
E    % Times 2 (element-wise)
q    % Minus 1 (element-wise)
s    % Sum of all values
I/   % Divide by 3
Zo   % Round towards 0. Implicit display
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 22 bytes

﹪%d∕ΣEΦθκ⊖﹪⊕⁻℅ι℅§θ곦³

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

       θ                Input string
      Φ κ               Filter out first letter
     E                  Map over remaining letters
              ι         Current letter
             ℅          Ordinal
            ⁻           Minus
                §θκ     Previous letter
               ℅        Ordinal
           ⊕            Incremented
          ﹪             Modulo
                   ³    Literal integer `3`
         ⊖              Decremented
    Σ                   Take the sum
   ∕                    Divide by
                     ³  Literal integer `3`
﹪                       Format as string using
 %d                     Truncate to integer
                        Implicitly print

17 bytes if (as in all of the examples so far) the input can be assumed to start with a:

FSM⊖﹪⁻℅ιⅈ³→﹪%d∕ⅈ³

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

FS

Loop over the characters of the input string.

M⊖﹪⁻℅ιⅈ³→

Subtract the current position from the character's ordinal, reduce modulo 3, subtract 1, and add that to the current position.

﹪%d∕ⅈ³

Truncating divide the current position by 3.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ The examples do include bcab->1 and cabc->1 (although they can be easily missed due to the weird formatting). \$\endgroup\$
    – Arnauld
    Commented May 17 at 18:01
1
\$\begingroup\$

05AB1E, 9 bytes

Ç¥>3%<O3÷

Attempt This Online!

Ç¥>3%<O3÷
Ç           # Convert each element in the input to its ASCII value
 ¥          # Calculate the deltas
  >         # Increment each element by 1
   3%       # Take each element modulo 3
     <      # Decrement each element by 1
      O     # Sum the elements
       3÷   # Integer divide by 3
\$\endgroup\$
0
\$\begingroup\$

Retina 0.8.2, 70 bytes

(.)\1+
$1
\B
#
+T`#`-`b#a|c#b|a#c
+`\w|#-|-#

..?(.)?
$1
^(-)?.*
$1$.&

Try it online! Link includes test cases. Explanation:

(.)\1+
$1

Deduplicate consecutive letters.

\B
#

Insert #s between pairs of letters.

+T`#`-`b#a|c#b|a#c

Change #s to -s where the letters are anticlockwise.

+`\w|#-|-#

Delete the letters and cancel out adjacent #s and -s.

..?(.)?
$1

Integer divide by 3.

^(-)?.*
$1$.&

Convert to decimal.

\$\endgroup\$
0
\$\begingroup\$

Perl 5 -M5.010 -MList::Util=reduce -Minteger -pF, 53 bytes

reduce{$_=(ord$b)-ord$a;$\+=/2/?$_/-2:$_;$b}@F}{$\/=3

Try it online!

\$\endgroup\$
0
\$\begingroup\$

AWK, 113 bytes

{for(j=1;++i<length($0);){x=substr($0,i,2);x~"ab"||x~"bc"||x~"ca"?j++:0;x~"cb"||x~"ac"||x~"ba"?j--:0}}$0=int(j/3)

Try it online!

This will implicitly ignore double characters. I feel like there's a shorter trick somewhere, but my test haven't panned out.

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