Common Algorithms

The code published on this page is provided with the conditions of the MIT license.

Arbitrary Number Base Conversion

TODO: This version converts to and from base-[2-10], but doesn't support input validation. Hexadecimal and base64 should be supported as well.

JavaScript

function baseNToBaseTen(inputValue, inputBase) {
    var inputValueStr = inputValue.toString();
    var sum = 0;
    for (var i=inputValueStr.length-1; i>=0; i--) {
        sum += Number(inputValueStr[i])*Math.pow(inputBase,inputValueStr.length-1-i);
    }
    return sum;
}
function convertInputValue(inputValue,inputBase,outputBase)
{
    var resultText = "";
    var quot=inputValue, rem=0, rounded=Math.floor(inputValue);
    if (inputBase === 10) {
        while (rounded > 0) {
            rem = rounded % outputBase;
            resultText = rem.toString() + resultText;
            quot = quot / outputBase;
            rounded = Math.floor(quot);
        }
    } else {
        var bTenValue = baseNToBaseTen(inputValue, inputBase)
        if (outputBase === 10) {
            resultText = bTenValue.toString();
        } else {
            convertInputValue(bTenValue, 10, outputBase);
        }
    }
    return resultText;
}

Integer to Words

This converts an integer into English words. Solving this problem was an interesting exercise, as I ended up parsing in 3 stages which were: splitting the digit groups, inserting symbols for base 10 exponents and ampersands after groups of hundreds, and then converting the symbols into words.

I initially started my implementation in Java, then after finishing, moved onto C++. The Rust version was the most difficult, as, of time of writing it, I was still fairly new to the language.

Java

package com.bgcottrell;

import java.util.*;

public class Main {
    public static String[] E0Literals = "zero,one,two,three,four,five,six,seven,eight,nine".split(",");
    public static String[] TNLiterals = "eleven,twelve,thirteen,fourteen,fifteen,sixteen,seventeen,eighteen,nineteen".split(",");
    public static String[] E1Literals = "ten,twenty,thirty,forty,fifty,sixty,seventy,eighty,ninety".split(",");
    public static String parseIntString(String strValue)
    {
        StringBuilder result = new StringBuilder();
        Long parsedValue = 0L;
        //int r = 0;
        try {
            parsedValue = Long.parseUnsignedLong(strValue);
            //r = strValue.length();
        } catch (NumberFormatException e) {
            throw new RuntimeException(e);
        }
        // Split with commas
        int numCommas = (int)Math.ceil((double) strValue.length() /6);
        StringBuilder tokens = new StringBuilder(strValue.length() + numCommas);
        if (strValue.length() < 4) {
            for (int i = strValue.length() - 1; i >= 0; i--) {
                tokens.insert(0, strValue.charAt(i));
            }
        } else {
            for (int i = strValue.length() - 1; i >= 0; i--) {
                tokens.insert(0, strValue.charAt(i));
                if ((strValue.length() - i) % 3 == 0 && (i > 0)) {
                    tokens.insert(0, ',');
                }
            }
        }
        System.out.printf("(%s) ",tokens);

        // Parse, insert exponents, hundred's joiners
        String groups[] = tokens.toString().split(",");
        ArrayList<String> parserTokens = new ArrayList<>();
        for (int gi=0; gi < groups.length; gi++) {
            switch (groups[gi].length()) {
                case 3: {
                    Integer p[] = {
                            Integer.parseUnsignedInt(String.valueOf(groups[gi].charAt(0))),
                            Integer.parseUnsignedInt(groups[gi].substring(1)),
                    };
                    if (p[0] != 0) {
                        parserTokens.add(E0Literals[p[0]]);
                        parserTokens.add("H");
                    }
                    if (p[1] != 0 && p[1] < 10) {
                        parserTokens.add("&");
                        parserTokens.add(E0Literals[p[1]]);
                    } else if (p[1] != 0 && p[1] < 20) {
                        parserTokens.add("&");
                        parserTokens.add(TNLiterals[p[1] - 11]);
                    } else {
                        if (groups[gi].charAt(1) != '0') {
                            parserTokens.add("&");
                            parserTokens.add(
                                    E1Literals[Integer.parseUnsignedInt(String.valueOf(groups[gi].charAt(1))) - 1]
                            );
                        }
                        if (groups[gi].charAt(2) != '0') {
                            parserTokens.add(
                                E0Literals[Integer.parseUnsignedInt(String.valueOf(groups[gi].charAt(2)))]
                            );
                        }
                    }
                    break;
                }
                case 2:
                {
                    Integer p = Integer.parseUnsignedInt(groups[gi]);
                    if (p < 10) {
                        parserTokens.add(E0Literals[p]);
                    } else if (p < 20) {
                        parserTokens.add(TNLiterals[p - 11]);
                    } else {
                        parserTokens.add(
                                E1Literals[Integer.parseUnsignedInt(String.valueOf(groups[gi].charAt(0))) - 1]
                        );
                        if (groups[gi].charAt(1) != '0') {
                            parserTokens.add(
                                    E0Literals[Integer.parseUnsignedInt(String.valueOf(groups[gi].charAt(1)))]
                            );
                        }
                    }
                    break;
                }
                case 1: {
                    Integer p = Integer.parseUnsignedInt(groups[gi]);
                    parserTokens.add(E0Literals[p]);
                }
            }
            if (gi == groups.length - 2 && groups[gi] != "000") {
                parserTokens.add("T");
            } else if (gi == groups.length - 3) {
                parserTokens.add("M");
            } else if (gi == groups.length - 4) {
                parserTokens.add("B");
            }
        }
        //System.out.printf("Parsed: %s", parserTokens);
        for (int i =0; i < parserTokens.size() - 1;i++) {
            switch (parserTokens.get(i)) {
                case "H":
                    result.append("hundred");
                    break;
                case "T":
                    result.append("thousand");
                    break;
                case "M":
                    result.append("million");
                    break;
                case "B":
                    result.append("billion");
                    break;
                case "&":
                    result.append("and");
                    break;
                default:
                    result.append(parserTokens.get(i));
            }
            result.append(" ");
        }
        switch (parserTokens.getLast()) {
            case "H":
                result.append("hundred");
                break;
            case "T":
                result.append("thousand");
                break;
            case "M":
                result.append("million");
                break;
            case "B":
                result.append("billion");
            case "&":
                result.append("and");
            default:
                result.append(parserTokens.getLast());
        }
        return result.toString();
    }
}

C++17

#include <cmath>
#include <iostream>
#include <iomanip>
#include <vector>
#include <ranges>
#include <string_view>
#include <algorithm>
#include <format>
static string IntToWords(const string& input)
{
    static array E0Literals = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    static array TNLiterals = {"eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};
    static array E1Literals = {"ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};
    string result;
    try {
        ulong parsedValue = stoul(input);
    } catch (const exception& ex) {
        return "invalid";
    }
    // Split with commas, make it easier to parse
    const auto numCommas = int(ceil(input.length()/6));
    string tokens;
    tokens.reserve(input.length()+numCommas);
    if (input.length() < 4) {
        for (int i=input.length()-1;i>=0;i--) {
            tokens.insert(tokens.begin(), input.at(i));
        }
    } else {
        for (int i=input.length()-1;i>=0;i--) {
            tokens.insert(tokens.begin(),input.at(i));
            if ((input.length() -i) % 3 == 0) {
                tokens.insert(tokens.begin(),',');
            }
        }
    }
    // Parse, insert exponents, joiners
    vector<string> groups = split(tokens, ",");
    vector<string> parserTokens;
    parserTokens.reserve(input.length()*2);
    for (size_t gi=0; gi != groups.size(); gi++) {
        switch (groups[gi].length()) {
        case 3:
        {
            vector<int> p = {
                stoi(groups[gi].substr(0,1)),
                stoi(groups[gi].substr(1))
            };
            if (p[0] != 0) {
                parserTokens.push_back(E0Literals[p[0]]);
                parserTokens.push_back("H");
            }
            if (p[1] != 0 && p[1] < 10) {
                parserTokens.push_back("&");
                parserTokens.push_back(E0Literals[p[1]]);
            } else if (p[1] != 0 && p[1] < 20) {
                parserTokens.push_back("&");
                parserTokens.push_back(TNLiterals[p[1]-11]);
            } else {
                if (groups[gi].at(1) != '0') {
                    parserTokens.push_back("&");
                    parserTokens.push_back(
                        E1Literals[stoi(groups[gi].substr(1,1))-1]
                    );
                }
                if (groups[gi].at(2) != '0') {
                    parserTokens.push_back(
                        E0Literals[stoi(groups[gi].substr(2,1))]
                    );
                }
            }
            break;
        }
        case 2:
        {
            int p = stoi(groups[gi]);
            if (p < 10) {
                parserTokens.push_back(E0Literals[p]);
            } else if (p < 20) {
                parserTokens.push_back(TNLiterals[p-11]);
            } else {
                parserTokens.push_back(
                    E1Literals[stoi(groups[gi].substr(0,1))-1]
                );
                if (groups[gi].at(1) != '0') {
                    parserTokens.push_back(
                        E0Literals[stoi(groups[gi].substr(1,1))]
                    );
                }
            }
            break;
        }
        case 1:
        {
            int p = stoi(groups[gi]);
            parserTokens.push_back(E0Literals[p]);
            break;
        }
        } /* switch */
        if (gi == groups.size() - 2 && groups[gi] != "000") {
            parserTokens.push_back("T");
        } else if (gi == groups.size() - 3) {
            parserTokens.push_back("M");
        } else if (gi == groups.size() - 4) {
            parserTokens.push_back("B");
        } else if (gi == groups.size() - 5) {
            parserTokens.push_back("Tr");
        }
        } /* for */
        for (int i=0; i < parserTokens.size() - 1; i++) {
            string s = parserTokens.at(i);
            if (s == "H") {
                result.append("hundred");
            } else if (s == "T") {
                result.append("thousand");
            } else if (s == "M") {
                result.append("million");
            } else if (s == "B") {
                result.append("billion");
            } else if (s == "Tr") {
                result.append("trillion");
            } else if (s == "&") {
                result.append("and");
            } else {
                result.append(s);
            }
            result.append(" ");
        }
        auto s = parserTokens.back();
        if (s == "H") {
            result.append("hundred");
        } else if (s == "T") {
            result.append("thousand");
        } else if (s == "M") {
            result.append("million");
        } else if (s == "B") {
            result.append("billion");
        } else if (s == "Tr") {
            result.append("trillion");
        } else if (s == "&") {
            result.append("and");
        } else {
            result.append(s);
        }
    return result;
}

Rust

use std::iter::Iterator;
use std::ops::Deref;
use std::str::FromStr;
struct IntToWords;
impl IntToWords
{
    // Using Option, because I cannot figure out how to return generic errors
    pub fn parse_value(&self, input: &str) -> Option<String>
    {
        let E0Literals: Vec<&'static str> = "zero,one,two,three,four,five,six,seven,eight,nine,ten".split(',').collect();
        let TNLiterals: Vec<&'static str> = "eleven,twelve,thirteen,fourteen,fifteen,sixteen,seventeen,eighteen,nineteen".split(',').collect();
        let E1Literals: Vec<&'static str> = "ten,twenty,thirty,forty,fifty,sixty,seventy,eighty,ninety".split(',').collect();
        let mut result: String = String::from("");
        let parsed_value = u64::from_str(input);
        if parsed_value.is_err() {
            return Some(String::from("invalid"));
        }
        let num_commas = (input.len() as f32/6.0).ceil();
        // Split into digit groups
        let mut tokens: String = "".to_string();
        tokens.reserve(input.len()+num_commas as usize);
        if input.len() < 4 {
            let mut i = input.len()-1;
            loop {
                tokens.insert(0, input.chars().nth(i).unwrap());
                if i > 0 { i -= 1; } else { break; }
            }
        } else {
            let mut i = input.len()-1;
            loop {
                tokens.insert(0,input.chars().nth(i).unwrap());
                if i > 0 && (input.len()-i) % 3 == 0 {
                    tokens.insert(0,',');
                }
                if i > 0 { i -= 1; } else { break; }
            }
        }
        // Parse the digit groups
        let groups : Vec<&str> = tokens.split(',').collect();
        let mut parser_tokens:Vec<&str> = Vec::new();
        for gi in 0..groups.len() {
            match groups[gi].len() {
                3 => {
                    let p = [
                        usize::from_str(&groups[gi].chars().as_str()[0..1]).unwrap(),
                        usize::from_str(&groups[gi].chars().as_str()[1..]).unwrap()
                    ];
                    let p1 = (p[1] as f32/10_f32).floor() as u32;
                    let p2 = p[1] as u32 - (p1 as u32 * 10);
                    if p[0] != 0 {
                        parser_tokens.push(E0Literals[p[0]]);
                        parser_tokens.push("H");
                    }
                    if p[1] != 0 && p[1] <= 10 {
                        parser_tokens.push("&");
                        parser_tokens.push(E0Literals[p[1]]);
                    } else if p[1] != 0 && p[1] < 20 {
                        parser_tokens.push("&");
                        parser_tokens.push(TNLiterals[p[1] - 11]);
                    } else {
                        if groups[gi].chars().nth(1).unwrap() != '0' {
                            parser_tokens.push("&");
                            parser_tokens.push(
                                E1Literals[p1 as usize - 1]
                            );
                        }
                        if groups[gi].chars().nth(2).unwrap() != '0' {
                            parser_tokens.push(
                                E0Literals[p2 as usize]
                            );
                        }
                    }
                }
                2 => {
                    let p = usize::from_str(&groups[gi]).unwrap();
                    let p1 = (p as f32/10_f32).floor() as u32;
                    let p2 = p as u32 - (p1 * 10);
                    if p <= 10 {
                        parser_tokens.push(E0Literals[p]);
                    } else if p < 20 {
                        parser_tokens.push(TNLiterals[p - 11]);
                    } else {
                        parser_tokens.push(
                            E1Literals[p1 as usize-1]
                        );
                        if groups[gi].chars().nth(1).unwrap() != '0' {
                            parser_tokens.push(
                                E0Literals[p2 as usize]
                            );
                        }
                    }
                }
                1 => {
                    let p = usize::from_str(groups[gi]).unwrap();
                    parser_tokens.push(E0Literals[p]);
                }
                _ => {}
            } /* match */
            if groups.len() >= 2 && gi == groups.len() - 2 && groups[gi] != "000" {
                parser_tokens.push("T");
            } else if groups.len() >= 3 && gi == groups.len() - 3 {
                parser_tokens.push("M");
            } else if groups.len() >= 4 && gi == groups.len() - 4 {
                parser_tokens.push("B");
            } else if groups.len() >= 5 && gi == groups.len() - 5 {
                parser_tokens.push("Tr");
            }
        }
        // Convert tokens to words
        for i in 0..parser_tokens.len() {
            let s = parser_tokens[i];
            result.push_str(match s {
                "H" => "hundred",
                "T" => "thousand",
                "M" => "million",
                "B" => "billion",
                "Tr" => "trillion",
                "&" => "and",
                _ => s
            });
            result.push_str(" ");
        }
        Some(result)
    }
}

pub fn main() {
    let instance: IntToWords = IntToWords { };
    let test_numbers: Vec<&str> = Vec::from(["1001","10101010","1100001","1110001","26","13","210"]);
    for n in test_numbers {
        println!("{:-15}: {}", n, instance.parse_value(n).unwrap());
    }
}