We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Functional Programming
  3. Recursion
  4. The Tree Of Life
  5. Discussions

The Tree Of Life

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 11 Discussions, By:

recency

Please Login in order to post a comment

  • nagendraallam
    2 years ago+ 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"))
      }
    }
    
    -3|
    Permalink
  • aryzach
    3 years ago+ 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|
    Permalink
  • martijnhoekstra
    5 years ago+ 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 nth evolution from the start, or the nth evolution from the last time?

    0|
    Permalink
  • sharon_shmorak
    5 years ago+ 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?

    0|
    Permalink
  • nikkne
    6 years ago+ 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?

    1|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy