Finding the shortest path between two keys on a keyboard

main.go

package main

import (
	"fmt"
	"strings"
)

type Key struct {
	val                   rune
	left, right, up, down *Key
}

func (k *Key) Goto(other *Key) []string {
	type back struct {
		*Key
		back *back
		dir  string
	}

	seen := make(map[rune]bool)
	q := []*back{{
		Key:  k,
		back: nil,
		dir:  "",
	}}

	var curr *back
	max := 26 * 26 // there's probably a better way to calculate a reasonable upper bound
	i := 0
	for len(q) > 0 {
		if i == max {
			panic("max iterations reached")
		}
		i++

		// fmt.Println("there are", len(q), "elements in queue")

		curr, q = q[0], q[1:]
		if _, found := seen[curr.val]; found {
			// We've already seen this key, no point in revisiting it
			continue
		}
		if curr.val == other.val {
			// We found it! break out of the loop
			break
		}

		// add the current key to the seen map, so we don't visit it again
		seen[curr.val] = true

		if curr.up != nil {
			if _, found := seen[curr.up.val]; !found {
				q = append(q, &back{
					Key:  curr.up,
					back: curr,
					dir:  "up",
				})
			}
		}
		if curr.down != nil {
			if _, found := seen[curr.down.val]; !found {
				q = append(q, &back{
					Key:  curr.down,
					back: curr,
					dir:  "down",
				})
			}
		}
		if curr.left != nil {
			if _, found := seen[curr.left.val]; !found {
				q = append(q, &back{
					Key:  curr.left,
					back: curr,
					dir:  "left",
				})
			}
		}
		if curr.right != nil {
			if _, found := seen[curr.right.val]; !found {
				q = append(q, &back{
					Key:  curr.right,
					back: curr,
					dir:  "right",
				})
			}
		}
	}

	// Move from the target key up the chain, appending the direction every step
	dir := []string{}
	for curr.back != nil {
		dir = append([]string{curr.dir}, dir...)
		curr = curr.back
	}

	return dir
}

func main() {
	chars := []rune{
		'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
		'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
		'u', 'v', 'w', 'x', 'y', 'z',
	}

	keymap := make(map[rune]*Key)
	for _, c := range chars {
		keymap[c] = &Key{val: c}
	}

	keymap['a'].up = keymap['q']
	keymap['a'].down = keymap['z']
	keymap['a'].right = keymap['s']

	keymap['b'].up = keymap['g'] // is this right? whatever, we'll assume it is
	keymap['b'].left = keymap['v']
	keymap['b'].right = keymap['n']

	keymap['c'].up = keymap['d']
	keymap['c'].left = keymap['x']
	keymap['c'].right = keymap['v']

	keymap['d'].up = keymap['e']
	keymap['d'].down = keymap['c']
	keymap['d'].left = keymap['s']
	keymap['d'].right = keymap['f']

	keymap['e'].down = keymap['d']
	keymap['e'].left = keymap['w']
	keymap['e'].right = keymap['r']

	keymap['f'].up = keymap['r']
	keymap['f'].down = keymap['v']
	keymap['f'].left = keymap['d']
	keymap['f'].right = keymap['g']

	keymap['g'].up = keymap['t']
	keymap['g'].down = keymap['b']
	keymap['g'].left = keymap['f']
	keymap['g'].right = keymap['h']

	keymap['h'].up = keymap['y']
	keymap['h'].down = keymap['n']
	keymap['h'].left = keymap['g']
	keymap['h'].right = keymap['j']

	keymap['i'].down = keymap['k']
	keymap['i'].left = keymap['u']
	keymap['i'].right = keymap['o']

	keymap['j'].up = keymap['u']
	keymap['j'].down = keymap['m']
	keymap['j'].left = keymap['h']
	keymap['j'].right = keymap['k']

	keymap['k'].up = keymap['i']
	keymap['k'].left = keymap['j']
	keymap['k'].right = keymap['l']

	keymap['l'].up = keymap['o']
	keymap['l'].left = keymap['k']

	keymap['m'].up = keymap['j']
	keymap['m'].left = keymap['n']

	keymap['n'].up = keymap['h']
	keymap['n'].left = keymap['b']
	keymap['n'].right = keymap['m']

	keymap['o'].down = keymap['l']
	keymap['o'].left = keymap['i']
	keymap['o'].right = keymap['p']

	keymap['p'].left = keymap['o']

	keymap['q'].down = keymap['a']
	keymap['q'].right = keymap['w']

	keymap['r'].down = keymap['f']
	keymap['r'].left = keymap['e']
	keymap['r'].right = keymap['t']

	keymap['s'].up = keymap['w']
	keymap['s'].down = keymap['x']
	keymap['s'].left = keymap['a']
	keymap['s'].right = keymap['d']

	keymap['t'].down = keymap['g']
	keymap['t'].left = keymap['r']
	keymap['t'].right = keymap['y']

	keymap['u'].down = keymap['j']
	keymap['u'].left = keymap['y']
	keymap['u'].right = keymap['i']

	keymap['v'].up = keymap['f']
	keymap['v'].left = keymap['c']
	keymap['v'].right = keymap['b']

	keymap['w'].down = keymap['s']
	keymap['w'].left = keymap['q']
	keymap['w'].right = keymap['e']

	keymap['x'].up = keymap['s']
	keymap['x'].left = keymap['z']
	keymap['x'].right = keymap['c']

	keymap['y'].down = keymap['h']
	keymap['y'].left = keymap['t']
	keymap['y'].right = keymap['u']

	keymap['z'].up = keymap['a']
	keymap['z'].right = keymap['x']

	dirs := keymap['s'].Goto(keymap['o'])
	fmt.Println(strings.Join(dirs, ", "))
}