Continuing on from the number base challenge, this time around we will be looking at square-free sequences. Although they might seem a little disconnected right now, trust me there is a theme to these challenges; all will become clear in time!

In combinatorics a square-free word is any word which does not contain any subword twice in row. An equivalent way to state this is that there can be no repetitions of the form XX, where X can be any list of symbols (or just a single symbol). So for example the word “squarefree” is not square-free, the letter “e” repeats, whereas “square” is square-free.

So the challenge today is to make a function that returns a bool telling us if a given list is square-free. The function should work regardless of the list type. So for example:

```
q) f "squarefree"
0b
q)f "square"
1b
q)f 10b
1b
q)f 1010b
0b
```

If you’re dealing with a list of booleans (i.e. an alphabet of two symbols) there are only 6 squarefree lists:

```
0b
1b
01b
10b
010b
101b
```

but with larger alphabets there are an infinite number…

## Comments 12

my attempt…not particularly pretty

q)subs:{{(-1_x),’y}[x _:x]} //return all subsequences of a list

q)f:{all (raze/)(1+c)<>'(1_’) each (deltas each) each value each group each x subs c:til count x:(),x}

hey Jose, I can’t get your solution to work atm. Is it due to some missing char?

saw the provided solution now. Doh! I should have just compared each subsequence to the one prior…not sure why I went through all the trouble of grouping and counting etc….oh well 😛

f:{[s] min min each (,/){differ each y cut’ (til y)_: x}[s;] each 1+til ceiling count[s]{e673f69332cd905c29729b47ae3366d39dce868d0ab3fb1859a79a424737f2bd}2}

A little correction.

f:{[s] min min each (,/){differ each y cut’ (til y)_\: x}[s;] each 1+til ceiling count[s]{e673f69332cd905c29729b47ae3366d39dce868d0ab3fb1859a79a424737f2bd}2}

Great effort Akash thanks! I prefer using

`floor`

than`ceiling`

though since we know that the ceiling cut will not have a subsequence match anyway.Pingback: Square-free = not for squares

Below is my solution, and it’s not as elegant as answers posted above.

f:{i:1+(count x)div 2;f:{((til(count x)-y-1),:y) sublist:x};while[i-:1;if[any f[(i)_x;i]~’f[(neg i)_x;i];:0b]];:1b};

hi Wei, can’t seem to get your function working. Can you reformat your solution?

My function:

f:{“b”$prd {not “b”$sum raze {t:til count x; {x[y] ~ x[z]}[x]'[-1_t;1_t]} each y cut/:(til y)_:x}[x;] each -1_1+til count x};

why cant it be as simple as…

f:{all 1=count each group x}

f:{all 2>{(+/)x in y}[x;] each x}

This adds a series of boolean arrays together, each array representing the presence of each individual character within the initial array relative to its position. If after adding them all together the result is not a uniform array of 1’s then some elements were repeated and 0b is returned.