Connecting Dots

Question

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.

Answer 1

Wolfram Language (Mathematica), 17 bytes

#2!StirlingS2@##&

Try it online!

This is OEIS A019538.

Answer 2

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

Answer 3

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!

Answer 4

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)

Answer 5

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!

Answer 6

Charcoal, 23 bytes

Ｆ⊕η⊞υ¬ιＦＮＵＭυ×λ⁺κ§υ⊖λＩ⊟υ

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

Ｆ⊕η⊞υ¬ι

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

ＦＮ

Repeat n times:

ＵＭυ×λ⁺κ§υ⊖λ

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

Ｉ⊟υ

Output the last value calculated.