16
\$\begingroup\$

A square-free word is a word consisting of arbitrary symbols where the pattern \$XX\$ (for an arbitrary non-empty word \$X\$) does not appear. This pattern is termed a "square". For example, squarefree is not square-free (using the lowercase letters as the alphabet), as the square ee appears; but word is square-free. Additionally, note that \$X\$ does not have to be a single symbol, so 1212 is not square-free, as 12 is repeated.

If the alphabet used has exactly one symbol, there are only two square-free words: the empty word, and the word of exactly one symbol.
For a binary alphabet, e.g. \$\{0,1\}\$, there are a finite number of square-free words: the empty word, \$0, 1, 01, 10, 010, 101\$. All other words made from just two symbols will contain a square.
However, for an alphabet of three or more symbols, there are an infinite number of square-free words. Instead, we can consider the number of words of length \$n\$ for an alphabet of \$k\$ characters:

\$\downarrow\$ Alphabet length \$k\$

    Word length \$n\$ \$\rightarrow\$

 \$0\$ \$1\$ \$2\$ \$3\$ \$4\$ \$5\$ \$6\$
\$1\$ \$1\$ \$1\$ \$0\$ \$0\$ \$0\$ \$0\$ \$0\$
\$2\$ \$1\$ \$2\$ \$2\$ \$2\$ \$0\$ \$0\$ \$0\$
\$3\$ \$1\$ \$3\$ \$6\$ \$12\$ \$18\$ \$30\$ \$42\$
\$4\$ \$1\$ \$4\$ \$12\$ \$36\$ \$96\$ \$264\$ \$696\$
\$5\$ \$1\$ \$5\$ \$20\$ \$80\$ \$300\$ \$1140\$ \$4260\$
\$6\$ \$1\$ \$6\$ \$30\$ \$150\$ \$720\$ \$3480\$ \$16680\$

For example, there are \$36\$ different squarefree words of length \$3\$ using a alphabet of \$4\$ symbols:

121 123 124 131 132 134 141 142 143 212 213 214 231 232 234 241 242 243 312 313 314 321 323 324 341 342 343 412 413 414 421 423 424 431 432 434

For a ternary alphabet, the lengths are given by A006156. Note that we include the zero word lengths for \$k = 1, 2\$ in the table above.

This is a (mostly) standard challenge. You must take one input \$k\$, representing the length of the alphabet. Alternatively, you may accept a list (or similar) of \$k\$ distinct symbols (e.g. single characters, the integers \$1, 2, ..., k\$, etc.). You can then choose to do one of the following:

  • Take a non-negative integer \$n\$, and output the number of square-free words of length \$n\$, using an alphabet with \$k\$ symbols
  • Take a positive integer \$n\$ and output the first \$n\$ elements of the sequence, where the \$i\$th element is the number of of square free words of length \$i\$ using an alphabet of \$k\$ symbols
    • Note that, as \$i = 0\$ should be included, \$n\$ is "offset" by 1 (so \$n = 3\$ means you should output the results for \$i = 0, 1, 2\$)
  • Take only \$k\$ as an input, and output indefinitely the number of square free words of increasing length, starting at \$i = 0\$, using the alphabet of \$k\$ symbols.
    • For \$k = 1, 2\$ you may decide whether to halt after outputting all non-zero terms, or to output 0 indefinitely afterwards

This is , so the shortest code in bytes wins.

Test cases

Aka, what my sample program can complete on TIO

 k => first few n
 1 => 1,  1,   0,    0,     0,      0,      0,     0,     0, ...
 2 => 1,  2,   2,    2,     0,      0,      0,     0,     0, ...
 3 => 1,  3,   6,   12,    18,     30,     42,    60,    78, ...
 4 => 1,  4,  12,   36,    96,    264,    696,  1848,  4848, ...
 5 => 1,  5,  20,   80,   300,   1140,   4260, 15960, 59580, ...
 6 => 1,  6,  30,  150,   720,   3480,  16680, 80040, ...
 7 => 1,  7,  42,  252,  1470,   8610,  50190, ...
 8 => 1,  8,  56,  392,  2688,  18480, 126672, ...
 9 => 1,  9,  72,  576,  4536,  35784, 281736, ...
10 => 1, 10,  90,  810,  7200,  64080, ...
11 => 1, 11, 110, 1100, 10890, 107910, ...
12 => 1, 12, 132, 1452, 15840, 172920, ...
13 => 1, 13, 156, 1872, 22308, 265980, ...
14 => 1, 14, 182, 2366, 30576, 395304, ...
15 => 1, 15, 210, 2940, 40950, 570570, ...
Improve this question
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Brownie points for beating/matching either of my 10 bytes in Jelly. Related \$\endgroup\$
    – caird coinheringaahin g ♦
    Commented Jan 24, 2022 at 0:04
  • 4
    \$\begingroup\$ The first few columns are \$1, k, k(k - 1), k(k - 1)^2, k^2(k - 1)(k - 2)\$. Is there a closed-form formula for all \$k\$? \$\endgroup\$
    – alephalpha
    Commented Jan 24, 2022 at 3:39
  • 2
    \$\begingroup\$ The \$n\$-th column is \$\sum_{w}k(k-1)\cdots(k-i(w)+1)\$, where \$w\$ runs over the square-free words of length \$n\$ in standard order, and \$i(w)\$ is the number of different characters in \$w\$. This isn't a closed-form formula, but it show that the \$n\$-th column is a polynomial in \$k\$ of degree \$n\$, and the polynomial is divisible by \$k(k-1)(k-2)\$ when \$n>3\$. \$\endgroup\$
    – alephalpha
    Commented Jan 24, 2022 at 6:20

13 Answers 13

Reset to default
6
\$\begingroup\$

Vyxal s, 9 bytes

ÞẊǎ:∷d=Ṡ†

Try it Online!

Vyxal, 10 bytes

ÞẊǎ:∷d=Ṡ†∑

Try it Online!

ÞẊ         # Cartesian product; all ways to choose n items from k
  -----    # Next bit contains only vectorising elements, applied to each
  ǎ:       # Get substrings and duplicate
    ---    # Next bit over each substring 
    ∷      # Get the second half
     d     # Double it
      =    # Is it equal to the original?
           # (If it is, that word's a square)
       Ṡ   # Sum each result - truthy if any are equal and word contains squares
        †  # NOT each result - those that are squarefree
         ∑ # Sum the result (s flag)
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Use s flag for -1 \$\endgroup\$
    – lyxal
    Commented Jan 24, 2022 at 0:48
6
\$\begingroup\$

Wolfram Language (Mathematica), 40 bytes

Count[Or@@@Tuples@##,_?(FreeQ[x_||x_])]&

Try it online!

Takes a list of \$k\$ distinct non-Boolean symbols and a non-negative integer \$n\$.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES7), 90 bytes

Expects (k)(n) and returns the number of square-free words of length \$n\$, using \$k\$ symbols.

k=>n=>eval("for(i=t=k**n;i--;)t-=/(-.*),\\1/.test([...Array(n)].map((_,j)=>~(i/k**j%k)))")

Try it online!

How?

The symbols are depicted with the decimal representation of the ones' complements of non-negative integers (\$-1\$, \$-2\$, \$-3\$, ... and so on) and implicitly joined with commas when the array is coerced to a string.

Hence the regular expression to detect squares: /(-.*),\1/.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Pyth, 17 bytes

lf!:T"(.+)\\1"0^F

Test suite

Takes input as a list/tuple of the alphabet as a string and the word length as an integer.

Explanation:
lf!:T"(.+)\\1"0^F  | Full code
lf!:T"(.+)\\1"0^FQ | with implicit variables filled
-------------------+--------------------------------------------------------------------------------------------------------
               ^FQ | Repeated cartesian product (get all combinations of elements of the alphabet of the appropriate length)
 f                 | Filter this list for elements T such that
  !:T         0    |  T does not match the regex pattern
     "(.+)\\1"     |   which searches for a repeated substring
l                  | Print the length of the filtered list
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Haskell, 118 bytes

s []=1>0
s l=and[take n l/=take n(drop n l)|n<-[1..length l]]&&s(tail l)
n!k=length$filter s$mapM id$replicate n[1..k]

Try it Online!

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

JavaScript (Node.js), 63 bytes

k=>g=(n,e,i=k)=>n?i&&g(n-1,[e,i])+g(n,e,i-1):!/(,.*)\1/.test(e)

Try it online!

JavaScript (Node.js), 82 bytes

(k,r=0)=>g=(n,e)=>n?[...Array(k)].map((_,i)=>g(n-1,[e,i]))|r:r+=!/(,.*)\1/.test(e)

Try it online!

Something like Arnauld's solution but recursive.

[e,i] finally returns ,1,2,1 which provides convenience for checking, no need to add minus sign.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Brachylog, 19 16 bytes

{gʰj₎∋ᵐ¬{s~jb}}ᶜ

Try it online!

-3 thanks to Fatalize actually reading the challenge 🙃

Input as a list [alphabet of n characters, k].

Phenomenally slow, and I still can't help thinking there's a somewhat shorter way to brute-force the words.

{             }ᶜ    Count how many ways it's possible to
     ∋ᵐ             choose an element from each of
 gʰj₎               k copies of the supplied alphabet
       ¬{    }      such that it is impossible to
         s          find a substring
          ~j        which is something concatenated to itself
            b       which is non-empty.

The empty list is considered a substring of itself but nothing else, so this is correct for \$n>0\$ without the b.

Brachylog, 16 bytes

gʰj₎ẋ{sᶠ~jˢcĖ}ˢl

Try it online!

More or less the same thing, but handling \$n=0\$ slightly differently might offer an opportunity to shave something off, maybe...

    ẋ               Get the Cartesian product of
gʰj₎                k copies of the supplied alphabet,
     {       }ˢ     then keep only the tuples for which
      sᶠ            the list of all substrings
        ~jˢ         filtermapped from "squares" to their halves
           c        concatenated
            Ė       is the empty list.
               l    How many remain?

The empty list is considered a substring of itself but nothing else, so this is correct for \$n>0\$ without the c.

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Note that when \$n = 0\$, the output should be 1, not 0 \$\endgroup\$
    – caird coinheringaahin g ♦
    Commented Jan 24, 2022 at 2:21
  • \$\begingroup\$ @cairdcoinheringaahing Didn't miss that in the question; not sure how I missed that in the output... \$\endgroup\$
    – Unrelated String
    Commented Jan 24, 2022 at 2:22
  • 1
    \$\begingroup\$ You can take the list of symbols as input as per the challenge description, so why not do this for 16 bytes: {gʰj₎∋ᵐ¬{s~jb}}ᶜ \$\endgroup\$
    – Fatalize
    Commented Jan 24, 2022 at 15:23
3
\$\begingroup\$

Husk, 10 bytes

#ȯΠṁoẊ≠½Qπ

Try it online! or Try first elements of first few test cases

Input is arg1=k, arg2=n. Outputs number of square-free words of length n, using an alphabet with k symbols.

         π  # Cartesian arg2-th power of range [1..arg1] 
#ȯ          # how many truthy elements of the following function:
        Q   #   get all contiguous sublists
   ṁo       #   and for each of them:
       ½    #     split them in half
     Ẋ≠     #     and check if both halves are unequal
  Π         #   now take the product of all of that 
            #   (so product is zero if any sublist contained
            #   non-unequal halves, non-zero [truthy] otherwise)
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 11 bytes

ãεŒε2äË≠]PO

Inputs \$n\$ and a list in the range \$[1,k]\$ and outputs the single result.

Try it online or verify all test cases.

Explanation:

ã         # Get the second (implicit) input-list [1,k] to the cartesian power of
          # the first (implicit) input-integer n, creating a list of all n-sized
          # sublists with elements from [1,k]
 ε        # Map over each inner list:
  Π      #  Get all its sublists
   ε      #  Map over each sublist:
    2ä    #   Split it into two equal-sized halves
      Ë≠  #   Check that both halves are NOT equal
 ]        # Close the nested maps
  P       # Take the product of each inner list
   O      # Take the sum to get the amount of truthy values
          # (after which this is output implicitly as result)
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ If it helps, you can take \$k\$ as the list [1,2,3,..,k] to save the first L \$\endgroup\$
    – caird coinheringaahin g ♦
    Commented Jan 24, 2022 at 15:50
  • \$\begingroup\$ @cairdcoinheringaahing That indeed helps to save 2 bytes. :) \$\endgroup\$
    – Kevin Cruijssen
    Commented Jan 24, 2022 at 15:54
3
\$\begingroup\$

Jelly, 10 bytes

ṗµẆ;"ḟƑ$)S

Try it online!

Went through no fewer than six 11-byters before finally reaching par, and turns out it's pretty much just what Dennis did on the linked challenge...

 µ      )     Map over
ṗ             the Cartesian power of the arguments:
  Ẇ           The list of the word's contiguous substrings
   ;"  $      with each one concatenated to itself,
      Ƒ       is it unchanged by
     ḟ        removing every substring of the word?
         S    Sum the results.
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Retina, 43 bytes

1A`
$
;
"$+"+%Lv$`(.).*;
$>`$1$'
A`(.+)\1
;

Try it online! No test suite due to the way the program uses history. Takes input as n on the first line and a string of k letters (any printable ASCII except semicolon) on the second. Explanation:

1A`

Delete n from the buffer.

$
;

Append a marker.

"$+"+%Lv$`(.).*;
$>`$1$'

Generate the Cartesian product.

A`(.+)\1

Remove all square results.

;

Count the remaining results.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Ruby, 64 bytes

->n,k{([*1..n]*k).permutation(k).uniq.count{|w|w*?_!~/(.+)_\1/}}

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python 3, 106 bytes

lambda k,n:sum(not re.search(r'(.+)\1',''.join(p))for p in i.product(k,repeat=n))
import itertools as i,re

Try it online!

Inputs a string of \$k\$ distinct characters and a positive integer \$n\$.
Returns the number of square-free words of length \$n\$ for alphabets of length \$k\$.

Improve this answer
\$\endgroup\$
0

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.