How to Solve 3-Sum Problem

Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0?

package main

import (
    "fmt"
    "sort"
)

func ThreeSum(numbers []int) {
    for i := 0; i < len(numbers); i++ {
        for j := 0; j < len(numbers); j++ {
            nSearch := -(numbers[i] + numbers[j])
            index := sort.SearchInts(numbers, nSearch)
            if index < len(numbers) && numbers[index] == nSearch {
                fmt.Println(numbers[i], numbers[j], numbers[index])
            }
        }
    }
}

func main() {
    numbers := []int{-40, 30, -10, 50, 20}
    sortedNumbers := sort.IntSlice(numbers)
    sort.Sort(sortedNumbers)
    ThreeSum(sortedNumbers)
}

A Tool to Escape HTML Characters in Go

I created a handy tool to escape HTML characters, especially for pasting code in a blog like this.

Usage: ./escapehtml  [dest_dir]

If the source is a directory, the tool will scan the whole directory and escape each file found and output the escaped string to stdout (if dest_dir isn't specified) or to a file (if dest_dir is specified).

escapehtml.go

package main

import (
    "fmt"
    "os"
    "errors"
    "path/filepath"
    "io/ioutil"
    "html"
    "strings"
)

func printUsage() {
    fmt.Println("Usage:", os.Args[0],
        "<source_file/source_dir>", "[dest_dir]")
}

func errorMessage(s string) string {
    return "Error: " + s
}

type fileType struct {
    directory bool
    regularFile bool
}

func fileExists(path string) (*fileType, error) {
    file, err := os.Open(path)
    if err != nil {
        if os.IsNotExist(err) {
            return nil, errors.New(
                errorMessage(path + " does not exist"))
        }
    }
    defer file.Close()
    fileInfo, err := file.Stat()
    if err != nil {
        return nil, err
    }
    if fileInfo.IsDir() {
        return &fileType{directory: true}, nil
    }
    return &fileType{regularFile: true}, nil
}

func validateArgs() (bool, error) {
    if len(os.Args) != 2 && len(os.Args) != 3 {
        return false, nil
    }

    if _, err := fileExists(os.Args[1]); err != nil {
        return false, err
    }
    if len(os.Args) == 3 {
        ft, _ := fileExists(os.Args[2])
        if ft != nil && !ft.directory {
            return false, errors.New(
                errorMessage(os.Args[2] + " must be a directory"))
        }
    }
    return true, nil
}

func printHeader(header string) {
    fmt.Println(strings.Repeat("=", 72))
    fmt.Println(header)
    fmt.Println(strings.Repeat("=", 72))
}

func escapeHTML(srcPath string, destPath string) {
    filepath.Walk(srcPath,
        func(path string, info os.FileInfo, err error) error {
            if info.IsDir() {
                return nil
            }

            b, err := ioutil.ReadFile(path)
            if err != nil {
                return nil
            }

            escapedString := html.EscapeString(string(b))
            if destPath == "" {
                printHeader(path)
                fmt.Println(escapedString)
            } else {
                if ft, _ := fileExists(destPath); ft == nil {
                    if e := os.MkdirAll(destPath, 0775); e != nil {
                        errors.New("Unable to create directory: " +
                            destPath)
                    } else {
                        fmt.Println("Creating directory: " + destPath)
                    }
                }
                newPath := filepath.Join(destPath,
                    filepath.Base(path) + ".txt")
                fmt.Println("Creating", newPath)
                e := ioutil.WriteFile(newPath, []byte(escapedString), 0644)
                if e != nil {
                    return e
                }
            }
            return nil
        })
}

func main() {
    if valid, err := validateArgs(); !valid {
        if err != nil {
            fmt.Println(err)
            os.Exit(1)
        } else {
            printUsage()
            os.Exit(1)
        }
    }

    srcPath := os.Args[1]
    destPath := ""
    if len(os.Args) == 3 {
        destPath = os.Args[2]
    }
    escapeHTML(srcPath, destPath)
}

To build it, just type

go build escapehtml.go

How to Implement Union Find Algorithms

package unionfind

type UnionFind interface {
    Find(int, int) bool
    Union(int, int)
}
//================================================
type QuickFind struct {
    Nodes []int
}

func (qf *QuickFind) Find(x, y int) bool {
    return qf.Nodes[x] == qf.Nodes[y]
}

func (qf *QuickFind) Union(x, y int) {
    tmp := qf.Nodes[x]
    qf.Nodes[x] = qf.Nodes[y]
    for i := 0; i < len(qf.Nodes); i++ {
        if qf.Nodes[i] == tmp {
            qf.Nodes[i] = qf.Nodes[y]
        }
    }
}
//================================================
type QuickUnion struct {
    Nodes []int
}

func (qu *QuickUnion) Find(x, y int) bool {
    return qu.root(x) == qu.root(y)
}

func (qu *QuickUnion) Union(x, y int) {
    rootX := qu.root(x)
    rootY := qu.root(y)
    qu.Nodes[rootX] = qu.Nodes[rootY]
}

func (qu *QuickUnion) root(x int) int {
    for qu.Nodes[x] != x {
        x = qu.Nodes[x]
    }
    return x
}
//================================================
type WeightedQuickUnion struct {
    Nodes []int
    sizes []int
}

func (wqu *WeightedQuickUnion) Find(x, y int) bool {
    return wqu.root(x) == wqu.root(y)
}

func (wqu *WeightedQuickUnion) Union(x, y int) {
    rootX := wqu.root(x)
    rootY := wqu.root(y)
    if wqu.sizes[rootX] < wqu.sizes[rootY] {
        wqu.Nodes[rootX] = wqu.Nodes[rootY]
        wqu.sizes[rootY] += wqu.sizes[rootX]
    } else {
        wqu.Nodes[rootY] = wqu.Nodes[rootX]
        wqu.sizes[rootX] += wqu.sizes[rootY]
    }
}

func (wqu *WeightedQuickUnion) root(x int) int {
    for wqu.Nodes[x] != x {
        x = wqu.Nodes[x]
    }
    return x
}