33
\$\begingroup\$

Inspired by Is it double speak?, I devised a harder challenge. Given a string, determine if the string is n-speak, for any \$n\geq 2\$.

N-speak is defined by repeating each letter \$n\$ times. With \$n = 4\$, the string Hello is transformed to HHHHeeeelllllllloooo. Your goal is to figure out if the input is a valid output for any n-speak transformation.

It should be noted that any sentence which is valid n-speak, for \$n = 2k\$, is also valid k-speak. Thus, the hard parts to solve will be odd values of \$n\$.

Input

A string consisting of at least 2 characters. Input could also be a list of characters. Input is case sensitive.

Output

Truthy if the string is n-speak, falsey otherwise.

Examples

True cases

HHeelllloo,,  wwoorrlldd!!
TTTrrriiipppllleee   ssspppeeeaaakkk
QQQQuuuuaaaaddddrrrruuuupppplllleeee    ssssppppeeeeaaaakkkk
7777777-------ssssssspppppppeeeeeeeaaaaaaakkkkkkk
999999999
aaaabb
aaaaaaaabbbbcc
aaaaabbbbb
@@@

If you want to generate additional truthy cases, you can use this MathGolf script. Place the string within the quotation marks, and the value of \$n\$ as the input.

False cases

Hello, world!
TTTrrriiipppllleee   speak
aaaaaaaaaaaaaaaab
Ddoouubbllee  ssppeeaakk
aabbab
aaaabbb
a (does not need to be handled)
(empty string, does not need to be handled)

Of course, since this is code golf, get ready to trim some bytes!

\$\endgroup\$
  • \$\begingroup\$ Suggested test case: aabbab \$\endgroup\$ – Adám Aug 12 at 15:22
  • \$\begingroup\$ Suggested test case: aaaabbb \$\endgroup\$ – 640KB Aug 12 at 15:37
  • \$\begingroup\$ I'll add them both tomorrow, good suggestions. \$\endgroup\$ – maxb Aug 12 at 21:12
  • 4
    \$\begingroup\$ I am genuinely honoured and flattered that you have used and expanded my challenge :) \$\endgroup\$ – AJFaraday Aug 13 at 9:46
  • \$\begingroup\$ @AJFaraday glad that you liked it! I enjoyed both of your challenges, which gave me the idea for this one. There might be an even harder challenge coming soon. \$\endgroup\$ – maxb Aug 13 at 10:25

33 Answers 33

16
\$\begingroup\$

APL (Dyalog Unicode), 12 bytes

Runs with ⎕io←0

1≠∨/⍸2≠/∊0⍞0

Try it online!

Golfed together with Adám.

On the input (example: "aaccccaaaaaabb", using "" to denote a string (an array of chars) and '' to denote a char)

∊0⍞0 surround with 0s and flatten, 0 'a' 'a' 'c' 'c' 'c' 'c' 'a' 'a' 'a' 'a' 'a' 'a' 'b' 'b' 0

2≠/ perform pairwise not-equal, 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1

get the 0-indexed indices, 0 2 6 12 14

∨/ compute the GCD, 2

1≠ is this not equal to 1?

\$\endgroup\$
10
\$\begingroup\$

Java 10, 85 bytes

s->{var r=0>1;for(int i=0;++i<s.length();)r|=s.matches("((.)\\2{"+i+"})*");return r;}

Regex ported from @Arnauld's JavaScript answer.

Try it online.

Explanation:

s->{                          // Method with String parameter and boolean return-type
  var r=0>1;                  //  Result-boolean, starting at false
  for(int i=0;++i<s.length();)//  Loop `i` in the range [1, input-length):
    r|=                       //   Change the result to true if:
      s.matches("((.)\\2{"+i+"})*");
                              //    The input-String matches this regex
                              // NOTE: String#matches implicitly adds a leading ^ and 
                              //       trailing $ to match the full String
  return r;}                  // After the loop, return the result-boolean

Regex explanation:

^((.)\2{i})*$                 // Full regex to match, where `i` is the loop-integer
^           $                 // If the full String matches:
  (.)                         //  A character
     \2{i}                    //  Appended with that same character `i` amount of times
 (        )*                  //  And that repeated zero or more times for the entire string
\$\endgroup\$
8
\$\begingroup\$

Jelly, 5 bytes

Œɠg/’

Try it online!

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

JavaScript (ES6), 53 bytes

Derived from the regular expression used by @wastl in Is it double speak?.

s=>[...s].some((_,n)=>s.match(`^((.)\\2{${++n}})*$`))

Try it online!


Recursive version, 55 bytes

s=>(g=n=>s[++n]&&!!s.match(`^((.)\\2{${n}})*$`)|g(n))``

Try it online!

Commented

s => (                    // s = input string
  g = n =>                // g is a recursive function taking a repetition length n
    s[++n] &&             // increment n; abort if s[n] is not defined
    !!s.match(            // otherwise, test whether s consists of groups of:
      `^((.)\\2{${n}})*$` //   some character, followed by n copies of the same character
    )                     //
    | g(n)                // or whether it works for some greater n
)``                       // initial call to g with n = [''] (zero-ish)
\$\endgroup\$
7
\$\begingroup\$

05AB1E, 5 bytes

γ€g¿≠

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I thought my 14-byter in MathGolf was a good one, but you just crushed it. I'd love an explanation both for this and your Jelly answer. \$\endgroup\$ – maxb Aug 12 at 11:30
  • 2
    \$\begingroup\$ @maxb It really just takes the lengths of the group runs, calculates their GCD and tests if it's not 1. \$\endgroup\$ – Erik the Outgolfer Aug 12 at 11:30
6
\$\begingroup\$

Python 2, 73 70 69 67 bytes

lambda s:s in[''.join(c*n for c in s[::n])for n in range(2,len(s))]

Try it online!

-4 bytes, thanks to Jitse

\$\endgroup\$
  • 2
    \$\begingroup\$ You can save 3 bytes by replacing set(...) with {...} \$\endgroup\$ – Jitse Aug 12 at 11:06
  • 1
    \$\begingroup\$ Also, you can remove the space in ...1 in[... \$\endgroup\$ – Jitse Aug 12 at 12:34
  • \$\begingroup\$ @Jitse Thanks :) \$\endgroup\$ – TFeld Aug 12 at 12:36
5
\$\begingroup\$

Python 3, 69 bytes

lambda s:any(s=="".join(i*k for i in s[::k])for k in range(2,len(s)))

Try it online!

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

QuadS, 16 bytesSBCS

1≠∨/⍵
(.)\1*
⊃⍵L

Try it online!

1≠ is 1 different from

∨/ the GCD

 of the result of

(.)\1* PCRE Searching for any character followed by 0 or more repetitions thereof

⊃⍵L and returning the first of the match lengths (i.e. the length of the match)

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

Stax, 5 bytes

╢b}▄;

Run and debug it

Procedure:

  • Calculate run-lengths.
  • GCD of array
  • Is > 1?
\$\endgroup\$
4
\$\begingroup\$

T-SQL 2008 query, 193 bytes

DECLARE @ varchar(max)='bbbbbbccc';

WITH C as(SELECT number+2n,@ t
FROM spt_values
WHERE'P'=type
UNION ALL 
SELECT n,stuff(t,1,n,'')FROM C
WHERE left(t,n)collate Thai_Bin=replicate(left(t,1),n))SELECT 1+1/~count(*)FROM C
WHERE''=t

Try it online

\$\endgroup\$
  • \$\begingroup\$ Is "collate Thai_Bin" really necessary? \$\endgroup\$ – Dr Y Wit Aug 14 at 10:39
  • 1
    \$\begingroup\$ @DrYWit it depends, the database could be set up as case sensitive. But case sensitive databases are not a popular choice. This could be handled better differently using HASHBYTES or maybe VARBINARY, but that is more costly in bytes \$\endgroup\$ – t-clausen.dk Aug 14 at 10:46
4
\$\begingroup\$

PHP, 76 75 bytes

while(($x=strspn($argn,$argn[$n+=$x],$n))>1&&($m=max($m,$x))%$x<1);echo!$x;

Try it online!

First attempt, a somewhat naïve iterative approach.

Ungolfed:

// get the length of the next span of the same char
while( $s = strspn( $argn, $argn[ $n ], $n ) ) {

    // if span is less than 2 chars long, input is not n-speak
    if ( $s < 2 ) {
        break;
    }

    // k is GCD
    $k = max( $k, $s );

    // if span length does not divide evenly into GCD, input is not n-speak
    if( ( $k % $s ) != 0 ) {
        break;
    }

    // increment current input string index
    $n += $s;

}

-1 byte, thx to @Night2!

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

Perl 6, 30 27 26 bytes

{1-[gcd] m:g/(.)$0*/>>.to}

Try it online!

Also uses the GCD trick, but uses the index of the end position of each run matched by the regex. Returns a negative number (truthy) if n-speak, zero (falsey) otherwise.

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

Haskell, 48 bytes

import Data.List
f=(>1).foldr(gcd.length)0.group

Try it online!

Straightforward; uses the GCD trick.

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

Red, 80 bytes

func[s][repeat n length? s[if parse/case s[any[copy t skip n t]][return on]]off]

Try it online!

More idiomatic Red:

Red, 81 bytes

func[s][any collect[repeat n length? s[keep parse/case s[any[copy t skip n t]]]]]

Try it online!

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

Brachylog, 5 bytes

ġz₂=Ṁ

Try it online!

Takes input through the input variable and outputs through success or failure.

At first I thought this would actually be shorter than my solution to Is it double speak?, but then I realized that ġ can and will try a group length of 1.

ġ        It is possible to split the input into chunks of similar length
 z₂      such that they have strictly equal length, and zipped together
    Ṁ    there are multiple results
   =     which are all equal.
\$\endgroup\$
3
\$\begingroup\$

Japt , 8 bytes

ò¦ mÊrÕÉ

Try it

ò¦ mÊrÕÉ     :Implicit input of string
ò            :Partition by
 ¦           :  Inequality
   m         :Map
    Ê        :  Length
     r       :Reduce by
      Õ      :  GCD
       É     :Subtract 1
             :Implicit output of boolean negation
\$\endgroup\$
3
\$\begingroup\$

Kotlin, 78 bytes

{s->(2..s.length/2).any{i->s.chunked(i).all{z->z.length==i&&z.all{z[0]==it}}}}

Try it online!

Explanation

{s->                      Take a string as input
  (2..s.length/2)         The each string needs two parts at least, prevents the case "aaa" is 3-speak
    .any{i->              If there is any n (in this case i) that is n-speak return true
      s.chunked(i)        Split into length i substrings
      .all{z->            All substrings z
        z.length==i       Should be completely full, ie. "aaa"->["aa","a"]
        &&                And
        z.all{            All chars (it)
          z[0]==it        Should be the same as the first char
        }
      }
    }
  }
\$\endgroup\$
  • \$\begingroup\$ Perhaps the description is unclear, but "aaa" is valid 3-speak. The input string should have at least two characters, but they do not need to be different. \$\endgroup\$ – maxb Aug 13 at 5:04
  • \$\begingroup\$ @maxb, ok cool. That should be -2 bytes. Thanks for the update. I'll fix that tomorrow \$\endgroup\$ – Brojowski Aug 13 at 5:08
3
\$\begingroup\$

Scala, 80 bytes

s=>"(.)\\1*".r.findAllIn(s).map(_.size).reduce((x,y)=>(BigInt(x) gcd y).toInt)>1

Try it online!

PS. Original solution was based on split function but it's longer (83 bytes).

s=>(s+s).split("(.)(?!\\1)").map(_.size+1).reduce((x,y)=>(BigInt(x) gcd y).toInt)>1
\$\endgroup\$
  • \$\begingroup\$ This returns true for input aab, unfortunately. \$\endgroup\$ – maxb Aug 13 at 13:36
  • \$\begingroup\$ @maxb, thanks for checking. s. replaced with (s+s). to handle that. \$\endgroup\$ – Dr Y Wit Aug 13 at 15:33
  • \$\begingroup\$ Good job! Though now I noticed that it fails for aaaabb and aabbbb. \$\endgroup\$ – maxb Aug 13 at 16:57
  • \$\begingroup\$ @maxb, apologies, now I tested on all your test cases from starting post. \$\endgroup\$ – Dr Y Wit Aug 14 at 0:09
2
\$\begingroup\$

Wolfram Language (Mathematica), 34 bytes

GCD@@Length/@Split@Characters@#>1&

Try it online!

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

Perl 5 -p, 83 79 76 74 bytes

$_=s,(.)\1+,$t=length$&;$t/=2while$t%2-1;$r+=$t==($g||=$t);'',ge==$r&&/^$/

Try it online!

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

Brain-Flak, 96 bytes

{<>({}())<>({}[({})]){{}<>({}<>){{(({})){({}[()])<>}{}}<>([{}()]({}<>)<>)}(<>)<>}{}}<>{}({}[()])

Try it online!

Uses the same GCD trick that many other submissions use. Output is 0 if the input is not n-speak, and a positive integer otherwise.

# For each character in the input
{

  # Add 1 to current run length
  <>({}())<>

  # If current and next characters differ:
  ({}[({})]){

    # Clean up unneeded difference
    {}<>

    # Move current run length to left stack, exposing current GCD on right stack
    ({}<>)

    # GCD routine: repeat until L=0
    {

      # Compute L mod R
      {(({})){({}[()])<>}{}}<>

      # Move R to left stack; finish computing L mod R and push to right stack
      ([{}()]({}<>)<>)

    }

    # Push 0 for new run length
    (<>)<>

  }{}

}

# Output GCD-1
<>{}({}[()])
\$\endgroup\$
2
\$\begingroup\$

Oracle SQL, 182 bytes

select+1-sign(min(length(x)-(select sum(length(regexp_substr(x,'(.)\1{'||i||'}',1,level)))from t connect by level<length(x))))from(select x,level i from t connect by level<length(x))

It works with an assumption that input data is stored in a table t(x), e.g.

with t(x) as (select 'HHeelllloo,,  wwoorrlldd!!' from dual)
\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 29 23 bytes

{~|/(&/s@&1<s)!s:#'=:x}

Try it online!

edit: removed some unnecessary colons (i know when a monadic is required but it's not always clear to me if there's ambiguity so i default to including the colon) and changed the mod x-y*x%y to ngn/k's y!x, which meant i could remove a variable assignment

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

APL (Dyalog Unicode), 24 22 bytesSBCS

Anonymous tacit prefix function.

⊂∊1↓⍳∘≢{⍵/⍨(≢⍵)⍴⍺↑⍺}¨⊂

Try it online!

 enclose the string to treat map using the entire string
 e.g. "aaabbb"

⍳∘≢{ for each of the ɩndices 1 through the tally of characters in the string:
 e.g. 3

⍺↑⍺ take the current number of elements from the current number, padding with 0s
 e.g. [3,0,0]

(≢⍵)⍴ cyclically reshape into the shape of the tally of characters in the string
  e.g. [3,0,0,3,0,0]

⍵/⍨ use that to replicate the string's characters
  "aaabbb"

1↓ drop the first one (n = 1)

⊂∊ is the the entire string a member of that list?

\$\endgroup\$
  • \$\begingroup\$ Are you dividing the input string into n-sized chunks, and checking that all characters are equal within each chunk? I haven't gotten into APL, but it's definitely the most readable "golfing" language. \$\endgroup\$ – maxb Aug 12 at 10:57
  • \$\begingroup\$ @maxb I'm in the process of writing an explanation. I'm filtering with all possible masks [1,0,0,1,0,0…] etc. I'll be happy to teach you APL (it doesn't take long to learn). Just pop unto the APL Orchard. \$\endgroup\$ – Adám Aug 12 at 10:59
  • \$\begingroup\$ Here's {1<∨/≢¨⍵⊆⍨≢∘∪¨,\⍵} for 18 \$\endgroup\$ – Kritixi Lithos Aug 12 at 11:17
  • \$\begingroup\$ @Cowsquack Clever, and different, so why don't you post {1<∨/≢¨⍵⊆⍨≢¨∪\⍵}? \$\endgroup\$ – Adám Aug 12 at 11:23
  • \$\begingroup\$ Unfortunately it fails for aacccaaaaabb \$\endgroup\$ – Kritixi Lithos Aug 12 at 11:37
1
\$\begingroup\$

Retina 0.8.2, 28 bytes

M!`(.)\1*
.
.
^(..+)(\1|¶)*$

Try it online! Link includes test cases. Explanation:

M!`(.)\1*

Split the text into runs of identical characters.

.
.

Replace them all with the same character.

^(..+)(\1|¶)*$

Check whether the GCD of the lengths of the runs is greater than 1.

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

Japt -mR, 12 bytes

ÊÆóXäd_äe e

Try it

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

MathGolf, 14 bytes

£─╞möl╠mÅ▀£╙╓┴

Try it online!

Explanation

Checks all possible divisions of the input string into equal length chunks, and checks if there is a partition in which all chunks have just one unique character.

£                length of string with pop
 ─               get divisors
  ╞              discard from left of string/array (removes 1)
   mö            explicit map using 7 operators
     l           push input
      ╠          divide input into chunks of size k
       mÅ        explicit map using 2 operators
         ߜ      number of unique elements of list
           ╙     get maximum number of unique characters per chunk
                 loop ends here
            ╓    get the minimum of all maximums
             ┴   check if equal to 1
\$\endgroup\$
1
\$\begingroup\$

Pyth, 7 bytes

Outputs 0 for falsy inputs or a positive integer otherwise.

tiFhCr8

Try it online!

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

Pyth, 8 bytes

<1iFhMr8

Try it online!

<1iFhMr8Q   Implicit: Q=eval(input())
            Trailing Q inferred
      r8Q   Run length encode Q into [count, character]
    hM      Take first element of each
  iF        Reduce by GCD
<1          Is 1 less than the above? Implicit print
\$\endgroup\$
1
\$\begingroup\$

Perl 5 -n, 38 bytes

for$i(1..y///c){print/^((.)\2{$i})*$/}

Try it online!

The print"\n" in the footer is needed to separate the outputs.

Straightforward loop through all possible ns. Outputs nothing for "1-speak", anything else for n-speak where n > 1.

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