kdb programming challenge – square-free sequences

Matt Doherty kdb+ 12 Comments

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…

 

Matt Dohertykdb programming challenge – square-free sequences

Comments 12

  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}

  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}

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

  6. Aditya K

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

  7. Kevin Zielinski

    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.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax