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
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 ...
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 ...