Make Turning Windows Off and On Again Great Again

There’s a joke about all Windows related problems being solvable by turning the computer off and on again. It’s one of the things that works most reliably about the OS. Well, even this has been broken by Microsoft in the Windows 10 Fall Creators Update.

When you get to the point where you have more than a dozen virtual desktops running with many different programs, your computer (not to mention your brain) will start to get overloaded. At times like these, I just want to hit refresh (to coin a phrase…) and get back to an unmussed system. However, a new “feature” in the Fall Creators Update of Windows 10 will try to reopen as many of the programs that you had running beforehand as possible. Not all programs will get restarted. Tiny programs like Notepad++ stay unloaded, but bloated behemoths that hang for 30 seconds to a minute to load (like Excel and Visual Studio) get restarted, maybe with the files that you had opened, maybe not. If you were using virtual desktops beforehand and had carefully separated your programs by task, all the programs will be in the first one but you will still have several empty and useless virtual desktops open. Instead of getting a fresh start on a clear desktop, you are left waiting for programs to load and needed to close all the virtual desktops. Unfortunately, there’s no setting to just turn off this rather half-baked behaviour.

However, a little PowerShell can reduce the pain and shutdown the computer more thoroughly.

I don’t want to accidentally trigger this, so my script starts with a confirmation:

Write-Output "This will close all your virtual desktops and shutdown the computer."
$Confirm = Read-Host "Hit Y to confirm."
if ($Confirm.ToLower() -ne 'y')
{
    Write-Output "Doing nothing"
    exit
}

Write-Output "Shutting down..."

Closing all the other virtual desktops can be achieved with by wrapping around MScholtes’ VirtualDesktop:

while ($true)
{
    $CountCommand = "$($VirtualDesktopExe) /C"
    $CountOutput = iex $CountCommand
    if ($CountOutput -match 'Count of desktops: (\d+)')
    {
        $Count = $Matches[1]

        if ($Count -gt 1)
        {
            Write-Output "You still have $($Count) virtual desktops."
            iex "$($VirtualDesktopExe) /R"
        }
        else
        {
            Write-Output "Only one virtual desktop at this point"
            break
        }
    }
    else
    {
        Write-Error "Unable to parse result of command '$($CountCommand)': '$($CountOutput)'"
        exit
    }
}

This simply invokes the program with the “/C” flag (count) then calls the program with “/R” (remove) until only one virtual desktop remains.

After that, the script just invokes the old fashioned shutdown command from Ramesh Srinivasan’s article above about this new feature.

shutdown.exe /s /t 0

On my desktop, I have a link to a script that invokes the PowerShell script with the location of the VirtualDesktop.exe file on my machine:

PowerShell -command "F:\Robert\Dropbox\local-scripts\_Common\CloseVirtualDesktopsAndShutdown.ps1 -VirtualDesktopExe F:\Robert\Dropbox\executables\Windows\x64\VirtualDesktop.exe"

Now I know that I will get a fresh start when I turn on my computer again. I’m not really sure why this isn’t the default behaviour.

Duplicated Line Finding in Go

I’m learning to read, write and understand Go at the moment:

https://golang.org/

As part of this, I am reading “The Go Programming Language” by Donovan and Kernighan and completing the exercises in it.

In the first tutorial chapter, there are samples of code for detecting duplicated lines in text files. The technique put forward by book is to use a map of strings to integers, where the key is the line and the value is the count. The programs simply loop over the lines and increment the value for the current line in the map.

An exercise that is left for the reader is adapt one of the existing sample programs to read several files and print the names of the files that contain each duplicated line.

The first problem to overcome is that the names of the files have not be recorded as the input files are being processed. This means that when we come to print the data that we have collected, we have lost that information.

My first approach was to add a map of strings to string slices. The idea was to add the file name to the string slice for that line as each line is read. This works in the sense that we have the list of file names for each line that is duplicated. However, the list of file names will contain duplicates itself if a line is duplicated in a file. I could wrap the code to append the new file name in an “if” statement and check whether that item is already there. However, checking whether a slice contains an item is O(n), which sounds like too much unnecessary work. I needed data structure that discards duplicates so that each item is unique. One way to do this is to use the keys of a map of strings to integers as the values that you wish to keep unique and increment the values of the map.

I created the following map of strings to maps of strings to ints:

lineCountsInFiles := make(map[string]map[string]int)

and incremented the values as simply as:

lineCountsInFiles[line][filename]++

One gotcha that I ran into during execution was that the nested map also needs to be initialized before we can increment the value:

if lineCountsInFiles[line] == nil {
    lineCountsInFiles[line] = make(map[string]int)
}

This caught me because we can increment a value in a map of strings to ints without any initialization as the int has default value that be incremented:

counts[line]++

Once the files have been processed, we have a map from the lines in all the files to a map from the names of the files in which they appear to the counts of each line in that file.

Putting everything together looks like this:

// Prints the counts, lines and names of files where
// a line is duplicated
package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    counts := make(map[string]int)
    lineCountsInFiles := make(map[string]map[string]int)

    for _, filename := range os.Args[1:] {
        f, err := os.Open(filename)
        if err != nil {
            fmt.Fprintf(os.Stderr, "Problem reading %v: %v\n", filename, err)
            continue
        }
        input := bufio.NewScanner(f)
        for input.Scan() {
            line := input.Text()
            counts[line]++
            if lineCountsInFiles[line] == nil {
                lineCountsInFiles[line] = make(map[string]int)
            }
            lineCountsInFiles[line][filename]++
        }
        f.Close()
    }

    for line, n := range counts {
        if n > 1 {
            fmt.Printf("%d, %v\n", n, line)
            for filename, count := range lineCountsInFiles[line] {
                fmt.Printf("\t%d,%v\n", count, filename)
            }
        }
    }
}

Which is saved here:

https://github.com/robert-impey/CodingExperiments/blob/master/Go/dup-with-names.go

For files like:

apples
coconuts
apples
bananas
apples
bananas

https://raw.githubusercontent.com/robert-impey/CodingExperiments/master/Go/duplicated-fruit.txt

and

apples

https://raw.githubusercontent.com/robert-impey/CodingExperiments/master/Go/more-duplicated-fruit.txt

The output might be something like:

C:\Users\Robert\code\CodingExperiments\Go>dup-with-names.exe duplicated-fruit.txt more-duplicated-fruit.txt
4, apples
        3,duplicated-fruit.txt
        1,more-duplicated-fruit.txt
2, bananas
        2,duplicated-fruit.txt

I write “might be” as the order that keys are retrieved from maps is deliberately undefined.

There are probably lots of ways to solve this problem. If you have any suggestions, please let me know.

Have you celebrated Baegil yet?

A Korean friend asked my wife if our son had celebrated Baegil or 100 days yet. Not being familiar with the celebration, we said that we hadn’t kept track of the days since his birth. I decided to write a little program in Go in order to check what day of one’s life one is currently on.

The program should take the subject’s date of birth as a string from the first command argument. This was simple enough for me to decide against using the flags package and check the command line arguments directly:

if len(os.Args) == 1 {
    os.Stderr.WriteString("Please tell me your date of birth!\n")
} else {
...
}

I wanted to save programming effort and avoid reinventing the square wheel by using a library for handling the dates. The time package from the standard library can represent times and parse strings to time structs.

The time package has a peculiar (but easy to grok) way of specifying date layouts for formatting. Rather than %Y, %h, %s and so on from the standard C library and its descendants, in Go a fixed date where days are 1 and months are 2 and so on is used. So, to parse dates such as “2016-06-20” or “1980-10-28”, we need:

var layout = "2006-01-02"
var dateOfBirth, dOBParseError = time.Parse(layout, os.Args[1])

Full details can be found on this blog post:

https://pauladamsmith.com/blog/2011/05/go_time.html

Of course, a user of the program might not enter a parseable date string, so we need a little bit more error handling:

if dOBParseError != nil {
    fmt.Fprintf(os.Stderr, "Unable to parse your date of birth: %s\n", dOBParseError)
} else {
...
}

Once we have a date of birth, we can perform our arithmetic. The time package has a Since(...) method that can give you the duration of time since a given time struct:

var age = time.Since(dateOfBirth)

For a simple program like this, methods like Since are more convenient than creating a date object of the current time and comparing the given time to it. However, this does create an issue when testing code that does anything to do with time. If your code makes direct use of the system’s clock, your functions are impure as the same input won’t always return the same output. How do you test that a given input produces the correct output? Such tests would only pass at specific times on a given date. The purely functional way to do this is to write your business logic handling functions to accept all the used time objects already created, so that appropriate mocks can be passed in during tests without calling any methods that get data from the system’s clock. Another approach is the override the methods that call the system’s clock so that they return a set time in the test. This is called monkey patching. I’ve heard of people even setting the system clock during the test, but this is likely to have unforeseen consequences, especially on a shared build server.

The time package defines an Hours function for Duration structs but not one for days. A quick and dirty solution to this is the divide the number of hours by 24 and floor the result:

var ageInDays = math.Floor(age.Hours() / 24)

This makes the assumption that every day has exactly 24 hours. What about leap seconds? A person might have a few leap seconds during a lifetime. What if this program is run within a few seconds of midnight? The result might be different from the true result. As we are not using the precise time of birth and are flooring the number of days anyway, this is not too much of a concern. However, if really precise maths is needed or you using the components of one time struct to create a new time struct, inaccuracies can creep into your code. The fun really begins when you need to handle issues like leap years, time zones and seasonal time adjustments. If I ran this code in San Francisco in Winter for someone who was born in Sydney during Daylight Saving Time, would the result be accurate? A more fully developed version of this program would probably use a library to handle the mind boggling complexity of time tracking in the real world.

Another issue to consider is off by one errors. I’m flooring the number of days in order to say, “days since”. If I enter today’s date, I will get 0 as the subject’s age has not reached one day yet. This might be confusing to someone expecting 1 on the first day and so on. How ages are reckoned changes among different cultures. How Koreans consider their ages is surprising to many foreigners.

https://en.wikipedia.org/wiki/East_Asian_age_reckoning#Korean

Koreans celebrate Baegil on the 100th day, so we would expect the program to return 99 on the appropriate day. A programmatic solution to this might be add 1 to the result and change the wording. Programmers need to consider the audience of their programs carefully and gather requirements fully.

Obviously, you can’t be born in the future and still use the program, so we need a bit more user input checking:

if ageInDays < 0 {
    os.Stderr.WriteString("Wow! I must be talking to a foetus!\n")
} else {
    ...
}

If we’ve made it this far, we can now print the age in days:

fmt.Printf("Days old: %.0f\n", ageInDays)

Putting it all together, this is my program:

package main

import (
    "fmt"
    "math"
    "os"
    "time"
)

func main() {
    if len(os.Args) == 1 {
        os.Stderr.WriteString("Please tell me your date of birth!\n")
    } else {
        var layout = "2006-01-02"
        var dateOfBirth, dOBParseError = time.Parse(layout, os.Args[1])

        if dOBParseError != nil {
            fmt.Fprintf(os.Stderr, "Unable to parse your date of birth: %s\n", dOBParseError)
        } else {
            var age = time.Since(dateOfBirth)
            var ageInDays = math.Floor(age.Hours() / 24)

            if ageInDays < 0 {
                os.Stderr.WriteString("Wow! I must be talking to a foetus!\n")
            } else {
                fmt.Printf("Days old: %.0f\n", ageInDays)
            }
        }
    }
}

Entering my son’s date of birth, I see that we still have a couple of days to go:

$ ./daysOld 2016-06-20
Days old: 97

The source code can be found at:

https://github.com/robert-impey/CodingExperiments/blob/master/Go/daysOld.go

Using F# to minimise a function

Finding the minimum of functions is at the heart of optimisation. Mathematicians, engineers and programmers have come up with a large number of approaches to solving this problem, including differentiation, genetic algorithms and even exhaustive search.

Consider a quadratic function such that could be written in F# as

let f x = (x ** 2.0) - (2.0 * x) + 1.0

Finding the minimum means finding the input value for the function that returns to lowest value. If we plot the curve, then the minimum is the lowest point of the curve.

One way to find this is find the derivative of the function:

(2.0 * x) - 2.0

and solve the equation where the derivative is equal to 0, which is when x is 1. This probably the best way to solve this problem in practice.

However, not all functions have derivatives that are easy to find. Therefore, an alternative way to minimise a function is an exhaustive search of the inputs in some range. This is not an elegant or generally efficient solution, but it works.

In F#, we might proceed as follows.

We define the range that we want to search and the step between candidate inputs:

let min = 0.0
let max = 10.0
let step = 0.01

We know where to start searching- with the lowest candidate input:

let firstCandidate = f min, min

This creates a tuple of two floats, the first being the output and the second being the lowest candidate input.

We also want a sequence of tuples of two floats that are the remaining candidate solutions:

let remainingCandidates = seq { for c in min + step .. step .. max do yield f c, c }

Note that at this point the sequence has not been enumerated and the function has not been run with each of the candidate inputs. Because sequences are evaluated lazily, the function will not be run for each of the candidate inputs until it is asked for.

We are trying to minimise the function, therefore we need a function that can compare the first elements of two candidate solutions:

let findMin currentMinSln candidateSln =
    match fst currentMinSln  currentMinSln
    | false -> candidateSln

Running this code in fsi shows its type to be:

val findMin : 'a * 'b -> 'a * 'b -> 'a * 'b when 'a : comparison

The F# compiler can infer that the function takes in two tuples, each with two elements. The tuples must be of the same type and the first element of each tuple must be comparable. Way to go, type inference!

Everything has been set up at this point. We just need to run the code:

let minSln = Seq.fold findMin firstCandidate remainingCandidates

The fold function is to reduce a sequence to a single value, starting with a given accumulator. In this case, the first candidate solution that we created earlier is our starting point. The output of the function for each candidate input is compared to that accumulator.

Running the code finds the same answer (1) that we found with calculus.

This code runs pretty quickly, but this approach is generally slow. Our range is only 10 wide and the step is 0.01, so there are only 1000 candidate inputs. Increasing the size of the range or decreasing the step would increase the number of inputs. More worryingly, the size of the search space increases exponentially as the number of inputs to the function increases. So a function that took two inputs for the same range for each input would have a million candidate inputs, three inputs would take a billion and so on.

However, it is also quite straightforward to parallelise this approach. The sequence of candidate solutions could be split up into partitions and each partition could be sent off to a different computer. Each batch would find a local minimum for the range it was given. Finding the minimum for the whole of our range of inputs is simply a matter of find the minimum in the returned list.

The complete code for this can be found here:

https://github.com/robert-impey/CodingExperiments/blob/master/F%23/Loose/MinimiseQuadratic.fs

Finding the Nearest Tube Station with LINQ

I recently wrote a little command line program in C# that can tell you the name of the nearest tube station. I’ve put the program on GitHub in my Coding Experiments repository:

https://github.com/robert-impey/CodingExperiments/tree/master/C%23/NearestTube

The interface is very simple- this more of an experiment than something that I intend for mass consumption! You enter a location via the command line as the latitude and longitude:

The starting point of the program was to calculate the distances between points. To do this I adapted some JavaScript code that John D. Cook wrote:

http://www.johndcook.com/lat_long_distance.html

Mathematical code looks very similar in many languages, and the translation from JavaScript to C# was trivially simple as the languages are very similar in this case. This code is part of the Point class:

        /// 

        /// Porting JavaScript code from
        /// http://www.johndcook.com/lat_long_distance.html
        /// 
        /// 
        /// 
        public double Distance(Point that)
        {
            // Compute spherical coordinates

            double rho = 6373;

            // convert latitude and longitude to spherical coordinates in radians
            // phi = 90 - latitude
            double phi1 = (90.0 - this.Latitude) * Math.PI / 180.0;
            double phi2 = (90.0 - that.Latitude) * Math.PI / 180.0;
            // theta = longitude
            double theta1 = this.Longitude * Math.PI / 180.0;
            double theta2 = that.Longitude * Math.PI / 180.0;

            // compute spherical distance from spherical coordinates
            // arc length = \arccos(\sin\phi\sin\phi'\cos(\theta-\theta') + \cos\phi\cos\phi')
            // distance = rho times arc length
            return rho * Math.Acos(
                    Math.Sin(phi1) * Math.Sin(phi2) * Math.Cos(theta1 - theta2)
                    + Math.Cos(phi1) * Math.Cos(phi2)) * 1000;
        }

Once I was able to calculate the distances between points on the map, I needed to be able to sort the tube stations of London by distance from the given point. This is the sort of code that LINQ to objects handles very naturally. In the SequentialTubeStationFinder class, I have the following method:

        public TubeStation FindNearestTubeStation(Point point)
        {
            return (from tubeStation in tubeStations
                    orderby tubeStation.Point.Distance(point)
                    select tubeStation).First();
        }

tubeStations is a generic list of TubeStation objects. Each has a Point property that is used to sort the tube stations and find the nearest one to our location.

The declarative style of programming that LINQ uses is much easier to read (and therefore maintain) than the equivalent code written with a for loop.

One liner to show logs without Rotated Backup files

I’ve been looking at the Apache log files on a web server this morning. There are many virtual hosts on the machine and the log rotation scripts have created many numbered backup files of the logs. To make the directory listing more readable, I have been using the following one-liner:

ls -l /var/log/apache2 | grep -Ev -e '[[:digit:]]+(\.gz)?$'

This will only display the current log files, assuming that /var/log/apache2 is the directory in which you store your Apache logs and that you do not store any other files there.

I hope it helps.

Decimal to Binary

In order to prepare for teaching computing, I’ve been reading Introduction to Computing by David Evans.

In the first chapter there is an excellent explanation of binary numbers using binary search trees. You can build a bitstring for the binary representation of a number by starting at the root (highest node on the tree) and comparing the number to the midpoints of a range of numbers that you are searching. If you answer a question with “yes” append “1” to your bitstring, otherwise append “0”.

The number 6 would be “Yes”, “Yes”, “No” or 110.

I decided to implement the logic of this binary tree in Java.

private static String decimalToBinary(int input) {
    if (input  7) {
        throw new IllegalArgumentException();
    }

    StringBuilder result = new StringBuilder();

    if (input >= 4) {
        result.append('1');
        if (input >= 6) {
            result.append('1');
            if (input == 7) {
                result.append('1');
            } else {
                result.append('0');
            }
        } else {
            result.append('0');
            if (input == 5) {
                result.append('1');
            } else {
                result.append('0');
            }
        }
    } else {
        result.append('0');
        if (input >= 2) {
            result.append('1');
            if (input == 3) {
                result.append('1');
            } else {
                result.append('0');
            }
        } else {
            result.append('0');
            if (input == 1) {
                result.append('1');
            } else {
                result.append('0');
            }
        }
    }

    return result.toString();
}

This works for converting decimal numbers to binary strings. I think that writing a program like this might work as an exercise for secondary school students for learning about conditional statements in programming and binary numbers.

However, the range of inputs is severely limited (0 to 7 inclusive). I wrote another method and a recursive helper method that can take arbitrary non-negative decimals in the range of Java ints and return the corresponding binary number:

private static String decimalToBinaryRecursive(int input) {
    if (input = midpoint) {
        result.append('1');
        return decimalToBinaryRecursiveHelper(input, midpoint, Math.abs(delta) / 2, result);
    } else {
        result.append('0');
        return decimalToBinaryRecursiveHelper(input, midpoint, Math.abs(delta) / -2, result);
    }
}

The recursive method is considerably more complex and would be much harder for a secondary school student to write. The mathematics might be unfamiliar for most secondary school students, particularly the code to do with logarithms. You could simplify the mathematics of that code with a while loop that compared increasing powers of 2 to the input. It might be a possible extension task for a gifted and talented student. It could also be a task for a lesson on recursive methods.

I can see that teaching computing will present challenges. There are an enormous number of toy programs that we can get students to create in order to learn about programming. However, in order to extend any of these tasks to make them more practical and interesting, it is very easy to set challenges that are rely on outside skills, knowledge and understanding that many secondary school students do not have.

The whole program with a main method for testing looks like this:

package decimaltobinary;

/**
 * @author Robert Impey
 */
public class DecimalToBinary {
    public static void main(String[] args) {
        System.out.println("Simple Approach");
        for (int i = 0; i <= 7; i++) {
            System.out.printf("%d\t%s\n", i, decimalToBinary(i));
        }
        
        System.out.println("Recursive Approach");
        int bits = 8;
        for (int i = 0; i <= Math.pow(2, bits) - 1; i++) {
            System.out.printf("%d\t%s\n", i, decimalToBinaryRecursive(i));
        }
    }

    private static String decimalToBinary(int input) {
        if (input  7) {
            throw new IllegalArgumentException();
        }
        
        StringBuilder result = new StringBuilder();
        
        if (input >= 4) {
            result.append('1');
            if (input >= 6) {
                result.append('1');
                if (input == 7) {
                    result.append('1');
                } else {
                    result.append('0');
                }
            } else {
                result.append('0');
                if (input == 5) {
                    result.append('1');
                } else {
                    result.append('0');
                }
            }
        } else {
            result.append('0');
            if (input >= 2) {
                result.append('1');
                if (input == 3) {
                    result.append('1');
                } else {
                    result.append('0');
                }
            } else {
                result.append('0');
                if (input == 1) {
                    result.append('1');
                } else {
                    result.append('0');
                }
            }
        }
        
        return result.toString();
    }
    
    private static String decimalToBinaryRecursive(int input) {
        if (input = midpoint) {
            result.append('1');
            return decimalToBinaryRecursiveHelper(input, midpoint, Math.abs(delta) / 2, result);
        } else {
            result.append('0');
            return decimalToBinaryRecursiveHelper(input, midpoint, Math.abs(delta) / -2, result);
        }
    }
}

This post contains content that was released with the following license:
http://creativecommons.org/licenses/by-nc-sa/3.0/us/
and is published with the same license.

GHCN Monthly and MS Access

For some of the last few evenings, I have been learning about MS Access’s data import functionality in order to interrogate the data of the Global Historical Climatology Network-Monthly dataset. This dataset holds records of temperature readings dating back to the beginning of the eighteenth century from more than seven thousand stations around the globe.

GHCN Monthly

The data are in text files with a fixed width format. It’s very straightforward to set up the import format (although there are many columns!) and save the import specification so that future datasets can be imported as they are released with ease. The largest data files have almost half a million rows, yet Access can import the data in a few seconds. The resulting table of readings of average, minimum and maximum temperatures for each month for each station has more than one million rows. I have not experimented with adding indexes yet but, in spite of this, I can run queries that are not painfully slow.

Now that I have the data into an Access database, I hope to start analysing the data. I have produced a couple of charts for a single station but am yet to run any serious calculations. I have read of a similar project at:

A Quick and Dirty Analysis of GHCN Surface Temperature Data

The algorithm that caerbannog (the blogger) uses in his C++ program to smooth the data and calculate averages is fairly simple. Something similar should be possible (or even easy) using the MS Office tools.

Ultimately, my aim for this is to make this the basis of an ICT lesson or project. As caerbannog notes “Never in history has science been more accessible to the general public than it is now.” The quantities of data that can be accessed for free are as enormous as the power of the computers that are now cheaply available. I hope that my students will be inspired to look deeply into the issue and this will help develop their sense of empirical curiosity.

Generics in VB.Net

Taking a lead (again) from Java generic types for beginners, I decided to experiment with generic types in VB.Net. The ICT Cool blog covers the idea behind generics and the MSDN documentation on generic types in VB.Net gives more details on the topic, so I won’t repeat what has been explained elsewhere.

My code shows how generics can make code more robust by enforcing compile time type checking. The type safety of the various objects can be checked in Visual Studio by hovering the mouse over any of the variables in the code. This brings up a pop up that says the type of the object. Many of the lines of the main sub have been commented out because the project would not build otherwise. Try uncommenting them to see the errors that the IDE finds.

The code also shows that generic types allow coders to build and use type safe, polymorphic collections. Put simply, we can create a list (for example) that will only allow us to add an object of any type, so long as it implements an interface given at the time of construction.

GenericsInLists

String Manipulation with the Decorator Pattern

Inspired by the Java program to sort and reverse a string at ICTCool.com, I decided to try to solve the problem using Java and the Decorator Pattern.

StringDecoratorDemo.tar.gz

My solution required considerably more lines of code than the code at ICT Cool. For a problem as simple as this, using the Decorator Pattern is probably overkill. However, the advantage of this pattern is that multiple decorators can be stacked up at run time in any order that we choose. Also, if we wanted to add more operations later, we simply add a new class, which is cleanly separate from the other operations.

I’ve written the program using NetBeans, which creates quite a few files other than the source files, which are in src. To run the program, cd to the dist directory and type java -jar StringDecoratorDemo.jar.