.tool-versions

ruby 3.0.3

README.md

Graph colouring exercise

This is the Graph Colouring exercise from Computer Science Distilled.

This gist contains a simple starting point for implementations in Ruby which deals with parsing the input file and a simple structure for Graph data. It does not implement the algorithm, which is left as an exercise for you.

colour.rb

#!/usr/bin/env ruby

input_file_name = ARGV[0]

unless input_file_name
  STDERR.puts "Must provide an input file name as an argument."
  exit 1
end

STDERR.puts "Reading graphs from #{input_file_name}"
input_file = File.open(input_file_name)

num_graphs = input_file.readline.to_i
STDERR.puts "Input file contains #{num_graphs} graphs"

graphs = []

class Graph
  def initialize(num_nodes, edges)
    @num_nodes = num_nodes
    @edges = edges
  end
end

num_graphs.times do |i|
  num_nodes, num_edges = input_file.readline.split(" ").map(&:to_i)
  edges = []
  num_edges.times do
    edges << input_file.readline.split(" ").map(&:to_i)
  end
  graphs << Graph.new(num_nodes, edges)
  if i < num_graphs - 1
    # Move past graph separator line
    input_file.readline
  end
end

puts graphs.inspect

rules.pdf

sample1.txt

1
12 11
1 2
3 1
4 1
5 1
6 1
7 1
8 2
9 2
10 2
11 2
12 2

sample2.txt

100
13 16
8 6
1 2
7 3
13 9
1 11
1 6
11 3
2 4
8 9
13 4
3 8
3 10
5 8
13 2
10 13
4 5

16 33
9 5
6 4
15 11
13 7
11 9
5 12
14 8
1 6
5 2
7 9
3 12
6 10
3 7
3 8
6 5
1 10
4 14
9 13
4 8
13 6
11 5
16 15
4 5
13 11
2 14
2 16
4 2
14 12
1 2
11 16
12 1
15 13
10 12

8 7
1 5
2 5
4 2
8 3
3 4
2 7
1 6

12 29
5 4
9 3
6 4
8 5
7 2
10 3
4 2
5 12
11 6
10 8
10 6
9 11
6 5
11 5
8 2
9 1
10 4
11 3
4 3
1 6
1 8
6 2
12 11
11 4
2 3
3 5
1 7
9 7
3 8

15 16
3 15
2 6
13 3
11 14
12 8
12 1
8 13
9 15
8 10
13 5
12 11
9 11
11 8
7 8
13 14
14 3

11 14
10 9
6 10
6 5
9 8
2 6
1 11
10 4
6 1
8 3
1 9
4 9
4 7
1 4
2 5

10 0

17 3
13 2
14 5
11 5

9 5
7 4
1 3
4 2
6 4
2 7

6 13
5 6
5 2
2 3
2 4
6 2
5 3
4 6
6 3
4 5
4 1
1 3
1 5
1 2

17 13
14 15
17 6
17 1
9 14
4 13
4 14
15 6
11 9
3 6
8 1
5 10
5 14
3 17

8 22
7 3
7 2
1 5
4 6
5 4
8 5
6 2
4 7
3 1
3 5
4 2
5 6
6 3
1 7
5 2
3 8
6 1
8 6
8 1
8 2
2 3
4 3

6 0

14 7
11 8
7 14
2 7
10 12
5 7
1 4
9 1

8 4
1 5
5 7
4 8
3 8

8 7
3 4
4 1
1 2
7 3
3 6
3 1
7 5

3 1
1 3

17 24
8 1
9 14
17 12
10 15
14 17
16 3
16 4
1 16
14 11
5 9
15 12
7 12
4 15
6 14
4 3
8 4
6 4
1 7
6 16
8 12
8 16
13 14
13 17
3 11

17 1
5 6

7 7
7 2
6 7
2 6
3 2
7 1
6 1
1 3

8 11
4 8
8 1
7 8
7 1
2 6
3 4
4 1
6 1
3 5
7 3
1 5

13 13
5 8
2 7
11 3
12 9
5 6
5 12
7 3
8 9
5 2
9 10
3 4
13 10
6 2

6 2
6 5
5 3

6 0

11 1
6 8

16 28
3 8
7 14
6 12
2 13
4 8
5 11
8 1
5 10
12 13
9 3
7 11
4 5
6 1
14 15
3 11
16 13
14 16
3 7
11 8
7 10
1 12
2 12
9 6
9 11
2 8
5 13
10 14
14 11

12 15
9 10
2 12
6 3
7 5
12 8
8 4
4 1
8 2
11 9
12 1
2 9
11 4
6 7
10 6
1 10

16 21
14 11
2 10
10 9
10 16
5 9
10 4
14 16
3 7
9 11
12 6
3 2
9 1
1 2
11 7
6 11
3 4
8 10
10 12
2 5
6 1
7 2

3 2
3 1
1 2

8 20
3 8
1 4
7 2
6 2
6 1
1 7
1 3
4 7
5 1
4 2
4 5
7 5
4 6
6 5
2 1
5 8
2 5
3 5
8 7
3 4

14 14
10 11
9 10
7 13
6 1
12 7
3 14
11 4
8 13
4 1
8 10
2 5
14 6
9 11
2 12

4 5
4 1
1 2
3 2
4 2
3 4

2 0

4 5
1 2
2 3
3 1
2 4
1 4

12 15
12 4
6 2
5 9
11 1
1 10
1 5
10 2
7 11
12 9
5 11
4 6
9 6
6 5
6 10
3 7

17 11
11 6
3 17
9 4
13 15
15 14
11 9
4 3
2 1
12 3
6 5
17 11

14 32
9 8
5 9
3 14
11 4
9 11
4 6
2 10
9 3
2 8
6 11
5 4
3 7
3 6
8 1
7 10
4 14
1 2
11 14
6 8
9 14
14 6
9 7
12 9
13 12
14 2
4 2
7 12
4 13
10 6
8 7
1 10
2 7

15 38
4 9
1 14
3 11
2 4
4 15
6 12
4 7
12 2
3 4
15 3
2 8
8 10
11 2
1 15
15 2
15 11
6 8
9 14
3 6
4 14
7 6
8 1
10 11
5 4
6 2
13 8
8 9
15 8
13 15
2 9
11 7
13 11
10 3
13 7
14 8
5 6
12 15
3 7

4 4
2 3
3 4
1 4
4 2

11 35
7 11
10 5
1 3
6 4
5 8
10 1
3 5
7 2
4 11
9 7
9 8
5 9
8 7
5 6
4 10
8 11
3 7
9 2
6 10
11 10
8 6
11 2
7 6
1 6
5 4
9 1
4 7
2 10
5 2
1 8
1 5
10 3
6 9
7 10
3 8

9 26
7 9
3 1
8 4
8 5
1 4
8 6
5 2
9 1
3 7
1 7
3 5
9 5
2 4
6 5
5 7
1 6
8 7
1 8
8 2
2 1
5 4
1 5
2 6
4 7
9 2
4 3

9 15
7 9
1 3
8 4
6 2
1 5
7 4
2 4
1 2
9 6
2 5
7 8
3 9
4 6
2 9
9 5

6 9
2 1
6 2
6 3
2 4
5 6
5 4
5 1
1 4
3 1

15 4
8 5
7 15
13 3
2 11

15 32
1 14
15 14
12 11
7 9
3 13
14 11
14 5
7 3
14 13
4 14
13 5
14 10
13 6
1 4
12 1
10 6
8 14
1 6
12 15
11 13
7 2
4 10
1 10
1 2
7 14
9 5
12 7
12 13
4 6
11 10
7 4
2 12

13 17
2 9
2 7
11 13
8 10
7 11
13 3
3 10
10 5
9 1
7 13
8 12
5 6
5 12
11 12
7 8
2 13
1 10

14 20
13 1
7 11
14 8
6 4
10 12
1 4
3 1
2 5
4 13
4 11
4 12
2 8
7 5
10 3
1 11
2 11
3 2
6 11
9 12
14 6

6 9
1 5
2 3
2 4
4 6
5 2
1 2
6 2
6 5
3 4

10 31
5 3
10 7
2 9
6 5
4 1
6 9
5 8
4 5
6 10
3 9
2 3
1 7
8 4
6 2
3 8
10 1
10 5
3 10
9 7
1 8
9 4
10 2
8 6
9 10
8 9
2 4
3 1
7 8
8 10
7 5
6 4

10 13
1 9
9 4
4 6
9 3
8 1
5 9
8 7
7 9
5 6
3 4
1 7
4 8
1 3

11 24
1 11
2 4
1 6
10 7
10 9
3 11
3 1
10 8
4 11
4 7
8 6
10 3
8 11
10 6
5 3
5 8
11 7
11 5
11 9
6 7
2 1
4 5
6 9
5 7

9 11
2 6
5 7
6 8
2 8
7 6
8 5
4 9
5 6
7 9
4 2
5 4

9 21
9 7
1 7
4 8
6 5
4 7
3 8
1 8
8 9
3 1
5 2
1 9
4 5
6 2
4 6
1 4
2 9
1 6
9 6
4 2
3 5
3 4

2 0

15 35
15 7
13 2
15 12
7 11
4 3
1 6
13 9
7 8
12 14
14 5
8 11
7 1
1 10
11 13
3 9
14 8
7 6
4 9
7 10
10 4
1 4
8 12
5 3
1 9
1 14
1 13
3 8
8 2
3 13
7 3
8 1
15 13
6 5
1 2
2 6

11 20
1 8
6 3
9 1
9 6
5 7
8 3
6 1
10 1
8 10
9 11
10 4
1 7
2 4
2 5
11 10
11 2
10 9
11 7
3 10
10 5

3 0

6 9
4 2
1 5
5 3
1 2
3 6
6 5
1 6
2 6
5 2

14 17
9 8
9 14
1 4
6 3
7 9
9 6
14 2
3 10
5 13
14 10
14 6
1 5
11 12
2 13
10 5
6 8
12 10

2 0

7 14
1 3
6 5
3 4
4 1
6 2
5 4
3 5
6 7
4 6
7 5
7 1
1 5
2 3
7 3

8 2
8 4
5 4

16 36
14 3
3 16
14 12
2 6
11 1
16 7
3 11
10 1
14 15
9 5
12 16
11 15
2 11
6 14
2 9
4 3
8 15
15 5
13 15
12 6
11 12
11 4
16 5
2 3
1 5
7 13
2 8
6 8
12 10
12 5
3 7
4 8
13 1
12 15
2 7
12 7

4 0

12 12
8 5
2 1
2 9
10 2
7 9
9 11
10 11
1 7
10 1
9 8
1 8
8 3

12 28
11 10
9 5
10 4
4 11
12 3
11 1
9 1
2 5
6 10
5 3
10 2
8 5
7 12
9 6
1 7
8 4
10 8
10 9
5 12
7 3
11 7
7 8
3 11
11 9
6 12
7 6
2 8
11 5

8 14
3 5
4 1
6 1
8 7
4 7
8 4
5 2
2 1
1 5
5 7
6 5
2 3
5 8
2 6

9 3
7 6
1 4
8 5

7 16
3 7
7 5
6 3
2 4
7 4
5 3
2 6
4 6
3 2
3 4
7 1
1 3
2 7
5 1
2 1
6 1

12 27
7 1
11 7
3 4
3 7
6 1
2 7
9 5
5 6
8 12
6 4
6 8
2 11
11 8
6 11
3 6
12 5
8 5
12 2
9 7
12 4
6 7
7 4
1 3
10 6
1 9
10 3
11 3

8 13
3 1
8 6
7 5
3 7
2 5
8 2
3 2
8 5
6 5
1 5
2 7
1 6
7 6

12 4
1 4
7 2
11 5
9 6

12 17
6 7
3 12
12 6
11 1
12 10
9 10
12 5
10 11
8 1
3 8
3 1
2 7
3 9
6 4
3 11
9 8
11 12

16 20
8 2
7 11
9 7
10 4
6 5
11 5
14 8
2 16
9 6
12 8
7 16
15 10
11 3
14 6
12 2
9 15
12 14
2 9
14 16
10 7

7 3
2 7
5 1
2 6

14 21
3 10
9 12
2 11
3 12
12 11
1 5
1 10
3 9
11 9
10 5
11 14
1 4
14 6
10 8
5 13
7 2
3 2
4 5
2 13
1 6
9 2

13 7
13 2
11 9
11 3
5 9
7 2
6 2
3 12

11 24
7 3
10 9
10 5
6 11
10 7
9 8
6 8
4 3
9 1
7 4
4 2
2 3
11 2
3 1
7 6
10 1
9 6
1 7
3 8
2 9
4 6
8 11
2 5
11 4

15 17
1 8
2 14
2 5
12 4
1 3
4 3
3 8
3 13
12 10
6 2
7 15
4 8
7 8
13 2
9 10
15 13
10 2

2 0

8 5
1 3
8 3
6 5
5 2
1 6

10 12
1 6
4 5
2 4
6 2
7 8
10 4
4 7
8 6
5 8
6 9
3 2
4 8

12 28
10 4
11 2
8 3
5 7
8 4
5 10
8 2
6 1
6 7
9 11
5 2
8 12
1 7
1 11
5 8
4 5
3 12
5 12
12 2
9 6
8 11
10 1
9 4
1 8
9 7
7 2
10 8
11 12

10 29
3 1
8 5
4 10
6 5
3 10
10 1
10 6
2 10
8 9
7 6
3 5
5 10
8 7
6 3
8 6
1 8
9 6
9 10
9 7
8 4
4 7
8 2
3 4
5 1
6 2
4 2
2 3
8 10
1 6

13 6
13 12
8 7
7 10
5 7
8 2
9 2

10 21
6 5
2 7
10 9
9 5
2 8
5 1
5 8
1 7
2 4
2 10
6 4
8 6
2 1
10 1
7 10
6 1
4 1
4 3
4 5
9 8
2 5

7 13
2 4
3 7
7 5
5 3
5 6
7 1
2 5
1 3
4 6
6 7
6 2
7 2
4 3

7 15
6 4
2 6
6 3
5 6
1 5
4 5
3 5
6 7
7 5
1 2
2 3
2 7
4 2
4 1
7 3

4 3
4 3
1 3
4 1

7 13
3 6
1 3
4 2
2 7
5 6
2 6
3 4
7 1
2 1
2 5
1 5
5 4
6 7

2 0

13 33
6 7
6 11
1 4
4 3
12 6
5 2
12 9
13 8
7 11
4 6
8 6
7 1
11 3
3 5
9 13
11 2
6 10
10 8
9 2
10 7
9 4
11 1
5 7
6 1
13 10
3 12
2 4
2 12
13 2
8 5
3 1
3 10
2 3

10 18
10 2
2 5
6 8
6 7
8 10
1 10
7 1
9 3
6 3
8 4
5 6
6 2
5 3
1 5
5 7
8 7
4 2
5 9

17 0

10 7
9 7
1 8
3 6
1 9
2 8
10 6
2 6

13 13
7 5
12 7
4 9
11 9
11 7
1 3
5 1
11 2
1 10
2 4
3 10
9 7
2 7

6 0

11 4
2 3
10 11
7 1
4 10

8 11
6 5
3 4
6 1
5 8
6 3
7 5
7 2
1 7
5 2
2 3
1 8

15 18
11 13
13 10
6 1
6 11
3 11
3 10
2 12
5 13
10 2
11 8
5 11
9 13
13 8
6 13
15 5
9 7
4 15
3 4

target1.txt

10
3 4 5 6 7 8 9 10 11 12

target2.txt

8
2 5 6 7 9 10 11 12
6
3 5 10 13 14 16
5
4 5 6 7 8
4
6 8 9 12
8
4 5 6 7 10 12 14 15
5
5 7 8 10 11
10
1 2 3 4 5 6 7 8 9 10
15
1 3 4 6 7 8 9 10 11 12 13 14 15 16 17
6
3 5 6 7 8 9
2
3 4
10
2 7 8 10 11 12 13 15 16 17
2
7 8
6
1 2 3 4 5 6
10
2 3 4 5 6 9 11 12 13 14
6
1 2 3 4 6 7
5
2 4 6 7 8
2
2 3
8
2 6 7 8 9 11 15 17
16
1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17
4
3 4 5 7
4
4 5 6 7
8
1 4 6 7 8 11 12 13
5
1 2 3 4 6
6
1 2 3 4 5 6
10
1 2 3 4 5 7 8 9 10 11
7
5 7 8 9 12 15 16
5
4 5 6 9 12
9
1 4 5 8 11 12 13 15 16
2
2 3
3
3 6 7
7
3 4 5 6 10 12 13
2
1 3
2
1 2
2
3 4
6
3 4 8 9 10 11
11
2 6 7 8 9 10 12 13 14 16 17
6
3 5 8 10 11 13
6
1 5 9 10 12 13
2
1 3
3
3 9 11
3
4 6 9
4
3 5 6 8
3
2 3 5
11
1 4 6 8 9 10 11 12 13 14 15
7
2 3 6 8 9 11 15
7
1 2 3 4 6 8 11
6
6 7 8 9 10 13
3
1 3 6
3
3 6 7
5
2 6 8 9 10
5
2 3 7 8 9
5
1 3 4 7 8
3
6 7 8
2
1 2
6
6 9 10 11 14 15
5
4 5 6 8 11
3
1 2 3
3
1 3 4
7
3 4 7 8 12 13 14
2
1 2
3
2 4 7
7
1 2 3 5 6 7 8
7
8 9 10 11 13 14 16
4
1 2 3 4
8
2 3 4 5 6 7 11 12
5
1 2 3 4 6
3
3 6 8
6
2 3 4 7 8 9
2
6 7
5
2 4 8 9 10
4
1 4 7 8
8
3 4 7 8 9 10 11 12
5
4 5 7 9 11
9
1 2 3 4 5 7 13 14 15
5
3 4 5 6 7
7
3 4 6 7 8 11 13
10
1 4 5 6 7 8 10 11 12 13
4
5 7 9 11
9
1 5 6 7 9 11 12 13 14
2
1 2
5
2 4 6 7 8
6
1 3 5 7 9 10
4
3 7 10 11
3
4 5 9
10
1 3 4 5 6 8 9 10 11 13
4
3 6 7 9
3
1 4 5
2
4 7
2
2 4
3
3 5 7
2
1 2
5
4 5 11 12 13
4
4 7 9 10
17
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
7
1 2 3 4 5 7 10
8
4 5 6 8 10 11 12 13
6
1 2 3 4 5 6
8
3 4 5 6 7 8 9 11
4
4 6 7 8
8
4 5 6 8 9 10 12 14