From 534715243e65728db4ee90b5ee5dee644ce71dac Mon Sep 17 00:00:00 2001 From: Archargelod Date: Fri, 1 Mar 2024 14:43:05 +0800 Subject: weeks 14-26, 258 in Nim --- challenge-014/archargelod/README | 1 + challenge-014/archargelod/nim/ch_1.nim | 52 ++++++++++++++++++ challenge-014/archargelod/nim/ch_2.nim | 38 ++++++++++++++ challenge-015/archargelod/README | 1 + challenge-015/archargelod/nim/ch_1.nim | 48 +++++++++++++++++ challenge-015/archargelod/nim/ch_2.nim | 49 +++++++++++++++++ challenge-016/archargelod/README | 1 + challenge-016/archargelod/nim/ch_1.nim | 21 ++++++++ challenge-016/archargelod/nim/ch_2.nim | 49 +++++++++++++++++ challenge-017/archargelod/README | 1 + challenge-017/archargelod/nim/ch_1.nim | 16 ++++++ challenge-017/archargelod/nim/ch_2.nim | 96 ++++++++++++++++++++++++++++++++++ challenge-018/archargelod/README | 1 + challenge-018/archargelod/nim/ch_1.nim | 33 ++++++++++++ challenge-018/archargelod/nim/ch_2.nim | 66 +++++++++++++++++++++++ challenge-019/archargelod/README | 1 + challenge-019/archargelod/nim/ch_1.nim | 16 ++++++ challenge-019/archargelod/nim/ch_2.nim | 40 ++++++++++++++ challenge-020/archargelod/README | 1 + challenge-020/archargelod/nim/ch_1.nim | 22 ++++++++ challenge-020/archargelod/nim/ch_2.nim | 28 ++++++++++ challenge-021/archargelod/README | 1 + challenge-021/archargelod/nim/ch_1.nim | 16 ++++++ challenge-021/archargelod/nim/ch_2.nim | 71 +++++++++++++++++++++++++ challenge-022/archargelod/README | 1 + challenge-022/archargelod/nim/ch_1.nim | 48 +++++++++++++++++ challenge-022/archargelod/nim/ch_2.nim | 55 +++++++++++++++++++ challenge-023/archargelod/README | 1 + challenge-023/archargelod/nim/ch_1.nim | 25 +++++++++ challenge-023/archargelod/nim/ch_2.nim | 39 ++++++++++++++ challenge-024/archargelod/README | 1 + challenge-024/archargelod/nim/ch_1.nim | 1 + challenge-024/archargelod/nim/ch_2.nim | 43 +++++++++++++++ challenge-025/archargelod/README | 1 + challenge-025/archargelod/nim/ch_1.nim | 68 ++++++++++++++++++++++++ challenge-025/archargelod/nim/ch_2.nim | 57 ++++++++++++++++++++ challenge-026/archargelod/README | 1 + challenge-026/archargelod/nim/ch_1.nim | 26 +++++++++ challenge-026/archargelod/nim/ch_2.nim | 23 ++++++++ challenge-258/archargelod/nim/ch_1.nim | 22 ++++++++ challenge-258/archargelod/nim/ch_2.nim | 22 ++++++++ 41 files changed, 1103 insertions(+) create mode 100644 challenge-014/archargelod/README create mode 100755 challenge-014/archargelod/nim/ch_1.nim create mode 100755 challenge-014/archargelod/nim/ch_2.nim create mode 100644 challenge-015/archargelod/README create mode 100755 challenge-015/archargelod/nim/ch_1.nim create mode 100755 challenge-015/archargelod/nim/ch_2.nim create mode 100644 challenge-016/archargelod/README create mode 100755 challenge-016/archargelod/nim/ch_1.nim create mode 100755 challenge-016/archargelod/nim/ch_2.nim create mode 100644 challenge-017/archargelod/README create mode 100755 challenge-017/archargelod/nim/ch_1.nim create mode 100755 challenge-017/archargelod/nim/ch_2.nim create mode 100644 challenge-018/archargelod/README create mode 100755 challenge-018/archargelod/nim/ch_1.nim create mode 100755 challenge-018/archargelod/nim/ch_2.nim create mode 100644 challenge-019/archargelod/README create mode 100755 challenge-019/archargelod/nim/ch_1.nim create mode 100755 challenge-019/archargelod/nim/ch_2.nim create mode 100644 challenge-020/archargelod/README create mode 100755 challenge-020/archargelod/nim/ch_1.nim create mode 100755 challenge-020/archargelod/nim/ch_2.nim create mode 100644 challenge-021/archargelod/README create mode 100755 challenge-021/archargelod/nim/ch_1.nim create mode 100755 challenge-021/archargelod/nim/ch_2.nim create mode 100644 challenge-022/archargelod/README create mode 100755 challenge-022/archargelod/nim/ch_1.nim create mode 100755 challenge-022/archargelod/nim/ch_2.nim create mode 100644 challenge-023/archargelod/README create mode 100755 challenge-023/archargelod/nim/ch_1.nim create mode 100755 challenge-023/archargelod/nim/ch_2.nim create mode 100644 challenge-024/archargelod/README create mode 100755 challenge-024/archargelod/nim/ch_1.nim create mode 100755 challenge-024/archargelod/nim/ch_2.nim create mode 100644 challenge-025/archargelod/README create mode 100755 challenge-025/archargelod/nim/ch_1.nim create mode 100755 challenge-025/archargelod/nim/ch_2.nim create mode 100644 challenge-026/archargelod/README create mode 100755 challenge-026/archargelod/nim/ch_1.nim create mode 100755 challenge-026/archargelod/nim/ch_2.nim create mode 100755 challenge-258/archargelod/nim/ch_1.nim create mode 100755 challenge-258/archargelod/nim/ch_2.nim diff --git a/challenge-014/archargelod/README b/challenge-014/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-014/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-014/archargelod/nim/ch_1.nim b/challenge-014/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..f5f4009e0e --- /dev/null +++ b/challenge-014/archargelod/nim/ch_1.nim @@ -0,0 +1,52 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/tables + +proc vanEckNth*(nth: Natural): int = + ## returns nth term of Van Eck's sequence + ## starting from 0-th term: [a(0) = 0] + var lastPos: Table[int, int] + + var prev = 0 + for n in 1 .. nth: + if prev notin lastPos: + lastPos[prev] = n - 1 + prev = 0 + continue + + let m = lastPos[prev] + lastPos[prev] = n - 1 + prev = n - 1 - m + + result = prev + +proc vanEckSequence*(count: Positive): seq[int] = + ## blazingly fast! + ## sub 1ms with 20_000 terms + result = newSeq[int](count) + var lastPos: Table[int, int] + + for n in 1 ..< count: + let prev = result[n - 1] + if prev notin lastPos: + lastPos[prev] = n - 1 + continue + + let m = lastPos[prev] + lastPos[prev] = n - 1 + result[n] = n - 1 - m + +when isMainModule: + import std/unittest + + const + Count = 97 + Expected = [ + 0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, 5, 3, 0, 3, 2, 9, 0, 4, 9, + 3, 6, 14, 0, 6, 3, 5, 15, 0, 5, 3, 5, 2, 17, 0, 6, 11, 0, 3, 8, 0, 3, 3, 1, 42, 0, + 5, 15, 20, 0, 4, 32, 0, 3, 11, 18, 0, 4, 7, 0, 3, 7, 3, 2, 31, 0, 6, 31, 3, 6, 3, + 2, 8, 33, 0, 9, 56, 0, 3, 8, 7, 19, 0, 5, 37, 0, 3, 8, 8, 1 + ] + + suite "Van Eck's sequence": + test "first 97 terms": + check vanEckSequence(Count) == Expected diff --git a/challenge-014/archargelod/nim/ch_2.nim b/challenge-014/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..cd87276a58 --- /dev/null +++ b/challenge-014/archargelod/nim/ch_2.nim @@ -0,0 +1,38 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[sets] + +const USStates = [ + "al", "ak", "az", "ar", "ca", "co", "ct", "de", "fl", "ga", "hi", "id", "il", "in", + "ia", "ks", "ky", "la", "me", "md", "ma", "mi", "mn", "ms", "mo", "mt", "ne", "nv", + "nh", "nj", "nm", "ny", "nc", "nd", "oh", "ok", "or", "pa", "ri", "sc", "sd", "tn", + "tx", "ut", "vt", "va", "wa", "wv", "wi", "wy" +].toHashSet() + +proc isComposableFrom(word: string, syllables: HashSet[string]): bool = + if word.len mod 2 != 0: + return false + + for i in countUp(0, word.len - 2, 2): + if word[i .. i + 1] notin syllables: + return false + + true + +proc longestWordFromSyllables(dictFile: string, syllables: HashSet[string]): string = + let dict = open(dictFile) + defer: + dict.close() + + for word in lines dict: + if word.len < result.len: + continue + if word.isComposableFrom syllables: + result = word + +when isMainModule: + import std/strformat + + const DictPath = "/usr/share/dict/words" + let res = DictPath.longestWordFromSyllables(USStates) + + echo &"Longest word composable from US 2-letter State names is '{res}'" diff --git a/challenge-015/archargelod/README b/challenge-015/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-015/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-015/archargelod/nim/ch_1.nim b/challenge-015/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..dd645f1540 --- /dev/null +++ b/challenge-015/archargelod/nim/ch_1.nim @@ -0,0 +1,48 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/math + +proc primeSieve(max: int): seq[int] = + var sieve = newSeq[bool](max) + + for p in 2 .. sieve.high: + if sieve[p]: + continue + + for i in countUp(2 * p, sieve.high, p): + sieve[i] = true + + for i, notPrime in sieve[2 ..^ 1]: + if not notPrime: + result.add i + 2 + +proc tierPrimesByStrength( + primes: openArray[int] +): tuple[weak, balanced, strong: seq[int]] = + for pInd, prime in primes[0 ..^ 2]: + if pInd == 0: + continue + let mean = (primes[pInd - 1] + primes[pInd + 1]) / 2 + + if almostEqual(prime.float, mean): + result.balanced.add prime + elif prime.float > mean: + result.strong.add prime + elif prime.float < mean: + result.weak.add prime + else: + raiseAssert("Error: bad float comparison.") + +when isMainModule: + import std/unittest + + const + ExpectedWeak = [3, 7, 13, 19, 23, 31, 43, 47, 61, 73] + ExpectedStrong = [11, 17, 29, 37, 41, 59, 67, 71, 79, 97] + + suite "Strong and weak primes": + let (weak, _, strong) = tierPrimesByStrength(primeSieve(200)) + + test "first 10 weak primes": + check weak[0 ..< 10] == ExpectedWeak + test "first 10 strong primes": + check strong[0 ..< 10] == ExpectedStrong diff --git a/challenge-015/archargelod/nim/ch_2.nim b/challenge-015/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..18770f6d15 --- /dev/null +++ b/challenge-015/archargelod/nim/ch_2.nim @@ -0,0 +1,49 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[strutils, math] + +type cipherMode = enum + Encode + Decode + +proc alphaOrd(c: char): int = + c.ord - 'a'.ord + +proc rot(c: sink char, shift: int): char = + char('a'.ord + euclMod(c.alphaOrd + shift, 26)) + +proc vigenereCipher(plaintext: var string, key: string, mode = Encode) = + for i, c in plaintext: + if c notin Letters: + continue + + let key = block: + let tmp = key[i mod key.len].toLowerAscii.alphaOrd + if mode == Decode: -tmp else: tmp + + plaintext[i] = c.toLowerAscii.rot(key) + +proc encode*(plaintext: var string, key: string) = + vigenereCipher(plaintext, key, Encode) + +proc decode*(plaintext: var string, key: string) = + vigenereCipher(plaintext, key, Decode) + + +when isMainModule: + import std/unittest + + const + Plaintext = "attacking tonight" + Key = "OCULORHINOLARINGOLOGY" + ExpectedEncoded = "ovnlqbpvt eoeqtnh" + + suite "Vigenère cipher": + var text = Plaintext + + test "encode sample text": + text.encode(Key) + check text == ExpectedEncoded + + test "decode sample text": + text.decode(Key) + check text == Plaintext diff --git a/challenge-016/archargelod/README b/challenge-016/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-016/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-016/archargelod/nim/ch_1.nim b/challenge-016/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..a5cc61c3f6 --- /dev/null +++ b/challenge-016/archargelod/nim/ch_1.nim @@ -0,0 +1,21 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off + +proc percent(value: float, pct: 0..100): float = + value / 100'f * pct.float + +proc largestPieceOfPieIndex(): int = + var amount = 1'f + var largest = 0'f + + for i in 1..100: + let piece = amount.percent(i) + if piece <= largest: + return i - 1 + largest = piece + amount -= piece + +when isMainModule: + import std/strformat + + let index = largestPieceOfPieIndex() + echo &"{index}th guest gets the largest piece of pie." diff --git a/challenge-016/archargelod/nim/ch_2.nim b/challenge-016/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..52f8e2202b --- /dev/null +++ b/challenge-016/archargelod/nim/ch_2.nim @@ -0,0 +1,49 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/strutils +import pkg/nimcrypto/sha2 ## `$ nimble install nimcrypto` + +const + DecodedLength = 25 + ChecksumLength = 4 + +func base58Decode(input: string): array[DecodedLength, byte] = + ## Taken from https://rosettacode.org/wiki/Bitcoin/address_validation#Nim + ## Tried to implement this myself, but failed to find easy to understand algorithm. + const Base = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz" + + for c in input: + var n = Base.find(c) + if n < 0: + raise newException(ValueError, "invalid character: " & c) + + for i in countdown(result.high, 0): + n += Base.len * result[i].int + result[i] = byte(n and 255) + n = n div 256 + + if n != 0: + raise newException(ValueError, "decoded address is too long") + +func validBtcChecksum(address: openarray[byte]): bool = + let digest1 = sha256.digest(address.toOpenArray(0, address.high - ChecksumLength)).data + let digest2 = sha256.digest(digest1).data + digest2[0 ..< ChecksumLength] == address[^ChecksumLength ..^ 1] + +func isValidBTCAddress(address: string): bool = + address.len >= 26 and address[0] in {'1', '3'} and + validBtcChecksum(address.base58Decode()) + +when isMainModule: + import std/unittest + + const + Valid = ["1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2", "3J98t1WpEZ73CNmQviecrnyiWrnqRhWNLy"] + Invalid = ["3J98t1WpEZ73CNmQviecrnyiWrDEADBEEF"] + + suite "Validate bitcoin address": + test "Example 1": + check isValidBTCAddress Valid[0] + test "Example 2": + check isValidBTCAddress Valid[1] + test "Invalid address": + check not isValidBtcAddress Invalid[0] diff --git a/challenge-017/archargelod/README b/challenge-017/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-017/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-017/archargelod/nim/ch_1.nim b/challenge-017/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..da820ff5d7 --- /dev/null +++ b/challenge-017/archargelod/nim/ch_1.nim @@ -0,0 +1,16 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off + +proc ackermann(m, n: Natural): int = + if m == 0: + n + 1 + elif n == 0: + ackermann(m - 1, 1) + else: + ackermann(m - 1, ackermann(m, n - 1)) + +when isMainModule: + import std/unittest + + suite "Ackermann function": + test "A(1, 2) == 4": + check ackermann(1, 2) == 4 diff --git a/challenge-017/archargelod/nim/ch_2.nim b/challenge-017/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..d64c57515f --- /dev/null +++ b/challenge-017/archargelod/nim/ch_2.nim @@ -0,0 +1,96 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[strutils, parseutils, options] + +type Url = object + scheme, userinfo, host: string + port = 80 + path, query, fragment: string + +template consume(input: string, chars: openarray[char]): bool = + var res = true + for i, c in chars: + if ind < input.len and input[ind] == c: + inc ind + else: + ind -= i + res = false + break + res + +proc parseUrl(input: string): Url = + result = Url() + + var ind = 0 + let schemeEnd = input.skipUntil({':'}, ind) + result.scheme = input[0 ..< schemeEnd] + ind += schemeEnd + + if not input.consume(":"): + raiseAssert("expected ':'") + + if input.consume("//"): + # user:password pair (optional) + let userinfoEnd = input.skipUntil({'@'}, ind) + if ind + userinfoEnd < input.len: + result.userinfo = input[ind ..< ind + userinfoEnd] + ind += userInfoEnd + 1 + + # hostname + let hostEnd = input.skipUntil({':', '/'}, ind) + if ind + hostEnd > input.high: + raiseAssert("expected ':' or '/'") + result.host = input[ind ..< ind + hostEnd] + ind += hostEnd + + # port (optional) + if input.consume(":"): + let portEnd = input.skipWhile(Digits, ind) + result.port = parseInt input[ind ..< ind + portEnd] + ind += portEnd + + # path + let pathEnd = input.skipUntil({'?', '#'}, ind) + result.path = input[ind ..< ind + pathEnd] + ind += pathEnd + + # query (optional) + if input.consume("?"): + let queryEnd = input.skipUntil({'#'}, ind) + result.query = input[ind ..< ind + queryEnd] + ind += queryEnd + + # match fragment (optional) + if input.consume("#"): + result.fragment = input[ind ..^ 1] + +when isMainModule: + import std/unittest + + const + Test = [ + "jdbc://user:password@localhost:3306/pwc?profile=true#h1", + "file:/home/test/hello.txt" + ] + Expected = [ + Url( + scheme: "jdbc", + userinfo: "user:password", + host: "localhost", + port: 3306, + path: "/pwc", + query: "profile=true", + fragment: "h1", + ), + Url( + scheme: "file", + port: 80, + path: "/home/test/hello.txt", + ) + ] + + suite "URL parsing": + test "Example 1": + check parseUrl(Test[0]) == Expected[0] + + test "Minimal Example": + check parseUrl(Test[1]) == Expected[1] diff --git a/challenge-018/archargelod/README b/challenge-018/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-018/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-018/archargelod/nim/ch_1.nim b/challenge-018/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..247f7682b5 --- /dev/null +++ b/challenge-018/archargelod/nim/ch_1.nim @@ -0,0 +1,33 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[sets, strutils, sequtils] + +proc longest(lines: sink openarray[string]): string = + for line in lines: + if line.len > result.len: + result = line + +proc longestCommonSubstring(lines: openarray[string]): string = + var substrings: HashSet[string] + + let first = lines[0] + for i in 0 .. first.high: + for j in i .. first.high: + if i == 0 and j == first.high: continue + substrings.incl first[i .. j] + + for line in lines: + var newSubstrings: HashSet[string] + for sub in substrings: + if sub in line: + newSubstrings.incl sub + substrings = newSubstrings + + substrings.toSeq.longest() + + +when isMainModule: + import std/unittest + + suite "Longest common substring": + test "Example 1": + check longestCommonSubstring(["ABABC", "BABCA", "ABCBA"]) == "ABC" diff --git a/challenge-018/archargelod/nim/ch_2.nim b/challenge-018/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..5da5e8e0db --- /dev/null +++ b/challenge-018/archargelod/nim/ch_2.nim @@ -0,0 +1,66 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +type + PriorityQueue*[T] = object + data: seq[tuple [item: T, priority: Natural]] + +proc isEmpty*(q: PriorityQueue): bool = + q.data.len == 0 + +proc add*[T](q: var PriorityQueue[T], item: sink T, priority: Natural = 0) = + ## add item to the queue with specified priority + ## 0 is max priority, 1 is less priority than 0 and so on + proc findBestPos(data: seq[tuple [item: T, priority: Natural]], priority: int): int = + # binary search + var + pivot = data.len div 2 + left = 0 + right = data.high + + while right - left > 1: + if priority < data[pivot].priority: + left = pivot + else: + right = pivot + pivot = left + (right - left) div 2 + + right + + if q.isEmpty or priority <= q.data[^1].priority: + q.data.add (item, priority) + elif priority > q.data[0].priority: + q.data.insert((item, priority), 0) + else: + var pos = q.data.findBestPos(priority) + q.data.insert((item, priority), pos) + +proc pop*[T](q: var PriorityQueue[T]): T = + ## remove the item with minimum priority value from the queue + ## and return it + if q.isEmpty: + raise newException(ValueError, "can't pop value; the queue is empty") + q.data.pop().item + +when isMainModule: + import std/unittest + + const + Test = [ + ("World", 20), + (",", 5), + ("!", 1000), + ("Hello", 0), + (" ", 10), + ] + Expected = "Hello, World!" + + suite "Priority Queue": + test "Hello world ordered with priority": + var queue: PriorityQueue[string] + var res = newStringOfCap(Expected.len) + for (word, prio) in Test: + queue.add(word, prio) + + while not queue.isEmpty: + res &= queue.pop() + + check res == Expected diff --git a/challenge-019/archargelod/README b/challenge-019/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-019/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-019/archargelod/nim/ch_1.nim b/challenge-019/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..56eaf65648 --- /dev/null +++ b/challenge-019/archargelod/nim/ch_1.nim @@ -0,0 +1,16 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +## The only way for a month to have 5 full weekends (Fri, Sat, Sun) is +## to be 31 days long and start on Friday: +## +## .... 567 +## 1234 567 +## 1234 567 +## 1234 567 +## 1234 567 +import std/[times] + +for year in 1900..2019: + for month in Month: + if getDaysInMonth(month, year) == 31 and + getDayOfWeek(1, month, year) == dFri: + echo ($month)[0..2], '-', year diff --git a/challenge-019/archargelod/nim/ch_2.nim b/challenge-019/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..e6e72d9db2 --- /dev/null +++ b/challenge-019/archargelod/nim/ch_2.nim @@ -0,0 +1,40 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[parseutils, strutils] + +proc wrap*(text: var string, lineWidth: Positive = 80) = + var spaceLeft: int = lineWidth + var index = 0 + while index < text.high: + let wordWidth = text.skipUntil(Whitespace, index) + let spaceWidth = text.skipWhile(Whitespace, index + wordWidth) + + #echo (text[index.. spaceLeft: + text.insert("\n", index) + spaceLeft = lineWidth - (wordWidth + spaceWidth) + inc index # for added newLine + else: + spaceLeft -= wordWidth + spaceWidth + index += wordWidth + spaceWidth + +proc wrapped*(text: sink string, lineWidth: Positive = 80): string = + result = text + result.wrap(lineWidth) + +when isMainModule: + import std/unittest + + const + Text = """ +A simple way to do word wrapping is to use a greedy algorithm that puts as many words on a line as possible, then moving on to the next line to do the same until there are no more words left to place. This method is used by many modern word processors, such as OpenOffice.org Writer and Microsoft Word. This algorithm always uses the minimum possible number of lines but may lead to lines of widely varying lengths.""" + Expected = """ +A simple way to do word wrapping is to use a greedy algorithm that puts as many +words on a line as possible, then moving on to the next line to do the same +until there are no more words left to place. This method is used by many modern +word processors, such as OpenOffice.org Writer and Microsoft Word. This +algorithm always uses the minimum possible number of lines but may lead to +lines of widely varying lengths.""" + + suite "Greedy line wrapping": + test "wikipedia paragraph": + check Text.wrapped(80) == Expected diff --git a/challenge-020/archargelod/README b/challenge-020/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-020/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-020/archargelod/nim/ch_1.nim b/challenge-020/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..55823e7de9 --- /dev/null +++ b/challenge-020/archargelod/nim/ch_1.nim @@ -0,0 +1,22 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off + +proc splitSameChars(s: string): seq[string] = + result = newSeqOfCap[string](s.len) + result.add $s[0] + + for c in s.toOpenArray(1, s.high): + if c != result[^1][^1]: + result.add $c + else: + result[^1] &= c + +when isMainModule: + import std/unittest + + const + Test = "ABBCDEEF" + Expected = ["A", "BB", "C", "D", "EE", "F"] + + suite "Same-character groups": + test "Example 1": + check Test.splitSameChars() == Expected diff --git a/challenge-020/archargelod/nim/ch_2.nim b/challenge-020/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..f8d47e2d01 --- /dev/null +++ b/challenge-020/archargelod/nim/ch_2.nim @@ -0,0 +1,28 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off + +proc aliquotSum[T: SomeInteger](n: T): T = + for d in T(1) .. T(n div 2): + if n mod d == 0: + result += d + +proc smallestAmicablePair(): (int, int) = + var invalid: set[int16] # could be useful for later pairs + + for first in 1'i16 .. high(int16): + if first in invalid: continue + + let second = aliquotSum(first) + if second != first and aliquotSum(second) == first: + return (first.int, second.int) + + invalid.incl first + invalid.incl second + +when isMainModule: + import std/unittest + + const Expected = (220, 284) + + suite "Smallest Amicable Number pair": + test "first pair is 220 and 284": + check smallestAmicablePair() == Expected diff --git a/challenge-021/archargelod/README b/challenge-021/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-021/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-021/archargelod/nim/ch_1.nim b/challenge-021/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..b93d56e1ef --- /dev/null +++ b/challenge-021/archargelod/nim/ch_1.nim @@ -0,0 +1,16 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import pkg/mapm + +proc approximateE(precision: int): Mapm = + let n = 1e41'm + pow(1'm + divide(1'm, n, precision), n, precision).round(precision) + +when isMainModule: + import std/unittest + + const + Expected = "2.7182818284590452353602874713526624977572" + + suite "Euler's number": + test "40-digit precision": + check $approximateE(40) == Expected diff --git a/challenge-021/archargelod/nim/ch_2.nim b/challenge-021/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..ec3b22ded2 --- /dev/null +++ b/challenge-021/archargelod/nim/ch_2.nim @@ -0,0 +1,71 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[uri, strutils, parseutils] + +template upd(mut, procedure: typed) = + mut = procedure(mut) + +proc normalizePercentEncoded(url: string): string = + result = url + + template decodeUnreserved(s: string, i: int) = + let hex = s[i+1..i+2].parseHexInt + case hex + of 0x41..0x5A, 0x61..0x7A, 0x30..0x39, 0x2D, 0x2E, 0x5F, 0x7E: + s[i..i+2] = $hex.chr + else: + discard + + var index = 0 + while index < result.len: + if result[index] == '%': + result[index + 1].upd(toUpperAscii) + result[index + 2].upd(toUpperAscii) + result.decodeUnreserved(index) + + index += 2 + + inc index + +proc removeDotSegments(path: string): string = + var stack: seq[string] + var ind = 1 + while ind < path.len: + let segmentLength = path.skipUntil('/', ind) + let lastSegment = path[ind..= count: + break + + var pairInd = pi + 1 + while primes[pairInd] - prime < 6: + inc pairInd + + if primes[pairInd] - prime == 6: + result.add (prime, primes[pairInd]) + +when isMainModule: + import std/unittest + + const Expected = [ + (5, 11), + (7, 13), + (11, 17), + (13, 19), + (17, 23), + (23, 29), + (31, 37), + (37, 43), + (41, 47), + (47, 53), + ] + + suite "Sexy prime pairs": + test "first 10 pairs": + check sexyPrimePairs(max = 100, count = 10) == Expected diff --git a/challenge-022/archargelod/nim/ch_2.nim b/challenge-022/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..3c10388559 --- /dev/null +++ b/challenge-022/archargelod/nim/ch_2.nim @@ -0,0 +1,55 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/tables + +proc lzwEncoded(input: string): seq[int] = + var dict: Table[string, int] + for c in 'a'..'z': + dict[$c] = dict.len + dict[" "] = dict.len + + var ind = 0 + var word = "" + while ind < input.len: + word = $input[ind] + + while ind < input.high and word & input[ind+1] in dict: + word &= input[ind+1] + inc ind + + result.add dict[word] + if ind < input.high: + dict[word & input[ind+1]] = dict.len + inc ind + +proc lzwDecoded(input: openarray[int]): string = + var dict: Table[int, string] + for c in 'a'..'z': + dict[dict.len] = $c + dict[dict.len] = " " + + var lastEmitted = "" + for i, encoded in input: + if encoded in dict: + let word = dict[encoded] + if i > 0: + dict[dict.len] = lastEmitted & word[0] + + result &= word + lastEmitted = word + else: + let v = lastEmitted & lastEmitted[0] + dict[dict.len] = v + + result &= v + lastEmitted = v + + +when isMainModule: + import std/unittest + + const + Test = "further refinements include reserving a code to indicate that the code table should be cleared and restored to its initial state a clear code typically the first value immediately after the values for the individual alphabet characters and a code to indicate the end of data a stop code typically one greater than the clear code the clear code lets the table be reinitialized after it fills up which lets the encoding adapt to changing patterns in the input data smart encoders can monitor the compression efficiency and clear the table whenever the existing table no longer matches the input well" + + suite "Lempel–Ziv–Welch (LZW) compression algorithm": + test "long text": + check lzwEncoded(Test).lzwDecoded == Test diff --git a/challenge-023/archargelod/README b/challenge-023/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-023/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-023/archargelod/nim/ch_1.nim b/challenge-023/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..c87d0b495a --- /dev/null +++ b/challenge-023/archargelod/nim/ch_1.nim @@ -0,0 +1,25 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import sequtils + +proc nthOrderForwardDifference(numbers: openarray[int], order = 1): seq[int] = + result = numbers.toSeq + for i in 1..order: + for j, num in result.toOpenArray(0, result.high - 1): + result[j] = result[j+1] - num + result.setLen(result.len - 1) + +when isMainModule: + import std/unittest + + const + Test = [5, 9, 2, 8, 1, 6] + Expected = [ + @[4, -7, 6, -7, 5], + @[-11, 13, -13, 12], + ] + + suite "nth order forward difference series": + test "first order": + check Test.nthOrderForwardDifference(1) == Expected[0] + test "second order": + check Test.nthOrderForwardDifference(2) == Expected[1] diff --git a/challenge-023/archargelod/nim/ch_2.nim b/challenge-023/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..f80edd3c3f --- /dev/null +++ b/challenge-023/archargelod/nim/ch_2.nim @@ -0,0 +1,39 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off + +proc primeSieve(max: int): seq[int] = + var sieve = newSeq[bool](max) + + for p in 2 .. sieve.high: + if sieve[p]: + continue + + for i in countUp(2 * p, sieve.high, p): + sieve[i] = true + + for i, notPrime in sieve.toOpenArray(2, sieve.high): + if not notPrime: + result.add i + 2 + +proc primeDecomposition(n: int): seq[int] = + let primes = primeSieve(n) + + var number = n + var pInd = 0 + while number > 1: + let prime = primes[pInd] + if number mod prime == 0: + result.add prime + number = number div prime + else: + inc pInd + +when isMainModule: + import std/unittest + + const + Test = 228 + Expected = [2,2,3,19] + + suite "Prime decomposition": + test "decomposition of 228 is 2,2,3,19": + check Test.primeDecomposition() == Expected diff --git a/challenge-024/archargelod/README b/challenge-024/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-024/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-024/archargelod/nim/ch_1.nim b/challenge-024/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..d51adfeb64 --- /dev/null +++ b/challenge-024/archargelod/nim/ch_1.nim @@ -0,0 +1 @@ +#!/usr/bin/env -S nim r \ No newline at end of file diff --git a/challenge-024/archargelod/nim/ch_2.nim b/challenge-024/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..5e12db7123 --- /dev/null +++ b/challenge-024/archargelod/nim/ch_2.nim @@ -0,0 +1,43 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[os, tables, strutils, strformat, sugar] + +type InvIndex* = object + indexes: Table[string, set[uint16]] + files: Table[uint16, string] + +proc initInvertedIndex(dir: string): InvIndex = + result = InvIndex() + for file in dir.walkDir(): + if file.kind != pcFile: continue + + let fileId = result.files.len.uint16 + result.files[fileId] = file.path.splitPath.tail + + for line in lines file.path: + for word in line.split(Whitespace + PunctuationChars): + if word.len < 1: continue + let word = word.toLower() + if word notin result.indexes: + result.indexes[word] = {fileId.uint16} + else: + result.indexes[word].incl fileId.uint16 + +proc `$`(db: InvIndex): string = + const offset = 30 + + result &= "{\n" + + for word, fileIds in db.indexes: + let namePart = &" '{word}'" + result &= namePart + result &= ' '.repeat(max(0, offset - namePart.len)) & ": " + + result.add $collect( + for id in fileIds: + db.files[id] + ) + result &= "\n" + result &= "}" + +when isMainModule: + echo initInvertedIndex("/usr/share/awk") diff --git a/challenge-025/archargelod/README b/challenge-025/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-025/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-025/archargelod/nim/ch_1.nim b/challenge-025/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..d3e5472fdc --- /dev/null +++ b/challenge-025/archargelod/nim/ch_1.nim @@ -0,0 +1,68 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[sequtils] + +func makeMap(words: openArray[string]): seq[seq[int8]] = + result = newSeq[seq[int8]](words.len) + for i, current in words: + for j, next in words: + if i == j: + continue + if current[^1] == next[0]: + result[i].add j.int8 + +func longestChains*(words: openArray[string]): seq[seq[string]] = + let map = makeMap(words) + var paths = newSeqOfCap[seq[int8]](128) + var longest = newSeqOfCap[seq[int8]](1300) + + for id, exits in map: + if exits.len > 0: + paths.add @[id.int8] + + while paths.len > 0: + let path = paths.pop() + let last = path[^1] + var endpoint = true + + for exit in map[last]: + if exit notin path: + paths.add path & exit + endpoint = false + + if endpoint: + if longest.len < 1 or path.len > longest[0].len: + longest = @[path] + elif path.len == longest[0].len: + longest.add path + + longest.mapIt(it.mapIt(words[it])) + +when isMainModule: + import std/unittest + + const + Names = [ + "audino", "bagon", "baltoy", "banette", "bidoof", "braviary", "bronzor", + "carracosta", "charmeleon", "cresselia", "croagunk", "darmanitan", "deino", + "emboar", "emolga", "exeggcute", "gabite", "girafarig", "gulpin", "haxorus", + "heatmor", "heatran", "ivysaur", "jellicent", "jumpluff", "kangaskhan", + "kricketune", "landorus", "ledyba", "loudred", "lumineon", "lunatone", "machamp", + "magnezone", "mamoswine", "nosepass", "petilil", "pidgeotto", "pikachu", "pinsir", + "poliwrath", "poochyena", "porygon2", "porygonz", "registeel", "relicanth", + "remoraid", "rufflet", "sableye", "scolipede", "scrafty", "seaking", "sealeo", + "silcoon", "simisear", "snivy", "snorlax", "spoink", "starly", "tirtouga", + "trapinch", "treecko", "tyrogue", "vigoroth", "vulpix", "wailord", "wartortle", + "whismur", "wingull", "yamask" + ] + Expected = @[ + "machamp", "pinsir", "rufflet", "trapinch", "heatmor", "remoraid", "darmanitan", + "nosepass", "starly", "yamask", "kricketune", "exeggcute", "emboar", + "relicanth", "haxorus", "simisear", "registeel", "landorus", "seaking", + "girafarig", "gabite", "emolga", "audino" + ] + + suite "Head to tail Pokémon names": + test "longest chain is 23 pokemons: machamp -> audino": + let longest = longestChains(Names) + check longest.allIt(it.len == 23) + check Expected in longest diff --git a/challenge-025/archargelod/nim/ch_2.nim b/challenge-025/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..56ca084716 --- /dev/null +++ b/challenge-025/archargelod/nim/ch_2.nim @@ -0,0 +1,57 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[algorithm] + +type + Alphabet = array[26, char] + Chaocipher* = object + zenith: int + left, right: Alphabet + +proc permute(disk: var Chaocipher) = + # permute left disk + let tmp = disk.left[(disk.zenith + 1) mod 26] + for i in disk.zenith + 1 .. disk.zenith + 12: + disk.left[i mod 26] = disk.left[(i + 1) mod 26] + disk.left[(disk.zenith + 13) mod 26] = tmp + + # permute right disk + disk.right.rotateLeft(1) + let tmp2 = disk.right[(disk.zenith + 2) mod 26] + for i in disk.zenith + 2 .. disk.zenith + 12: + disk.right[i mod 26] = disk.right[(i + 1) mod 26] + disk.right[(disk.zenith + 13) mod 26] = tmp2 + +proc encipher*(plaintext: string, left, right: Alphabet): string = + var disk = Chaocipher(left: left, right: right) + for c in plaintext: + disk.zenith = disk.right.find(c) + result.add disk.left[disk.zenith] + disk.permute() + +proc decipher*(ciphertext: string, left, right: Alphabet): string = + var disk = Chaocipher(left: left, right: right) + for c in ciphertext: + disk.zenith = disk.left.find(c) + result.add disk.right[disk.zenith] + disk.permute() + +when isMainModule: + import std/unittest + + const + LeftAlphabet = [ + 'b', 'f', 'v', 'g', 'u', 'h', 'w', 'j', 'k', 'n', 'c', 'p', 'e', 'd', 'q', 'r', + 's', 't', 'i', 'x', 'y', 'l', 'm', 'o', 'z', 'a', + ] + RightAlphabet = [ + 'c', 'm', 'o', 'p', 'r', 't', 'u', 'v', 'j', 'x', 'a', 'y', 'z', 'n', 'b', 'q', + 'd', 's', 'e', 'f', 'g', 'h', 'l', 'w', 'i', 'k', + ] + Plaintext = "allgoodqquickbrownfoxesjumpoverlazydogtosavetheirpartyw" + Ciphertext = "clytzpnzklddqgfbootysnepuagkiunkncrinrcvkjnhtoafqpdpncv" + + suite "Chaocipher": + test "Encipher text": + check Plaintext.encipher(LeftAlphabet, RightAlphabet) == Ciphertext + test "Decipher text": + check Ciphertext.decipher(LeftAlphabet, RightAlphabet) == Plaintext diff --git a/challenge-026/archargelod/README b/challenge-026/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-026/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-026/archargelod/nim/ch_1.nim b/challenge-026/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..807a9b847b --- /dev/null +++ b/challenge-026/archargelod/nim/ch_1.nim @@ -0,0 +1,26 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[strutils] + +proc countLetters(input, alphabet: string): int = + let uniq = block: + var tmp: set[char] + for c in alphabet: + if c notin Letters: continue + tmp.incl c + tmp + + for c in input: + if c in uniq: + inc result + +when isMainModule: + import std/unittest + + const + Test = "chancellor" + Alphabet = "chocolate" + Expected = 8 + + suite "Stones and jewels alphabets": + test "Example 1": + check Test.countLetters(Alphabet) == Expected diff --git a/challenge-026/archargelod/nim/ch_2.nim b/challenge-026/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..cd7c76908f --- /dev/null +++ b/challenge-026/archargelod/nim/ch_2.nim @@ -0,0 +1,23 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[math, sequtils] + +proc circularMean(degrees: varargs[float, toFloat]): float = + let radians = degrees.mapIt(it.degToRad) + + let sinSum = radians.mapIt(it.sin).sum() + let cosSum = radians.mapIt(it.cos).sum() + + arctan2(sinSum, cosSum).radToDeg.euclMod(360) + +when isMainModule: + import std/unittest + + const + Test = [@[180.0, 200.0], @[355.0, 5.0, 15.0]] + Expected = [190.0, 5.0] + + suite "Mean angles": + test "180, 200 -> 190": + check almostEqual(Test[0].circularMean(), Expected[0]) + test "355, 5, 15 -> 5": + check almostEqual(Test[1].circularMean(), Expected[1]) diff --git a/challenge-258/archargelod/nim/ch_1.nim b/challenge-258/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..175af303f2 --- /dev/null +++ b/challenge-258/archargelod/nim/ch_1.nim @@ -0,0 +1,22 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off + +proc countEvenDigitsNumbers(numbers: openarray[Natural]): int = + for num in numbers: + if num < 0: raise newException(ValueError, "Only positive values allowed") + if len($num) mod 2 == 0: + inc result + +when isMainModule: + import std/unittest + + const + Test = [@[10.Natural, 1, 111, 24, 1000], @[111, 1, 11111], @[2, 8, 1024, 256]] + Expected = [3, 0, 1] + + suite "Count Even Digits Number": + test "Example 1": + check countEvenDigitsNumbers(Test[0]) == Expected[0] + test "Example 2": + check countEvenDigitsNumbers(Test[1]) == Expected[1] + test "Example 3": + check countEvenDigitsNumbers(Test[2]) == Expected[2] diff --git a/challenge-258/archargelod/nim/ch_2.nim b/challenge-258/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..d7bbad4430 --- /dev/null +++ b/challenge-258/archargelod/nim/ch_2.nim @@ -0,0 +1,22 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/strutils + +proc indexSetBitsNumberSum(numbers: openarray[int], setBits: int): int = + for ind, num in numbers: + if ind.toBin(64).count('1') == setBits: + result += num + +when isMainModule: + import std/unittest + + const + Test = [(@[2, 5, 9, 11, 3], 1), (@[2, 5, 9, 11, 3], 2), (@[2, 5, 9, 11, 3], 0)] + Expected = [17, 11, 2] + + suite "Sum of Values": + test "Example 1": + check indexSetBitsNumberSum(Test[0][0], Test[0][1]) == Expected[0] + test "Example 2": + check indexSetBitsNumberSum(Test[1][0], Test[1][1]) == Expected[1] + test "Example 3": + check indexSetBitsNumberSum(Test[2][0], Test[2][1]) == Expected[2] -- cgit