Wednesday, November 6, 2013

How to Embed Python into C++

Below is a simple example how to embed Python into C++.
#include <iostream>
#include <Python.h>

int main(int argc, char* argv[]) {
    Py_Initialize();
    PyRun_SimpleString("import math; a = 100; result = math.log10(100)");
    PyObject* module = PyImport_AddModule("__main__");
    PyObject* dictionary = PyModule_GetDict(module);
    PyObject* result = PyDict_GetItemString(dictionary, "result");
    double resultValue = PyFloat_AsDouble(result);
    std::cout << "result: " << resultValue << std::endl;
    Py_Finalize();
    return 0;
}
Output:
result: 2

Thursday, October 31, 2013

How to Solve Max Volume Problem

My solution for max volume problem.
package main

import (
    "fmt"
)

func maxVolume(a []int) int {
    left := 0
    right := len(a) - 1
    volume := 0
    total := 0
    for left != right {
        if a[left] <= a[right] {
            for i := left + 1; i < len(a); i++ {
                if a[left] > a[i] {
                    volume += a[left] - a[i]
                } else {
                    left = i
                    total += volume
                    volume = 0
                    break
                }
            }
        } else {
            for i := right - 1; i >= left; i-- {
                if a[right] > a[i] {
                    volume += a[right] - a[i]
                } else {
                    right = i
                    total += volume
                    volume = 0
                    break
                }
            }
        }
    }
    return total
}

func main() {
    fmt.Println(maxVolume([]int{2, 5, 1, 2, 3, 4, 7, 7, 6}) == 10)
    fmt.Println(maxVolume([]int{2, 5, 1, 3, 1, 2, 1, 7, 7, 6}) == 17)
    fmt.Println(maxVolume([]int{2, 3, 1, 2, 3, 1, 3}) == 5)
    fmt.Println(maxVolume([]int{1, 2, 3, 4, 5, 6, 7, 8, 9}) == 0)
    fmt.Println(maxVolume([]int{9, 8, 7, 6, 5, 4, 3, 2, 1}) == 0)
    fmt.Println(maxVolume([]int{1, 1, 1, 1, 1}) == 0)
    fmt.Println(maxVolume([]int{1, 0, 1}) == 1)
    fmt.Println(maxVolume([]int{5, 0, 5}) == 5)
    fmt.Println(maxVolume([]int{5, 0, 4}) == 4)
    fmt.Println(maxVolume([]int{4, 0, 5}) == 4)
    fmt.Println(maxVolume([]int{4, 0, 5, 0, 2}) == 6)
    fmt.Println(maxVolume([]int{0, 1, 0, 1, 0}) == 1)
    fmt.Println(maxVolume([]int{0, 1, 0, 0, 1, 0}) == 2)
    fmt.Println(maxVolume([]int{4, 2, 2, 1, 1, 1, 3}) == 8)
    fmt.Println(maxVolume([]int{0, 3, 2, 1, 4}) == 3)
    fmt.Println(maxVolume([]int{1, 0, 1, 0}) == 1)
    fmt.Println(maxVolume([]int{1, 0, 1, 2, 0, 2}) == 3)
    fmt.Println(maxVolume([]int{2, 5, 1, 2, 3, 4, 7, 7, 6}) == 10)
    fmt.Println(maxVolume([]int{5, 1, 0, 1}) == 1)
    fmt.Println(maxVolume([]int{2, 5, 1, 2, 3, 4, 7, 7, 6, 3, 5}) == 12)
    fmt.Println(maxVolume([]int{3, 0, 1, 0, 2}) == 5)
}

How to Solve Spiral Problem

My solution for spiral problem.
package main

import (
    "fmt"
)

func spiral(height, width, row, col int) []int {
    a := createSlice(height, width)
    result := []int{}
    r := row - 1
    c := col - 1
    result = append(result, a[r][c])
    x := 1
    for z := 0; (height * width) != len(result); z++ {
        for i := 0; i < x; i++ {
            r, c = up(r, c)
            if !outOfBoundary(height, width, r, c) {
                result = append(result, a[r][c])
            }
        }
        for i := 0; i < x; i++ {
            r, c = left(r, c)
            if !outOfBoundary(height, width, r, c) {
                result = append(result, a[r][c])
            }
        }
        x += 1
        for i := 0; i < x; i++ {
            r, c = down(r, c)
            if !outOfBoundary(height, width, r, c) {
                result = append(result, a[r][c])
            }
        }
        for i := 0; i < x; i++ {
            r, c = right(r, c)
            if !outOfBoundary(height, width, r, c) {
                result = append(result, a[r][c])
            }
        }
        x += 1
    }
    return result
}

func outOfBoundary(height, width, row, col int) bool {
    return !((row >= 0 && row < height) && (col >= 0 && col < width))
}

func left(row, col int) (int, int) {
    return row, col - 1
}

func right(row, col int) (int, int) {
    return row, col + 1
}

func up(row, col int) (int, int) {
    return row - 1, col
}

func down(row, col int) (int, int) {
    return row + 1, col
}

func createSlice(height, width int) [][]int {
    a := make([][]int, height)
    n := 1
    for i := 0; i < height; i++ {
        a[i] = make([]int, width)
        for j := 0; j < width; j++ {
            a[i][j] = n
            n += 1
        }
    }
    return a
}

func main() {
    fmt.Println(spiral(5, 5, 3, 3))
    fmt.Println(spiral(2, 4, 1, 2))
    fmt.Println(spiral(5, 5, 4, 2))
}

Sunday, October 27, 2013

How to Call C++ from Go

.
└── src
    └── cgotest
        ├── hello
        │   ├── cpp
        │   │   └── hellocpp.cpp
        │   ├── hello.go
        │   ├── include
        │   │   └── hellocpp.h
        │   └── lib
        │       └── libhellocpp.so
        └── main.go
hellocpp.h
#ifndef _HELLOCPP_H_
#define _HELLOCPP_H_

#ifdef __cplusplus
extern "C" {
#endif
    void SayHello();
#ifdef __cplusplus
}
#endif

#endif
hellocpp.cpp
#include <iostream>
#include "hellocpp.h"
using namespace std;

void SayHello() {
    cout << "Hello from C++" << endl;
}
Let's now create a C++ shared library.
cd $GOPATH/src/cgotest/hello
mkdir lib
g++ -Wall -shared -fpic cpp/hellocpp.cpp -Iinclude -o lib/hellocpp.so
hello.go
package hello

// #cgo CFLAGS: -Iinclude
// #cgo LDFLAGS: -Llib -lhellocpp
// #include "hellocpp.h"
import "C"

func HelloFromCpp() {
    C.SayHello()
}
main.go
package main

import "cgotest/hello"

func main() {
    hello.HelloFromCpp()
}
There seems to be a bug that makes setting relative paths in LDFLAGS not to work. The workaround is to set LIBRARY_PATH env variable using absolute path.
cd $GOPATH
export LIBRARY_PATH=$GOPATH/src/cgotest/hello/lib
export LD_LIBRARY_PATH=$LIBRARY_PATH
go build cgotest
./cgotest
Output:
Hello from C++

Wednesday, October 23, 2013

How to Create a Self-Extracting Installer in Bash

The basic idea of creating a self-extracting installer in Bash is really straightforward. We just need to append the binary package, e.g. an archive file in our installer script. Here's a simple example on how to do that.
  1. Create an installer script
  2. #!/bin/bash
    
    echo "Running self-extracting installer"
    
    ARCHIVE=`awk '/^__START_HERE__/ {print NR + 1; exit 0; }' $0`
    echo $ARCHIVE
    tail -n+$ARCHIVE $0 | tar xzv
    
    exit 0
    
    __START_HERE__
    
  3. Append an archive file into an installer script
  4. cat myproject.tar.gz >> installer
    
  5. Give an executable permission
  6. chmod +x installer
    
  7. Execute the installer script
  8. ./installer
    

Tuesday, October 15, 2013

How to Programmatically Download Dependencies using Ivy

Below is an example how to programmatically download dependencies using Ivy.
apply plugin: "java"
apply plugin: "eclipse"

repositories {
    mavenCentral()
}

dependencies {
    compile "org.apache.ivy:ivy:2.3.0"
    testCompile "junit:junit:4.10"
}
import java.util.ArrayList;
import java.util.List;

import org.apache.ivy.Main;

public class Test {
    public static void main(String[] args) throws Exception {
        List<String> list = new ArrayList<>();
        list.add("-settings");
        list.add("ivysettings.xml");
        list.add("-dependency");
        list.add("testgroup");
        list.add("testartifact");
        list.add("1.0.0");
        list.add("-retrieve");
        list.add("lib/[artifact]-[revision].[ext]");
        String[] newArgs = new String[list.size()];
        Main.main(list.toArray(newArgs));
    }
}
<ivysettings>
  <settings defaultResolver="myResolver"/>
  <property name="ivy.checksums" value="" />
  <include url="${ivy.default.settings.dir}/ivysettings-public.xml"/>
  <include url="${ivy.default.settings.dir}/ivysettings-shared.xml"/>
  <include url="${ivy.default.settings.dir}/ivysettings-local.xml"/>
  <include url="${ivy.default.settings.dir}/ivysettings-main-chain.xml"/>
  <include url="${ivy.default.settings.dir}/ivysettings-default-chain.xml"/>
  <resolvers>
    <url name="testivy">
      <ivy pattern="http://myivyserver/[organisation]/[module]/[revision]/ivy-[revision].xml" /> -->
      <artifact pattern="http://myivyserver/[organisation]/[module]/[revision]/[artifact]-[revision].[ext]" />
    </url>
    <ibiblio name="testmaven" m2compatible="true" root="http://mymavenserver/maven" />
    <chain name="myResolver">
      <resolver ref="default" />
      <resolver ref="testivy" />
      <resolver ref="testmaven" />
    </chain>
  </resolvers>
</ivysettings>

Thursday, September 5, 2013

How to Solve Triangle Minimal Path in Go

Write a function which calculates the sum of the minimal path through a triangle. The triangle is represented as a collection of vectors. The path should start at the top of the triangle and move to an adjacent number on the next row until the bottom of the triangle is reached.
assert
f(  [[1]
    [2 4]
   [5 1 4]
  [2 3 4 5]] ) == 7 ; 1+2+1+3

assert
f(    [[3]
      [2 4]
     [1 9 3]
    [9 9 2 4]
   [4 6 6 7 8]
  [5 7 3 5 1 4]] ) == 20 ; 3+4+3+2+7+1
This is an iterative solution in Go.
package main

import (
    "fmt"
)

func min(m map[int][]int) int {
    r := m[0][0]
    for _, v := range m {
        for _, v1 := range v {
            if r > v1 {
                r = v1
            }
        }
    }
    return r
}

func triangleMinPath(input [][]int) int {
    result := map[int][]int{}
    result[0] = input[0]
    for i := 1; i < len(input); i++ {
        result = minPath(input[i], result)
    }
    return min(result)
}

func minPath(input []int, accu map[int][]int) map[int][]int {
    result := map[int][]int{}
    for i := 0; i < len(input); i++ {
        for j := 0; j < len(accu[i]); j++ {
            if _, ok := result[i]; !ok {
                result[i] = []int{}
            }
            result[i] = append(result[i], input[i]+accu[i][j])
            if _, ok := result[i+1]; !ok {
                result[i+1] = []int{}
            }
            result[i+1] = append(result[i+1], input[i+1]+accu[i][j])
        }
    }
    return result
}

func main() {
    fmt.Println(triangleMinPath([][]int{{1}, {2, 4}, {5, 1, 4}, {2, 3, 4, 5}})) // 7
    fmt.Println(triangleMinPath([][]int{{3}, {2, 4}, {1, 9, 3}, {9, 9, 2, 4}, {4, 6, 6, 7, 8}, {5, 7, 3, 5, 1, 4}})) // 20
    fmt.Println(triangleMinPath([][]int{{3}})) // 3
    fmt.Println(triangleMinPath([][]int{{3}, {1, 2}})) // 4
}

Thursday, August 15, 2013

How to Rearrange an Array in Alternate Positive and Negative Position

Problem:
Given an array containing both positive and negative elements, arrange in such a manner; 1 positive number, then 1 negative,then 1 positive and so on. If there are more negative numbers, extra negative numbers should be kept at the end and vice versa. Note that the order of negative and positive elements should be same in the modified array and you are not allowed to use any extra space.

Sample inputs and outputs:

Input : [1 -2 3 4 -5 -6 7 8 -9 10 11]
Output: [1 -2 3 -5 4 -6 7 -9 8 10 11]

Input : [-1 2 3 4 -5 -6 7 8 -9 10 11]
Output: [-1 2 -5 3 -6 4 -9 7 8 10 11]

Input : [-1 2 -3 4 -5 6 -7 8 -9 10 11]
Output: [-1 2 -3 4 -5 6 -7 8 -9 10 11]

Input : [1 2 3 4 5 6 7 8 9 10 11]
Output: [1 2 3 4 5 6 7 8 9 10 11]

Input : [-1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11]
Output: [-1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11]
package main

import (
    "fmt"
)

func shiftAndSwap(a []int, fromIdx, toIdx int) {
    tmp := a[toIdx]
    for j := toIdx; j > fromIdx; j-- {
        a[j] = a[j-1]
    }
    a[fromIdx] = tmp
}

func arrange(a []int) {
    positive := false
    if a[0] < 0 {
        positive = true
    }
    fromIdx := 1
    for i := 1; i < len(a); i++ {
        if positive {
            if a[i] >= 0 {
                if fromIdx != i {
                    shiftAndSwap(a, fromIdx, i)
                    i = fromIdx
                }
                positive = false
                fromIdx = i + 1
            }
        } else { // negative
            if a[i] < 0 {
                if fromIdx != i {
                    shiftAndSwap(a, fromIdx, i)
                    i = fromIdx
                }
                positive = true
                fromIdx = i + 1
            }
        }
    }
}

func main() {
    a := []int{1, -2, 3, 4, -5, -6, 7, 8, -9, 10, 11}
    fmt.Println("Input :", a)
    arrange(a)
    fmt.Println("Output:", a)

    a = []int{-1, 2, 3, 4, -5, -6, 7, 8, -9, 10, 11}
    fmt.Println("Input :", a)
    arrange(a)
    fmt.Println("Output:", a)

    a = []int{-1, 2, -3, 4, -5, 6, -7, 8, -9, 10, 11}
    fmt.Println("Input :", a)
    arrange(a)
    fmt.Println("Output:", a)
    
    a = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
    fmt.Println("Input :", a)
    arrange(a)
    fmt.Println("Output:", a)

    a = []int{-1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11}
    fmt.Println("Input :", a)
    arrange(a)
    fmt.Println("Output:", a)
}

Tuesday, August 6, 2013

How to Solve Maximum Sum of a Subsequence Problem

Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.
Input: [3, 2, 7, 10]
Output: [3 10] 13

Input: [3, 2, 5, 10, 7]
Output: [3 5 7] 15

Input: [3, 20, 5, 10, 7]
Output: [20 10] 30

Input: [3, 10, 30, 100, 40]
Output: [10 100] 110

Input: [3, 10, 1, 2, 3, 30, 4, 40, 5, 6, 50]
Output: [10 2 30 40 50] 132
This solution is not an optimal solution.
package main

import (
    "fmt"
)

func sum(a []int) int {
    s := 0
    for _, v := range a {
        s += v
    }
    return s
}

func maxSumSubsequence(a []int) []int {
    result := [][]int{}
    // odd
    recurseMaxSumSub(a, 0, []int{}, &result)
    // even
    recurseMaxSumSub(a, 1, []int{}, &result)
    max := 0
    var maxSubsequence []int
    for _, v := range result {
        s := sum(v)
        if max == 0 {
            max = s
            maxSubsequence = v
        } else if max < s {
            max = s
            maxSubsequence = v
        }
    }
    return maxSubsequence
}

func recurseMaxSumSub(a []int, idx int, accu []int, result *[][]int) {
    if idx < len(a) {
        recurseMaxSumSub(a, idx+2, append(accu, a[idx]), result)
    } else {
        *result = append(*result, accu)
    }

    if idx+1 < len(a) {
        recurseMaxSumSub(a, idx+3, append(accu, a[idx+1]), result)
    } else {
        *result = append(*result, accu)
    }
}

func main() {
    out := maxSumSubsequence([]int{3, 2, 7, 10})
    fmt.Println(out, sum(out))
    out = maxSumSubsequence([]int{3, 2, 5, 10, 7})
    fmt.Println(out, sum(out))
    out = maxSumSubsequence([]int{3, 20, 5, 10, 7})
    fmt.Println(out, sum(out))
    out = maxSumSubsequence([]int{3, 10, 30, 100, 40})
    fmt.Println(out, sum(out))
    out = maxSumSubsequence([]int{3, 10, 1, 2, 3, 30, 4, 40, 5, 6, 50})
    fmt.Println(out, sum(out))
}

Friday, August 2, 2013

How to Solve Word Search Puzzle

Write a program that builds a 2D array from a given input string and search for some words from the input and then output the indices for every word found. The search can be horizontal, vertical, and diagonal.

Input:

String: SCALAALHPCUAMNJWAYDXBOSRVSTRVOYOAWKHUQZPJVUEOSNNPFOKLNTLMCEGULA
Number of column: 9
Words to search: RUBY, PYTHON, JAVA, HASKELL, GO, LUA, ML, AWK, JS, SCALA, CPP, RUST  
Output:
[S C A L A A L H P]
[C U A M N J W A Y]
[D X B O S R V S T]
[R V O Y O A W K H]
[U Q Z P J V U E O]
[S N N P F O K L N]
[T L M C E G U L A]

SCALA [{0 0} {0 1} {0 2} {0 3} {0 4}]
HASKELL [{0 7} {1 7} {2 7} {3 7} {4 7} {5 7} {6 7}]
PYTHON [{0 8} {1 8} {2 8} {3 8} {4 8} {5 8}]
ML [{1 3} {0 3}]
JS [{1 5} {2 4}]
RUST [{3 0} {4 0} {5 0} {6 0}]
AWK [{3 5} {3 6} {3 7}]
JAVA [{4 4} {3 5} {2 6} {1 7}]
LUA [{5 7} {4 6} {3 5}]
ML [{6 2} {6 1}]
CPP [{6 3} {5 3} {4 3}]
GO [{6 5} {5 5}]
package main

import (
    "fmt"
)

type index struct {
    row int
    col int
}

func create2DSlice(s string, nCol int) [][]string {
    nRow := len(s) / nCol
    slice := make([][]string, nRow, nRow)
    idx := 0
    for i := 0; i < nRow; i++ {
        slice[i] = make([]string, nCol, nCol)
        for j := 0; j < nCol; j++ {
            slice[i][j] = string(s[idx])
            idx++
        }
    }
    return slice
}

func isOutOfRange(nRow, nCol, fromRow, toRow, fromCol, toCol int) bool {
    if fromRow >= 0 && fromRow < nRow && fromCol >= 0 && fromCol < nCol &&
        toRow >= 0 && toRow < nRow && toCol >= 0 && toCol < nCol {
        return false
    }
    return true
}

func search(slice [][]string, word string, nRow, nCol, fromRow, toRow, fromCol, toCol int) {
    rowInc := 1
    if fromRow > toRow {
        rowInc = -1
    } else if fromRow == toRow {
        rowInc = 0
    }
    colInc := 1
    if fromCol > toCol {
        colInc = -1
    } else if fromCol == toCol {
        colInc = 0
    }
    if !isOutOfRange(nRow, nCol, fromRow, toRow, fromCol, toCol) {
        str := ""
        indices := []index{}
        for i, r, c := 0, fromRow, fromCol; i < len(word); i++ {
            indices = append(indices, index{r, c})
            str += slice[r][c]
            r = r + rowInc
            c = c + colInc
        }
        w := str
        if w == word {
            fmt.Println(word, indices)
        }
    }
}

func wordSearch(s string, nCol int, words []string) {
    twoDSlice := create2DSlice(s, nCol)
    for i := 0; i < len(twoDSlice); i++ {
        fmt.Println(twoDSlice[i])
    }
    fmt.Println("========")
    fmt.Println("Solution")
    fmt.Println("========")
    for row := 0; row < len(twoDSlice); row++ {
        for col := 0; col < len(twoDSlice[row]); col++ {
            for _, word := range words {
                // up
                search(twoDSlice, word, len(twoDSlice), len(twoDSlice[row]),
                    row, row-len(word)+1, col, col)
                // down
                search(twoDSlice, word, len(twoDSlice), len(twoDSlice[row]),
                    row, row+len(word)-1, col, col)
                // left
                search(twoDSlice, word, len(twoDSlice), len(twoDSlice[row]),
                    row, row, col, col-len(word)+1)
                // right
                search(twoDSlice, word, len(twoDSlice), len(twoDSlice[row]),
                    row, row, col, col+len(word)-1)
                // upper left diagonal
                search(twoDSlice, word, len(twoDSlice), len(twoDSlice[row]),
                    row, row-len(word)+1, col, col-len(word)+1)
                // upper right diagonal
                search(twoDSlice, word, len(twoDSlice), len(twoDSlice[row]),
                    row, row-len(word)+1, col, col+len(word)-1)
                // lower left diagonal
                search(twoDSlice, word, len(twoDSlice), len(twoDSlice[row]),
                    row, row+len(word)-1, col, col-len(word)+1)
                // lower right diagonal
                search(twoDSlice, word, len(twoDSlice), len(twoDSlice[row]),
                    row, row+len(word)-1, col, col+len(word)-1)
            }
        }
    }
}

func main() {
    s := "SCALAALHPCUAMNJWAYDXBOSRVSTRVOYOAWKHUQZPJVUEOSNNPFOKLNTLMCEGULA"
    words := []string{"RUBY", "PYTHON", "JAVA", "HASKELL", "GO", "LUA", "ML",
        "AWK", "JS", "SCALA", "CPP", "RUST"}
    wordSearch(s, 9, words)
}

Thursday, July 25, 2013

How to Solve Minimum Difference Problem

Given two arrays, sorted and exactly the same length, write a function that finds a pair of numbers, one from each of the arrays,such that the difference between both is as small as possible.
Input:
[0, 3, 5, 8, 10], [6, 9, 12, 13, 14]
Output:
[5, 6]

Input:
[7.12, 15, 20, 21], [1, 5, 9, 13, 17]
Output:
[12, 13]

Input:
[6, 10, 15, 18, 21], [16, 17, 18, 23, 27]
Output:
[8, 8]
package main

import (
    "fmt"
)

func diff(n int) int {
    if n < 0 {
        return n * -1
    }
    return n
}

func minDiff(a []int, b []int) (int, int) {
    min := -1
    var result1, result2 int
    for i, j := 0, 0; i < len(a) && j < len(b); {
        newMin := diff(a[i] - b[j])
        if min == -1 {
            min = newMin
            result1, result2 = a[i], b[j]
        } else {
            if newMin < min {
                min = newMin
                result1, result2 = a[i], b[j]
            }
        }
        if a[i] < b[j] {
            i++
        } else {
            j++
        }
    }
    return result1, result2
}

func main() {
    fmt.Println(minDiff([]int{0, 3, 5, 8, 10}, []int{6, 9, 12, 13, 14}))
    fmt.Println(minDiff([]int{7, 12, 15, 20, 21}, []int{1, 5, 9, 13, 17}))
    fmt.Println(minDiff([]int{6, 10, 15, 18, 21}, []int{16, 17, 18, 23, 27}))
}

Friday, July 12, 2013

How to Solve Balancing Arrays Problem

Given an array of numbers, return the index at which the array can be balanced by all numbers on the left side add up the sum of all numbers of the right side.

For example:
an array with [1,5,6,7,9,10] can be balanced by splitting the array at position 4
an array with [1, 5, 6, 7, 9, 10] can be balanced by splitting the array at position 4
an array with [3, 8, 4, 15] can be balanced by splitting the array at position 3
an array with [1, 8, 1, 2, 8]) can be balanced by splitting the array at position 3
an array with [1, 3, 5, 1, 2] can't be balanced, hence position -1

package main

import (
    "fmt"
)

func balancingArrays(slice []int) int {
    left := 0
    right := len(slice) - 1
    sumLeft := 0
    sumRight := 0
    for left <= right {
        if sumLeft < sumRight {
            sumLeft += slice[left]
            left++
        } else {
            sumRight += slice[right]
            right--
        }
    }
    if sumLeft == sumRight {
        return left
    }
    return -1
}

func main() {
    fmt.Println(balancingArrays([]int{1, 5, 6, 7, 9, 10})) // 4
    fmt.Println(balancingArrays([]int{3, 8, 4, 15}))       // 3
    fmt.Println(balancingArrays([]int{1, 8, 1, 2, 8}))     // 3
    fmt.Println(balancingArrays([]int{1, 3, 5, 1, 2}))     // -1
}

Wednesday, June 12, 2013

How to Solve the Longest Substring Problem

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"))
}

Friday, May 3, 2013

How to Solve On-Screen Keyboard Problem

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

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

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
--------------------------------

Friday, April 19, 2013

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();
            }
        }
    }
    

    Tuesday, April 16, 2013

    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();
        }
    }
    

    Monday, April 15, 2013

    How to Implement Digital Root

    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))
    }
    

    Thursday, April 11, 2013

    How to Implement Powerset

    Below is a simple implementation of Powerset in Go.
    package main
    
    import (
        "fmt"
        "sort"
        "strings"
    )
    
    func powerset(set []int) [][]int {
        m := map[string][]int{}
        m = recursePowerset(set, m)
        result := [][]int{set}
        for _, v := range m {
            result = append(result, v)
        }
        return result
    }
    
    func join(s []int) string {
        result := []string{}
        for _, v := range s {
            result = append(result, string(v))
        }
        return strings.Join(result, ",")
    }
    
    func recursePowerset(set []int, accumulator map[string][]int) map[string][]int {
        if len(set) == 0 {
            return accumulator
        }
        for i, _ := range set {
            subset := make([]int, len(set[:i]))
            copy(subset, set[:i])
            subset = append(subset, set[i+1:len(set)]...)
            sort.Ints(subset)
            key := join(subset)
            accumulator[key] = subset
            accumulator = recursePowerset(subset, accumulator)
        }
        return accumulator
    }
    
    func main() {
        set := []int{1, 2, 3, 4}
        powset := powerset(set)
        // pretty print the output
        for i := 0; i <= len(set); i++ {
            for _, v := range powset {
                if len(v) == i {
                    fmt.Println(v)
                }
            }
        }
    }
    
    Output:
    []
    [1]
    [4]
    [2]
    [3]
    [1 2]
    [2 4]
    [1 4]
    [3 4]
    [1 3]
    [2 3]
    [1 3 4]
    [2 3 4]
    [1 2 4]
    [1 2 3]
    [1 2 3 4]
    

    Monday, April 8, 2013

    How to Publish Artifacts with Gradle

    In this blog, I'm going to show you how to publish and consume artifacts with Gradle using both Ivy and Maven plugins.

  • Publishing via Ivy (old way)
  • apply plugin: "java"
    
    group = "test"
    version = "0.0.1"
    
    repositories {
        mavenCentral()
    }
    
    uploadArchives {
        repositories {
            ivy {
                url "file://home/foo/tmp/ivy"
            }
        }
    }
    
    dependencies {
        // just an example to test transitive dependencies
        compile "ch.qos.logback:logback-classic:1.0.11"
        compile "ch.qos.logback:logback-core:1.0.11"
    }
    
  • Publishing via Ivy (new way)
  • apply plugin: "java"
    apply plugin: "ivy-publish"
    
    group = "test"
    version = "0.0.1"
    
    repositories {
        mavenCentral()
    }
    
    publishing {
        publications {
            ivyJava(IvyPublication) {
                from components.java
            }
        }
        repositories {
            ivy {
                url "file://home/foo/tmp/ivy"
            }
        }
    }
    
    dependencies {
        // just an example to test transitive dependencies
        compile "ch.qos.logback:logback-classic:1.0.11"
        compile "ch.qos.logback:logback-core:1.0.11"
    }
    
  • Publishing via Maven (old way)
  • apply plugin: "java"
    apply plugin: "maven"
    
    group = "test"
    version = "0.0.1"
    
    repositories {
        mavenCentral()
    }
    
    uploadArchives {
        repositories {
            mavenDeployer {
                repository(url: "file:///home/foo/tmp/maven")
            }
        }
    }
    
    dependencies {
        // just an example to test transitive dependencies
        compile "ch.qos.logback:logback-classic:1.0.11"
        compile "ch.qos.logback:logback-core:1.0.11"
    }
    
  • Publishing via Maven (new way)
  • apply plugin: "java"
    apply plugin: "maven-publish"
    
    group = "test"
    version = "0.0.1"
    
    repositories {
        mavenCentral()
    }
    
    publishing {
        publications {
            mavenJava(MavenPublication) {
                from components.java
            }
       }
        repositories {
            maven {
                url "file://home/foo/tmp/maven"
            }
        }
    }
    
    dependencies {
        // just an example to test transitive dependencies
        compile "ch.qos.logback:logback-classic:1.0.11"
        compile "ch.qos.logback:logback-core:1.0.11"
    }
    
  • Consuming via Ivy
  • apply plugin: "java"
    
    version = "0.0.1"
    
    repositories {
        mavenCentral()
        ivy { url "file://home/foo/tmp/ivy" }
    }
    
    dependencies {
        compile "test:upload-artifact:0.0.1"
    }
    
  • Consuming via Maven
  • apply plugin: "java"
    
    version = "0.0.1"
    
    repositories {
        mavenCentral()
        maven { url "file://home/foo/tmp/maven" }
    }
    
    dependencies {
        compile "test:upload-artifact:0.0.1"
    }
    

    Tuesday, April 2, 2013

    How to Implement Pascal's Triangle

    My simple implementation of Pascal's Triangle in Go.
    package main
    
    import "fmt"
    import "os"
    import "strconv"
    
    func pascal(n int) [][]int {
        result := make([][]int, n)
        // initial value
        idx := 0
        result[idx] = []int{1}
        return recursePascal(idx, n, result)
    }
    
    func recursePascal(idx int, length int, accumulator [][]int) [][]int {
        if (idx == length-1) {
            return accumulator
        }
        slice := []int{1}
        for i := 0; i < len(accumulator[idx])-1; i++ {
            slice = append(slice,
                accumulator[idx][i] + accumulator[idx][i+1])
        }
        slice = append(slice, 1)
        idx++
        accumulator[idx] = slice
        return recursePascal(idx, length, accumulator)
    }
    
    func main() {
        n, _ := strconv.Atoi(os.Args[1])
        for _, v := range pascal(n) {
            fmt.Println(v)
        }
    }
    

    Tuesday, February 19, 2013

    Rebasing in SVN

    Suppose you are creating a branch from a trunk and you need to merge the commits from the trunk to the branch. Unlike Git, SVN does not really have a concept of rebasing. To do that in SVN, it requires quite a bit of work. To simplify the tasks of rebasing in SVN, I created small tools, one in Go and the other one in Python.
    svnrebase.go
    package main
    
    import (
        "bufio"
        "bytes"
        "errors"
        "fmt"
        "io"
        "os"
        "os/exec"
        "strings"
    )
    
    const BaseRevFile = "base_rev.txt"
    
    func getLatestBaseSVNRev(svnBaseURL string) (string, error) {
        out, e1 := exec.Command("svn", "info", svnBaseURL).Output()
        if e1 != nil {
            return "", errors.New("Unable to execute svn info " +
                svnBaseURL)
        }
        r := bufio.NewReader(bytes.NewReader(out))
        for {
            l, _, e2 := r.ReadLine()
            if e2 == io.EOF {
                break
            }
            s := string(l)
            if strings.Contains(s, "Revision:") {
                svnRev := strings.TrimSpace(strings.Split(s, ":")[1])
                return svnRev, nil
            }
        }
        return "", errors.New("Unable to get the SVN revision number")
    }
    
    func getOldBaseSVNRev() (string, error) {
        f, e := os.Open(BaseRevFile)
        if e != nil {
            return "", errors.New(BaseRevFile + " does not exist. " +
                "You need to create this file initially!")
        }
        defer f.Close()
        r := bufio.NewReader(f)
        l, _, _ := r.ReadLine()
        return strings.TrimSpace(string(l)), nil
    }
    
    func updateBaseSVNFile(newBaseRev string) error {
        f, e := os.OpenFile(BaseRevFile, os.O_WRONLY, 0666)
        if e != nil {
            return e
        }
        defer f.Close()
        f.Write([]byte(newBaseRev))
        return nil
    }
    
    func SVNRebase(svnBaseURL string, dryRun bool) error {
        oldBaseRev, e1 := getOldBaseSVNRev()
        if e1 != nil {
            return e1
        }
        newBaseRev, e2 := getLatestBaseSVNRev(svnBaseURL)
        if e2 != nil {
            return e2
        }
        if oldBaseRev == newBaseRev {
            fmt.Println("Your repo has already had the latest revision")
            return nil
        }
        cmd := "svn"
        args := []string{"merge"}
        if dryRun {
            args = append(args, "--dry-run")
        }
        args = append(args, svnBaseURL + "@" + oldBaseRev)
        args = append(args, svnBaseURL + "@" + newBaseRev)
        fmt.Println("Command:", cmd + " " + strings.Join(args, " "))
        c := exec.Command(cmd, args...)
        c.Stdout = os.Stdout
        c.Stdin = os.Stdout
        c.Stderr = os.Stderr
        e3 := c.Run()
        if e3 != nil {
            return e3
        }
        if !dryRun {
            updateBaseSVNFile(newBaseRev)
        }
        return nil
    }
    
    func printUsage() {
        fmt.Println("Usage:", os.Args[0], "<svn_base_url> [--dry-run]")
    }
    
    func validateArgs() {
        if len(os.Args) == 1 || len(os.Args) > 3 {
            printUsage()
            os.Exit(1)
        }
        if len(os.Args) == 3 {
            if os.Args[2] != "--dry-run" {
                fmt.Println("Error: Invalid option:", os.Args[2])
                os.Exit(1)
            }
        }
    }
    
    func main() {
        validateArgs()
        baseSVNURL := os.Args[1]
        dryRun := false
        if len(os.Args) == 3 {
            dryRun = true
        }
        if e := SVNRebase(baseSVNURL, dryRun); e != nil {
            fmt.Println("Error:", e)
        }
    }
    
    Usage: ./svnrebase  [--dry-run]
    svnrebase.py
    #!/usr/bin/env python
    import sys, subprocess, os
    
    BASE_REV_FILE = 'base_rev.txt'
    
    def get_latest_base_svn_rev(svn_base_url):
        p = subprocess.Popen(['svn', 'info', svn_base_url], stdout=subprocess.PIPE)
        for line in p.communicate()[0].split(os.linesep):
            if line.startswith('Revision:'):
                return line.split(":")[1].strip()
        return None
    
    def get_old_base_svn_rev():
        if not os.path.exists(BASE_REV_FILE):
            raise Exception(BASE_REV_FILE + ' does not exist. ' + 
                            'You need to create this file initially!')
        f = open(BASE_REV_FILE, 'r')
        return f.read().strip() 
    
    def update_base_svn_file(new_base_rev):
         f = open(BASE_REV_FILE, 'w')
         f.write(new_base_rev)
         f.close()
    
    def svn_rebase(svn_base_url, dry_run):
        old_base_rev = get_old_base_svn_rev()
        new_base_rev = get_latest_base_svn_rev(svn_base_url)
        if old_base_rev == new_base_rev:
            print 'Your repo has already had the latest revision'
            return
        cmd = ['svn', 'merge']
        if dry_run:
            cmd.append('--dry-run')
        cmd.append(svn_base_url + '@' + old_base_rev)
        cmd.append(svn_base_url + '@' + new_base_rev)
        print 'Command:', ' '.join(cmd)
        subprocess.call(cmd)
        if not dry_run:
           update_base_svn_file(new_base_rev)
    
    def print_usage():
        print 'Usage:', sys.argv[0], '<svn_base_url> [--dry-run]'
    
    def validate_args():
        if len(sys.argv) == 1 or len(sys.argv) > 3:
            print_usage()
            sys.exit(1)
        if len(sys.argv) == 3:
            if sys.argv[2] != '--dry-run':
                print 'Error: Invalid option:', sys.argv[2]
                sys.exit(1)
    
    if __name__ == '__main__':
        validate_args()
        base_svn_url = sys.argv[1]
        dry_run = True if len(sys.argv) == 3 else False
        try:
            svn_rebase(base_svn_url, dry_run)
        except Exception, e:
            print 'Error:', e
    
    Usage: ./svnrebase.py  [--dry-run]
    Initially, you need to create base_rev.txt that specifies which revision your branch was created. Subsequently, the base_rev.txt will be automatically updated by the tool.