I solved 100 LeetCode Problems using Motoko: Here's what I learned

Hello fellow IC enthusiasts,

I have decided to write a series about solving leetcode problems in motoko on Medium

You can find the first Installment here: Link to First article

I will use this as a thread to link to all the iterations i will produce!

Please share your thoughts after checking out the article.

13 Likes

New iteration! Is Motoko a good Programming Language

4 Likes

New Article Problem 12, Integer to roman

Here’s the code for anyone interested

import Text "mo:base/Text";
import Iter "mo:base/Iter";

actor {
    public func intToRoman(num: Nat): async Text {
        let values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
        let symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];

        var result = "";
        var n = num;

        for (i in Iter.range(0, values.size() - 1)) {
            while (n >= values[i]) {
                result #= symbols[i];
                n -= values[i];
            };
        };
        return result;
    };
};
5 Likes

New Article Problem 13 Roman to Int

Here’s the code

import Text "mo:base/Text";
import Array "mo:base/Array";
import Iter "mo:base/Iter";

actor {
    public func romanToInt(s: Text) : async ?Int {
        let chars = Text.toArray(s);
        var result = 0;
        var prevValue = 0;
        var repeatCount = 0;
        var lastChar : Char = ' ';
        
        for (i in Iter.fromArray(Array.reverse(chars))) {
            let currentValue = switch (i) {
                case 'I' 1;
                case 'V' 5;
                case 'X' 10;
                case 'L' 50;
                case 'C' 100;
                case 'D' 500;
                case 'M' 1000;
                case _ return null; // Invalid character
            };
            if (i == lastChar) {
                repeatCount += 1;
                if (repeatCount > 3 or (i != 'I' and i != 'X' and i != 'C' and i != 'M')) {
                    return null; // Invalid repetition
                }
            } else {
                repeatCount := 1;
            };
            if (prevValue > currentValue) {
                switch (currentValue, prevValue) {
                    case (1, 5 or 10) {}; // IV or IX
                    case (10, 50 or 100) {}; // XL or XC
                    case (100, 500 or 1000) {}; // CD or CM
                    case _ return null; // Invalid subtractive combination
                };
            };
            if (currentValue >= prevValue) {
                result += currentValue;
            } else {
                result -= currentValue;
            };  
            prevValue := currentValue;
            lastChar := i;
        };
        ?result
    };
};
2 Likes

New Article Problem 17 Combinations of a Keypad

Here’s the code

import Text "mo:base/Text";
import Buffer "mo:base/Buffer";
import HashMap "mo:base/HashMap";
import Nat "mo:base/Nat";
import Int "mo:base/Int";
import Char "mo:base/Char";

actor {
  let keypad : HashMap.HashMap<Nat, [Char]> = HashMap.HashMap(10, Nat.equal, Int.hash);

  public func initialize() : async () {
    keypad.put(2, ['a', 'b', 'c']);
    keypad.put(3, ['d', 'e', 'f']);
    keypad.put(4, ['g', 'h', 'i']);
    keypad.put(5, ['j', 'k', 'l']);
    keypad.put(6, ['m', 'n', 'o']);
    keypad.put(7, ['p', 'q', 'r', 's']);
    keypad.put(8, ['t', 'u', 'v']);
    keypad.put(9, ['w', 'x', 'y', 'z']);
  };

  public func findKeyPadCombinations(digits : Text) : async [Text] {
    if (Text.size(digits) == 0) {
      return [];
    };
    let digitArray = Text.toArray(digits);
    let initialBuffer = Buffer.Buffer<Text>(1);
    initialBuffer.add("");
    let combinations = getCombinations(digitArray, 0, initialBuffer);
    return Buffer.toArray(combinations);
  };

  func getCombinations(digits : [Char], index : Nat, combinations : Buffer.Buffer<Text>) : Buffer.Buffer<Text> {
    if (index == digits.size()) {
      return combinations;
    };

    let digit = Nat.fromText(Text.fromChar(digits[index]));
    switch (digit) {
      case (null) {
        return getCombinations(digits, index + 1, combinations);
      };
      case (?d) {
        switch (keypad.get(d)) {
          case (null) {
            return getCombinations(digits, index + 1, combinations);
          };
          case (?mapping) {
            let newCombinations = Buffer.Buffer<Text>(combinations.size() * mapping.size());
            for (c in combinations.vals()) {
              for (m in mapping.vals()) {
                newCombinations.add(Text.concat(c, Text.fromChar(m)));
              };
            };
            return getCombinations(digits, index + 1, newCombinations);
          };
        };
      };
    };
  };
};
3 Likes

This series will definitely have a high success rate in attracting developers with little experience.

I wonder how languages like Python or Lua would rank given your criteria :smile: :partying_face:

1 Like

Python is my favorite language as I find the syntax to be quite relaxed and I find it easy to grasp. I am waiting to see what kybra looks like in production. I managed to create my own language using python, with all the buzzwords. It’s a blockchain smart contract language that uses AI to interpret the AST(a truly dreadful and UNSAFE concept). It was essentially a fusion of Solidity and Motoko concepts +AI, it’s an awful language, but I had a fun making it, thanks to the libraries that allowed me to explore my ideas.

You can check it out if you’re into terrible programming languages. I’m not very familiar with Lua but I know it has 22 keywords. So i’m guessing the syntax is either very clean or an absolute nightmare.

1 Like

New Article Problem 36 Valid Sudoku

Here’s the code. I will include 2 separate implementations as some might not be familiar with bitwise operations, the second example uses extra buffers which makes it less efficient with space but it achieves the same time complexity.

Using Bitwise operations

import Array "mo:base/Array";
import Nat32 "mo:base/Nat32";
import Nat8 "mo:base/Nat8";
import Iter "mo:base/Iter";

actor {
    type Cell = ?Nat8;
    type Row = [Cell];
    type Board = [Row];

    public func validBoardCheck(board: Board) : async Bool {
        let size = 9;
        var rows = Array.init<Nat32>(size, 0);
        var cols = Array.init<Nat32>(size, 0);
        var boxes = Array.init<Nat32>(size, 0);

        for (i in Iter.range(0, size - 1)) {
            for (j in Iter.range(0, size - 1)) {
                switch (board[i][j]) {
                    case null { /* Empty cell, skip */ };
                    case (?value) {
                        if (value < 1 or value > 9) {
                            return false; // Invalid value
                        };

                        let num = Nat32.fromNat(Nat8.toNat(value));
                        let bitMask = Nat32.bitshiftLeft(1, num - 1);

                        let boxIndex = (i / 3) * 3 + (j / 3);

                        // Check if the number is already in row, column, or box
                        if (Nat32.bitand(rows[i], bitMask) != 0 or
                            Nat32.bitand(cols[j], bitMask) != 0 or
                            Nat32.bitand(boxes[boxIndex], bitMask) != 0) {
                            return false; // Duplicate found
                        };
                        // Mark the number as seen in row, column, and box
                        rows[i] := Nat32.bitor(rows[i], bitMask);
                        cols[j] := Nat32.bitor(cols[j], bitMask);
                        boxes[boxIndex] := Nat32.bitor(boxes[boxIndex], bitMask);
                    };
                };
            };
        };
        return true; // Valid Sudoku board
    };
};

Using additional buffers + helper function

import Array "mo:base/Array";
import Iter "mo:base/Iter";
import Nat8 "mo:base/Nat8";
import Buffer "mo:base/Buffer";

actor {
    type Cell = ?Nat8;
    type Row = [Cell];
    type Board = [Row];

    func isValidValue(n: Nat8): Bool {
        n >= 1 and n <= 9
    };

    func hasDuplicates(cells: [Nat8]): Bool {
        var seen = Array.init<Bool>(10, false);
        for (n in cells.vals()) {
            if (seen[Nat8.toNat(n)]) return true;
            seen[Nat8.toNat(n)] := true;
        };
        return false;
    };

    public func validBoardCheck(board: Board): async Bool {
        // Check if the board has exactly 9 rows of 9 cells each
        if (board.size() != 9) {
            return false;
        };
        
        for (row in board.vals()) {
            if (row.size() != 9) {
                return false;
            };
        };

        // Buffer to collect filled cells for each row, column, and box
        var rows = Array.tabulate<Buffer.Buffer<Nat8>>(9, func(_) { Buffer.Buffer<Nat8>(9) });
        var cols = Array.tabulate<Buffer.Buffer<Nat8>>(9, func(_) { Buffer.Buffer<Nat8>(9) });
        var boxes = Array.tabulate<Buffer.Buffer<Nat8>>(9, func(_) { Buffer.Buffer<Nat8>(9) });

        for (i in Iter.range(0, 8)) {
            for (j in Iter.range(0, 8)) {
                switch (board[i][j]) {
                    case (?n) {
                        if (not isValidValue(n)) return false;
                        rows[i].add(n);
                        cols[j].add(n);
                        let boxIndex = (i / 3) * 3 + (j / 3); //0-8
                        boxes[boxIndex].add(n);
                    };
                    case null {};
                };
            };
        };

        // Check for duplicates in rows, columns, and boxes
        for (i in Iter.range(0, 8)) {
            if (hasDuplicates(Buffer.toArray(rows[i]))) return false;
            if (hasDuplicates(Buffer.toArray(cols[i]))) return false;
            if (hasDuplicates(Buffer.toArray(boxes[i]))) return false;
        };

        return true;
    };
};
3 Likes