Slime Molds Can Count!

Question

Background

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.

Input

Your inputs shall be a list L of 2D integer coordinates in the native format of your language, and a nonnegative integer N. The list L is guaranteed to be duplicate-free, but it may not be sorted. The input N is between 0 and the length of L, inclusive.

The list L represents a set of coordinates for food sources. For example, the list

[(0,0),(2,-1),(3,1),(0,4),(5,5)]

could be interpreted visually as

     o
o


   o
o
  o

Output

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 L and K has size exactly N.
• The set K is connected as a subset of the integer grid (via orthogonal or diagonal adjacencies).
• If any coordinate of K is 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 L and N = 4 would be

[(0,0),(0,1),(0,2),(0,3),(0,4),(1,4),(2,4),(3,3),(3,2),(3,1),(3,5),(4,5),(5,5)]

which can be visualized as

   xxO
Oxx
x  x
x  x
x  O
O
  o

where each O represents a coordinate in both L and K, and each x represents a coordinate in K but not in L. 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 

Rules

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.

Test Cases

Your program should work on these lists for all applicable values of N.

[]
[(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)]

Visualized:

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

Answer 1

CJam, 77 95 bytes

I think this can be golfed a bit more, but here goes:

q~$<_{{:X;]{[X\]z::-~mhW*}$~:Y{_)Y1{_@=X@=}:B~-g-{+__X=!\}:C~1B=!&}g{_(Y0B-g-\C0B=!&}g}*]_&}L?p

Input goes like N <Array of coordinate array>. For example:

4 [[0 0] [1 5] [2 1] [0 3] [5 0] [5 5]]

Output:

[[0 5] [1 5] [0 4] [0 3] [0 0] [0 2] [0 1] [1 1] [2 1]]

Algorithm:

The algorithm is pretty straight forward and goes like:

• Sort the input coordinate array. This makes the coordinates sorted first by row and then by column.
• Now we pick first N points
• Now we reduce on these N points. The destination is the last point and the source is the closes point to that last point.
• Then we start with the top-left most point, walk right (or left) till its on or directly above the next point.
• Then we walk down to reach the next point.
• It is guaranteed that there will be no uncovered point left to the above point in the same row. This ensures that we do not touch any other point that the chosen N. Choosing the closes point also ensures that second rule is held true.

Try it online here