Questions tagged [open-ended-function]
For challenges where an exact output is not required but some property must still be fulfilled.
40
questions
14
votes
3answers
217 views
Bijection between \$ \mathbb N \$ and at-most-\$n\$-ary trees
Background
Related: a golflang theory I posted in TNB a while ago
At-most-\$n\$-ary trees are rooted trees where each internal node has between 1 and \$n\$ children (inclusive). Two trees are ...
9
votes
0answers
109 views
NP-complete reduction: (grid-)Hamiltonian circuit
Background
Hamiltonian circuit problem is a decision problem which asks whether a given graph has a Hamiltonian circuit, i.e. a cycle that visits every vertex exactly once. This problem is one of the ...
26
votes
17answers
2k views
Give me odd, even, square, cube, prime and composite 3-digit numbers
Given a string which is guaranteed to be either odd, even, square, ...
9
votes
4answers
283 views
Venn of \$n\$ statements
Given a positive integer \$n\$, output \$n\$ 2D bool images with the same width and height such that:
Each image should be 4-connected, i.e. for each two pixels that are true, you can start from one ...
8
votes
8answers
671 views
Encode a Lenguage
The Len(language,encoding) family of languages is a variety of Lenguage derivatives. To encode a program into a Len language, you replace every character with its representation in a certain encoding, ...
19
votes
1answer
506 views
Demonstrate some advanced abstract algebra
Consider a binary operator \$*\$ that operates on a set \$S\$. For simplicity's sake, we'll assume that \$*\$ is closed, meaning that its inputs and outputs are always members of \$S\$. This means ...
9
votes
5answers
404 views
Rewrite strings without changing their order
Lexicographic Ordering
For this challenge we will be talking about the lexicographic ordering of strings. If you know how to put words in alphabetical order you already understand the basic idea of ...
15
votes
11answers
2k views
Generate a mantis's head (symmetrical triangle)
Given guaranteed strictly positive integers \$w\$ and \$n\$, output
An equilateral triangle array with side length \$w\$, filled with two distinct, consistent values. I'll call these ...
25
votes
10answers
2k views
Floor of complex number
Background
Complex floor is a domain extension of the mathematical floor function for complex numbers. This is used in some APL languages to implement floor ⌊, ...
16
votes
3answers
555 views
Compute the uncomputable ... sort of
Implement a function \$f\$ (as a function or complete program), such that
\$
\displaystyle\lim_{n\rightarrow \infty} f(n)
\$
converges to a number which is not a computable number.
Answers will be ...
35
votes
63answers
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 ...
10
votes
14answers
449 views
Golf a bijection \$\mathbb{N}^n\to\mathbb{N}\$
Your task is to write a program which implements a bijection \$\mathbb{N}^n\to\mathbb{N}\$ for \$n \ge 1\$. Your program should take \$n\$ natural numbers as input, in any acceptable method (including ...
asked Oct 25 '20 at 17:07
caird coinheringaahing
42.1k9 gold badges91 silver badges285 bronze badges
42
votes
21answers
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 ...
16
votes
11answers
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 ...
18
votes
10answers
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 ...
17
votes
8answers
988 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 ...
14
votes
28answers
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.
...
23
votes
4answers
3k 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, ...
18
votes
7answers
2k views
Hilbert's binary Hotel
In this challenge you will be asked to implement any function (or full program) that fulfills two properties. Those properties are:
Your function must be an injective (reversible) function from the ...
12
votes
9answers
1k views
BigNum Bakeoff Reboot
Some of you may be familiar with the BigNum Bakeoff, which ended up quite interestingly. The goal can more or less be summarized as writing a C program who's output would be the largest, under some ...
23
votes
11answers
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 ...
4
votes
17answers
406 views
Any digital permutation
Task
Your task is to output a single integer, with one restriction: its digits must be a permutation of [1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6].
For example, you could output 653443653152432, ...
18
votes
15answers
1k views
Design a commutative injective function between any (restricted) infinite set and unordered pairs thereof
Related, but this only requires positive integers and does not have to be commutative
The Cantor Pairing Function is described in this Wikipedia article. Essentially, it is an operation such that ...
7
votes
1answer
216 views
Fabricate Frequently Factored Functions
In one of this question's bonuses I asked you to design a permutation on the natural numbers such that the probability of a random term being odd was \$1\$. Now let's kick it up a notch. I want you ...
48
votes
23answers
11k 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 ...
10
votes
3answers
208 views
Two interwoven chains
In this question I defined a "chain" function as a function that:
is a permutation, meaning that every value maps to and is mapped to by exactly one value.
and allows any value can be obtained from ...
15
votes
10answers
890 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 ...
9
votes
11answers
405 views
Construct a Permuter
For this challenge you are going to make a function (your function may be a complete program) that takes a list as input and returns a permutation of that list. Your function must obey the following ...
14
votes
5answers
963 views
Golf a bijection within the natural numbers which map the primes to a proper subset of the primes
Definitions
A bijection from a set S to a set T is a function from S to ...
25
votes
7answers
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 ...
21
votes
2answers
466 views
Rational decomposition
Write functions \$x(a)\$, \$y(a)\$ and \$z(a)\$ such that for any rational \$a\$ all functions return rational numbers and
$$x(a) \times y(a) \times z(a) \times (x(a) + y(a) + z(a)) = a$$
You may ...
45
votes
4answers
3k 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 ...
45
votes
27answers
3k 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 ...
36
votes
1answer
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 ...
11
votes
6answers
656 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 ...
8
votes
3answers
446 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 ...
4
votes
5answers
541 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)...
5
votes
5answers
526 views
Add an integer to a set and take it back out
Definition: a set is a datatype which allows testing of inclusion ("does set X contain element Y?") but does not have order. Its size is the number of distinct elements it contains.
Define an ...
44
votes
32answers
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)) = -...
11
votes
6answers
818 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 ...
