import kotlinx.coroutines.experimental.async
import kotlinx.coroutines.experimental.runBlocking
import kotlin.system.measureTimeMillis

data class City(
        val name: String
) {
    val fligths: MutableSet<Flight> = mutableSetOf()
}

data class Flight(
        val from: City,
        val destination: City
)

suspend fun fly(deep: Int, visitedCities: MutableSet<City>, city:City, previousFlight: Flight?): List<Flight>? {
    return city.fligths.filterNot {
        visitedCities.contains(city)
    }.flatMap {
        val visitedCopy = visitedCities.toMutableSet().apply {
            if(previousFlight!=null) add(it.from)
        }
        if(it.destination.name == "Vancouver") {
            listOf(async {
                mutableListOf<Flight>().apply {
                    if (previousFlight != null) add(previousFlight)
                    add(it)
                }
            })
        }
        else {
            listOf(async { fly(deep+1, visitedCopy, it.destination, it) })
        }
    }.flatMap {
        listOf(it.await())
    }.filterNotNull().maxBy {
        it.size
    }?.toMutableList()?.apply {
        previousFlight?.let {
            add(it)
        }
    }
}

fun main(args: Array<String>) = runBlocking {
    val cities = mutableListOf<City>()
    cities.apply {
        add(City("Vancouver"))
        add(City("Yellowknife"))
        add(City("Edmonton"))
        add(City("Calgary"))
        add(City("Winnipeg"))
        add(City("Toronto"))
        add(City("Montreal"))
        add(City("Halifax"))
    }
    cities[0].apply {
        fligths.add(Flight(this, cities[2]))
        fligths.add(Flight(this, cities[3]))
    }
    cities[2].apply {
        fligths.add(Flight(this, cities[0]))
        fligths.add(Flight(this, cities[6]))
        fligths.add(Flight(this, cities[1]))
        fligths.add(Flight(this, cities[3]))
    }
    cities[3].apply {
        fligths.add(Flight(this, cities[0]))
        fligths.add(Flight(this, cities[4]))
    }
    cities[4].apply {
        fligths.add(Flight(this, cities[0]))
        fligths.add(Flight(this, cities[5]))
    }
    cities[5].apply {
        fligths.add(Flight(this, cities[0]))
        fligths.add(Flight(this, cities[6]))
    }
    cities[6].apply {
        fligths.add(Flight(this, cities[0]))
        fligths.add(Flight(this, cities[7]))
    }
    cities[7].apply {
        fligths.add(Flight(this, cities[0]))
    }

    val time = measureTimeMillis {
        val result = fly(0, mutableSetOf(), cities[0], null)
        print(cities[0].name)
        result?.forEach {
            print(" -> ${it.destination.name}")
        }
        println(" (${result?.size} flights)")
    }
    println("$time ms")
}