# 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:

*
*
*
*
*
*
*
*
*


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

This is code golf.

• So, the number of surjective functions? May 10 at 12:37
• I searched... Yeah, sort of... May 10 at 12:40
• 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? May 10 at 12:52
• I think so, but I am not quite fluent with "subjective functions". May 10 at 12:54
• en.wikipedia.org/wiki/Surjective_function May 10 at 12:54

# Wolfram Language (Mathematica), 17 bytes

#2!StirlingS2@##&


Try it online!

This is OEIS A019538.

• First time I've ever seen THAT builtin... May 10 at 15:27

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

# Python, 9795 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!

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

# 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!

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)


# Vyxals, 7 bytes

ɾ↔vUvL=


## 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¹=


# Vyxal, 8 bytes

ɾ↔vUvL=∑


Try it Online!

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