# Insalgo Winter contest

## 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 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>) {

val prices = mutableMapOf<String, Int>()
// For n dishes

// 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
// 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

// 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 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)

}