12
\$\begingroup\$

Overview

In this challenge, your task is to randomly generate a monotonic mathematical function between two sets.

Input

Your inputs are two positive integers s and n.

After getting these inputs, your program shall generate a random mathematical function f from the set {0,1,...,s-1}n to {0,1,...,s-1}. In other words, f is a "rule" that takes in an n-tuple of integers between 0 and s-1, and returns one such integer. Additionally, f should be monotonic in the following sense. If A and B are two n-tuples such that A[i] ≥ B[i] holds for every coordinate i, then f(A) ≥ f(B).

The exact distribution of the monotonic functions f doesn't matter, as long as each such function has a positive probability of being generated (assuming a perfect RNG).

Output

Your output shall be an enumeration of the inputs and outputs of f. It shall contain all n-tuples of integers between 0 and s-1 in some order, each one being followed by the corresponding output of f. The exact output format is flexible (within reason).

Examples

The inputs s = 3 and n = 2 might produce the output

(0, 0) 0
(0, 1) 1
(0, 2) 2
(1, 0) 0
(1, 1) 1
(1, 2) 2
(2, 0) 1
(2, 1) 1
(2, 2) 2

It contains all the pairs over the set {0, 1, 2} exactly once, and each one is followed by its f-value. The monotonicity condition is also satisfied. The tuples are given here in lexicographical order, but this is not necessary.

As another example, s = 2 and n = 4 might produce

(0, 0, 0, 0) 0
(0, 0, 0, 1) 0
(0, 0, 1, 0) 0
(0, 0, 1, 1) 0
(0, 1, 0, 0) 1
(0, 1, 0, 1) 1
(0, 1, 1, 0) 1
(0, 1, 1, 1) 1
(1, 0, 0, 0) 0
(1, 0, 0, 1) 1
(1, 0, 1, 0) 0
(1, 0, 1, 1) 1
(1, 1, 0, 0) 1
(1, 1, 0, 1) 1
(1, 1, 1, 0) 1
(1, 1, 1, 1) 1

The following are all possible outputs for s = 2 and n = 2 (up to reordering the tuples); your program should randomly output one of them:

(0,0) 0
(0,1) 0
(1,0) 0
(1,1) 0
-------
(0,0) 0
(0,1) 0
(1,0) 0
(1,1) 1
-------
(0,0) 0
(0,1) 0
(1,0) 1
(1,1) 1
-------
(0,0) 0
(0,1) 1
(1,0) 0
(1,1) 1
-------
(0,0) 0
(0,1) 1
(1,0) 1
(1,1) 1
-------
(0,0) 1
(0,1) 1
(1,0) 1
(1,1) 1

Rules and Scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. Code with explanation is preferred.

There are no restrictions on time complexity, but I'll give a bonus of -15 % if your solution is always guaranteed to finish in a certain amount of time (depending on the inputs, and assuming a perfect RNG that runs in constant time).

\$\endgroup\$
  • \$\begingroup\$ It might help if you completely enumerate all of the possible functions for a tiny case such as s=2 n=2. I had to read the description a few times to grasp how the randomness would come into play. \$\endgroup\$ – Sparr Sep 23 '15 at 18:47
  • \$\begingroup\$ @Sparr Good idea; edited. \$\endgroup\$ – Zgarb Sep 23 '15 at 18:53
  • \$\begingroup\$ is bounded runtime a requirement? I'm contemplating a solution that produces random functions until it finds a monotonic one. \$\endgroup\$ – Sparr Sep 23 '15 at 18:57
  • \$\begingroup\$ @Sparr I think I'll add a bonus for bounded runtime, so such a solution won't be disqualified. \$\endgroup\$ – Zgarb Sep 23 '15 at 19:00
  • \$\begingroup\$ @Zgarb - perhaps you should make a large bonus for solutions that are both bounded and likely to finish within an hour. \$\endgroup\$ – Glen O Sep 24 '15 at 6:46
4
\$\begingroup\$

Pyth, 35 bytes (38 - 15% = 31.45 farther down)

#I!sm><FhMds<MCeMd^JC,mOQK^UQvzK2JB

Demonstration

Input is in the format:

n
s

Output is in the format:

[[value, tuple], [value, tuple], ...]

Simply generates random possibilities and tests them.


Alternative 37 byte version which I believe qualifies for the bonus:

Of!sm><FhMds<MCeMd^T2mC,d^UQvz^UQ^Qvz

Demonstration

This starts by generating all possible monotonic functions, then outputs one at random. It is much slower, and tops out at 2,2.

\$\endgroup\$
  • \$\begingroup\$ Nice example with input 3, 2. Unfortunately, I didn't even get a response for 3, 3 in the online pyth executor. Is there an endless loop for this combination?! \$\endgroup\$ – bobbel Sep 23 '15 at 21:55
  • \$\begingroup\$ @bobbel The online executor has a timeout, I think. I try it locally. \$\endgroup\$ – isaacg Sep 23 '15 at 23:08
  • \$\begingroup\$ @bobbel It's not so much an infitie loop has a very slow one. It also works for 2, 4, but not much else. \$\endgroup\$ – isaacg Sep 23 '15 at 23:15
  • \$\begingroup\$ @bobbel I added something even slower. \$\endgroup\$ – isaacg Sep 24 '15 at 2:31
1
\$\begingroup\$

CJam, 40 bytes - 15% = 34 bytes

q~1$\m*\1$,m*{W$\.+2m*{:.<2b}%1&!},mR]zp

This approach generates all valid functions and then selects on at random. Run time is at least O(s2sn), but constant for a given input.

I doubt this is what the OP had in mind, but it is guaranteed to finish in a certain amount of time (depending on the inputs[...]) and therefore qualifies for the bonus.

Try it online in the CJam interpreter.

\$\endgroup\$
1
\$\begingroup\$

Julia, 64 bytes (-15% = 54.4)

g(s,n)=(K=rand(0:s-1,ntuple(n,i->s));for i=1:n K=sort(K,i)end;K)

Ungolfed:

function g(s,n)
  # Generates a random n-dimensional array with s per dimension
  # and all values being integers between 0 and s-1
  K=rand(0:s-1,ntuple(n,i->s))
  # Loop over the various dimensions
  for i=1:n
    # Sort in the current dimension
    K=sort(K,i)
  end
  return K
end

This will run quickly, with the only possible issue being with memory for large enough s and n (g(10,10) has to produce a 10^10 array, so obviously it's going to run out of memory - even if each number is one byte, that's 10 gigabytes of data).

Output is 1-based indexing, so to determine the result for a given input, you need to add one to each input value. For example, to find f(1,2,6,0,3), you need to examine K[2,3,7,1,4].

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.