cf. https://hsin.hr/2008/ (Final Exam #2)
class Solution { fun solution(arrows: IntArray): Int { var answer = 0 var oldp = Point(0, 0) val history = History() for(a in arrows){ val bar = Bar(oldp, oldp.move(a), a) if(!history.containsOverrideBarWith(bar)){ if(history.containsPoint(bar.end)) answer++ if(history.containsCrossBar(bar)) answer++ } history.add(bar) oldp = bar.end } return answer } } class History( val bars:MutableSet<Bar> = mutableSetOf(), val startPoints:MutableSet<Point> = mutableSetOf() ){ fun add(bar: Bar){ bars.add(bar) startPoints.add(bar.start) } fun containsPoint(p:Point):Boolean { return startPoints.contains(p) } fun containsCrossBar(b:Bar):Boolean { return bars.any{it.cross(b)} } fun containsOverrideBarWith(b:Bar):Boolean { return bars.any{it.overrideWith(b)} } } data class Bar( val start: Point, val end: Point, val dir: Int, val diagonal: Boolean ){ constructor(start:Point, end:Point, dir:Int): this(start, end, dir, (dir%2 != 0)) fun cross(b:Bar):Boolean{ return this.diagonal && b.diagonal && this.dir != b.dir && this.start.distanceOneTo(b.start) && this.end.distanceOneTo(b.end) } fun overrideWith(b:Bar): Boolean{ return this == b || b.start==end && b.end==start } } data class Point( val x: Int, val y: Int ){ fun distanceOneTo(p:Point):Boolean{ return Math.abs(this.x - p.x) + Math.abs(this.y - p.y) == 1 } fun move(arrow: Int):Point{ val xoffset = when(arrow){ 7,6,5 -> -1 1,2,3 -> 1 else -> 0 } val yoffset = when(arrow){ 7,0,1 -> -1 5,4,3 -> 1 else -> 0 } return Point(x+xoffset, y+yoffset) } }
TEST CASE
[6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] --> 3 [6, 5, 2, 7, 1, 4, 2, 4, 6] --> 3 [5, 2, 7, 1, 6, 3] --> 3 [6, 2, 4, 0, 5, 0, 6, 4, 2, 4, 2, 0] --> 3
speed up
class Solution { fun solution(arrows: IntArray): Int { var answer = 0 var oldp = Point(0, 0) val history = History() for(a in arrows){ //val bar = Bar(oldp, oldp.move(a), a) val bar = Bar(oldp, a) if(!history.containsOverrideBarWith(bar)){ if(history.containsPoint(bar.end)) answer++ if(history.containsCrossBar(bar)) answer++ } history.add(bar) oldp = bar.end } return answer } } class History( val bars:MutableSet<Bar> = mutableSetOf(), val startPoints:MutableSet<Point> = mutableSetOf(), val barsThatHasCross:MutableSet<Bar> = mutableSetOf(), val barsReversedDir:MutableSet<Bar> = mutableSetOf() ){ fun add(bar: Bar){ bars.add(bar) startPoints.add(bar.start) barsThatHasCross.addAll(bar.crosses()) barsReversedDir.add(bar.reverseDir()) } fun containsPoint(p:Point):Boolean { return startPoints.contains(p) } fun containsCrossBar(b:Bar):Boolean { return barsThatHasCross.contains(b) } fun containsOverrideBarWith(b:Bar):Boolean { // return bars.any{it.overrideWith(b)} return bars.contains(b) || barsReversedDir.contains(b) } } data class Bar( val start: Point, val end: Point, val dir: Int, val diagonal: Boolean ){ constructor(start:Point, dir:Int): this(start, start.move(dir), dir, (dir%2 != 0)) fun cross(b:Bar):Boolean{ return this.diagonal && b.diagonal && this.dir != b.dir && this.start.distanceOneTo(b.start) && this.end.distanceOneTo(b.end) } fun crosses():List<Bar>{ return when(dir){ 1 -> listOf(Bar(start.move(0), 3), Bar(start.move(2), 7)) 3 -> listOf(Bar(start.move(4), 1), Bar(start.move(2), 5)) 5 -> listOf(Bar(start.move(4), 7), Bar(start.move(6), 3)) 7 -> listOf(Bar(start.move(0), 5), Bar(start.move(6), 1)) else -> listOf() } } fun reverseDir():Bar{ return Bar(end, (dir+4) % 8) } fun overrideWith(b:Bar): Boolean{ return this == b || b.start==end && b.end==start } } data class Point( val x: Int, val y: Int ){ fun distanceOneTo(p:Point):Boolean{ return Math.abs(this.x - p.x) + Math.abs(this.y - p.y) == 1 } fun move(arrow: Int):Point{ val xoffset = when(arrow){ 7,6,5 -> -1 1,2,3 -> 1 else -> 0 } val yoffset = when(arrow){ 7,0,1 -> -1 5,4,3 -> 1 else -> 0 } return Point(x+xoffset, y+yoffset) } }