Questions tagged [open-ended-function]
For challenges where an exact output is not required but some property must still be fulfilled.
38
questions
67
votes
161
answers
10k
views
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:
...
- 38.4k
16
votes
8
answers
1k
views
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 ...
- 399
55
votes
36
answers
5k
views
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 ...
- 707
51
votes
30
answers
12k
views
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 ...
- 96.5k
4
votes
5
answers
570
views
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)...
- 8,696
24
votes
11
answers
3k
views
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 ...
- 15.4k
24
votes
16
answers
1k
views
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, ...
- 42k
14
votes
28
answers
2k
views
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.
...
- 2,191
12
votes
6
answers
888
views
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 ...
- 6,198
11
votes
8
answers
630
views
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 ...
- 39k
42
votes
70
answers
5k
views
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 ...
- 523
35
votes
1
answer
2k
views
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 ...
- 39.4k
35
votes
14
answers
3k
views
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 ...
- 635
26
votes
7
answers
1k
views
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 ...
- 96.5k
18
votes
9
answers
1k
views
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 ...
- 6,364
12
votes
6
answers
749
views
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 ...
- 49.6k
81
votes
82
answers
8k
views
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 ...
- 14.4k
47
votes
4
answers
4k
views
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 ...
- 196k
44
votes
32
answers
4k
views
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)) = -...
- 2,329
42
votes
21
answers
2k
views
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 ...
- 144k
38
votes
54
answers
3k
views
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 ...
- 23.3k
33
votes
10
answers
2k
views
Build a nest
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 ...
- 49.9k
29
votes
19
answers
3k
views
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 ...
- 1,875
28
votes
11
answers
2k
views
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 ...
- 7,828
27
votes
6
answers
5k
views
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, ...
- 7,197
27
votes
63
answers
3k
views
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 ...
- 26.5k
22
votes
24
answers
2k
views
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 ...
- 9,692
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 ...
- 96.5k
21
votes
10
answers
3k
views
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 ...
- 96.5k
17
votes
11
answers
2k
views
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 ...
- 13.1k
17
votes
15
answers
1k
views
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 ...
- 35.6k
16
votes
15
answers
1k
views
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 ...
- 523
15
votes
11
answers
967
views
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 ...
- 96.5k
8
votes
3
answers
495
views
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 ...
- 1,045
8
votes
3
answers
355
views
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 ...
- 3,707
6
votes
0
answers
195
views
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 ...
- 221
4
votes
7
answers
741
views
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 ...
- 20.5k
0
votes
6
answers
417
views
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 ...
- 1,473