Squares and Graphs

Recently I came across this intriguing little puzzle…

Take the integers 1..n and, if possible, arrange them in a list in such a way that consecutive numbers in the list add up to a square number. Use each number 1..n once only.

In exploring this puzzle I started writing down the numbers and forming a graph where two numbers are connected if they add up to a square. Drawing such graphs is fun but slightly tedious for, for example, [1..300]… Here’s such a graph for numbers 1..15. Starting at 8 then 1 etc. and following the path gives the solution for 1..15.

I became sidetracked into writing a bit of Haskell to generate such graphs and and then create an image from it 🙂

In this post we’ll

  1. look at one way of capturing the essence of what a graph is – without any formal development or assertions.
  2. Then add a few utility functions to create and manipulate such a graph and finally.
  3. Use some Haskell bindings to graphviz to create images of the graphs.

Graph Types

A graph is just a collection of vertices of a given type and a set of edges representing connections between vertices. There are various ways to represent this idea, here is one simplistic option.

For a Graph holding things of type a we have a list of a representing the vertices – V [a].
An edge between two a s is shown as a tuple and all edges is a list of such tuples – E [(a, a)].
Finally a Graph of a is G (V a, E a).

Some Functions

If we start with a list of vertices – for this problem we have 1..n but we can keep it quite general – some vertices will be connected to other vertices, some vertices may have many connections and some may have none. In our puzzle the criteria is that the two vertices (integers) add up to a square. Two numbers adding to give a square is a very specific function on integers. We can generalise it to a function that takes two vertices to give a boolean if the vertices should be connected.
i.e. (a -> a -> Bool)

So, for a given list of vertices we can generate a graph by applying the function to each possible pair like this:

Here we are mapping a function f over the vertices and f is a fold over the vertices of the ‘am I an edge function‘ – (a -> a -> Bool)

The join function is needed as makeEdges creates a list of lists and nubBy sameEdge is used to remove duplicate edges.

We can use this general function for our puzzle by creating a suitable ‘am I an edge function‘ i.e.

To generate a graph where connected vertices add up to a square we just call the buildGraph with a list of vertices and the sqEdge function.

Drawing with Graphviz

Having some previous familiarity with Graphviz I found a Haskell library with bindings for Graphviz. Of course you will need to install Graphviz but the Haskell side is covered by the stack and cabal files in the Github repo for this post. In outline, the pipeline to get an image (.png) of a graph is to

  1. Create the graph… we’ve covered that.
  2. Modify the structure of the graph so that Graphviz can process it. This involves adding ‘labels’ to the edges and vertices.
  3. Use the Haskell Graphviz library to create an intermediate Graphviz dot file.
  4. Use the Graphviz command line to create a png from the dot file.
  5. Look at the pictures 🙂

Modify the structure. Perhaps in retrospect I could/should have defined Vs and Es as a pair and a triple respectively as this is what Grapviz needs. The extra item is a label for the vertex or edge – so we need to add an extra value to the vertices and edges. Here’s a labelling function to do just that.

It takes a vertex function, vf which defines how to label a vertex. Similarly an edge function, ef, that creates a label from the two vertices of this edge. The function works by mapping these two functions over the edges and vertices.

Graphviz dot file. Creation of a dot file and the invocation of the Graphviz command line is done in makeImage

and the graphParams function gives basic details on how to format the display of a vertex – G.fmtNode – and an edge – G.fmtEdge. Pulling all this together into one utility function gives

And some sample outputs:

graphToImage 15

 

 

graphToImage 30

 

graphToImage 50

 

 

and the above can be sequenced like this graphToImage 15 >> graphToImage 30 >> graphToImage 50

Really, just an interesting diversion into playing with graphs and then rendering them!

Of course we can quite easily use a different ‘am I an edge function‘ to create other ‘Integer graphs’. For example buildGraph [1..20 ] (\ x y -> x `mod` y == 0)

produces this graph

 

Having touched on graphs and rendering them the next post will either start looking at how to solve the original problem or will perhaps explore and refine the graph type and further investigate rendering.

Anyway, all the code is here in Github.

Thanks for reading!

 

 

 

 

 

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *

ˆ Back To Top