Since trivial problems bore me, I thought I might make a weekly programming challenge for a bit of fun. Sometimes I find it fun to solve a problem, and compair it to other peoples solutions.

Let me know what you think about the idea (if you like the idea, if the problems are too easy/hard, or if I should just stop).

Rules: There are no rules. You may use any programming language, or any other method of finding the answer (even by hand).

Warning! Don't read the comments if you don't want to see other peoples solutions. You should probably try the problem out yourself before reading the comments.

Challenge #1: Graph Colourability

Difficulty: 2/5
The graph on the left is said to be two-colourable (or bipartite), because you are able to colour the nodes with two colours such that no adjacent nodes are the same colour.
It is impossible to colour the graph on the right with two colours such that no adjacent nodes share the same colour. Thus, it is not two-colourable.

Out of all possible graphs with 7 nodes, how many are two-colourable?

Here's my own solution in Racket.

I do not make any guarentee that my solution is correct!

647168
Time: 5.1s

Whoops! I made the mistake of assuming that the first element's colour doesn't matter. Goes to show you you shouldn't take my word for it.

379312
Time: 5.6s

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.