N-ary tree serialization, Java

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

interface TreeVisitor
{
void visit(TreeNode node);
}

interface VisitableTree
{
void accept(TreeVisitor visitor);
}

class TreeNode implements VisitableTree
{
private int value;
private List children;
public TreeNode(int value)
{
this.value = value;
children = new ArrayList();
}

public void addChild(TreeNode child)
{
children.add(child);
}

public List getChildren()
{
return children;
}

public void accept(TreeVisitor visitor){
visitor.visit(this);
}

public int getValue()
{
return value;
}

public String toString(){
return "" + value;
}

}

class PreOrderTreeVisitor implements TreeVisitor
{
public void visit(TreeNode node)
{
System.out.print(node.getValue() + " [");
for(TreeNode child : node.getChildren())
{
child.accept(this);
}
System.out.print("] ");

}
}

class TreeSerializerVisitor implements TreeVisitor
{
public void visit(TreeNode node)
{
System.out.println(node.getValue());

for(TreeNode child : node.getChildren())
{
child.accept(this);
}

System.out.println("--");
}
}

class TreeBuilder
{
public TreeNode build(String input)
{
String[] lines = input.split("\n");
if(lines[0] == "--")
return null;

TreeNode currentNode = null;
List stack = new ArrayList();
for(String line : lines)
{
if(line.equals("--"))
{
currentNode = stack.remove(stack.size()-1);
continue;
}

TreeNode newNode = new TreeNode(Integer.parseInt(line));

if(currentNode == null)
{
currentNode = newNode;
stack.add(currentNode);
continue;
}
currentNode.addChild(newNode);
stack.add(currentNode);
currentNode = newNode;
}
return currentNode;
}
}

public class Main
{
public static void main(String[] args)
{
TreeNode root = new TreeNode(4);
TreeNode child1 = new TreeNode(5);
TreeNode child2 = new TreeNode(6);
child1.addChild(new TreeNode(22));
child1.addChild(new TreeNode(44));

root.addChild(child1);
root.addChild(child2);

TreeVisitor visitor = new PreOrderTreeVisitor();

TreeVisitor serializer = new TreeSerializerVisitor();
serializer.visit(root);

TreeBuilder builder = new TreeBuilder();
System.out.println("");
visitor.visit(builder.build("4\n5\n22\n--\n44\n--\n--\n6\n--\n--\n"));
System.out.println("");
visitor.visit(root);
}
}

Floodfill algorithm Java, recursive

import java.util.Arrays;

public class Main
{
public static void main(String[] args)
{
int[][] image = {
{0,0,0},
{1,1,1},
{0,0,0}
};

printImage(image);
floodFill(image, 0, 2, 0, 0);
printImage(image);
}

public static void floodFill(int[][] image, int targetColor,
int newColor, int x, int y)
{
if (image.length < 1 || image[0].length < 1)
return;
if( !checkBoundaries(image, x, y))
return;

boolean visited[][] = new boolean[image.length][image[0].length];

floodFillInternal( image, visited, targetColor, newColor, x, y);

}

private static void floodFillInternal(int[][] image, boolean[][] visited,
  int targetColor, int newColor, int x, int y)
{
if (!checkBoundaries(image, x, y))
return;

if(image[x][y] != targetColor || visited[x][y])
return;

image[x][y] = newColor;
visited[x][y] = true;

floodFillInternal( image, visited, targetColor, newColor, x+1, y);
floodFillInternal( image, visited, targetColor, newColor, x-1, y);
floodFillInternal( image, visited, targetColor, newColor, x, y+1);
floodFillInternal( image, visited, targetColor, newColor, x, y-1);
}

private static boolean checkBoundaries(int[][] image, int x, int y)
{
if ( x >= image.length || x < 0 || y >= image[0].length || y < 0)
return false;
return true;
}

private static void printImage(int[][] image)
{
for(int[] col : image)
System.out.println(Arrays.toString(col));
}
}

Simplistic FloodFill algorithm in C++, recursive implementation

White morning in Switzerland

I woke up today to this lovely view from my living room:

uhh, it must be really cold outside!!!

Enjoy!

Quicksort in Python

import random

class QuickSort :
    def __init__(self):
        self.r = random.Random()
       
    def sort(self, input):
        if len(input) <= 1 :
            return input

        pivot = self.r.randint(0, len(input)-1)
        pivotValue = input[pivot]

        left = list()
        right = list()

        s = 0
        for elem in input:
            s = s + elem
            if elem < pivotValue :
                left.append(elem)
            else :
                right.append(elem)
       
        if (len(left)==0 or len(right)==0) \
                and s/float(len(input)) == pivotValue:
            return input


        return self.sort(left) + self.sort(right)


if __name__ == "__main__":
    sorter = QuickSort()
    print sorter.sort([1,3,2,4,2,5,3,4,3,3,2,32,235,23,523,5,235,23-253])

Not so simple QuickSort in Java

package com.julio.quicksort;

import java.math.*;
import java.util.*;
import java.lang.System;

public class QuickSort {

    public static void main(String args[]) {
        QuickSort sort = new QuickSort();
        int[] input = {1,2,5,4,3,2,6,7,8,34,22,-22,22,-22,22-123,1241,-12412,9,-1,-12,2,44};
        String s = Arrays.toString(sort.sort(input));
        System.out.println(s);
    }

    public int[] sort(int[] input) {
        if (input.length == 1) {
            return input;
        }

        return sortInternal(input, input.length);

    }

    private int[] sortInternal(int[] integers, int size) {
        System.out.println("Input" + Arrays.toString(integers));
        if (size <= 1) {
            return integers;
        }

        int pivot = (int) (Math.random() * size);
        System.out.println("Pivot " + pivot);
        int pivotValue = integers[pivot];

        int l[] = new int[size];
        int r[] = new int[size];

        int ll = 0;
        int rl = 0;
       
        int sum = 0;

        for (int i = 0; i < size ; ++i) {
            sum += integers[i];
            if (integers[i] < pivotValue) {
                l[ll++] = integers[i];
            } else {
                r[rl++] = integers[i];
            }
        }
       
        if (sum/(float)size == integers[0]) {
            return integers;
        }
       
        System.out.println("left " + Arrays.toString(l));
        System.out.println("right " + Arrays.toString(r));

        int[] finalArray = new int[size];

        System.arraycopy(sortInternal(l, ll), 0, finalArray, 0, ll);
        System.arraycopy(sortInternal(r, rl), 0, finalArray, ll, rl);

        return finalArray;
    }
}