# Road golf through the mountains

You have a bunch of cities on a grid which you wish to link up. Roads can be placed on any tile that doesn't contain a city, and connect to all roads or cities adjacent to them, vertically, horizontally or diagonally.

C
\
C-C


However, there are some mountains in your way. Roads can't pass through mountains, and have to go around them. In my examples/testcases, these will be be marked as M.

With

  M
C M C
M


Something like

  ^
/M\
C M C
M


Will have to be done.

Roads can go through mountain passes diagonally, for example

C M
\M
MM\
C


is valid.

Given an arrangement of cities and mountains, output the minimum number of roads needed to connect them all.

# Rules

Input can be taken however you like, as ascii-art, a matrix, the positions of the cities and mountains, etc.

You may assume that no adjacent cities (like CC) will ever be inputted.

# Testcases

Note: These are formatted as ASCII-art.

C C
=> 1

C C

C
=> 1 (in the centre)

C M C
=> 3

MMC
M
C M
=> 1

MMMMMMMMM
MCMCM   M
M M M M M
M M   M M
M MMMMM M
M       M
MMMMMMMMM
=> 15

C   C
C

C
C   C
=> 5

MMM
CMC
MMM
=> 5

C
MMMMMMMMMM
C        C
=> 11

• May roads cross? What is expected for ...../.MCM./.C.C./.MCM./.....
– tsh
Jun 4 at 11:49
• Why the test case with 6 cities output 7, not 5?
– tsh
Jun 4 at 11:53
• Can you draw the connections for the last test case? Jun 4 at 13:35
• @Jonah .RRRRRCRRRR./RMMMMMMMMMMR/.C........C.
– tsh
Jun 4 at 13:52
• Do cities that are already adjacent still need roads to connect them? For example is CC 0? Or is it 1? Or is it something else? Jun 5 at 6:33

# 05AB1E, 6354 52 bytes

Quite slow, but after some optimisation, this can now run some testcases!

2Føðδ.ø}©˜„ CSδQƶø0δK<®øg‰Uæé.ΔX«Dδ-nO3‹DvDδ*O}ßĀ}g


Try it online!

The algorithm used has complexity $$\\mathcal{O}\left(2^{n^2} n^6\right)\$$ (for a grid of size $$\n \times n\$$) and uses matrix multiplication (øδ*O), which is often incredibly slow in 05AB1E.

### How?

A slightly different interpretation of the tasks helps explaining the approach: Instead of placing roads, we can also place additional cities into the grid until all cities are connected.
The program tries all combinations of new cities in increasing order of new cities until it finds a valid solution.

To validate a given attempt we consider a graph where the vertices are cities and two cities are connected with an edge if they are vertically, horizontally or diagonally adjacent. Two cities are adjacent, iff their squared Euclidean distance is less than $$\3\$$.
This property can be used to calculate an adjacency matrix from a list of city coordinates. An undirected graph of $$\n\$$ vertices with adjacency matrix $$\A\$$ is connected, iff $$\A^n\$$ has no zeros. Example:

map
C
C C

city coordinates
[0,1], [1,0], [1,2]

pairwise squared Euclidean distances
0 2 2
2 0 4
2 4 0

1 1 1
1 1 0
1 0 1

A^3
7 5 5
5 4 3
5 3 4

min(A^3) = 3 > 0 => connected


Commented Code:

                         # pad with spaces
2F     }                 # execute two times:
ø                      #   transpose the grid
ðδ.ø                  #   and surround every row with spaces

# get coordinates of cities and spaces
˜                       # flatten the grid
„ CS                   # push [" ", "C"]
δQ                 # equality table (== [[char==" ", char=="C"] for char in flat_grid])
ƶ                # multiply each pair by its 1-based index
ø               # tranpose
0δK            # remove all zeros
<           # decrement by 1
# Now we have a two list of coordinates of spaces and cities in the flattened grid
®          # get the grid from the register
øg        # get the height (length of the tranpose)
‰       # divmod each flat index with this
# this results into the 2d-indices
# push cities and spaces seperately on the stack
U     # store coordinates of cities in variable X
# coordinates of spaces are now on top of the stack

# try subsets of the spaces until we get a connected graph
æ                        # push the powerset (all subsets) of space coordinates
é                       # sort by length
.Δ                  }  # find the first value for which the following is truthy
X«                   # append the existing cities to the current subset of spaces
D                  # duplicate
δ-                # subtraction table
n               # square each difference
O              # sum each pair of squared differences
3‹            # for each number: is it less than 3?
# this is the adjacency matrix A
D           # make a copy of the matrix
v    }     # for each row in A:
D         # duplicate current matrix
δ*O      # matrix multiplication (for symmetric matrices)
ßĀ   # is the minimum not 0?

g                        # take the length of the result


# 05AB1E, 31 bytes

Takes input as lists of 1-indexed coordinates of cities and mountains. Even less efficient if the input is not square.

«Z>ÝãsKæé.Δ¹«Dδ-nO3‹DvDδ*O}ßĀ}g


Try it online!

«        # concatenate cities and mountains
Z>      # maximum integer in the list + 1 (0 and +1 for padding)
Ý     # push range from 0 to this value
ã    # cartesian square: all 2d coordinates with values in that range
sK  # remove all cities and mountains, this leaves the coordinates of spaces
...     # same as above

• Much slower to save bytes - Now that's the code golf spirit! Jun 7 at 7:17
• So the algorithm is bruteforce, and the bit you described is just the code to verify each attempt? Jun 7 at 14:09
• @Hack5 exactly, added a sentence that hopefully clarifies this a bit :)
– ovs
Jun 7 at 14:35
• So I took the reverse approach, finding the paths between existing cities with Dijkstra and finding the shortest of these paths. I guess mine would be faster for very large grids with only 2 cities. Jun 7 at 17:09
• I have to check all the combinations of all the paths between all the cities. Whereas my solution scales with the number of cities, yours scales with the size of the grid. Jun 7 at 17:28

# Kotlin with JGraphT, 3009 2984 (thanks to ophact) bytes (plus header/footer)

import org.jgrapht.Graph
import org.jgrapht.GraphPath
import org.jgrapht.alg.connectivity.ConnectivityInspector
import org.jgrapht.alg.shortestpath.AllDirectedPaths
import org.jgrapht.alg.shortestpath.DijkstraManyToManyShortestPaths
import org.jgrapht.graph.DefaultDirectedGraph
import org.jgrapht.graph.DefaultEdge
import org.jgrapht.graph.DefaultUndirectedGraph
import org.jgrapht.graph.builder.GraphBuilder
import kotlin.streams.asStream

sealed class P
object C:P()
object M:P()
object E:P()
object R:P()
typealias D=Pair<Int,Int>
typealias L<T> =List<T>
typealias A<T> =Array<T>
typealias F=DefaultEdge
typealias G=BooleanArray
const val B=4
fun GraphPath<D,F>.v():A<D>{val r=arrayOfNulls<D>(edgeList.size+1)
r[0]=graph.getEdgeSource(edgeList.first())
edgeList.forEachIndexed{i,e->r[i+1]=graph.getEdgeTarget(e)}
return r as A<D>}
fun A<GraphPath<D,F>>.d()=sumOf{val table=if(B<=3){G(1 shl(B*2)){false}}else{H.get().also{for(i in it.indices){it[i]=false}}}
it.v().sumOf{val hash=(it.first+1)or(it.second+1).shl(B)
if(table[hash]){0}else{table[hash]=true
1}.toInt()}}
fun j(b:GraphBuilder<D,*,*>,x:Int,y:Int){val others=(x-1..x+1).flatMap{z->(y-1..y+1).map{z to it}}
fun g(g:L<L<P>>):Pair<Set<D>,Graph<D,F>>{val b=DefaultDirectedGraph.createBuilder<D,F>(::DefaultEdge)
val c=mutableSetOf<D>()
g.forEachIndexed{y,r->r.forEachIndexed{x,p->when(p){C->{c+=x to y
j(b,x,y)}
E->j(b,x,y)
R->error("")}}}
val width=g[0].size
g.indices.forEach{y->if (g[y][0]==M)j(b,-1,y)
if (g[y].last()==M)j(b,width,y)}
(0 until width).forEach{x->if (g[0][x]==M)j(b,x,-1)
if (g.last()[x]==M)j(b,x,g.size)}
return c to b.buildAsUnmodifiable()}
fun t(c: Set<D>, g:Graph<D,F>):Set<D>{val d=DijkstraManyToManyShortestPaths(g).getManyToManyPaths(c,c)
val h=c.flatMap{o->c.map{o to it}}.filter{if(it.first.first==it.second.first)it.first.second>it.second.second else it.first.first>it.second.first}.associateWith{d.getPath(it.first,it.second)}.map{it.key to AllDirectedPaths(g).getAllPaths(it.key.first,it.key.second,true,it.value.length)}
val j=h.map{it.first}
val k=h.map{it.second}
val l=k.s{val m=DefaultUndirectedGraph.createBuilder<D,F>(::DefaultEdge)
ConnectivityInspector(m.buildAsUnmodifiable()).isConnected}
return HashSet(l.asStream().parallel().map{it to it.d()}.min{n,o->n.second-o.second}.get().first.flatMap{it.v().asList()})}
fun a(a:String)=a.lines().map{it.map{when(it){'M'->M
'.',' '->E
'C'->C
'R'->R
else->null}}.filterNotNull()}.filter{it.isNotEmpty()}
fun l(data:L<L<P>>, route:Set<D>)=route.sumOf{if(it.second<0||it.second>data.lastIndex)return@sumOf 1
val row=data[it.second]
if(it.first<0||it.first>row.lastIndex)return@sumOf 1
if(row[it.first]==E)1.toInt()else 0}
inline fun<reified T>L<L<T>>.s(noinline test:(A<Boolean>)->Boolean)=List(size){listOf(false,true)}.c().filter(test).let{sequence{for(selection in it){yieldAll(filterIndexed { i, _->selection[i]}.c())}}}
inline fun <reified T>L<L<T>>.c()=sequence{if(isEmpty())return@sequence
val j=map{it.iterator()}.toTypedArray()
val v=j.map{it.next()}.toTypedArray()
yield(v.clone())
while(true){var i=0
while(!j[i].hasNext()){j[i]=get(i).iterator()
v[i]=j[i].next()
if(++i>lastIndex)return@sequence}
v[i]=j[i].next()
yield(v.clone())}}

fun main() {
val art = System.in.bufferedReader().readText()
val data = a(art)
val (cities, graph) = g(data)
val route = t(cities, graph)
println("Length: ${l(data, route)}") }  Here is the original, prior to golfing: import org.jgrapht.Graph import org.jgrapht.GraphPath import org.jgrapht.alg.connectivity.ConnectivityInspector import org.jgrapht.alg.shortestpath.AllDirectedPaths import org.jgrapht.alg.shortestpath.DijkstraManyToManyShortestPaths import org.jgrapht.graph.DefaultDirectedGraph import org.jgrapht.graph.DefaultEdge import org.jgrapht.graph.DefaultUndirectedGraph import org.jgrapht.graph.builder.GraphBuilder import java.util.concurrent.atomic.AtomicLong import kotlin.concurrent.thread import kotlin.streams.asStream sealed class Place object City : Place() object Mountain : Place() object Empty : Place() object Road : Place() typealias Coord = Pair<Int, Int> operator fun Coord.compareTo(other: Coord): Int { return first.compareTo(other.first).let { if (it == 0) second.compareTo(other.second) else it } } fun <T> Collection<T>.toHashSet() = HashSet(this) object HashTable : ThreadLocal<BooleanArray>() { override fun initialValue(): BooleanArray { return BooleanArray(1 shl (MAX_DIMEN_BITS * 2)) { false } } } const val MAX_DIMEN_BITS = 4 inline fun <reified V, E> GraphPath<V, E>.getVertexListFast(): Array<V> { val ret = Array<V?>(edgeList.size + 1) { null } ret[0] = graph.getEdgeSource(edgeList.first()) edgeList.forEachIndexed { i, edge -> ret[i + 1] = graph.getEdgeTarget(edge) } @Suppress("UNCHECKED_CAST") return ret as Array<V> } fun Array<GraphPath<Coord, DefaultEdge>>.distinctSize() = sumOf { path -> val table = if (MAX_DIMEN_BITS <= 3) { BooleanArray(1 shl (MAX_DIMEN_BITS * 2)) { false } } else { HashTable.get().also { for (i in it.indices) { it[i] = false } } } path.getVertexListFast().sumOf { val hash = (it.first + 1) or (it.second + 1).shl(MAX_DIMEN_BITS) if (table[hash]) { 0 } else { table[hash] = true 1 }.toInt() /* stupid overload resolution */ } } fun joinUp(builder: GraphBuilder<Coord, *, *>, x: Int, y: Int) { val others = (x - 1 .. x + 1).flatMap { otherX -> (y - 1 .. y + 1).map { otherY -> otherX to otherY } } others.forEach { builder.addEdge(x to y, it) } } fun createGraph(grid: List<List<Place>>): Pair<Set<Coord>, Graph<Coord, DefaultEdge>> { val builder = DefaultDirectedGraph.createBuilder<Coord, DefaultEdge> { DefaultEdge() } val cities = mutableSetOf<Coord>() grid.forEachIndexed { y, row -> row.forEachIndexed { x, place -> when (place) { City -> { cities += x to y joinUp(builder, x, y) } Mountain -> { } Empty -> joinUp(builder, x, y) Road -> error("Cannot pre-supply Roads") } } } val width = grid.first().size grid.indices.forEach { y -> if (grid[y].first() == Mountain) joinUp(builder, -1, y) if (grid[y].last() == Mountain) joinUp(builder, width, y) } (0 until width).forEach { x -> if (grid.first()[x] == Mountain) joinUp(builder, x, -1) if (grid.last()[x] == Mountain) joinUp(builder, x, grid.size) } return cities to builder.buildAsUnmodifiable() } fun joinCities(cities: Set<Coord>, graph: Graph<Coord, DefaultEdge>): Set<Coord> { val allPathsAlgo = AllDirectedPaths(graph) val dijkstraAlgo = DijkstraManyToManyShortestPaths(graph) val shortestPaths = dijkstraAlgo.getManyToManyPaths(cities, cities) val sourceTargets = cities.flatMap { outer -> cities.map { outer to it } }.filter { it.first > it.second } val shortestLengths = sourceTargets.associateWith { shortestPaths.getPath(it.first, it.second) } val allShortestPathsWithKey = shortestLengths.map { it.key to allPathsAlgo.getAllPaths(it.key.first, it.key.second, true, it.value.length) } val allShortestPathsKeys = allShortestPathsWithKey.map { it.first } val allShortestPaths = allShortestPathsWithKey.map { it.second } val i = AtomicLong() val (total, allPathsProduct) = allShortestPaths.selectiveCartesianProduct { selection -> val builder = DefaultUndirectedGraph.createBuilder<Coord, DefaultEdge> { DefaultEdge() } builder.addVertices(*cities.toTypedArray()) selection.mapIndexed { i, bool -> if (bool) allShortestPathsKeys[i] else null }.filterNotNull().forEach { builder.addEdge(it.first, it.second) } val selectionGraph = builder.buildAsUnmodifiable() ConnectivityInspector(selectionGraph).isConnected } val startTime = System.currentTimeMillis() val counterThread = thread(true) { try { while (true) { Thread.sleep(1000) val progress = i.getOpaque() val percent = (progress.toDouble() / total.toDouble()) * 100f print("Progress:$progress\t/ $total\t($percent%)\t(${System.currentTimeMillis() - startTime} ms)\r") } } catch (e: InterruptedException) { println() } } val ret = allPathsProduct .asStream() .parallel() .map { (it to it.distinctSize()).also { i.incrementAndGet() } } .min { left, right -> left.second - right.second }.get().first.flatMap { it.getVertexListFast().asIterable() }.toHashSet() counterThread.interrupt() counterThread.join() return ret } fun artToData(art: String) = art.lines().map { it.map { char -> when (char) { 'M' -> Mountain '.', ' ' -> Empty 'C' -> City 'R' -> Road else -> null } }.filterNotNull() }.filter { it.isNotEmpty() } fun plotRoute(data: List<List<Place>>, route: Set<Coord>): List<List<Place>> { val width = data[0].size val emptyLine = List<Place>(width + 2) { Empty } val newData = mutableListOf(emptyLine.toMutableList(), *data.map { mutableListOf(Empty, *it.toTypedArray(), Empty) }.toTypedArray(), emptyLine.toMutableList()) for (point in route) { if (newData[point.second + 1][point.first + 1] == Empty) { newData[point.second + 1][point.first + 1] = Road } } return newData } fun routeLength(data: List<List<Place>>, route: Set<Coord>): Int = route.sumOf { point -> if (point.second < 0 || point.second > data.lastIndex) return@sumOf 1 val row = data[point.second] if (point.first < 0 || point.first > row.lastIndex) return@sumOf 1 if (row[point.first] == Empty) 1.toInt() /* needed due to overload ambiguity */ else 0 } fun dataToArt(data: List<List<Place>>) = buildString { data.forEach { row -> row.forEach { place -> append( when (place) { City -> 'C' Empty -> '.' Mountain -> 'M' Road -> 'R' } ) } append('\n') } } inline fun <reified T> List<Collection<T>>.selectiveCartesianProduct(noinline test: (Array<Boolean>) -> Boolean): Pair<Long, Sequence<Array<T>>> { val selections = List(size) { listOf(false, true) }.cartesianProduct().filter(test) val total = selections.sumOf { selection -> val selected = filterIndexed { i, _ -> selection[i] } if (selected.isEmpty()) 0 else selected.fold(1L) { acc, value -> acc * value.size } } return total to sequence { for (selection in selections) { yieldAll(filterIndexed { i, _ -> selection[i] }.cartesianProduct()) } } } inline fun <reified T> List<Iterable<T>>.cartesianProduct() = sequence { if (isEmpty()) return@sequence val iterators = map { it.iterator() }.toTypedArray() val values = iterators.map { it.next() }.toTypedArray() yield(values.clone()) while (true) { var i = 0 while (!iterators[i].hasNext()) { // reset current iterator, move on to check next one iterators[i] = get(i).iterator() values[i] = iterators[i].next() if (++i > lastIndex) return@sequence } values[i] = iterators[i].next() yield(values.clone()) } } fun main() { val art = System.in.bufferedReader().readText() val data = artToData(art) val (cities, graph) = createGraph(data) val route = joinCities(cities, graph) println("Length:${routeLength(data, route)}")
val newData = plotRoute(data, route)
println(dataToArt(newData))
}


The algorithm is very intractable: with the sample with 6 cities, it takes ~300 minutes of CPU time on my high-end desktop

Note that if your input data is longer than 14 on any dimension, you have to increase MAX_DIMEN_BITS.

Input is sent to stdin followed by EOF (^D) as ASCII art.

• If this is the one you are willing to use, I recommend you delete the other one and keep this one.
– user100690
Jun 6 at 15:20
• Also, could you not reduce the length of your function names? routeLength -> R for example? As well as your variable names and some extraneous whitespace (in main, which presumably cannot be renamed)
– user100690
Jun 6 at 15:22
• I didn't count main in the byte count, so I didn't obfuscate it either. Maybe this is wrong, I'm new here :D Jun 6 at 15:35
• @ophact thanks, i missed some names to obfuscate, my eye glossed over them Jun 6 at 15:37
• @ophact I could delete the other one, but I'd like to keep the unobfuscated version available somewhere so people can rebuild it in a different language Jun 6 at 15:40

Ż€ZUƊ4¡µœẹ0ŒPçƇœẹ1$ḢL  Try it online! Also incredibly slow. For an input of size $$\n\times m\$$ with $$\x\$$ spaces, this has an absolute lower bound of $$\O(2^{2(n+m)+x})\$$, and that doesn't factor in the speed of Jelly's matrix power, or the fact that it has to calculate $$\2^{2(n+m)+x}\$$ Cartesian products with the number of cities in the input. There are various optimisations you can do if you know the input before hand. For example, this is a much faster version that works for inputs that can be constructed as going over the "top" of the mountains. # Jelly, 34 bytes ;’_þ²§<3æ*L$Ȧ
Ż€ZUƊ4¡µœẹ0ŒPçƇŒṪḢL


Try it online!

Exactly the same as the 36 byte version, but takes input as a matrix where 0 is a space, 1 is a city and [] is a mountain. For example, C M C is [[1, 0, [], 0, 1]]

## How they work

;_þ²§<3æ*L$Ȧ - Helper link. Takes S (indices of spaces) and C (indices of cities) ; - Concatenate _þ - Create a subtraction table ² - Square each § - Sums of each <3 - Less than 3?$  - To this square matrix M:
L   -   Get its length
æ*    -   Raise it to that power
Ȧ - Are all elements of the matrix non-zero?

FṀ‘Żṗ2ḟẎŒPçƇḢḢL - Main link. Takes [a, b] on the left
F               - Flatten
Ṁ              - Maximum
‘             - Increment
Ż            - Range from zero
ṗ2          - Cartesian square
This gets all possible coordinates, including an outer border
Ẏ        - Flatten the argument into a list of coords
ḟ         - Remove the mountain + city coords from the list
ŒP      - Powerset
Ḣ   - Extract the list of city coords
çƇ    - Keep the powerset elements that are truthy under the helper link
ḢL - Take the shortest one and return its length


;’_þ²§<3æ*L$Ȧ - Helper link. Takes S (indices of spaces) and C (indices of cities) ; - Concatenate ’ - Decrement to zero index _þ - Create a subtraction table ² - Square each § - Sums of each <3 - Less than 3?$  - To this square matrix M:
L   -   Get its length
æ*    -   Raise it to that power
Ȧ - Are all elements of the matrix non-zero?

Ż€ZUƊ4¡µœẹ0ŒPçƇœẹ1$ḢL - Main link. Takes matrix M on the left Ɗ4¡ - Do the following 4 times: Ż€ - Prepend a zero to each row Z - Transpose U - Reverse µ - Begin a new link with this bordered matrix M' as the argument œẹ0 - Get the indices of zeros ŒP - Powerset$   - To M':
œẹ1    -   Get the indices of ones
çƇ       - Keep the powerset elements that are truthy under the helper link
ḢL - Take the shortest one and return its length


The third one takes advantage of the fact [] is both falsey and non-zero, and replaces œẹ1\$ with ŒṪ which gets the indices of all truthy elements in M'

# Python 3 + numpy, 325 bytes

A (slightly faster) port of my 05AB1E solution. The computational complexity is still the same, but especially the matrix operations are faster.

from itertools import*
from numpy import*
def f(G):
E=enumerate;k=[' '];p,c,*s=[k*len(G[0])],[]
for y,r in E([k+r+k for r in p+G+p]):
for x,v in E(r):[s,p,p,c][ord(v)%4]+=[y,x],
for i in count():
for N in combinations(s,i):
v=array(c+[*N]);A=sum((v-v[:,None])**2,axis=2)<3
for _ in v:A=A@A
if A.min():return i


Try it online!

Ungolfed full program:

import itertools, sys
import numpy as np

grid = [list(line) for line in sys.stdin.read().splitlines()]
print(grid)
width = len(grid[0])

# pad with spaces on all sides
padding = [[' '] * width]
grid = [[' ', *row, ' '] for row in padding + grid + padding]

# get the coordinates of cities and empty spaces
cities = [[y, x] for y, row in enumerate(grid) for x, v in enumerate(row) if 'C' == v]
spaces = [[y, x] for y, row in enumerate(grid) for x, v in enumerate(row) if ' ' == v]

for i in range(len(spaces)):
# Iterate over all combinations of i new cities
for new_cities in itertools.combinations(spaces, i):
vertices = np.array([*cities, *new_cities])
adjacency = (np.sum((vertices - vertices[:, None])**2, axis=-1)<3)
`