# kdb programming challenge – square-free sequences

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! Not all squares are free

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…

kdb programming challenge – square-free sequences

1. Jose Cambronero

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}

1. 2. Jose Cambronero

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 😛

3. Akash

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

1. Akash

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

1. WooiKent Lee

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.

4. Pingback: Square-free = not for squares

5. Wei

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};

1. 6. 7. 8. 