Codingame puzzle walkthough: abcdefghijklmnopqrstuvwxyz

My implementation for the codingame puzzle: abcdefghijklmnopqrstuvwxyz in golang

September 2024

Find the puzzle on Codingame: Puzzle link.

Parsing

Classic puzzle start, store the input in a grid! I’m also saving the locations of all the a to know where to start the searches later on.

	grid := make([][]string, n)
	starts := make([]Coord, 0)

	for i := 0; i < n; i++ {
		var m string
		fmt.Scan(&m)
		row := make([]string, len(m))
		for j, val := range strings.Split(m, "") {
			row[j] = val
			if val == "a" {
				starts = append(starts, Coord{i, j})
			}
		}
		grid[i] = row
	}

Checking for a loop

Then for each position in the starts array, we can try to do a solve. A solve only stops when we find arrive on a z.

We go in each direction around the location, and if we find the letter after the one we’re in currently, we launch a new solve in this location.

We’re also saving the path we’re taking to simplify the output.

for _, val := range starts {
    match, path := solve(grid, val, []Coord{})
    // [...]
}

func solve(grid [][]string, start Coord, path []Coord) (bool, []Coord) {
	path = append(path, Coord{start.X, start.Y})
	if grid[start.X][start.Y] == "z" {
		return true, path
	}
	
	target := string(grid[start.X][start.Y][0] + 1)
	directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
	for _, direction := range directions {
		newX, newY := start.X  + direction[0], start.Y  + direction[1]

		if newX >= 0 && newX < len(grid) && newY >= 0 && newY < len(grid[0]) && grid[newX][newY] == target {
			match, newPath := solve(grid, Coord{newX, newY}, path)
			if match {
				return true, newPath
			}
		}
	}

	return false, path
}

Output

When we finally find the loop, we iterate through the grid a last time, and for each position we check if it’s the path that represent the loops. If it is, we print it correctly. If it isn’t, we print -.

And that’s it!

	for _, val := range starts {
		match, path := solve(grid, val, []Coord{})
		if match {
			for i := range grid {
			CELL:
				for j := range grid[i] {
					for _, pos := range path {
						if pos.X == i && pos.Y == j {
							fmt.Print(grid[pos.X][pos.Y])
							continue CELL
						}
					}
					fmt.Print("-")
				}
				fmt.Println()
			}
			break
		}
	}

Complete solution

If you have any questions or suggestions, send me a message at me@krayorn.com or a DM on Twitter/X

package main

import (
	"fmt"
	"strings"
)

type Coord struct {X, Y int}

func main() {
	var n int
	fmt.Scan(&n)

	grid := make([][]string, n)
	starts := make([]Coord, 0)

	for i := 0; i < n; i++ {
		var m string
		fmt.Scan(&m)
		row := make([]string, len(m))
		for j, val := range strings.Split(m, "") {
			row[j] = val
			if val == "a" {
				starts = append(starts, Coord{i, j})
			}
		}
		grid[i] = row
	}

	for _, val := range starts {
		match, path := solve(grid, val, []Coord{})
		if match {
			for i := range grid {
			CELL:
				for j := range grid[i] {
					for _, pos := range path {
						if pos.X == i && pos.Y == j {
							fmt.Print(grid[pos.X][pos.Y])
							continue CELL
						}
					}
					fmt.Print("-")
				}
				fmt.Println()
			}
			break
		}
	}
}

func solve(grid [][]string, start Coord, path []Coord) (bool, []Coord) {
	path = append(path, Coord{start.X, start.Y})
	if grid[start.X][start.Y] == "z" {
		return true, path
	}
	
	target := string(grid[start.X][start.Y][0] + 1)
	directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
	for _, direction := range directions {
		newX, newY := start.X  + direction[0], start.Y  + direction[1]

		if newX >= 0 && newX < len(grid) && newY >= 0 && newY < len(grid[0]) && grid[newX][newY] == target {
			match, newPath := solve(grid, Coord{newX, newY}, path)
			if match {
				return true, newPath
			}
		}
	}

	return false, path
}

go