Java practicing algorithms on Codewars.

+0_algo4j.md

Algorithms for Java

Java algorithm practice from Codewars site, wrote by me.

Here's my mainpage: ldcc.

Kind of fun, here we go!

Srot

• Problem: Srot the inner ctonnet in dsnnieedcg oredr

• Solution: Srot Ctonnet

Abbreviation Terminology

• Problem: Word a10n (abbreviation)

• Solution: Abbreviator

Alternating Split

• Problem: Simple Encryption #1 - Alternating Split

• Solution: Alt Split

Column Title

• Problem: Get the Excel column title!

• Solution: Column Title

Resistor Color Codes

• Problem: Resistor Color Codes, Part 2

• Solution: Resistor Color

Perimeter of squares in a rectangle

• Problem: Perimeter of squares in a rectangle

• Solution: Sum Fct

Strings Mix

• Problem: Strings Mix

• Solution: Mixing

Unknown Digit

• Problem: Find the unknown digit

• Solution: Runes

Histogram

• Problem: Histogram - V1

• Solution: Dingle Mouse

Breadcrumb Generator

• Problem: Breadcrumb Generator

• Solution: Generating

Decode the Morse code

• Problem: Decode the Morse code, advanced

• Solution: Morse Decoder

Smallfuck Interpreter

• Problem: Esolang Interpreters #2 - Custom Smallfuck Interpreter

• Solution: Smallfuck

Paintfuck Interpreter

• Problem: Esolang Interpreters #3 - Custom Paintfuck Interpreter

• Solution: Paintfuck

Fuzzy Searching

• Problem: Did you mean ...?

• Solution: Dictionary

Tiny Three-Pass Compiler

• Problem: Tiny 3 Pass Compiler

• Solution: Compiler

Interactive Interpreter

• Problem: Simple Interactive Interpreter

• Solution: Interpreter

01_srot.java

import java.util.Arrays;
import java.util.Collections;
import java.util.stream.Collectors;

// Solution
public class Srot {
    public static String sortTheInnerContent(String words) {
        return Arrays.stream(words.split(" "))
                .map(source -> getSortedString(source, sortChars(source)))
                .collect(Collectors.joining(" "));
    }

    private static String getSortedString(String source, String sorted) {
        return source.charAt(0) + sorted + source.charAt(source.length() - 1);
    }

    private static String sortChars(String source) {
        String[] letter = source.substring(1, source.length() - 1).split("");
        Arrays.sort(letter, Collections.reverseOrder());
        return String.join("", letter);
    }
}

// Test
public class Main {
    public static void main(String[] args) {
        String words = "sort the inner content in descending order";
        String result = Srot.sortTheInnerContent(words);
        System.out.println(result);
    }
}

02_abbreviator.java

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;

// Solution
public class Abbreviator {
    public String abbreviate(String string) {
        return specSplit(string).stream()
                .map(list -> list.size() > 3 ?
                        String.valueOf(list.get(0)) + String.valueOf(list.size() - 2) + String.valueOf(list.get(list.size() - 1)) :
                        list.stream().map(String::valueOf).reduce((s1, s2) -> s1 + s2).orElse(""))
                .reduce((s1, s2) -> s1 + s2)
                .orElse("");
    }

    private List<List<Character>> specSplit(String string) {
        List<List<Character>> lists = new ArrayList<>();
        List<Character> list = new ArrayList<>();
        for (byte b : string.getBytes()) {
            list = (b >= 65 && b <= 90) || (b >= 97 && b <= 122) ? addWords(list, (char) b) : addSymbol(lists, list, (char) b);
        }
        lists.add(list);
        return lists;
    }

    private List<Character> addWords(List<Character> list, char c) {
        list.add(c);
        return list;
    }

    private List<Character> addSymbol(List<List<Character>> lists, List<Character> list, char c) {
        lists.add(list);
        list = new ArrayList<>();
        list.add(c);
        lists.add(list);
        return new ArrayList<>();
    }
}

// Test
public class Main {
    public static void main(String[] args) {
        Abbreviator abbr = new Abbreviator();
        String result = abbr.abbreviate("elephant-rides are really fun!");
        System.out.println(result);
    }
}

03_alt-split.java

// Solution
public class AltSplit {
    public static String encrypt(final String text, final int n) {
        if (n <= 0) return text;
        String l = "", r = "";
        char[] chars = text.toCharArray();
        for (int j = 0; j < chars.length; j++) {
            if (j % 2 == 0) r += String.valueOf(chars[j]);
            else l += String.valueOf(chars[j]);
        }
        return encrypt(l + r, n - 1);
    }

    public static String decrypt(final String encryptedText, final int n) {
        if (n <= 0) return encryptedText;
        String l = encryptedText.substring(0, encryptedText.length() / 2);
        String r = encryptedText.substring(encryptedText.length() / 2);
        String source = "";
        for (int i = 0; i < r.length(); i++) {
            source += r.charAt(i);
            if (i < l.length()) source += l.charAt(i);
        }
        return decrypt(source, n - 1);
    }
}

// Test
public class Main {
    public static void main(String[] args) {
        System.out.println(AltSplit.encrypt("This is a reduce!", 0));
        System.out.println(AltSplit.encrypt("This is a reduce!", 1));
        System.out.println(AltSplit.encrypt("This is a reduce!", 2));
        System.out.println(AltSplit.encrypt("This is a reduce!", 3));
        System.out.println(AltSplit.encrypt("This is a reduce!", 4));
        System.out.println(AltSplit.encrypt("This is a reduce!", -1));
        System.out.println(AltSplit.decrypt("This is a reduce!", 0));
        System.out.println(AltSplit.decrypt("hsi  etTi sats!", 1));
        System.out.println(AltSplit.decrypt("s eT ashi tist!", 2));
        System.out.println(AltSplit.decrypt(" Tah itse sits!", 3));
        System.out.println(AltSplit.decrypt("This is a reduce!", 4));
        System.out.println(AltSplit.decrypt("This is a reduce!", -1));
    }
}

04_column-title.java

// Solution
public class ColumnTitle {
    public static String getColumnTitle(int num) {
        if (num <= 0) throw new IllegalArgumentException("The Number can't be zero");
        String result = num <= 26 ? String.valueOf((char) (num + 64)) : num % 26 == 0 ? getColumnTitle(num / 26 - 1) : getColumnTitle(num / 26);
        return num > 26 ? num % 26 == 0 ? result + getColumnTitle(26) : result + getColumnTitle(num % 26) : result;
    }
}

// Test
public class Main {
    public static void main(String[] args) {
        System.out.println(ColumnTitle.getColumnTitle(1));
        System.out.println(ColumnTitle.getColumnTitle(26));
        System.out.println(ColumnTitle.getColumnTitle(52));
        System.out.println(ColumnTitle.getColumnTitle(53));
        System.out.println(ColumnTitle.getColumnTitle(702));
        System.out.println(ColumnTitle.getColumnTitle(1337));
        System.out.println(ColumnTitle.getColumnTitle(432778));
    }
}

05_resistor-colors.java

// Solution
public class ResistorColor {
    private static final String[] COLOR = {"black ", "brown ", "red ", "orange ", "yellow ", "green ", "blue ", "violet ", "gray ", "white "};

    public static String encodeResistorColors(String ohmsString) {
        String str = ohmsString.replace("ohms", "").trim();
        int multiplier = str.endsWith("k") ? 1000 : str.endsWith("M") ? 1000000 : 1;
        str = "" + (int) (Double.parseDouble(str.endsWith("k") || str.endsWith("M") ? str.substring(0, str.length() - 1) : str) * multiplier);
        return COLOR[str.charAt(0) - 48] + COLOR[str.charAt(1) - 48] + COLOR[str.length() - 2] + "gold";
    }
}

// Test
public class Main {
    public static void main(String[] args) {
        System.out.println(ResistorColor.encodeResistorColors2("10 ohms"));
        System.out.println(ResistorColor.encodeResistorColors2("47 ohms"));
        System.out.println(ResistorColor.encodeResistorColors2("100 ohms"));
        System.out.println(ResistorColor.encodeResistorColors2("220 ohms"));
        System.out.println(ResistorColor.encodeResistorColors2("330 ohms"));
        System.out.println(ResistorColor.encodeResistorColors2("470 ohms"));
        System.out.println(ResistorColor.encodeResistorColors2("680 ohms"));
        System.out.println(ResistorColor.encodeResistorColors2("1k ohms"));
        System.out.println(ResistorColor.encodeResistorColors2("4.7k ohms"));
        System.out.println(ResistorColor.encodeResistorColors2("4.7M ohms"));
        System.out.println(ResistorColor.encodeResistorColors2("10k ohms"));
        System.out.println(ResistorColor.encodeResistorColors2("22k ohms"));
        System.out.println(ResistorColor.encodeResistorColors2("47k ohms"));
        System.out.println(ResistorColor.encodeResistorColors2("100k ohms"));
        System.out.println(ResistorColor.encodeResistorColors2("330k ohms"));
        System.out.println(ResistorColor.encodeResistorColors2("1M ohms"));
        System.out.println(ResistorColor.encodeResistorColors2("2M ohms"));
    }
}

06_sum-fct.java

import java.math.BigInteger;

// Solution
public class SumFct {    
    public static BigInteger perimeter(BigInteger n) {
        BigInteger a = BigInteger.ZERO;
        BigInteger b = BigInteger.ONE;
        BigInteger c = BigInteger.ZERO;
        BigInteger sum = BigInteger.ZERO;
        for (int i = 0; i <= n.intValue(); i++) {
            a = b;
            b = c;
            c = a.add(b);
            sum = sum.add(c);
        }
        return sum.multiply(BigInteger.valueOf(4));
    }
}

// Test
public class Main {
    public static void main(String[] args) {
        System.out.println(Fibonacci.fib(BigInteger.valueOf(96)));
        System.out.println(Fibonacci.fib(BigInteger.valueOf(-96)));
        System.out.println(Fibonacci.fib(BigInteger.valueOf(1000000)));
    }
}

07_mixing.java

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

// Solution
public class Mixing {
    public static String mix(String s1, String s2) {
        Map<Character, String> map = new HashMap<>();
        if (s1 != null || s1.length() != 0) {
            char[] chars1 = s1.trim().toCharArray();
            Map<Character, String> map1 = getMap(chars1);
            if (map1.size() > 0) {
                map1.forEach(map::put);
            }
        }
        if (s2 != null || s2.length() != 0) {
            char[] chars2 = s2.trim().toCharArray();
            Map<Character, String> map2 = getMap(chars2);
            if (map2.size() > 0) {
                map2.forEach((c, s) -> map.put(c, map.containsKey(c)
                        ? map.containsValue(s) ? "=:" + s + "/" : s.length() < map.get(c).length()
                        ? "1:" + map.get(c) + "/" : "2:" + s + "/" : "2:" + s + "/"));
            }
        }
        String result = "";
        if (map.size() > 0) {
            map.forEach((c, s) -> {
                if (s.charAt(0) != '=' && s.charAt(0) != '2' && s.charAt(0) != '1') {
                    map.put(c, "1:" + s + "/");
                }
            });
            String[] str = new String[map.size()];
            int index = 0;
            for (String s : map.values()) str[index++] = s;
            for (int i = 0; i < str.length; i++) {
                for (int j = i + 1; j < str.length; j++) {
                    if (str[i].length() < str[j].length()) {
                        switchS(str, i, j);
                    } else if (str[i].length() == str[j].length()) {
                        if (str[i].charAt(0) > str[j].charAt(0)) {
                            switchS(str, i, j);
                        } else if (str[i].charAt(0) == str[j].charAt(0) && str[i].charAt(2) > str[j].charAt(2)) {
                            switchS(str, i, j);
                        }
                    }
                }
            }
            for (String s : str) result += s;
        }
        return result.length() == 0 ? result : result.substring(0, result.length() - 1);
    }

    private static Map<Character, String> getMap(char[] chars) {
        Map<Character, String> map = new HashMap<>();
        Set<Character> set = new HashSet<>();
        for (char c : chars) if (Character.isLowerCase(c)) map.put(c, set.add(c) ? "" + c : map.get(c) + c);
        set.forEach(c -> map.remove(map.get(c).equals(c + "") ? c : ' '));
        return map;
    }

    private static void switchS(String[] str, int i, int j) {
        String t = str[i];
        str[i] = str[j];
        str[j] = t;
    }
}

// Test
public class Main {
    public static void main(String[] args) {
        System.out.println(Mixing.mix("Are they here", "yes, they are here"));
        System.out.println(Mixing.mix("looping is fun but dangerous", "less dangerous than coding"));
        System.out.println(Mixing.mix(" In many languages", " there's a pair of functions"));
        System.out.println(Mixing.mix("Lords of the Fallen", "gamekult"));
        System.out.println(Mixing.mix("codewars", "codewars"));
        System.out.println(Mixing.mix("A generation must confront the looming ", "codewarrs"));
    }
}

08_runes.java

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;

// Solution
public class Runes {
    public static int solveExpression(final String expression) {
        System.out.println(expression);
        int missingDigit = -1;
        if (expression == null || expression.length() == 0) return missingDigit;

        List<Integer> numList = new ArrayList<>();
        for (char c : expression.toCharArray()) {
            if (c > 47 && c < 58 && !numList.contains((int) c - 48)) numList.add((int) c - 48);
        }

        String[] chars = expression.split("=");
        if (chars.length != 2) return missingDigit;
        String exp = chars[0];
        String sol = chars[1];

        int runes1 = 1;
        int runes2 = 1;

        if (exp.charAt(0) == '-') {
            runes1 = -1;
            exp = exp.substring(1);
        }

        int mid = exp.lastIndexOf('-');
        if (mid != -1) {
            String sy = exp.substring(mid - 1, mid + 1);
            if (sy.equals("+-") || sy.equals("--") || sy.equals("*-") || sy.equals("/-")) {
                runes2 = -1;
                String l = exp.substring(0, mid);
                String r = exp.substring(mid + 1, exp.length());
                exp = l + r;
            }
        }

        String[] nums = exp.split("\\+|-|\\*|/");
        if (nums.length != 2) return missingDigit;
        String e1 = nums[0];
        String e2 = nums[1];

        int c1 = 0, c2 = 0, solc = 0;

        for (char c : e1.toCharArray()) if (c == '?') c1++;
        for (char c : e2.toCharArray()) if (c == '?') c2++;
        for (char c : sol.toCharArray()) if (c == '?') solc++;

        boolean b = sol.matches("\\?\\?+");

        e1 = e1.replace("?", "%d");
        e2 = e2.replace("?", "%d");
        sol = sol.replace("?", "%d");

        char symbol = 0;
        for (char c : exp.substring(1).toCharArray()) {
            if (c == '+' || c == '-' || c == '*' || c == '/') {
                symbol = c;
                break;
            }
        }

        for (int i = 0; i < 10; i++) {
            if (b && i == 0 || numList.contains(i)) continue;
            double result = calc(getNumber(e1, c1, i, runes1), getNumber(e2, c2, i, runes2), symbol);
            if (result == getNumber(sol, solc, i, 1)) return i;
        }
        return missingDigit;
    }

    private static double calc(double num1, double num2, char symbol) {
        return symbol == '+' ? num1 + num2 : symbol == '-' ? num1 - num2 : symbol == '*' ? num1 * num2 : num1 / num2;
    }

    private static double getNumber(String e, int c, int missing, int runes) {
        return Double.parseDouble(String.format(e, Stream.of(new Object[c]).map(o -> missing).toArray())) * runes;
    }
}

// Test
public class Main {
    public static void main(String[] args) {
        System.out.println(Runes.solveExpression("1+1=?"));
        System.out.println(Runes.solveExpression("123*45?=5?088"));
        System.out.println(Runes.solveExpression("-5?*-1=5?"));
        System.out.println(Runes.solveExpression("19--45=5?"));
        System.out.println(Runes.solveExpression("??*??=302?"));
        System.out.println(Runes.solveExpression("?*11=??"));
        System.out.println(Runes.solveExpression("123?45*?=?"));
        System.out.println(Runes.solveExpression("-7715?5--484?00=-28?9?5"));
    }
}

09_dingle-mouse.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;
import java.util.stream.Collectors;

// Solution
public class Dinglemouse {
    public static String histogram(final int results[]) {
        if (results == null || results.length == 0) return "";
        List<List<String>> before = new ArrayList<>();
        int max = Arrays.stream(results).max().orElse(0);

        for (int i = 0; i < results.length; i++) {
            List<String> list = new ArrayList<>();
            List<String> line = new ArrayList<>();
			for (int j = max; j >= 0; j--)
                histogramAdd(list, line, j >= results[i] ? j == results[i] && results[i] != 0 ? results[i] > 9 ?
                        new Object[]{results[i] / 10, results[i] % 10} : 
                        new Object[]{results[i], " "} : 
                        new Object[]{" ", " "} : 
                        new Object[]{"#", " "});
            histogramAdd(list, line, new Object[]{"-", i != results.length - 1 ? "-" : " "});
            histogramAdd(list, line, new Object[]{i + 1, " "});
            before.add(list);
            before.add(line);
        }

//        the key
        List<List<String>> after = numberList(before.get(0).size()).stream()
                .map(i -> before.stream()
                        .map(list -> list.get(i))
                        .collect(Collectors.toList()))
                .collect(Collectors.toList());
        after.forEach(list -> list.add("\n"));

        return after.stream()
                .flatMap(Collection::stream)
                .reduce((s1, s2) -> s1 + s2)
                .orElse("");
    }

    private static List<Integer> numberList(int beforeSize) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < beforeSize; i++) list.add(i);
        return list;
    }

    private static void histogramAdd(List<String> list, List<String> line, Object[] args) {
        list.add(args[0].toString());
        line.add(args[1].toString());
    }
}

// Test
public class Main {
    public static void main(String[] args) {
        System.out.println(Dinglemouse.histogram(new int[]{7, 3, 10, 1, 0, 5}));
        System.out.println(Dinglemouse.histogram(new int[]{8, 5, 10, 7, 9, 11}));
        System.out.println(Dinglemouse.histogram(new int[]{7, 10, 6, 8, 10, 9}));
        System.out.println(Dinglemouse.histogram(new int[]{0, 0, 0, 0, 0, 0}));
    }
}

10_generate-bc.java

import java.util.Arrays;
import java.util.stream.Collectors;

public class Generating {
    private static final String HREF = "<a href=\"";
    private static final String AMSG = "\">";
    private static final String FOOT = "</a>";
    private static final String SPANH = "<span class=\"active\">";
    private static final String SPANE = "</span>";
    private static final String[] IGNORE = new String[]{"the", "of", "in", "from", "by", "with", "and", "or", "for", "to", "at", "a"};

    public static String generateBc(String url, String separator) {
//        init url
        url = url.substring(url.indexOf("."));
        url = url.substring(url.indexOf("/") + 1).split("\\?|#|index\\.")[0];

        if (url.trim().equals("") || !url.contains("/")) return String.format("%s%s%s", SPANH, "HOME", SPANE);
        if (url.endsWith("/")) url = url.substring(0, url.length() - 1);

//        System.out.println(url);

        String[] block = url.split("/");

//        the home
        String home = HREF + "/" + AMSG + "HOME" + FOOT + separator;

//        the span
        String span = String.format("%s%s%s", SPANH, parse(block[block.length - 1].split("\\.")[0]), SPANE);

//        the middle part
        StringBuilder href = new StringBuilder();

        block = Arrays.copyOf(block, block.length - 1);
        for (int i = 0; i < block.length; i++) {
            StringBuilder dir = new StringBuilder();
            for (int j = 0; j <= i; j++) dir.append(block[j]).append("/");
            String folder = parse(block[i]);
            href.append(HREF + "/").append(dir).append(AMSG).append(folder).append(FOOT).append(separator);
        }

        return home + href + span;
    }

    private static String parse(String local) {
        return (local.length() >= 30 ?
                Arrays.stream(local.replace("/", "").split("-"))
                        .filter(s -> Arrays.stream(IGNORE).noneMatch(s::equals))
                        .map(s -> "" + s.charAt(0))
                        .collect(Collectors.joining())
                : local.replace("-", " ")).toUpperCase();
    }
}

// Test
public class Main {
    public static void main(String[] args) {
        String[] urls = new String[]{
                "www.agcpartners.co.uk/",
                "www.agcpartners.co.uk",
                "https://pippi.pi/biotechnology-with-cauterization-to-and-by/index.htm?sortBy=year",
                "https://pippi.pi/biotechnology-with-cauterization-to-and-by/login.htm?sortBy=year",
                "http://www.facebook.fr/users/by-immunity-and-pippi-bioengineering/#bottom?previous=normalSearch&output=full"};
        String[] seps = new String[]{" : ", " / ", " * ", " > ", " + "};
        for (int i = 0; i < urls.length; i++) {
            String actual = Generating.generateBc(urls[i], seps[i]);
            System.out.println(actual);
        }
    }
}

11_morse-decoder.java

import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Comparator;
import java.util.stream.Collectors;

public class MorseCode {
    private static final Map<String, String> CODE = new HashMap<>();
    static {
        CODE.put(".-", "A");
        CODE.put("-...", "B");
        CODE.put("-.-.", "C");
        CODE.put("-..", "D");
        CODE.put(".", "E");
        CODE.put("..-.", "F");
        CODE.put("--.", "G");
        CODE.put("....", "H");
        CODE.put("..", "I");
        CODE.put(".---", "J");
        CODE.put("-.-", "K");
        CODE.put(".-..", "L");
        CODE.put("--", "M");
        CODE.put("-.", "N");
        CODE.put("---", "O");
        CODE.put(".--.", "P");
        CODE.put("--.-", "Q");
        CODE.put(".-.", "R");
        CODE.put("...", "S");
        CODE.put("-", "T");
        CODE.put("..-", "U");
        CODE.put("...-", "V");
        CODE.put(".--", "W");
        CODE.put("-..-", "X");
        CODE.put("-.--", "Y");
        CODE.put("--..", "Z");
        CODE.put(".-.-.-", ".");
    }

    public static String get(String morseCode) {
        return CODE.get(morseCode);
    }
}

// Solution
public class MorseDecoder {
    private static final String DASH = "(111)";
    private static final String PL = "(000)";
    private static final String PW = "(0000000)";

    public static String decodeMorse(String morseCode) {
        return Arrays.stream(morseCode.split("   "))
                .map(s -> Arrays.stream(s.split(" "))
                        .map(MorseCode::get)
                        .collect(Collectors.joining()))
                .collect(Collectors.joining(" "));
    }

    public static String decodeBits(String bits) {
        bits = bits.substring(bits.indexOf('1'), bits.lastIndexOf('1') + 1);
        final String unit = "{" + reduce(bits) + ",}";
        return Arrays.stream(bits.split(PW + unit))
                .map(word -> Arrays.stream(word.split(PL + unit))
                        .map(letter -> Arrays.stream(letter.split("0+"))
                                .map(morse -> morse.matches(DASH + unit) ? "-" : ".")
                                .collect(Collectors.joining()))
                        .collect(Collectors.joining(" ")))
                .collect(Collectors.joining("   "));
    }

    private static int reduce(String bits) {
        List<String> list = new ArrayList<>();
        StringBuilder str = new StringBuilder();
        for (char c : bits.toCharArray()) {
            if (!str.toString().matches(c + "*")) {
                list.add(str.toString());
                str = new StringBuilder();
            }
            str.append(c);
        }
        list.add(str.toString());
        return list.stream().min(Comparator.comparing(String::length)).orElse("").length();
    }
}

// Test
public class Main {
    public static void main(String[] args) {
        String morseCode = MorseDecoder.decodeBits(bits);
        String cipher = MorseDecoder.decodeMorse(morseCode);
        System.out.println(cipher);
    }
    
    String bits = "1111111111111110000000000000001111100000111110000011111000001111100000000000000011111000000000000000000000000000000" +
        "00000111111111111111000001111111111111110000011111000001111111111111110000000000000001111100000111110000011111111111111100000" +
        "00000000001111100000111110000000000000001111111111111110000011111000001111111111111110000011111000000000000000111111111111111" +
        "00000111110000011111111111111100000000000000000000000000000000000111111111111111000001111100000111110000011111000000000000000" +
        "11111000001111111111111110000011111000000000000000111111111111111000001111111111111110000011111111111111100000000000000011111" +
        "00000111111111111111000001111111111111110000000000000001111111111111110000011111000000000000000000000000000000000001111100000" +
        "11111000001111111111111110000011111000000000000000111111111111111000001111111111111110000011111111111111100000000000000011111" +
        "11111111110000011111000001111100000111111111111111000000000000000000000000000000000001111100000111111111111111000001111111111" +
        "11111000001111111111111110000000000000001111100000111110000011111111111111100000000000000011111111111111100000111111111111111" +
        "00000000000000011111000001111111111111110000011111111111111100000111110000000000000001111100000111110000011111000000000000000" +
        "00000000000000000000111111111111111000001111111111111110000011111111111111100000000000000011111000001111100000111110000011111" +
        "11111111110000000000000001111100000000000000011111000001111111111111110000011111000000000000000000000000000000000001111111111" +
        "11111000000000000000111110000011111000001111100000111110000000000000001111100000000000000000000000000000000000111110000011111" +
        "11111111110000011111000001111100000000000000011111000001111111111111110000000000000001111111111111110000011111111111111100000" +
        "11111000001111100000000000000011111111111111100000111110000011111111111111100000111111111111111000000000000000000000000000000" +
        "00000111111111111111000001111100000111110000000000000001111111111111110000011111111111111100000111111111111111000000000000000" +
        "11111111111111100000111111111111111000001111100000000000000011111000001111111111111110000011111000001111111111111110000011111" +
        "00000111111111111111"
}

12_smallfuck-interpreter.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

// Solution
public class Smallfuck {
    public static String interpreter(String code, String tape) {
        int[] points = Arrays.stream(tape.split("")).mapToInt(Integer::parseInt).toArray();
        List<Integer> pres = new ArrayList<>();
        Stack<Boolean> braces = new Stack<>();
        braces.push(true);
        int currP = 0;
        for (int i = 0; i < code.length(); i++) {
            if (currP >= points.length || currP < 0) {
                return Arrays.stream(points).mapToObj(String::valueOf).collect(Collectors.joining());
            } else if (code.charAt(i) == ']' || code.charAt(i) == '[') {
                if (code.charAt(i) == ']') {
                    braces.pop();
                    i = points[currP] == 1 ? pres.remove(braces.size() - 1) : i;
                } else {
                    braces.push(points[currP] != 0);
                    pres.add(i - 1);
                }
            } else if (braces.peek()) {
                if (code.charAt(i) == '>') ++currP;
                else if (code.charAt(i) == '<') --currP;
                else if (code.charAt(i) == '*') points[currP] ^= 1;
            }
        }
        return Arrays.stream(points).mapToObj(String::valueOf).collect(Collectors.joining());
    }
}

// Test
public class Main {
    public static void main(String[] args) {
        System.out.println(Smallfuck.interpreter("*>*>*>*>*>*>*>*>*>*>*>*>*>*>*>*>*>*>", "00000000000000000000000000"));
        System.out.println(Smallfuck.interpreter("[[]*>*>*>]", "000"));
        System.out.println(Smallfuck.interpreter("[*>[>*>]>]", "11001"));
        System.out.println(Smallfuck.interpreter("[>[*>*>*>]>]", "10110"));
        System.out.println(Smallfuck.interpreter("*>*>>*>>>*>*", "00101100"));
        System.out.println(Smallfuck.interpreter("*[>*]", "00000000000000000000000000000000000000000000000000000000000000000000000000"));
        System.out.println(Smallfuck.interpreter("[>*]", "000000000000000000000000000000000000000000000000000000000000000000000000000"));
        System.out.println(Smallfuck.interpreter(("<<<*>*>*>*>*>>>*>>>>>*>*"), "0000000000000000"));
    }
}

13_paintfuck-interpreter.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;

// Solution
public class Paintfuck {
    public static String interpreter(String code, int iterations, int width, int height) {
        code = code.replaceAll("[^nesw\\[\\]*]*", "");
        int[][] tapes = new int[height][width];
        List<Integer> pres = new ArrayList<>();
        Stack<Boolean> braces = new Stack<>();
        braces.push(true);
        int currX = 0;
        int currY = 0;
        for (int i = 0; i < code.length() && iterations > 0; i++, iterations--) {
            if (currY >= tapes.length) currY = 0;
            else if (currX >= tapes[0].length) currX = 0;
            else if (currY < 0) currY = tapes.length - 1;
            else if (currX < 0) currX = tapes[0].length - 1;
            if (code.charAt(i) == ']' || code.charAt(i) == '[') {
                if (code.charAt(i) == ']') {
                    braces.pop();
                    i = tapes[currY][currX] != 0 ? pres.get(braces.size() - 1) : i;
                } else {
                    braces.push(tapes[currY][currX] != 0);
                    pres.add(i - 1);
                    iterations++;
                }
            } else if (braces.peek()) {
                if (code.charAt(i) == 'e') ++currX;
                else if (code.charAt(i) == 'w') --currX;
                else if (code.charAt(i) == 's') ++currY;
                else if (code.charAt(i) == 'n') --currY;
                else if (code.charAt(i) == '*') tapes[currY][currX] ^= 1;
            } else iterations++;
        }
        return toTapes(tapes);
    }

    private static String toTapes(int[][] tapes) {
        return Arrays.stream(tapes)
                .map(tape -> Arrays.stream(tape)
                        .mapToObj(String::valueOf)
                        .collect(Collectors.joining()))
                .collect(Collectors.joining("\r\n"));
    }
}

// Test
public class SolutionTests {
    @Test
    public void random() {
        char commands[] = "nesw*".toCharArray();
        int iterations = (int)(1001 * Math.random());
        char randomPaintfuckProgram[] = new char[100 + (int)(901 * Math.random())];
        for (int i = 0; i < randomPaintfuckProgram.length; i++) {
            randomPaintfuckProgram[i] = commands[(int)(5 * Math.random())];
        }
        String code = new String(randomPaintfuckProgram);
        assertEquals(GgmoySolution.interpreter(code, iterations, 10, 10), Paintfuck.interpreter(code, iterations, 10, 10));
    }
}

14_dictionary.java

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

// Solution
public class Dictionary {
    private final String[] words;
    public Dictionary(String[] words) { this.words = words; }
  
    public String findMostSimilar(String to) {
        Map<String, Integer> frequency = new HashMap<>();
        for (String word : words) for (int i = 0; i < to.length(); i++) {
            int times = 0;
            for (int j = i + 1; j <= to.length(); j++) if (word.contains(to.substring(i, j))) times += 2;
            if (!frequency.containsKey(word) || frequency.get(word) < times) frequency.put(word, times);
        }
        String correct = "";
        int maxAbs = Integer.MIN_VALUE, currAbs = 0;
        for (String s : frequency.keySet()) {
            currAbs = frequency.get(s) - s.length() - Math.abs(s.length() - to.length());
            if (currAbs > maxAbs) {
                correct = s;
                maxAbs = currAbs;
            }
        }
        return correct;
    }
}

// Test
public class Main {
    public static void main(String[] args) {
        Dictionary dictionary = new Dictionary(new String[]{
                "cherry", "pineapple", "melon", "strawberry", "raspberry",
                "javascript", "java", "ruby", "php", "python", "coffeescript",
                "wars", "codewars", "rkacypviuburk", "zqdrhpviqslik", "pdyjrkaylryr"});
        String[] inputs = new String[]{
                "strawbery",
                "berry",
                "heaven",
                "javascript",
                "coddwars",
                "rkacypviuburk"};
        for (String input : inputs) {
            String expectation = dictionary.findMostSimilar(input);
            System.out.println(input);
        }
    }
}

15_tiny-three-pass-compiler.java

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Compiler {
  public List<String> compile(String prog) {
    return pass3(pass2(pass1(prog)));
  }

  private boolean isAS(String token) {
    return token.matches("[+-]");
  }

  private boolean isMD(String token) {
    return token.matches("[*/]");
  }

  private boolean isNumber(String token) {
    return token.matches("[0-9]*");
  }

  private boolean isSymbol(String token) {
    return token.matches("[\\w]*");
  }

  private int getArgIndex(String arg) {
    for (int i = 0; i < args.length; i++) if (args[i].equals(arg)) return i;
    return 0;
  }

  private Ast judgeUnOp(String token) {
    if (isNumber(token)) {
      return new UnOp("imm", Integer.parseInt(token));
    } else {
      return new UnOp("arg", getArgIndex(token));
    }
  }

  private Ast pass1Iter(Deque<String> tokens) {
    String token = tokens.pop();
    return isAS(token) || isMD(token) ? new BinOp(token, pass1Iter(tokens), pass1Iter(tokens)) : judgeUnOp(token);
  }

  private Deque<String> parse(Deque<String> tokens) {
    Deque<String> stack1 = new LinkedList<>();
    Deque<String> stack2 = new LinkedList<>();
    while (!tokens.isEmpty()) {
      String token = tokens.pollLast();
      if (isNumber(token) || isSymbol(token)) {
        stack2.push(token);
      } else if (token.equals(")")) {
        stack1.push(token);
      } else if (token.equals("(")) {
        String tem = stack1.pop();
        while (!tem.equals(")")) {
          stack2.push(tem);
          tem = stack1.pop();
        }
      } else if (isMD(token)) {
        stack1.push(token);
      } else if (isAS(token)) {
        String tem = stack1.peek();
        while (tem != null && isMD(tem)) {
          stack2.push(stack1.pop());
          tem = stack1.peek();
        }
        stack1.push(token);
      }
    }
    while (!stack1.isEmpty()) stack2.push(stack1.pop());
    return stack2;
  }

  private String[] args;

  /**
   * Returns an un-optimized AST
   */

  public Ast pass1(String prog) {
    Deque<String> tokens = tokenize(prog);
    List<String> tem = new ArrayList<>();
    String token;
    tokens.pop();
    while (!(token = tokens.pop()).equals("]")) tem.add(token);
    args = tem.toArray(new String[0]);
    Deque<String> stack = parse(tokens);
    return pass1Iter(stack);
  }

  /**
   * Returns an AST with constant expressions reduced
   */

  private Ast calculator(String op, int a, int b) {
    switch (op) {
      case "+": return new UnOp("imm", a + b);
      case "-": return new UnOp("imm", a - b);
      case "*": return new UnOp("imm", a * b);
      default:  return new UnOp("imm", a / b);
    }
  }

  public Ast pass2(Ast ast) {
    if (ast instanceof UnOp) {
      return ast;
    } else {
      Ast a = pass2(((BinOp) ast).a());
      Ast b = pass2(((BinOp) ast).b());
      if (a.op().equals("imm") && b.op().equals("imm")) {
        return calculator(ast.op(), ((UnOp) a).n(), ((UnOp) b).n());
      } else {
        return new BinOp(ast.op(), a, b);
      }
    }
  }

  /**
   * Returns assembly instructions
   */

  private String opSelector(String op) {
    switch (op) {
      case "+": return "AD";
      case "-": return "SU";
      case "*": return "MU";
      default:  return "DI";
    }
  }

  private String unSelector(UnOp un) {
    return (un.op().equals("imm") ? "IM " : "AR ") + un.n();
  }

  public List<String> pass3(Ast ast) {
    if (ast instanceof UnOp) {
      return Collections.singletonList(unSelector((UnOp) ast));
    } else {
      BinOp bin = (BinOp) ast;
      List<String> v1 = pass3(bin.a());
      List<String> v2 = pass3(bin.b());

      List<String> tem = new ArrayList<>();
      if (bin.b() instanceof UnOp) {
        tem.addAll(v1);
        tem.add("SW");
        tem.addAll(v2);
        tem.add("SW");
        tem.add(opSelector(ast.op()));
        return tem;
      } else {
        tem.addAll(v1);
        tem.add("PU");
        tem.addAll(v2);
        tem.add("SW");
        tem.add("PO");
        tem.add(opSelector(ast.op()));
        return tem;
      }
    }
  }

  private static Deque<String> tokenize(String prog) {
    Deque<String> tokens = new LinkedList<>();
    Pattern pattern = Pattern.compile("[-+*/()\\[\\]]|[a-zA-Z]+|\\d+");
    Matcher m = pattern.matcher(prog);
    while (m.find()) tokens.add(m.group());
    tokens.add("$"); // end-of-stream
    return tokens;
  }
}

16_simple-interactive-interpreter.java

import javafx.util.Pair;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Interpreter {
  private List<Pair<String, Ast>> env = new ArrayList<>();
  private Ast lookup(String key) {
    for (int i = env.size() - 1; i >= 0; i--) if (env.get(i).getKey().equals(key)) return env.get(i).getValue(); 
    throw new IllegalArgumentException("Unknown identifier " + key);
  }
  private boolean contain(String key) {
    for (Pair<String, Ast> pair : env) if (pair.getKey().equals(key)) return true;
    return false;
  }
  private Double extEnv(String key, Ast val) {
    env.add(new Pair<>(key, val));
    return calcIter(val);
  }
  private boolean strikeOut(String key) {
    for (int i = env.size() - 1; i >= 0; i--) if (env.get(i).getKey().equals(key)) return env.remove(env.get(i));
    return false;
  }
  private void extEnv(String[] args, Ast[] asts) { for (int i = 0; i < args.length; i++) extEnv(args[i], (asts[i])); }
  private void strikeOut(String[] args) { for (String arg : args) strikeOut(arg); }

  private Map<String, Closure> funMap = new HashMap<>();
  private boolean isAS(String token) { return token.matches("[-+]"); }
  private boolean isMD(String token) { return token.matches("[*/%]"); }
  private boolean isAssign(String token) { return token.equals("="); }
  private boolean isNumber(String token) { return token.matches("\\d+.?\\d*"); }
  private boolean isSymbol(String token) { return token.matches("[\\w]*"); }
  private boolean isFunction(String token) { return token.equals("=>"); }

  private Deque<String> parsing(Deque<String> tokens) {
    Deque<String> stack1 = new LinkedList<>();
    Deque<String> stack2 = new LinkedList<>();
    while (!tokens.isEmpty()) {
      String token = tokens.pollLast();
      if (isNumber(token) || isSymbol(token)) {
        stack2.push(token);
      } else if (token.equals(")")) {
        stack1.push(token);
      } else if (token.equals("(")) {
        while (!stack1.peek().equals(")")) stack2.push(stack1.pop());
        stack1.pop();
      } else if (isMD(token)) {
        stack1.push(token);
      } else if (isAS(token)) {
        while (!stack1.isEmpty() && isMD(stack1.peek())) stack2.push(stack1.poll());
        stack1.push(token);
      } else if (isAssign(token)) {
        while (!stack1.isEmpty() && !stack1.peek().equals(")")) stack2.push(stack1.pop());
        stack1.push(token);
      } else if (isFunction(token)) {
        while (!stack1.isEmpty()) stack2.push(stack1.pop());
        stack2.push(token);
      }
    }
    while (!stack1.isEmpty()) stack2.push(stack1.pop());
    return stack2;
  }

  private Ast closure(Deque<String> tokens) {
    String op = tokens.pop();
    String name = tokens.pop();
    String[] args = getArgs(tokens).split(" ");
    Ast expr = getAst(tokens);
    if (checkFnArgs(args) && checkFnExpr(args, expr)) return new Closure(op, name, args, expr);
    else throw new IllegalArgumentException("Unknown identifier " + Arrays.toString(args));
  }
  private Ast getAst(Deque<String> tokens) {
    String token = tokens.pop();
    return funMap.containsKey(token) ? new Func(token, getAsts(tokens, funMap.get(token).args.length)) 
          : token.matches("[-+*/%=]") ? new Op(token, getAst(tokens), getAst(tokens)) : getAtom(token);
  }
  private Ast[] getAsts(Deque<String> tokens, int len) {
    Ast[] asts = new Ast[len];
    for (int i = 0; i < asts.length; i++) asts[i] = getAst(tokens);
    return asts;
  }
  private String getArgs(Deque<String> tokens) {
    String token = tokens.pop();
    return token.equals("=>") ? " " : token + " " + getArgs(tokens);
  }
  private Ast getAtom(String token) {
    return new Atom(isNumber(token) ? "const" : "param", token);
  }
  private boolean checkFnArgs(String[] args) {
    Set<String> set = new HashSet<>();
    Collections.addAll(set, args);
    return set.size() == args.length;
  }
  private boolean checkFnExpr(String[] args, Ast expr) {
    return expr.op().matches("[-+*/%=]") ? checkFnExpr(args, ((Op) expr).car) && checkFnExpr(args, ((Op) expr).cdr)
          : isNumber(((Atom) expr).v) || Arrays.stream(args).anyMatch(arg -> arg.equals(((Atom) expr).v));
  }

  private Double calcIter(Ast ast) {
    if (ast == null) return null;
    if (ast.op().matches("[-+*/%]")) {
      Op bin = (Op) ast;
      Double car = calcIter(bin.car);
      Double cdr = calcIter(bin.cdr);
      switch (bin.op()) {
        case "+": return car + cdr;
        case "-": return car - cdr;
        case "*": return car * cdr;
        case "/": return car / cdr;
        case "%": return car % cdr;
      }
    } else if (ast.op().equals("=")) {
      Op bin = (Op) ast;
      String key = ((Atom) bin.car).v;
      if (funMap.containsKey(key)) throw new IllegalArgumentException("Identifier with conflicts");
      else return extEnv(key, bin.cdr);
    } else if (ast.op().equals("fn")) {
      Closure closure = (Closure) ast;
      if (contain(closure.name)) throw new IllegalArgumentException("Function with conflicts");
      else funMap.put(closure.name, closure);
    } else if (funMap.containsKey(ast.op())) {
      Func func = (Func) ast;
      Closure closure = funMap.get(ast.op());
      extEnv(closure.args, func.asts);
      Double val = calcIter(closure.exp);
      strikeOut(closure.args);
      return val;
    } else {
      Atom atom = (Atom) ast;
      switch (atom.op()) {
        case "const": return Double.valueOf(atom.v);
        case "param": return calcIter(lookup(atom.v));
      }
    }
    return null;
  }

  public Double input(String input) {
    if (input.trim().isEmpty()) return null;
    Deque<String> tokens = tokenize(input);
    Deque<String> polish = parsing(tokens);
    Ast ast = polish.peek().equals("fn") ? closure(polish) : getAst(polish);
    if (!polish.isEmpty()) throw new IllegalArgumentException("Mismatch expression");
    else return calcIter(ast);
  }

  interface Ast { String op(); }
  private class Closure implements Ast {
    String op; String name; String[] args; Ast exp; 
    public Closure(String op, String name, String[] args, Ast exp) { this.op = op; this.name = name; this.args = args; this.exp = exp; }
    public String op() { return op; }
  }
  private class Func implements Ast {
    String op; Ast[] asts;
    public Func(String op, Ast[] asts) { this.op = op; this.asts = asts; }
    public String op() { return op; }
  }
  private class Op implements Ast {
    String op; Ast car; Ast cdr;
    public Op(String op, Ast car, Ast cdr) { this.op = op; this.car = car; this.cdr = cdr; }
    public String op() { return op; }
  }
  private class Atom implements Ast {
    String op; String v;
    public Atom(String op, String v) { this.op = op; this.v = v; }
    public String op() { return op; }
  }
  private static Deque<String> tokenize(String input) {
    Deque<String> tokens = new LinkedList<>();
    Pattern pattern = Pattern.compile("=>|[-+*/%=()]|[A-Za-z_][A-Za-z0-9_]*|[0-9]*(\\.?[0-9]+)");
    Matcher m = pattern.matcher(input);
    while (m.find()) tokens.add(m.group());
    return tokens;
  }
}