Activity Selection Problem

Activity Selection Problem 通常用於時間表排程或資源分配。

該問題要求在一組互相競爭的活動中，找到一個最大的互不衝突活動子集，使得這些活動能夠在同一時間段內進行，而不會互相干擾。

具體來說，給定一組活動，每個活動都有一個開始時間和一個結束時間，您需要選擇一些活動，使得它們的時間段不重疊，同時最大化所選活動的數量。這個問題的目標是找到一個最優解，即選擇最多的互不衝突活動。

活動選擇問題通常用於優化排程和資源利用，例如在會議安排、課程選擇、工作排程等方面。

簡而言之，它是一個重要的排程問題，需要找到一個最佳的時間表，以滿足特定的約束條件。

// Activity Selection Problem in Kotlin
class ActivitySelection {
    fun printMaxActivities(s: IntArray, f: IntArray, n: Int) {
        var i: Int
        var j: Int
        println("Following activities are selected")
        i = 0
        println(i)
        j = 1
        while (j < n) {
            if (s[j] >= f[i]) {
                println(j)
                i = j
            }
            j++
        }
    }
}

// main function
fun main(args: Array<String>) {
    val s = intArrayOf(1, 3, 0, 5, 8, 5)
    val f = intArrayOf(2, 4, 6, 7, 9, 9)
    val n = s.size
    val asp = ActivitySelection()
    asp.printMaxActivities(s, f, n)
}

Huffman Coding

Huffman Coding 是一種常用於資料壓縮的技術，它是一種讓資料更有效率地儲存或傳輸的方法。它的主要目的是根據不同字符在文本中出現的頻率，為每個字符分配一個獨特的編碼，以便將文本壓縮成較短的位元序列。

Huffman 編碼的主要目的是：將出現頻率高的字符賦予較短的編碼，而出現頻率低的字符賦予較長的編碼。這樣做可以確保經過壓縮後的資料能夠更有效地表示原始資料，從而節省儲存空間或傳輸帶寬。

Huffman 編碼的過程包括建立一個稱為「哈夫曼樹」的二叉樹，其中每個葉子節點代表一個字符，並且根據其出現的頻率排列在樹的不同層次上。然後，通過遞迴地遍歷這個樹，分別賦予0和1的二進制編碼給每個字符，直到編碼為止。

使用Huffman編碼，我們可以將原始文本中的字符轉換為壓縮後的二進制位元序列，並在解壓縮時根據相同的Huffman樹將它們還原成原始字符。

這種技術在許多應用中都有廣泛的應用，例如壓縮檔案、數據傳輸、通信協議等，以提高資料的效率和節省資源。

import java.util.SortedSet

fun main(args: Array<String>) {

    val input = "A_DEAD_DAD_CEDED_A_BAD_BABE_A_BEADED_ABACA_BED"

    val huffmanTree = createHuffmanTree(input)

    val encoder = encoder(huffmanTree)
    val decoder = decoder(huffmanTree)

    val expected = "1000011101001000110010011101100111001001000111110010011111011111100010001111110100111001001011111011101000111111001"

    check(expected == encoder(input)) { "expected did not match encoded result" }
    check(input == decoder(encoder(input))) { "decoding expected did not match input" }
}

fun encoder(huffmanTree: Node): (String) -> String {
    val dictionary = createDictionary(huffmanTree)
    return { input -> input.map { dictionary[it] }.joinToString(separator = "") }
}

fun decoder(huffmanTree: Node): (String) -> String {
    return { input ->
        var remaining = input
        var result = ""
        while (remaining.isNotEmpty()) {
            val (left, answer) = readPath(huffmanTree, remaining)
            result += answer
            remaining = left
        }
        result
    }
}

/**
 * Partially reads a portion of the encoded value and returns the un-read portion of the encoded value and a decoded
 * fragment.
 */
private fun readPath(node: Node, path: String) : Pair<String, String> {
    if (node.left == null || node.right == null) {
        return Pair(path, node.value)
    }
    return when (path[0]) {
        '0' -> readPath(node.left, path.subSequence(1, path.length).toString())
        '1' -> readPath(node.right, path.subSequence(1, path.length).toString())
        else -> Pair("", "")
    }
}

/**
 * Creates a huffman tree based on the input string and the letter frequency analysis of that input string.
 */
fun createHuffmanTree(input: String): Node {
    val nodes = readFrequencies(input)
    while (nodes.size != 1) {
        val (a, b) = nodes.take(2)
        nodes.removeAll(listOf(a, b))
        nodes.add(Node(a.value + b.value, a.freq + b.freq, a, b))
    }
    return nodes.first()
}

/**
 * Creates a set of character nodes and their frequencies, ordered by least frequent first.
 */
private fun readFrequencies(input: String): SortedSet<Node> {
    return input.groupBy { it }
            .mapValues { it.value.size }
            .map { Node(it.key.toString(), it.value) }
            .toSortedSet()
}

/**
 * Creates a dictionary from each leaf character to the path of how to traverse the tree to that leaf.
 */
private fun createDictionary(node: Node, path: String = "") : Map<Char, String> {
    if (node.left == null || node.right == null) {
        check(node.value.length == 1) { "leaf should only contain a single character" }
        return mapOf(Pair(node.value.toCharArray()[0], path))
    }
    return createDictionary(node.left, path + "0") + createDictionary(node.right, path + "1")
}

data class Node(val value: String,
                val freq: Int,
                val left: Node? = null,
                val right: Node? = null) : Comparable<Node> {
    override fun compareTo(other: Node): Int {
        val i = this.freq.compareTo(other.freq)
        return when (i) {
            0 -> other.value.compareTo(this.value)
            else -> i
        }
    }

所有 Code 可以在 Github 找到 ～

感謝大家，明天見！！！

Reference

• andrewrlee/Huffman.kt