Questions tagged [open-ended-function]

For challenges where an exact output is not required but some property must still be fulfilled.

Filter by
Sorted by
Tagged with
67 votes
161 answers

Print all integers

Write a program or function which will provably print all integers exactly once given infinite time and memory. Possible outputs could be: ...
Fatalize's user avatar
  • 38.4k
16 votes
8 answers

Code Golf: Mix the nuts so that none of the same kind are touching

Input: Input is a randomized array of nuts (in your language), the possible nuts follow. Your program must have a way of representing each kind of nut, such as an integer code. Program must be able ...
Thomas Dignan's user avatar
55 votes
36 answers

Turing-Complete Language Interpreter

A challenge I thought that would be very cool is to make an interpreter for a Turing-complete language of your choosing. The rules are simple: You may use any language to create this interpreter ...
arodebaugh's user avatar
51 votes
30 answers

What an Odd Function

Your task here will be to implement a function1 that forms a permutation on the positive integers (A bijection from the positive integers onto themselves). This means that each positive integer ...
Wheat Wizard's user avatar
  • 96.5k
4 votes
5 answers

Pack sequences of non-negative integers

Let N be the set of nonnegative integers, i.e. {0, 1, 2, 3, ...}. Let c0(N) be the set of all infinite sequences in N that converge to 0, i.e. { (xn) ∈ NN | xn → 0 as n → ∞}. c0(N)...
algorithmshark's user avatar
24 votes
11 answers

Bijective function ℤ → ℤⁿ

It is trivially possible to create a bijective function from \$\mathbb{Z}\$ (the set of all integers) to \$\mathbb{Z}\$ (e.g. the identity function). It is also possible to create a bijective ...
Esolanging Fruit's user avatar
24 votes
16 answers

Every Possible Cycle Length

A function (or program) which takes inputs and provides outputs can be said to have a cycle if calling the function on its own output repeatedly eventually reaches the original number. For instance, ...
isaacg's user avatar
  • 42k
14 votes
28 answers

Injection from two strings to one string

Challenge Write a program that applies an injective function which takes an ordered pair of strings as input and one string as output. In other words, each input must map to a unique output. ...
negative seven's user avatar
12 votes
6 answers

Bijection between binary strings and pairs thereof

Input: Either one or two strings consisting of '0's and '1's. If there are 2, they are separated by a space. All strings are of ...
cardboard_box's user avatar
11 votes
8 answers

Bijective mapping from integers to a variable number of bits

A variable number of bits is an array of 0 or more bits. So [0, 1] is a variable number of bits, but so is []. Write a function ...
orlp's user avatar
  • 39k
42 votes
70 answers

Infinitely many ℕ

Background: A sequence of infinite naturals is a sequence that contains every natural number infinitely many times. To clarify, every number must be printed multiple times! The Challenge: Output a ...
Adam Katav's user avatar
35 votes
1 answer

Write a program whose nontermination is independent of Peano arithmetic

Challenge Write a program P, taking no input, such that the proposition “the execution of P eventually terminates” is independent of Peano arithmetic. Formal rules (In case you are a mathematical ...
Anders Kaseorg's user avatar
35 votes
14 answers

Put together a Senate majority

There are one hundred members of the United States Senate. Assuming that nobody filibusters and that the Vice President isn't cooperating, at least fifty-one members are necessary to pass a bill. But ...
Sneftel's user avatar
  • 635
26 votes
7 answers

Decode the Void

A void list is a list that at no level contains any non-list objects. Or if you prefer a recursive definition The empty list is void A list containing only other void lists is void All void lists ...
Wheat Wizard's user avatar
  • 96.5k
18 votes
9 answers

Surjection from one string to two strings

This is the inverse of negative seven's question. Write a program or function which, given any single, possibly-empty string of printable ASCII (codes \$[32,126]\$) outputs or returns two strings of ...
GammaFunction's user avatar
12 votes
6 answers

Map a list of indefinite size to a number!

It is well known, in the field of Mathematics studying infinity, that the Cartesian product of any finite amount of countable sets is also countable. Your task is to write two programs to implement ...
Leaky Nun's user avatar
  • 49.6k
81 votes
82 answers

Print some JSON

This challenge is straightforward, but hopefully, there are plenty of avenues you can approach it: You need to print/return a valid JSON object of at least 15 characters, not counting unessential ...
Nathan Merrill's user avatar
47 votes
4 answers

f(g(x)) decreases while g(f(x)) increases

For this challenge you need to implement two functions, f and g, on the integers, such that f ∘ g is a strictly decreasing function while g ∘ f is a strictly increasing function. In other words, if ...
Martin Ender's user avatar
44 votes
32 answers

Define a function f such that f(f(n)) = -n for all non-zero integers n

This challenge was inspired by a programming blog I frequent. Please see the original post here: A Programming Puzzle Challenge Define a function \$f:\mathbb{Q}\to\mathbb{Q}\$ such that \$f(f(n)) = -...
ardnew's user avatar
  • 2,329
42 votes
21 answers

Three other numbers

Given three distinct numbers from \$1\$ to \$7\$, output three other distinct numbers from \$1\$ to \$7\$, that is having no numbers in common with the original numbers. Your code must produce a ...
xnor's user avatar
  • 144k
38 votes
54 answers

Output a random unary string

Your task is simple: output the letter x a random number of times. Every possible length of xs must have a non-zero probability ...
pxeger's user avatar
  • 23.3k
33 votes
10 answers

B​u​i​l​d a n​e​s​t

The challenge is simple: write a program or function that, when given a finite non-negative integer, outputs a nested array. The rules Your code must produce a unique valid nested array for every ...
ETHproductions's user avatar
29 votes
19 answers

Transform characters of your choice into "Hello, world!"

Write a program or function that takes a character as input and outputs a character. Also, choose a list of 13 distinct ASCII printable characters (32-126). When a character from this list is passed ...
Jiří's user avatar
  • 1,875
28 votes
11 answers

Infinite ordinals from a well-ordering

Your task is to write a short program that represents a large (infinite) ordinal, using a well-ordering of the set of positive integers. Your program will take two different positive integers and ...
AnttiP's user avatar
  • 7,828
27 votes
6 answers

Golf a number bigger than Loader's number

As a follow up to Shortest terminating program whose output size exceeds Graham's number and Golf a number bigger than TREE(3), I present a new challenge. Loader's number is a very large number, ...
PyRulez's user avatar
  • 7,197
27 votes
63 answers

Create an array with repeated numbers

Challenge Your task in this question is to write a program or a named function which takes a positive integer n (greater than 0) as input via STDIN, ARGV or ...
Optimizer's user avatar
  • 26.5k
22 votes
24 answers

Generate an arbitrary half of a string

Given a string \$ x \$, we say another string \$ y \$ is half of it, if both of the following properties are true: \$ y \$ is a (not necessarily continuous) subsequence of \$ x \$ - there exists a ...
Command Master's user avatar
21 votes
13 answers

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 ...
Wheat Wizard's user avatar
  • 96.5k
21 votes
10 answers

An unknowably odd function

This challenge initially appeared in this challenge as a an extra brain teaser. I am posting it with permission from the original author so that we can have a formal competition. Your task here ...
Wheat Wizard's user avatar
  • 96.5k
17 votes
11 answers

Shortest total non-primitive recursive function

Natural numbers ≡ \$\mathbb{N}≡\{0,1,2,...\}\$ The submission can be either a program or a function, both cases will henceforth be referred to as "function". The task is to golf the shortest ...
user41805's user avatar
  • 13.1k
17 votes
15 answers

Enumerate all pure sets

In set theory, a set is an unordered group of unique elements. A pure set is either the empty set \$\{\}\$ or a set containing only pure sets, like \$\{\{\},\{\{\}\}\}\$. Your challenge is to write a ...
emanresu A's user avatar
  • 35.6k
16 votes
15 answers

Average-ignorant sets of integers

Recently a friend of mine posed the following: What subset of the integers satisfies the condition if distinct a and b are in the subset, their average is not in the subset? I know the set of non-0 ...
Binary198's user avatar
  • 523
15 votes
11 answers

Make an infinite chain

Lets define a class of functions. These functions will map from the positive integers to the positive integers and must satisfy the following requirements: The function must be Bijective, meaning ...
Wheat Wizard's user avatar
  • 96.5k
8 votes
3 answers

One-to-one correspondence between pairs of integers and the positive integers

It is well-known that there are one-to-one correspondences between pairs of integers and the positive integers. Your task is to write code defining such a correspondence (by defining a pair of ...
Ewan Delanoy's user avatar
  • 1,045
8 votes
3 answers

Injectively saturate bit strings

It can be easily proven using Hall's marriage theorem that given fixed \$n\$ and \$k<n/2\$, there is an injective (one-to-one) function from all \$n\$-bit strings with \$k\$ ones to \$n\$-bit ...
Parcly Taxel's user avatar
  • 3,707
6 votes
0 answers

Give the best Chaitin incompleteness bound

This was originally a pure mathematics question, but I think I've got the best chance for an answer here. The Challenge For concreteness, consider Peano Arithmetic (PA). For some language L of your ...
Charles Wang's user avatar
4 votes
7 answers

Don't output the file

This rar file, when decompressed, gives a 65024-byte exe file. Requiring you to output the contents of that file would be ...
l4m2's user avatar
  • 20.5k
0 votes
6 answers

Generate number from given range

Your function must accept three numbers in any order: A signed real number (or ±Infinity) - The number (N) for which you have ...
EzioMercer's user avatar
  • 1,473