Posts Tagged ‘source code’

Select 100 random values from a stream / linked list

Friday, July 11th, 2008

Here’s an interesting puzzle / interview question that I heard recently.

Problem

You have a either a linked list or a stream containing int values. You don’t know how large the stream / linked list except that it contains 100 or more values. You need to write a method that selects 100 random values from the stream. You have to write the method so that there isn’t a bias towards values at the start, middle or end of the stream / list. In other words the chances of picking a value from anywhere in the stream / list should be roughly the same.

There are some restrictions.
You can’t cache the whole stream (if it is a stream).
Or if it is a linked list – you are only allowed a single pass of the list. You can’t iterate through it once to determine its length.

Solution

The solution is:

  1. Select the first 100 values and store them in an array.
  2. For each value after the first 100 we select them according to a decreasing probability. If we select a value then we replace a randomly selected value from our existing list.

So values 1-100 have a probability of 1 of being initially selected.
Value 101 has a 100/101 chance of being selected.
Value 102 has a 100/102 chance of being selected.
Value 1050 has a 100/1050 chance… etc.

100 is at the top of the division as this is our value for x – the number of values we are selecting.

You can see that value 101 has a very high chance of being selected. 100/101 in fact. As we are replacing one of our existing values, each of the existing values has a 100/101 chance of remaining after the replacement.

Using this simple logic we can get a random sample of the values even though we don’t know the length of the stream / list.

Code

Here is the C++ code showing how to do this. Also included is a simple test which sends the values 1-1 million to the function. 100 are randomly selected.

After the code is a graph which shows the distribution of the selected values. You can see that the distribution is fairly even showing that the code works. For random number selection code such as this, the easiest way to verify that the code works is to manually view the results in a graph and see if the output looks sensible.

const int size = 100;
int selected[size];
int count = 0;
void SelectRandomNumbers(int nextNum)
{
	if (count < size)
	{
		selected[count++] = nextNum;
		return;
	}
	double probability = (double)size / (double)(count+1);
	double select = (double)rand() / RAND_MAX;
	if (select < probability)
	{
		int randomIndex = RandomNumber(0, size);
		selected[randomIndex] = nextNum;
	}
	++count;
}
// min is inclusive
// max is non-inclusive
int RandomNumber(int min, int max)
{
	return (int)((double)rand()	/
		(RAND_MAX + 1) * (max - min) + min);
}
///////////////

const int iterations = 1000000;
void RandomSelectionTest()
{
	srand((unsigned)time(0));
	for (int i=0; i<iterations; ++i)
	{
		SelectRandomNumbers(i);
	}
	cout << size <<	" randomly selected ints:" << endl;
	PrintIntArray(selected, size);
}
void PrintIntArray(int thearray[], int size)
{
	for (int i=0; i<size; ++i)
	{
		cout << thearray[i] << endl;
	}
}

Graph

Here are the results. 1 million numbers were passed in. 100 were selected. You can see that the distribution is fairly even which means that the code is doing the correct thing.

Graph of randomly selected numbers

PhotoStamper utility with Java source

Thursday, July 3rd, 2008

PhotoStamper is a simple application which will add a date/time stamp to your jpeg photos. You can decide which corner of the photo to put the stamp in, as well as configuring the font size. It currently uses the last modified date of the file as the timestamp.

I wrote this after finding that most of the other tools to add date/time stamps were not free. It is written using Java 1.5 (Java 5.0) so you'll need a Java runtime 1.5+ on your computer to use it.

The tool won't overwrite the original file - it wil save the stamped file to <originalfile>_stamped.jpg.

Usage

java -jar PhotoStamper.jar [options]

Stamps the last modified date onto the image file.
PhotoStamper file [-s size] [-x xoffset] [-y yoffset] [-a anchor] [-c color]
        file    File or directory to be stampped.
        -s      Font size in pixels.
        -a      Anchor for text. One of tl, bl, tr, br. (top left, bottom left, etc).
        -x      x offset from the anchor.
        -y      y offset from the anchor.
        -c      color consisting of r:g:b values. 0-255.
e.g.
        PhotoStamper photo.jpg -s 50 -x 25 -y 25 -a tl -c 255:0:0

Download

PhotoStamper.jar
PhotoStamper source and Eclipse build files

Limitiations

Unlike some of the commercial tools this photo stamer will result in a small reduction in image quality as the whole jpeg will be recompressed after the date/time stamp is applied. The difference with the original is very small so you probably won't even notice.


QuickSort Implementation Code in C++

Wednesday, June 25th, 2008

I was having a look at the QuickSort algorithm (as you do for fun) and was trying to find a tidy looking implementation in C++. I found a lot of implementations out there but most of them looked far more complicated than I thought they should have been.

The QuickSort algorithm as printed in the Introduction to Algorithms book looks relatively simple. I wanted a C++ version that has a QuickSort function and a partition function. Many of the implementations that I’ve seen on the internet have both functions merged into one.

The neatest looking QuickSort code that I found was one this Java version written by a Prof. Dr. H. W. Lang. Compare how short and easy to read this piece of code is to other QuickSort implementations. This is close to what I want but the partition part is rolled into the main QuickSort code.

It also had quite a few differences to the Introduction to Algorithms QuickSort. I used the Prof. Dr. H. W. Lang code as a base, split the partition part out, and then made a few other changes to make the implementation closer to the Introduction to Algorithms version. This is what I ended up with.

int partition(int a[], int left, int right, int pivotIndex)
{
    int pivot = a[pivotIndex];
    do
    {
        while (a[left] < pivot) left++;
        while (a[right] > pivot) right--;
        if (left < right && a[left] != a[right])
        {
            swap(a[left], a[right]);
        }
        else
        {
            return right;
        }
    }
    while (left < right);
    return right;
}
void quicksort(int a[], int left, int right)
{
    if (left < right)
    {
        int pivot = (left + right) / 2; // middle
        int pivotNew = partition(a, left, right, pivot);
        quicksort(a, left, pivotNew - 1);
        quicksort(a, pivotNew + 1, right);
    }
}

I tested this in the free Microsoft Visual C++ Express Edition. Here is what I used to test the QuickSort code.

#include "stdafx.h"
#include <iostream>
using namespace std;
void printArray(int thearray[], int count)
{
    for (int i=0; i<count; ++i)
    {
        cout << thearray[i] << " ";
    }
    cout << endl;
}
void arraySortingTests()
{
// unique unsorted
int numbers1[] = {14, 17, 11, 13, 19, 16, 12, 15, 18, 10};
int numbers2[] = {19, 16, 10, 12, 14, 17, 13, 18, 15, 11};
// already sorted
int numbers3[] = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
// reverse sorted
int numbers4[] = {19, 18, 17, 16, 15, 14, 13, 12, 11, 10};
// all duplicates
int numbers5[] = {7, 7, 7, 7, 7};
// 1 pair
int numbers6[] = {14, 17, 11, 13, 19, 16, 12, 15, 18, 14};
// 1 pair at start
int numbers7[] = {14, 14, 17, 11, 13, 19, 16, 12, 15, 18};
// multiple duplicates
int numbers8[] = {14, 14, 14, 13, 13, 13, 13, 12, 12, 12};
int numbers9[] = {12};
int numbers10[] = {12,10};
quicksort(numbers1, 0, 9);
printArray(numbers1, 10);
quicksort(numbers2, 0, 9);
printArray(numbers2, 10);
quicksort(numbers3, 0, 9);
printArray(numbers3, 10);
quicksort(numbers4, 0, 9);
printArray(numbers4, 10);
quicksort(numbers5, 0, 4);
printArray(numbers5, 5);
quicksort(numbers6, 0, 9);
printArray(numbers6, 10);
quicksort(numbers7, 0, 9);
printArray(numbers7, 10);
quicksort(numbers8, 0, 9);
printArray(numbers8, 10);
quicksort(numbers9, 0, 0);
printArray(numbers9, 1);
quicksort(numbers10, 0, 1);
printArray(numbers10, 2);
}
int _tmain(int argc, _TCHAR* argv[])
{
    arraySortingTests();
    return 0;
}

Update: 25/09/2011 as people noticed my original version of the Quick Sort algorithm didn’t work with duplicates. This new version does, and has extra tests cases to verify this. I’ve had to delete the comments which refer to the old version of the code, as they don’t make sense any more! If you spot any problems with this new version of the code, please let me know.
Update: 30/09/2011 Sergiy in the comments below has found a test case that this doesn’t work with :( If anyone can spot the fix please leave a comment.


C# – How to make a window stay on top and become transparent

Sunday, May 18th, 2008

Whilst looking for information on how to make a window stay on top using C#, I spotted some odd solutions on a number of other web sites. After looking through the Form properties in Visual Studio C# 2008 myself it turns out that it is really easy to make a window stay on top. I added a check box to by application and when it is ticked the window stays on top.

Visual C# buttons

private void stayOnTopCheckBox_CheckedChanged(object sender,
                                              EventArgs e)
{
    if (stayOnTopCheckBox.Checked)
    {
         this.TopMost = true;
    }
    else
    {
        this.TopMost = false;
    }
}

Along the same theme of ‘very cheap and quick tricks that you add to your C# program’ I added another box to make the window transparent. Below is the code and the result of ticking this box.

private void transparentCheckBox_CheckedChanged(object sender,
                                                EventArgs e)
{
    if (this.transparentCheckBox.Checked)
    {
        this.Opacity = 0.5;
    }
    else
    {
        this.Opacity = 1;
    }
}

Visual C# transparent buttons

FTP uploading a directory of files using perl

Monday, February 18th, 2008

Here is a simple script to upload the files which are in a particular directory. I use something similar to automate the file uploading for my tube walking blog.

Whenever I take photos for the blog I put them into a directory with the current date as the directory name. So I have a structure like this:

c:\website\080115\
c:\website\080203\
c:\website\080205\
c:\website\080218\

I want the images in these directories to be uploaded to a new directory on the FTP server where the FTP server directory is named with the date e.g. ‘080218’.

The script is run with a command such as:

perl imageupload.pl c:\website\080218\

The script will then:

  1. Extract the date part of the directory – ‘080218’.
  2. Connect to the FTP server.
  3. Create a directory called ‘080218’ on the FTP server.
  4. Get a list of all the local files in the directory that you passed in as the argument.
  5. Upload each of these files to the FTP server.

Here’s the script. You’ll need to modify the FTP server address, username and password if you want to use it.

use File::Basename;
use Net::FTP;
my $directory = $ARGV[0];
my @parts = split(/\\/, $directory);
# get leaf directory name from whole path
my $length = $parts;
my $dateDir = $parts[$length-1];
$ftp = Net::FTP->new("ftp.yourwebsite.com", Debug => 1)
    or die "Cannot connect to hostname: $@";
$ftp->login("username", "password")
    or die "Cannot login ", $ftp->message;
$ftp->cwd("/website/data")
    or die "Cannot change working directory ", $ftp->message;
# create 'date named' directory on FTP server
$ftp->mkdir($dateDir);
$ftp->cwd($dateDir);
# set binary mode which is needed for image upload
$ftp->binary();
opendir(DIR, "$directory");
my @files = readdir(DIR);
foreach my $file (@files)
    {
    if (not -d $file)
        {
        # make sure the names are lower case on the server
        $file = lc($file);
        # upload the file
        $ftp->put("$directory\\$file");
        }
    }
$ftp->quit();

The script is simple, but it can easily be integrated into a more complex set of scripts to help you manage your web site.

Backup / restore of last modified and created file time attributes on Windows

Saturday, January 12th, 2008

Last month I found that I needed to be able to backup and restore the last modified and created file times of a load of files in Windows XP. This is probably a bit of an obscure thing to need to do so naturally I couldn’t find any existing tools to do it.

I’ve therefore made a Perl script to allow this to be done. Just so you are clear, this isn’t backing up the files, it is backing up the last modified and created file time attributes.

This allows changes to be made to the files whilst keeping these attributes intact. In theory Perl’s utime function should allow me to change these attributes. However on my Windows XP machine it just didn’t work. I’ve therefore used the rather excellent nircmd tool to handle the file attribute modifications. You’ll need to download it and modify backupLastModified.pl to point to it.

Usage is simple:

perl backupLastModified.pl c:\yourdir -backup
perl backupLastModified.pl c:\yourdir -restore

Make sure you do a test of this script before you use it for real. It has only ever been tested on one machine.

  1. Download backupLastModified.zip
  2. View backupLastModified.pl

This script will create a file ‘backuplist.txt’ in the directory that you pass in as the first argument. If you run -backup multiple times then any new files will be appended to the backuplist.txt. The stored last modified / created times of any existing files will be preserved.

Adding a date/time stamp to a jpeg image in Java

Monday, October 22nd, 2007

I’ve been looking for a simple tool to add a date/time stamp to some jpeg images. There are quite a lot of tools to do this but they all tend to cost money. I decided to make my own in Java. The actual process of loading a jpeg, adding a stamp and then saving it again is very simple. The below snippet will do the job.

BufferedImage bi = ImageIO.read(sourceFile);
Graphics2D graphics = bi.createGraphics();
Font font = new Font("ARIAL", Font.PLAIN, 20);
graphics.setFont(font);
graphics.drawString(stamp, 50, 50);
bi.flush();
ImageIO.write(bi, "jpg", targetFile);

I added some options (you can change font size, position, colour) to meet my needs. You can download it for free from https://www.reviewmylife.co.uk/blog/2008/07/03/photostamper-utility-with-java-source/. It is very basic – command line only – but does the job well enough. The Java source code and Eclipse project files are also available for download.

Adding source code into WordPress blog posting

Sunday, October 21st, 2007

As demonstrated by another post of mine I finally figured out how to easily add source code into a WordPress blog posting. Searching on Google for this issue reveals large numbers of people facing the same problem. It makes you think that including source code in a WordPress 2.2.1 blog posting is the most difficult problem known to man.

Many of the problems seem to be caused by the visual editor in WordPress. It reformats code in ways that you are unlikely to want (such as trimming any whitespace), leaving your carefully constructed source code looking like a real mess.

The way to turn it off is to go to ‘Login -> Users -> Edit’ and then untick the ‘Use the visual editor when writing’. There seems to be no way to edit and then re-edit in-line source code when the visual editor is turned on, because when you re-edit your posting the visual editor reformats your code automatically – even if you don’t make any changes and switch straight to the code editor.

This problem is in part because if you have the visual editor enabled it becomes the default editor and re-formats any code that it loads. WordPress could easily fix this be allowing you to make the code editor the default editor so the visual editor only gets its hands on your posting if you give it permission. There is a discussion on the worpress.org site about this here.

If you still want to use the visual editor then the workaround that I’ve seen mentioned is to create a second user account with the visual editor turned on. You then need to use the correct account depending on whether you will post source code or not and remember never to load your source code posts with the visual editor.

The next problem that I came across was that adding code within <pre></pre> tags causes the lines to be double spaced when using the default WordPress theme. I solved this by installing the CodeMarkup plugin which allows code samples to be displayed in a way which looks sensible to me. It automatically escapes all your code so that you can paste it directly in between <pre><code></code></pre> tags without having to use a tool tool to escape the special characters.

ProGuard Eclipse Ant build.xml

Saturday, October 20th, 2007

If you are building J2SE apps with Eclipse and want to use ProGuard to compress, optimise or obfuscate your code you’ll need to create an Ant build.xml file to do this. I found various bits of help on the internet explaining parts of the build.xml file, but couldn’t find anywhere that gave the complete build.xml to do the full compile, jar and proguard steps.

Here is the full build.xml I cobbled together to do all three:

<?xml version="1.0" ?>
<project default="main">
<taskdef resource="proguard/ant/task.properties"
	classpath="D:\apps\proguard4.0.1\lib\proguard.jar" />
<target name="main" depends="compile, jar, obfuscate"
	description="Create project">
	<echo>Creating project.</echo>
</target>
<target name="compile" description="Compile target">
	<javac srcdir="src" destdir="bin"/>
</target>
<target name="jar" description="Jar target">
	<jar jarfile="PhotoStamper_debug.jar"
		basedir="bin" includes="*.class">
		<manifest>
		<attribute name="Main-Class" value="PhotoStamper" />
		</manifest>
	</jar>
</target>
<target name="obfuscate" depends="jar"
	description="Obfuscate compiled classes">
	<proguard>
		  -libraryjars "${java.home}\lib\rt.jar"
		  -injars      PhotoStamper_debug.jar
		  -outjars     PhotoStamper.jar
		  -keep public class PhotoStamper {
			public static void main(java.lang.String[]);
			  }
	</proguard>
</target>
</project>