The Tree Of Life
The Tree Of Life
+ 0 comments incase anyone was looking for solution :
import java.util.Scanner import scala.annotation.tailrec trait Tree { def value: Boolean def applyRule(rule: Int, parentValue: Boolean = false): Tree @tailrec final def changeState(rule: Int, stepCount: Int): Tree = if (stepCount == 0) this else applyRule(rule).changeState(rule, stepCount - 1) def atPath(path: List[Char]): Boolean protected def nextValue(rule: Int, parentValue: Boolean, leftValue: Boolean, rightValue: Boolean): Boolean = { def toBit(value: Boolean, index: Int) = (if (value) 1 else 0) << index val bit = toBit(parentValue, 3) | toBit(leftValue, 2) | toBit(value, 1) | toBit(rightValue, 0) (rule & (1 << bit)) != 0 } } object Tree { def parse(s: List[Char]): Tree = { def inner(s: List[Char]): (Tree, List[Char]) = s match { case Nil => (Empty, Nil) case c :: cs => c match { case '.' => (Leaf(false), cs) case 'X' => (Leaf(true), cs) case '(' => val (left, afterLeft) = inner(cs) val (root, afterRoot) = inner(afterLeft) val (right, afterRight) = inner(afterRoot) (Node(root.value, left, right), afterRight) case _ => inner(cs) } } inner(s)._1 } } case class Node(value: Boolean, left: Tree, right: Tree) extends Tree { override def applyRule(rule: Int, parentValue: Boolean): Tree = Node( nextValue(rule, parentValue, left.value, right.value), left.applyRule(rule, value), right.applyRule(rule, value) ) override def atPath(path: List[Char]): Boolean = path match { case ']' :: _ => value case c :: cs => (if (c == '<') left else right).atPath(cs) case Nil => throw new Exception("Wrong path") } } case class Leaf(value: Boolean) extends Tree { override def applyRule(rule: Int, parentValue: Boolean): Tree = Leaf( nextValue(rule, parentValue, leftValue = false, rightValue = false) ) override def atPath(path: List[Char]): Boolean = path match { case ']' :: _ => value case _ => throw new Exception("Wrong path") } } object Empty extends Tree { override def value: Boolean = throw new Exception("Value of empty tree") override def applyRule(rule: Int, parentValue: Boolean): Tree = this override def atPath(path: List[Char]): Boolean = throw new Exception("atPath of empty tree") } case class Rule(n: Int) object Solution { def main(args: Array[String]): Unit = { val sc = new Scanner(System.in) val rule = sc.nextInt sc.nextLine val s = sc.nextLine val root = Tree.parse(s.toList) val n = sc.nextInt case class Query(initialIndex: Int, time: Int, path: List[Char]) @scala.annotation.tailrec def readQueries(rest: Int, time: Int, acc: List[Query]): List[Query] = if (rest == 0) acc else { val stepCount = sc.nextInt val path = sc.nextLine.toList.drop(2) val nextTime = time + stepCount readQueries(rest - 1, nextTime, Query(n - rest, nextTime, path) :: acc) } val queries = readQueries(n, 0, Nil).sortBy(_.time) sc.close() case class Answer(initialIndex: Int, value: Boolean) case class Accumulator(tree: Tree, time: Int, answers: List[Answer]) val accumulator = queries.foldLeft(Accumulator(root, 0, Nil))((acc, query) => { val tree = acc.tree.changeState(rule, query.time - acc.time) Accumulator(tree, query.time, Answer(query.initialIndex, tree.atPath(query.path)) :: acc.answers) }) println(accumulator.answers.sortBy(_.initialIndex).map(v => if (v.value) 'X' else '.').mkString("\n")) } }
+ 1 comment I'm passing all but two tests, and failing because of a time limit. My process is that I convert the string into a tree data structure, then I call a function that keeps the tree data structure but each node also has info about it's parent and children values. Then I map the rules onto the nodes (with parent and child info) onto the tree to get the new nodes. My traversal is straight forward. Is this the most efficient outline? I must have efficiency losses somewhere
+ 1 comment A query has the form
number path
Is the
path
taken from the root, or from the point you just left off?Is the number the
n
th evolution from the start, or then
th evolution from the last time?
+ 1 comment Hi, I don't understand what exactly the input of each step (e.g. query) mean. After initialization input, we get a query of this form: 2 [><] What I understand is that we should start at the root traverse the tree denoted by the path while applaying the rule to the final destination of the path. We output the state of the neighbour denoted by the first number (2 in the example). Am I right? Should the rule be applied to all nodes the path goes through or just the destination? should we start at each step from the root of the tree or should we continue from the position we ended up in previous query?
+ 2 comments It feels as if the specification is not complete. What a conformant program should print if path description is describing a path that doesn't exist? For example, if I have a tree (X . X), and a path description [>>>>><], what should be the correct output in this case?
Sort 11 Discussions, By:
Please Login in order to post a comment