import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
public class MergeSortForkJoin {
public static class MergeSortTask extends RecursiveAction {
private static final long serialVersionUID = 1L;
private final List<Integer> list;
private final int lo;
private final int hi;
public MergeSortTask(List<Integer> list, int lo, int hi) {
this.list = list;
this.lo = lo;
this.hi = hi;
}
@Override
protected void compute() {
if (lo >= hi) {
return;
} else {
int mid = (lo + hi) / 2;
MergeSortTask task1 = new MergeSortTask(list, lo, mid);
MergeSortTask task2 = new MergeSortTask(list, mid+1, hi);
invokeAll(task1, task2);
merge(list, lo, mid, hi);
}
}
private void merge(List<Integer> list, int lo, int mid, int hi) {
List<Integer> tmp = new ArrayList<>();
for (int i : list) {
tmp.add(i);
}
int left = lo;
int right = mid + 1;
int idx = lo;
while (left <= mid && right <= hi) {
if (tmp.get(left) <= tmp.get(right)) {
Integer element = tmp.get(left);
list.set(idx, element);
left++;
idx++;
} else {
Integer element = tmp.get(right);
list.set(idx, element);
right++;
idx++;
}
}
while (left <= mid) {
Integer element = tmp.get(left);
list.set(idx, element);
idx++;
left++;
}
while (right <= hi) {
Integer element = tmp.get(right);
list.set(idx, element);
idx++;
right++;
}
}
}
public static void main(String[] args) throws Exception {
ForkJoinPool pool = new ForkJoinPool();
List<Integer> list = Arrays.asList(4, 9, 1, 5, 8, 0, 7, 6, 3, 2);
System.out.println("Unsorted: " + list);
MergeSortTask task = new MergeSortTask(list, 0, list.size()-1);
try {
do {
pool.execute(task);
} while (!task.isDone());
} finally {
pool.shutdown();
}
System.out.println("Sorted: " + list);
}
}
Showing posts with label Algorithm. Show all posts
Showing posts with label Algorithm. Show all posts
Monday, August 17, 2015
Parallel Merge Sort using Fork and Join
Wednesday, March 26, 2014
How to Solve Diagonal Print
Given a string and a number, and print the string diagonally filling in
empty space with periods and going down as many lines as the given number.
So "Peter piper picked a peck of pickled peppers" with n = 10 becomes
P.........r......... .........i.........p... .e......... .........p.........c.........e.. ..t.........p.........e.........k.........r. ...e.........i.........c.........l.........s ....r.........c.........k.........e......... ..... .........k......... .........d........ ......P.........e.........o......... ....... .......i.........d.........f.........P...... ........p......... ......... .........e..... .........e.........a.........p.........p....
package main
import (
"fmt"
"os"
"strconv"
)
func main() {
str := os.Args[1]
n, _ := strconv.Atoi(os.Args[2])
for i := 0; i < n; i++ {
for k := 0; k < i; k++ {
fmt.Print(".")
}
for j := 0; j < len(str)-i; j++ {
if (j % n == 0 && j+1 < len(str)) {
fmt.Print(string(str[j+i]))
} else {
fmt.Print(".")
}
}
fmt.Println()
}
}
Sunday, January 12, 2014
How to Convert a BST to a Doubly Linked List In-Place
Problem:
Convert a BST to a doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.
package main
import (
"fmt"
)
type Node struct {
Value int
Left *Node
Right *Node
}
type LinkedList struct {
Front *Node
Back *Node
}
// this is the actual algorithm that converts a BSt into a doubly linked list
// the rest of the code is just to make unit testing easier
func (l *LinkedList) ToLinkedList(node *Node) {
if node == nil {
return
}
l.ToLinkedList(node.Left)
node.Left = l.Back
if l.Back != nil {
l.Back.Right = node
} else {
l.Front = node
}
l.Back = node
l.ToLinkedList(node.Right)
}
type BST struct {
Root *Node
}
func (b *BST) Add(value int) {
b.Root = b.add(b.Root, value)
}
func (b *BST) add(node *Node, value int) *Node {
if node == nil {
return &Node{value, nil, nil}
}
if node.Value > value {
node.Left = b.add(node.Left, value)
} else if node.Value < value {
node.Right = b.add(node.Right, value)
}
return node
}
func main() {
values := []int{8, 3, 10, 1, 6, 14, 4, 7, 13}
bst := BST{}
for _, v := range values {
bst.Add(v)
}
ll := LinkedList{}
ll.ToLinkedList(bst.Root)
for n := ll.Front; n != nil; n = n.Right {
fmt.Print(n.Value, " ")
}
fmt.Println()
for n := ll.Back; n != nil; n = n.Left {
fmt.Print(n.Value, " ")
}
fmt.Println()
}
Output:
1 3 4 6 7 8 10 13 14 14 13 10 8 7 6 4 3 1
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))
}
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:
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] 132This 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, RUSTOutput:
[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
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 aabbOutputs:
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 zUsing 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".
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
{"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:
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:
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 2012Sample 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();
}
}
}
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]
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)
}
}
Monday, December 17, 2012
How to Solve Cutting Rod Problem
This solution uses memoization.
#!/usr/bin/env python
def find_max(list_tuples):
if len(list_tuples) == 0:
return None
maximum = list_tuples[0]
for i in xrange(1, len(list_tuples)):
if maximum[0] < list_tuples[i][0]:
maximum = list_tuples[i]
return maximum
memo = {}
def cutting_rod(prices, ncuts):
if ncuts == 0:
return (0, [])
if ncuts in memo:
return memo[ncuts]
tmp = []
for i in xrange(0, ncuts):
r = cutting_rod(prices, ncuts-i-1)
new_list = list(r[1])
new_list.append(i)
value = prices[i] + r[0]
tmp.append((value, new_list))
result = find_max(tmp)
memo[ncuts] = result
return result
if __name__ == '__main__':
p = [2, 5, 6, 7]
r = cutting_rod(p, len(p))
print "Prices:", p
print "Optimal value:", r[0]
print "Indices:", r[1]
print "Cuts:", [p[x] for x in r[1]]
Output:
Prices: [2, 5, 6, 7] Optimal value: 10 Indices: [1, 1] Cuts: [5, 5]
Subscribe to:
Posts (Atom)