color-it

Implementation for the "color-it" contest.

Building

Build the binary using the Go SDK (preferred)

# Install the application dependencies.
go mod download

# Build the application.
go build

# Test it.
./color-it samples/30_30_3-1.csv

Build a Docker image

# Build the Docker image
docker build -t color-it .

# Test it.
docker run --rm \
  -v $(pwd)/samples/30_30_3-1.csv:/data/input.csv \
  color-it /data/input.csv

Usage

The only required parameter to run the program is the input CSV file to process; it is passed as a positional argument. Some other optional arguments can be provided to control the program behavior but the default values should be used for the contest.

Usage of ./color-it:
  -check-square
        Check whether the board is a square after loading it (default true)
  -debug
        Enable the debug logs
  -impl string
        Name of the algorithm implementation to execute (default "deep-search")
  -output string
        File path in which to write the solution found
  -timeout int
        Timeout in seconds of the execution (default 115)

Output

The best solution found is printed on stdout, one step per line at the end of the program execution, for example:

1
2
0
2

Results

Sample	Deep search
12_12_4-1.csv	0m0,255s nb-steps=12 solution=[1,0,3,1,3,0,1,0,2,3,1,0]
12_12_5-1.csv	0m0,391s nb-steps=14 solution=[0,4,3,4,1,2,3,4,2,0,3,4,2,1]
12_12_6-1.csv	1m29,299s nb-steps=19 solution=[0,2,4,5,3,1,0,5,2,3,0,5,4,2,3,5,4,0,1]
15_15_3-1.csv	0m0,042s nb-steps=9 solution=[1,2,0,1,0,2,0,1,2]
15_15_3-2.csv	0m0,045s nb-steps=9 solution=[2,0,1,0,2,0,1,2,0]
15_15_4-1.csv	0m4,270s nb-steps=16 solution=[3,2,0,1,3,1,0,1,3,0,2,3,1,2,0,3]
15_15_5-1.csv	1m19,528s nb-steps=17 solution=[3,0,2,3,4,1,2,1,3,0,2,4,0,1,3,2,4]
15_15_6-1.csv	timeout nb-steps=24 solution=[...]
20_20_3-1.csv	0m0,049ss nb-steps=11 solution=[0,2,1,2,0,1,2,1,0,2,1]
20_20_4-1.csv	1m27,674s nb-steps=19 solution=[3,1,0,1,3,2,3,0,2,1,0,3,1,2,3,1,0,2,3]
20_20_5-1.csv	timeout nb-steps=26 solution=[...]
20_20_6-1.csv	timeout nb-steps=34 solution=[...]
30_30_3-1.csv	0m4,027s nb-steps=19 solution=[1,2,0,2,1,2,0,1,2,0,1,2,1,2,1,0,2,1,0]
30_30_4-1.csv	timeout nb-steps=28 solution=[...]
30_30_5-1.csv	timeout nb-steps=38 solution=
30_30_6-1.csv	timeout nb-steps=51 solution=[...]

Profiling

Use go test benchmark feature to generate the profiling files:

go test -cpuprofile cpu.prof -memprofile mem.prof -bench=. -benchtime=15s

Use the pprof tool to visualize the profiling results with pprof:

go tool pprof -http=":" cpu.prof

TODO

Parallelize the deep search implementation using multiple Goroutines.

Try new implementation:

1. start from the initial solution (of length L)
2. start from level L-2 and test the other colors to see if there is a better solution at this level
3. go upward until reaching the tree root