Coding Challenges

This is a compilation of my programming challenges along with some solutions in multiple languages. I try to provide a acceptable solution for each problem but I am not perfect, feel free to add better or your own solutions by creating a pull request. The challenges are not in any particular order, so feel free to jump around and try to solve them. All challenges are language agnostic, so you can solve them in any language you like.

These challenges are for you if:

• You are a beginner/intermediate programmer and want to practice.
• You want to experiment with a new language.

General Steps to Add a New Challenge

You can also add new challenges! However, please follow the format of the existing challenges. Contributing guidelines can be found in the CONTRIBUTING.md file.

• Fork the repository
• if you want to add a new challenge called "New Challenge", you would create a folder called challenge{number}
• Inside the folder, you would create a README.md file with the challenge description
  • you will put the challenge name as the title with a # {name (New Challenge)}
  • you will put the challenge description as the first paragraph
  • you will put the example test case/output as a code block
• You would also create an answers.md file with the solutions
  • you will put the solutions in this general format
    • ## {Language}
    • ```{language}
    • {code}
    • ```
• Add the challenge to the SUMMARY.md file
• Create a pull request

Special Instructions for Rust Solutions

MdBook features a runtime for the builtin code blocks, please include the valid code to run the test/code in the code block. You can use the following syntax to run the code block:

# fn main() { // # is used to hide this line
    let x = 5;
    let y = 6;

    println!("{}", x + y);
# } // # is used to hide this line

Therefore, all the end user will see is

fn main() {
    let x = 5;
    let y = 6;

    println!("{}", x + y);
}

However, they can click in the top right corner and run the code on their machine. More info here.

(CODE SOURCE: mdBook)

License

This book is licensed under the MIT License. See here for more details: LICENSE

Reversing A String While Preserving Special Characters

Create a function that accepts a string and returns the reverse of that string while preserving the position of all punctuation.

a,b$c -> c,b$a
hello world! -> dlrow olleh!

Examples

assert reverse_string("a,b$c") == "c,b$a"
assert reverse_string("hello world!") == "dlrow olleh!"

Notes

• The string may include letters, numbers, and special characters.

Constraints

• The string will not be empty.
• The string will contain at least one letter.

Answers

These are my solutions, and probably wont be the most efficient, but they work.

Javascript

function isAlphabet(char) {
    return /\w+/.test(char);
}

function reverseStringWithPunctuationRecursive(str) {
    if (typeof str === "string") str = str.split(""); // Ensure str is split into an array of characters
    if (!str.length) return "";
    if (!isAlphabet(str[0])) return str[0] + reverseStringWithPunctuation(str.slice(1));
    if (!isAlphabet(str[str.length - 1])) return reverseStringWithPunctuation(str.slice(0, -1)) + str[str.length - 1];
    return str[str.length - 1] + reverseStringWithPunctuation(str.slice(1, str.length - 1)) + str[0];
}

// or 

function reverseStringWithPunctuation(str) {
    const chars = str.split('');

    const reversedAlphabets = chars.filter(c => isAlphabet(c)).reverse();

    let alphaIndex = 0;

    const result = chars.map(c => isAlphabet(c) ?  reversedAlphabets[alphaIndex++] : c);

    return result.join('');
}

Go

func isAlphanumeric(c rune) bool {
	return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' || c >= '0' && c <= '9'
}

func reverseStringPreservePunctuation(s string) string {
	r := []rune(s)
	for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
		for !isAlphanumeric(r[i]) && i < j { 
			i++ 
		}
		for !isAlphanumeric(r[j]) && i < j { 
			j--
		}

		r[i], r[j] = r[j], r[i]
	}
	return string(r)
}

Python

def reverse_string_preserve_punctuation(s):
    characters = list(s)
    left_index = 0
    right_index = len(characters) - 1

    while left_index < right_index:
        if not characters[left_index].isalnum():
            left_index += 1
        elif not characters[right_index].isalnum():
            right_index -= 1
        else:
            characters[left_index], characters[right_index] = characters[right_index], characters[left_index]
            left_index += 1
            right_index -= 1

    return ''.join(characters)

Happy Numbers - Code Golf (Finding the shortest code to solve a problem)

Here is how it works basically:

1. take any number N.
2. Square the individual digits of N then add them together
3. Repeat step 2 until the answer is equal to 1, if it is a infinite loop, it is not a happy number.

Example

N = 13
1^2 + 3^2 = 1 + 9 = 10
1^2 + 0^2 = 1

So 13 is a happy number.

Challenge

Create a function that accepts a number and returns True if the number is a happy number, False if it is not.

Answers

You can probably get shorter

Javascript

h=n=>{for(s=new Set;n!=1&&!s.has(n);s.add(n),n=n.toString().split('').reduce((a,c)=>a+c**2,0));return n==1}

Commented code:

h = n => {
    for (s = new Set; // set to store numbers
         n != 1 && !s.has(n);  // while n is not 1 and n is not in set, if n is in set, it is an infinite loop and not a happy number
         s.add(n),  // add n to set
         n = n.toString().split('').reduce((a, c) => a + c ** 2, 0)); // sum of squares of digits
    return n == 1 // return true if n is 1
}

Find all the Armstrong numbers in a range specified number, 0..N

Defining:

A Armstrong number is a number that is equal to the sum of the values of the digits raised to the length of the number.

Examples:

1^3 + 5^3 + 3^3 = 153
1^4 + 6^4 + 3^4 + 4^4 = 1634
0^1 = 0 
individual_digit_of_N^number_of_digits_in_N = N_Is_Armstrong_number

So, 153 is a Armstrong number, 1634 is a Armstrong number, and 0 is a Armstrong number.

Answers

Javascript

function isArmstrongNumber(n) {
    return n === n.toString().split('').reduce((a, c) => a + Math.pow(parseInt(c), n.toString().length), 0);
}

Haskell

isArmstrongNumber :: Int -> Bool
isArmstrongNumber n = n == sum (map (\x -> read [x] ^ length (show n)) (show n))

findNArmstrongNumbers :: Int -> [Int]
findNArmstrongNumbers n = filter isArmstrongNumber [1..n]

Python

def is_armstrong_number(n: int) -> bool:
    return n == sum([int(x) ** len(str(n)) for x in str(n)])

def find_n_armstrong_numbers(n: int) -> list:
    return [x for x in range(1, n + 1) if is_armstrong_number(x)]

Rotate An Array

Rotate an array to the left or right. So, [1, 2, 3, 4, 5] rotated right twice would be [4, 5, 1, 2, 3] Hint: there is a formula for calculating array rotation, so if you're stuck you can just use that :3 (I won't say what it is here just in case you'd rather not use it) - rainy.boyo (Discord)

examples

rotate([1, 2, 3, 4, 5], 2) // [4, 5, 1, 2, 3]
rotate([1, 2, 3, 4, 5], -2) // [3, 4, 5, 1, 2]

Answers

JavaScript

function rotate(nums, k, right) {
    if (right) k = nums.length - k;
    nums.unshift(...nums.splice(k));
    return nums;
}

Go

func rotate(nums []int, k int, right bool) []int {
    if right {
        k = len(nums) - k
    }
    return append(nums[k:], nums[:k]...)
}

Python

def rotate(nums, k, right=False):
    if right:
        k = len(nums) - k
    return nums[k:] + nums[:k]

Reverse the Odd Length Words

Given a String, reverse all of the words whose length is a odd number.

Ex:

reverseOdd("One two three four") ➞ "enO owt eerht four"

Stolen Borrowed from Edabit

Answers

Javascript

function reverseOddWords(string) {
    const words = string.split(' ');
    words.map((word, index) => {
        if (word.length % 2 !== 0) {
            words[index] = word.split('').reverse().join('');
        }
    });

    return words.join(' ');
}

Haskell

reverseOddWords :: String -> String 
reverseOddWords = unwords . map (\x -> if odd (length x) then reverse x else x) . words

Python

def reverse_odd_words(s: str) -> str:
    return ' '.join([word[::-1] if len(word) % 2 != 0 else word for word in s.split()])

Palindrome Checker

Create a program that checks if a given strings is a palindrome. A palindromeis defined as being a string that is string that can be written the same way forwards as backwards.

Examples

assert is_palindrome("racecar") == True
assert is_palindrome("hello") == False

Answers

JavaScript

function isPalindrome(str) {
  return str === str.split('').reverse().join('');
}

Python

def is_palindrome(s: str) -> bool:
    return s == s[::-1]

Random Password Generator

Create a simple (it doesn’t have to be cryptographically secure) random password generator. DO NOT USE IT AS A REAL ONE.

Examples

assert len(generatePassword(10)) == 10

Answers

JavaScript

function generatePassword(length) {
  const charset = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
  let password = "";
  for (let i = 0; i < length; i++) {
    const randomIndex = Math.floor(Math.random() * charset.length);
    password += charset[randomIndex];
  }
  return password;
}

console.log(generatePassword(10));

Lua

function generate_random_password(length)
    local characters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*()_+{}[]|:;<>,.?/~"
    local password = ""
    for i = 1, length do
        local random_index = math.random(1, #characters)
        password = password .. string.sub(characters, random_index, random_index)
    end
    return password
end

Encryption/Decryption

Create a function that can encrypt or decrypt a function without a external library to do the encryption/decryption. It can be as simple as a xor cipher!

Example

assert encrypt("hello", 3) == "khoor"
assert decrypt("khoor", 3) == "hello"

Answer

JavaScript

class RSA {
    constructor(p = 61n, q = 53n) {
        this.p = p;
        this.q = q;
        this.n = this.p * this.q;
        this.λ = this.lcm((this.p - 1n), (this.q - 1n));
        this.e = 17n; // 1 < e < λ and coprime with λ
        this.d = this.modInverse(this.e, this.λ); 
    }

    lcm(a, b) {
        return (a * b) / this.gcdExtended(a, b)[0];
    }

    getPublicKey() {
        return [this.n, this.e];
    }

    getPrivateKey() {
        return [this.n, this.d];
    }

    gcdExtended(a, b) {
        if (a === 0n) {
            return [b, 0n, 1n];
        }
        const [g, x1, y1] = this.gcdExtended(b % a, a);
        const x = y1 - (b / a) * x1;
        const y = x1;
        return [g, x, y];
    }

    modInverse(a, b) {
        let [g, x] = this.gcdExtended(a, b);
        if (g !== 1n) {
            throw 'Modular inverse does not exist';
        }
        else {
            return (x % b + b) % b;
        }
    }

    encrypt(m, publicKey) {
        return (m ** publicKey[1]) % publicKey[0];
    }

    decrypt(c, privateKey) {
        return (c ** privateKey[1]) % privateKey[0];
    }
}

const rsa = new RSA();
const publicKey = rsa.getPublicKey();
const privateKey = rsa.getPrivateKey();

const message = 54n;
const encryptedMessage = rsa.encrypt(message, publicKey);
const decryptedMessage = rsa.decrypt(encryptedMessage, privateKey);

console.log('Message:', message);
console.log('Encrypted Message:', encryptedMessage);
console.log('Decrypted Message:', decryptedMessage);

Closest Index To A Specified Integer

Create a function that accepts two parameters, an integer and a array of integers, and returns the index of the integer that is the closest the the value; however, if they are the same distance from the integer, return the greater one!

Examples

closestIndexToNumber(10, [1, 5, 9, 11]); // 3
closestIndexToNumber(2, [1, 5, 9, 10]); // 0
closestIndexToNumber(5, [1, 5, 9, 10]); // 1
closestIndexToNumber(10, [9, 11]); // 1
closestIndexToNumber(-10, [-9, -11]); // 0
closestIndexToNumber(0, []); // 0

Answer

JavaScript

function closestIndexToNumber(number, array) {
    let closestIndex = 0;
    let closestDistance = Math.abs(array[0] - number);
 
    array.forEach((value, index) => {
        const distance = Math.abs(value - number);
        if (distance < closestDistance || (closestDistance === distance && value > array[closestIndex])) { 
            closestDistance = distance;
            closestIndex = index;
        }
    });
    
    return closestIndex;
}

Collatz Conjecture

This is a fairly easy one, most should be able to complete since it is well know. It goes like this:

1. take a number,
   1. half it if it is even, but
   2. if it’s odd you multiply by three and add one.
2. It should return one at the end.

Create a program that can calculate the sequence for all n > 0 to 10000 (or 100000 (slo))

Answer

Haskell

collatzSequenceForN :: (Integral a) => a -> [a]
collatzSequenceForN n
  | n == 1 = [1]
  | even n = n : collatzSequenceForN (n `div` 2)
  | odd n = n : collatzSequenceForN (n * 3 + 1)

collatzSequenceToN :: (Integral a) => a -> [[a]]
collatzSequenceToN n = map collatzSequenceForN [1..n]

Javascript (Recursive)

function collatzForN(n) {
    if (n === 1) return [1];
    if (n % 2 === 0) return [n, ...collatzForN(n / 2)];
    return [n, ...collatzForN(3 * n + 1)];
}

function getCollatzToN(n) {
    const collatz = Array(n).fill().map((_, i) => collatzForN(i + 1));
    return collatz;
}

Javascript (Iterative)

function collatzForN(n) {
    const sequence = [];
    while (n !== 1) {
        sequence.push(n);
        n = n % 2 === 0 ? n / 2 : 3 * n + 1;
    }
    sequence.push(1);
    return sequence;
}

Python

def collatz_for_n(n):
    sequence = []
    while n != 1:
        sequence.append(n)
        n = n // 2 if n % 2 == 0 else 3 * n + 1
    sequence.append(1)
    return sequence

Calculate is a number is a prime number

A prime number is a number > 1 and cannot be produced from the product of two smaller numbers. For example 13 is prime, so 1 * 13 is its only factor. While 15 is not prime because 3 * 5 = 15.

Examples

isPrime(13); // true
isPrime(15); // false

Answer

JavaScript (recursive trial division)

function isAPrimeNumberRecursive(n, i = 2) {
    if (n <= 2) return n === 2;
    if (n % i === 0) return false;
    if (i * i > n) return true;
    return isAPrimeNumberRecursive(n, i + 1);
}

Python

def is_a_prime_number(n: int) -> bool:
    if n <= 2:
        return n == 2
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

JavaScript (Solovay–Strassen primality test)

function modPow(base, exponent, modulus) {
    let result = 1;
    base = base % modulus;
    while (exponent > 0) {
        if (exponent % 2 === 1) result = (result * base) % modulus;
        exponent = Math.floor(exponent / 2);
        base = (base * base) % modulus;
    }
    return result;
}

function jacobi(a, n) {
        if (n <= 0 || n % 2 === 0) return 0;
        a = a % n;
        let t = 1;
        while (a !== 0) {
            while (a % 2 === 0) {
                a = a / 2;
                let r = n % 8;
                if (r === 3 || r === 5) t = -t;
            }
            let temp = a;
            a = n;
            n = temp;
            if (a % 4 === 3 && n % 4 === 3) t = -t;
            a = a % n;
        }
        if (n === 1) return t;
        return 0;
}

function isAPrimeNumber(n, k = 10) {
    for (let i = 0; i < k; i++) {
        let a = Math.floor(Math.random() * (n - 2)) + 2;
        let x = jacobi(a, n);
        if (x === 0 || modPow(a, (n - 1) / 2, n) !== ((x % n) + n) % n) {
            return false;
        }
    }
    return true;
}

Matrix Multiplication

Create a function that accepts two 2d matrixes and multiplies them together. Pretty simple stuff honestly, google matrix multiplication if you are confused.

Example

[[1,2][3,4]], [[5,6],[0,7]] -> [[5, 20],[15, 46]]

Answer

Javascript

function matrixMultiply(matrix1, matrix2) {
    if (matrix1.length === 0 || matrix2.length === 0) return null;
    if (matrix1[0].length !== matrix2.length) return null;
 
    const result = [];
    for (const rowOfMatrix1 of matrix1) {
        const newRow = [];
        for (let matrix2Index = 0; matrix2Index < matrix2[0].length; matrix2Index++) {
            const column = matrix2.map(row => row[matrix2Index]);
            const sum = rowOfMatrix1.reduce((acc, value, index) => acc + value * column[index], 0);
            newRow.push(sum);
        }
        result.push(newRow);
    }
 
    return result;
}

Anagram Checker

Create a anagram checker, it should accept two strings and return a boolean if it is a valid anagram. This program should also handle spaces and be case insensitive (capital and lowercase are treated the same).

A anagram is defined as the following: A phrase that can be formed from rearranging the characters of another string.

Examples

a , a -> True
b, a -> False
b a, a b -> True
Ba, ba -> True
silent, listen -> True

Answer

Javascript

function isAnagramWithSorting(str1, str2) {
    str1 = str1.toLowerCase()
    str2 = str2.toLowerCase()
    if (str1 === str2) return true
    if (str1.length !== str2.length) return false
    return str1.split('').sort().join('') === str2.split('').sort().join('')
}

function isAnagram(str1, str2) {
    str1 = str1.toLowerCase()
    str2 = str2.toLowerCase()
    if (str1 === str2) return true
    if (str1.length !== str2.length) return false
    const frequency = new Map()
    for (let i = 0; i < str1.length; i++) {
        frequency.set(str1[i], (frequency.get(str1[i]) || 0) + 1)
        frequency.set(str2[i], (frequency.get(str2[i]) || 0) - 1)
    }
    return [...frequency.values()].every(freq => freq === 0)
}

Python Equivalent

def is_anagram(str1: str, str2: str) -> bool:
    str1 = str1.lower()
    str2 = str2.lower()
    if str1 == str2:
        return True
    if len(str1) != len(str2):
        return False
    frequency = {}
    for i in range(len(str1)):
        frequency[str1[i]] = frequency.get(str1[i], 0) + 1
        frequency[str2[i]] = frequency.get(str2[i], 0) - 1
    return all(freq == 0 for freq in frequency.values())

Integer to Roman Numberal

Write a program that converts a integer to a roman numeral string. I can't really describe it more, but here are some tests...

Examples

48 -> XLVIII
99 -> XCIX
1234 -> MCCXXXIV
500 -> D

Answer

Javascript

function getRomanNumberalStringFromN(n) {
    const romanNumerals = [
        ['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]
    ];

    let result = '';

    for (const [numeral, value] of romanNumerals) {
        while (n >= value) {
            result += numeral;
            n -= value;
        }
    }

    return result;
}

Python Equivalent

def get_roman_numberal_string_from_n(n: int) -> str:
    roman_numerals = [
        ['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]
    ]

    result = ''

    for numeral, value in roman_numerals:
        while n >= value:
            result += numeral
            n -= value

    return result

Circular Primes - Project Euler

Basically, you generate prime numbers for a given range, then you compute all the rotations for that number, for example "197" can be "197", "971", or "719", then determine if all the rotations are prime numbers. If they are, it is a circular prime.

"197" -> "197", "971", "719"
"11" -> "11"
"13" -> "13", "31"

Answer

Python

from itertools import permutations
from math import factorial

def is_prime(x):
    return factorial(x - 1) % x == x - 1

def circular_prime(n: int):
    digits = [int(i) for i in str(n)]
    for x in permutations(digits):
        if not is_prime(int("".join([str(i) for i in x]))):
            return False
        
        return True
    
print(circular_prime(197))

Longest Pandigital Prime Number - Project Euler

A pandigital number is a number that uses each digit once, for example

1234567890 is a pandigital number, it uses each number once 1234 is a pandigital number, it uses each number once 1233 is not a pandigital number, it uses 3 twice 122233 is not pandigital, it uses 2 three times, and 3 two times

You will create a function(s) that accepts a integer, generates a list of prime numbers to that integer then returns the longest pandigital prime number of that list of prime numbers.

Answer

Javascript

function getPrimeNumbersUpToN(n) {
    const primes = [];
    for (let i = 2; i < n; i++) {
        let isPrime = true;
        for (let j = 2; j <= Math.sqrt(i); j++) {
            if (i % j === 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            primes.push(i);
        }
    }
    
    return primes;
}

function isPandigital(number) {
    const splitNumber = number.toString().split("");
    const splitNumberLength = splitNumber.length;
    const uniqueDigits = new Set(splitNumber);

    if (splitNumberLength > 10) return false; // it cannot have more than 10 because that would repeat 
    if (uniqueDigits.size !== splitNumberLength) return false;

    return true;
}

function longestPandigitalPrimeToN(n) {
    const pandigitalPrimes = getPrimeNumbersUpToN(n).filter((value) => {
        return isPandigital(value);
    })

    return pandigitalPrimes[pandigitalPrimes.length - 1]
}

Blackjack Game

Blackjack is a card game against the dealer, players will be dealt two cards, which they can choose to "hit" (draw another card) or "stand" (Keep current hand, and ends all their turns). Whoever has the higher value cards, wins, if you go over 21, you lose. The goal of the game is to reach the highest value

Card Values:

• Faces: 10
• Aces: 1 or 11
• Numbered: Number on face

Requirements

• Basically do the requirements above!
• It should feature at least one player and a ai dealer. Here are some dealer rules: The Dealer must draw on 16 or less, and stand on hard 17 (no ace) but must hit on a soft 17 (with ace that can be counted as 11)
• It should feature a deck with realistic odds for a 52 card deck.

Answer

Javascript (kinda bad 💀)

Pastebin

Right Triangle Checker

The name basically explains it, this is middle-high school level math, don’t overthink it! Input is a array of side lengths. so..

Examples

[3,5,4] -> True
[1, 2, 27] -> false

Answer

Javascript

function isRightTriangle(arr) {
    if (arr.length !== 3) return false;
    
    let sortedArr = arr.sort((a, b) => a - b);
    
    return (sortedArr[0] ** 2 + sortedArr[1] ** 2) === (sortedArr[2] ** 2);
}

Haskell

isRightTriangle :: [Int] -> Bool
isRightTriangle arr
    | length arr /= 3 = False
    | otherwise = a^2 + b^2 == c^2
    where [a, b, c] = sort arr

Python

from typing import List

def is_right_triangle(arr: List[int]) -> bool:
    if len(arr) != 3:
        return False
    
    a, b, c = sorted(arr)
    return a ** 2 + b ** 2 == c ** 2

Solve for the first 5 digits of PI

Pretty simple, create a function that can solve for the first 5 digits of pi, there are TONS of formulas, you cannot use the built in pi function though. The easiest formula (not accurate) is Leibniz Formula for pi, it’s really easy.

Answer

Rust

fn bellard_pi(iterations: i32) -> f64 {
    let mut sum: f64 = 0.0;
    for n in 0..iterations {
        let t1 = f64::powi(-1.0, n) / f64::powi(2.0, 10 * n);
        let n = n as f64;
        let t2 = -32.0 / (4.0 * n + 1.0);
        let t3 = -1.0 / (4.0 * n + 3.0);
        let t4 = 256.0 / (10.0 * n + 1.0);
        let t5 = -64.0 / (10.0 * n + 3.0);
        let t6 = -4.0 / (10.0 * n + 5.0);
        let t7 = -4.0 / (10.0 * n + 7.0);
        let t8 = 1.0 / (10.0 * n + 9.0);

        sum += t1 * (t2 + t3 + t4 + t5 + t6 + t7 + t8);
    }
    return sum / 64.0;
}

fn main() {
let iterations = 10;
println!("Result: {}", bellard_pi(iterations));
}

fn leibniz(n: u32) -> f64 {
    if n == 0 {
       return 1.0
    }
    
    let numerator = if n % 2 == 0 {
        1.0
    } else {
        -1.0
    };
    
    return (numerator / (2 * n + 1) as f64) + leibniz(n-1);
}

fn main() {
let n = 10000;
println!("Result: {}", 4.0 * leibniz(n));
}

Python Equivalent

def leibniz(n: int) -> float:
    if n == 0:
        return 1.0
    
    numerator = 1.0 if n % 2 == 0 else -1.0
    return (numerator / (2 * n + 1)) + leibniz(n-1)

def bellard_pi(iterations: int) -> float:
    sum = 0.0
    for n in range(iterations):
        t1 = (-1) ** n / 2 ** (10 * n)
        t2 = -32 / (4 * n + 1)
        t3 = -1 / (4 * n + 3)
        t4 = 256 / (10 * n + 1)
        t5 = -64 / (10 * n + 3)
        t6 = -4 / (10 * n + 5)
        t7 = -4 / (10 * n + 7)
        t8 = 1 / (10 * n + 9)

        sum += t1 * (t2 + t3 + t4 + t5 + t6 + t7 + t8)
    return sum / 64

Square Root Calculation

Do what the title says :3, no built in square root functions, it should be able to accept numbers like 13 which have no square perfect root and compute one. Use Heron’s method for the easiest solution.

Examples

square_root(9) == 3
square_root(13) == 3.605551275463989

Answer

Rust

use std::f64::consts::E;
fn square_root(s: f64) -> f64 {
    // sqrt(x) = e^((1/2)ln(S))
    let guess = E.powf(0.5 * f64::ln(s));
    (guess * 1e9).round() / 1e9 // round to 9 decimal places
}

fn main() {
let s = 19.0;
println!("The square root of {} is {}", s, square_root(s));
}

Python Equivalent

import math

def square_root(s: float) -> float:
    guess = math.e ** (0.5 * math.log(s))
    return round(guess, 9)

s = 19.0
print(f"The square root of {s} is {square_root(s)}")

Rust - Heron's Method

fn herons_method(S: f64, x_current: f64, tolerance: f64) -> f64 {
    let x_next = 0.5 * (x_current + S / x_current);
    
    if (x_next - x_current).abs() < tolerance {
        x_next
    } else {
        herons_method(S, x_next, tolerance)
    }
}

fn main() {
    let S = 13.0;
    let guess = S / 2.0;
    let tolerance = 1e-10;
    println!("Result: {}", herons_method(S, guess, tolerance));
}

Find the Missing Number

You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in the list. One of the integers is missing in the list. Write an efficient code to find the missing integer.

Examples

let v = vec![1, 2, 4, 6, 3, 7, 8];
assert_eq!(find_missing_number(&v), 5);

Answer

JavaScript - For Loop

function findMissingNumber(v) {
    for (let i = 1; i <= v.length + 1; i++) {
        if (!v.includes(i)) {
            return i;
        }
    }
}

JavaScript - HashMap

function findMissing(numbers) {
    const seen = new Set(numbers);
    const n = Math.max(...numbers) + 1;
    for (let i = 1; i <= n; i++) {
        if (!seen.has(i)) {
            return i;
        }
    }
    return n + 1;
}

Rust - Sum

fn find_missing_number(v: &Vec<i32>) -> i32 {
    let n = v.len() as i32 + 1;
    let total = n * (n + 1) / 2;
    let sum: i32 = v.iter().sum();
    total - sum
}

fn main() {
let v = vec![1, 2, 4, 6, 3, 7, 8];
assert_eq!(find_missing_number(&v), 5); // no output
}

Haskell

findMissingNumber :: [Int] -> Int
findMissingNumber v = n * (n + 1) `div` 2 - sum v
    where n = fromIntegral $ length v + 1

C

int findMissingNumber(int arr[], int size) {
    int xor = 0;
    for(int i = 0; i < size; i++) {
        xor ^= arr[i] ^ (i + 1);
    }
    return xor ^ (size + 1);
}

Python

def find_missing(numbers):
    n = len(numbers) + 1
    return (n * (n + 1)) // 2 - sum(numbers)

Run Length Encoding

Run-length encoding (RLE) is a basic form of lossless data compression. It works by replacing repeated sequences of data with a single data value and the number of times it repeats. Your function only has to handle alphabetic characters; however, you should have two functions that can convert to and from the RLE form.

Examples

Encoding:
AAAABBBCCDAA => 4A3B2C1D2A
A => 1A
AA => 2A

Decoding: 
4A3B2C1D2A => AAAABBBCCDAA
1A => A
2A => AA

Answer

JavaScript

function RLEEncode(str) {
  let encoded = '';
  let count = 1;
  for (let i = 0; i < str.length; i++) {
      if (str[i] === str[i + 1]) {
          count++;
      } else {
          encoded += count + str[i];
          count = 1;
      }
  }

  return encoded;
}

function RLEDecode(str) {
  let decoded = '';
  let count = 0;
  for (let i = 0; i < str.length; i++) {
      if (str[i] >= '0' && str[i] <= '9') {
          count += str[i];
      } else {
          decoded += str[i].repeat(Number(count));
          count = '';
      }
  }
  return decoded;
}

Python Equivalent

def rle_encode(s: str) -> str:
    encoded = ''
    count = 1
    for i in range(len(s)):
        if i + 1 < len(s) and s[i] == s[i + 1]:
            count += 1
        else:
            encoded += str(count) + s[i]
            count = 1
    return encoded

def rle_decode(s: str) -> str:
    decoded = ''
    count = ''
    for i in range(len(s)):
        if s[i].isdigit():
            count += s[i]
        else:
            decoded += s[i] * int(count)
            count = ''
    return decoded

Find the Longest Word in a String

This challenge is pretty simple, you are given a string and you need to find the longest word in that string. If two words are the same length, return the first word that appears in the string. If the string is empty, return a empty string.

Examples

longest_word("Hello there") -> "Hello"
longest_word("My name is") -> "name"
longest_word("What is the longest word in this sentence") -> "sentence"

Answer

JavaScript

function longest_word(str) {
    let words = str.split(' ');
    let longest = '';
    for (let word of words) {
        if (word.length > longest.length) {
            longest = word;
        }
    }
    return longest;
}

Rust

fn longest_word(s: &str) -> String {
    let words: Vec<&str> = s.split_whitespace().collect()
    let mut longest = String::new();
    for word in words {
        if word.len() > longest.len() {
            longest = word.to_string();
        }
    }
    longest
}

fn main() {
println!("{}", longest_word("Hello there")); // Hello
println!("{}", longest_word("My name is")); // name
println!("{}", longest_word("What is the longest word in this sentence")); // sentence
}

Python Equivalent

def longest_word(s: str) -> str:
    words = s.split()
    longest = ''
    for word in words:
        if len(word) > len(longest):
            longest = word
    return longest

print(longest_word("Hello there")) # Hello
print(longest_word("My name is")) # name
print(longest_word("What is the longest word in this sentence")) # sentence

End to End Encryption

Build a simple end to end encrypted chat script; you can use existing libraries/implementations for things like encryption.

At simplest, the solution should take 2 inputs, encrypt them using the sender's private key and the receiver's public key, then decrypt again. You can go a step further if you'd like by implementing a networking backend or support for over 2 users but this is not required!

Answer

Javascript - Node.js

const crypto = require('crypto');
const assert = require('node:assert');

const message = 'Hello World!'

// Generate a ECDH key pair
// these would be different for each transmission or reception
const transmitterEncryptionKeyPair = crypto.generateKeyPairSync('x25519')
const receiverEncryptionKeyPair = crypto.generateKeyPairSync('x25519')

// Diffie-Hellman key exchange to compute their shared secret
// this would then be ran through a KDF to generate a longer key for encryption
const transmitterSecret = crypto.diffieHellman({
    privateKey: transmitterEncryptionKeyPair.privateKey,
    publicKey: receiverEncryptionKeyPair.publicKey
})

const receiverSecret = crypto.diffieHellman({
    privateKey: receiverEncryptionKeyPair.privateKey,
    publicKey: transmitterEncryptionKeyPair.publicKey
})

// they should both equal the same...
assert.strictEqual(transmitterSecret.toString('hex'), receiverSecret.toString('hex'))

/// 
/// Generating the shared keys to the specified length
///
const transmitterEncryptionDerivedKey = crypto.createHash("BLAKE2s256").update(transmitterSecret).digest()
const recieverDecryptionDerivedKey = crypto.createHash("BLAKE2s256").update(receiverSecret).digest()

assert.strictEqual(transmitterEncryptionDerivedKey.toString('hex'), recieverDecryptionDerivedKey.toString('hex'))

/// 
/// Shared Initialization Vector
///
const iv = crypto.randomBytes(12)

///
/// ENCRYPTION
///
const cipher = crypto.createCipheriv('aes-256-gcm', transmitterEncryptionDerivedKey, iv)

let encrypted = cipher.update(message, 'utf8', 'hex') + cipher.final('hex')

const authTag = cipher.getAuthTag()

///
/// DECRYPTION
///
const decipher = crypto.createDecipheriv('aes-256-gcm', recieverDecryptionDerivedKey, iv)

decipher.setAuthTag(authTag)

let decrypted = decipher.update(encrypted, 'hex', 'utf8') + decipher.final('utf8')

assert.strictEqual(message, decrypted) // these now should equal

console.log('Message:', message)
console.log('Decrypted:', decrypted)

Series Pattern Detection

The goal of this challenge is to detect the pattern in a series of numbers, lets say 3 or more. For example, in the series

[3, 6, 9]

we know that it is simply adding 3 each time, and so, the computer should determine that the next number in the series should be 12.

[4, 16, 64]

in this case, each number is multiplied by 4, so the next number in the series is 256.

Your code should be able to detect arithmetic and geometric series, then be able to find the nth term in the series.

Answer

JavaScript

const seriesTypes = {
    arithmetic: 'arithmetic',
    geometric: 'geometric'
}

/**
 * Get the type of series, either arithmetic or geometric
 * @param {number[]} sequence The sequence to find the type of
 * @returns {string|null} the type of series
 */
function getSeriesType(sequence) {
    if (sequence.length < 3) throw new Error("Sequence is not long enough, 3 items required. Found: " + sequence.length);

    const differences = new Set();
    const ratios = new Set();

    for (let i = 1; i < sequence.length; i++) {
        const difference = sequence[i] - sequence[i - 1]; // a arthimetic series will only have one difference between all numbers exp: 2, 4, 6, 8 (diff: 2)
        const ratio = sequence[i] / sequence[i - 1]; // For this, the ratio is the same, exp: 4, 16, 64 (ratio: 4)

        // store each value found then in set, a set can only have one unique value, so if there is anymore its not that series type
        differences.add(difference);
        ratios.add(ratio);
    }

    if (differences.size === 1) return seriesTypes.arithmetic;
    if (ratios.size === 1) return seriesTypes.geometric;

    return null;
}

/**
 * Find the nth term in a geometric or arithmetic sequence
 * @param {number[]} sequence The sequence to find the nth term in
 * @param {number} n The nth term to find
 * @returns {number|null} the nth term of the series
 */
function findNthTermInSequence(sequence, n) {
    const type = getSeriesType(sequence);
    if (type === seriesTypes.arithmetic) {
        const difference = sequence[1] - sequence[0];
        return sequence[sequence.length - 1] + difference * (n - sequence.length);
    } else if (type === seriesTypes.geometric) {
        const ratio = sequence[1] / sequence[0];
        return sequence[sequence.length - 1] * Math.pow(ratio, n - sequence.length);
    } else {
        throw new Error("Unsupported series type")
    }
}

Python Equivalent

from typing import List, Union

def get_series_type(sequence: List[int]) -> Union[str, None]:
    if len(sequence) < 3:
        raise ValueError("Sequence is not long enough, 3 items required. Found: " + str(len(sequence)))

    differences = set()
    ratios = set()

    for i in range(1, len(sequence)):
        difference = sequence[i] - sequence[i - 1]
        ratio = sequence[i] / sequence[i - 1]

        differences.add(difference)
        ratios.add(ratio)

    if len(differences) == 1:
        return "arithmetic"
    if len(ratios) == 1:
        return "geometric"

    return None

def find_nth_term_in_sequence(sequence: List[int], n: int) -> Union[int, None]:
    series_type = get_series_type(sequence)
    if series_type == "arithmetic":
        difference = sequence[1] - sequence[0]
        return sequence[-1] + difference * (n - len(sequence))
    elif series_type == "geometric":
        ratio = sequence[1] / sequence[0]
        return sequence[-1] * ratio ** (n - len(sequence))
    else:
        raise ValueError("Unsupported series type")

print(find_nth_term_in_sequence([3, 6, 9], 4))  # 12

Shortest Path Finder

Given a 2d matrix, find the shortest path from a point (row1, column1) to another point (row2, column2) and print the new matrix where the path it follows is the value 2. The matrix will have a value of 1 for walls and 0 for paths. Because it goes by row, column imagine the matrix as a coordinate system where the top left is (0, 0) and the bottom right is (n, m).

Example

Input
[
    [0, 0, 0, 0, 0],
    [1, 1, 1, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1],
    [0, 0, 0, 0, 0]
]
(0, 0) -> (4, 4)

Output
[
    [2, 2, 2, 2, 2]
    [1, 1, 1, 1, 2]
    [2, 2, 2, 2, 2]
    [2, 1, 1, 1, 1]
    [2, 2, 2, 2, 2] 
]

Where 2 is the path followed.

Answer

Python

from collections import deque

def reconstruct_path(came_from, current_node):
    """Reconstructs the path from start to end node based on the came_from map."""
    total_path = [current_node]
    while current_node in came_from:
        current_node = came_from[current_node]
        total_path.append(current_node)
    return total_path[::-1]  # Reverse the path to start->end direction

def get_neighbors(grid, node):
    """Returns the non-diagonal, non-blocked neighbors of a node."""
    neighbors = []
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # Up, Down, Left, Right
    for dx, dy in directions:
        x, y = node[0] + dx, node[1] + dy
        if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] != 1:
            neighbors.append((x, y))
    return neighbors

def bfs(grid, start, end):
    """Performs BFS on the grid from start to end node, returns the path."""
    queue = deque([start])
    came_from = {start: None}

    while queue:
        current = queue.popleft()
        if current == end:
            break
        for neighbor in get_neighbors(grid, current):
            if neighbor not in came_from:
                queue.append(neighbor)
                came_from[neighbor] = current

    return reconstruct_path(came_from, end) if end in came_from else []

def create_new_path_grid(grid, path):
    """Marks the path on the grid by setting the path nodes to 2, optimized for readability and efficiency."""
    path_set = {node for node in path if node}
    new_grid = [[2 if (i, j) in path_set else cell for j, cell in enumerate(row)] for i, row in enumerate(grid)]
    return new_grid

start = (0, 0)
end =  (4, 4)
grid = [
    [0, 0, 0, 0, 0],
    [1, 1, 1, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1],
    [0, 0, 0, 0, 0]
]

path = bfs(grid, start, end)
new_grid = create_new_path_grid(grid, path)

for row in new_grid:
    print(row)

Determining the Day of the Week

Given three things, (day, month, year), determine the day of the week. You may assume that the day is always valid, the month is always valid, and the year is always valid. The year is always greater than 1752.

Example

Input
    day: 1
    month: 1
    year: 2020
Output
    Wednesday

Answer

Rust - Sakamoto's method

const DAYS: [&str; 7] = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"];

fn get_day_of_week(day: i32, month: i32, year: i32) -> String {
    let t = [0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4];
    let y = year - if month < 3 { 1 } else { 0 };
    let w = (y + y / 4 - y / 100 + y / 400 + t[(month - 1) as usize] + day) % 7;
    DAYS[w as usize].to_string()
}

fn main() {
    println!("{}", get_day_of_week(1, 1, 2020));
}

Rust - Schwerdtfeger's method

const DAYS: [&str; 7] = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"];

fn get_day_of_week(day: i32, month: i32, year: i32) -> String {
    let c = if month > 2 { year / 100 } else { (year - 1) / 100 };
    let g = if month > 2 { year - 100 * c } else { year - 1 - 100 * c };
    let e = [0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4];
    let f = [0, 5, 3, 1];

    let w = (day + e[(month - 1) as usize] + f[(c % 4) as usize] + g + (g / 4)) % 7;
    DAYS[w as usize].to_string()
}

fn main() {
println!("{}", get_day_of_week(1, 1, 2020));        
}

Equivalent JavaScript

const days = ['Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday'];

function getDayOfTheWeek(day, month, year) { 
    let c = Math.floor(month > 2 ? year / 100 : (year - 1) / 100);
    let g = month > 2 ? year - 100 * c : year - 1 - 100 * c;
    const e = [0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4];
    const f = [0, 5, 3, 1]

    let w = (day + e[month - 1] + f[c % 4] + g + Math.floor((g/4))) % 7;
    return days[w];
}

Python - Simplified Zeller w/ Keith's Month-Length Equation

import math

days = ["Sat", "Sun", "Mon", "Tue", "Wed", "Thu", "Fri"]

def h(d, m, y):
    if m == 1 or m == 2:
        y -= 1
        m += 12
    return days[((d+math.floor((((23*m)/9)+4))+y+math.floor(y/4)-math.floor(y/100)+math.floor(y/400)) % 7) - 1]

Rust Equivalent

const DAYS: [&str; 7] = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"];

fn get_day_of_week(day: i32, mut month: i32, mut year: i32) -> String {
    if month < 3 {
        month += 12;
        year -= 1;
    }
    let d = day;
    let k = year % 100;
    let j = year / 100;
    let day_of_week = (d + ((13 * (month + 1)) / 5) + k + (k / 4) + (j / 4) + 5 * j) % 7;

    DAYS[(day_of_week + 6) as usize % 7].to_string()
}

fn main() {
println!("{}", get_day_of_week(1, 1, 2020));
}

Zeckendorf Representation

Zeckendorf's theorem states that every positive integer can be represented as the sum of 1 or more distinct nonconsecutive Fibonacci numbers. This representation is called the Zeckendorf representation. Create a function that accepts a integer and returns a list of the Zeckendorf representation of that number.

Examples

64 -> [55, 8, 1]
4 -> [3, 1]

Answer

Rust

fn get_fibonacci(n: usize) -> Vec<i64> {
    let mut numbers = vec![0i64, 1];
    while numbers.len() < n {
        let next_number = numbers[numbers.len() - 1] + numbers[numbers.len() - 2];
        numbers.push(next_number);
    }
    numbers
}
fn zeckendorf_representation(mut n: i64) -> Vec<i64> {
    let numbers = get_fibonacci(50); // 50 is basically enough, otherwise it will be too slow/overflow
    let mut result = Vec::new();
    let mut i = numbers.len() - 1;
    while n > 0 && i > 0 {
        if numbers[i] <= n {
            n -= numbers[i];
            result.push(numbers[i]);
        }
        if i > 0 { i -= 1; }
    }

    result
}

fn main() {
println!("{:?}", zeckendorf_representation(64));
println!("{:?}", zeckendorf_representation(4));
}

Python

def fib(n):
    l = []
    a, b = 0, 1
    while b < n:
        a, b = b, a+b
        l.append(a)
    return l

def zec(n):
    l = []
    nums = fib(n)
    while len(nums) > 0:
        if max(nums) <= n - sum(l):
            l.append(max(nums))
            nums.pop()
        else:
            nums.pop()
    return l

Lychrel Numbers

A lychrel number is a natural number that never forms a palindrome through the reverse and add process. The process is defined as follows:

1. Take an integer
2. Reverse the digits
3. Add the original number and the reversed number
4. Check if the sum is a palindrome
5. If the sum is not a palindrome, repeat the process with the sum

Example

47 -> 47 + 74 = 121 -> 121 is a palindrome, therefore 47 is not a lychrel number

Because this is an open problem, there is no known lychrel number. Therefore, you can assume that if the process reaches 50 iterations, the number is not a lychrel number.

Create a function that accepting a integer returns a boolean indicating if the number is a lychrel number.

Examples

196 -> True
47 -> False

Source

Project Euler - Problem 55

Answer

Rust

fn reverse_number(num: u128) -> u128 {
    num.to_string().chars().rev().collect::<String>().parse::<u128>().unwrap()
}

fn is_lychrel_number(n: u128) -> bool {
    let mut num = n;
    for _ in 0..50 {
        let rev_num = reverse_number(num);
        num += rev_num;
        if num == reverse_number(num) { 
            return false;
        }
    }
    true
}

fn main() {
println!("{}", is_lychrel_number(196)); // true
println!("{}", is_lychrel_number(47)); // false
}

Python

def lyc(num):
    rev = int("".join(reversed(str(num))))
    num += rev
    if "".join(reversed(str(num))) == str(num):
        return True
    else:
        try:
            lyc(num)
        except RecursionError:
            return False

Boomerang Numbers

Create a function that counts the "boomerangs" in an array where, given array x and index n, x[n] and x[n+2] are the same, but x[n+1] is different.

[1, 5, 1] -> 1
[1, 5, 1, 5, 1] -> 3

Examples

assert num_boomerangs([1, 5, 1, 5, 1]) == 3

Notes

• Boomerangs can overlap, and you must account for this.

Answers

Python

def b(arr):
    c = 0
    for i,j in enumerate(arr[:-2]):
        if j == arr[i+2] and not j == arr[i+1]:
            c += 1
    return c

Brainfuck Interpreter

Brainfuck is a esoteric programming language created by Urban Müller which consists of 8 basic commands.

Commands/Characters

Notes

• It is recommended to convert outputted bytes to ASCII, but is not required.
• You should handle cell wrapping, i.e handling cells that have values of below 0 or above 255

Resources

• Wikipedia

Answer

Rust

I think this one works right...

const PROGRAM: &str = r#"
    ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.
"#;
const INCREMENT_DATAPOINTER: char = '>';
const DECREMENT_DATAPOINTER: char = '<';
const INCREMENT_BYTE: char = '+';
const DECREMENT_BYTE: char = '-';
const OUTPUT_BYTE: char = '.';
const INPUT_BYTE: char = ',';
const JUMP_FORWARD: char = '[';
const JUMP_BACKWARD: char = ']';

enum Instruction {
    IncrementDataPointer,
    DecrementDataPointer,
    IncrementByte,
    DecrementByte,
    OutputByte,
    InputByte,
    JumpBlock(Vec<Instruction>),
}

fn parse<T: AsRef<str>>(input: T) -> Result<Vec<Instruction>, &'static str> {
    let mut instructions = Vec::new();
    let mut chars = input.as_ref().chars().peekable();
    while let Some(&c) = chars.peek() {
        match c {
            INCREMENT_DATAPOINTER => instructions.push(Instruction::IncrementDataPointer),
            DECREMENT_DATAPOINTER => instructions.push(Instruction::DecrementDataPointer),
            INCREMENT_BYTE => instructions.push(Instruction::IncrementByte),
            DECREMENT_BYTE => instructions.push(Instruction::DecrementByte),
            OUTPUT_BYTE => instructions.push(Instruction::OutputByte),
            INPUT_BYTE => instructions.push(Instruction::InputByte),
            JUMP_FORWARD => {
                chars.next();
                let mut block = Vec::new();
                while let Some(&c) = chars.peek() {
                    block.push(c);

                    if c == JUMP_BACKWARD {
                        break;
                    }
                    chars.next();
                }
    
                if block.last() != Some(&JUMP_BACKWARD) {
                    return Err("Expected ']' to close block");
                }

                let parsed_block = parse(block.iter().collect::<String>().as_str())?;
                instructions.push(Instruction::JumpBlock(parsed_block));
            }
            _ => (),
        }
        chars.next();
    }
    Ok(instructions)
}

fn process_instruction(instruction: &Instruction, data: &mut Vec<u8>, data_pointer: &mut usize) {
    match instruction {
        Instruction::IncrementDataPointer => increment_data_pointer(data_pointer),
        Instruction::DecrementDataPointer => decrement_data_pointer(data_pointer),
        Instruction::IncrementByte => increment_byte(data, *data_pointer),
        Instruction::DecrementByte => decrement_byte(data, *data_pointer),
        Instruction::OutputByte => output_byte(data, *data_pointer),
        Instruction::InputByte => input_byte(data, *data_pointer),
        Instruction::JumpBlock(ref block) => process_jump_block(block, data, data_pointer),
    }
}

fn increment_data_pointer(data_pointer: &mut usize) {
    *data_pointer += 1;
}

fn decrement_data_pointer(data_pointer: &mut usize) {
    if *data_pointer > 0 {
        *data_pointer -= 1;
    }
}

fn increment_byte(data: &mut Vec<u8>, data_pointer: usize) {
    data[data_pointer] += 1;
}

fn decrement_byte(data: &mut Vec<u8>, data_pointer: usize) {
    data[data_pointer] = data[data_pointer].saturating_sub(1);
}

fn output_byte(data: &mut Vec<u8>, data_pointer: usize) {
    print!("{}", data[data_pointer] as char);
}

fn input_byte(data: &mut Vec<u8>, data_pointer: usize) {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).unwrap();
    data[data_pointer] = input.chars().next().unwrap() as u8;
}

fn process_jump_block(block: &[Instruction], data: &mut Vec<u8>, data_pointer: &mut usize) {
    while data[*data_pointer] != 0 {
        for instruction in block {
            process_instruction(instruction, data, data_pointer);
        }
    }
}

fn evaluate(instructions: &[Instruction]) {
    let mut data: Vec<u8> = vec![0; 30000];
    let mut data_pointer = 0;
    let mut instruction_pointer = 0;

    while instruction_pointer < instructions.len() {
        process_instruction(&instructions[instruction_pointer], &mut data, &mut data_pointer);
        instruction_pointer += 1;
    }
}
fn main() {
    let instructions = parse(PROGRAM).unwrap();
    evaluate(&instructions);
}

Grouping Lists Based On Their Most Common Shared Element

Given a 2d array of lists, group the lists based on their most common element. If two lists have the same most common element, they should be grouped together. For example, if [1, 2, 3] and [3, 4] have the same most common element, they should be grouped together based on that element (3). The output should be a dictionary (or hashmap) where the keys represent the most common element and the values are the lists that contain that element. Each list will only be in one grouping.

Test Case

// input:
[
    ["red", "green"],
    ["red", "blue"],
    ["red"],
    ["green", "blue"],
    ["blue", "yellow"],
    ["yellow"],
    ["yellow"],
    ["yellow", "red"],
    ["red"],
    ["green", "red"],
    ["red", "green"],
];

// output: 
{
    "yellow": [["blue", "yellow"], ["yellow"], ["yellow"]], 
    "green": [["green", "blue"]], 
    "red": [["red", "green"], ["red", "blue"], ["red"], ["yellow", "red"], ["red"], ["green", "red"], ["red", "green"]], 
    "blue": [] 
    // no lists have blue as the most common element,
    // because the lists that contain blue contain other elements that are more common
    // however if you just had a list with ["blue"] in it, it would be in this list as 
    // blue: [["blue"]] as that would be the most common element globally that is also in that list
}

Answer

Rust

use std::{collections::HashMap, hash::Hash};
fn group_by_most_common_element<T: Hash + Eq + Copy>(
    lists: Vec<Vec<T>>,
) -> HashMap<T, Vec<Vec<T>>> {
    // A global count of each element that i can refer back to
    let mut element_count = HashMap::new(); 
    // The final result map
    let mut result_map: HashMap<T, Vec<Vec<T>>> = HashMap::new(); 

    for list in &lists {
        for &element in list {
            // count each occurance of each element contained in list.
            *element_count.entry(element).or_insert(0) += 1;
        }
    }

    // represent all elements in the result map
    // even if they dont actually exist
    for &element in element_count.keys() {
        result_map.entry(element).or_default();
    }

    for list in lists {
        if let Some(most_common_element) = list
            .iter()
            // Find the most common element in the list based on the global count
            .max_by_key(|&element| element_count.get(element).unwrap_or(&0))
        {
            result_map
                // create a new element in the result map with the found most common element
                .entry(*most_common_element) 
                .or_default()
                // pushes the list to the array if it exists, or it creates one then pushes it on too.
                .push(list); 
        }
    }

    result_map
}
fn main() {
    let list: Vec<Vec<&str>> = vec![
        vec!["red", "green"],
        vec!["red", "blue"],
        vec!["red"],
        vec!["green", "blue"],
        vec!["blue", "yellow"],
        vec!["yellow"],
        vec!["yellow"],
        vec!["yellow", "red"],
        vec!["red"],
        vec!["green", "red"],
        vec!["red", "green"],
    ];
    let map = group_by_most_common_element(list);
    println!("{:?}", map);
}

Pascal's Triangle

Pascal's triangle is a triangular array of binomial coefficients, named after the famous French mathematician Blaise Pascal. It is constructed by summing the two numbers directly above it. The numbers at the edges of the triangle are always one, and all other numbers can be determined by the sum.

Create a function that takes an integer n and returns the nth row of Pascal's triangle. You can assume that the nth row is greater than or equal to 0. You do not have to print the triangle, just return a 2d array.

Example

1 
1 1 
1 (1+1) 1
1 (1+2) (2+1) 1
1 (1+3) (3+3) (3+1) 1

    1
   1 1
  1 2 1
 1 3 3 1

By Hersfold on the English Wikipedia - Own work, Public Domain, here

Answer

Rust

fn pascals_triangle(depth: usize) -> Vec<Vec<usize>> {
    let mut triangle = vec![vec![0; depth]; depth];
    for i in 0..depth {
        triangle[i][0] = 1;
        triangle[i][i] = 1; // the edge bits...
        for j in 1..i {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
    }
    triangle
}
fn main() {
    let depth = 5;
    let triangle = pascals_triangle(depth);
    for row in triangle {
      for num in row {
            if num == 0 { // as the triangle is a square initialized with 0s
               break;
            }
          print!("{} ", num);
      }
      println!();
    }
}

Perfect Numbers

A perfect number is a number that can be formed by adding its proper divisors (excluding itself). Create a function that accepts a number and returns True if the number is a perfect number, and False if it is not.

Example

* A proper divisor is a positive divisor that is not the number itself.

Answer

Rust

fn is_perfect_number(n: i32) -> bool {
    let sum: i32 = (1..n).filter(|x| n % x == 0).sum();
    sum == n
}

// no builtins  
/*fn is_perfect_number(n: i32) -> bool {
    let mut sum = 0;
    for i in 1..n {
        if n % i == 0 {
            sum += i;
        }
    }
    sum == n
}*/
fn main() {
println!("{}", is_perfect_number(6)); // true
println!("{}", is_perfect_number(28)); // true
println!("{}", is_perfect_number(7)); // false
}

ASCII Art/PNG Parsing

In this challenge, you will be creating a program that can accept a path to a PNG file, and then convert that PNG file into ASCII art. The art should be displayed in the console. You decide what the output to the console should look like, but it should still be recognisable to the original image.

For beginners, you may use a library to parse the PNG file; however, more advanced programmers should try to parse the PNG file themselves.

Answer

JavaScript

const fs = require('fs');
const zlib = require('zlib');

// Based on the PNG file format specification: https://www.w3.org/TR/PNG/
class PNG {
    buffer = null;
    width = 0;
    height = 0;
    bitDepth = 0;
    colorType = 0;
    compressionMethod = 0;
    filterMethod = 0;
    interlaceMethod = 0;

    chunks = [];
    data = [];

    constructor(imageBuffer) {
        if (!imageBuffer || imageBuffer.length < 8) {
            throw new Error('Invalid PNG file');
        }

        this.buffer = imageBuffer;
        this.parse();
    }

    parseIHDR() {
        const ihdr = this.chunks.find(chunk => chunk.type === 'IHDR');
        if (!ihdr) {
            throw new Error('IHDR chunk not found, This is not a valid PNG file');
        }

        this.width = ihdr.data.readUInt32BE(0);
        this.height = ihdr.data.readUInt32BE(4);
        this.bitDepth = ihdr.data.readUInt8(8);
        this.colorType = ihdr.data.readUInt8(9);
        this.compressionMethod = ihdr.data.readUInt8(10);
        this.filterMethod = ihdr.data.readUInt8(11);
        this.interlaceMethod = ihdr.data.readUInt8(12);
    }

    parseHeader() {
        const header = this.buffer.slice(0, 8);

        if (header.toString('hex') !== '89504e470d0a1a0a') {
            throw new Error('Invalid PNG signature');
        }
    }

    chunker() {
        let i = 8; // Skip the header
        while (i < this.buffer.length) {
            const length = this.buffer.readUInt32BE(i);
            const type = this.buffer.slice(i + 4, i + 8).toString('ascii');
            const data = this.buffer.slice(i + 8, i + 8 + length);
            const crc = this.buffer.readUInt32BE(i + 8 + length);
            this.chunks.push({ length, type, data, crc });
            i += 12 + length;
        }
    }

    // Start to parse the image data chuck!
    parseIDAT() {
        // As image data can be split into multiple IDAT chunks
        // we need to concatenate them all
        const idatChunks = this.chunks.filter(chunk => chunk.type === 'IDAT');
        const idatData = Buffer.concat(idatChunks.map(chunk => chunk.data));

        if (!idatData) {
            throw new Error('IDAT chunk not found, This is not a valid PNG file');
        }

        if (this.colorType !== 6) {
            throw new Error('Only RGBA color type is supported currently.');
        }

        const decompressedData = zlib.inflateSync(idatData);

        const data = [];
        let i = 0;
        for (let y = 0; y < this.height; y++) {
            const filterType = decompressedData.readUInt8(i);
            i++;
            for (let x = 0; x < this.width; x++) {
                let red = decompressedData.readUInt8(i);
                let green = decompressedData.readUInt8(i + 1);
                let blue = decompressedData.readUInt8(i + 2);
                let alpha = decompressedData.readUInt8(i + 3);

                if (x !== 0 || y !== 0) {
                    let left = x !== 0 ? data[data.length - 1] : { red: 0, green: 0, blue: 0, alpha: 0 };
                    let above = y !== 0 ? data[data.length - this.width] : { red: 0, green: 0, blue: 0, alpha: 0 };
                    let aboveLeft = x !== 0 && y !== 0 ? data[data.length - this.width - 1] : { red: 0, green: 0, blue: 0, alpha: 0 };

                    if (filterType === 4) {
                        console.log(filterType);
                    }
                    switch (filterType) {
                        case 0: // None
                            break;
                        case 1: // Sub
                            red += left.red;
                            green += left.green;
                            blue += left.blue;
                            alpha += left.alpha;
                            break;
                        case 2: // Up
                            red += above.red;
                            green += above.green;
                            blue += above.blue;
                            alpha += above.alpha;
                            break;
                        case 3: // Average
                            red += Math.floor((left.red + above.red) / 2);
                            green += Math.floor((left.green + above.green) / 2);
                            blue += Math.floor((left.blue + above.blue) / 2);
                            alpha += Math.floor((left.alpha + above.alpha) / 2);
                            break;
                        case 4: // Paeth
                            red += this.paethPredictor(left.red, above.red, aboveLeft.red);
                            green += this.paethPredictor(left.green, above.green, aboveLeft.green);
                            blue += this.paethPredictor(left.blue, above.blue, aboveLeft.blue);
                            alpha += this.paethPredictor(left.alpha, above.alpha, aboveLeft.alpha);
                            break;
                    }
                }

                data.push({ red: red & 0xFF, green: green & 0xFF, blue: blue & 0xFF, alpha: alpha & 0xFF });
                i += 4;
            }
        }

        this.data = data;
    }

    paethPredictor(a, b, c) {
        const p = a + b - c;
        const pa = Math.abs(p - a);
        const pb = Math.abs(p - b);
        const pc = Math.abs(p - c);

        if (pa <= pb && pa <= pc) return a;
        else if (pb <= pc) return b;
        else return c;
    }

    parse() {
        this.parseHeader();
        this.chunker();
        this.parseIHDR();
        console.log(this.width, this.height, this.bitDepth, this.colorType, this.compressionMethod, this.filterMethod, this.interlaceMethod);

        if (this.interlaceMethod !== 0) {
            throw new Error('Interlaced images are not yet supported');
        }

        this.parseIDAT();

        return this.data;
    }

    // given a width and height, resize the image using nearest neighbor interpolation
    resize(width, height) {
        let resizedData = [];
        let xRatio = this.width / width;
        let yRatio = this.height / height;

        for (let y = 0; y < height; y++) {
            for (let x = 0; x < width; x++) {
                let pixel = this.data[Math.floor(y * yRatio) * this.width + Math.floor(x * xRatio)];
                resizedData.push(pixel);
            }
        }

        this.width = width;
        this.height = height;
        this.data = resizedData;
    }
}

function createSizedPNGType(imagePath, maxWidth = 30, maxHeight = 20) {
    const imageBuffer = fs.readFileSync(imagePath);
    const png = new PNG(imageBuffer);

    if (png.height > maxHeight) {
        const ratio = maxHeight / png.height;
        png.resize(Math.floor(png.width * ratio), maxHeight);
    }

    if (png.width > maxWidth) {
        const ratio = maxWidth / png.width;
        png.resize(maxWidth, Math.floor(png.height * ratio));
    }

    return png;
}

function printPNGImagePathAsAscii(imagePath) {
    const png = createSizedPNGType(imagePath);
    const { data, width, height } = png;
    const chars = ['.', '+', '*', '#', '@'];
    
    let ascii = '';
    for (let y = 0; y < height; y++) {
        for (let x = 0; x < width; x++) {
            const pixel = data[y * width + x];

            // represent it as a range from 0 to chars.length
            // i got this formula from https://stackoverflow.com/questions/596216/formula-to-determine-brightness-of-rgb-color
            const luminance = ((0.299 * pixel.red + 0.587 * pixel.green + 0.114 * pixel.blue) / 255) * chars.length; 
    

            if (pixel.alpha === 0) {
                ascii += ' ';
            } else {
                ascii += chars[Math.floor(luminance)];
            }
        }
        ascii += '\n';
    }
    console.log(ascii);
}

#printPNGImagePathAsAscii('image.png');

Merge Intervals

Create a function that accepts a list of intervals as input and return a list of intervals where the overlapping intervals are merged into one.

Example

Input: [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

Source

LeetCode

Answer

Rust

use std::collections::HashMap;
fn merge_intervals(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    if intervals.is_empty() {
        return vec![];
    }

    intervals.sort_unstable_by(|a, b| a[0].cmp(&b[0]));
    let mut result = Vec::new();
    let mut current_interval = intervals[0].clone();

    for interval in intervals.into_iter().skip(1) {
        if interval[0] <= current_interval[1] {
            current_interval[1] = current_interval[1].max(interval[1]);
        } else {
            result.push(current_interval);
            current_interval = interval;
        }
    }

    result.push(current_interval);
    result
}
fn main() {
    let intervals = vec![vec![1, 3], vec![2, 6], vec![8, 10], vec![15, 18]];
    let result = merge_intervals(intervals.clone()); // just clone them rn bc im lazy
    println!("{:?} === {:?}", intervals, result);
}

Edit Distance

Create a function that accepts two strings and returns the minimum number of operations needed to transform one. The operations are: insert, delete, and replace.

Example

Input: "kitten", "sitting"
Output: 3

Answer

Rust

use std::cmp::min;
fn levenshtein_distance(s1: &str, s2: &str) -> usize {
    let (len_s1, len_s2) = (s1.len(), s2.len());
    let mut cache = vec![vec![0; len_s2 + 1]; len_s1 + 1];

    (0..=len_s1).for_each(|i| cache[i][0] = i);
    (0..=len_s2).for_each(|j| cache[0][j] = j);

    for (i, char_s1) in s1.chars().enumerate() {
        for (j, char_s2) in s2.chars().enumerate() {
            let cost = if char_s1 == char_s2 { 0 } else { 1 };
            cache[i + 1][j + 1] = min(
                min(cache[i][j + 1] + 1, cache[i + 1][j] + 1),
                cache[i][j] + cost,
            );
        }
    }

    cache[len_s1][len_s2]
}
fn main() {
    let str1 = "kitten";
    let str2 = "sitting";
    let distance = levenshtein_distance(str1, str2);

    println!(
        "The edit distance between '{}' and '{}' is: {}",
        str1, str2, distance
    );
}

Error Correcting Codes

Implement a error correction code using any way you'd like, you may use a algorithm. It should be able to correct atleast a single bit error while still returning the original data

Example

data = [1, 0, 1, 0]
corrupted = (flip a random bit in data)
decoded = [1, 0, 1, 0]

Answer

Rust

fn hamming_encode(data: [i32; 4]) -> [i32; 7] {
    let p = [
        data[0] ^ data[1] ^ data[3],
        data[0] ^ data[2] ^ data[3],
        data[1] ^ data[2] ^ data[3],
    ];
    [p[0], p[1], data[0], p[2], data[1], data[2], data[3]]
}

fn hamming_decode(mut encoded: [i32; 7]) -> [i32; 4] {
    let s = [
        encoded[0] ^ encoded[2] ^ encoded[4] ^ encoded[6],
        encoded[1] ^ encoded[2] ^ encoded[5] ^ encoded[6],
        encoded[3] ^ encoded[4] ^ encoded[5] ^ encoded[6],
    ];
    let error_position = s[0] + (s[1] << 1) + (s[2] << 2);

    if error_position != 0 {
        encoded[(error_position - 1) as usize] ^= 1;
    }

    [encoded[2], encoded[4], encoded[5], encoded[6]]
}
fn main() {
    let data = [1, 0, 1, 0];
    println!("Inputed Data: {:?}", data);
    let encoded = hamming_encode(data);
    println!("Encoded Data: {:?}", encoded);
    let mut encoded = encoded;
    encoded[3] = encoded[3] ^ 1;
    println!("Corrupt Data: {:?}", encoded);
    let decoded = hamming_decode(encoded);
    println!("Decoded Data: {:?}", decoded);
    assert_eq!(decoded, data, "Data is not the same");
}

Cash To Coins

Create a function that accepts a float value representing a amount of money (Ex: $2.75) and returns a the number of each coins/dollars required to make that amount of money. It should always return the smallest number of coins/dollars possible.

cash_to_coins(2.75) -> {
    "dollars": 2,
    "quarters": 3,
    "dimes": 0,
    "nickels": 0,
    "pennies": 0
}

cash_to_coins(0.99) -> {
    "dollars": 0,
    "quarters": 3,
    "dimes": 2,
    "nickels": 0,
    "pennies": 4
}

cash_to_coins(100.75) -> {
    "dollars": 100,
    "quarters": 3,
    "dimes": 0,
    "nickels": 0,
    "pennies": 0
}

Answer

Rust

#[derive(Debug)]
struct Wallet {
    dollars: i32,
    quarters: i32,
    dimes: i32,
    nickels: i32,
    pennies: i32,
}

fn cash_to_coins(cash: f64) -> Wallet {
    let dollars: i32 = cash as i32;
    let mut fractional = cash.fract();

    let quarters = (fractional / 0.25).floor() as i32;
    fractional %= 0.25; // ex: 0.76 % 0.25 = 0.01 which is the remaining cash after
                        // just repeat over and over 💀

    let dimes = (fractional / 0.10).floor() as i32;
    fractional %= 0.10;

    let nickels = (fractional / 0.05).floor() as i32;
    fractional %= 0.05;

    let pennies = (fractional / 0.01).floor() as i32;

    Wallet {
        dollars,
        quarters,
        dimes,
        nickels,
        pennies,
    }
}
fn main() {
    println!("{:?}", cash_to_coins(2.75));
    println!("{:?}", cash_to_coins(0.99));
    println!("{:?}", cash_to_coins(100.75));
}

Morse Code Translator

Write two functions, one to encode a string to Morse code, and another to decode Morse code back to a string. The Morse code table is provided below as a dictionary.

morse_code = {
  'A': '.-', 'B': '-...', 'C': '-.-.', 'D': '-..', 'E': '.', 'F': '..-.',
  'G': '--.', 'H': '....', 'I': '..', 'J': '.---', 'K': '-.-', 'L': '.-..',
  'M': '--', 'N': '-.', 'O': '---', 'P': '.--.', 'Q': '--.-', 'R': '.-.',
  'S': '...', 'T': '-', 'U': '..-', 'V': '...-', 'W': '.--', 'X': '-..-',
  'Y': '-.--', 'Z': '--..', ' ': ' ', '0': '-----',
  '1': '.----', '2': '..---', '3': '...--', '4': '....-', '5': '.....',
  '6': '-....', '7': '--...', '8': '---..', '9': '----.',
  '&': '.-...', "'": '.----.', '@': '.--.-.', ')': '-.--.-', '(': '-.--.',
  ':': '---...', ',': '--..--', '=': '-...-', '!': '-.-.--', '.': '.-.-.-',
  '-': '-....-', '+': '.-.-.', '"': '.-..-.', '?': '..--..', '/': '-..-.'
}

encodeMorse('Hello World!'); // .... . .-.. .-.. ---   .-- --- .-. .-.. -.. -.-.--
decodeMorse('.... . .-.. .-.. ---   .-- --- .-. .-.. -.. -.-.--'); // HELLO WORLD!

Idea from:

Edabit

Answer

Javascript

const morse_code = {
    'A': '.-', 'B': '-...', 'C': '-.-.', 'D': '-..', 'E': '.', 'F': '..-.',
    'G': '--.', 'H': '....', 'I': '..', 'J': '.---', 'K': '-.-', 'L': '.-..',
    'M': '--', 'N': '-.', 'O': '---', 'P': '.--.', 'Q': '--.-', 'R': '.-.',
    'S': '...', 'T': '-', 'U': '..-', 'V': '...-', 'W': '.--', 'X': '-..-',
    'Y': '-.--', 'Z': '--..', ' ': ' ', '0': '-----',
    '1': '.----', '2': '..---', '3': '...--', '4': '....-', '5': '.....',
    '6': '-....', '7': '--...', '8': '---..', '9': '----.',
    '&': '.-...', "'": '.----.', '@': '.--.-.', ')': '-.--.-', '(': '-.--.',
    ':': '---...', ',': '--..--', '=': '-...-', '!': '-.-.--', '.': '.-.-.-',
    '-': '-....-', '+': '.-.-.', '"': '.-..-.', '?': '..--..', '/': '-..-.'
};

function encodeMorse(str) {
    return str.split('').map(char => morse_code[char.toUpperCase()] ?? '').join(' ');
}

function decodeMorse(str) {
    return str.split('   ').map(word => // looking for 3+ spaces for word separation
        word.split(' ').map(char => 
            Object.keys(morse_code).find(key => morse_code[key] === char) || ' '
        ).join('')
    ).join(' ');
}

Prime Number Factorization

Prime factorization is essential for cryptographic algorithms, and other applications. The goal is to produce a list of the smallest prime numbers that when multiplied produce the original number. For example:

84 -> [2, 2, 3, 7]
64 -> [2, 2, 2, 2, 2, 2]
83 -> [83] (it is prime)

Answer

Javascript

function prime_factor(n) {
    let factors = [];
    
    if (n <= 1) {
        return factors;
    }

    // while the factor is even, 
    // 2 is always the smallest prime number
    while (n % 2 === 0) {
        factors.push(2);
        n /= 2;
    }

    for (let i = 3; i <= Math.sqrt(n); i += 2) {
        while (n % i === 0) {
            factors.push(i);
            n /= i;
        }
    }

    // the remaining number is prime if it is greater than 2
    if (n > 2) { 
        factors.push(n);
    }

    return factors;
}