Loïc Rouquette

An IT Engineer student

Discover me Discover my work

Insalgo Winter Contest

by Loïc Rouquette
Friday, February 16, 2018

Insalgo Winter contest

Insalgo is a student association about algorithmic. They made a winter contest this week. In this article I will speak about the exercices and the possible solutions.

Problem 1 - Duty free price

Subject

This probleme is a simple mathematical problem, we need to calculate a duty free price from a tax rate and the vat price.

We have :

$$ dutyFreePrice + (dutyFreePrice * taxRate) = VATPrice $$

$$ dutyFreePrice * (1 + taxRate) = VATPrice $$

$$ dutyFreePrice = \frac{VATPrice}{1 + taxRate} $$

Inputs:

0.45  # VAT Price
7     # Tax rate (in percent)

Ouput:

0.42  # Duty free price

Algorithm:

fun main(args: Array<String>) {

  val vatPrice = readLine()!!.toDouble()
  val taxRate = readLine()!!.toDouble() / 100.0 // Convert percent to taxRate

  println(String.format("%.2f", vatPrice / (1.0 + taxRate)))
}

Problem 2 - Restaurant note

Subject

The purpose of the exercice is to calculate the note of the restaurant.

Inputs:

5             # Number of different dishes in the menu
marguerite 5  # Dish and price
royale 6
bolognaise 8
forestiere 8
fromage 8
2             # Number of different ordered dishes
royale 1      # Ordered dish and quantity
fromage 2

Output:

22            # The amount of the bill

Algorithm:

fun main(args: Array<String>) {

  // We create the menu
  val prices = mutableMapOf<String, Int>()
  // For n dishes
  (0 until readLine()!!.toInt()).forEach {

    // We split the input as "dish" "price"
    val (dish, priceStr) = readLine()!!.split(" ")
    // We record the price for the dish
    prices[dish] = priceStr.toInt()
  }

  var bill = 0
  // For n dishes
  (0 until readLine()!!.toInt()).forEach {
    // We got "dish" "quantity"
    val (dish, qtyStr) = readLine()!!.split(" ")
    // We add the price of the dish * his quantity to the bill
    bill += prices[dish]!! * qtyStr.toInt()
  }

  println(bill)

}

Problem 3 - ToqueToc, palindrome

Subject

The purpose of the exercice is to try to make a palindrome from an input word where the first parts is sorted (ascending) and the second part is also sorted but descending. If a letter (it can be only one) has an odd number of appearances, it will placed on the middle of the keyword

Inputs:

4       # Number of inputs
acbbacb
insalgo
kayak
baba

Output:

abcbcba
-         # This is not a palindrome
akyka
abba

Algorithm:

fun main(args: Array<String>) {

  // For n lines
  (0 until readLine()!!.toInt()).forEach {

    // We got the line and map it to a List<Char>
    var input = readLine()!!.map { it }

    /*
      We count how many time a letter appears
      acbbacb => [(a, 2), (c, 2), (b, 3)]
     */
    val countLetter = input
        .groupBy { it }
        .map {
          Pair(it.key, it.value.size)
        }

    // Here we got (if it exists) the letter with the odd number of appearance
    val impairLetter = countLetter.firstOrNull { it.second % 2 == 1 }?.first

    // If impairLetter exist we remove it from the rest of the letters
    if(impairLetter != null) {
      input -= impairLetter
    }

    // We sort the list to put the same letters aside
    val sorted = input.sorted()

    // We took one letter in two for the
    val begin = sorted.filterIndexed { index, _ -> index % 2 == 0 }.joinToString("")
    // The rest will go to the end
    val end = sorted.filterIndexed { index, _ -> index % 2 != 0 }.sortedDescending().joinToString("")

    // If we got an impairLetter we put it in the middle of the word
    val result = if(impairLetter != null) {
      begin + impairLetter.toString() + end
    } else {
      // Else we only put the two parts of the word
      begin + end
    }

    // We check is the word is a palindrome or not
    if(isPalindrom(result)) {
      println(result)
    } else {
      println("-")
    }

  }

}

fun isPalindrom(string: String): Boolean {
  var a = 0
  var b = string.length - 1
  while(a < b && string[a] == string[b]) {
    a++
    b--
  }
  return a >= b
}

Problem 4

Subject

Here we have to calculate the longest path in a matrix of Chars.

Inputs:

5
^^^^^
<v<>>
<v^>>
<>^>>
vvvvv

Outputs:

6

Algorithm:

import java.util.*

typealias Coordinates = Pair<Int, Int>

fun main(args: Array<String>) {

  // We define the matrix size
  val size = readLine()!!.toInt()
  val matrix = Array(size, { _ -> CharArray(size, { _ -> ' ' }) })

  // Mémoization of the paths length
  val pathLength = Array(size, { _ -> IntArray(size, { _ -> -1 }) })
  fun computePathLength(i: Int, j: Int, seen: List<Coordinates>): Int {

    // If we don't know the size of the path, we compute it
    if (pathLength[i][j] == -1) {
      var x = i
      var y = j
      val alreadySeen = seen + Coordinates(i, j)
      // We compute the next coordinates to visit
      when (matrix[x][y]) {
        '^' -> x -= 1
        'V', 'v' -> x += 1
        '<' -> y -= 1
        else /* '>' */ -> y += 1
      }
      val newCoordinates = Coordinates(x, y)

      if (x < 0 || x >= size || y < 0 || y >= size || newCoordinates in alreadySeen) {
        // If we go out of the matrix or we have already visited the next point
        // We set the length to 1
        pathLength[i][j] = 1
      } else {
        // Else the lenth = the length of the next point + 1
        pathLength[i][j] = computePathLength(x, y, alreadySeen) + 1
      }
    }

    // We return the memoized length
    return pathLength[i][j]
  }

  // For each line of the matrix
  (0 until size).forEach { line ->

    // We read the line and transform the String to a List<Char>
    val directions = readLine()!!.map { it }
    // We filled up the corresponding matrix line
    directions.forEachIndexed { column, c ->
      matrix[line][column] = c
    }

  }

  var max = 0
  for(i in 0 until size) {
    for(j in 0 until size) {
      // We compute the length of the path at [i][j]
      val length = computePathLength(i, j, listOf(Coordinates(i, j)))
      // If the path is better we record the new path length
      if (length > max) {
        max = length
      }
    }
  }
  println(max)

}