My thoughts on Basecamp

For the last few months I have been using basecamp to coordinate and communicate with my group for a (rather large) piece of coursework. I've had a reasonable amount of time to get used to basecamp and how it works, so (upon request) I thought that I would share thoughts on it here.

To start with, the summary page gives a quick overview of what has been going on recently, without giving you that feeling of information overload. The discussions are good too - they are arranged in chronological order with the avatar of the most recent commenter next to each post. The files section is ok, but it feels rather cluttered and would be more helpful if you could upload a new version of someone else's file.

The problems start in the "To-do lists" section. You can create multiple lists of items, but you can't create subtasks or tasks that depend on other tasks. This makes basecamp rather unsuitable for software development as I often find that in order to fix one issue I have to fix another first. I also like to categorise my todos (which basecamp doesn't support either) - GitHub issues do this very well. The ability to assign multiple people to a task would also make working in a group much easier. I also found that once I'd created a few todo items, it quickly got to the point where I couldn't tell them apart - it just looked like a big wall of text, but that is probably just me.

The last thing I haven't mentioned yet is the events tab. Here you can create events and have basecamp automatically email (optionally selected) people, which is nice, but a special field to specify the location of the event would be welcomed as I found in my group that the venue of our meetings kept changing. A number of different views on the calendar would make it even better - the month view displays too much time, and I always get times mixed in the agenda view.

To conclude, Basecamp is a good project management tool that you can use when working in a group, but is still a bit rough around the edges. I wouldn't use it for software development, but I'm not ruling it out for other kinds of projects (although I think that trello would probably better float my boat, depending on the situation).

Learning Prolog: Lab #10

We are in double figures! Welcome to my solutions for the tenth and final lab session for this semester. This lab lets you in easy, and then hits you with a really nasty problem right at the end.

The first problem asked for a rule that returned the length of a list. I found this one easy:

listlength([], 0).
listlength([ _ | Tail ], Length) :-
    length(Tail, RecursiveLength),
    Length is RecursiveLength + 1.

?- listlength([ hurricane, typhoon, cyclone ], Length).
Length = 3.

I simply recurse over the list in question and add one to a counter variable on the way out. The next one is a bit harder, but still very easy - A rule that returns the nth element in a list.

nthelement(0, [ Head | _ ], Head).
nthelement(N, [ _ | Tail ], Result) :-
    N > 0,
    NRecurse is N - 1,
    nthelement(NRecurse, Tail, Result).

?- nthelement(2, [sequoia, baobab, redwood], Item).
Item = redwood .

My solution works very similary to my listlength/2 solution, but instead counts down from the number you give it until it reaches zero ,at which point it climbs back out of the recursion again and returns the item that it got up to.

The last problem was a really tough one. It demands flattened list containing all the elements in a given list of lists of arbitrary depth (exceptempty lists). It took me a while (and some help) in order to figure this one out:

squash([[]], []).
squash([], []).
squash([ [ HeadHead | HeadTail ] | Tail ], Result) :-
    squash([ HeadHead | HeadTail ], HeadResult),
    squash(Tail, TailResult),
    append(HeadResult, TailResult, Result).
squash([ Head | Tail ], Result) :-
    squash(Tail, TailResult),
    append([Head], TailResult, Result).

Cracking particular problem requires a new brain-breaking type of recursion, called Top-and-Tail recursion. It's specific to Prolog (as far as I know), and means that instead of just recursing over the tail of the list in order to iterate over it, you iterate over the head of the list as well.

Since Prolog lets us break arguments down to any depth we like, I break the incoming list down into its head and tail, and then I break the head down into its component head and tail in order to ensure that it is actually a list.

I then recurse over the head of the list ad the tail of the list separately, and concatenate the result of the two recursive calls at the end.

If the head isn't a list, then I only recurse over the tail, and append the head to the flattened tail on the way out.

I also declare that both an empty list and an empty lsit inside an empty list should return a single empty list. This allows us to avoid any rogue empty lists that might happen to be floating around from finding their way into the solution by mistake. Here's an example:

?- squash([[[a],b],[c],[d,[e],[]]], Result).
Result = [a, b, c, d, e] .

That concludes all the AI labs for semester 1, although I have another AI lab scheduled for the coming Monday. If it turns out that there's another lab, I'll post about it here. Otherwise, I'll resume this series in sesmeter 2.

Learning Prolog: Lab #9

Sorry this post is rather late! I had multiple ACW deadlies to deal with, and I now have a nasty cold as of the time of writing :(

I had a bit of trouble with this lab - I originally lost the code that I had written due to a bug in my chromebook where it doesn't resume properly when I lift the lid...! Anyway, the main point of this lab was to practice the Prolog that we have learnt already. A lot. There were 7 problems to solve, 6 of which I have a solution for. The first two aren't very interesting, so I'll just include the code and some examples below and move on.

sbrlmember(Item, [ Head | Tail ]) :-
        Item = Head ;
        sbrlmember(Item, Tail).

lastitem([ LastItem | [] ], LastItem).
lastitem([ _ | Tail ], LastItem) :-
        lastitem(Tail, LastItem).

?- sbrlmember(Item, [ apple, orange, grape ]).
Item = apple ;
Item = orange ;
Item = grape ;
false.
?- lastitem([ car, bus, truck, lorry, aeroplane ], Result).
Result = aeroplane .

The above contains definitions for two rules: sbrlmember and lastitem. sbrlmember works exactly like the member function that's built into Prolog, and lastitem, given a list, tells you what the last item in that list is.

The next one in the sequence is a rule that, given a list, returns the reverse of that list. Here's my solution, and an example:

listreverse([ Head | [] ], [Head]).
listreverse([ Head | Tail ], Result) :-
    listreverse(Tail, TailReversed),
    append(TailReversed, [Head], Result).

?- listreverse([windows, max, linux], Result).
Result = [linux, max, windows] .

Basically, it recurses over the tail of the list until there is just a single item left, at which point it returns the head on it's own in a list. When it comes back out of the recursion, it sticks everything back on the end of the list again in the reverse order.

The next problem we were given was to, given a pair of lists, return a third list containing all the items that appeared in both of the original lists. I decided to cheat a bit here and use an accumulator

intersection([], _, []).
intersection([ Head | Tail ], ListB, Result) :-
    member(Head, ListB),
    intersection(Tail, ListB, RecResult),
    append(RecResult, [Head], Result).
intersection([ _ | Tail ], ListB, Result) :-
    intersection(Tail, ListB, Result).

Complicated problems call for complicated solutions, so I decided to recurse over the first list and check to see if the current item is present in the second list. If so, then we add it to the result - if not, then we simply ignore it and carry on recursing. When it hits the end o fthe recursion, I start it off with an empty list, which it then adds to as it climbs its way back out of the recursion.

?- intersection([snow, rain, wind, flame], [snow, flame], Result).
Result = [flame, snow] .

The last problem I built a solution for asked for a rule that deleted the given atom (I think that's what you call them in Prolog?) from the given list.

deleteall(_, [], []).
deleteall(Item, [ Head | Tail ], [ Head | Result ]) :-
    not(Item = Head),
    deleteall(Item, Tail, Result).
deleteall(Item, [ _ | Tail ], Result) :-
    deleteall(Item, Tail, Result).

?- deleteall(snake, [ squirrel, bird, cat, snake ], Result).
Result = [squirrel, bird, cat] .

My solution copies everything in the list over to the result (rather like the intersection problem above actually), unless the next item along is equal to the item we are supposed to be ognoring, in which case we skip it. I do this by adding a condition on the rule that copies the item over to the result that it can't be the item that we were told to remove.

That's the last problem from this lab - I'll have the solutions for the 10th lab up soon.

Easy Bezier Curves on the HTML5 Canvas

This is a follow up post to the vector.js post that I made last week, and depends on the vector class I released then. Please take a look at that post first.

Last week, I released a simple Ecmascript 6 vector class that I wrote. It's mildly interesting on its own, but this post is the real reason I wrote that other one. Using that vector class, I then went ahead and wrote my own bezier curve class, that supports an arbitrary number of control points. Before I continue, here's the code:

(Gist, Raw)

I was surprised by how easy the bezier curve algorithm was to implement. Basically, you loop over all your control points, finding the point that lies in a specific percentage of the distance between the current point and the next one. You then repeat this process until you have just a single point remaining. This results in a smooth curve that is skewed towards all of the given control points.

In my implementation, I did it recursively, with all the magic happening in the interpolate() function. It performs the above algorithm given a time between 0 and 1, and spits out the interpolated value. I called it a time here because bezier curves are often used to smooth out animations, and I travel along the line in the curve() function when applying it to the given canvas rendering context.

To use it, you first create an instance like so:

var bz = new BezierCurve([
    new Vector(38, 41),
    new Vector(96, 302),
    new Vector(807, 12)
]);

Then, in your rendering function, you can ask your new bezier curve to add itself to any given canvas rendering context like this:

// ...

context.beginPath();
// ...
bz.curve(context, 32);
// ...
context.stroke();

// ...

The second argument in the curve() call above is the number of segments to use when rendering. This tells the bezier curve class how many different points along the line it should calculate. More segments make it smoother, but will consume more processing power when first calculated. Pick just enough that you can't tell that the bezier curve is made up of lines - this is different for every curve.

I added a caching function to it too, so if you call the curve() function with the same number of segments more than once, it uses the interpolated values it calculated previously instead of calculating them all over again. This isn't the case if you call it with a different number of segments each time, however. If you want to do this, I suggest that you create a new instance for each different segment number that you need.

That concludes this post on my own bezier curve class. It's a little bit buggy in places (see the gif above), but I haven't managed to track down the issue. It should work fine for most purposes, though. If you do manage to spot the mistake, please let me know!

Update 24th January 2016: I've replaced the original code with an embedded version of the gist in order to keep it up to date, since I've revised it slightly sinec writing this blog post.

Easy circles on the canvas with context.ellipse()

A while ago I was building a family tree viewer for an ACW (Assessed CourseWork) at University. Part of this ACW involved drawing faces inside ovals and using circles for various things. The suggested method here was using bezier curves (more on this on Wednesday), but I found another (much easier!) way of doing it that I thought others would find useful, so I am posting about it here.

Instead of using context.bezierCurveTo() and battling with control points, you can just use context.ellipse to add either a circle or an ellipse to the current path. Here's an extract fomr the wonderful MDN:

Syntax

void ctx.ellipse(x, y, radiusX, radiusY, rotation, startAngle, endAngle, anticlockwise);

Parameters

Parameter	Explanation
x	The x axis of the coordinate for the ellipse's center.
y	The y axis of the coordinate for the ellipse's center.
radiusX	The ellipse's major-axis radius.
radiusY	The ellipse's minor-axis radius.
rotation	The rotation for this ellipse, expressed in radians.
startAngle	The starting point, measured from the x axis, from which it will be drawn, expressed in radians.
endAngle	The end ellipse's angle to which it will be drawn, expressed in radians.
anticlockwise	Optional. An Boolean which, if true, draws the ellipse anticlockwise (counter-clockwise), otherwise in a clockwise direction.

For example, here's how you'd draw a 100x200 red ellipse at (0, 0):

function renderEllipse(context)
{
    context.fillStyle = "#ff3300";
    context.beginPath();
    context.ellipse(0, 0, 100, 200, 0, 0, Math.PI * 2, false);
    context.fill();
}

The startAngle and endAngle functions work the same as the context.arc() command - they let you draw just part of a circle or ellipse instead of a full one. In the example above, I'm drawing a full one by starting at 0 and finishing at 2π (360°).

I've built a simple 'ripples' demo that demonstrates context.ellipse() in action. Click anywhere on the screen to create a ripple. The background is made with a few quick radial gradiants that fade from a colour into transparency.

Bitwise Operators in C++

A while ago I was given some directed reading on bitwise operators in C++. I've been so busy with coursework, I haven't had time to take a look! Thankfully, I found some time and thought that it would make a good post here.

Bitwise operators in C++ appear to be very similar to those in Javascript. They operate on things at a binary level - i.e. operating on the individual bits that make up a number. Apparently there are 6 different operators:

• & - Bitwise AND
• | - Bitwise OR
• ^ - Bitwise XOR (eXclusive OR)
• ~ - Bit inversion (monadic)
• << - Shift bits to the left
• >> - Shift bits to the right

I'll explain each of these with examples below.

Bitwise AND

Bitwise AND takes a bit from each thing (usually a number), and outputs a 1 if they are both 1s, and a 0 otherwise. Here's an example:

87654321
--------
01011010 // 90
11010101 // 213
-- AND --
01010000 // 80

In the above example, the only 1s that actually make it through to the final result are positions 7 and 5, which are worth 64 and 16 respectively. This can be useful for extracting a specific bit from a number, like this:

#include <iostream>
using namespace std;
void main() {
    int c = 58, d = 15;

    cout << "c " << (c & 32) << endl;
    cout << "d " << (d & 32) << endl;
}

In the above, I create 2 variables to hold the 2 numbers that I want to test, and then I perform an AND on each one in turn, writing the result to the console. It should output something like this:

c 32
d 0

This is because 58 is 00111010, and 32 is 00100000, so only the 6th bit has a chance of making ti through to the final result.

Bitwise OR

Bitwise OR outputs a 1, so long as any of the inputs are true. Here's an example:

87654321
--------
10110101
00011101
-- OR --
10111101

Bitwise XOR

Bitwise XOR stands for exclusive OR, and outputs a 1 so long as either of the inputs are 1, but not both. For example, 1 ^ 0 = 1, but 1 ^ 1 = 0.

87654321
--------
10101101
11001110
-- XOR --
01100011

Bit inversion

Bitwise inversion is a monadic operator (i.e. it only takes one operand), and flips every bit of the input. For example 11011101 (221) would become 00100010 (34), although this greatly depends of the type and length of the number you are using.

Bit shifting

Bitshifting is the process of shifting a bit of bits to the left or right a given number of places. For example, if you shift 1010 (10) over to the left 1 place you get 10100 (20), and if you shift 0111 (7) over to the right by one place you get 0011 (3). If you play around with this, you notice that this has the effect of doubling and halving the number:

cout << "f ";
int f = 5;
for(int i = 0; i < 5; i++)
{
    f = f << 1;
    cout << f << " ";
}
cout << endl;
cout << "g ";
int g = 341;
for(int i = 0; i < 5; i++)
{
    g = g >> 1;
    cout << g << " ";
}
cout << g << endl;

It doesn't deal with the decimal place, though - for that you need something like a float or a double. Here's some example output from the above:

f 10 20 40 80 160
g 170 85 42 21 10 10

At first glance, the bit shifting operators in c++ look the same as the ones used to stream things to and from an input / output stream - I'll have to be careful when using these to make sure that I don't accidentally stream something when I meant to bitshift it.

Bitshifting can be useful when working with coloured pixels. You can set a colour like this:

unsigned int newCol = ((unsigned int) 248)<<16) +
    ((unsigned int) 0)<<8) +
    ((unsigned int) 78);

I think that just about covers bitwise operators in C++. If you're interested, you can find the source code that I've written whilst writing this post here (Raw).

Vector.js: A simple vector class in ES6

Recently I built a vector class in Ecmascript 6 for some coursework that I've been writing, and I thought that I'd share it here. I found out a little while ago that chrome does actually support classes, so long as you enable strict mode. After looking into them, they are actually really useful when writing a HTML5 canvas demo, or writing a reusable library. I'll make a post on how to use them sometime soon (as soon as I have time).

Anyway, the class that I wrote supports addition, subtraction, division, multiplication, length limitation (preserving direction), the dot product, angle from another vector, unit vector calculation, length calculation, and cloning. Here's the code:

(Gist, Raw)

You can create instances of this class as you would any other:

var v = new Vector(100, 100), // Create a new vector for the point (100, 100)
    v2 = new Vector(300, 400); // Vector for the point (300, 400)

// Clone v and subtracts v2 from it, putting the result into v3.
// Note that `add()`, `subtract()`, etc. are _mutators_.
v3 = v.clone().subtract(v2);

If I've missed any functionality, please feel free to leave a request in a comment below. Even better - fork the gist and implement it yourself! I'd love to pull in your changes. Feel free to use this class in your own projects. A link back isn't required, but very much appreciated!

That's about everything I have to say about this class, but I'll be posting a bezier curve class soon that depends on this one - probably sometime next week. Bye!

Update 24th January 2016: I've replaced the original code with an embedded version of the gist in order to keep it up to date, since I've revised it slightly sinec writing this blog post.

Easy Quadratic Ease In/Out Algorithm

Recently I wanted to add an ease in / out effect to an animation that I was writing. I searched the internet, but couldn't find anything particularly useful that actually explained how the algorithm worked, so I am writing this post.

The formula I ended up using works by taking an input between 0 and 1, and spitting out an adjusted output which is also between 0 and 1, but has the easing function applied. For easing both in and out, there are two formulae.

To ease in, for $y < 0.5$: $$ y = 2x^2 $$

To ease out, for $y >= 0.5$: $$ y = -1 + x(4 - 2x) $$

If you want to only ease in or ease out, go ahead and use just one of the above equations, and forget about the other one. Or, you can combine them to ease in and out at the same time.

Initially, I wrote my implementation in C♯ while I was testing the equations. Here's what I came up with:

using System;
using System.Threading;

namespace EasingTest
{
    class MainClass
    {
        static int width = 75;
        static int frameDelay;

        public static float QuadEaseInOut(float time)
        {
            return time < 0.5f ? 2.0f * time * time : -1.0f + (4.0f - 2.0f * time) * time;
            //return t<.5 ? 2*t*t : -1+(4-2*t)*t
        }

        public static void displayEase(float time)
        {
            float ease = QuadEaseInOut(time);

            int nextWidth = (int)(ease * width);
            Console.Write("{0}{2}{1}\r", new string(' ', nextWidth), new String(' ', width - nextWidth), 'o');
        }

        public static void Main(string[] args)
        {
            Console.Write("Enter the frame delay: ");
            frameDelay = int.Parse(Console.ReadLine());

            int count = 0;
            float step = 0.01f;
            bool dir = false; // false = right->left, true = left->right
            while(count < 10)
            {
                if(!dir)
                {
                    for(float t = step; t < 1; t += step)
                    {
                        displayEase(t);
                        Thread.Sleep(frameDelay);
                    }
                    dir = true;
                }
                else
                {
                    for(float t = 1; t > 0; t -= step)
                    {
                        displayEase(t);
                        Thread.Sleep(frameDelay);
                    }
                    dir = false;
                }

                count++;

            }
        }
    }
}

(Pastebin, Raw)

Here's an example run of the above code:

The important stuff happens in the QuadEaseInOut function on line #11. If you just want the easing function, here it is in multiple languages:

C Sharp

public static float QuadEaseInOut(float time)
{
    return time < 0.5f ? 2.0f * time * time : -1.0f + (4.0f - 2.0f * time) * time;
}

Javascript

function (t)
{
    return t<.5 ? 2*t*t : -1+(4-2*t)*t;
}

The above can easily be ported to other languages if you aren't using C♯ or Javascript.

Sources

I originally got this algorithm from gre's wonderful gist, which also contains a number of other easing functions that you might be interested in.

Drive Naming Schemes in Linux

If you've used linux before, you'll probably have seen your flash drive or hard drive appearing as /dev/sdc4 at one point or another. You may have a cd drive which appeared as /dev/sr2 or /dev/cdrom. If you're really lucky, you might even have a tape drive that appears as /dev/st0.

What do all of these letters mean? I was wondering the same thing, so I looked it up and am writing up what I found in this post.

It would appear that in linux devices have a prefix and then an identifier. Before I explain the identifiers, I should outline each of the prefixes that I've come across (or looked up) first. You can find them below.

sd*

By far the most common device name prefix that I have come across is sd. This apparently originally stood for SCSI (SATA?) Device, but today it represents any regular block device that can be used for storage. This includes hard drives and flash drives for example.

hd*

The hd prefix originally stood for Hard Disk and was used for IDE drives, but it was dropped as of Linux 2.6.19 and sd* is now used instead.

sr*

sr stands for SCSI ROM and is used for CD / DVD drives (It might be used for blu-rays too, but I don't have one to check. Please post in the comments if you do!). On my machine, I have a number of symbolic links leading back to this drive in my /dev called cdrom, cdrw, dvd, and dvdrw.

st*

I have not come across a device with this prefix yet. If you have one, please post in the comments below! It stands for SCSI Tape drive.

Identifiers

The numbers and / or letters after the prefix refer to the device number, and, if appropriate, partition on the device. For example, /dev/sdb4 refers to the 4th partition on the 2nd disk, /dev/sr2 refers to the 3rd CD / DVD drive, and /dev/hdc3 refers to the 3rd partition on the 3rd IDE hard drive.

Sources

• Super User - What does /dev/sda for linux mean?
• Ask Ubuntu - What is the Linux drive naming scheme?
• The Linux Documentation Project - Drive Naming in Linux

Learning Prolog: Lab #8 - findall/3

This week's lab was all about findall/3, and a little bit more about lists. To summarise, findall lets you, well, um, find everything that matches a given rule or set of rules. For example, if we have the following dataset:

mountain(everest).
mountain(k2).
mountain(matterhorn).
mountain(kangchenjunga).
desert(sahara).
desert(gobi).
desert(atacama).

tall(everest).
tall(k2).
tall(kangchenjunga).

We could ask Prolog to give us a list of all the mountains in it's world. It's rather like issuing a database with an SQL query, asking it to find all the records that match a set of criteria and return them.

?- findall(Mountain, mountain(Mountain), MountainList).
MountainList = [everest, k2, matterhorn, kangchenjunga] .

?- findall(Mountain, (mountain(Mountain), tall(Mountain)), List).
MountainList = [everest, k2, kangchenjunga] .

?- findall(Desert, desert(Desert), DesertList).
DesertList = [sahara, gobi, atacama].

?- findall(Place, (desert(Place); mountain(Place)), Places).

Places = [sahara, gobi, atacama, everest, k2, matterhorn, kangchenjunga] .

As I demonstrated above, you can combine multiple criteria with a set of brackets and a few commas or semi-colons.

The other thing that we looked at was a rule that would return the last item in a list. Here's what I came up with:

% Stopping condition - stop when we reach the last item
lastitem([ LastItem | [] ], LastItem).
% If we haven't reached the end of the list, recurse on the rest of the list.
lastitem([ _ | Rest ], LastItem) :-
    lastitem(Rest, LastItem).

The above keeps throwing away the first item in the given list until it finds the last item, which it then stores in the variable LastItem. It knows which the last item is because lists in Prolog are always terminated with an empty list ([]). Here's an example of the above in action:

?- findall(Place, (desert(Place); mountain(Place)), Places), lastitem(Places, LastPlace), write('The last place is '), write(LastPlace), write('.'), nl.
The last place is kangchenjunga.
Places = [sahara, gobi, atacama, everest, k2, matterhorn, kangchenjunga],
LastPlace = kangchenjunga .

That brings us to the end of the 8th Prolog lab session. This post feels a bit short, but I'm sure that there will be more to post about next time. If you're interested, here is a link to the Prolog file that I have written whilst writing this post.