Questions tagged [subsequence]

Challenges pertaining to a sequence within a larger sequence

Filter by
Sorted by
Tagged with
25 votes
30 answers
3k views

Backronymiser឵឵

Background A backronym is an acronym that was formed from an existing word. For example, spam is actually named after the canned meat product as used in the Monty Python sketch, but can be ...
  • 22.6k
14 votes
11 answers
1k views

Make the list Fibonacci-like

Related, but not dupe. Challenge A list of integers \$a_1, a_2, a_3, \dots, a_n\$ (\$ n ≥ 1 \$) is Fibonacci-like if \$a_i = a_{i-1} + a_{i-2}\$ for every \$i > 2\$. Note that every list that ...
  • 1,017
11 votes
7 answers
649 views

Shortest restricted superstring

Given two sets of strings, \$ D \$ and \$ R \$, find the shortest string which contains every string in \$ D \$, but contains none of the strings in \$ R \$. There are almost always multiple possible ...
  • 22.6k
19 votes
8 answers
2k views

Optimally break a string into words

Given a string, like potatocarrot, break it into the smallest number of substrings possible. These substrings can consist either be a single character, or one of a ...
32 votes
35 answers
3k views

Is it a fibonacci-like sequence?

The Fibonacci Sequence is a sequence of positive integers where the first two elements are 1 and the rest are the sum of the previous two. It begins \$1, 1, 2, 3, 5, 8, 13\$ and continues forever. But ...
  • 31.9k
12 votes
8 answers
801 views

All sequences as substrings

Make a program that outputs a sequence of integers so that every finite sequence of positive integers is a substring (continuous subsequence) of the output. For example, the following sequence ...
  • 6,775
22 votes
22 answers
1k views

How many laps around the permutation?

Your input is an array of numbers: a permutation of \$\{1, 2 \dots n\}\$ for some integer \$n \geq 2\$. How many times must you repeat this list before you can "pick out" the numbers \$[1, 2 ...
  • 66.2k
21 votes
13 answers
2k views

Output every sublist ... eventually

You will be given as input an infinite stream of positive integers. Your task is to write a program which outputs an infinite sequence of lists with two requirements: All lists in the output are ...
  • 90.2k
16 votes
16 answers
839 views

Shuffle a subsequence

Thanks to rak1507 for the suggestion "Random" in this challenge always refers to "uniformly random" - of all possible choices, each has an equal chance of being chosen. Uniform ...
24 votes
27 answers
1k views

Check if the string is reshaped

Challenge Given an input string X, determine if X can be obtained from reshaping a strict prefix of itself (a prefix that is not ...
  • 2,555
24 votes
29 answers
3k views

AoCG2021 Day 2: Naughty or nice?

Part of Advent of Code Golf 2021 event. See the linked meta post for details. The story continues from AoC2015 Day 5, Part 2. Santa needs help figuring out which strings in his text file are naughty ...
  • 66.1k
25 votes
33 answers
2k views

Even sum subarrays

Given an array of integers, count the number of contiguous subarrays with an even sum. You may assume that the array is non-empty, and contains only non-negative integers. This is code-golf, so the ...
  • 18.6k
12 votes
22 answers
2k views

Park, Lake, Santa Fe [closed]

Given a long multi-sentence string, the goal is the count the occurrences of the following words: park, lake, ...
  • 541
22 votes
22 answers
3k views

Longest Zero Sum Sub-array

Given an array of integers. Find out its longest sub-array (contiguous subsequence) whose sum is 0. The sub-array for output may be an empty array. Input Input an array of integers. Output Output the ...
  • 30.8k
33 votes
25 answers
4k views

Is there a single straight line in the matrix?

Inspired by Wzl Determine if a given square binary matrix has exactly one row or column consisting of entirely 1s, and the rest of the matrix is ...
20 votes
19 answers
2k views

Guide my eyes in the right direction

Inspired by this: http://nolandc.com/smalljs/mouse_reveal/ (source). A valid answer: Takes a number \$w\$ and (assumed non-negative) integer \$x\$. Starts with an integer list with a length of \$2^w\$...
  • 1,450
18 votes
19 answers
3k views

Did I die or not?

Given a permutation of the alphabet and an intended "word", determine if the word was guessed in a game of Hangman, where the permutation is the list of guesses. For example, given ...
14 votes
2 answers
489 views

What's my TIO uniqueness?

Try it online! currently has 680 listed languages, all of which are searchable. For most of those languages, when searching for it, you don't have to enter the entire string. For example, entering <...
12 votes
15 answers
789 views

Check if B is composed of substrings of A of length n

Given two strings \$ A \$ and \$ B \$ and a positive integer \$ n \$, determine whether \$ B \$ is composed entirely of (possibly overlapping) strict substrings of \$ A \$ of a length of at least \$ ...
  • 22.6k
18 votes
19 answers
3k views

cadaddadadaddddaddddddr - linked list accessing

Create a function (or closest equivalent, or full program) that takes an list of some datatype (your choice) that may be nested and a string (in either order), and generalizes the lisp c[ad]+r ...
  • 1,450
19 votes
13 answers
943 views

Count strictly overlapping substrings

Given two strings a and b, count how many times b occurs as a substring in ...
  • 22.6k
41 votes
36 answers
7k views

Speed of Lobsters

From the subreddit r/SpeedOfLobsters: Edit the text of an image to create a new phrase This meme format/style is pretty self-explanatory. Simply have a browse through the subreddit if you need more ...
20 votes
19 answers
2k views

Vandalizing Marquees

A marquee is a low-tech board that allows customizable letters. For example, here is a marquee: SALE ON SNEAKERS However, someone might come along and vandalize it ...
  • 13.5k
18 votes
19 answers
2k views

The Fibonacci Rectangular Prism Sequence

What is the Fibonacci Rectangular Prism Sequence? The Fibonacci Rectangular Prism Sequence is a sequence derived from the Fibonacci sequence starting with one. The first 3 numbers of the Fibonacci ...
  • 399
5 votes
11 answers
877 views

Even-Odd chunks

(Inspired by the Keg utility of this challenge) Given a non-empty input string, e.g. s c 1= e(a"E"), split the input into even-odd chunks. Example (Feel free to ...
's user avatar
4 votes
2 answers
225 views

How many ways can given subsequence occur in given sequence?

Let me know if this task has already been posed. I haven't found it when I looked. Input master sequence \$\ X = x_1\dots x_n\$: sequence of characters, eg. \$\rm international\$ subsequence \$\ Y = ...
  • 615
44 votes
23 answers
4k views

Is it a circumfix?

Introduction We all know prefixes and suffixes. But there are other types of affixes that exist too. Such as circumfixes, a type of affix that has two parts, one of which is a prefix and another of ...
  • 3,615
39 votes
27 answers
3k views

Length-terminated sequences

We all know the age-old debate - should strings be length-prefixed or should they be null-terminated? Well, you've run into a blob of binary data and apparently whoever made it decided that the best ...
  • 3,615
23 votes
10 answers
3k views

Where are they calling from?

When making phone calls internationally, phone numbers are prefixed with a code indicating what country the number is located in. These codes are prefix codes, meaning that no code is a prefix of ...
  • 3,615
5 votes
2 answers
498 views

Highest cardinality grouping of contiguous integers with minimum-sum threshold

Challenge Given an array of positive integers and a threshold, the algorithm should output a set of consecutive-element-groupings (subarrays) such that each group/subarray has a sum greater than the ...
16 votes
13 answers
942 views

Determine if a grid contains another grid

Challenge Create a function takes in two 2-dimensional arrays of characters (or strings if the programming language does not have characters as a datatype) as inputs: a and b. If your language does ...
  • 161
31 votes
31 answers
4k views

Greatest common substring

Create a program or function which takes a list of strings as input, and outputs the longest string that is a substring of all input strings. If there are several substrings of equal length, and no ...
  • 3,615
25 votes
29 answers
3k views

Make me a metasequence

Background For this challenge, a 'metasequence' will be defined as a sequence of numbers where not only the numbers themselves will increase, but also the increment, and the increment will increase by ...
5 votes
0 answers
210 views

Pattern Finder - Find Repeated Pattern in String [closed]

Introduction This is a little challenge with the goal of identifying repeated pattern "blocks" in a string, and outputting them with their frequency of occurence from left to right. A friend ...
19 votes
21 answers
911 views

Most contributing rows

Given a non-empty matrix of non-negative integers, answer which unique rows contribute most to the sum total of elements in the matrix. Answer by any reasonable indication, for example a mask of the ...
  • 28.3k
20 votes
23 answers
3k views

Playing with the musical turtle

My two kids like to play with the following toy: The colored areas with the shapes inside can be touched and the turtle then lights the area and plays a sound or says the name of the color or the ...
  • 12.6k
17 votes
18 answers
4k views

Longest Repeating Subsequence of a Single Digit

Challenge: Given a positive integer, output the longest single-digit subsequence that occurs at least twice, AND has boundaries of another digit (or the start/end of the integer). An example: Input: <...
1 vote
10 answers
2k views

Indent your code according to Fibonacci

Okay, so I saw this in a meme and decided it'd be the perfect code golf challenge: I prefer to increase the side of my indents according to the Fibonacci sequence: ...
  • 11.3k
10 votes
8 answers
578 views

Codegolf Rainbow : Sorting Colors with Reflection

Introduction: After I posted two rainbow-related challenges: Codegolf Rainbow : Fun with Integer-Arrays 1 and Codegolf Rainbow : Draw in Black-and-White 2, the following comment was made by @ChrisM in ...
22 votes
2 answers
480 views

Subset Sum Orderings

A set of n positive numbers has 2^n subsets. We'll call a set "nice" if none of those subsets have the same sum. ...
  • 41.4k
12 votes
8 answers
2k views

Indexing Cha-Cha Slide

Introduction: Although I originally had a Dutch song in my head, where the lyrics are: "Doe 'n stapje naar voren, en 'n stapje terug" (which translated to "Take a little step forward, and a little ...
23 votes
11 answers
2k views

The Ever-Increasing Graph

Consider a one-dimensional sequence of numbers within a fixed range, i.e. [1, 2, 4, 6, 8, 0, 2, 7, 3] in range [0, 10⟩ The Ever-Increasing Graph* ** is a line ...
  • 333
7 votes
5 answers
423 views

Visit and exit an array

Challenge: Input: An integer n (> 0) An integer-array a of size ...
16 votes
24 answers
1k views

ID generator with no matching contiguous pairs

Given 2 inputs (m=minimum starting id, n=number of ids), generate a sequential list of ids, starting at >=m, made up of the digits 0-9 where no 2 contiguous numbers are the same, e.g. 1232 is ok, 1233 ...
  • 689
28 votes
9 answers
1k views

Collapse the antistring

In this challenge you will be given an alphabetic string as input. We will define the "anti-string" of a given input to be the string with the case of all the letters inverted. For example ...
  • 90.2k
19 votes
25 answers
1k views

Column-wise summation of overlapping slices

Task Given a list of integers L and another integer s, the goal is to compute the column-wise sums of all s-length (potentially overlapping) slices of L, while pertaining their positions relative to ...
  • 41.6k
13 votes
3 answers
515 views

Remove entries from array to sort it and maximize sum of elements

This challenge is from an admission test to a closed number cyber security course. Anyway it doesn't have to do with cyber security, it's just to test the students logical and coding skills. Task ...
  • 251
0 votes
4 answers
182 views

Partition it into as few disjoint contiguous increasing subsequences as possible [closed]

Specification This challenge is simple to state: your input is a non-empty array of nonnegative integers, and your task is to partition it into as few substrings as possible, such that each substring ...
8 votes
8 answers
841 views

Extension of the Game of Sevens

Introduction Output all the numbers in specific base that would appear in an adapted version of the game of seven. Challenge Your task is to output all the numbers in a given base in a given range, ...
  • 3,577
10 votes
8 answers
395 views

Collection from a sequence that constitute a perfect square

Given the sequence OEIS A033581, which is the infinite sequence, the n'th term (0-indexing) is given by the closed form formula 6 × n2 . Your task is to write code, which outputs all the subsets of ...