Wednesday, March 7, 2012

Go Snail Go

I came across a post which solves what it calls the "snail" problem in Go. We've seen some very pretty examples of the same thing in Python here.

This is the output of my version in Go for S = 9.

 1  2  3  4  5  6  7  8  9
32 33 34 35 36 37 38 39 10
31 56 57 58 59 60 61 40 11
30 55 72 73 74 75 62 41 12
29 54 71 80 81 76 63 42 13
28 53 70 79 78 77 64 43 14
27 52 69 68 67 66 65 44 15
26 51 50 49 48 47 46 45 16
25 24 23 22 21 20 19 18 17

You can see why he called it the snail. Anyway, I noticed a chance to use a goroutine for this problem. In any cycle starting with [left] followed by [down] we go n steps in each direction, then n+1 steps in the [right,up] directions. In the code below, we obtain these step values from a Go channel.

A couple of other Go-like things about this code. We stash the 2D array (as a 1D array with a shape parameter) in a struct, and then attach a func to that struct to pretty print it. The details of the pprint function could doubtless be improved---I'm not too swift with formatting. The other Goish thing is to modify both the row and column indices at once, returning what we'd call in Python a tuple value from the step function.

Fun.

package main

import (
    "fmt"
    "os"
    "strings"
)

func dist(ch chan int) {
    var a int = 1
    for { 
        ch <- a
        ch <-a
        a++ 
    }
}

var m = map[string]string{"L":"D","D":"R","R":"U","U":"L"}

func step(r, c int, dir string)(rn, cn int) {
    switch dir {
        case "L": { c-- }
        case "D": { r++ } 
        case "R": { c++ }
        case "U": { r-- }
    }
    return r,c
}

type A struct { arr []int;  SZ int }
func (a *A) pprint() {
    d := a.SZ
    for i:= 0; i < len(a.arr); i += d {
        S := []string{}
        for _,f := range a.arr[i:i+d] {
            S = append(S,fmt.Sprintf("%2d", f))
        }
        fmt.Println(strings.Join(S," "))
    }
}

func main() {
    S := 9
    if S%2 != 1 { os.Exit(1) }
    N := S*S
    a := A{make([]int,N), S}
    ch := make(chan int)
    go dist(ch)
    dir := "L"
    var r, c int;  r = S/2 + 1;  c = r
    n := <- ch
    for {
        for i := 0; i < n; i++ {
            //fmt.Println(r, c, N)
            a.arr[(r-1)*S + (c-1)] = N
            N--
            if N == 0 { break }
            r,c = step(r, c, dir)
        }
        n = <- ch
        dir = m[dir]
        if N == 0 { break }
    }
    a.pprint()
}