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.
New iteration! Is Motoko a good Programming Language
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;
};
};
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
};
};
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);
};
};
};
};
};
};
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 
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.
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;
};
};
New Article Sudoku Solver
Here is the code, I’ll provide both implementations as shown previously
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 solveSudoku(board: Board) : async ?Board {
let size = 9;
var rows = Array.init<Nat32>(size, 0);
var cols = Array.init<Nat32>(size, 0);
var boxes = Array.init<Nat32>(size, 0);
// Time to play "Spot the Number" across the board
for (i in Iter.range(0, size - 1)) {
for (j in Iter.range(0, size - 1)) {
switch (board[i][j]) {
case null { /* Empty cell, nothing to see here, move along */ };
case (?value) {
let num = Nat32.fromNat(Nat8.toNat(value));
let bitMask = Nat32.bitshiftLeft(1, num - 1); // gives a unique bit representation, a mask of sorts
let boxIndex = (i / 3) * 3 + (j / 3); // Magic formula to find which 3x3 box we're in
// Record the presence of the number in the corresponding 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);
};
};
};
};
// Create a mutable board
let mutableBoard = Array.tabulateVar<[var Cell]>(size, func(i) {
Array.thaw<Cell>(board[i])
});
if (solve(mutableBoard, rows, cols, boxes, 0, 0)) {
// Let's freeze this bad boy back up
return ?Array.tabulate<Row>(size, func(i) {
Array.freeze<Cell>(mutableBoard[i])
});
} else {
return null; // No solution :-(
};
};
func solve(board: [var [var Cell]], rows: [var Nat32], cols: [var Nat32], boxes: [var Nat32], row: Nat, col: Nat) : Bool {
//we've won. we populated all 0-8 rows
if (row == 9) {
return true;
};
// Calculate next cell
let nextRow = if (col == 8) { row + 1 } else { row };
let nextCol = (col + 1) % 9; // Making sure we don't fall off the edge of the board
switch (board[row][col]) {
case null {
// Empty cell! Time to play "Guess the Number" (now with backtracking!)
for (num in Iter.range(1, 9)) {
let bitMask = Nat32.bitshiftLeft(1, Nat32.fromNat(num) - 1);
let boxIndex = (row / 3) * 3 + (col / 3); // magic formula strikes again
// Check if we can place the number here
if (Nat32.bitand(rows[row], bitMask) == 0 and
Nat32.bitand(cols[col], bitMask) == 0 and
Nat32.bitand(boxes[boxIndex], bitMask) == 0) {
// Record the presence of the number in the corresponding row, column, and box(again)
board[row][col] := ?Nat8.fromNat(num);
rows[row] := Nat32.bitor(rows[row], bitMask);
cols[col] := Nat32.bitor(cols[col], bitMask);
boxes[boxIndex] := Nat32.bitor(boxes[boxIndex], bitMask);
// Recursive. call to solve the next row and col
if (solve(board, rows, cols, boxes, nextRow, nextCol)) {
return true; // We found a solution!
};
// That didn't work. Time to erase our mistakes
board[row][col] := null;
rows[row] := Nat32.bitand(rows[row], ^bitMask);
cols[col] := Nat32.bitand(cols[col], ^bitMask);
boxes[boxIndex] := Nat32.bitand(boxes[boxIndex], ^bitMask);
};
};
return false; // We've tried, nothing and we're all out of ideas
};
case _ {
// This cell is already filled. Let's move on and pretend we did something useful here.
return solve(board, rows, cols, boxes, nextRow, nextCol);
};
};
};
};
Using additional buffers + helper functions
import Array "mo:base/Array";
import Buffer "mo:base/Buffer";
import Iter "mo:base/Iter";
import Nat "mo:base/Nat";
import Nat8 "mo:base/Nat8";
actor {
type Cell = ?Nat8;
type Row = [Cell];
type Board = [Row];
func hasDuplicates(cells: Row): Bool {
var seen = Array.init<Bool>(10, false);
for (cell in cells.vals()) {
switch (cell) {
case (?n) {
if (seen[Nat8.toNat(n)]) return true;
seen[Nat8.toNat(n)] := true;
};
case (null) {};
}
};
return false;
};
func isValidBoard(board: Board): Bool {
// Check rows
for (row in board.vals()) {
if (hasDuplicates(row)) {
return false;
};
};
// Check columns
for (colIdx in Iter.range(0, board[0].size() - 1)) {
let col = Array.tabulate(board.size(), func(rowIdx: Nat): Cell {
board[rowIdx][colIdx]
});
if (hasDuplicates(col)) {
return false;
}
};
// Check each 3x3 box for duplicates
for (boxRow in Iter.range(0, 2)) {
for (boxCol in Iter.range(0, 2)) {
let boxBuffer = Buffer.Buffer<Cell>(9);
for (rowIdx in Iter.range(boxRow * 3, boxRow * 3 + 2)) {
for (colIdx in Iter.range(boxCol * 3, boxCol * 3 + 2)) {
boxBuffer.add(board[rowIdx][colIdx]);
}
};
let box = Buffer.toArray(boxBuffer);
if (hasDuplicates(box)) {
return false;
};
};
};
return true;
};
func findEmptyCell(board: Board): ?(Nat, Nat) {
for (rowIdx in Iter.range(0, board.size() - 1)) {
for (colIdx in Iter.range(0, board[rowIdx].size() - 1)) {
if (board[rowIdx][colIdx] == null) {
return ?(rowIdx, colIdx);
}
}
};
return null;
};
func solveSudoku(board: Board): ?Board {
switch (findEmptyCell(board)) {
case (null) {
return ?board;
};
case (?coords) {
let (i, j) = coords;
for (num in Iter.range(1, 9)) {
let candidate = ?Nat8.fromNat(num);
let newBoard = Array.tabulate<Row>(board.size(), func(rowIdx: Nat): Row {
if (rowIdx == i) {
Array.tabulate<Cell>(board[rowIdx].size(), func(colIdx: Nat): Cell {
if (colIdx == j) {
candidate;
} else {
board[rowIdx][colIdx];
}
});
} else {
board[rowIdx];
}
});
if (isValidBoard(newBoard)) {
switch (solveSudoku(newBoard)) {
case (null) {};
case (?solvedBoard) { return ?solvedBoard; };
}
}
};
return null;
};
}
};
public func solve(board: Board): async ?Board {
return solveSudoku(board);
};
};
New Article Design Twitter
Code
import List "mo:base/List";
import TrieMap "mo:base/TrieMap";
import Int "mo:base/Int";
import Nat "mo:base/Nat";
import HashMap "mo:base/HashMap";
actor Twitter{
// Type aliases for clarity
type UserId = Nat;
type TweetId = Nat;
private var users = HashMap.HashMap<UserId, User>(10, Nat.equal, Int.hash);
private var tweets = List.nil<Tweet>();
class Tweet(userId: Int, tweetId:Int) {
public let id = tweetId;
public let author = userId;
};
class User(){
public var tweets = List.nil<(Tweet)>();
public let following = TrieMap.TrieMap<UserId, Bool>(Int.equal, Int.hash);
};
func getorCreateUser(uid:UserId): User {
switch(users.get(uid)) {
case(null) {
let newUser = User();
users.put(uid, newUser);
newUser;
};
case(?user) {user};
};
};
public func postTweet(uid: UserId, tweetId : TweetId): async (){
let user = getorCreateUser(uid);
//We are told to assume the tweet id input is unique
let tweet = Tweet(uid, tweetId);
user.tweets := List.push(tweet, user.tweets);
tweets := List.push(tweet, tweets);
};
public func getFeed(uid: UserId) : async [TweetId] {
let user = getorCreateUser(uid);
func isRelevantTweet(tweet: Tweet) : Bool {
tweet.author == uid or (switch (user.following.get(Int.abs(tweet.author))) {
case (?true) true;
case _ false;
})
};
// Filter relevant tweets and take the 10 most recent
let relevantTweets = List.filter(tweets, isRelevantTweet);
let recentTweets = List.take(relevantTweets, 10);
// Convert the list of tweets to an array of tweet IDs
List.toArray(List.map(recentTweets, func (tweet: Tweet) : TweetId { Int.abs(tweet.id) }))
};
public func follow(followerId: UserId, followeeId: UserId) : async (){
if (followerId != followeeId){
let follower = getorCreateUser(followerId);
follower.following.put(followeeId, true);
};
};
public func unfollow(followerId: UserId, followeeId: UserId): async (){
if(followerId != followeeId){
let follower = getorCreateUser(followerId);
follower.following.delete(followeeId);
}
};
};
Eliminating the possibility of following a user that does not exist yet.(No Ghost following)
import List "mo:base/List";
import TrieMap "mo:base/TrieMap";
import Int "mo:base/Int";
import Nat "mo:base/Nat";
import HashMap "mo:base/HashMap";
actor Twitter {
type UserId = Nat;
type TweetId = Nat;
private var users = HashMap.HashMap<UserId, User>(10, Nat.equal, Int.hash);
private var tweets = List.nil<Tweet>();
class Tweet(userId: UserId, tweetId: TweetId) {
public let id = tweetId;
public let author = userId;
};
class User() {
public var tweets = List.nil<Tweet>();
public let following = TrieMap.TrieMap<UserId, Bool>(Nat.equal, Int.hash);
};
func getUser(uid: UserId): ?User {
users.get(uid)
};
public func postTweet(uid: UserId, tweetId: TweetId): async () {
let user = switch (getUser(uid)) {
case (?existingUser) existingUser;
case (null) {
let newUser = User();
users.put(uid, newUser);
newUser;
};
};
let tweet = Tweet(uid, tweetId);
user.tweets := List.push(tweet, user.tweets);
tweets := List.push(tweet, tweets);
};
public func getFeed(uid: UserId): async [TweetId] {
switch (getUser(uid)) {
case (?user) {
func isRelevantTweet(tweet: Tweet): Bool {
tweet.author == uid or (switch (user.following.get(tweet.author)) {
case (?true) true;
case _ false;
})
};
let relevantTweets = List.filter(tweets, isRelevantTweet);
let recentTweets = List.take(relevantTweets, 10);
List.toArray(List.map(recentTweets, func (tweet: Tweet): TweetId { tweet.id }))
};
case (null) { [] };
};
};
public func follow(followerId: UserId, followeeId: UserId): async () {
if (followerId == followeeId) {
// Can't follow yourself
};
switch (getUser(followerId), getUser(followeeId)) {
case (?follower, ?_) {
// Both users exist
follower.following.put(followeeId, true);
};
case (_, _) {
// Either follower or followee (or both) don't exist
};
};
};
public func unfollow(followerId: UserId, followeeId: UserId): async () {
if (followerId == followeeId) {
// Can't unfollow yourself
};
switch (getUser(followerId)) {
case (?follower) {
follower.following.delete(followeeId);
};
case (null) {
//no one to unfollow
};
};
};
}
New Article Minimum size Subarray
Code
import Array "mo:base/Array";
import Nat "mo:base/Nat";
actor {
func minsubarray(arr : [var Nat], num : Nat) : Nat {
var sum = 0;
var left = 0;
var right = 0;
var minlength = arr.size() + 1;
label search while (left < arr.size()) {
if (right < arr.size() and sum < num) {
sum += arr[right];
right += 1;
} else if (sum >= num) {
minlength := Nat.min(minlength, right - left);
sum -= arr[left];
left += 1;
} else {
break search;
};
};
return if (minlength > arr.size()) 0 else minlength;
};
public func findminimumsubarray(arr: [Nat], target: Nat) : async Nat {
return minsubarray(Array.thaw<Nat>(arr), target);
};
};
New article Dynamic Programming in Motoko
Code
import Array "mo:base/Array";
import Nat "mo:base/Nat";
import Int "mo:base/Int";
import Iter "mo:base/Iter";
actor CoinMachine {
public func tellmehowmanycoins(coins: [Nat], t: Nat): async Int {
let dp = Array.tabulateVar<Nat>(t + 1, func(i) = if (i == 0) 0 else t + 1);
for (amount in Iter.range(1, t)) {
for (coin in coins.vals()) {
if (coin <= amount) {
let remainder = Int.abs(amount - coin);
dp[amount] := Nat.min(dp[amount], dp[remainder] + 1);
};
};
};
let result = dp[t];
if (result > t) {
return -1; // It's not possible to make up the amount
} else {
return Int.abs(result);
};
};
};