Last active
August 29, 2015 14:06
-
-
Save sungkmi/0be1fdfdf843525436ec to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
object Magicka extends App { | |
class Solver(combines: Seq[Seq[Char]], opposeds: Seq[Seq[Char]]) { | |
private val comb: Map[(Char, Char), Char] = combines.flatMap { | |
case Seq(a, b, c) => Seq(((a, b), c), ((b, a), c)) | |
}.toMap | |
private val oppo = ((Map.empty[Char, Set[Char]] withDefaultValue Set.empty) /: opposeds.flatMap { | |
case Seq(a, b) => Seq((a, b), (b, a)) | |
}) { | |
case (map, (a, b)) => map updated (a, map(a) + b) | |
} | |
def solve(elements: Seq[Char]): Seq[Char] = { | |
@annotation.tailrec | |
def solve0(input: (List[Char], List[Char])): List[Char] = { | |
val (elements, acc) = input | |
if (elements.isEmpty) acc.reverse | |
else solve0 { | |
elements match { | |
case x :: xs if (oppo contains x) && (acc exists oppo(x).contains) => (xs, Nil) | |
case x :: y :: xs if comb contains (x, y) => (xs, comb((x, y)) :: acc) | |
case x :: xs => (xs, x :: acc) | |
} | |
} | |
} | |
solve0(elements.toList, Nil) | |
} | |
} | |
def process(lineIn: Iterator[String])(lineOut: String => Unit) = { | |
for (i <- 1 to lineIn.next().toInt) { | |
val c :: cs = (lineIn.next() split ' ').toList | |
val (combines, d :: ds) = cs splitAt c.toInt | |
val (opposeds, e :: elements :: Nil) = ds splitAt d.toInt | |
val solver = new Solver(combines.map(_.toSeq), opposeds.map(_.toSeq)) | |
lineOut(s"Case #$i: ${solver solve elements mkString ("[", ", ", "]")}") | |
} | |
} | |
val writer = new java.io.PrintWriter("b.large.out") | |
try { | |
process(io.Source.fromFile("B-large-practice.in").getLines)(writer.println) | |
} finally { | |
writer.flush(); writer.close() | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import org.scalatest._ | |
import Magicka._ | |
class MagickaTest extends FunSuite { | |
val solver = new Solver(Seq("QFT"), Seq("RF")) | |
test("example #1") { | |
assert(solver.solve("QF") === "T".toSeq) | |
} | |
test("example #2") { | |
assert(solver.solve("QEF") === "QEF".toSeq) | |
} | |
test("example #3") { | |
assert(solver.solve("RFE") === "E".toSeq) | |
} | |
test("example #4") { | |
assert(solver.solve("REF") === "".toSeq) | |
} | |
test("example #5") { | |
assert(solver.solve("RQF") === "RT".toSeq) | |
} | |
test("example #6") { | |
assert(solver.solve("RFQ") === "Q".toSeq) | |
} | |
test("sample case") { | |
val input = """5 | |
0 0 2 EA | |
1 QRI 0 4 RRQR | |
1 QFT 1 QF 7 FAQFDFQ | |
1 EEZ 1 QE 7 QEEEERA | |
0 1 QW 2 QW""".lines | |
val expected = """Case #1: [E, A] | |
Case #2: [R, I, R] | |
Case #3: [F, D, T] | |
Case #4: [Z, E, R, A] | |
Case #5: []""".lines | |
process(input) { s => | |
for (line <- s.lines) | |
assert(line === expected.next()) | |
} | |
} | |
test("some case") { | |
val input = """1 | |
2 QRI RTK 0 4 RRQRT""".lines | |
val expected = """Case #1: [R, I, K]""".lines | |
process(input) { s => | |
for (line <- s.lines) | |
assert(line === expected.next()) | |
} | |
} | |
test("full small case") { | |
val input = io.Source.fromFile("B-small-practice.in").getLines() | |
val expected = io.Source.fromFile("b.small.out.ref").getLines() | |
process(input) { s => | |
for (line <- s.lines) | |
assert(line.trim === expected.next().trim) | |
} | |
} | |
test("full large case") { | |
val input = io.Source.fromFile("B-large-practice.in").getLines() | |
val expected = io.Source.fromFile("b.large.out.ref").getLines() | |
process(input) { s => | |
for (line <- s.lines) | |
assert(line.trim === expected.next().trim) | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment