Coursera Kotlin

BoardImpl.kt

package board

import board.Direction.*

class SquareBoardImpl(private val size: Int, private val cells: List<Cell>) : SquareBoard {

    constructor(width: Int) : this(width, createCells(width))

    override val width: Int
        get() = size


    override fun getCellOrNull(i: Int, j: Int) = cells.firstOrNull { (ci, cj) -> ci == i && cj == j }

    override fun getCell(i: Int, j: Int) =
            getCellOrNull(i, j) ?: throw IllegalArgumentException("Invalid position")

    override fun getAllCells() = cells

    override fun getRow(i: Int, jRange: IntProgression) =
            jRange.takeWhile { it <= size }.map { j -> getCell(i, j) }

    override fun getColumn(iRange: IntProgression, j: Int) =
            iRange.takeWhile { it <= size }.map { i -> getCell(i, j) }

    override fun Cell.getNeighbour(direction: Direction): Cell? {
        return when (direction) {
            UP -> getCellOrNull(this.i - 1, this.j)
            DOWN -> getCellOrNull(this.i + 1, this.j)
            RIGHT -> getCellOrNull(this.i, this.j + 1)
            LEFT -> getCellOrNull(this.i, this.j - 1)
        }
    }

    companion object {
        private fun createCells(size: Int)
                = (1..size).flatMap { i -> (1..size).map { j -> Cell(i, j) } }
    }

}


class GameBoardImpl<T> private constructor(private val squareBoard: SquareBoard) : GameBoard<T>, SquareBoard by squareBoard {

    private val cells = mutableMapOf<Cell, T?>()

    constructor(width: Int) : this(createSquareBoard(width))

    override fun get(cell: Cell) = cells[cell]

    override fun set(cell: Cell, value: T?) {
        cells[cell] = value
    }

    override fun filter(predicate: (T?) -> Boolean) =
            squareBoard.getAllCells().filter { predicate.invoke(cells[it]) }

    override fun find(predicate: (T?) -> Boolean) =
            filter(predicate).firstOrNull()

    override fun any(predicate: (T?) -> Boolean) =
            squareBoard.getAllCells().any { predicate.invoke(get(it)) }

    override fun all(predicate: (T?) -> Boolean) =
            squareBoard.getAllCells().all { predicate.invoke(get(it)) }

}

fun createSquareBoard(width: Int): SquareBoard = SquareBoardImpl(width)
fun <T> createGameBoard(width: Int): GameBoard<T> = GameBoardImpl(width)

EvaluateGuess.kt

package mastermind

data class Evaluation(val rightPosition: Int, val wrongPosition: Int) {

    operator fun plus(evaluation: Evaluation): Evaluation {
        return Evaluation(evaluation.rightPosition + rightPosition, evaluation.wrongPosition + wrongPosition)
    }
}

fun evaluateGuess(secret: String, guess: String): Evaluation {

    val rightPositions = secret.zip(guess).count { (a, b) -> a == b }

    val commonLetters = "ABCDEF".sumBy { ch ->

        Math.min(secret.count { ch == it }, guess.count { ch == it })
    }
    return Evaluation(rightPositions, commonLetters - rightPositions)
}

Game2048.kt

package games.game2048

import board.Cell
import board.Direction
import board.Direction.*
import board.GameBoard
import board.createGameBoard
import games.game.Game

/*
 * Your task is to implement the game 2048 https://en.wikipedia.org/wiki/2048_(video_game).
 * Implement the utility methods below.
 *
 * After implementing it you can try to play the game running 'PlayGame2048'.
 */
fun newGame2048(initializer: Game2048Initializer<Int> = RandomGame2048Initializer): Game =
        Game2048(initializer)

class Game2048(private val initializer: Game2048Initializer<Int>) : Game {
    private val board = createGameBoard<Int?>(4)

    override fun initialize() {
        repeat(2) {
            board.addNewValue(initializer)
        }
    }

    override fun canMove() = board.any { it == null }

    override fun hasWon() = board.any { it == 2048 }

    override fun processMove(direction: Direction) {
        if (board.moveValues(direction)) {
            board.addNewValue(initializer)
        }
    }

    override fun get(i: Int, j: Int): Int? = board.run { get(getCell(i, j)) }
}

/*
 * Add a new value produced by 'initializer' to a specified cell in a board.
 */
fun GameBoard<Int?>.addNewValue(initializer: Game2048Initializer<Int>) {
    initializer.nextValue(this)?.let { (cell, value) -> this[cell] = value }
}

/*
 * Update the values stored in a board,
 * so that the values were "moved" in a specified rowOrColumn only.
 * Use the helper function 'moveAndMergeEqual' (in Game2048Helper.kt).
 * The values should be moved to the beginning of the row (or column),
 * in the same manner as in the function 'moveAndMergeEqual'.
 * Return 'true' if the values were moved and 'false' otherwise.
 */
fun GameBoard<Int?>.moveValuesInRowOrColumn(rowOrColumn: List<Cell>): Boolean {
    val previousValues = rowOrColumn.map { this[it] }
    val mergedValues = rowOrColumn.map { this[it] }.moveAndMergeEqual { v: Int -> v * 2 }
    val newValues = mergedValues + (1..(this.width - mergedValues.size)).map { null }
    rowOrColumn.zip(newValues).forEach { (cell, v) -> this[cell] = v }
    return previousValues != newValues
}

/*
 * Update the values stored in a board,
 * so that the values were "moved" to the specified direction
 * following the rules of the 2048 game .
 * Use the 'moveValuesInRowOrColumn' function above.
 * Return 'true' if the values were moved and 'false' otherwise.
 */
fun GameBoard<Int?>.moveValues(direction: Direction): Boolean {
    val cells = when (direction) {
        UP -> (1..this.width).map { j -> (1..this.width).map { i -> Cell(i,j) } }
        DOWN -> (1..this.width).map { j -> (1..this.width).reversed().map { i -> Cell(i,j) } }
        LEFT -> (1..this.width).map { i -> (1..this.width).map { j -> Cell(i,j) } }
        RIGHT -> (1..this.width).map { i -> (1..this.width).reversed().map { j -> Cell(i,j) } }
    }
    val moves = cells.map { this.moveValuesInRowOrColumn(it) }
    return moves.any { it }
}

Game2048Helper.kt

package games.game2048

/*
 * This function moves all the non-null elements to the beginning of the list
 * (by removing nulls) and merges equal elements.
 * The parameter 'merge' specifies the way how to merge equal elements:
 * it returns a new element that should be present in the resulting list
 * instead of two merged elements.
 *
 * If the function 'merge("a")' returns "aa",
 * then the function 'moveAndMergeEqual' transforms the input in the following way:
 *   a, a, b -> aa, b
 *   a, null -> a
 *   b, null, a, a -> b, aa
 *   a, a, null, a -> aa, a
 *   a, null, a, a -> aa, a
 *
 * You can find more examples in 'TestGame2048Helper'.
*/
fun <T : Any> List<T?>.moveAndMergeEqual(merge: (T) -> T): List<T> {
    return recursiveMerging(this.filterNotNull(), merge)
}

fun <T> recursiveMerging(list : List<T>, merge: (T) -> T): List<T>  {
    if (list.size < 2) return list

    val first = list[0]
    val second = list[1]
    return if (first == second) {
        listOf(merge.invoke(first)) +  recursiveMerging(list.drop(2), merge)
    } else {
        listOf(first) +  recursiveMerging(list.drop(1), merge)
    }
}

Game2048Initializer.kt

package games.game2048

import board.Cell
import board.GameBoard
import kotlin.random.Random

interface Game2048Initializer<T> {
    /*
     * Specifies the cell and the value that should be added to this cell.
     */
    fun nextValue(board: GameBoard<T?>): Pair<Cell, T>?
}

object RandomGame2048Initializer: Game2048Initializer<Int> {
    private fun generateRandomStartValue(): Int =
            if (Random.nextInt(10) == 9) 4 else 2

    /*
     * Generate a random value and a random cell among free cells
     * that given value should be added to.
     * The value should be 2 for 90% cases, and 4 for the rest of the cases.
     * Use the 'generateRandomStartValue' function above.
     * If the board is full return null.
     */
    override fun nextValue(board: GameBoard<Int?>): Pair<Cell, Int>? {
        if (board.isFull()) return null
        val emptyCell  = board.emptyCells().shuffled().first()
        val startValue = generateRandomStartValue()
        return Pair(emptyCell, startValue)
    }
}

GameOfFifteen.kt

package games.gameOfFifteen

import board.Cell
import board.Direction
import board.GameBoard
import board.createGameBoard
import games.game.Game

/*
 * Implement the Game of Fifteen (https://en.wikipedia.org/wiki/15_puzzle).
 * When you finish, you can play the game by executing 'PlayGameOfFifteen'.
 */

class GameOfFifteen(
        private val initializer: GameOfFifteenInitializer = RandomGameInitializer(),
        private val board: GameBoard<Int?> = createGameBoard(4)) : Game, GameBoard<Int?> by board {

    override fun initialize() {
        getAllCells().zip(initializer.initialPermutation).forEach { (k, v) -> this[k] = v }
    }

    override fun canMove() = !hasWon()

    override fun hasWon() =
            (1..15).zip(getAllCells().map { this[it] }).all { (a, b) -> a == b }

    override fun processMove(direction: Direction) {
        emptyCells().first().let { emptyCell ->
            emptyCell.getNeighbour(direction.reversed())?.let { cellToMove ->
                this[emptyCell] = this[cellToMove]
                this[cellToMove] = null
            }
        }
    }

    override fun get(i: Int, j: Int) = this[Cell(i, j)]

}

fun newGameOfFifteen(initializer: GameOfFifteenInitializer = RandomGameInitializer()) = GameOfFifteen(initializer)

GameOfFifteenHelper.kt

package games.gameOfFifteen

/*
 * This function should return the parity of the permutation.
 * true - the permutation is even
 * false - the permutation is odd
 * https://en.wikipedia.org/wiki/Parity_of_a_permutation

 * If the game of fifteen is started with the wrong parity, you can't get the correct result
 *   (numbers sorted in the right order, empty cell at last).
 * Thus the initial permutation should be correct.
 */
fun isEven(permutation: List<Int>): Boolean {
    val reordering = permutation.toMutableList()
    var numberOfPermutations = 0
    val ordered = (permutation.min()!!..permutation.max()!!).toList()
    for (expectedIndex in 0 until ordered.size) {
        val searchedValue = ordered[expectedIndex]
        if (searchedValue != reordering[expectedIndex]) {
            val currentIndex = reordering.indexOf(searchedValue)
            numberOfPermutations++
            swap(reordering, expectedIndex, currentIndex)
        }
    }
    return numberOfPermutations % 2 == 0
}

fun swap(arrays: MutableList<Int>, i: Int, j: Int) {
    val old = arrays[i]
    arrays[i] = arrays[j]
    arrays[j] = old
}

GameOfFifteenInitializer.kt

package games.gameOfFifteen

import kotlin.random.Random

interface GameOfFifteenInitializer {
    /*
     * Even permutation of numbers 1..15
     * used to initialized the first 15 cells on a board.
     * The last cell is empty.
     */
    val initialPermutation: List<Int>
}

class RandomGameInitializer : GameOfFifteenInitializer {
    /*
     * Generate a random permutation from 1 to 15.
     * `shuffled()` function might be helpful.
     * If the permutation is not even, make it even (for instance,
     * by swapping two numbers).
     */
    override val initialPermutation by lazy {
        var numbers = (1..15).toMutableList().shuffled()
        while (!isEven(numbers)) {
            numbers = numbers.shuffled()
        }
        numbers
    }
    
}

NiceString.kt

package nicestring

fun String.isNice(): Boolean {
    val firstCondition = setOf("bu", "ba", "be").none { this.contains(it) }
    val secondCondition = count { it in listOf('a', 'e', 'i', 'o', 'u') } > 2
    val thirdCondition = zipWithNext().any { (a, b) ->  a == b}

    return listOf(firstCondition, secondCondition, thirdCondition).filter { it }.size > 1
}

Rationnal.kt

package rationals

import java.math.BigInteger

infix fun Int.divBy(denominator: Int) = Rational(this.toBigInteger(), denominator.toBigInteger())

infix fun Long.divBy(denominator: Long) = Rational(this.toBigInteger(), denominator.toBigInteger())

infix fun BigInteger.divBy(denominator: BigInteger) = Rational(this, denominator)

fun String.toRational(): Rational {
    if (!this.contains('/')) return Rational(this.toBigInteger(), BigInteger.ONE)
    val split = this.split("/")
    return split[0].toBigInteger() divBy split[1].toBigInteger()
}

class Rational(numerator: BigInteger, denominator: BigInteger) : Comparable<Rational> {

    private val numerator: BigInteger
    private val denominator: BigInteger

    init {
        if (denominator == BigInteger.ZERO) throw IllegalArgumentException("Zero is an invalid denominator")

        val gcd = numerator.gcd(denominator)
        var n = numerator / gcd
        var d = denominator / gcd

        if (d < BigInteger.ZERO) {
            n = -n
            d = -d
        }
        this.numerator = n
        this.denominator = d
    }

    operator fun unaryMinus() = Rational(-numerator, denominator)

    operator fun plus(rational: Rational) =
            Rational((numerator * rational.denominator) + (rational.numerator * denominator), denominator * rational.denominator)

    operator fun minus(rational: Rational) =
            Rational((numerator * rational.denominator) - (rational.numerator * denominator), denominator * rational.denominator)

    operator fun times(rational: Rational) =
            Rational(numerator * rational.numerator, denominator * rational.denominator)

    operator fun div(rational: Rational) =
            Rational((numerator * rational.denominator), (rational.numerator * denominator))

    override fun compareTo(other: Rational): Int {
        val first = numerator * other.denominator
        val second = other.numerator * denominator
        return first.compareTo(second)
    }

    override fun toString() = if (denominator == BigInteger.ONE) {
        "$numerator"
    } else {
        "$numerator/$denominator"
    }

    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (javaClass != other?.javaClass) return false

        other as Rational

        if (numerator != other.numerator) return false
        if (denominator != other.denominator) return false

        return true
    }

    override fun hashCode(): Int {
        var result = numerator.hashCode()
        result = 31 * result + denominator.hashCode()
        return result
    }

}


fun main() {
    val half = 1 divBy 2
    val third = 1 divBy 3

    val sum: Rational = half + third
    println(5 divBy 6 == sum)

    val difference: Rational = half - third
    println(1 divBy 6 == difference)

    val product: Rational = half * third
    println(1 divBy 6 == product)

    val quotient: Rational = half / third
    println(3 divBy 2 == quotient)

    val negation: Rational = -half
    println(-1 divBy 2 == negation)

    println((2 divBy 1).toString() == "2")
    println((-2 divBy 4).toString() == "-1/2")
    println("117/1098".toRational().toString() == "13/122")

    val twoThirds = 2 divBy 3
    println(half < twoThirds)

    println(half in third..twoThirds)

    println(2000000000L divBy 4000000000L == 1 divBy 2)

    println("912016490186296920119201192141970416029".toBigInteger() divBy
            "1824032980372593840238402384283940832058".toBigInteger() == 1 divBy 2)
}

TaxiParkTask.kt

package taxipark

/*
 * Task #1. Find all the drivers who performed no trips.
 */
fun TaxiPark.findFakeDrivers(): Set<Driver> =
        allDrivers - trips.map { it.driver }

/*
 * Task #2. Find all the clients who completed at least the given number of trips.
 */
fun TaxiPark.findFaithfulPassengers(minTrips: Int): Set<Passenger> =
        allPassengers.filter { passenger ->
            trips.count { passenger in it.passengers } >= minTrips
        }.toSet()

/*
 * Task #3. Find all the passengers, who were taken by a given driver more than once.
 */
fun TaxiPark.findFrequentPassengers(driver: Driver): Set<Passenger> =
        allPassengers.filter { passenger ->
            trips.count { it.driver == driver && passenger in it.passengers } > 1
        }.toSet()

/*
 * Task #4. Find the passengers who had a discount for majority of their trips.
 */
fun TaxiPark.findSmartPassengers(): Set<Passenger> {
    return allPassengers.filter { p ->
        val withDiscount = trips.count { t -> p in t.passengers && t.discount != null }
        val withoutDiscount = trips.count { t -> p in t.passengers && t.discount == null }
        withDiscount > withoutDiscount
    }.toSet()
}


/*
 * Task #5. Find the most frequent trip duration among minute periods 0..9, 10..19, 20..29, and so on.
 * Return any period if many are the most frequent, return `null` if there're no trips.
 */
fun TaxiPark.findTheMostFrequentTripDurationPeriod(): IntRange? {
    return trips
            .groupBy {
                val start = it.duration / 10 * 10
                val end = start + 9
                start..end
            }.maxBy { (_, group) -> group.size }
            ?.key
}

/*
 * Task #6.
 * Check whether 20% of the drivers contribute 80% of the income.
 */
fun TaxiPark.checkParetoPrinciple(): Boolean {
    if (trips.isEmpty()) return false
    val totalIncome80percent = 0.8 * trips.sumByDouble(Trip::cost)
    val incomeByDrivers = trips
            .groupBy(Trip::driver)
            .map { (_, trips) -> trips.sumByDouble(Trip::cost) }
            .sortedDescending()

    val bestIncomeOf20percentOfDrivers = incomeByDrivers.take((allDrivers.size * 0.2).toInt()).sum()

    return totalIncome80percent <= bestIncomeOf20percentOfDrivers
}