Codingame puzzle walkthough: Moves in a maze

First, the puzzle link if you didn’t complete it already, I encourage you to finish it first!

Parsing

First step, parsing the input. I store the width, the height and make the grid.

When I find the S indicating the Start, I replace it with a 0 (for the distance) and save this location in a queue.

We’ll use the queue like in a Breadth-First Search to find the shortest path.

	var w, h int
	scanner.Scan()
	fmt.Sscan(scanner.Text(), &w, &h)

	grid := make([][]string, h)
	queue := make([][]int, 1)

	for i := 0; i < h; i++ {
		row := make([]stringg, w)
		scanner.Scan()
		txt := scanner.Text()
		for j, c := range strings.Split(txt, "") {
			if c == "S" {
				queue[0] = []int{i, j}
				row[j] = "0"
				continue
			}
			row[j] = c
		}
		grid[i] = row
	}

The Search

Now for the actual algo.

For each item in the queue:

• check if this cell was already visited
• check the four neighbours (the maze being periodic, if we go out one way, we come back on the other side if there is no wall)
• check that the neigbour cell was not already reached from another cell
• set the distance for the neighbour cell, which is current cell distance + 1
• add the neigbour cell to the queue

	visited := make(map[string]bool)
	directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

	for len(queue) > 0 {
		item := queue[0]
		queue = queue[1:]

		if _, ok := visited[fmt.Sprintf("%s-%s", strconv.Itoa(item[0]), strconv.Itoa(item[1]))]; ok {
			continue
		}
		visited[fmt.Sprintf("%s-%s", strconv.Itoa(item[0]), strconv.Itoa(item[1]))] = true

		val, _ := strconv.Atoi(grid[item[0]][item[1]])
		for _, dir := range directions {
			newI := (item[0] + h + dir[0]) % h
			newJ := (item[1] + w + dir[1]) % w

			if grid[newI][newJ] == "." {
				grid[newI][newJ] = strconv.Itoa(val + 1)
				queue = append(queue, []int{newI, newJ})
			}
		}
	}

At first I had 4 if elses to handle the exploration, I replaced them by the directions array.

The periodicity of the maze is handled by this line newI := (item[0] + h + dir[0]) % h.

Output

To output the maze filled, we iterate through it, and if the cell is a number above 9, we convert it to a letter.

The letter A correspond the the rune 65. So string(rune(55 + val)) makes sure that if val is 10, A will be written.

	for _, row := range grid {
		for _, c := range row {
			val, err := strconv.Atoi(c)
			if err != nil || val <= 9 {
				fmt.Print(c)
				continue
			}
			fmt.Print(string(rune(55 + val)))
		}
		fmt.Println()
	}

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 (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]byte, 1000000), 1000000)

	var w, h int
	scanner.Scan()
	fmt.Sscan(scanner.Text(), &w, &h)

	grid := make([][]string, h)
	queue := make([][]int, 1)

	for i := 0; i < h; i++ {
		row := make([]string, w)
		scanner.Scan()
		txt := scanner.Text()
		for j, c := range strings.Split(txt, "") {
			if c == "S" {
				queue[0] = []int{i, j}
				row[j] = "0"
				continue
			}
			row[j] = c
		}
		grid[i] = row
	}

	visited := make(map[string]bool)
	directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

	for len(queue) > 0 {
		item := queue[0]
		queue = queue[1:]

		if _, ok := visited[fmt.Sprintf("%s-%s", strconv.Itoa(item[0]), strconv.Itoa(item[1]))]; ok {
			continue
		}
		visited[fmt.Sprintf("%s-%s", strconv.Itoa(item[0]), strconv.Itoa(item[1]))] = true

		val, _ := strconv.Atoi(grid[item[0]][item[1]])
		for _, dir := range directions {
			newI := (item[0] + h + dir[0]) % h
			newJ := (item[1] + w + dir[1]) % w

			if grid[newI][newJ] == "." {
				grid[newI][newJ] = strconv.Itoa(val + 1)
				queue = append(queue, []int{newI, newJ})
			}
		}
	}

	for _, row := range grid {
		for _, c := range row {
			val, err := strconv.Atoi(c)
			if err != nil || val <= 9 {
				fmt.Print(c)
				continue
			}
			fmt.Print(string(rune(55 + val)))
		}
		fmt.Println()
	}
}