Slime molds are awesome. If you place them on a surface with food sources, they will spread their tendrils to find the food, after which they form a network of connections between the sources. In this challenge, you shall simulate a slime mold looking for food. Moreover, this particular mold will stop once it's found enough.
Your inputs shall be a list
L of 2D integer coordinates in the native format of your language, and a nonnegative integer
L is guaranteed to be duplicate-free, but it may not be sorted.
N is between 0 and the length of
L represents a set of coordinates for food sources.
For example, the list
could be interpreted visually as
o o o o o
Your output is another duplicate-free list
K of 2D integer coordinates on the same format as the input.
It represents the network formed by the slime mold, and it shall satisfy the following conditions:
- The intersection of
Khas size exactly
- The set
Kis connected as a subset of the integer grid (via orthogonal or diagonal adjacencies).
- If any coordinate of
Kis removed, it no longer satisfies the first two conditions.
Note that if
N = 0, the output must be an empty list.
An example of an acceptable output for the above list
N = 4 would be
which can be visualized as
xxO Oxx x x x x x O O o
O represents a coordinate in both
K, and each
x represents a coordinate in
K but not in
Other outputs are also acceptable, and the "tendrils" don't have to be the shortest possible.
For example, this is also an acceptable solution:
xxOxx Oxx x x x x x x o x O x Ox
Both the input and output shall be lists, not sets or other datatypes. The coordinates themselves can be lists or tuples. You can change the order of the two inputs if needed.
You can write either a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.
Your program should work on these lists for all applicable values of
 [(2,3)] [(0,0),(1,0),(0,1),(1,1)] [(0,0),(2,-1),(3,1),(0,4),(5,5)] [(0,0),(1,0),(2,0),(3,0),(0,3),(1,3),(2,3),(3,3)] [(0,0),(1,0),(2,0),(3,0),(0,3),(1,3),(2,3),(3,3),(0,1),(0,2),(3,1),(3,2),(8,1),(8,2),(-5,1),(-5,2)] [(0,0),(20,0),(15,15),(-10,4),(-10,3),(0,-5),(7,6),(7,7),(8,8),(9,8),(10,-2),(-1,12),(-3,10)] [(0,0),(1,0),(2,0),(3,0),(5,0),(6,0),(7,0),(0,9),(1,9),(2,9),(3,8),(4,9),(5,10),(6,10),(7,9),(3,3),(4,4),(5,5)]
=== o === oo oo === o o o o o === oooo oooo === oooo o o o o o o o o oooo === o o o oo o o o o o o o o === oo ooo o o o o o o oooo ooo