Skip to content

Instantly share code, notes, and snippets.

@mayonesa
Last active February 6, 2022 22:31
Show Gist options
  • Save mayonesa/72089dc9933f85e7343b209d6177d18e to your computer and use it in GitHub Desktop.
Save mayonesa/72089dc9933f85e7343b209d6177d18e to your computer and use it in GitHub Desktop.
Given a board, `b`, with obstacles, guards, and an assassin, will determine if said assassin can reach the bottom right undetected
import scala.annotation.tailrec
/*
Assassin
--------
Write a method that given a board, `b`, with obstacles, guards, and an assassin, will determine if said assassin can
reach the bottom right undetected:
object Assassin {
def undetected(b: Array[String]): Boolean
}
The "board" is an array of same-size strings where each string is a row on the board and each array element is a
column. The assassin is represented with an `A`. The obstacles on the board are represented with an `X`. And, the guards are represented with `>`, `<`, `^`, or `v` where the pointy part of the guard points to its line of sight: right, left, up, or down, respectively. The assassin cannot cross a guard's line of sight and remain undetected. Also, the assassin cannot cross obstacles, `X`s, or guards. The goal is for the assassin, `A`, to get to the bottom right of the board undetected.
The following are some examples:
1. b: "AX..",
"....",
".X.."
goal: success
2. b: "AX..",
"..>.",
".X.."
goal: fail
reason: the only passageway, y: 1, x: 3, is in plain view of `>`.
Solve in an efficient manner.
*/
object Assassin {
private val X = 'X'
private val `.` = '.'
private val Up = (y: Int, x: Int) => (y - 1, x)
private val Down = (y: Int, x: Int) => (y + 1, x)
private val Left = (y: Int, x: Int) => (y, x - 1)
private val Right = (y: Int, x: Int) => (y, x + 1)
def undetected(b: Array[String]): Boolean = {
val n = b.head.length
val m = b.length
// fill lines of guard sight w/ Xs (including guard)
val (bWithXs, assassinYx) = (0 until m).foldLeft((b, Option.empty[(Int, Int)])) {
case ((b1, assassinYx0), y) =>
(0 until n).foldLeft((b1, assassinYx0)) { case ((b2, ayx1), x) =>
val currentRow = b2(y)
lazy val (l, r) = currentRow.splitAt(x)
lazy val (up, down) = b2.splitAt(y)
def gWithXs(row: String) = {
val (beginning, ending) = row.splitAt(x)
beginning + X + ending.tail
}
def insertWithX(l: String, r: String) = (up :+ (l + X + r)) ++ down.tail
currentRow(x) match {
case '>' =>
@tailrec
def loop(restOfRow: String, acc: String): String =
if (terminal(restOfRow, restOfRow.head)) acc + restOfRow
else loop(restOfRow.tail, acc :+ X)
val b3 = if (r.length > 1) {
val withXs = loop(r.tail, "")
insertWithX(l, withXs)
} else
b2
(b3, ayx1)
case '<' =>
@tailrec
def loop(restOfRow: String, acc: String): String =
if (terminal(restOfRow, restOfRow.last)) restOfRow + acc
else loop(restOfRow.init, X +: acc)
val b3 = if (l.isEmpty)
b2
else {
val withXs = loop(l, "")
insertWithX(withXs, r.tail)
}
(b3, ayx1)
case 'v' =>
@tailrec
def loop(restOfColumns: Array[String], acc: Array[String]): Array[String] = {
lazy val row = restOfColumns.head
lazy val c = row(x)
if (terminal(restOfColumns, c)) acc ++ restOfColumns
else loop(restOfColumns.tail, acc :+ gWithXs(row))
}
val b3 = if (down.length == 1) b2 else (up :+ down.head) ++ loop(down.tail, Array())
(b3, ayx1)
case '^' =>
@tailrec
def loop(restOfColumns: Array[String], acc: Array[String]): Array[String] = {
lazy val row = restOfColumns.last
lazy val c = row(x)
if (terminal(restOfColumns, c)) restOfColumns ++ acc
else loop(restOfColumns.init, gWithXs(row) +: acc)
}
val b3 = if (up.isEmpty) b2 else loop(up, Array()) ++ down
(b3, ayx1)
case 'A' =>
(b2, Some((y, x)))
case _ =>
(b2, ayx1)
}
}
}
// get to the bottom-right
def loop(y: Int, x: Int, traversed: Set[(Int, Int)]): Boolean = {
def go(dir: (Int, Int) => (Int, Int)) = {
val peek = dir(y, x)
lazy val (y1, x1) = peek
if (traversed(peek)) false else loop(y1, x1, traversed + peek)
}
if (y == m - 1 && x == n - 1)
true
else if (y >= 0 && x >= 0 && y < m && x < n) {
val e = bWithXs(y)(x)
if (e == `.` || e == 'A') {
if (go(Up)) true
else if (go(Down)) true
else if (go(Left)) true
else go(Right)
} else false
} else false
}
val (ay, ax) = assassinYx.get
loop(ay, ax, Set())
}
private def terminal(empty: String, elem: => Char): Boolean = terminal(empty.isEmpty, elem)
private def terminal(empty: Array[String], elem: => Char): Boolean = terminal(empty.isEmpty, elem)
private def terminal(cond0: Boolean, elem: => Char) = cond0 || elem != `.`
}
import org.scalatest.flatspec.AnyFlatSpec
class AssassinSpec extends AnyFlatSpec {
"w/o guardians" should "work" in {
val board = Array("AX..", "....", ".X..")
assert(Assassin.undetected(board))
}
"w/ right-looking guardians" should "work" in {
val board = Array("AX..", "..>.", ".X..")
assert(!Assassin.undetected(board))
}
"w/ down-looking guardians" should "work" in {
val board = Array("AXv.", "....", ".X..")
assert(!Assassin.undetected(board))
}
"w/ up-looking guardians" should "work" in {
val board = Array("AX..", "....", ".^..")
assert(!Assassin.undetected(board))
}
"it" should "avoid going around in circles" in {
val board = Array("AX..", "..^.", "....")
assert(Assassin.undetected(board))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment