Merge pull request #9677 from Archargelod/nim-archar-w254

weeks 14-26, 258 in Nim

3 files changed, 100 insertions, 0 deletions

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