I like to develop apps that work on different platforms, and across different platforms. These apps often need to transmit data across the network (e.g. in the case of a web application with both server and JavaScript code), store data in files, or read configuration data. I’m a fan of using JSON for these types of applications. It’s a popular meta-format based on JavaScript types and syntax, but its use extends well beyond JavaScript applications. There are many interchange formats, but JSON is very well supported; there are JSON libraries for every language you can think of. It’s stored as text, which means it is easily sent in web requests, and it’s easy for humans to read and edit (much friendlier than XML, or a binary format, in my opinion).

A JSON file to store or transmit a player details in a game might look like this:

{
    "name": "Jim",
    "score": 500,
    "alive": true
}

On thing that makes JSON easy to use is that you don’t need a formal definition of valid data. One system can write a JSON file and another can read it, without any other files needing to be shared. The convention as to how the JSON should be interpreted is a matter of convention; determined by how the programs are written.

That’s great for making a quick start when you’re creating software. But it can cause a problem as the program grows in complexity, or more engineers get involved. Without a formal written structure (known as a schema) it’s easy to become confused about exactly how to read or write it.

JSON Schema

Fortunately there is a standard schema format for JSON, called appropriately JSON Schema.

A JSON Schema is itself a JSON document that specifies a test as to whether another JSON file passes certain tests that assert its validity for a certain application. An application developer supplies a schema for their program’s data, and if an individual file passes the schema, it’s valid for use.

This is one schema to validate the above JSON:

{
  "$schema": "https://json-schema.org/draft/2019-09/schema",
  "properties": {
    "name": {
      "type": "string"
    },
    "score": {
      "type": "integer",
      "minimum": 0
    },
    "alive": {
      "type": "boolean"
    }
  },
  "additionalProperties": false,
  "required": ["name", "score"]
}

I’ve been working on an application that uses JSON extensively. Much of the system is written in Java, so I use the popular org.json library to read the data. The text of a JSON file is parsed into an org.json.JSONObject or JSONArray, then it’s read using string key accessors. For example:

  public static void read(JSONObject jsonObject) {
    String name = jsonObject.getString("name");
    int score = jsonObject.getInt("score");
    boolean alive = jsonObject.getBoolean("alive");
    // ....
  }

Having to use string key accessors means that there’s room for programming error; even when a Schema is available. I found a few libraries that could copy JSON data into structured Java classes. However they all required the whole JSON file to be copied into Java classes at once. This means that if schemas aren’t available or practical for part of the data, they can’t be used. If the schema uses features that the library doesn’t support, it can’t be used either.

I wanted something that could allow me to gradually adapt a program written for org.json types into structured types, with the option to ‘fall back’ to regular unstructured data access for any reason.

Structured JSON access in Java

Something like this:

  public static void read(JSONObject jsonObject) {
    Player player = new Player(jsonObject);
    String name = player.getName();
    int score = player.getScore();
    boolean alive = player.isAlive();
    // ...
  }

This approach greatly reduces the changes of misinterpreting the structure. IDEs such as those published by JetBrains will be able to make suggestions as you type that match the intended format of the data you’re reading. In short; errors that would normally become evident at run time are made evident as you first write the code.

jsonschematypes

I wrote a library to generate Java wrappers around org.json objects that make this kind of structured access possible. It means that many format problems will be detected at build time, rather than run time.

It converts standard JSON Schemas into strutured access classes that wrap the JSONObject. They look like this:

public class Player {
	private final JSONObject jsonObject;

	public Player(JSONObject jsonObject) {
		this.jsonObject = jsonObject;
	}

	public JSONObject getJSONObject() {
		return jsonObject;
	}

	public String getName() {
		return jsonObject.getString("name");
	}

	public int getScore() {
		return jsonObject.getInt("score");
	}

	public boolean isAlive() {
		return jsonObject.getBoolean("alive");
	}

	public boolean hasAlive() {
		return jsonObject.has("alive");
	}
}

Design

Classes are created according to the design of the JSON Schema from which they are derived. The library takes some license in creating Java classes that match the inferred intent of the schema, to make them relatively lightweight and not overwhelming humans to read. This means tactcialy omitting some varations of accessors that could potentially be supplied. For example, if a schema specifies a default value for a property, no has method will be generated to test for the presence of that property on an object, since a value can always be returned. The effect of this is that changes to the schema could result in methods being removecd from generated Java classes.

Where the generator cannot identify any useful accessors to build, no class is generated and the containing class will supply JSONObjects directly.

The generated classes are designed to be as close as possible to idiomatic Java as possible. For example, using is getters such as isEnabled when exposing booleans.

They are not designed to hide or completely abstract the fact that the objects they interface are backed by JSONObjects and JSONArrays. It is a goal of the library that programmers can switched to unstructured access (via the usual JSON accessors) of data where required.

To build the classes I used a code generation library com.helger.jcodemodel which is an extended fork of Sun’s Java code generator.

As well as the Java library there’s a Gradle plugin that means it can be use in IntellIJ IDEA and Android Studio to automatically generate the classes when your schema changes.

Library, plugin and demonstration

Instructions on how to use it are on the github repository, where I’ve made the source code available under the Apache 2.0 license. Note there are separate instructions for the library and for the Gradle plugin.

There’s also an online demonstration where you can copy your own schemas into an editor and preview the Java code that would be created.

If you have questions, as always, feel free to contact me on the comments below, in GitHub issues on the project, or by email at jimblackler@gmail.com.

For a demo click here

download (1)

I’ve written a web app that generates diagrams showing the sequence of digits when a fraction (such as ¼) is written in decimal form (0.25). One diagram can be used for every fraction (non-negative proper fraction) with a particular value on the bottom (the denominator). My program feeds data into the springy.js framework which uses a force-based layout to draws network diagrams of graphs.

To see how to find the decimal form of 21 / 56, click on the demo link. This diagram can be used to find the decimal form any non-negative proper fraction with 56 on the bottom.

Start by writing down “0.” (since all simple fractions are no less than zero but under one). Then find the vertex labeled ‘21’, your numerator (the top part of the fraction). Next simply follow the arrows, writing down the numbers on the arrows as you go. The arrow labeled “3” takes you to vertex 42 (write down “3”), “7” to vertex 28 (write down “7”), and “5” to vertex 0 (write down “5”). We always stop at ‘0’ so the sequence is complete.

You’ve written “0.”, “3”, “7”, “5”. A quick check on a calculator will confirm that 21 / 56 is equal to 0.375.

This diagram works for all other fractions with a denominator of 56 and numerator between zero and 55. On the same diagram try for ‘18’. The sequence starts out “3”, “2” but after a bit you’ll find you’re in a cycle that starts “1”, “4”, “2”, “8”, “5”, “7”, then returns to “1”.

Checking with a calculator shows me that 18 / 56 is 0.32142857142857142857… repeating forever.

Motivation

I made the app because I was wondering if there was a rule to say which fractions had repeating sequences when written as decimals, and it occurred to me how easy it would be to generate a graph from the data using a standard tool. I’m still thinking about the rule problem, but the diagrams help visualize the problem.

More diagrams

Here are some more examples for fractions of different denominator values.

Note that you can change the values in the input boxes then hit return. You can also use the up/down arrow boxes when an input box is enabled.

Springy is like most popular graph diagram generators in that it uses a spring system to arrange the vertices.

This makes it interesting and fun to.manipulate. However you usually need to ‘unknot’ diagrams by hand to remove any overlapping edges. A graph drawing algorithm could be tailored to generate these diagrams while maintaining more of the symmetry and making overlapping edges impossible.

How it works

Pseudocode to generate the diagram:

for (numerator = 0; numerator != denominator; n++) {
  // make a vertex labeled ‘numerator’
}

for (numerator = 0; numerator != denominator; n++) {
  digit = (numerator * 10) / denominator;
  next = (numerator * 10) % denominator;
  // make an edge from ‘numerator’ vertex to ‘next’
  // vertex, labeled ‘digit’ 
}

To understand how this works, consider how you might find just the first digit after the decimal point in an expansion of a fraction n / d (non-negative proper fraction). Remember that in general, multiplying a number by 10 shifts its decimal point one position to the right. If we do that to any fraction we get 10n / d. Now what was the first digit of its decimal form (right of the decimal point) is now to the left of the decimal point. So the whole part (the ‘quotient’) of 10n divided by d will give us the first decimal digit. The remainder of 10n divided by d (still over d) represents the part to the right of the decimal point, which is the rest of the decimal string (discarding the leading ‘0.’). Since ‘n’ hasn’t changed we can find this value on the same diagram, and repeat the process to get the next digit, then continue forever to get the whole string!

Let’s look at an example 25/27. Your calculator will show you this is 0.9259259259259259. But let’s verify with this method.

25 multiplied by 10 is 250, which divided by 27 is equal to 9 + 7 / 27. “9” is the whole part (the quotient) and this is the first digit. 7 / 27 is the remainder which is the rest of the string. Indeed, my calculator tells me this is 0.25925925925925924. If I repeat the process for 7 / 27, I get 70 / 27 which is 2 + 16 / 27. “2” is the next digit. Repeat with the remainder, so 16 / 27 goes to 160 / 27 which is 5 + 25 / 27. The next digit is “5”, but now our remainder is what we started with. So we will repeat “9”, “2”, “5”, forever, verifying the calculator result of 0.925925925….

Different bases

What if we wanted to see how fractions would be written in systems other than decimal, such as binary or hexadecimal? Changing the base is as easy as changing the number 10 in our calculations above. This diagram shows part of a binary base expansion.

Some more examples:

Patterns

We get lots of interesting patterns from playing with the numbers, but whatever you do, certain constraints arise. Many of thse are from the fact that the kind of graph we create is a directed pseudoforest, that is, every vertex has exactly one edge out (although this may be to itself).

Given the ‘many to one’ relationship between the different vertices (each vertex has just one edge out) you can only ever end up with one or more subgraphs of connected vertices formed of a ‘hub’ (one or more vertices in a cycle) and ‘spokes’ (non cycling or tree graphs heading into the hub).

The rough explanation is that a walk starting at any vertex you will always end in a cycle or (closed walk) since even ‘0’ has an edge back to itself. Any other vertex with a walk reaches any vertex on this cycle will be part of the same subgraph (connectable in any direction on the edges). Since any walk can only have one cycle, no other cycles can exist in this subtree. So, all walks entering the cycle can be drawn as trees rooted at the position they enter the cycle.

But beyond that in this specific case (the fraction graphs) you see some really interesting patterns just by changing the numbers.

Note how values of ‘d’ that have no factors in common with the base (in the case of 10 can’t be evenly divided by 2, 5 or 10) have subgraphs that are all cycles.

You might consider how d’s prime factors (including if they are in common with the base’s prime factors or not) affect the shape of the graph. You might ask what determines the number of subgraphs, or the number of vertices in the cycles, and whether they are all the same.

Another interesting thing about this is the whole graph is a closed walk (starting at any value will end up in the original position) you now have a graph equivalent to the kind encountered in the modular arithmetic used in cryptography.

Source

I hope you enjoy the app. The source can be found on GitHub.

I’ve just published a new app for Android Wear smartwatches to the Google Play Store. It’s called Your Photos Watch and it lets you view your personal photos as backgrounds to a specially-designed watch face.

watch_pic

Project

I wrote previously about my first Android Wear watch face. With that project done I turned to something a little more complex. When I first received my smartwatch (a LG G Watch), I thought it might be nice to put some family photos on it – like a high-tech version of the photo in the wallet. I was a little disappointed to find that this isn’t something supported out-of-the-box. Nor could I find any photo apps on the Play store, using the obvious keywords.

This seemed like a missed opportunity as this is something that a smartwatch can uniquely offer. As an app developer there was only one thing to do; make the app myself.

Making the app you want to see is an approach I would recommend to anyone looking to get started with app development. Think of those times you go looking for an app to do a particular thing and don’t find one that works the way you want. Build that app and get it out there! Others will find it useful too, I guarantee it!

App design

shot0

I asked myself what form the app should take. A simple picture viewer was one idea, but traditional apps aren't really a good fit for the tiny screen of smartwatch. A custom watch face seemed like a better approach. The app could show a fresh picture each time the watch wakes from ambient mode (done by the watch when you rotate it to look at it). The user could make a selection photos to show using the companion phone app.

Data

The first technical hurdles were to get the photos from the phone app to the watch face app, and to keep them stored there.

In my first experiments I attempted to download photos directly from the internet on the device. I soon found out that this isn’t supported – directly at least – even though it could have been, since the watch is effectively tethered to the phone, which could proxy an internet connection. I realized this was probably by design, to encourage a thoughtful economy of internet use. I studied the intention of the Android Wear design to see how my plans could be adapted to gel with the API designers’ intentions.

I studied the Data API and after some experiments it was clear that creating a Data Item per photograph would allow me to synchronize from phone to watch. In addition experiments showed that the Data Items persist as long as the companion app remains installed on the phone. This means that in practice the Data API can act as long-term storage for the photos. The watch face and companion apps simply query for all Data Items to see which photographs have been selected by the user. When the user chooses to remove a picture, the Data Item is deleted.

Cropping

subject_top

One issue had yet to be solved. I was expecting to have to down-scale pictures to the resolution of the watch. However, the screen resolution of the smart watches is in a square aspect where most photographs are something like 4:3. It would not be possible to show the whole picture on the full screen of the watch. Some ‘letterboxing’ could be applied to show the entire picture but on an already small watch face this means diminished visual impact. I’d rather crop the photos, but this means typically one quarter of the area of the picture will have to be cut out.

Unfortunately taking the center square of the photo will often crop out the subject of the photo. A common case is when the subject is standing, in a vertical or ‘portrait’ format picture. The face is often in the top quarter of the frame; not the center, as in the picture above.

example

Here’s an example of a landscape format photograph where the subject of the photograph (some strange looking software engineer) is not in the center of the frame. If this photo was cropped for a watch face by taking the center square, half of the subject’s face would be cut from the picture, which in this would be terrible.

example1

The most obvious option would be to have the user select the area to crop in the companion app. However this adds an extra step for users to complete. On mobile, fewer required user interactions is always better.

Face detection

My more ambitious idea was to use some off-the-shelf computer image recognition software to find the faces in each picture. When faces were found the cropped square can be adjusted to ensure as many as possible were in the chosen area.

example3

example4

It says something about technology today when such a computationally-intensive task can be performed on demand on a mobile phone, but a quick web search revealed that this was indeed feasible. The free software application called Open CV emerged as the most likely candidate. An Android port is available and many developers seem to be using it.

[Later edit: Thanks to Ian Lake on the Google+ Android Wear Developers group for pointing me at this article. The existence of this class escaped me in my own research, somewhat embarrassingly. Since the OpenCV solution is working to my satisfaction currently I will leave it as it is for now.]

I had one or two practical issues importing the latest version into the build and getting the face-finding classifiers I had loaded and working. (Check the AutoCropper class in the files in the project on GitHub if you’re curious). Some tweaking of the input parameters was needed to get the balance between false negatives (faces not recognized) and processing time right.

I was pleased to arrive at a solution that works to my satisfaction around 19 times out of 20. The great advantage is the user has to do nothing to have their photos correctly cropped. In fact I would wager that the majority of users never even think about the cropping process. It will work as expected with no involvement from. Exactly how a good app should be.

Visual design

watch1

Making this app I spent a great deal of time tweaking the watch face design. I thought about exposing settings to the user to change the visual appearance. If enough people ask me I might add this in later versions, but design-wise this can be something of a cop out. I would prefer to ship the app with a design that made a strong statement and that I felt worked within the design constraints of the app.

The main problem is this; the watch face should communicate the time quickly and clearly. If it doesn’t, it is failing in its primary function as a watch face, and once the novelty of the photo feature is worn off people will switch to a more easily-read watch.

On the other hand, the design should not cover too much of the user’s photo. If it does, the unique selling proposition of the app is lost.

Yet these two requirements conflict. A bolder design will be easier to read but will obscure too much of the user’s photos.

Faces

shot4

I decided to include both a digital and traditional “analog” watch face.

The analog face took by far the most experimentation. The first problem is choice of colors. These shouldn't be too similar to the background photograph color or the watch face will be unreadable. As I can’t predict the colors of the photographs selected by users this is a problem.

A trick for showing text of other details over a multi-colored background is to use two colors side-by-side that contrast from each other. That way you have created an internal contrast in the image, meaning it should be readable whatever the background is. In the case of the watch face I found a white outline a few pixels thick coupled with a dark blue fill color achieves this contrast. Because the effect is quite striking I softened the design with round rather than square edges on ticks and hands. The high contrast allows the hands to be drawn slightly semi-transparent (around the 80% opaque mark) to subtly reveal a small amount of extra detail under the hands and tick marks.

watch2

The application of a dark drop shadow creates even more contrast and creates a subtle three-dimensional effect with the watch face over the background picture.

The digital face was a lot more straightforward. I chose to display hours and minutes in a large-ish Roboto font in the bottom half of the screen. Because it occupies relatively little of the screen the risk of obscuring the user photos is low. The same contrast-enhancing methods were used in the analog face.

Data sources

shot2As the user has to supply photos for the watch face, I needed to work out where these would come from. The most obvious and easiest source is the photos that the user has already stored on their phone (e.g. ones they have taken with their phone camera).

Phone

A query of images in the Media Store handles this easily, once the relevant permission is added to the manifest.

Two classes handle the import of photos and handling in a Recycler Adapter. (This project marked the first time I've used the new Recycler View on an Android project.)

One nice feature of this API is that the pictures can be requested in a couple of thumbnail sizes. The MINI_KIND size approximates at 512 x 384, which is actually larger than the typical target watch size of 320 x 320. That way my app doesn't have to downscale massive camera images itself.

Google

shot1

Given that any user with access to the play store will have their phone connected to a Google account, this suggested another obvious photo source. Interestingly there is no modern API to access photos shared on Google Plus, or photos that might have been save with the photos backup feature from one of the user’s previous Android phones. However these photos can be obtained from the aging Picasa API. I say aging, because this uses an earlier version of the GData API and by default returns XML.

This part of the operation turned out to be the trickiest parts of the project, something I had not anticipated at all.

I made several wrong turns trying to parse the XML, for instance by reading a document and using XPath expressions. After a lot of annoyances with namespaces in the XML, I got it working, just. However long delays in the app showed that this is simply far too slow to be done on the phone when 100s of photos are being processed.

Then I tried to use the official GData API Android libraries. However this took my app over the 65,535 symbol limit (Dex limit). I experimented with various ways to work around this such as ProGuard rules to strip unused content, and multi-Dex mode. However ProGuard was breaking OpenCV by stripping symbols it was using (the large amount of native code in OpenCV complicated this). I spent many hours trying to get the ProGuard rules right before deciding I should move on. Multi-dex mode was similarly troublesome.

I then went back to parsing the XML myself, this time using a faster “forward parser” (aka SAX) which interprets the XML stream without building a full version of the document in mmeory (a 'DOM'). This approach is faster but the code is considerably harder to develop and read than XPaths. This probably would have worked but I stubbornly wanted to separate the code that handled the parsing of each photo fragment into a different class, to match the existing structure of the code. Unfortunately, Java’s SAX implementation has a ‘push’ structure – the parser controls flow and calls back a handler with information about the file data – rather than a ‘pull’ structure where the main program would call back the parser to iterate over the data. This means the whole file has to be dealt with by a single handler. I looked around for an XML parser with a ‘pull’ approach but again I felt that I was really wasting time.

Then the penny dropped; I vaguely recalled that older Google feeds can on demand return a form of XML translated into JSON. JSON has a wider selection of parsers on Android including a ‘pull’ parser; android.util.JsonReader. Sure enough, adding ‘alt=json’ to the feed URL returned a translated feed. I could have the best of both worlds; my code could be structured the way I wanted, and a reasonable performance could be obtained too.

Authentication to get access to a user's private data was the remaining challenge. For Google GData services it is possible to authenticate with the aid of the phone's account manager. There is something of a back-and-forth (sometimes called the 'OAuth2 dance') to get the user's email address (required) and an up-to-date access token to pass in to the API.

Facebook

shot3

I could have gone on to add access to lots of other services such as Dropbox, Flikr, Instagram and more. If this app gets super-popular and I get requests to do so, I might. However, there was one obvious candidate given its popularity on Android and its history as a photo-sharing service, and that’s Facebook. By allowing import of photos shared in Facebook I could increase further users chances of finding treasured photos for the watch service (and get some useful experience in the API for myself too!)

The last time I dealt with Facebook as a developer was at work, some time around 2009, when I added some integration widgets to the AdSense publisher controls. I remember this being reasonably straightforward, but even so taking a new look five years later I was amazed; Facebook’s developer experience is incredibly slick, for Android at least. They supply an Android library that integrates with the Facebook Android app making user management (signing in and out), authentication and data collection incredibly easy. I had it running quite quickly; the most complex part was some logic to select the most appropriate-sized version of images from the selection offered.

Another hurdle was that apps that request permission to view user photos need to be manually reviewed by Facebook to ensure they meet the terms of use and offer a good user experience. This was understandable but added a little paperwork and worry (for one thing, would the reviewers even have an Android Wear device to hand to test the app?) In the event, they quickly approved my request.

The app

Like all my apps it’s completely free. It’s on the Play Store from today. This one is licensed under Apache 2, and the source can be found on GitHub.

Feel free to get in touch on jimblackler@gmail.com if you have any thoughts or queries about the app.

feature

I made a watch face for Anrdoid Wear which is in the Play Store now. It’s inspired by the clock tower at the Palace of Westminster, London, better known as Big Ben.

hero_watch

Idea

Recently I was given an LG G Watch. As an introduction to Android Wear I loved it, I found the device much more useful than I was expecting. Not having to get my phone out of my pocket to check my notifications is surprisingly useful.

I also loved the ability to chose watch faces I’ve previously written about an animated Big Ben effect.This was written in SVG for use on the web, but I had a ‘light bulb moment’ when I realized that this existing could be adapted for Anrdoid Wear. Most of the difficult work (preparing the digital images and proving the concept would work) had been done.

big_ben_2

Project

The first job was to update to Android Studio (I’ve been a long-standing Eclipse user to date) and to learn how to code for Android Wear. I was pleased to discover that it’s not too different to coding for a phone, it’s basically Android on the device, slightly cut down for the form factor. The hardest part for me was realizing how the two app executable (APKs) you have to deliver (one for phone, one for app) work together and how deployment (e.g. to Play Store) was supposed to be done.

Design

twoI studied the design guidelines and realized one adjustment would need to be made; introduction of an ‘ambient mode’ where the screen was mostly black. This meant drawing new stylized versions of the watch face and hands, which I did in Inkscape. I tried to capture the iconic Gothic style of the original while using outline effects so as to draw very little content in ambient mode.

Code-wise it was then a matter of studying the watch face samples and producing my own version. I used Android canvas to scale, rotate and overlay the bitmap watch face elements.

Check it out

The app can be download from the Play Store now. It requires an Android Wear watch with Android 5 (Lollipop) or better.

Source for the project is available in GitHub.

IMG_20141220_145738

I regularly read Reddit on a phone, and I’ve come to admire a particular bot autowikibot. When someone posts a link to a Wikipedia article the bot replies with an excerpt from the article directly into the conversation. Without the bot replying, in order to understand why the link was posted I’d have to follow the link – taking me out of the app, incurring a delay and data use.

I noticed that there was a similar problem to be solved with YouTube links. Reddit users regularly post these but unlike Wikipedia links there’s nothing in the URL to indicate what the article might be about, just a string of digits such as “dQw4w9WgXcQ”. When I’m reading a conversation on Reddit and someone posts a YouTube link without explanation it’s frustrating; I have to leave the Reddit app to know why that post was made.

I built a bot in Python using the Reddit API (via the superb PRAW), the Google API for YouTube for video statistics, all hosted on the cloud application platform Heroku.

bot2

It’s up and running now, and can be seen in action at http://www.reddit.com/user/youtubefactsbot

What is Reddit and what are bots?

Redit is a massive and hugely popular discussion website. It has hundreds of millions of users, and thousands of subreddits (discussion pages). As well as internet users talking amongst themselves, the Reddit API allows the creation of ‘bots’. These can look like normal Reddit accounts, but their activity is controlled by an automated processes. The bots join in conversations; they typically react to a phrase and reply in order to provide information or amusement.

How does it work?

mobile

A bot is really nothing more than a manually-registered Reddit account being controlled through the API by a long-running program on a computer somewhere. Comments are fetched and and analysed by the program; if it chooses to reply, it does so through a POST to the API.

PRAW makes this process very easy with a helper method called comment_stream(). This allows you to get a look at submissions and comments as they are posted. Provided not much extra processing is needed, it’s feasible to keep up with the comment stream and react to every post.

My bot simply runs a regular expression over the comment to extract YouTube links, gets the video ID and fetches the data from the YouTube API. Most of the logic in the app is around formatting the comments and obeying Bot Etiquette.

Bot etiquette

From the outset with this project I wanted to ensure that the bot would be found useful and not annoying by Reddit users. It’s important to remember that a bot is a machine process injecting itself into a human conversation. This is one reason why bots have a mixed reputation on Reddit, even though subreddit moderators can choose to ban individual bots (very likely if they cause annoyance). I took care to err on the side of caution with the bot’s interaction.

At the time of writing, the bot:

  • Only replies to very short comments; normally just a raw link without context.

  • Doesn’t reply to a comment if there’s a reply already, so as not to break the flow of the conversation.

  • Attempts to delete any of its comments if they are downvoted (effectively allowing readers to delete bot comments).

  • Only adds a single comment to any given submission (thread); except in very large threads.

In addition, the creator of autowikibot made not only the source for his bot online, but also (via Reddit’s wiki feature) the user and subreddit blacklist. These are users who have requested the bot not reply to them, and subreddits that have banned the bot. By applying the same blacklists to the youtubefacts bot from day one I was able to reduce the risk that the bot would comment where it wasn’t wanted.

Mainly I took care to make the information posted by the bot about the videos as information-dense as possible in order to justify its position in the threads. I have a ton of information available from the API, but a lot of it (such as bit rate, comment count and more) simply would be interesting enough to justify it’s place in the thread. I decided not even to include the channel (YouTube poster) name. I include the video name, running time, view count and posting date. I also include the first line of the description as it often adds useful information about the context. I don’t do this if it contains a link so as not to potentially introduce spammy links into Reddit threads, and also because those kinds of comments tend to be promotional rather than informative.

Source

The source is also online at https://github.com/jimblackler/youtubefactsbot and licensed under GPL.

If you want your own implementation you’ll have to register applications on both Reddit and Google API (YouTube), sign into both accounts locally, and upload the secrets and tokens folder to your application on Heroku.

Hope you like the bot.

bigpicHere’s a web-based version of Conway’s Game of Life. The rules are the standard recipe but I’ve added colour a color effect to the cells. At startup the cells are assigned colors with random hues. Newly-created cells take the color most similar to the neighbouring cells. When cells die I leave a trace of their color in the vacant cell background.

Adding color makes the simulation more striking, and it also vividly illustrates how local patches of the simulation share common ancestry.

About Life

Conway’s Game of Life is a wonder of mathematics. Invented by mathematician John Conway in the 1970s, it isn’t really a game but a simulation experiment involving squares in a grid (‘cells’) that are either ‘live’ or ‘dead’. Any live cell without two or thee neighboring live cells (including diagonals) becomes a dead cell on the next turn (or ‘generation’). Any dead cell with three neighbouring live cells becomes live on the next generation.

trad_glider

From those very simple rules arises a fascinating array of complex behavior. The menagerie of structures and creatures that can emerge has been studied continuously since Conway invented his game. You can read all about Oscillators, Spaceships, Reflectors and more on LifeWiki and elsewhere. The small library of Life shapes that I include in my simulation were borrowed from the excellent resources on LifeWiki.

Life is one of those ideas that is so simple it begs for variations. For my project I decided to make an implementation that kept the basic Life rules but added colors to the cells.

Demo

My demo is written in JavaScript and uses Canvas for the graphics. You can vary the size of the grid and the update rate with the links at the top of the page, as well as toggle the color effect.

starpic

When a cell is newly-created a hue is determined which is formed by summing a 2D vector for each of the three live neighbours’ hues; representing the position on the circumference of a circle where the angle represents the continuous hue value. The hue of the new cell is taken as the angle between the origin and the end of the combined vectors (using Math.atan2). This way an ‘average’ can be obtained that does not tend towards any locality on the color spectrum.

As the simulation is so computationally extensive it can act as a benchmark of sorts between browsers. At the time of writing, Safari on OS X was giving the fastest results.

The source is available on GitHub and has a GNU license.

As always, any comments or enquiries are welcome here or at jimblackler@gmail.com.

This tool creates SVG (Standard Vector Graphics) files to illustrate information structured as a basic tree.

Simple tree image

Here I define tree as an ordered graph without loops where every node has zero or one ‘parent’ nodes in the same tree.

It’s a very common structure in computing and will be familiar to most as the structure of folders on a personal computer (as seen in the ‘Unix’ example). It’s also the structure of classes in a single-inheritance object oriented programming language (as seen in the ‘Java’ example).

However lots of real world data can be formatted this way too. For instance an ‘org chart’ of the hierarchy of an organization (because everyone has a boss, apart from the boss of the company).

Project

I wanted to visualize binary search trees to help understand a problem, but I couldn’t find a simple tool to take tree data as text and to output it as a line drawing. I also became interested in the problem of arranging arbitrary tree arrangements neatly, in the original breadthwise order, without overlapping and with sensible spacing between elements. So, I decided to make a tree diagram tool myself.

It may be useful as a tool to generate diagrams of tree structures for documents, presentations and so forth, so I’ve put it online.

Example tree showing character classifications in an online game

The tool is written in pure JavaScript and creates SVGs that all modern browsers can render. This means the scripts can also be dropped directly into web applications that create tree data on the fly, as a reporting/visualization tool. The source is freely licensed under GPL and placed on GitHub.

Use

To make your own diagrams all you have to do is visit one of the demo pages and edit the data (specified in classic tabular style, e.g:

My Root
  My First Child
    My Grandchild
  My Second Child

This will generate the diagram below:

Custom tree image

You can edit the options (provided as editable JSON in an edit box on the page) to customize the image in various ways. For instance setting "flipXY": 1 will convert the image to a horizontal diagram.

Custom horizontal tree image

I won’t detail all the options here because it’s designed for experimentation; just play with the values and see what you get. You can change the relative size and margins of the nodes, line spacing in the labels, arrow size and direction and more.

To change the colors or line styles of the nodes and arrows, or the label font size and style, simply edit the CSS data on the page. For instance, editing the CSS as follows…

text {
  text-anchor: middle;
  font-size: x-small;
  fill: white;
  }

rect {
  fill: green;
  stroke: black;
  stroke-width: 0;
  }

.. would result in this diagram:Custom style tree

Method

The diagram generator has the task of building diagrams that have elements positioned and spaced sensibly, without nodes or lines overlapping, and making the best use of available space (the nominated rectangle the diagram may occupy). Element positions need to be considered as a whole, as repositioning any element will have a knock-on effect on any other elements it might now overlap, free space to better position, and so on.

After experimentation I developed a relatively simple method with all nodes having their vertical position fixed in a level based on the distance to their tree root. The horizontal positions are in order of the breath order of the nodes in the tree, but other than that, they are allowed to move horizontally. The method relies on identifying the one level which has least potential to be repositioned, laying this out with regular spacing and fitting the other rows around it.

Relative values are given in the options for the widths of nodes and the spaces between sibling nodes (nodes that share the same parent) and cousin nodes (nodes that are the same distance from their roots but don’t share the same parent).

  • The tree structure is converted into an array of levels to be displayed in rows.

  • Each level is measured for its minimum width given the spacing ratios in the
    options.

  • The row that occupies the most screen width is nominated as the fixed row.

  • Fixed row

  • All rows between the fixed row up to an including the root are now considered in turn. For nodes that have children (in the level below) they are given an ideal horizontal position as the average (horizontally) of their children.

  • A ‘sweep’ process then travels left to right across the nodes and forcing the rightmost node of each considered pair further right to ensure that it is not positioned too closely to its predecessor. As this may push nodes outside the diagram area, a return sweep performs the same operation from right to left with the rightmost element constrained to the available horizontal space.

  • These positions won’t result in overlapping elements. However because of the way the sweep operates, elements will often result in nodes positioned immediately to the right of neighbours when there is a large gap remaining that could be occupied. In order to have nodes occupy the central position in the available space, a third and fourth sweep are performed in mirror-image of the first two (right to left then left to right). Naturally after sweep four the elements are often positioned immediately to the left of neighbours. So, the positions after sweep two and sweep four are averaged to determine the final position of the nodes; non- overlapping and evenly positioned in the available space.

  • Illustration of the sweep process

  • A similar operation is performed on all the rows below the fixed row traveling downwards. On this occasion, the ideal horizontal position for the nodes is an even distribution of children underneath, with the group centered on their parent node.

Contact

I hope some find the tool useful or interesting. Check out the site and as ever, feel free to contact me on the comments or at jimblackler@gmail.com, or make requests via the GitHub page.

Often I’m browsing the web, and I’m curious as to what others have thought about the article’s I’m reading. Many pages have comment sections but these are usually mostly occupied by that site’s regulars rather than a cross-section of internet users in general. For a while I’ve wanted to make an app that lets you view comments about an article that have originated elsewhere.

So here’s my third Chrome app (after the solitaire game, and an earlier web-dev tool URLGuide, thatI didn’t blog about). It’s an extension that lets you see which Google+ users have shared pages you browse to. You can read the comments on the shares and their replies, and there’s nothing stopping you from joining in the conversation, or circling the other users who may share your interests.

As you browse the web, an icon will appear in your Chrome address bar linking you to discussion between Google+ users about that page. If the icon is red it means it’s a ‘hot topic’ with a number of replies from G+ users.

Like all Chrome apps it’s JavaScript and HTML. It’s pretty standard stuff; you can view the source on the extension using developer mode and it’s not encrypted. I’ve taken care over privacy. The app uses a direct, secure connection to the Google+ API; this can’t be eavesdropped, but I also take care to only make queries about public sites.

I hope you enjoy the extension. You can find it here.

Link to the demo

This next project is a bit of fun for the new year. It’s a maze generator written with JavaScript/HTML5 Canvas. I was thinking about possible algorithms to generate classic maze puzzles and thought it might be interesting to write one.

The algorithm is simple at heart. It’s from a class of puzzle generators that work in conjunction with a solver algorithm; changing the puzzle step by step while continuously trying to solve it to see if it’s still viable.

Method

The maze generator starts with a blank grid. One in four squares are blocked with base ‘columns’. It keeps a list in memory of all the squares on the grid that could be filled in, the ‘blockable’ squares. It then solves the grid in its current state by a classic flood-fill algorithm.

In the solve operation every square that forms part of the shortest path (or joint shortest paths) from top left to bottom right is detected (this are the squares painted as red in the demo visualizer). Because in the early phases there are many equally good routes, it is typical that much of the maze can be painted red.

These squares are then searched in random order to find one that is still in the ‘blockable’ list. It’s removed from the list, the grid square is blocked, and the solver re-run. If the solver reports that every blank square on the grid is no longer accessible from every other square, that piece cannot be blocked without breaking the puzzle. We ‘unblock’ it, but we don’t put it back in the list because it can *never* be blocked without breaking the puzzle. If the solver reports the puzzle is still universally accessible, the current grid is rendered to the screen and the solver repeats.

When there are no squares remaining from the path that are in the blockable list, the algorithm just attempts to block any random squares in the list (with the same accessibility checks) until nothing remains in that list. Then the puzzle is complete.

The reason that squares along the current best route are considered first is that in doing so the length of the solution path can only be increased. Without this constraint virtually every maze ends up with a solution that is too short and almost always forms a diagonal path roughly direct from top left to bottom right.

Please take a look at the demo. Different sized puzzles can be selected (you can customize the values if you’d like to edit the URL parameters). When the puzzle is complete the red solution indicator can be turned on and off. If you’d like to look at the source you can do so in Chrome Web Developer tools or similar tools in other browsers.

Link to the demo

Click here for the Chrome application

Click here to play online

Does the world really need yet another implementation of Solitaire for the browser? Yes, absolutely!

When I acquired a Chromebook recently I looked for Solitaire Chrome apps (my gaming tastes aren’t particularly sophisticated) only to be disappointed by over-presented apps heavy in Flash and Ad-laden.

I just wanted an implementation of regular Klondike Solitaire that matched the simplicity of the old Windows-bundled version. The one played for years by bored office workers worldwide before the internet took over as principal time-wasting activity.

Also I wanted one that would work offline (when user have no internet connection). Solitaire is an ideal activity on the plane or train.

Another motivation was simply that I felt like writing a card game having never developed one before. Also I wanted to understand how feasible the idea of offline browser applications is.

Here it is, a minimal implementation of classic Klondike Solitaire to be played in the browser, developed with HTML5 technology including JavaScript. It’s also presented as a working Chrome application, that can be installed to Chrome with just two clicks.

It was developed using Eclipse and Chrome Developer Tools. Cards were adapted in Photoshop and Inkscape from public domain and Creative Commons resources.

Click here for the Chrome application

Click here to play online

« Older entries