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\$ – user41805 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

1
2
1
\$\begingroup\$

Dyalog APL, 13 11 bytes

⊢,/⍨⊣⌊1+∘⍴⊢

It does exactly as intended now. Stupid errors. Thanks to Adám for giving me the hint that there is an 11 byte solution, even though this isn't the one he was looking for.

\$\endgroup\$
  • \$\begingroup\$ … except when it doesn't. \$\endgroup\$ – Adám May 8 '17 at 11:13
  • \$\begingroup\$ There, it's fixed. \$\endgroup\$ – Zacharý May 8 '17 at 11:20
  • \$\begingroup\$ Good. Now golf it! (Hint: I can do it in 11.) \$\endgroup\$ – Adám May 8 '17 at 11:21
  • \$\begingroup\$ Well, now it works. \$\endgroup\$ – Zacharý May 8 '17 at 11:23
  • \$\begingroup\$ The third time's the charm. Still waiting for -2 bytes… \$\endgroup\$ – Adám May 8 '17 at 11:33
0
\$\begingroup\$

Standard ML, 68 bytes

fun f$n=List.tabulate(size$ -n+1,fn m=>substring($,m,n))handle _=>[]

Try it online! Example usage: f "abcdef" 3 returns ["abc", "bcd", "cde", "def"].

Explanation:

For two bytes more we can replace the identifier $ by s to get better readable code:

fun f s n=List.tabulate(size s-n+1,fn m=>substring(s,m,n))handle _=>[]

The function takes a string s and an integer n as arguments. List.tabulate(m,g) takes an integer m and some function g and builds the list [g 0, g 1, ..., g(m-1)]. In this case, we give for m the size of the string s minus the n-gram length n (+1 to avoid off-by-one-errors). For each such m we return the substring of s at position m with length n.

In case of n > size s, an exception is thrown. handle _=>[] catches the exception and returns the empty list.

\$\endgroup\$
0
\$\begingroup\$

brainfuck, 52 bytes

[[>],+[<]>-]>[->]<[[<]>[.>]<[<]++++++++++.>[-]>[>],]

Try it online!

Takes K as the value on the starting cell and the string as input.

\$\endgroup\$
0
\$\begingroup\$

q/kdb+, 19 bytes

Solution:

{(0-x)_x#'next\[y]}

Example:

q){(0-x)_x#'next\[y]}[4;"ABCDEFGHIJ"]
"ABCD"
"BCDE"
"CDEF"
"DEFG"
"EFGH"
"FGHI"
"GHIJ"
q){(0-x)_x#'next\[y]}[4;"AC"]
q)

Explanation:

Use next and scan over the input string, then take the first 'x' (sliding window size), then drop off the extras from the end:

{(0-x)_x#'next\[y]} / the solution
{                 } / anonymous lambda with implicit args x and y
          next\[y]  / take 'next' element of y until exhausted
       x#'          / x take-each (take first x chars of each)
 (0-x)              / negate x
      _             / drop (negative drops from the end rather than front)
\$\endgroup\$
0
\$\begingroup\$

Japt, 2 bytes

Straightforward, built-in solution.

ãV

Try it

\$\endgroup\$
1
2

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.