0
\$\begingroup\$

Connecting Dots

We define a type of question on the test, connecting the dots

Question parameters

There are two parameters. Suppose they are 5 and 4. The second one must be less than or equal to the first one.

Thus, the question will look like this:

*
         *
*
         *
*
         *
*
         *
*

Possible answers

An answer is termed logically possible if and only if:

  • Each dot on the left corresponds to one and only one dot on the right

  • Each dot on the right corresponds to at least one dot on the left (there is no maximum)

We describe an answer using a matrix, or list of lists.

For instance, [[0,0],[1,0],[2,1]] will link the dot indexed 0 on the left to the dot indexed 0 on the right, et cetera. You may choose to use 0-indexed or 1-indexed.

We define an answer's complexity...

...as the number of intersections there are. For instance, the complexity of the answer [[0,2],[1,1],[2,0]] to be 1 as they intersect at the same point (assuming they are evenly spaced out).

Purpose

  • Calculate the complexity of a given solution

Grading

This is code golf.

\$\endgroup\$
8
  • 2
    \$\begingroup\$ So, the number of surjective functions? \$\endgroup\$
    – Jonah
    May 10 at 12:37
  • \$\begingroup\$ I searched... Yeah, sort of... \$\endgroup\$ May 10 at 12:40
  • \$\begingroup\$ Can we say that the output is the number of (distinct) surjective functions f: A -> B, where the cardinality of A and B are respectively the question parameters? \$\endgroup\$
    – Matteo C.
    May 10 at 12:52
  • \$\begingroup\$ I think so, but I am not quite fluent with "subjective functions". \$\endgroup\$ May 10 at 12:54
  • \$\begingroup\$ en.wikipedia.org/wiki/Surjective_function \$\endgroup\$
    – Matteo C.
    May 10 at 12:54

6 Answers 6

5
\$\begingroup\$

Wolfram Language (Mathematica), 17 bytes

#2!StirlingS2@##&

Try it online!

This is OEIS A019538.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ First time I've ever seen THAT builtin... \$\endgroup\$
    – Romanp
    May 10 at 15:27
4
\$\begingroup\$

C (gcc), 42 bytes

f(a,b){return a--?b*(f(a,b)+f(a,b-1)):!b;}

Try it online!

This uses a recurrence relation. Let \$f(a,b)\$ be the number of answers for \$a\$ left dots and \$b\$ right dots.

Consider the first left dot; it is joined to one right dot, with \$b\$ possibilities.

  • If that right dot is joined to at least one other left dot, then the remaining \$a-1\$ left dots cover the \$b\$ right dots at least once each, for \$f(a-1,b)\$ possibilities.
  • If that right dot is not joined to any other left dot, then the remaining \$a-1\$ left dots cover the \$b-1\$ other right dots at least once each, for \$f(a-1,b-1)\$ possibilities.

Therefore, \$ f(a,b) = b \times (f(a-1,b) + f(a-1,b-1)) \$.

The base case is \$ f(0,0) = 1\$ and \$ f(0,b) = 0\$ for \$ b > 0 \$.

\$\endgroup\$
0
2
\$\begingroup\$

Python, 97 95 88 bytes

-2 bytes thanks to @Number Basher

from itertools import*
f=lambda a,b:sum(b==len({*x})for x in product(range(b),repeat=a))

Attempt This Online!

\$\endgroup\$
6
  • \$\begingroup\$ That's good!!! I especially like it because if the input is [2,3] or invalid, it gives out 0 which is sensible. \$\endgroup\$ May 10 at 13:09
  • \$\begingroup\$ Check this out, codegolf.stackexchange.com/questions/54/…. \$\endgroup\$ May 10 at 13:10
  • \$\begingroup\$ in short, you can use [*{*x}]==b instead of len(set(x))==b, which saves 4 bytes. \$\endgroup\$ May 10 at 13:11
  • 2
    \$\begingroup\$ Watch carefully the tip you linked and what's needed in this context \$\endgroup\$
    – Matteo C.
    May 10 at 13:16
  • \$\begingroup\$ Oops, I missed that, sorry. \$\endgroup\$ May 10 at 13:19
2
\$\begingroup\$

05AB1E, 10 bytes

LIãεÙg¹Q}O

Two loose inputs in reversed order.

Port of @MatteoC.'s Python answer, so make sure to upvote him as well!

Try it online or verify all test cases below 6.

Explanation:

          #  E.g. inputs: b=2,a=3
L         # Push a list in the range [1, first (implicit) input `b`]
          #  → [1,2]
 Iã       # Create all possible `a`-sized combinations from this list, using the
          # cartesian product
          #  → [[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2]]
   ε      # Map over each inner list:
    Ù     #  Uniquify it
          #   → [[1],[1,2],[1,2],[1,2],[2,1],[2,1],[2,1],[2]]
     g    #  Pop and push the length to get the amount of unique values
          #   → [1,2,2,2,2,2,2,1]
      ¹Q  #  Check if its equal to the first input `b`
          #   → [0,1,1,1,1,1,1,0]
   }O     # After the map: check how many were truthy by taking the sum
          #  → 6
          # (which is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Vyxal s, 7 bytes

ɾ↔vUvL=

Try it Online! or Run all the test cases below 6

How?

ɾ↔vUvL=
ɾ       # List in the range [1, (implicit) first input `b`]
 ↔      # Get all possible combinations of this list of size (implicit) second input `a`
  vU    # For each item, uniquify
    vL  # For each item, get the length
      = # Is each item equal to the (implicit) first input `b`?
        # `s` flag sums the top of the stack

Other 7-byters:

ɾ↔ƛUL;=
ɾ↔ƛUL¹=

Flagless:

Vyxal, 8 bytes

ɾ↔vUvL=∑

Try it Online!

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

Charcoal, 23 bytes

F⊕η⊞υ¬ιFNUMυ×λ⁺κ§υ⊖λI⊟υ

Try it online! Link is to verbose version of code. Explanation:

F⊕η⊞υ¬ι

Create a list of one 1 and k 0s corresponding to a 0-indexed first row of the table in OEIS linked by @alephalpha.

FN

Repeat n times:

UMυ×λ⁺κ§υ⊖λ

Update the row using the recurrence relation given in OEIS but also @m90's answer.

I⊟υ

Output the last value calculated.

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