Deux chemins partent dans tous les sens. Ils se croisent, mais où ?
Cette semaine, c'est Adrien qui vous propose un #KataOfTheWeek : Croisements
Briefing du Kata : Pour résoudre ce kata vous devrez trouver le croisement entre deux chemins qui se trouve le plus proche du point de départ.
Vous disposez de deux chemins qui partent du même point sur une grille. Un chemin est défini par une suite d'étapes séparées par des virgules : R8,U5,L5,D3.
Chaque étape est composée de deux parties :
- La direction: R(ight), L(eft), U(p), D(own).
- Un entier qui représente la distance parcourue dans cette direction
On cherche à déterminer le point où ces deux chemins se croisent qui est le plus proche du départ en utilisant la distance de Manhattan.
La réponse attendue est la distance (de Manhattan) entre le point de départ et l'intersection la plus proche.
Exemple :
Chemin 1 : R75,D30,R83,U83,L12,D49,R71,U7,L72
Chemin 2 : U62,R66,U55,R34,D71,R55,D58,R83
la réponse attendue est 221.
Maintenant que trouvez vous pour ceux-ci :
R998,U367,R735,U926,R23,U457,R262,D473,L353,U242,L930,U895,R321,U683,L333,U623,R105,D527,R437,D473,L100,D251,L958,U384,R655,U543,L704,D759,R529,D176,R835,U797,R453,D650,L801,U437,L468,D841,R928,D747,L803,U677,R942,D851,R265,D684,L206,U763,L566,U774,L517,U337,L86,D585,R212,U656,L799,D953,L24,U388,L465,U656,L467,U649,R658,U519,L966,D290,L979,D819,R208,D907,R941,D458,L882,U408,R539,D939,R557,D771,L448,U460,L586,U148,R678,U360,R715,U312,L12,D746,L958,U216,R275,D278,L368,U663,L60,D543,L605,D991,L369,D599,R464,D387,L835,D876,L810,U377,L521,U113,L803,U680,L732,D449,R891,D558,L25,U249,L264,U643,L544,U504,R876,U403,R950,U19,L224,D287,R28,U914,R906,U970,R335,U295,R841,D810,R891,D596,R451,D79,R924,U823,L724,U968,R342,D349,R656,U373,R864,U374,L401,D102,L730,D886,R268,D188,R621,U258,L788,U408,L199,D422,R101,U368,L636,U543,R7,U722,L533,U242,L340,D195,R158,D291,L84,U936,L570,D937,L321,U947,L707,U32,L56,U650,L427,U490,L472,U258,R694,U87,L887,U575,R826,D398,R602,U794,R855,U225,R435,U591,L58,U281,L834,D400,R89,D201,L328,U278,L494,D70,L770,D182,L251,D44,R753,U431,R573,D71,R809,U983,L159,U26,R540,U516,R5,D23,L603,U65,L260,D187,R973,U877,R110,U49,L502,D68,R32,U153,R495,D315,R720,D439,R264,D603,R717,U586,R732,D111,R997,U578,L243,U256,R147,D425,L141,U758,R451,U779,R964,D219,L151,D789,L496,D484,R627,D431,R433,D761,R355,U975,L983,U364,L200,U578,L488,U668,L48,D774,R438,D456,L819,D927,R831,D598,L437,U979,R686,U930,L454,D553,L77,D955,L98,U201,L724,U211,R501,U492,L495,U732,L511
L998,U949,R912,D186,R359,D694,L878,U542,L446,D118,L927,U175,R434,U473,R147,D54,R896,U890,R300,D537,R254,D322,R758,D690,R231,U269,R288,U968,R638,U192,L732,D355,R879,U451,R336,D872,L141,D842,L126,U584,L973,D940,R890,D75,L104,U340,L821,D590,R577,U859,L948,D199,L872,D751,L368,U506,L308,U827,R181,U94,R670,U901,R739,D48,L985,D801,R722,D597,R654,D606,R183,U646,R939,U677,R32,U936,L541,D934,R316,U354,L415,D930,R572,U571,R147,D609,L534,D406,R872,D527,L816,D960,R652,D429,L402,D858,R374,D930,L81,U106,R977,U251,R917,U966,R353,U732,L613,U280,L713,D937,R481,U52,R746,U203,L500,D557,L209,U249,R89,D58,L149,U872,R331,D460,R343,D423,R392,D160,L876,U981,L399,D642,R525,U515,L537,U113,R886,D516,L301,D680,L236,U399,R460,D869,L942,D280,R669,U476,R683,D97,R199,D444,R137,D489,L704,D120,R753,D100,L737,U375,L495,D325,R48,D269,R575,U895,L184,D10,L502,D610,R618,D744,R585,U861,R695,D775,L942,U64,L819,U161,L332,U513,L461,D366,R273,D493,L197,D97,L6,U63,L564,U59,L699,U30,L68,U861,R35,U564,R540,U371,L115,D595,L412,D781,L185,D41,R207,D264,R999,D799,R421,D117,R377,D571,R268,D947,R77,D2,R712,D600,L516,U389,L868,D762,L996,U205,L178,D339,L844,D629,R67,D732,R109,D858,R630,U470,L121,D542,L751,U353,L61,U770,R952,U703,R264,D537,L569,U55,L795,U389,R836,U166,R585,U275,L734,U966,L130,D357,L260,U719,L647,D606,R547,U575,R791,U686,L597,D486,L774,U386,L163,U912,L234,D238,L948,U279,R789,U300,R117,D28,L833,U835,L340,U693,R343,D573,R882,D241,L731,U812,R600,D663,R902,U402,R831,D802,L577,U920,L947,D538,L192
Saurez-vous résoudre le problème ?
Bon courage !
Et voici une solution proposée par l'auteur en kotlin :
La solution est 221
import kotlin.math.abs
val input = arrayOf("R998,U367,R735,U926,R23,U457,R262,D473,L353,U242,L930,U895,R321,U683,L333,U623,R105,D527,R437,D473,L100,D251,L958,U384,R655,U543,L704,D759,R529,D176,R835,U797,R453,D650,L801,U437,L468,D841,R928,D747,L803,U677,R942,D851,R265,D684,L206,U763,L566,U774,L517,U337,L86,D585,R212,U656,L799,D953,L24,U388,L465,U656,L467,U649,R658,U519,L966,D290,L979,D819,R208,D907,R941,D458,L882,U408,R539,D939,R557,D771,L448,U460,L586,U148,R678,U360,R715,U312,L12,D746,L958,U216,R275,D278,L368,U663,L60,D543,L605,D991,L369,D599,R464,D387,L835,D876,L810,U377,L521,U113,L803,U680,L732,D449,R891,D558,L25,U249,L264,U643,L544,U504,R876,U403,R950,U19,L224,D287,R28,U914,R906,U970,R335,U295,R841,D810,R891,D596,R451,D79,R924,U823,L724,U968,R342,D349,R656,U373,R864,U374,L401,D102,L730,D886,R268,D188,R621,U258,L788,U408,L199,D422,R101,U368,L636,U543,R7,U722,L533,U242,L340,D195,R158,D291,L84,U936,L570,D937,L321,U947,L707,U32,L56,U650,L427,U490,L472,U258,R694,U87,L887,U575,R826,D398,R602,U794,R855,U225,R435,U591,L58,U281,L834,D400,R89,D201,L328,U278,L494,D70,L770,D182,L251,D44,R753,U431,R573,D71,R809,U983,L159,U26,R540,U516,R5,D23,L603,U65,L260,D187,R973,U877,R110,U49,L502,D68,R32,U153,R495,D315,R720,D439,R264,D603,R717,U586,R732,D111,R997,U578,L243,U256,R147,D425,L141,U758,R451,U779,R964,D219,L151,D789,L496,D484,R627,D431,R433,D761,R355,U975,L983,U364,L200,U578,L488,U668,L48,D774,R438,D456,L819,D927,R831,D598,L437,U979,R686,U930,L454,D553,L77,D955,L98,U201,L724,U211,R501,U492,L495,U732,L511", "L998,U949,R912,D186,R359,D694,L878,U542,L446,D118,L927,U175,R434,U473,R147,D54,R896,U890,R300,D537,R254,D322,R758,D690,R231,U269,R288,U968,R638,U192,L732,D355,R879,U451,R336,D872,L141,D842,L126,U584,L973,D940,R890,D75,L104,U340,L821,D590,R577,U859,L948,D199,L872,D751,L368,U506,L308,U827,R181,U94,R670,U901,R739,D48,L985,D801,R722,D597,R654,D606,R183,U646,R939,U677,R32,U936,L541,D934,R316,U354,L415,D930,R572,U571,R147,D609,L534,D406,R872,D527,L816,D960,R652,D429,L402,D858,R374,D930,L81,U106,R977,U251,R917,U966,R353,U732,L613,U280,L713,D937,R481,U52,R746,U203,L500,D557,L209,U249,R89,D58,L149,U872,R331,D460,R343,D423,R392,D160,L876,U981,L399,D642,R525,U515,L537,U113,R886,D516,L301,D680,L236,U399,R460,D869,L942,D280,R669,U476,R683,D97,R199,D444,R137,D489,L704,D120,R753,D100,L737,U375,L495,D325,R48,D269,R575,U895,L184,D10,L502,D610,R618,D744,R585,U861,R695,D775,L942,U64,L819,U161,L332,U513,L461,D366,R273,D493,L197,D97,L6,U63,L564,U59,L699,U30,L68,U861,R35,U564,R540,U371,L115,D595,L412,D781,L185,D41,R207,D264,R999,D799,R421,D117,R377,D571,R268,D947,R77,D2,R712,D600,L516,U389,L868,D762,L996,U205,L178,D339,L844,D629,R67,D732,R109,D858,R630,U470,L121,D542,L751,U353,L61,U770,R952,U703,R264,D537,L569,U55,L795,U389,R836,U166,R585,U275,L734,U966,L130,D357,L260,U719,L647,D606,R547,U575,R791,U686,L597,D486,L774,U386,L163,U912,L234,D238,L948,U279,R789,U300,R117,D28,L833,U835,L340,U693,R343,D573,R882,D241,L731,U812,R600,D663,R902,U402,R831,D802,L577,U920,L947,D538,L192")
fun main() {
val path1 = input[0].toPath()
val path2 = input[1].toPath()
val result = path1.combinationsWith(path2)
.mapNotNull { (s1, s2) -> s1.intersectionWith(s2)?.getManhattan() }
.min()
println(result)
}
data class Point(val x: Int, val y: Int) {
fun withXDiff(x: Int) = Point(this.x + x, y)
fun withYDiff(y: Int) = Point(x, this.y + y)
fun getManhattan() = abs(x) + abs(y)
companion object {
val ZERO = Point(0, 0)
}
}
class PathStep(private val direction: Direction, private val length: Int, private var point: Point) {
val nextPoint by lazy {
when (direction) {
Direction.UP -> point.withYDiff(-length)
Direction.DOWN -> point.withYDiff(+length)
Direction.RIGHT -> point.withXDiff(+length)
Direction.LEFT -> point.withXDiff(-length)
}
}
private val range by lazy {
if (direction.isVertical) {
point.y.absRangeTo(nextPoint.y)
} else {
point.x.absRangeTo(nextPoint.x)
}
}
private val alignment by lazy {
if (direction.isVertical) {
point.x
} else {
point.y
}
}
override fun toString(): String {
return "($direction, $length, $point)"
}
fun intersectionWith(pathStep: PathStep): Point? {
if (!direction.isOrthogonalWith(pathStep.direction) || (point == Point.ZERO && pathStep.point == Point.ZERO)) {
return null
}
if (range.contains(pathStep.alignment) && pathStep.range.contains(alignment)) {
return if (direction.isVertical) {
Point(point.x, pathStep.point.y)
} else {
Point(point.y, pathStep.point.x)
}
}
return null
}
}
enum class Direction(private val char: Char, val isVertical: Boolean) {
UP('U', true),
DOWN('D', true),
RIGHT('R', false),
LEFT('L', false);
companion object {
fun fromString(str: Char) = values().find { it.char == str } ?: throw Exception()
}
fun isOrthogonalWith(direction: Direction) = direction.isVertical != isVertical
override fun toString(): String {
return char.toString()
}
}
fun String.toPath(): List<PathStep> {
var previous = Point(0, 0)
return this.split(",").map {
val s = it.toPathStep(previous)
previous = s.nextPoint
s
}
}
fun String.toPathStep(point: Point) = PathStep(Direction.fromString(this[0]), this.substring(1).toInt(), point)
fun Int.absRangeTo(value: Int) = if (this > value) value.rangeTo(this) else this.rangeTo(value)
fun <T, S> Collection<T>.combinationsWith(other: Iterable<S>): List<Pair<T, S>> {
return this.flatMap { first -> other.map { second -> Pair(first, second) } }
Votre équipe TakiVeille