diff options
63 files changed, 4684 insertions, 2188 deletions
diff --git a/challenge-005/archargelod/README b/challenge-005/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-005/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-005/archargelod/nim/ch_1.nim b/challenge-005/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..43f865180d --- /dev/null +++ b/challenge-005/archargelod/nim/ch_1.nim @@ -0,0 +1,30 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[strutils, algorithm, sets] + +let dict = block: + var tmp: Hashset[string] + for word in lines "/usr/share/dict/words": + tmp.incl word + tmp + +proc allAnagrams(word: string): seq[string] = + var tmp = word + while tmp.nextPermutation(): + let word = tmp.join() + if word in dict: result.add word + + tmp = word + while tmp.prevPermutation(): + let word = tmp.join() + if word in dict: result.add word + +when isMainModule: + import std/unittest + + const + TestWord1 = "god" + ExpectedAnagrams1 = sorted ["dog"] + + suite "All anagrams for word": + test "should return all anagrams for \'god\'": + check sorted(allAnagrams(TestWord1)) == ExpectedAnagrams1 diff --git a/challenge-005/archargelod/nim/ch_2.nim b/challenge-005/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..dbe7b063fe --- /dev/null +++ b/challenge-005/archargelod/nim/ch_2.nim @@ -0,0 +1,16 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[algorithm, strutils, strformat, tables] + +proc mostAnagramWord(dictfile: string): (seq[char], int) = + var counts: CountTable[seq[char]] + for word in lines dictFile: + counts.inc word.sorted() + + counts.largest + +proc main = + let (val, cnt) = mostAnagramWord("/usr/share/dict/words") + echo &"Word with most anagrams is '{val.join()}' with count of {$cnt} possible anagrams." + +when isMainModule: + main() diff --git a/challenge-006/archargelod/README b/challenge-006/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-006/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-006/archargelod/nim/ch_1.nim b/challenge-006/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..0e1c252ea3 --- /dev/null +++ b/challenge-006/archargelod/nim/ch_1.nim @@ -0,0 +1,33 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off + +type + NumberRange = tuple + val, l: int + +func `$`(s: NumberRange): string = + if s.l == 0: + $s.val + elif s.l == 1: + $s.val & ',' & $(s.val + s.l) + else: + $s.val & '-' & $(s.val + s.l) + +func compactNumString*(numbers: openarray[int]): string = + if numbers.len < 1: return result + + var range: NumberRange = (numbers[0], 0) + for i, num in numbers[1..^1]: + if num == range.val + range.l + 1: + inc range.l + else: + result &= $range & ',' + range = (num, 0) + + result &= $range + +when isMainModule: + import std/unittest + + suite "Compact number lists": + test "Example 1": + check compactNumString([1,2,3,4,9,10,14,15,16]) == "1-4,9,10,14-16" diff --git a/challenge-006/archargelod/nim/ch_2.nim b/challenge-006/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..7f788da601 --- /dev/null +++ b/challenge-006/archargelod/nim/ch_2.nim @@ -0,0 +1,11 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import pkg/mapm # `$ nimble install mapm` + +let approxR* = pow(640_320'M, 3) + 744'M - divide(75'M, 100_000_000_000_000'M, 16) + +when isMainModule: + import std/unittest + + suite "Ramanujan's constant": + test "32-digit approximation": + check $approxR == "262537412640768743.99999999999925" diff --git a/challenge-007/archargelod/README b/challenge-007/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-007/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-007/archargelod/nim/ch_1.nim b/challenge-007/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..13b3d016c1 --- /dev/null +++ b/challenge-007/archargelod/nim/ch_1.nim @@ -0,0 +1,21 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off + +proc sumOfDigits(n: int): int = + for d in $n: + result += d.ord - '0'.ord + +proc allNivenNumbers(range: HSlice[int, int]): seq[int] = + for n in max(1, range.a) .. range.b: + if n mod sumOfDigits(n) == 0: + result.add n + +when isMainModule: + import std/[unittest] + + const Expected = [ + 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 18, 20, 21, 24, 27, 30, 36, 40, 42, 45, 48, 50 + ] + + suite "Niven numbers": + test "niven numbers 0 to 50": + check allNivenNumbers(0 .. 50) == Expected diff --git a/challenge-007/archargelod/nim/ch_2.nim b/challenge-007/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..ef95601c09 --- /dev/null +++ b/challenge-007/archargelod/nim/ch_2.nim @@ -0,0 +1,87 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[tables, deques] + +type Node = ref object + word: string + neighbours: seq[Node] + +func hammingDist(s1, s2: string): int = + if s1.len != s2.len: + raise newException(ValueError, "Both words should be the same length.") + for i, c in s1: + if c != s2[i]: + inc result + +func shortestPath(start: Node, finish: string): seq[string] = + var paths: Deque[seq[Node]] + paths.addFirst @[start] + + while paths.len > 0: + var + path = paths.popLast() + last = path[^1] + + if last.word == finish: + for n in path: + result.add n.word + return result + + for neighbour in last.neighbours: + if neighbour notin path: + paths.addLast path & neighbour + + raise newException(ValueError, "No path exists.") + +func makeMap(words: sink seq[string], start: string): Node = + var nodes: Table[string, Node] + + for word in words: + nodes[word] = Node(word: word) + + for i, word in words: + for j, word2 in words: + if i == j: + continue + if hammingDist(word, word2) == 1: + nodes[word].neighbours.add nodes[word2] + + nodes[start] + +proc makeMap(dictFile, start: string): Node = + var words: seq[string] + for word in lines dictFile: + words.add word + makeMap(words, start) + +proc findShortestWordLadder*( + start, finish: string, dict: string | seq[string] + ): seq[string] = + ## dict should be the path to dictionary file + ## with words separated by newlines or `seq[string]` of these words + ## dictionary words should be the same length + ## returns empty `seq[string]` on error. + try: + var startNode = makeMap(dict, start) + result = startNode.shortestPath(finish) + except ValueError: + return @[] + +when isMainModule: + import std/unittest + + const + Words = @["cold", "cord", "core", "care", "card", "ward", "warm"] + WrongLengthWords = @["cold", "cord", "core", "caress"] + NoPathsWords = @["cold", "rule", "core", "bear"] + Start = "cold" + Finish = "warm" + Expected = @["cold", "cord", "card", "ward", "warm"] + Empty: seq[string] = @[] + + suite "Word Ladders": + test "cold -> warm": + check findShortestWordLadder(Start, Finish, Words) == Expected + test "wrong length": + check findShortestWordLadder(Start, Finish, WrongLengthWords) == Empty + test "no possible paths": + check findShortestWordLadder(Start, Finish, NoPathsWords) == Empty diff --git a/challenge-008/archargelod/README b/challenge-008/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-008/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-008/archargelod/nim/ch_1.nim b/challenge-008/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..2dd3eccd25 --- /dev/null +++ b/challenge-008/archargelod/nim/ch_1.nim @@ -0,0 +1,13 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/math + +proc fivePerfectNumbers(): array[5, int] = + const Primes = [2, 3, 5, 7, 13] + for i, p in Primes: + result[i] = (2 ^ (p - 1)) * (2 ^ p - 1) + +when isMainModule: + import std/unittest + suite "Perfect numbers": + test "first 5 perfect numbers": + check fivePerfectNumbers() == [6, 28, 496, 8128, 33550336] diff --git a/challenge-008/archargelod/nim/ch_2.nim b/challenge-008/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..d96b378446 --- /dev/null +++ b/challenge-008/archargelod/nim/ch_2.nim @@ -0,0 +1,23 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/strutils + +proc center(lines: varargs[string]): seq[string] = + let maxOffset = block: + var maxLen = 0 + for line in lines: + if line.len > maxLen: + maxLen = line.len + maxLen div 2 + + for line in lines: + result.add ' '.repeat(maxOffset - line.len div 2) & line + +when isMainModule: + import std/unittest + + const Example = ["This", "is", "a test of the", "center function"] + const Expected = [" This", " is", " a test of the", "center function"] + + suite "Centering strings": + test "Example 1": + check center(Example) == Expected diff --git a/challenge-009/archargelod/README b/challenge-009/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-009/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-009/archargelod/nim/ch_1.nim b/challenge-009/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..817d551fef --- /dev/null +++ b/challenge-009/archargelod/nim/ch_1.nim @@ -0,0 +1,19 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +proc distinctDigitsCount(number: int): int = + var digits: set[char] + for d in $number: + if d notin digits: + digits.incl d + digits.len + +proc findSquareNDistinctDigits*(digits: range[1 .. 10]): int = + var n = 1 + while result.distinctDigitsCount < digits: + result = n * n + inc n + +when isMainModule: + import std/unittest + suite "Square with 5 distinct digits": + test "12769 is the first square with 5 distinct digits": + check findSquareNDistinctDigits(5) == 12769 diff --git a/challenge-009/archargelod/nim/ch_2.nim b/challenge-009/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..6105f56f60 --- /dev/null +++ b/challenge-009/archargelod/nim/ch_2.nim @@ -0,0 +1,59 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[algorithm] + +type + IndexedItems[T] = seq[tuple[val: T, idx: int]] + TieStrategy = enum + Standard + Modified + Dense + +proc standardRanking(items: sink IndexedItems): seq[int] = + result = newSeq[int](items.len) + var currentRank = 1 + for i, (item, idx) in items: + if i > 0 and items[i - 1].val < item: + currentRank = i + 1 + result[idx] = currentRank + +proc modifiedRanking(items: sink IndexedItems): seq[int] = + result = newSeq[int](items.len) + var currentRank = items.len + for i in countDown(items.high, 0): + let (item, idx) = items[i] + if i < items.high and items[i + 1].val > item: + currentRank = i + 1 + result[idx] = currentRank + +proc denseRanking(items: sink IndexedItems): seq[int] = + result = newSeq[int](items.len) + var currentRank = 1 + for i, (item, idx) in items: + if i > 0 and items[i - 1].val < item: + inc currentRank + result[idx] = currentRank + +proc rank*[T](items: openArray[T], strategy: TieStrategy = Standard): seq[int] = + var indexedItems = newSeq[tuple[val: T, idx: int]](items.len) + for idx, val in items: + indexedItems[idx] = (val, idx) + + indexedItems.sort() + + case strategy + of Standard: + standardRanking(indexedItems) + of Modified: + modifiedRanking(indexedItems) + of Dense: + denseRanking(indexedItems) + +when isMainModule: + import std/unittest + suite "Standard/modified/dense ranking": + test "standard ranking": + check [0, 4, 4, 5].rank(Standard) == [1, 2, 2, 4] + test "modified ranking": + check [0, 4, 4, 5].rank(Modified) == [1, 3, 3, 4] + test "dense ranking": + check [0, 4, 4, 5].rank(Dense) == [1, 2, 2, 3] diff --git a/challenge-010/archargelod/README b/challenge-010/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-010/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-010/archargelod/nim/ch_1.nim b/challenge-010/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..ca4c236d12 --- /dev/null +++ b/challenge-010/archargelod/nim/ch_1.nim @@ -0,0 +1,66 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/tables + +type RomanNumeral = string + +const + validRomanDigits = "IVXLCDM" + RomanToDec = { + "M": 1000, + "CM": 900, + "D": 500, + "CD": 400, + "C": 100, + "XC": 90, + "L": 50, + "XL": 40, + "X": 10, + "IX": 9, + "V": 5, + "IV": 4, + "I": 1 + }.toOrderedTable + +proc toRoman*(number: 1 .. 3999): RomanNumeral = + var number: int = number + while number > 0: + for roman, dec in RomanToDec: + if number >= dec: + number -= dec + result.add roman + break + +proc toDec*(roman: RomanNumeral): int = + if roman.len < 1: + raise newException(ValueError, "Invalid roman numeral") + var prev = int.high + for romanDigit in roman: + if romanDigit notin validRomanDigits: + raise newException(ValueError, "Invalid roman numeral") + let cur = RomanToDec[$romanDigit] + if cur > prev: + result -= prev * 2 + result += cur + prev = cur + + if result notin 0 .. 3999: + raise newException(ValueError, "Invalid roman numeral") + +when isMainModule: + import std/unittest + + const + TestNumber = 246 + Expected = "CCXLVI" + + suite "Roman numeral encode/decode": + test "246 should be CCXLVI": + check TestNumber.toRoman == Expected + test "number encoded then decoded equals itself": + check TestNumber.toRoman.toDec == TestNumber + test "roman numerals with invalid digits are invalid": + expect ValueError: + discard "Hello".toDec + test "roman numerals outside of range 1..3999 are invalid": + expect ValueError: + discard "MMMMMMM".toDec diff --git a/challenge-010/archargelod/nim/ch_2.nim b/challenge-010/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..e06717f39c --- /dev/null +++ b/challenge-010/archargelod/nim/ch_2.nim @@ -0,0 +1,71 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off + +proc jaroSimilarity*(s1, s2: string): float = + if min(s1.len, s2.len) < 1: raise newException(ValueError, "strings can't be empty") + let margin = int max(s1.len, s2.len) div 2 - 1 + var + matches = (newSeq[bool](s1.len), newSeq[bool](s2.len)) + m: int + t: float + + # number of matches in order + for i, c in s1: + var left = max(s2.low, i - margin) + let right = max(s2.low, min(s2.high, i + margin)) + var pos = s2[left .. right].find(c) + if pos == -1: continue + + while left+pos < s2.high and matches[1][left+pos]: + left = left + pos + 1 # shift search start past the previous find + pos = s2[left .. right].find(c) + + if left + pos > s2.high: + pos = -1 + + matches[0][i] = true + matches[1][left + pos] = true + inc m + + if m == 0: return 0 + + # count transpositions + var mInd2 = 0 + for mInd1, matched in matches[0]: + if not matched: continue + while not matches[1][mInd2]: + inc mInd2 + if s1[mInd1] != s2[mInd2]: + t += 1 + inc mInd2 + t /= 2 + + 1/3 * (m/s1.len + m/s2.len + (m.float - t)/m.float) + +proc jaroWinklerSimilarity*(s1, s2: string, p = 0.1): float = + if min(s1.len, s2.len) < 1: raise newException(ValueError, "strings can't be empty") + if p < 0 or p > 0.25: + raiseAssert("P should not exceed 0.25, as similarity could become > 1") + + # common prefix + var l: int + for i, c in s1[0 .. min(s1.high, 3)]: + if i > s2.high or s2[i] != c: + break + l = i + 1 + + let simj = jaroSimilarity(s1, s2) + simj + l.float * p * (1 - simj) + +proc jaroWinklerDistance*(s1, s2: string, p = 0.1): float = + if min(s1.len, s2.len) < 1: raise newException(ValueError, "strings can't be empty") + 1 - jaroWinklerSimilarity(s1, s2, p) + +when isMainModule: + import std/[unittest] + + proc approxEqual(a, b, tolerance: float): bool = + return abs(a - b) <= tolerance + + suite "Jaro-Winkler string distance": + test "similarity of 'faremviel' and 'farmville' is around 0.88": + check approxEqual(jaroSimilarity("faremviel", "farmville"), 0.88, 0.01) diff --git a/challenge-011/archargelod/README b/challenge-011/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-011/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-011/archargelod/nim/ch_1.nim b/challenge-011/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..b7514dd648 --- /dev/null +++ b/challenge-011/archargelod/nim/ch_1.nim @@ -0,0 +1,24 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/math + +const + CelsiusFreezing = 0 + CelsiusBoiling = 100 + FahrenheitFreezing = 32 + FahrenheitBoiling = 212 + +proc toFahrenheit(t: int): int = + let slope = + (FahrenheitBoiling - FahrenheitFreezing) / (CelsiusBoiling - CelsiusFreezing) + int round(FahrenheitFreezing.float + slope * float(t - CelsiusFreezing)) + +proc equalPoint(): int = + while result.toFahrenheit() > result: + dec result + +when isMainModule: + import std/unittest + |