Find the longest sub-string of the given string that contains, at most, two unique characters. If you find multiple sub-strings that match the description, print the last sub-string (furthest to the right).

Inputs:

abbccc
abcabcabcabccc
qwertyytrewq
aaabaaabccbcccbde
abcde
aaaa
aabb

Outputs:

bbccc
bccc
tyyt
bccbcccb
de
aaaa
aabb

package main

import (
    "fmt"
)

type Substring struct {
    begin int
    end   int
}

func longestSubstring(str string) string {
    m := map[uint8]bool{}
    substrings := []Substring{}
    for i := 0; i < len(str); i++ {
        if _, ok := m[str[i]]; !ok {
            m[str[i]] = true
        }
        if len(m) == 3 {
            m = map[uint8]bool{}
            m[str[i-1]] = true
            m[str[i]] = true
            if len(substrings) == 0 {
                substrings = append(substrings, Substring{0, i - 1})
            } else {
                begin := substrings[len(substrings)-1].end
                c := str[begin]
                for j := begin; str[j] == c && j != 0; j-- {
                    begin--
                }
                substrings = append(substrings, Substring{begin + 1, i - 1})
            }
        }
    }
    if len(m) == 2 {
        if len(substrings) == 0 {
            substrings = append(substrings, Substring{0, len(str) - 1})
        } else {
            begin := substrings[len(substrings)-1].end
            c := str[begin]
            for j := begin; str[j] == c && j != 0; j-- {
                begin--
            }
            substrings = append(substrings, Substring{begin + 1, len(str) - 1})
        }
    } else {
        return str
    }
    var longest string
    for _, v := range substrings {
        substring := str[v.begin : v.end+1]
        if len(longest) <= len(substring) {
            longest = substring
        }
    }
    return longest
}

func main() {
    fmt.Println(longestSubstring("abbccc"))
    fmt.Println(longestSubstring("abcabcabcabccc"))
    fmt.Println(longestSubstring("qwertyytrewq"))
    fmt.Println(longestSubstring("aaabaaabccbcccbde"))
    fmt.Println(longestSubstring("abcde"))
    fmt.Println(longestSubstring("aaaa"))
    fmt.Println(longestSubstring("aabb"))
}

How to Solve On-Screen Keyboard Problem in Go

Problem description:

Given the English alphabet, 'a' through 'z' (lowercase), and an imaginary onscreen keyboard with the letters laid out in 6 rows and 5 columns:

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

Using a remote control - (up - 'u', down 'd', left 'l', right 'r' and enter '!'), write a function that given a word will produce the sequence of key presses required to type out the word on the onscreen keyboard. The function should return the sequence string. The optimal solution will require the least keystrokes. There could be more than one optimal solutions. Assume the initial position is 'a'.

Input:

hello

Output:

drr!urr!ddlll!!rrr!

package main

import (
    "fmt"
)

func position(idx, ncols int) (int, int) {
    row := (idx - int('a')) / ncols
    col := (idx - int('a')) - (ncols * row)
    return row, col
}

func printKeyboard(ncols int) {
    m := [][]rune{}
    for i := 'a'; i <= 'z'; {
        chars := make([]rune, ncols)
        for j := 0; j < ncols; j++ {
            if i > 'z' {
                break
            }
            chars[j] = i
            i++
        }
        m = append(m, chars)
    }
    for i := range m {
        for j := range m[i] {
            fmt.Print(string(m[i][j]), " ")
        }
        fmt.Println()
    }
}

func showKeystrokes(word string, ncols int) {
    printKeyboard(ncols)
    fmt.Print(word + ": ")
    startRow, startCol := 0, 0
    for i := 0; i < len(word); i++ {
        nextRow, nextCol := position(int(word[i]), ncols)
        if startRow < nextRow {
            for step := 0; step < nextRow-startRow; step++ {
                fmt.Print("d")
            }
        } else if startRow > nextRow {
            for step := 0; step < startRow-nextRow; step++ {
                fmt.Print("u")
            }
        }

        if startCol < nextCol {
            for step := 0; step < nextCol-startCol; step++ {
                fmt.Print("r")
            }
        } else if startCol > nextCol {
            for step := 0; step < startCol-nextCol; step++ {
                fmt.Print("l")
            }
        }
        fmt.Print("!")
        startRow, startCol = nextRow, nextCol
    }
    fmt.Println()
}

func main() {
    showKeystrokes("hello", 5)
}

How to Solve the Longest String Problem in Go

Problem Description:

You are given a dictionary in the form of a file that contains one word per line. e.g.,

abacus
deltoid
gaff
giraffe
microphone
reef
war

You are also given a collection of letters. E.g., {a, e, f, f, g, i, r, q}. Your task is to find the longest word in the dictionary that can be spelled with the collection of letters. For example, the correct answer for the example values above is "giraffe". Note that "reef" is not a possible answer, because the set of letters contains only one "e".

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
)

func longestString(path string, letters []uint8) (string, error) {
    file, err := os.Open(path)
    defer file.Close()
    if err != nil {
        return "", err
    }
    r := bufio.NewReader(file)
    longest := 0
    result := ""
    for {
        bytes, _, e := r.ReadLine()
        if e == io.EOF {
            break
        }
        line := string(bytes)
        count := 0
        tmp := make([]uint8, len(letters))
        copy(tmp, letters)
        for i := 0; i < len(line); i++ {
            for j := 0; j < len(tmp); j++ {
                if line[i] == tmp[j] {
                    // 0 to indicate the letter can't be used anymore
                    tmp[j] = 0
                    count++
                    break
                }
            }
        }
        if count > longest {
            longest = count
            result = line
        }
    }
    return result, nil
}

func main() {
    chars := []uint8{'a', 'e', 'f', 'f', 'g', 'i', 'r', 'q'}
    str, _ := longestString(os.Args[1], chars)
    fmt.Println(str)
}

How to Solve Word Chains Problem in Java

Problem description:

A word chain consists of a set of words ordered so that each word differs by only one letter from the words directly before and after it. The one letter difference can be either an insertion, a deletion, or a substitution. Here is an example word chain:

Write a function which takes a set of words, and returns true if they can be arranged into one continuous word chain, and false if they cannot.

Sample Input:

{"hat", "coat", "dog", "cat", "oat", "cot", "hot", "hog"}
{"cot", "hot", "bat", "fat"}
{"to", "top", "stop", "tops", "toss"}
{"spout", "do", "pot", "pout", "spot", "dot"}

Sample Output:

true
false
false
true

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

public class WordChains {
    private static int editDistance(String str1, String str2) {
        int lenStr1 = str1.length();
        int lenStr2 = str2.length();
        if (lenStr1 == 0) {
            return lenStr2;
        }
        if (lenStr2 == 0) {
            return lenStr1;
        }
        int cost = 0;
        if (!str1.substring(lenStr1 - 1).equals(str2.substring(lenStr2 - 1))) {
            cost = 1;
        }
        return minimum(editDistance(str1.substring(0, lenStr1 - 1), str2) + 1,
            editDistance(str1, str2.substring(0, lenStr2 - 1)) + 1,
            editDistance(str1.substring(0, lenStr1 - 1), str2.substring(0, lenStr2 - 1)) + cost);

    }

    private static int minimum(int i1, int i2, int i3) {
        return Math.min(Math.min(i1, i2), i3);
    }
    
    private static Map<Integer, Set<Integer>> buildMap(String[] words) {
        Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
        for (int i = 0; i < words.length; i++) {
            map.put(i, new HashSet<Integer>());
        }
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                if (words[i].equals(words[j])) {
                    continue;
                }
                if (editDistance(words[i], words[j]) == 1) {
                    map.get(i).add(j);
                }
            }
        }
        return map;
    }
    
    public static boolean wordChains(String[] words) {
        Map<Integer, Set<Integer>> map = buildMap(words);
        Set<List<Integer>> result = new HashSet<List<Integer>>();
        for (Map.Entry<Integer, Set<Integer>> e : map.entrySet()) {
            List<Integer> processed = new ArrayList<>();
            processed.add(e.getKey());
            recurseWordChains(map, e.getValue(), processed, result);
        }
        
        if (result.size() == 0) {
            return false;
        }
        
        for (List<Integer> list : result) {
            for (int i : list) {
                System.out.print(words[i] + " ");
            }
            System.out.println();
        }
        return true;
    }

    private static void recurseWordChains(Map<Integer, Set<Integer>> map,
        Set<Integer> set, List<Integer> processed, Set<List<Integer>> result) {
        if (processed.size() == map.size()) {
            result.add(processed);
        }
        
        for (int i : set) {
            if (processed.contains(i)) {
                continue;
            }
            List<Integer> newList = new ArrayList<>(processed);
            newList.add(i);
            recurseWordChains(map, map.get(i), newList, result);
        }
    }
    
    private static void printSeperator() {
        for (int i = 0; i < 72; i++) {
            System.out.print("-");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        System.out.println(wordChains(new String[]{"cat", "cot", "coat", "oat", "hat", "hot", "hog", "dog"}));
        printSeperator();
        System.out.println(wordChains(new String[]{"cot", "hot", "bat", "fat"}));
        printSeperator();
        System.out.println(wordChains(new String[]{"to", "top", "stop", "tops", "toss"}));
        printSeperator();
        System.out.println(wordChains(new String[]{"spout", "do", "pot", "pout", "spot", "dot"}));
        printSeperator();
    }
}

Output:

oat hat cat coat cot hot hog dog 
hat oat cat coat cot hot hog dog 
dog hog hot hat cat oat coat cot 
hat oat coat cat cot hot hog dog 
dog hog hot cot coat oat hat cat 
dog hog hot hat oat cat cot coat 
dog hog hot cot coat cat hat oat 
dog hog hot cot coat cat oat hat 
coat cot cat oat hat hot hog dog 
dog hog hot cot cat coat oat hat 
cat cot coat oat hat hot hog dog 
dog hog hot cot coat oat cat hat 
dog hog hot hat oat cat coat cot 
dog hog hot hat oat coat cot cat 
dog hog hot hat oat coat cat cot 
cot coat cat oat hat hot hog dog 
cot cat coat oat hat hot hog dog 
cot coat oat cat hat hot hog dog 
dog hog hot cot cat hat oat coat 
dog hog hot hat cat cot coat oat 
oat coat cot cat hat hot hog dog 
coat oat hat cat cot hot hog dog 
cat hat oat coat cot hot hog dog 
hat cat oat coat cot hot hog dog 
true
--------------------------------
false
--------------------------------
false
--------------------------------
do dot pot pout spout spot 
do dot pot spot spout pout 
spot spout pout pot dot do 
pout spout spot pot dot do 
true
--------------------------------

How to Solve Mayan Long Count Problem

Problem Description:
The Mayan Long Count calendar is a counting of days with these units: "* The Maya name for a day was k'in. Twenty of these k'ins are known as a winal or uinal. Eighteen winals make one tun. Twenty tuns are known as a k'atun. Twenty k'atuns make a b'ak'tun.*". Essentially, we have this pattern:

1 kin = 1 day

1 uinal = 20 kin

1 tun = 18 uinal

1 katun = 20 tun

1 baktun = 20 katun

The long count date format follows the number of each type, from longest-to-shortest time measurement, separated by dots. As an example, '12.17.16.7.5' means 12 baktun, 17 katun, 16 tun, 7 uinal, and 5 kin. This is also the date that corresponds to January 1st, 1970. Another example would be December 21st, 2012: '13.0.0.0.0'. This date is completely valid, though shown here as an example of a "roll-over" date.

Write a function that accepts a year, month, and day and returns the Mayan Long Count corresponding to that date. You must remember to take into account leap-year logic, but only have to convert dates after the 1st of January, 1970.

Input Description:
Through standard console, expect an integer N, then a new-line, followed by N lines which have three integers each: a day, month, and year. These integers are guaranteed to be valid days and either on or after the 1st of Jan. 1970.

Output Description:
For each given line, output a new line in the long-form Mayan calendar format: <Baktun>.<Katun>.<Tun>.<Uinal>.<Kin>.

Sample Input:

3
1 1 1970
20 7 1988
12 12 2012

Sample Output:

12.17.16.7.5
12.18.15.4.0
12.19.19.17.11

import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.Date;
import java.util.Scanner;

public class MayanLongCount {
    private static class MayanCalendar {
        private final int kin;
        private final int uinal;
        private final int tun;
        private final int katun;
        private final int baktun;
        
        public MayanCalendar(int baktun, int katun, int tun, int uinal, int kin) {
            this.baktun = baktun;
            this.katun = katun;
            this.tun = tun;
            this.uinal = uinal;
            this.kin = kin;
        }
        
        @Override
        public String toString() {
            return baktun + "." + katun + "." + tun + "." + uinal + "." + kin;
        }
    }
    
    private static Date epochTime() {
        Calendar cal = Calendar.getInstance();
        cal.setTime(new Date(0));
        return cal.getTime();
    }
    
    private static long getNumberOfDays(Date date1, Date date2) {
        return ((date2.getTime() - date1.getTime()) / (1000 * 60 * 60 * 24));
    }
    
    private static MayanCalendar toMayanCalendar(long numberOfDays) {
        long numOfMayanDaysBeforeEpoch = 0;
        int[] mayanEpoch = new int[]{12, 17, 16, 7, 5};
        int[] mayan = new int[]{20*20*18*20, 20*18*20, 18*20, 20, 1};
        for (int i = 0; i < mayan.length; i++) {
            numOfMayanDaysBeforeEpoch += mayan[i] * mayanEpoch[i];
        }
        int[] result = new int[mayan.length];
        long remainder = numberOfDays + numOfMayanDaysBeforeEpoch;
        for (int i = 0; i < mayan.length; i++) {
            int value = (int) (remainder / mayan[i]);
            if (value > 0) {
                remainder = remainder % mayan[i];
            }
            result[i] = value;
        }
        return new MayanCalendar(
            result[0], result[1], result[2], result[3], result[4]);
    }
    
    public static void main(String[] args) throws Exception {
        Scanner scanner = null;
        try {
            scanner = new Scanner(System.in);
            int n = Integer.parseInt(scanner.nextLine());
            for (int i = 0; i < n; i++) {
                Date epoch = epochTime();
                Date input = new SimpleDateFormat("dd MM yyyy")
                    .parse(scanner.nextLine());
                long numberOfDays = getNumberOfDays(epoch, input);
                MayanCalendar mc = toMayanCalendar(numberOfDays);
                System.out.println(mc);
            }
        } finally {
            scanner.close();
        }
    }
}

Creating a Simple Calendar Application in SWT

import java.text.SimpleDateFormat;
import java.util.Calendar;

import org.eclipse.swt.SWT;
import org.eclipse.swt.events.MouseAdapter;
import org.eclipse.swt.events.MouseEvent;
import org.eclipse.swt.graphics.Color;
import org.eclipse.swt.layout.GridData;
import org.eclipse.swt.layout.GridLayout;
import org.eclipse.swt.widgets.Button;
import org.eclipse.swt.widgets.Composite;
import org.eclipse.swt.widgets.Display;
import org.eclipse.swt.widgets.Label;
import org.eclipse.swt.widgets.Shell;
import org.eclipse.swt.widgets.Table;
import org.eclipse.swt.widgets.TableColumn;
import org.eclipse.swt.widgets.TableItem;

public class JCalendar {
    private static Calendar currentTime = Calendar.getInstance();
    private static Label dateLabel;
    private static Table table;
    
    private static void updateDate(Calendar calendar) {
        dateLabel.setText(new SimpleDateFormat("MMM YYYY").format(calendar.getTime()));
    }
    
    private static void createNavigation(final Shell shell, final Calendar calendar) {
        Composite composite = new Composite(shell, SWT.BORDER);
        composite.setLayout(new GridLayout(3, true));
        composite.setLayoutData(
            new GridData(GridData.FILL, GridData.FILL, true, true));
        
        Button leftArrowButton = new Button(composite, SWT.PUSH);
        leftArrowButton.setText("<");
        leftArrowButton.setLayoutData(
            new GridData(GridData.FILL, GridData.FILL, true, true));
        leftArrowButton.addMouseListener(new MouseAdapter() {
            @Override
            public void mouseDown(MouseEvent e) {
                calendar.add(Calendar.MONTH, -1);
                updateDate(calendar);
                updateCalendar(shell, table, calendar);
                shell.pack();
            }
        });
        
        dateLabel = new Label(composite, SWT.CENTER);
        dateLabel.setLayoutData(
            new GridData(GridData.FILL, GridData.FILL, true, true));
        updateDate(calendar);
        
        Button rightArrowButton = new Button(composite, SWT.PUSH);
        rightArrowButton.setText(">");
        rightArrowButton.setLayoutData(
            new GridData(GridData.FILL, GridData.FILL, true, true));
        rightArrowButton.addMouseListener(new MouseAdapter() {
            @Override
            public void mouseDown(MouseEvent e) {
                calendar.add(Calendar.MONTH, 1);
                updateDate(calendar);
                updateCalendar(shell, table, calendar);
                shell.pack();
            }
        });
    }
    
    private static void addRows(Shell shell, Calendar calendar) {
        int currentDayOfMonth = currentTime.get(Calendar.DAY_OF_MONTH);
        int currentYear = currentTime.get(Calendar.YEAR);
        int currentMonth = currentTime.get(Calendar.MONDAY);
        
        calendar.set(Calendar.DAY_OF_MONTH, 1);
        int dayOfWeek = calendar.get(Calendar.DAY_OF_WEEK);
        int daysInMonth = calendar.getActualMaximum(Calendar.DAY_OF_MONTH);
        int year = calendar.get(Calendar.YEAR);
        int month = calendar.get(Calendar.MONTH);
        
        TableItem item = new TableItem(table, SWT.NONE);
        for (int i = 0; i < dayOfWeek-1; i++) {
            item.setText(i, "  ");
        }
        int value = 1;
        for (int i = 0; i < 7-dayOfWeek+1; i++) {
            String day = Integer.toString(value);
            if (value < 10) {
                day = " " + value;
            }
            item.setText(i+dayOfWeek-1, day);
            value++;
        }
        
        while (value <= daysInMonth) {
            item = new TableItem(table, SWT.NONE);
            for (int j = 0; j < 7; j++) {
                if (value <= daysInMonth) {
                    if (value == currentDayOfMonth
                        && currentYear == year && currentMonth == month) {
                        Color blue = new Color(shell.getDisplay(), 0, 0, 255);
                        item.setForeground(j, blue);
                        blue.dispose();
                    }
                    String day = Integer.toString(value);
                    if (value < 10) {
                        day = " " + value;
                    }
                    item.setText(j, day);
                } else {
                    item.setText(j, "  ");
                }
                value++;
            }
        }
    }
    
    private static void updateCalendar(Shell shell, Table table, Calendar calendar) {
        table.removeAll();
        addRows(shell, calendar);
    }
    
    private static void createCalendar(Shell shell, Calendar calendar) {
        table = new Table(shell, SWT.BORDER);
        table.setLayoutData(new GridData(GridData.FILL, GridData.FILL, true, true));
        table.setLinesVisible(true);
        table.setHeaderVisible(true);

        String[] titles = {
            "S", "M", "T", "W", "T", "F", "S"
        };
        for (int i = 0; i < titles.length; i++) {
            TableColumn column = new TableColumn(table, SWT.NONE);
            column.setResizable(false);
            column.setText(titles[i]);
        }
        
        addRows(shell, calendar);
        
        for (int i = 0; i < titles.length; i++) {
            table.getColumn(i).pack();
        }
    }
    
    public static void main(String[] args) {
        
        Display display = new Display();
        Shell shell = new Shell(display,
            SWT.TITLE | SWT.CLOSE | SWT.BORDER & (~SWT.RESIZE));
        shell.setText("Calendar");
        shell.setLayout(new GridLayout());
        
        Calendar calendar = Calendar.getInstance();
        calendar.setTime(currentTime.getTime());
        createNavigation(shell, calendar);
        createCalendar(shell, calendar);
        
        shell.pack();
        shell.open();
        while (!shell.isDisposed()) {
            if (!display.readAndDispatch()) {
                display.sleep();
            }
        }
        display.dispose();
    }
}

How to Implement Digital Root in Go

Below is an implementation of Digital Root in Go.

package main

import (
    "fmt"
    "os"
    "strconv"
)

func digitalRoot(n int) int {
    if n < 10 {
        return n
    }
    sum := 0
    for n > 0 {
        sum += n % 10
        n /= 10
    }
    return digitalRoot(sum)
}

func main() {
    n, e := strconv.Atoi(os.Args[1])
    if e != nil {
        fmt.Println("Invalid number:", os.Args[1])
        os.Exit(1)
    }
    fmt.Println(digitalRoot(n))
}