Intuitive language – HackerRank Solution

Leave a Comment / HackerRank, HackerRank Functional Programming / By

In this post, we will solve Intuitive language HackerRank Solution. This problem (Intuitive language) is a part of HackerRank Functional Programming series.

Task

Sometimes it is hard to read code written in the language you are not familiar with, not unless its written in Intuitive Language. Here’s the sample of a program.

A is 15.  
Sum is function of 2: 1, 1, 0.  
Inc is function of 1: 1, 1.  
I is 1.  
F1 is 1.  

do {10} assign I*F1 to F1 AND Inc[I] to I!  
what is I AND F1?  

what is Sum[1]?

Pretty straightforward, when compared with some popular languages, isn’t it? Lets break down the rules here.

Language allows:

* To declare function.
* Assign value to variable.
* Make a loop with fixed number of repetition.
* Ask about function's value.

How to declare a function?

Function is an expression of n parameters.
Function1 is function of n: k1, k2, ..., kn, k0.
represents a function called Function1, when called with n parameters it will yield following value

k1*%1 + k2*%2 + ... + kn*%n + k0
where %i is the ith parameter, and k0, k1, ..., kn are the coefficients.
Formally, a function with n parameters is defined as
%Variable% is function of %N%: %Expression1%, %Expression2%, ..., %ExpressionN%, %Expression0%.

where k0 = Expression0, k1 = Expression1, ..., kn = Expressionn.
Simpler, optional, way to declare a function with no  parameter is:

%Variable% is %Expression%.

Note:
1. Declaration ends with a dot, (‘.‘) .
2. You can declare a function, with one or more parameters, only one time.
3. It’s guaranteed that function declaration will not any contain function calls, i.e., there will be no coefficient ki which contains a function call.
4. A function with 0 parameter will be considered as a variable. It can be reassigned multiple times.

Examples
1.That means A = 3*%1 - 15*%2 + 1.

A is function of 2: 3, -15, 1.

2. That means B = 14.

B is function of 0: 14.

3. That means C = 7.

C is 7.

How to assign value to variable?

Assign %Expression1% to %Variable1% [ AND %Expression2% to %Variable2% ... ]!

This means that the value of Variablei will be Expressioni.

Note:
1. Multiple assignments go left-to-right.
2. Assignment ends with an exclamation sign, ‘!‘.
3. You can assign values to a variable multiple times.

Examples

1. V will be equal to 11.

assign (3+4*2) to V!

2. This expression assigns 3 to P, 9 to Q and -6 to R.

assign 3 to P AND (4+5) to Q AND (Q-15) to R!

How to make a loop?

do {Expression} %Assign values(s) to variable(s)%!

Assignment inside the loop will be repeated number of times, indicated in {}. This number is guaranteed to be positive integer.

Examples

I is 1.
F is 1.
do {3} assign I*F to F AND I+1 to I!

Initially it will be I = F = 1. It will loop 3 times. At first loop, F = 1, I = 2, after second loop F = 2, I = 3 and after third/final loop it will be F = 6, I = 4.

How to ask about variables and function’s value?

what is %Function1 call% [AND %Variable1% [ AND %Function2 call% ... ] ]?

  • A function’s value or variable’s value can be asked anywhere, once it has been initialised.
  • Function call: %Name%[Expression1][Expression2]...[ExpressionM].
    • Expressioni will be the ith parameter, %i, in function declaration.
  • Results
    • If all n parameters are provided: the result of function call will be a value.
    • Otherwise: it will result into another function which takes remaining parameters. You have print coefficients, comma and space separated, as output in a line.
  • Question ends with ‘?‘.

Examples

A is 15/4.  
Sum is function of 2: 3, 2, 4. 

what is Sum[10] AND A?
what is Sum[20][10]?

will print the following output

2, 34
15/4
84

Let’s represent Sum function as

Let’s represent Sum function as
(a, b) -> 3 * a + 2 * b + 4
So, Sum[10] (a = 10) will result into another function
(b) -> 3 * 10 + 2 * b + 4
(b) -> 2 * b + 34
So new coefficients will be 2, 34.
Calling Sum[20][10] will result into 3*20 + 2*10 + 4 = 84

Notes:

  1. All numbers are rational integers, represented like a / b (or just a if b=1). Here b is a positive integer, a is any integer. Greatest common divisor for a and b should be 1.
    • Number: n where n is any integer number.
    • PNumber: n where n > 0.
    • Value: Number | Number / PNumber | FValue.
    • FValue: Calling function of n with all n parameters.
    • OPa: + | -.
    • OPb: * | /.
    • Expression: Term [OPa Term1 …].
    • Term: Fact [OPb Fact1 …].
    • Fact: Value | (Expression)
    • Letter: ‘A’..’Z’ | ‘a’..’z’.
    • OPb > OPa
  2. Variable consists of 1 or more letters followed by 0 or more digits; Key words (is, of, assign, what, function, do, and, to) are not allowed as variable names.
  3. Language is case insensitive. Variable name, function name and keywords are all case insensitive.
  4. The coefficients of functions are guaranteed to be expressions without variables.
  5. It is guaranteed that function call will occur only after it’s definition.
  6. Whitespace between tokens should be ignored.
  7. Operators
    • Operator precedence: * = / > + = -
    • Associativity: All operators follows left associativity

Constraints

  • It’s guaranteed that function declaration will not contain function calls.
  • All given numbers will be between -100 and 100.
  • Resulting numerator / denominator will not exceed 109 by absolute value.
  • Functions will have no more than 5 parameters.
  • Function name will contain no more than 20 characters.
  • Each loop will have no more than 1000 iterations.

Input

You are given compilable working program written in IL. You have to read it to the end of file.
It will contain no more than 100 lines.
Each line will contain no more than 200 characters and will represent one statement.

Output Format

For each function call/variable in what is question output it’s value, each per line.
If function is provided with all parameters that it was declared with – the result will be value, otherwise – function with remaining parameters.

Output Value Format
Print a / b (without spaces) if b > 1 or just a if b = 1.

Output Function Format
Resulting function of n parameters should be printed in the following format:
k1, k2, … , kn, k0
where ki is the coefficient.

Sample Input #00

A is 15.  
Sum is function of 2: 1, 1, 0.  
Inc is function of 1: 1, 1.  
I is 1.  
F1 is 1.  

do {10} assign I*F1 to F1 AND Inc[I] to I!  
what is I AND F1?  

what is Sum[1]?

Sample Output #00

11  
3628800  
1, 1

Sample Input #01

A is 2/6.  
b Is function of 2: -3, 7/4, 6/1.  
I is 1.  

what is b[0] and A and b[-1/3]?  
do {b[-1][4]-A*30} assign I+1 to I and I-1 to I and I+1 to I!  

what is I?

Sample Output #01

7/4, 6  
1/3  
7/4, 7  
7

Explanation

Test case #00: Inside the loop we calculate 10!, so I will be 11 and 10! is 3628800. Sum function is x+y, so Sum[1] is y+1.
Test case #01:

A = 1/3  
b = -3*x+7/4*y+6.  
b[0] = 7/4*y+6.  
b[-1/3] = -3*(-1/3)+7/4*y+6 = 7/4*y+7  
b[-1][4] = -3*(-1)+(7/4)*4+6 = 16.  
b[-1][4]-A*30 = 16-10 = 6

We repeat 6 times increasing of I, so I will be 7.

Solution – Intuitive Language – HackerRank Solution

Scala

import scala.collection.mutable

case class RationalNumber(nominator: Long, denominator: Long) {
  def +(that: RationalNumber): RationalNumber = RationalNumber(this.nominator * that.denominator + this.denominator * that.nominator, this.denominator * that.denominator).normalize

  def -(that: RationalNumber): RationalNumber = RationalNumber(this.nominator * that.denominator - this.denominator * that.nominator, this.denominator * that.denominator).normalize

  def *(that: RationalNumber): RationalNumber = RationalNumber(this.nominator * that.nominator, this.denominator * that.denominator).normalize

  def /(that: RationalNumber): RationalNumber = RationalNumber(this.nominator * that.denominator, this.denominator * that.nominator).normalize

  def normalize: RationalNumber = {
    val div = gcd(math.abs(nominator), math.abs(denominator))
    val sign = if ((nominator > 0) == (denominator > 0)) 1 else -1
    RationalNumber(math.abs(nominator) / div * sign, math.abs(denominator) / div)
  }

  override def toString: String = if (denominator == 1) nominator.toString else s"$nominator/$denominator"

  @scala.annotation.tailrec
  private def gcd(a: Long, b: Long): Long = if (b == 0) a else gcd(b, a % b)
}

case class Ram(data: mutable.Map[String, RationalNumber], functions: Map[String, Syntax.FunctionDeclaration])

object Ram {
  val empty: Ram = new Ram(mutable.Map(), Map())
}

object Lex {

  trait Lexeme

  trait Operation extends Lexeme

  trait PotentialUnary extends Operation

  case class Variable(name: String) extends Lexeme

  case class Number(value: Long) extends Lexeme

  case object Function extends Lexeme

  case object Is extends Lexeme

  case object Of extends Lexeme

  case object Do extends Lexeme

  case object Assign extends Lexeme

  case object To extends Lexeme

  case object And extends Lexeme

  case object Exclamation extends Lexeme

  case object Question extends Lexeme

  case object What extends Lexeme

  case object Colon extends Lexeme

  case object Comma extends Lexeme

  case object Point extends Lexeme

  case object OpenCurlyBracket extends Lexeme

  case object CloseCurlyBracket extends Lexeme

  case object OpenRoundBracket extends Lexeme

  case object CloseRoundBracket extends Lexeme

  case object OpenSquareBracket extends Lexeme

  case object CloseSquareBracket extends Lexeme

  case object Addition extends PotentialUnary

  case object Subtraction extends PotentialUnary

  case object Multiplication extends Operation

  case object Division extends Operation

  case object Unary

}

object Syntax {

  trait Executable {
    def execute(ram: Ram): Unit
  }

  trait Operation {
    def eval(a: RationalNumber, b: RationalNumber): RationalNumber
  }

  trait Expression {
    def eval(ram: Ram): RationalNumber
  }

  case class VariableDeclaration(name: String, expression: Expression) extends Executable {
    override def execute(ram: Ram): Unit = ram.data(name) = expression.eval(ram)
  }

  case class FunctionDeclaration(name: String, parameters: List[RationalNumber]) extends Executable {
    override def execute(ram: Ram): Unit = {}
  }

  case class Pair(variable: Variable, expression: Expression)

  case class Assignment(pairs: List[Pair]) extends Executable {
    override def execute(ram: Ram): Unit = pairs.foreach(pair => ram.data(pair.variable.name) = pair.expression.eval(ram))
  }

  case class Do(expression: Expression, assignment: Assignment) extends Executable {
    override def execute(ram: Ram): Unit = {
      val count = expression.eval(ram).nominator.toInt
      (0 until count).foreach(_ => assignment.execute(ram))
    }
  }

  case class What(expressions: List[Expression]) extends Executable {
    override def execute(ram: Ram): Unit = println(expressions.map {
      case f: FunctionCall => f.partialCall(ram)
      case ex => ex.eval(ram)
    }.mkString("\n"))
  }

  case class Wrapper(expression: Expression) extends Lex.Lexeme

  case class Variable(name: String) extends Expression {
    override def eval(ram: Ram): RationalNumber = ram.data(name)
  }

  case class Number(value: Long) extends Expression {
    override def eval(ram: Ram): RationalNumber = RationalNumber(value, 1)
  }

  case class SquareBracket(parameters: List[Expression]) extends Expression {
    override def eval(ram: Ram): RationalNumber = throw new Exception("Not supported")
  }

  case class FunctionCall(name: String, parameters: List[Expression]) extends Expression {
    def partialCall(ram: Ram): String = {
      val coefficients = ram.functions(name).parameters
      val (suppliedCoefficients, restCoefficients) = coefficients.splitAt(parameters.length)
      val value = (if (parameters.isEmpty) RationalNumber(0, 1) else suppliedCoefficients.zip(parameters)
        .map { case (c, p) => c * p.eval(ram) }
        .reduce(_ + _)) + coefficients.last

      s"${restCoefficients.init.mkString(", ")}${if (parameters.length == coefficients.length - 1) "" else ", "}$value"
    }

    override def eval(ram: Ram): RationalNumber = {
      val coefficients = ram.functions(name).parameters
      coefficients.zip(parameters)
        .map { case (c, p) => c * p.eval(ram) }
        .reduce(_ + _) + coefficients.last
    }
  }

  case class Addition(a: Expression, b: Expression) extends Expression {
    override def eval(ram: Ram): RationalNumber = a.eval(ram) + b.eval(ram)
  }

  case class Subtraction(a: Expression, b: Expression) extends Expression {
    override def eval(ram: Ram): RationalNumber = a.eval(ram) - b.eval(ram)
  }

  case class Multiplication(a: Expression, b: Expression) extends Expression {
    override def eval(ram: Ram): RationalNumber = a.eval(ram) * b.eval(ram)
  }

  case class Division(a: Expression, b: Expression) extends Expression {
    override def eval(ram: Ram): RationalNumber = a.eval(ram) / b.eval(ram)
  }

  case class UnaryAddition(a: Expression) extends Expression {
    override def eval(ram: Ram): RationalNumber = a.eval(ram)
  }

  case class UnarySubtraction(a: Expression) extends Expression {
    override def eval(ram: Ram): RationalNumber = {
      val number = a.eval(ram)
      RationalNumber(-number.nominator, number.denominator)
    }
  }

}

object Expression {

  import Syntax._

  def findCloseBracket(lexemes: List[Lex.Lexeme], openBracket: Lex.Lexeme, closeBracket: Lex.Lexeme): (List[Lex.Lexeme], List[Lex.Lexeme]) = {
    case class Acc(lexemes: List[Lex.Lexeme] = Nil, bracketCount: Int = 1)
    @scala.annotation.tailrec
    def inner(lexemes: List[Lex.Lexeme], acc: Acc = Acc()): (List[Lex.Lexeme], List[Lex.Lexeme]) = {
      lexemes match {
        case (lex@`closeBracket`) :: lexemes =>
          if (acc.bracketCount == 1) (acc.lexemes.reverse, lexemes)
          else inner(lexemes, Acc(lex :: acc.lexemes, acc.bracketCount - 1))
        case (lex@`openBracket`) :: lexemes => inner(lexemes, Acc(lex :: acc.lexemes, acc.bracketCount + 1))
        case lex :: lexemes => inner(lexemes, Acc(lex :: acc.lexemes, acc.bracketCount))
        case Nil => throw new Exception("Wrong exception")
      }
    }

    inner(lexemes)
  }

  def apply(lexemes: List[Lex.Lexeme]): Expression = {
    val operationGroups = Seq(Seq(), Seq(Lex.Unary),
      Seq(Lex.Multiplication, Lex.Division), Seq(Lex.Addition, Lex.Subtraction))

    def headAsExpression(list: List[Lex.Lexeme]): Expression = list match {
      case Wrapper(expression) :: Nil => expression
      case _ => throw new Exception("Incorrect expression")
    }

    def inner(lexemes: List[Lex.Lexeme], startOfList: Boolean = false): List[Lex.Lexeme] = {
      val res = operationGroups.foldLeft(lexemes)((acc, ops) => {
        def simplify(lexemes: List[Lex.Lexeme], startOfList: Boolean = false): List[Lex.Lexeme] = lexemes match {
          case Nil => Nil

          case Lex.OpenRoundBracket :: rest =>
            val (roundBracket, nextRest) = findCloseBracket(rest, Lex.OpenRoundBracket, Lex.CloseRoundBracket)
            simplify(Wrapper(Expression(roundBracket)) :: nextRest)

          case Lex.Variable(name) :: Lex.OpenSquareBracket :: rest =>
            val (squareBracket, nextRest) = findCloseBracket(rest, Lex.OpenSquareBracket, Lex.CloseSquareBracket)
            val parameters = inner(squareBracket, startOfList = true).collect { case Wrapper(ex) => ex }
            simplify(Wrapper(FunctionCall(name, parameters)) :: nextRest)

          case Wrapper(FunctionCall(name, firstParameters)) :: Lex.OpenSquareBracket :: rest =>
            val (squareBracket, nextRest) = findCloseBracket(rest, Lex.OpenSquareBracket, Lex.CloseSquareBracket)
            val parameters = inner(squareBracket, startOfList = true).collect { case Wrapper(ex) => ex }
            simplify(Wrapper(FunctionCall(name, firstParameters ++ parameters)) :: nextRest)

          case Lex.Variable(name) :: exs => simplify(Wrapper(Syntax.Variable(name)) :: exs)

          case Lex.Number(a) :: exs => simplify(Wrapper(Number(a)) :: exs)

          case Wrapper(a) :: (op: Lex.Operation) :: Wrapper(b) :: exs if ops.contains(op) =>
            simplify(Wrapper(
              op match {
                case Lex.Addition => Addition(a, b)
                case Lex.Subtraction => Subtraction(a, b)
                case Lex.Multiplication => Multiplication(a, b)
                case Lex.Division => Division(a, b)
              }
            ) :: exs)

          case (lex: Lex.Lexeme) :: (op: Lex.PotentialUnary) :: Wrapper(a) :: exs if !lex.isInstanceOf[Wrapper] && ops.contains(Lex.Unary) =>
            simplify(lex :: Wrapper(
              op match {
                case Lex.Addition => UnaryAddition(a)
                case Lex.Subtraction => UnarySubtraction(a)
              }
            ) :: exs)

          case (op: Lex.PotentialUnary) :: Wrapper(a) :: exs if startOfList && ops.contains(Lex.Unary) =>
            simplify(Wrapper(
              op match {
                case Lex.Addition => UnaryAddition(a)
                case Lex.Subtraction => UnarySubtraction(a)
              }
            ) :: exs)

          case ex :: exs =>
            ex :: simplify(exs)
        }

        simplify(acc, startOfList)
      })

      res
    }

    headAsExpression(inner(lexemes, startOfList = true))
  }
}

object Parser {

  import Syntax._

  def toLexemes(s: String): List[Lex.Lexeme] = {
    val lexemeNames = Map(
      "is" -> Lex.Is,
      "function" -> Lex.Function,
      "of" -> Lex.Of,
      ":" -> Lex.Colon,
      "," -> Lex.Comma,
      "." -> Lex.Point,
      "do" -> Lex.Do,
      "{" -> Lex.OpenCurlyBracket,
      "}" -> Lex.CloseCurlyBracket,
      "(" -> Lex.OpenRoundBracket,
      ")" -> Lex.CloseRoundBracket,
      "[" -> Lex.OpenSquareBracket,
      "]" -> Lex.CloseSquareBracket,
      "assign" -> Lex.Assign,
      "to" -> Lex.To,
      "and" -> Lex.And,
      "!" -> Lex.Exclamation,
      "?" -> Lex.Question,
      "+" -> Lex.Addition,
      "-" -> Lex.Subtraction,
      "*" -> Lex.Multiplication,
      "/" -> Lex.Division,
      "what" -> Lex.What
    )

    def parseLexeme(index: Int, predicate: Char => Boolean): (Int, String) = {
      @scala.annotation.tailrec
      def inner(index: Int, sb: StringBuilder = new StringBuilder): (Int, String) = if (index < s.length) {
        val c = s(index)
        if (predicate(c)) inner(index + 1, sb.append(c)) else (index, sb.toString())
      } else (index, sb.toString())

      inner(index)
    }

    case class State(index: Int = 0, acc: List[Lex.Lexeme] = Nil)

    @scala.annotation.tailrec
    def inner(state: State): State = if (state.index < s.length) {
      val c = s(state.index)

      val nextState = c match {
        case d: Char if d.isLetter =>
          val (nextIndex, lexemeName) = parseLexeme(state.index, _.isLetterOrDigit)
          val lexeme = lexemeNames.getOrElse(lexemeName, Lex.Variable(lexemeName))
          State(nextIndex, lexeme :: state.acc)

        case d: Char if d.isDigit =>
          val (nextIndex, lexemeName) = parseLexeme(state.index, _.isDigit)
          val lexeme = lexemeNames.getOrElse(lexemeName, Lex.Number(lexemeName.toLong))
          State(nextIndex, lexeme :: state.acc)

        case d: Char if lexemeNames.contains(d.toString) =>
          val lexeme = lexemeNames(d.toString)
          State(index = state.index + 1, lexeme :: state.acc)

        case _ => state.copy(index = state.index + 1)
      }

      inner(nextState)
    } else state

    inner(State()).acc.reverse
  }

  implicit class Splitter(lexemes: List[Lex.Lexeme]) {
    def splitBy(separators: Set[Lex.Lexeme], drop: Set[Lex.Lexeme] = Set()): List[List[Lex.Lexeme]] = {
      case class Acc(current: List[Lex.Lexeme] = Nil, data: List[List[Lex.Lexeme]] = Nil)
      val acc = lexemes.foldLeft(Acc())((acc, lex) => {
        val nextCurrent = if (drop.contains(lex)) acc.current else lex :: acc.current
        if (separators.contains(lex)) Acc(Nil, nextCurrent.reverse :: acc.data)
        else Acc(nextCurrent, acc.data)
      })

      (if (acc.current.isEmpty) acc.data else acc.current.reverse :: acc.data).reverse
    }
  }

  def toExecutable(lexemes: List[Lex.Lexeme]): Executable = {
    lexemes match {
      case Lex.Variable(name) :: Lex.Is :: Lex.Function :: Lex.Of :: lexemes => //Function declaration
        val (paramCountLexemes, paramsLexemes) = lexemes.span(_ != Lex.Colon)
        val paramCount = Expression(paramCountLexemes).eval(Ram.empty).nominator
        val params = paramsLexemes.tail.splitBy(Set(Lex.Comma), Set(Lex.Comma, Lex.Point))

        if (paramCount == 0) {
          VariableDeclaration(name, Expression(params.head))
        } else {
          FunctionDeclaration(name, params.map(Expression(_).eval(Ram.empty)))
        }

      case Lex.Variable(name) :: Lex.Is :: lexemes => //Variable declaration
        val expression = Expression(lexemes.init)
        VariableDeclaration(name, expression)

      case Lex.Assign :: lexemes => //Assignment
        val params = lexemes.splitBy(Set(Lex.And), Set(Lex.And, Lex.Exclamation))
        val pairs = params.map(lexemes => {
          val (forExpression, forVariable) = lexemes.splitAt(lexemes.length - 2)
          Pair(Variable(forVariable.last.asInstanceOf[Lex.Variable].name), Expression(forExpression))
        })
        Assignment(pairs)

      case Lex.Do :: Lex.OpenCurlyBracket :: lexemes => //Loop
        val (expressionLexemes, rest) = lexemes.span(_ != Lex.CloseCurlyBracket)
        val assignmentLexemes = rest.tail
        Do(Expression(expressionLexemes), toExecutable(assignmentLexemes).asInstanceOf[Assignment])

      case Lex.What :: Lex.Is :: lexemes => //Query
        val params = lexemes.splitBy(Set(Lex.And), Set(Lex.And, Lex.Question))
        val expressions = params.map(Expression(_))

        What(expressions)

      case _ => throw new Exception("Wrong program")
    }
  }
}

object Solution {

  import Parser._
  import Syntax._

  def main(args: Array[String]): Unit = {
    val code = io.Source.stdin.getLines().map(_.toLowerCase).mkString("\n")
    solve(code)
  }

  def solve(s: String): Unit = {
    val lexemes = Parser.toLexemes(s)
    val groupedLexemes = lexemes.splitBy(Set(Lex.Point, Lex.Exclamation, Lex.Question))
    val executables = groupedLexemes.map(toExecutable)
    val ram = Ram(mutable.Map(), executables.collect { case f: FunctionDeclaration => f.name -> f }.toMap)
    val fixedExecutables = executables
      .map {
        case What(list) => What(list.map {
          case Variable(name) if ram.functions.contains(name) => FunctionCall(name, Nil)
          case v => v
        })
        case v => v
      }

    fixedExecutables.foreach(_.execute(ram))
  }
}

Note: This problem (Intuitive Language) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.

Leave a Comment

Your email address will not be published. Required fields are marked *