02 Nov 2016, 00:00

How to do Google Sign-In with Go - Part 2

Intro

Hi Folks.

This is a follow up on my previous post about Google Sign-In. In this post we will discover what to do with the information retrieved in the first encounter, which you can find here: Google Sign-In Part 1.

Forewords

The Project

Everything I did in the first post, and that I’m going to do in this example, can be found in this project: Google-OAuth-Go-Sample.

Just to recap, we left off previously on the point where we successfully obtained information about the user, with a secure token and a session initiated with them. Google nicely enough provided us with some details which we can use. This information was in JSON format and looked something like this:

{
  "sub": "1111111111111111111111",
  "name": "Your Name",
  "given_name": "Your",
  "family_name": "Name",
  "profile": "https://plus.google.com/1111111111111111111111",
  "picture": "https://lh3.googleusercontent.com/asdfadsf/AAAAAAAAAAI/Aasdfads/Xasdfasdfs/photo.jpg",
  "email": "your@gmail.com",
  "email_verified": true,
  "gender": "male"
}

In my example, to keep things simple, I will use the email address since that has to be unique in the land of Google. You could assign an ID to the user, and you could complicate things even further, but my goal is not to write an academic paper about cryptography here.

Implementation

Making something useful out of the data

In order for the app to recognise a user it must save some data about the user. I’m doing that in MongoDB right now, but that could be any form of persistence layer, like, SQLite3, BoltDB, PostgresDB, etc.

After successful user authorization

Once the user used google to provide us with sufficient information about him/herself, we can retrieve data about that user from our records. The data could be anything that is linked to our unique identifier like: Character Profile, Player Information, Status, Last Logged-In, etcetc. For this, there are two things that need to happen after authorization: Save/Load user information and initiate a session.

The session can be in the form of a cookie, or a Redis storage, or URL re-writing. I’m choosing a cookie here.

Save / Load user information

All I’m doing is a simple, returning / new user handling. The concept is simple. If the email isn’t saved, we save it. If it’s saved, we set a logic to our page render to greet the returning user.

In the AuthHandler I’m doing the following:

...
seen := false
db := database.MongoDBConnection{}
if _, mongoErr := db.LoadUser(u.Email); mongoErr == nil {
    seen = true
} else {
    err = db.SaveUser(&u)
    if err != nil {
        log.Println(err)
        c.HTML(http.StatusBadRequest, "error.tmpl", gin.H{"message": "Error while saving user. Please try again."})
        return
    }
}
c.HTML(http.StatusOK, "battle.tmpl", gin.H{"email": u.Email, "seen": seen})
...

Let’s break this down a bit. There is a db connection here, which calls a function that either returns an error, or it doesn’t. If it doesn’t, that means we have our user. If it does, it means we have to save the user. This is a very simple case (disregard for now, that the error could be something else as well (If you can’t get passed that, you could type check the error or check if the returned record contains the requested user information instead of checking for an error.)).

The template is than rendered depending on the seen boolean like this:

<!DOCTYPE html>
<link rel="icon"
      type="image/png"
      href="/img/favicon.ico" />
<html>
  <head>
    <link rel="stylesheet" href="/css/main.css">
  </head>
  <body>
    {{if .seen}}
        <h1>Welcome back to the battlefield '{{ .email }}'.</h1>
    {{else}}
        <h1>Welcome to the battlefield '{{ .email }}'.</h1>
    {{end}}
  </body>
</html>

You can see here, that if seen is true the header message will say: “Welcome back…“.

Initiating a session

When the user is successfully authenticated, we activate a session so that the user can access pages that require authorization. Here, I have to mention that I’m using Gin, so restricted end-points are made with groups which require a middleware.

As I mentioned earlier, I’m using cookies as session handlers. For this, a new session store has to be created with some secure token. This is achieved with the following code fragments ( note that I’m using a Gin session middleware which uses gorilla’s session handler located here: Gin-Gonic(Sessions)):

// RandToken in handlers.go:
// RandToken generates a random @l length token.
func RandToken(l int) string {
	b := make([]byte, l)
	rand.Read(b)
	return base64.StdEncoding.EncodeToString(b)
}

// quest.go:
// Create the cookie store in main.go.
store := sessions.NewCookieStore([]byte(handlers.RandToken(64)))
store.Options(sessions.Options{
    Path:   "/",
    MaxAge: 86400 * 7,
})

// using the cookie store:
router.Use(sessions.Sessions("goquestsession", store))

After this gin.Context lets us access this session store by doing session := sessions.Default(c). Now, create a session variable called user-id like this:

session.Set("user-id", u.Email)
err = session.Save()
if err != nil {
    log.Println(err)
    c.HTML(http.StatusBadRequest, "error.tmpl", gin.H{"message": "Error while saving session. Please try again."})
    return
}

Don’t forget to save the session. ;) That is it. If I restart the server, the cookie won’t be usable any longer, since it will generate a new token for the cookie store. The user will have to log in again. Note: It might be that you’ll see something like this, from session: [sessions] ERROR! securecookie: the value is not valid. You can ignore this error.

Restricting access to certain end-points with the auth Middlewareâ„¢

Now, that our session is alive, we can use it to restrict access to some part of the application. With Gin, it looks like this:

authorized := router.Group("/battle")
authorized.Use(middleware.AuthorizeRequest())
{
    authorized.GET("/field", handlers.FieldHandler)
}

This creates a grouping of end-points under /battle. Which means, everything under /battle will only be accessible if the middleware passed to the Use function calls the next handler in the chain. If it aborts the call chain, the end-point will not be accessible. My middleware is pretty simple, but it gets the job done:

// AuthorizeRequest is used to authorize a request for a certain end-point group.
func AuthorizeRequest() gin.HandlerFunc {
	return func(c *gin.Context) {
		session := sessions.Default(c)
		v := session.Get("user-id")
		if v == nil {
			c.HTML(http.StatusUnauthorized, "error.tmpl", gin.H{"message": "Please log in."})
			c.Abort()
		}
		c.Next()
	}
}

Note, that this only check if user-id is set or not. That’s certainly not enough for a secure application. Its only supposed to be a simple example of the mechanics of the auth middleware. Also, the session usually contains more than one parameter. It’s more likely that it contains several variables, which describe the user including a state for CORS protection. For CORS I’d recommend using rs/cors.

If you would try to access http://127.0.0.1:9090/battle/field without logging in, you’d be redirected to an error.tmpl with the message: Please log in..

Final Words

That’s pretty much it. Important parts are:

  • Saving the right information
  • Secure cookie store
  • CORS for sessions
  • Checks of the users details in the cookie
  • Authorised end-points
  • Session handling

Any questions, remarks, ideas, are very welcomed in the comment section. There are plenty of very nice Go frameworks which do Google OAuth2 out of the box. I recommend using them, as they save you a lot of legwork.

Thank you for reading! Gergely.

19 Aug 2016, 00:00

Always Go with []byte

Another quick reminder… Always go with []byte if possible. I said it before, and I’m going to say it over and over again. It’s crucial.

Here is a little code from exercism.io. First, with strings:

package igpay

import (
    "strings"
)

// PigLatin translates reguler old English into awesome pig-latin.
func PigLatin(in string) (ret string) {
    for _, v := range strings.Fields(in) {
        ret += pigLatin(v) + " "
    }

    return strings.Trim(ret, " ")
}

func pigLatin(in string) (ret string) {
    if strings.IndexAny(in, "aeiou") == 0 {
        ret += in + "ay"
        return
    }

    for i := 0; i < len(in); i++ {
        vowelPos := strings.IndexAny(in, "aeiou")

        if (in[0] == 'y' || in[0] == 'x') && vowelPos > 1 {
            vowelPos = 0
            ret = in
        }
        if vowelPos != 0 {
            adjustPosition := vowelPos

            if in[adjustPosition] == 'u' && in[adjustPosition - 1] == 'q' {
                adjustPosition++
            }

            ret = in[adjustPosition:] + in[:adjustPosition]
        }
    }
    ret += "ay"
    return
}

Than with []byte:

package igpay

import (
    // "fmt"
    "bytes"
)

// PigLatin translates reguler old English into awesome pig-latin.
func PigLatin(in string) (ret string) {
    inBytes := []byte(in)
    var retBytes [][]byte
    for _, v := range bytes.Fields(inBytes) {
        v2 := make([]byte, len(v))
        copy(v2, v)
        retBytes = append(retBytes, pigLatin(v2))
    }

    ret = string(bytes.Join(retBytes, []byte(" ")))
    return
}

func pigLatin(in []byte) (ret []byte) {
    if bytes.IndexAny(in, "aeiou") == 0 {
        ret = append(in, []byte("ay")...)
        return
    }

    for i := 0; i < len(in); i++ {
        vowelPos := bytes.IndexAny(in, "aeiou")

        if (in[0] == 'y' || in[0] == 'x') && vowelPos > 1 {
            vowelPos = 0
            ret = in
        }
        if vowelPos != 0 {
            adjustPosition := vowelPos

            if in[adjustPosition] == 'u' && in[adjustPosition - 1] == 'q' {
                adjustPosition++
            }

            in = append(in[adjustPosition:], in[:adjustPosition]...)
            ret = in
            // fmt.Printf("%s\n", ret)
        }
    }
    ret = append(ret, []byte("ay")...)
    return
}

And than,the benchmarks of course:

BenchmarkPigLatin-8          	  200000	     10688 ns/op
BenchmarkPigLatinStrings-8   	  100000	     15211 ns/op
PASS

The improvement is not massive in this case, but it’s more than enough to matter. And in a bigger, more complicated program, string concatenation will take a LOT of time away.

In Go, the bytes package has a 1-1 map compared to the strings packages, so chances are, if you are doing strings concatenations you will be able to port that piece of code easily to []byte.

That’s all folks.

Happy coding, Gergely.

16 Aug 2016, 00:00

Global variable for never changing regex

Quick reminder. If you have a never changing regex in Go, do NOT put it into a frequently called function. ALWAYS put it into a global variable. I’ll show you why.

Benchmark for code with a variable in a frequently called function:

BenchmarkNumber-8     	   30000	     41633 ns/op
BenchmarkAreaCode-8   	   50000	     27736 ns/op
BenchmarkFormat-8     	   50000	     29263 ns/op
PASS
ok  	_/phone-number	5.110s

Benchmark for code with the same variable outside in a global scope:

BenchmarkNumber-8     	  300000	      5618 ns/op
BenchmarkAreaCode-8   	  500000	      3884 ns/op
BenchmarkFormat-8     	  300000	      4696 ns/op
PASS
ok  	_/phone-number	5.197s

Notice the magnitude change in ns/op! That’s something to keep an eye out for.

Thanks for reading! Cheers, Gergely.

12 Jun 2016, 00:00

How to do Google sign-in with Go

Hi folks.

Today, I would like to write up a step - by - step guide with a sample web app on how to do Google Sign-In and authorization.

Let’s get started.

EDIT: A sample project of this, and Part 2, can be found here or here.

Setup

Google OAuth token

First what you need is, to register your application with Google, so you’ll get a Token that you can use to authorize later calls to Google services.

You can do that here: Google Developer Console. You’ll have to create a new project. Once it’s done, click on Credentials and create an OAuth token. You should see something like this: “To create an OAuth client ID, you must first set a product name on the consent screen.”. Go through the questions, like, what type your application is, and once you arrive at stage where it’s asking for your application’s name – there is a section asking for redirect URLs; there, write the url you wish to use when authorising your user. If you don’t know this yet, don’t fret, you can come back and change it later. Do NOT use localhost. If you are running on your own, use http://127.0.0.1:port/whatever.

This will get you a client ID and a client secret. I’m going to save these into a file which will sit next to my web app. It could be stored more securely, for example, in a database or a mounted secure, encrypted drive, and so and so forth.

Your application can now be identified through Google services.

The Application

Libraries

Google has a nice library to use with OAuth 2.0. The library is available here: Google OAth 2.0. It’s a bit cryptic at first, but not to worry. After a bit of fiddling you’ll understand fast what it does. I’m also using Gin, and Gin’s session handling middleware Gin-Session.

Setup - Credentials

Let’s create a setup which configures your credentials from the file you saved earlier. This is pretty straightforward.

// Credentials which stores google ids.
type Credentials struct {
    Cid string `json:"cid"`
    Csecret string `json:"csecret"`
}

func init() {
    var c Credentials
    file, err := ioutil.ReadFile("./creds.json")
    if err != nil {
        fmt.Printf("File error: %v\n", err)
        os.Exit(1)
    }
    json.Unmarshal(file, &c)
}

Once you have the creds loaded, you can now go on to construct the OAuth client.

Setup - OAuth client

Construct the OAuth config like this:

conf := &oauth2.Config{
  ClientID:     c.Cid,
  ClientSecret: c.Csecret,
  RedirectURL:  "http://localhost:9090/auth",
  Scopes: []string{
    "https://www.googleapis.com/auth/userinfo.email", // You have to select your own scope from here -> https://developers.google.com/identity/protocols/googlescopes#google_sign-in
  },
  Endpoint: google.Endpoint,
}

It will give you a struct which you can then use to Authorize the user in the google domain. Next, all you need to do is call AuthCodeURL on this config. It will give you a URL which redirects to a Google Sign-In form. Once the user fills that out and clicks ‘Allow’, you’ll get back a TOKEN in the code query parameter and a state which helps protect against CSRF attacks. Always check if the provided state is the same which you provided with AuthCodeURL. This will look something like this http://127.0.0.1:9090/auth?code=4FLKFskdjflf3343d4f&state=lhfu3f983j;asdf. Small function for this:

func getLoginURL(state string) string {
    // State can be some kind of random generated hash string.
    // See relevant RFC: http://tools.ietf.org/html/rfc6749#section-10.12
    return conf.AuthCodeURL(state)
}

Construct a button which the user can click and be redirected to the Google Sign-In form. When constructing the url, we must do one more thing. Create a secure state token and save it in the form of a cookie for the current user.

Random State and Button construction

Small piece of code random token:

func randToken() string {
	b := make([]byte, 32)
	rand.Read(b)
	return base64.StdEncoding.EncodeToString(b)
}

Storing it in a session and constructing the button:

func loginHandler(c *gin.Context) {
    state = randToken()
    session := sessions.Default(c)
    session.Set("state", state)
    session.Save()
    c.Writer.Write([]byte("<html><title>Golang Google</title> <body> <a href='" + getLoginURL() + "'><button>Login with Google!</button> </a> </body></html>"))
}

It’s not the nicest button I ever come up with, but it will have to do.

User Information

After you got the token, you can construct an authorised Google HTTP Client, which let’s you call Google related services and retrieve information about the user.

Getting the Client

Before we construct a client, we must check if the retrieved state is still the same compared to the one we provided. I’m doing this before constructing the client. Together this looks like this:

func authHandler(c *gin.Context) {
    // Check state validity.
    session := sessions.Default(c)
    retrievedState := session.Get("state")
    if retrievedState != c.Query("state") {
        c.AbortWithError(http.StatusUnauthorized, fmt.Errorf("Invalid session state: %s", retrievedState))
        return
    }
    // Handle the exchange code to initiate a transport.
  	tok, err := conf.Exchange(oauth2.NoContext, c.Query("code"))
  	if err != nil {
  		c.AbortWithError(http.StatusBadRequest, err)
          return
  	}
    // Construct the client.
    client := conf.Client(oauth2.NoContext, tok)
    ...

Obtaining information

Our next step is to retrieve information about the user. To achieve this, call Google’s API with the authorised client. The code for that is:

...
resp, err := client.Get("https://www.googleapis.com/oauth2/v3/userinfo")
if err != nil {
    c.AbortWithError(http.StatusBadRequest, err)
    return
}
defer resp.Body.Close()
data, _ := ioutil.ReadAll(resp.Body)
log.Println("Resp body: ", string(data))
...

And this will yield a body like this:

{
  "sub": "1111111111111111111111",
  "name": "Your Name",
  "given_name": "Your",
  "family_name": "Name",
  "profile": "https://plus.google.com/1111111111111111111111",
  "picture": "https://lh3.googleusercontent.com/asdfadsf/AAAAAAAAAAI/Aasdfads/Xasdfasdfs/photo.jpg",
  "email": "your@gmail.com",
  "email_verified": true,
  "gender": "male"
}

Parse it, and you’ve got an email which you can store somewhere for registration purposes. At this point, your user is not yet Authenticated. For that, I’m going to post a second post, which describes how to go on. Retrieving the stored email address, and user session handling with Gin and MongoDB.

Putting it all together

package main

import (
    "crypto/rand"
    "encoding/base64"
    "encoding/json"
    "io/ioutil"
    "fmt"
    "log"
    "os"
    "net/http"

    "github.com/gin-gonic/contrib/sessions"
    "github.com/gin-gonic/gin"
    "golang.org/x/oauth2"
    "golang.org/x/oauth2/google"
)

// Credentials which stores google ids.
type Credentials struct {
    Cid     string `json:"cid"`
    Csecret string `json:"csecret"`
}

// User is a retrieved and authentiacted user.
type User struct {
    Sub string `json:"sub"`
    Name string `json:"name"`
    GivenName string `json:"given_name"`
    FamilyName string `json:"family_name"`
    Profile string `json:"profile"`
    Picture string `json:"picture"`
    Email string `json:"email"`
    EmailVerified string `json:"email_verified"`
    Gender string `json:"gender"`
}

var cred Credentials
var conf *oauth2.Config
var state string
var store = sessions.NewCookieStore([]byte("secret"))

func randToken() string {
	b := make([]byte, 32)
	rand.Read(b)
	return base64.StdEncoding.EncodeToString(b)
}

func init() {
    file, err := ioutil.ReadFile("./creds.json")
    if err != nil {
        log.Printf("File error: %v\n", err)
        os.Exit(1)
    }
    json.Unmarshal(file, &cred)

    conf = &oauth2.Config{
        ClientID:     cred.Cid,
        ClientSecret: cred.Csecret,
        RedirectURL:  "http://127.0.0.1:9090/auth",
        Scopes: []string{
            "https://www.googleapis.com/auth/userinfo.email", // You have to select your own scope from here -> https://developers.google.com/identity/protocols/googlescopes#google_sign-in
        },
        Endpoint: google.Endpoint,
    }
}

func indexHandler(c *gin.Context) {
    c.HTML(http.StatusOK, "index.tmpl", gin.H{})
}

func getLoginURL(state string) string {
    return conf.AuthCodeURL(state)
}

func authHandler(c *gin.Context) {
    // Handle the exchange code to initiate a transport.
    session := sessions.Default(c)
    retrievedState := session.Get("state")
    if retrievedState != c.Query("state") {
        c.AbortWithError(http.StatusUnauthorized, fmt.Errorf("Invalid session state: %s", retrievedState))
        return
    }

	tok, err := conf.Exchange(oauth2.NoContext, c.Query("code"))
	if err != nil {
		c.AbortWithError(http.StatusBadRequest, err)
        return
	}

	client := conf.Client(oauth2.NoContext, tok)
	email, err := client.Get("https://www.googleapis.com/oauth2/v3/userinfo")
    if err != nil {
		c.AbortWithError(http.StatusBadRequest, err)
        return
	}
    defer email.Body.Close()
    data, _ := ioutil.ReadAll(email.Body)
    log.Println("Email body: ", string(data))
    c.Status(http.StatusOK)
}

func loginHandler(c *gin.Context) {
    state = randToken()
    session := sessions.Default(c)
    session.Set("state", state)
    session.Save()
    c.Writer.Write([]byte("<html><title>Golang Google</title> <body> <a href='" + getLoginURL(state) + "'><button>Login with Google!</button> </a> </body></html>"))
}

func main() {
    router := gin.Default()
    router.Use(sessions.Sessions("goquestsession", store))
    router.Static("/css", "./static/css")
    router.Static("/img", "./static/img")
    router.LoadHTMLGlob("templates/*")

    router.GET("/", indexHandler)
    router.GET("/login", loginHandler)
    router.GET("/auth", authHandler)

    router.Run("127.0.0.1:9090")
}
}

This is it folks. I hope this helped. Any comments or advices are welcomed.

Google API Documentation

The documentation to this whole process, and MUCH more information can be found here: Google API Docs.

Thanks for reading, Gergely.

09 Mar 2016, 00:00

Wercker Fixed

Hi Folks.

So Wercker was not working. After a minor modification it seems to be okay now. The config file needed for it to work looks like this:

box: golang 
build:
    steps:
        - arjen/hugo-build:
            theme: redlounge
deploy:
    steps:
        - install-packages:
            packages: git 
        - leipert/git-push:
            gh_oauth: $GIT_TOKEN
            repo: skarlso/skarlso.github.io
            branch: master
            basedir: public    

The modification is the box type to golang and removed ssh-client from packages.

Thanks, Gergely.

04 Mar 2016, 00:00

Wercker Test

Basics

This is a wercker Test.

10 Feb 2016, 00:00

Wercker Test

Basics

This is a wercker Test.

02 Feb 2016, 00:00

Doing CORS in Go with Gin and JSON

Basics

Hello folks.

This will be a quick post about how to do CORS with jQuery, Gin in Go with a very simple ajax GET and Json.

I’m choosing JSON here because basically I don’t really like JSONP. And actually, it’s not very complicated to do CORS, it’s just hidden enough so that it doesn’t become transparent.

First, what is CORS? It’s Cross-Platform Resource Sharing. It has been invented so that without your explicit authorization in the header of a request, Javascript can’t reach outside of your domain and be potentially harmful to your visitors.

Now, suppose you have an architecture like this.

Architecture

You have multiple agents sitting on multiple nodes. You have one central server, and you have multiple front-ends. Everybody can only talk to the Server but the server does talk to everyone. You would like to have a dynamic front-end and would like to display data with ajax calls. Since your front-end sits on a different server, you will have to do something about CORS. This is how I solved it…

I’m using Gin for my REST service for Dockmaster. For this two work, you need to adjust two component.

Server

There is thing called a Preflight-Check. In essence, the preflight check is sent BEFORE the actual request to check if the next request is allowed to go out of the domain. The preflight check is sent to the same URI just with OPTIONS method. In order to tell the caller that the next one will be safe, you need three things.

First, you need to set two Headers. #1 -> Access-Control-Allow-Origin to “*“. #2 -> Access-Control-Allow-Headers to “access-control-allow-origin, access-control-allow-headers”.

These are the minimum headers you can set. If you allow Access-Control-Allow-Origin you also have to allow it in the headers section because the next request will expect it to be there. Also, note here that setting Origin to * is only recommended in development environment. Otherwise it should be set to whatever your domain is.

Second, you need to respond to the OPTIONS method with a 200. In order to do that, I added a simple rule with the same end-point but with OPTIONS.

func main() {
    router := gin.Default()
    v1 := router.Group(APIBASE)
    {
        v1.GET("/list", listContainers)
        v1.POST("/add", addContainers)
        v1.POST("/delete", deleteContainers)
        v1.GET("/inspect/:agentID/:containerID", inspectContainer)
        v1.OPTIONS("/inspect/:agentID/:containerID", preflight)
        v1.POST("/stopAll", stopAll)
        v1.OPTIONS("/stopAll", preflight)
    }
    router.Run(":8989")
}

func preflight(c *gin.Context) {
    c.Header("Access-Control-Allow-Origin", "*")
    c.Header("Access-Control-Allow-Headers", "access-control-allow-origin, access-control-allow-headers")
    c.JSON(http.StatusOK, struct{}{})
}

You can see that the preflight method is there for two end-points. I added it to those end-points which will reach over the domain. The others are all local, thus they don’t need that. This leads to a little duplication, but that is fine. I have a very fine control over what actually is allowed to go outside of the domain.

So, how do we call this?

Frontend

In the front-end’s web layout, I’m doing an Ajax GET, which looks like this:

                $.ajax({
                    url: 'http://localhost:8989/api/1/inspect/'+data.agentid+'/'+data.id,
                    type: 'GET',
                    dataType:"json",
                    headers: {"Access-Control-Allow-Origin": "*", "Access-Control-Allow-Headers": "access-control-allow-origin, access-control-allow-headers"},
                    processData: false,
                    success: function(data) {
                        var json = JSON.stringify(data, null, 4)
                        independentPopup.html("<pre >"+json+"</pre>");
                        $(link).after(independentPopup);
                    }
                });

After the headers are set, the request will work nicely.

Y U No Middleware?

And now you could say that, why not just have a middleware which will always accept OPTIONS for every end-point. Because I like it better this way. Some would argue that this is too granular, but fact is, that in my opinion, this is more readable and immediatly visible. However, if you DO want to do that, you have several options to your disposal.

Cors Basic Http Middleware and for Gin Gin CORS Middleware.

Summary

This is it. You can see the code in its entirety on Github. Have a better idea on how to do it? Please! Do not hesitate to share. I always like to learn.

Thank you for reading!

And as always, Have a nice day!

Gergely.

22 Jan 2016, 00:00

My Journey in advent of code

Hello folks.

I wanted to share with you my tale of working through the problems with Advent Of Code.

It is a nice tale and there are a few things I learned from it, especially in Go, since I used that solve all of the problems. So, let’s get started.

Solving the problems

The most important lesson I learned while doing these exercises was, how to solve these problems. A couple of them were simple enough to not have to over think it, but most of them got very tricky. I could have gone with a brute force attempt, but as we see later, that wasn’t always a very good solution. And people who used that, actually just got lucky finding their solutions.

The eight stages of breaking down a problem according to this book Thinking Like a Programmer are the following:

  • Have a plan
  • Rephrase
  • Divide
  • Start with what you know
  • Reduce
  • Analogies
  • Experiment
  • Don’t get frustrated

Have a plan and understanding your goal

This is simple. Always have a plan of what you would like to do, and how to start. This will help you massively along the way to not to loose sight of what your goal is actually. For example, look at Day 24. At first, it looks like a permutational puzzle, but if you understand the solution we are looking for, you realize that there is an easier way of finding it. Since you only want the packages which consists of the fewest item counts, you would only care about the largest numbers because those will be the fewest which still give you the desired package weight. Suddenly the problem gets easier because you don’t have to worry about the other groups any longer.

Rephrase

Rephrasing the problem with your own words can help in understanding it better. Or even better, try explaining it to somebody else. If you cannot rephrase it, you didn’t understand it in the first place.

Divide

If the problem seems daunting because it’s massive, just divide it into smaller chunks. This is something that we usually do with large problems, but it’s more subtle than that. If you face a problem which seems complex, just factor out parts of it until you got a problem which you do understand. Even if you have to butcher the original puzzle problem. It doesn’t matter. Adding complexity later is easier than adding complexity in its infancy.

Start with what you know && Finding analogies

This one speaks for itself. If you know parts of the problem, because you know analogy for it, or you faced something similar before, or exactly that, start with that.

Reduce

If the problem seems too complex, remove complexity. Start with a smaller set. Preferably something testable (I’ll come back to that later). Remove constraints, or add them as desired. A constraint makes it harder to solve the puzzle? Remove it, and try solving it without. After that, the solution will give you insight into the problem and you can add that constraint back in.

Consider Day 11. I had fun with this one. In order to easy it up a little, I first, removed the constraint of doing the increment with letters. I did it with numbers. I also removed the constraint of doing it within the confines of a limited length array. After I got that I’ll use modulo to make the numbers wrap around, it was way more easy to apply it to characters. And after a little fidgeting this came to life:

passwd[i] -= 'a'
passwd[i] = (passwd[i] + 1) % (('z' - 'a') + 1)
passwd[i] += 'a'

The -,+ ‘a’ is needed so that it’s dealing with ascii code from 0 - ‘z’. This basically makes it so that when I reach the end of the alphabet it will wrap around and start from ‘a’ again.

Experiment

This led to more solutions than I care to admit. Basically just start experimenting with solutions which are in your head. There is a chance, that what you come up with, will be the solution. This goes very well with the principle of Make it work, Make it right, Make it fast. Just have something working first, and than you can make it work properly after. It’s always better to have something rather than nothing.

And last but not least…

Don’t get frustrated

This is something I cannot say strongly enough. Seriously. DO NOT GET FRUSTRATED. Most of the problems were designed to be harder. Unless you work as a programmer professionally for several years now, or this is a field of interest for you, you will spend a day hacking around on a problem and trying to find a solution which is adequate. In these times, you will get frustrated and think you are too stupid for this, this couldn’t be more far from the truth! You might need some inspiration, you might need some time away from the screen, it helps if you draw out the problem in a piece of paper, or just think about it without seeing it for a while. Just take a break, eat something, watch a comedy and get back to it later with a fresh view.

Technical Gotchas

So after the general problem solving side of things, I learned many things about Go, and about the tidbits of this language.

Byte Slices

I already knew that []byte is more performant and that Go optimizes on them more, but not to this extent. As in my previous blog posts I discovered that using them can really make a huge difference. Go even has a library called bytes which has helper functions similar to that of strings to help you out in these situations. Go optimizes on map recalls as well when you cast to string from []byte and use that as a map key like this: myMap[string(data)].

Brute Force or Looping

Most of the times you could get away with looping or trying to brute force out a solution. But there were times, where you really had to huddle down and think the problem through. Because simply looping, either took too long, or didn’t come up with a good answer. That’s why I rather always start with: ‘How could I solve this without looping?’. This will get you into the right mindset. Or thinking: ‘How could I solve this without taking each and every combination into account?’. These questions will help you to think about the problem without loops. Or only if you REALLY must use one.

Doing this will get you into the right way of thinking. I know that in advent of code there is a Leaderboard and you could get on it if you were fast. But most of the times having a fast solution is far from having the right solution.

Structs are Awesome

I like using structs. They are a very lightweight way of defining objects, structures which stick together. For example in the Day 6 Light puzzle, or even Day 3 Traveling santa example, a struct which stuck x,y locations together and made it a map key, it was trivial to make my gif out of it with SVG ->

Traveling Santa

Go is Simple to Read

[opinion] I like Go because of its simplicity. You don’t see stuff in Go most of the times, where you need to look three times to understand what the heck is going on. I like filter, reduce, map and syntactic sugar, but they make for a very poor reading experience. Go, in that way, choose not to incorporate these paradigms and I find that refreshing. [/opinion]

Testing

TDD is something we all should know by now and care about. When I’m doing puzzles, or finger exercises, I tend to not write tests. But on a more complex puzzle, or a task, I always start with a test. Especially if you are given samples for a puzzle which work. That’s a gold mine. You can tweak your algorithm using those samples until they work and then simply apply a larger sample size.

Tests will also help you with breaking down a problem and identifying parts which you already know.

For example Day 13. Optimal Seating arrangements. Or the similar Day 9. Which was calculating shortest route distance. Or the password one, Day 11 which I showed before. In these cases, tests helped me make the core of the algorithm solid. Calculating connections, or the odd regex here and there, which was making sure that the password was validated properly.

Tests will also help you to be able to move on after you found your solution. When I was done with the first iteration of passwords which was still using strings, I went on to optimize it, to use []byte. The tests helped me to know that the code was still working as expected after the refactoring.

Closing words

All in all it was a massive amount of fun doing these exercises and I’m thankful to the creator for making it. And I did enjoy the story behind the exercises as well. I think this site stood out because it had a fun factor. For simple exercises there are a lot of other sites -like Project Euler, or Sphere Judge Online-, which just plainly present you a problem and that’s it. It’s still fun, but it can also became boring very fast. Don’t forget the fun factor which makes you plow on and go into a blind frenzy that you cannot quit until it’s done. That’s the fun part.

Thank you for reading! Have a nice day. Gergely.

05 Jan 2016, 00:00

Improving performance with byte slice and int map

Hello Folks.

Today I would like to share with you my little tale of refactoring my solution to Advent Of Code Day 13.

It’s a lovely tale of action, adventure, drama, and comedy.

Let’s being with my first iteration of the problem.

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"

	"github.com/skarlso/goutils/arrayutils"
)

var seatingCombinations = make([][]string, 0)
var table = make(map[string][]map[string]int)
var keys = make([]string, 0)

//Person a person
type Person struct {
	// neighbour *Person
	name string
	like int
}

func main() {
	file, _ := os.Open("input.txt")
	defer file.Close()
	scanner := bufio.NewScanner(file)
	for scanner.Scan() {
		line := scanner.Text()
		split := strings.Split(line, " ")
		like, _ := strconv.Atoi(split[3]) //If lose -> * -1
		if split[2] == "lose" {
			like *= -1
		}
		table[split[0]] = append(table[split[0]], map[string]int{strings.Trim(split[10], "."): like})
		if !arrayutils.ContainsString(keys, split[0]) {
			keys = append(keys, split[0])
		}
	}
	generatePermutation(keys, len(keys))
	fmt.Println("Best seating efficiency:", calculateSeatingEfficiancy())
}

func generatePermutation(s []string, n int) {
	if n == 1 {
		news := make([]string, len(s))
		copy(news, s)
		seatingCombinations = append(seatingCombinations, news)
	}
	for i := 0; i < n; i++ {
		s[i], s[n-1] = s[n-1], s[i]
		generatePermutation(s, n-1)
		s[i], s[n-1] = s[n-1], s[i]
	}
}

func calculateSeatingEfficiancy() int {
	bestSeating := math.MinInt64
	for _, v := range seatingCombinations {
		calculatedOrder := 0

		for i := range v {
			left := (i - 1) % len(v)
			//This is to work around the fact that in Go
			//modulo of a negative number will not return a positive number.
			//So -1 % 4 will not return 3 but -1. In that case we add length.
			if left < 0 {
				left += len(v)
			}
			right := (i + 1) % len(v)
			// fmt.Printf("Left: %d; Right: %d\n", left, right)
			leftLike := getLikeForTargetConnect(v[i], v[left])
			rightLike := getLikeForTargetConnect(v[i], v[right])
			// fmt.Printf("Name: %s; Left:%d; Right:%d\n", v[i], leftLike, rightLike)
			calculatedOrder += leftLike + rightLike
		}
		// fmt.Printf("Order for: %v; Calc:%d\n", v, calculatedOrder)
		if calculatedOrder > bestSeating {
			bestSeating = calculatedOrder
		}
	}

	return bestSeating
}

func getLikeForTargetConnect(name string, neighbour string) int {
	neighbours := table[name]
	for _, t := range neighbours {
		if v, ok := t[neighbour]; ok {
			return v
		}
	}
	return 0
}

This is quiet large. And takes a bit of explaining. So what is happening here? We are putting the names which correspond with numbers and neighbours into a map which has a map as a value. The map contains seating information for a person. For example, next to Alice, a bunch of people can sit, and they have a certain relationship to Alice, represented by a number.

We could, at this point, represent it with a graph, but that would be overkill.

Permutation is simple because I choose to represent a Table with a Circular Slice. This means that a slice like this => Alice, Bob, Tom; means that Alice is sitting next to Bob and Tom. So Alice’s neighbour of -1 (left) is in fact i-1 % 3. And Bob is i + 1. For Tom, Alice is i + 1 % 3. After we got this, we just permutate the possible combinations into slices of slices and iterate over them.

The benchmark for this is terrible.


================With Strings================
20	 589571259 ns/op
ok  	github.com/skarlso/goprojects/advent/day13/part1	11.873s

So, my first thought was, convert everything I can to []byte. But because slices cannot be map keys, because map keys need to be comparable, we are still stuck with the same ns/ops.

//var seatingCombinations = make([][]string, 0)
//var keys = make([]string, 0)
var seatingCombinations = make([][][]byte, 0)
var keys = make([][]byte, 0)

And I adjusted the code to work with []byte instead. What can we do to fix the map though? One obvious gain is, not to use string as a key. Because strings are immutable, working with them always means copy-ing and that’s why they get to be very slow. So removing them from Keys and using Numbers instead will mean a huge gain for us.

To do this, I created a map which maps names with numbers. I could hardcode them with iota, but that is a very bad thing to do. It would mean, that when I add a new name, I would have to go, and re-compile my code, because data changed. That’s not what we want.

So, I added this little tid-bit into the for cycle when I’m reading in the file lines =>

...
if _, ok := nameMapping[split[0]]; !ok {
    nameMapping[split[0]] = id
    id++
}
if _, ok := nameMapping[trimmedNeighbour]; !ok {
    nameMapping[trimmedNeighbour] = id
    id++
}
...

Id starts as Zero. And nameMapping is a simple map[string]int. After this, we fix all the map calls, from table[split[0]] to table[nameMapping[split[0]]]. Table’s map will now work with int, but we can still work with strings otherwise.

table[nameMapping[split[0]]] = append(table[nameMapping[split[0]]], map[int]int{nameMapping[trimmedNeighbour]: like})

This has now a marginally better performance as before:

BenchmarkCalculateSeating	      50	  32637879 ns/op
ok  	github.com/skarlso/goprojects/advent/day13/part1	1.698s

But, we can still do a HUGE one better. Can you notice the other bottleneck? See, how keys are still []byte? That’s, now completely unnecessary. We can use int, since our keys are ints! Permutation changes, and the retrieve.

...
func generatePermutation(s []int, n int) {
...

...
func getLikeForTargetConnect(name int, neighbour int) int {
	neighbours := table[name]
	for _, t := range neighbours {
		if v, ok := t[neighbour]; ok {
			return v
		}
	}
	return 0
}
...

Permutation was the Other huge performance consumption. Now, our run time is…. drum rolls…

BenchmarkCalculateSeating	   10000	    166431 ns/op
ok  	github.com/skarlso/goprojects/advent/day13/part1	1.695s

Down to 166431 ns/op!!! From 32637879 ns/op!! And notice how suddenly, go’s benchmark jumped up in sample count. Our code is now blazing fast. It’s 0.05% of the previous run! It’s almost 200 times faster!

We could still improve it here and there. I’m sure I’m doing some extra stuff which is not needed or could be made easier somehow. But I’m actually quiet happy with this solution right now.

The full code:

package main

import (
	"bufio"
	"math"
	"os"
	"strconv"
	"strings"

	"github.com/skarlso/goutils/arrayutils"
)

var seatingCombinations = make([][]int, 0)
var table = make(map[int][]map[int]int)
var keys = make([]int, 0)
var nameMapping = make(map[string]int)

//Person a person
type Person struct {
	// neighbour *Person
	name string
	like int
}

func main() {
	CalculatePerfectSeating()
}

//CalculatePerfectSeating returns the perfect seating order based on Love/Hate relations
func CalculatePerfectSeating() {
	file, _ := os.Open("input.txt")
	defer file.Close()
	scanner := bufio.NewScanner(file)
	id := 0
	for scanner.Scan() {
		line := scanner.Text()
		split := strings.Split(line, " ")
		trimmedNeighbour := strings.Trim(split[10], ".")
		like, _ := strconv.Atoi(split[3]) //If lose -> * -1
		if _, ok := nameMapping[split[0]]; !ok {
			nameMapping[split[0]] = id
			id++
		}
		if _, ok := nameMapping[trimmedNeighbour]; !ok {
			nameMapping[trimmedNeighbour] = id
			id++
		}
		if split[2] == "lose" {
			like *= -1
		}
		table[nameMapping[split[0]]] = append(table[nameMapping[split[0]]], map[int]int{nameMapping[trimmedNeighbour]: like})
		if !arrayutils.ContainsInt(keys, nameMapping[split[0]]) {
			keys = append(keys, nameMapping[split[0]])
		}
	}
	generatePermutation(keys, len(keys))
	// fmt.Println("Best seating efficiency:", calculateSeatingEfficiancy())
}

func generatePermutation(s []int, n int) {
	if n == 1 {
		news := make([]int, len(s))
		copy(news, s)
		seatingCombinations = append(seatingCombinations, news)
	}
	for i := 0; i < n; i++ {
		s[i], s[n-1] = s[n-1], s[i]
		generatePermutation(s, n-1)
		s[i], s[n-1] = s[n-1], s[i]
	}
}

func calculateSeatingEfficiancy() int {
	bestSeating := math.MinInt64
	for _, v := range seatingCombinations {
		calculatedOrder := 0

		for i := range v {
			left := (i - 1) % len(v)
			//This is to work around the fact that in Go
			//modulo of a negative number will not return a positive number.
			//So -1 % 4 will not return 3 but -1. In that case we add length.
			if left < 0 {
				left += len(v)
			}
			right := (i + 1) % len(v)
			calculatedOrder += getLikeForTargetConnect(v[i], v[left]) + getLikeForTargetConnect(v[i], v[right])
		}
		if calculatedOrder > bestSeating {
			bestSeating = calculatedOrder
		}
	}

	return bestSeating
}

func getLikeForTargetConnect(name int, neighbour int) int {
	neighbours := table[name]
	for _, t := range neighbours {
		if v, ok := t[neighbour]; ok {
			return v
		}
	}
	return 0
}

Also, on github => Advent Of Code Day 13.

Thank you very much for reading, this has been a massive fun to write and to refactor.

Have something to say? Please don’t hesitate.

And as always,

Have a nice day!

Gergely.