21
\$\begingroup\$

Intro

We have had histograms and counting, but not listing all of them.

Every year, Dyalog Ltd. holds a student competition. The challenge there is to write good APL code. This is a language agnostic edition of this year's sixth problem.

I have explicit permission to post this challenge here from the original author of the competition. Feel free to verify by following the provided link and contacting the author.

Problem

The term k-mer typically refers to all the possible substrings of length k that are contained in a string. In computational genomics, k-mers refer to all the possible subsequences (of length k) from a read obtained through DNA Sequencing. Write a function/program that takes a string and k (the substring length) and returns/outputs a vector of the k-mers of the original string.

Examples

[4,"ATCGAAGGTCGT"]["ATCG","TCGA","CGAA","GAAG","AAGG","AGGT","GGTC","GTCG","TCGT"]

k > string length? Return nothing/any empty result:
[4,"AC"][] or "" or [""]

\$\endgroup\$
  • 4
    \$\begingroup\$ Does the order of the output matter? When a substring occurs multiple times, should it be repeated in the output? \$\endgroup\$ – feersum May 1 '17 at 8:02
  • 1
    \$\begingroup\$ Can I return a string of the required substrings separated by newlines instead of an array of strings, like this? \$\endgroup\$ – Leaky Nun May 1 '17 at 8:39
  • \$\begingroup\$ May we also input and output the string as an array of characters (like ['A', 'T', 'C', 'G'] instead of "ATCG"? \$\endgroup\$ – Adnan May 1 '17 at 8:39
  • \$\begingroup\$ Are Dyalog APL answers allowed in this PPCG challenge (because the challenge is also hosted by Dyalog)? \$\endgroup\$ – Kritixi Lithos May 1 '17 at 9:14
  • 1
    \$\begingroup\$ @feersum Order matters, and repetitions should be repeated. This is just like a sliding window. \$\endgroup\$ – Adám May 1 '17 at 12:29

35 Answers 35

15
\$\begingroup\$

Jelly, 1 byte

Jelly has a single byte dyadic atom for this very operation

Try it online! (the footer splits the resulting list with newlines, to avoid a mushed representation being printed.)

\$\endgroup\$
  • 1
    \$\begingroup\$ Somehow the OP must have known... \$\endgroup\$ – Leaky Nun May 1 '17 at 7:35
  • 1
    \$\begingroup\$ @LeakyNun I actually didn't. \$\endgroup\$ – Adám May 1 '17 at 12:26
8
\$\begingroup\$

Octave, 28 bytes

@(N,s)s((1:N)+(0:nnz(s)-N)')

Try it online!

For k > string length works in Octave 4.2.1-windows but in tio (Octave 4.0.3) doesn't work.

Creates numeric indexes of consecutive elements and index the string by it.

s= "ATCGAAGGTCGT"
N = 4
idx = (1:N)+(0:nnz(s)-N)'
 =
    1    2    3    4
    2    3    4    5
    3    4    5    6
    4    5    6    7
    5    6    7    8
    6    7    8    9
    7    8    9   10
    8    9   10   11
    9   10   11   12

s(idx) =

ATCG
TCGA
CGAA
GAAG
AAGG
AGGT
GGTC
GTCG
TCGT
\$\endgroup\$
7
\$\begingroup\$

05AB1E, 2 bytes

Code:

Ν

Explanation:

Π     # Get all substrings of the input
 ù     # Only keep the substrings of length the second input

Uses the 05AB1E encoding.

Try it online!

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

C (GCC on POSIX), 67 66 63 bytes

-3 bytes thanks to @LeakyNun!

f(i,s,j)char*s;{for(;j+i<=strlen(s);puts(""))write(1,s+j++,i);}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I don't think you need j=0. \$\endgroup\$ – Leaky Nun May 1 '17 at 10:08
  • \$\begingroup\$ @LeakyNun the function should be reusable. Try it online! vs Try it online! \$\endgroup\$ – betseg May 1 '17 at 11:43
  • \$\begingroup\$ Though if i do this... \$\endgroup\$ – betseg May 1 '17 at 11:46
  • 1
    \$\begingroup\$ You can replace j+i<=strlen(s) with just s[j+i] \$\endgroup\$ – Kritixi Lithos May 1 '17 at 16:01
5
\$\begingroup\$

Brachylog, 3 bytes

s₎ᶠ

Try it online!

Specs:

  • Input: ["ATCGAAGGTCGT",4]
  • Argument: Z
  • Output: Z = ["ATCG","TCGA","CGAA","GAAG","AAGG","AGGT","GGTC","GTCG","TCGT"]

How it works

s₎ᶠ
s    Output is a substring of first element of input,
 ₎   with length specified by second element of input.
  ᶠ  Find all solutions.
\$\endgroup\$
5
\$\begingroup\$

Python 3,  47 45 42 bytes

-3 bytes thanks to ovs (use Python 3's unpacking to reuse a[n-1:] at the tail.)

f=lambda a,n:a[n-1:]and[a[:n],*f(a[1:],n)]

A recursive function taking the string, a, and the slice length, n, and returning a list of the slices or an empty string.

a[n-1:] takes a slice of the current string from the n-1th (0-indexed) element onward to test whether there are enough elements remaining (an empty string is falsey in Python) - this is shorter than the equivalent len(a)>=n.

  • If there are enough elements a list is constructed, [...], with the first n elements of the string, a[:n], and the unpacked result of calling the function again, *f(...), with a dequeued version of the current input (without the first element), a[1:].

  • If there are not enough elements the tail of the recursion is reached when a[n-1:] is returned (in this case an empty string).

Try it online!


45 for Python 2 or 3 with:

f=lambda a,n:a[n-1:]and[a[:n]]+f(a[1:],n)or[]
\$\endgroup\$
  • \$\begingroup\$ f=lambda a,n:a[n-1:]and[a[:n],*f(a[1:],n)] for 42 bytes (Python 3) TIO \$\endgroup\$ – ovs May 1 '17 at 8:32
  • \$\begingroup\$ @ovs, very nice, I've asked if this is acceptable (since they empty result is a string, while the non-empty result is a list). \$\endgroup\$ – Jonathan Allan May 1 '17 at 9:29
4
\$\begingroup\$

J, 2 bytes

,\

It is not a complete program, but a function with an operator.

Call it as such:

echo 4 ,\ 'ATCGAAGGTCGT'

Try it online!

How it works

The operator (called "conjunction") \ (named "infix") is used as such:

(x u\ y) applies verb u to successive parts of list y (called infixes).

The function (called "verb") u in this case is the function , which is a simple "append" function:

Creates an array containing the items of x followed by the items of y.

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

Mathematica, 21 bytes

##~StringPartition~1&

Anonymous function. Takes a string and a number (in that order) as input and returns a list of strings as output.

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

R, 65 61 bytes

-2 bytes thanks to MickyT

-2 bytes by changing the indexing

returns an anonymous function.

function(s,n,x=nchar(s))`if`(n>x,'',substring(s,x:n-n+1,n:x))

substring cycles through the indices (as opposed to substr which does not), and if the starting index is less than 1, it defaults to 1 instead, so it checks and returns the empty string.

x:n-n+1 is equivalent to 1:(x-n+1) since : takes precedence over sums/differences

Try it online!

\$\endgroup\$
  • \$\begingroup\$ you can save a couple of bytes with function(s,n,x=nchar(s))if(n>x,'',substring(s,1:(x-n+1),n:x)) \$\endgroup\$ – MickyT May 1 '17 at 19:43
  • \$\begingroup\$ @MickyT, thanks! I also noticed I could drop some bytes by changing the index computation \$\endgroup\$ – Giuseppe May 1 '17 at 19:51
2
\$\begingroup\$

Pyth, 2 bytes

.:

It is not a complete program, but a built-in function.

Call it as such:

.:"ATCGAAGGTCGT"4

Try it online!

Full program:

.:.*

Try it online!

(The .* is splat.)

\$\endgroup\$
  • \$\begingroup\$ While it doesn't really matter, .:F is a byte shorter for the full program. \$\endgroup\$ – FryAmTheEggman May 1 '17 at 17:21
2
\$\begingroup\$

Jellyfish, 7 bytes

p
_I
\i

Try it online!

How it works

In linear: p(\(I,i)), where p is print and \ gets the required substrings.

I is the raw first input while i is the evaluated second input.

In Jellyfish, every function and operator gets two arguments, one from the right, and one from the bottom. Here, the function p gets the argument from the output of _, which is required if we are to use the operator \ to get substrings.

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

Python 2, 54 bytes

lambda x,n:map(''.join,zip(*[x[b:]for b in range(n)]))

Try it online!

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

Java (OpenJDK 8), 92 bytes

void f(String s,int n){for(int i=n;i<=s.length();)System.out.println(s.substring(i-n,i++));}

Try it online!

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

Clojure, 19 bytes

Well this is handy:

#(partition % 1 %2)

Examples:

(def f #(partition % 1 %2))
(println [(f 4 "ATCGAAGGTCGT")
          (f 4 "abc")])

[((A T C G) (T C G A) (C G A A) (G A A G) (A A G G) (A G G T) (G G T C) (G T C G) (T C G T))
 ()]
\$\endgroup\$
2
\$\begingroup\$

CJam, 4 bytes

{ew}

Anonymous block that expects the arguments on the stack and leaves the result on the stack after.

Try it online!

ew is a built-in that does exactly what is required.

\$\endgroup\$
  • 5
    \$\begingroup\$ I have only one thing to say: ew \$\endgroup\$ – Adám May 1 '17 at 14:30
2
\$\begingroup\$

Retina, 41 38 bytes

.*$
$*
!&`(.)+(?=.*¶(?<-1>.)+(?(1)¶)$)

Try it online!

Takes the string and count on separate lines. The first two lines are used to convert the count from decimal to unary, so if unary input is acceptable then the byte count would be reduced to 34 31. Edit: Saved 3 bytes thanks to @FryAmTheEggman. Or, if you prefer, a 48-byte version that handles newlines in the string, although that does produce confusing output:

.*$
$*
!&`(\S|\s)+(?=[\S\s]*¶(?<-1>.)+(?(1)$.)$)
\$\endgroup\$
  • \$\begingroup\$ @KritixiLithos I don't see how your solution takes the count into account... \$\endgroup\$ – Neil May 1 '17 at 11:52
  • \$\begingroup\$ Oh, sorry I just had a brain fart >_< \$\endgroup\$ – Kritixi Lithos May 1 '17 at 12:07
  • \$\begingroup\$ This doesn't necessarily work if the string can contain a newline, so I think you can change (?!) to . \$\endgroup\$ – FryAmTheEggman May 1 '17 at 17:34
2
\$\begingroup\$

Octave with Image Package, 29 bytes

@(s,n)[im2col(+s, [1 n])' '']

Try it online!

Explanation

The function im2col(m,b) takes a matrix m, extracts blocks of size b from it, and arranges them as columns. By default blocks are sliding (as opposed to distinct). Here the matrix m is a row vector of the ASCII codes of the input string s (this is done as +s, which is shorter than the standard double(s)), and the size b is [1 n] to obtain horizontally sliding blocks of n elements.

The result is transposed (using complex-conjugate transpose ', which is shorter than transpose .') to turn the columns into rows, and then it is converted back to char ([... ''], which is shorter than the standard char(...)).

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

oK, 2 bytes

':

oK has a sliding window operator!

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

Python 3, 49 bytes

f=lambda a,n:[a[i:i+n]for i in range(len(a)-n+1)]

Try it online!

A non-recursive solution, albeit not shorter.

Compatible with Python 2.

\$\endgroup\$
  • \$\begingroup\$ You can drop f=, saving two bytes, because you do not use f anywhere else. By default, functions that are just declared and not used can be left unnamed. \$\endgroup\$ – Mr. Xcoder May 2 '17 at 17:30
1
\$\begingroup\$

PHP, 75 Bytes

Online Version

for([,$n,$s]=$argv;$i+$n-1<strlen($s);)$r[]=substr($s,$i++,$n);print_r($r);

80 Bytes without double values

for([,$n,$s]=$argv;$i+$n-1<strlen($s);)$r[$p=substr($s,$i++,$n)]=$p;print_r($r);
\$\endgroup\$
1
\$\begingroup\$

Haskell, 39 bytes

n#s|length s<n=[]|1<2=take n s:n#tail s

Usage example: 4 # "ABCDEF" -> ["ABCD","BCDE","CDEF"]. Try it online!

A simple recursion that keeps the first n chars of the input string an continues with the tail of the string as long as its length is not less than n.

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

Microsoft Sql Server, 199 bytes

create function dbo.f(@s nvarchar(max),@ int)returns table as return
with v as(select 2 p,left(@s,@)g where len(@s)>=@ union all
select p+1,substring(@s,p,@)from v where len(@s)>p-2+@)select g from v

Check it.

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

PowerShell, 70 bytes

$b={$c,$s=$args;[regex]::matches($s,"(?=(.{$c}))")|%{''+$_.groups[1]}}

Try it online!

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

Stacked, 7 bytes

infixes

Try it online!

Pretty standard. Without this builtin, it becomes 20 bytes:

{%x#'y-#+:>y#-#>x\#}

Which is:

{%x#'y-#+:>y#-#>x\#}
{%                 }   dyad; first arg: x, second arg: y
  x#'                  length of x (the array)
     y-                minus y (the skew)
       #+              plus 1
         :>            range [x, y]
           y#-         y minus 1
              #>       range from [[x, y], [x, y] + y]
                x\#    get indices from x
\$\endgroup\$
1
\$\begingroup\$

MATL, 3 bytes

YC!

Try it online!

Explanation

YC   % Sliding blocks of input string with input size, arranged as columns
!    % Transpose
\$\endgroup\$
1
\$\begingroup\$

C# 89 bytes

void a(string s,int n){for(int i=n;i<=s.Length;)Console.WriteLine(s.Substring(i++-n,n));}

Try it online!

Best method I could find in C# is basically the same as Java

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

Ruby, 48 46 bytes

->(s,k){0.upto(s.size-k).map{|i|s[i..i+k-1]}}

No particular tricks, just a stabby-lambda defining a function that pulls the required substring from each valid starting point.

Saved two bytes, since there doesn't seem to be a need to store the lambda.

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

V, 16 bytes

òÀ|ly0Ïp
"_xòkVp

Not terribly well golfed I'm afraid, struggling with "delete the string if k > len(str)". Input is in the file, k is an argument. Golfing before explanation

Try it online!

\$\endgroup\$
  • \$\begingroup\$ What happens if you do not try to handle the k > len(str) case? \$\endgroup\$ – Adám May 2 '17 at 14:34
  • \$\begingroup\$ Depending on the method I use (in this one in particular) it just leaves the string as is \$\endgroup\$ – nmjcman101 May 2 '17 at 14:37
1
\$\begingroup\$

Standard ML (mosml), 109 65 61 bytes

fun f(n,x)=if n>length(x)then[]else List.take(x,n)::f(n,tl x)

Takes a number and a character list (quite a common alternative to strings in the SML world). (Really works on all lists of course.)

Usage:

- f(3,explode("ABCDEFGH"));
> val it =
    [[#"A", #"B", #"C"], [#"B", #"C", #"D"], [#"C", #"D", #"E"],
     [#"D", #"E", #"F"], [#"E", #"F", #"G"], [#"F", #"G", #"H"]] :
  char list list
- f(7, explode("ABCD"));
> val it = [] : char list list

Changelog:

  • Right, there is a standard library.. (-44 bytes)
  • Change comparison and nil to [] as suggested (-4 bytes)
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save a byte by changing if length(x)<n then to if n>length(x)then. However, as it is perfectly possible for SML to handle strings, I'm not sure it is allowed to require explode being already applied to the input string. \$\endgroup\$ – Laikoni May 13 '17 at 18:17
  • \$\begingroup\$ Also then nil else can be shortened to then[]else. \$\endgroup\$ – Laikoni May 13 '17 at 18:20
  • \$\begingroup\$ @Laikoni not sure either, but ¯\_(ツ)_/¯ \$\endgroup\$ – L3viathan May 13 '17 at 18:23
  • \$\begingroup\$ Using some other library functions I got a 68 byte version which deals with strings instead of char lists. Also your approach can be shortened to 54 bytes: fun f$n=if n>length$then[]else List.take($,n)::f(tl$)n. \$\endgroup\$ – Laikoni May 15 '17 at 7:52
1
\$\begingroup\$

JavaScript (Firefox 30-57), 51 bytes

(s,n,t='')=>[for(c of s)if((t+=c)[n-1])t.slice(-n)]

64 bytes in ES6:

(s,n,t=s.slice(0,--n))=>[...s.slice(n)].map(c=>(t+=c).slice(~n))
\$\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.