Weeks 5-13, 257 in Nim

3 files changed, 138 insertions, 0 deletions

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)