From 3a120930c5773eba4641d49e02ea5e58c12dcfcb Mon Sep 17 00:00:00 2001 From: Archargelod Date: Sat, 23 Mar 2024 13:33:35 +0800 Subject: weeks 41-47, 260, 261 in Nim --- challenge-041/archargelod/README | 1 + challenge-041/archargelod/nim/ch_1.nim | 45 +++++++++++++++++++ challenge-041/archargelod/nim/ch_2.nim | 21 +++++++++ challenge-042/archargelod/README | 1 + challenge-042/archargelod/nim/ch_1.nim | 14 ++++++ challenge-042/archargelod/nim/ch_2.nim | 31 +++++++++++++ challenge-043/archargelod/README | 1 + challenge-043/archargelod/nim/ch_1.nim | 51 +++++++++++++++++++++ challenge-043/archargelod/nim/ch_2.nim | 51 +++++++++++++++++++++ challenge-044/archargelod/README | 1 + challenge-044/archargelod/nim/ch_1.nim | 71 +++++++++++++++++++++++++++++ challenge-044/archargelod/nim/ch_2.nim | 41 +++++++++++++++++ challenge-045/archargelod/README | 1 + challenge-045/archargelod/nim/ch_1.nim | 26 +++++++++++ challenge-045/archargelod/nim/ch_2.nim | 18 ++++++++ challenge-046/archargelod/README | 1 + challenge-046/archargelod/nim/ch_1.nim | 38 ++++++++++++++++ challenge-046/archargelod/nim/ch_2.nim | 38 ++++++++++++++++ challenge-047/archargelod/README | 1 + challenge-047/archargelod/nim/ch_1.nim | 81 ++++++++++++++++++++++++++++++++++ challenge-047/archargelod/nim/ch_2.nim | 26 +++++++++++ challenge-260/archargelod/nim/ch_1.nim | 32 ++++++++++++++ challenge-260/archargelod/nim/ch_2.nim | 25 +++++++++++ challenge-261/archargelod/nim/ch_1.nim | 31 +++++++++++++ challenge-261/archargelod/nim/ch_2.nim | 30 +++++++++++++ 25 files changed, 677 insertions(+) create mode 100644 challenge-041/archargelod/README create mode 100755 challenge-041/archargelod/nim/ch_1.nim create mode 100755 challenge-041/archargelod/nim/ch_2.nim create mode 100644 challenge-042/archargelod/README create mode 100755 challenge-042/archargelod/nim/ch_1.nim create mode 100755 challenge-042/archargelod/nim/ch_2.nim create mode 100644 challenge-043/archargelod/README create mode 100755 challenge-043/archargelod/nim/ch_1.nim create mode 100755 challenge-043/archargelod/nim/ch_2.nim create mode 100644 challenge-044/archargelod/README create mode 100755 challenge-044/archargelod/nim/ch_1.nim create mode 100755 challenge-044/archargelod/nim/ch_2.nim create mode 100644 challenge-045/archargelod/README create mode 100755 challenge-045/archargelod/nim/ch_1.nim create mode 100755 challenge-045/archargelod/nim/ch_2.nim create mode 100644 challenge-046/archargelod/README create mode 100755 challenge-046/archargelod/nim/ch_1.nim create mode 100755 challenge-046/archargelod/nim/ch_2.nim create mode 100644 challenge-047/archargelod/README create mode 100755 challenge-047/archargelod/nim/ch_1.nim create mode 100755 challenge-047/archargelod/nim/ch_2.nim create mode 100755 challenge-260/archargelod/nim/ch_1.nim create mode 100755 challenge-260/archargelod/nim/ch_2.nim create mode 100755 challenge-261/archargelod/nim/ch_1.nim create mode 100755 challenge-261/archargelod/nim/ch_2.nim diff --git a/challenge-041/archargelod/README b/challenge-041/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-041/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-041/archargelod/nim/ch_1.nim b/challenge-041/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..67fe9c9acc --- /dev/null +++ b/challenge-041/archargelod/nim/ch_1.nim @@ -0,0 +1,45 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off + +proc primeSieve(max: int): seq[int] = + var sieve = newSeq[bool](max+1) + sieve[0..1] = [true, true] + + for p in 2..sieve.high: + if sieve[p]: continue + for m in countup(p+p, sieve.high, p): + sieve[m] = true + + for i in 2..sieve.high: + if not sieve[i]: result.add i + +proc primeFactors(number: int): seq[int] = + var number = number + + let primes = primeSieve(100) + var facInd = 0 + + while number > 1: + while number mod primes[facInd] != 0: + inc facInd + number = number div primes[facInd] + result.add primes[facInd] + +proc attractiveNumbersBetween1and50: seq[int] = + let primes = primeSieve(100) + for n in 2..<50: + if primeFactors(n).len in primes: + result.add n + +when isMainModule: + import std/unittest + + const + Expected = [ + 4, 6, 8, 9, 10, 12, 14, 15, 18, 20, 21, 22, 25, 26, 27, 28, 30, 32, 33, + 34, 35, 38, 39, 42, 44, 45, 46, 48, 49 + ] + + suite "Attractive Numbers": + test "Numbers with a prime number of prime divisors between 1 and 50": + check attractiveNumbersBetween1and50() == Expected + diff --git a/challenge-041/archargelod/nim/ch_2.nim b/challenge-041/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..8777e9cd30 --- /dev/null +++ b/challenge-041/archargelod/nim/ch_2.nim @@ -0,0 +1,21 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off + +proc leonardoNumbers(n: int): seq[int] = + result = newSeq[int](n) + result[0..1] = [1, 1] + for i in 2.. 0: + var rem = 0 + (dec, rem) = divmod(dec, base) + result.insert($rem, 0) + +when isMainModule: + for i in 0..50: + echo "Decimal ", i, " = Octal ", i.toBase(8) + diff --git a/challenge-042/archargelod/nim/ch_2.nim b/challenge-042/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..57a722e222 --- /dev/null +++ b/challenge-042/archargelod/nim/ch_2.nim @@ -0,0 +1,31 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/random + +const + OpeningBracket = '(' + ClosingBracket = ')' + Brackets = [OpeningBracket, ClosingBracket] + +proc genRandomBrackets: string = + result = newString(rand(1..60) * 2) + for c in result.mItems: + c = Brackets[rand(Brackets.low..Brackets.high)] + +proc isBalanced(brackets: string): bool = + var stack: seq[char] + for c in brackets: + if c == OpeningBracket: + stack.add ClosingBracket + else: + if stack.len < 1: return false + discard stack.pop() + stack.len == 0 + +when isMainModule: + randomize() + + while true: + let brackets = genRandomBrackets() + if brackets.isBalanced(): + echo brackets, " is balanced!" + break diff --git a/challenge-043/archargelod/README b/challenge-043/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-043/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-043/archargelod/nim/ch_1.nim b/challenge-043/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..c8849dc17c --- /dev/null +++ b/challenge-043/archargelod/nim/ch_1.nim @@ -0,0 +1,51 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[sequtils, options, algorithm, sugar] + +type + Number = ref object + value: Option[int] + Ring = object + color: string + numbers: seq[Number] + +proc sum(s: Ring): int = + for n in s.numbers: + if n.value.isSome(): + result += n.value.get() + +proc main = + var numbers = [ + Number(value: some(9)), + Number(value: none(int)), + Number(value: some(5)), + Number(value: none(int)), + Number(value: none(int)), + Number(value: none(int)), + Number(value: some(7)), + Number(value: none(int)), + Number(value: some(8)), + ] + + var rings = [ + Ring(color: "red", numbers: @[numbers[0], numbers[1]]), + Ring(color: "green", numbers: @[numbers[1], numbers[2], numbers[3]]), + Ring(color: "black", numbers: @[numbers[3], numbers[4], numbers[5]]), + Ring(color: "yellow", numbers: @[numbers[5], numbers[6], numbers[7]]), + Ring(color: "purple", numbers: @[numbers[7], numbers[8]]), + ] + + var empty = collect: + for n in numbers: + if n.value.isNone(): n + + var givenNums = [1,2,3,4,6] + while not rings.allIt(it.sum() == 11): + for i, n in givenNums: + empty[i].value = some(n) + givenNums.nextPermutation() + + for ring in rings: + echo ring.color, ": ", ring.numbers.mapIt(it.value.get()) + +when isMainModule: + main() diff --git a/challenge-043/archargelod/nim/ch_2.nim b/challenge-043/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..bac6cbe9ba --- /dev/null +++ b/challenge-043/archargelod/nim/ch_2.nim @@ -0,0 +1,51 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +## Anyone could implement a formula, so here is a +## bruteforce approach of trying every combination of digits +## which sum is equal to the base and checking if number is self-descriptive. +## It's very slow past base 12. +import std/[sequtils, strutils, bitops, math, sugar] + +type Number = object + data: seq[int] + +proc `$`(number: Number): string = + const digits = @"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" + var digitSeq: seq[char] + for i in countDown(number.data.high, 0): + digitSeq.insert(digits[number.data[i]]) + digitSeq.join() + +iterator combinations(fullSet: openarray[int], n: int): seq[int] = + for i in 1..2^fullSet.len: + if i.countSetBits() != n: continue + + var buf = newSeqOfCap[int](n) + for j in 0..fullSet.high: + if i.testBit(j): + buf.add fullSet[j] + + yield buf + +iterator groupCombinations(n, m: int): seq[int] = + for c in combinations(toSeq(0..= base): continue + let number = Number(data: comb) + if number.isSelfDescriptive(): + echo base, ": ", number + break diff --git a/challenge-044/archargelod/README b/challenge-044/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-044/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-044/archargelod/nim/ch_1.nim b/challenge-044/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..24661fe41f --- /dev/null +++ b/challenge-044/archargelod/nim/ch_1.nim @@ -0,0 +1,71 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[strutils, parseutils, math] + +type + Sign = enum + None + Plus + Minus + +proc evaluate(s: string): int = + var index = 0 + let length = s.skipWhile(Digits, index) + result = parseInt(s[0.. 0: + result.insert $(n mod 3) + n = n div 3 + + result = result.align(digits, '0') + +iterator allSignPermutations(n: int): seq[Sign] = + var buf = newSeqOfCap[Sign](n) + for i in 1..<3^n: + for digit in i.toTrinary(n): + buf.add ( + case digit + of '0': None + of '1': Plus + of '2': Minus + else: + raiseAssert("Invalid digit.") + ) + yield buf + buf.setLen(0) + +when isMainModule: + const Expression = "123456789" + for signs in allSignPermutations(Expression.len - 1): + var newExpression = Expression + var shift = 1 + for i, sign in signs: + case sign + of None: + discard + of Plus: + newExpression.insert("+", i + shift) + inc shift + of Minus: + newExpression.insert("-", i + shift) + inc shift + + if evaluate(newExpression) == 100: + echo newExpression, " == 100" + break diff --git a/challenge-044/archargelod/nim/ch_2.nim b/challenge-044/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..c15b6b50ff --- /dev/null +++ b/challenge-044/archargelod/nim/ch_2.nim @@ -0,0 +1,41 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +## The rules: +## With every move you can either double or add 1. +## Get 200 from 1 with the smallest number of moves +## Solution: +## Reverse the problem: get from 200 to 1. If value is even - divide by 2, +## else subtract 1. + +type Move = enum + Div2 = "/ 2" + Sub1 = "- 1" + Mul2 = "* 2" + Add1 = "+ 1" + +proc minimumStepsTo1(start: int): seq[Move] = + var value = start + + while value > 1: + if value mod 2 == 0: + value = value div 2 + result.add Div2 + else: + dec value + result.add Sub1 + +when isMainModule: + import std/[unittest, sequtils, algorithm] + + const + Test = 200 + Expected = [ + [Div2, Div2, Div2, Sub1, Div2, Div2, Div2, Sub1, Div2], + [Mul2, Add1, Mul2, Mul2, Mul2, Add1, Mul2, Mul2, Mul2], + ] + + suite "Make it $200": + test "steps 200 -> 1": + check minimumStepsTo1(Test) == Expected[0] + test "steps 1 -> 200": + let reverse = minimumStepsTo1(Test).mapIt(if it == Div2: Mul2 else: Add1).reversed() + check reverse == Expected[1] diff --git a/challenge-045/archargelod/README b/challenge-045/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-045/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-045/archargelod/nim/ch_1.nim b/challenge-045/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..40c642133f --- /dev/null +++ b/challenge-045/archargelod/nim/ch_1.nim @@ -0,0 +1,26 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[strutils, sequtils] + +proc squareCoded(input: string): string = + const Columns = 8 + let input = input.filterIt(it in Letters).toLower() + + for x in 0.. / + P x w l b 3 k \ + 2 e 3 5 R 8 y u + < ! r ^ ( ) k 0""".dedent() + ] + + Expected = ["Hello", "PerlRaku"] + + suite "Cryptic Message": + test "message: Hello": + check decrypt(Test[0].splitLines()) == Expected[0] + test "message: PerlRaku": + check decrypt(Test[1].splitLines()) == Expected[1] diff --git a/challenge-046/archargelod/nim/ch_2.nim b/challenge-046/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..f754d66f96 --- /dev/null +++ b/challenge-046/archargelod/nim/ch_2.nim @@ -0,0 +1,38 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/math + +proc main = + ## open room numbers are all perfect squares + ## because room number stays open if it has odd number of positive divisors + ## and that is only true for perfect square numbers + for i in 1..500: + if (let root = sqrt(float i); root) == trunc(root): + echo i, " is open" + + +type + DoorState = enum + Open + Closed + +proc main2 = + ## bruteforce approach + var rooms: array[1..500, DoorState] + + template toggle(state: var DoorState) = + case state + of Open: + state = Closed + of Closed: + state = Open + + for i in 2..500: + for j in countUp(i, rooms.high, i): + rooms[j].toggle() + + for i, room in rooms: + if room == Open: echo i, " is open" + +when isMainModule: + main() + #main2() diff --git a/challenge-047/archargelod/README b/challenge-047/archargelod/README new file mode 100644 index 0000000000..6cd57e1074 --- /dev/null +++ b/challenge-047/archargelod/README @@ -0,0 +1 @@ +Solution by archargelod diff --git a/challenge-047/archargelod/nim/ch_1.nim b/challenge-047/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..4108cc100d --- /dev/null +++ b/challenge-047/archargelod/nim/ch_1.nim @@ -0,0 +1,81 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[strutils, parseutils] + +type RomanDigit = enum + I = 1 + V = 5 + X = 10 + L = 50 + C = 100 + D = 500 + M = 1000 + +const + Squish = { + "VIIII": "IX", + "LXXXX": "XC", + "DCCCC": "CM", + "IIII": "IV", + "XXXX": "XL", + "CCCC": "CD", + } + +const RomanDescending = [M, D, C, L, X, V, I] + +proc toRoman(dec: int): string = + var dec = dec + while dec > 0: + for roman in RomanDescending: + if dec >= roman.ord: + dec -= roman.ord + result &= $roman + break + + for (sub, by) in Squish: + result = result.replace(sub, by) + +proc toDec(roman: string): int = + var prev = M + for c in roman: + let r = parseEnum[RomanDigit]($c) + result += r.ord + if prev < r: + result -= prev.ord * 2 + prev = r + +proc romanCalculator(input: string): string = + let tmp = input.splitWhitespace() + assert tmp.len == 3 + let (arg1, op, arg2) = (tmp[0], tmp[1], tmp[2]) + + toRoman( + case op + of "+": toDec(arg1) + toDec(arg2) + of "-": toDec(arg1) - toDec(arg2) + of "*": toDec(arg1) * toDec(arg2) + else: + raiseAssert("Invalid expression") + ) + +when isMainModule: + import std/unittest + + const + Test = [ + "XXXVI + X", + "DIV - X", + "VII * X", + ] + Expected = [ + "XLVI", + "CDXCIV", + "LXX", + ] + + suite "Show multiple arrays content": + test "Addition": + check romanCalculator(Test[0]) == Expected[0] + test "Subtraction": + check romanCalculator(Test[1]) == Expected[1] + test "Multiplication": + check romanCalculator(Test[2]) == Expected[2] diff --git a/challenge-047/archargelod/nim/ch_2.nim b/challenge-047/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..9f02ecc75c --- /dev/null +++ b/challenge-047/archargelod/nim/ch_2.nim @@ -0,0 +1,26 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/math + +proc isGapful(n: int): bool = + let last = n mod 10 + let first = int(n / (10 ^ int log10(float n))) + n mod (first * 10 + last) == 0 + +proc firstGapfulNumbers(n: int): seq[int] = + var number = 100 + while result.len < n: + if number.isGapful(): + result.add number + inc number + +when isMainModule: + import std/unittest + + const + Test = 20 + Expected = [100, 105, 108, 110, 120, 121, 130, 132, 135, 140, 143, 150, 154, + 160, 165, 170, 176, 180, 187, 190] + + suite "Gapful Number": + test "first 20": + check firstGapfulNumbers(Test) == Expected diff --git a/challenge-260/archargelod/nim/ch_1.nim b/challenge-260/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..2525d8dbcf --- /dev/null +++ b/challenge-260/archargelod/nim/ch_1.nim @@ -0,0 +1,32 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/sequtils + +proc allOccurencesCountsUnique(numbers: seq[int]): bool = + var counts: seq[int] + var uniq: seq[int] + for n in numbers: + if n in uniq: continue + let cnt = numbers.count(n) + if cnt in counts: return false + counts.add cnt + uniq.add n + true + +when isMainModule: + import std/unittest + + const + Test = [ + @[1,2,2,1,1,3], + @[1,2,3], + @[-2,0,1,-2,1,1,0,1,-2,9] + ] + Expected = [true, false, true] + + suite "Unique Occurrences": + test "Example 1": + check allOccurencesCountsUnique(Test[0]) == Expected[0] + test "Example 2": + check allOccurencesCountsUnique(Test[1]) == Expected[1] + test "Example 3": + check allOccurencesCountsUnique(Test[2]) == Expected[2] diff --git a/challenge-260/archargelod/nim/ch_2.nim b/challenge-260/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..23f0c21eba --- /dev/null +++ b/challenge-260/archargelod/nim/ch_2.nim @@ -0,0 +1,25 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/[algorithm] + +proc dictionaryRank(word: string): int = + var letters = word.sorted() + + result = 1 + while letters != word: + doAssert nextPermutation(letters) + inc result + +when isMainModule: + import std/unittest + + const + Test = ["CAT", "GOOGLE", "SECRET"] + Expected = [3, 88, 255] + + suite "Dictionary Rank": + test "Example 1": + check dictionaryRank(Test[0]) == Expected[0] + test "Example 2": + check dictionaryRank(Test[1]) == Expected[1] + test "Example 3": + check dictionaryRank(Test[2]) == Expected[2] diff --git a/challenge-261/archargelod/nim/ch_1.nim b/challenge-261/archargelod/nim/ch_1.nim new file mode 100755 index 0000000000..f73a60dca6 --- /dev/null +++ b/challenge-261/archargelod/nim/ch_1.nim @@ -0,0 +1,31 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off +import std/sequtils + +proc diffElementDigitSums(numbers: openArray[int]): int = + for num in numbers: + if num < 10: continue + let digitSum = ($num).mapIt(it.ord - '0'.ord).foldl(a+b) + result += num - digitSum + + +when isMainModule: + import std/unittest + + const + Test = [ + @[1,2,3,45], + @[1,12,3], + @[1,2,3,4], + @[236, 416, 336, 350], + ] + Expected = [36, 9, 0, 1296] + + suite "Element Digit Sum": + test "Example 1": + check diffElementDigitSums(Test[0]) == Expected[0] + test "Example 2": + check diffElementDigitSums(Test[1]) == Expected[1] + test "Example 3": + check diffElementDigitSums(Test[2]) == Expected[2] + test "Example 4": + check diffElementDigitSums(Test[3]) == Expected[3] diff --git a/challenge-261/archargelod/nim/ch_2.nim b/challenge-261/archargelod/nim/ch_2.nim new file mode 100755 index 0000000000..36d8badb5d --- /dev/null +++ b/challenge-261/archargelod/nim/ch_2.nim @@ -0,0 +1,30 @@ +#!/usr/bin/env -S nim r -d:release --verbosity:0 --hints:off + +proc searchThenDoubleRepeat(numbers: openarray[int], value: int): int = + result = value + while true: + block lookingForValue: + for num in numbers: + if num == result: + result *= 2 + break lookingForValue + return + +when isMainModule: + import std/unittest + + const + Test: array[3, tuple[arr: seq[int], value: int]] = [ + (@[5,3,6,1,12], 3), + (@[1,2,4,3], 1), + (@[5,6,7], 2), + ] + Expected = [24, 8, 2] + + suite "Multiply by Two": + test "Example 1": + check Test[0].arr.searchThenDoubleRepeat(Test[0].value) == Expected[0] + test "Example 2": + check Test[1].arr.searchThenDoubleRepeat(Test[1].value) == Expected[1] + test "Example 3": + check Test[2].arr.searchThenDoubleRepeat(Test[2].value) == Expected[2] -- cgit