 # ChrisPritchard's solution

## to SGF Parsing in the C# Track

Published at Oct 18 2018 · 0 comments
Instructions
Test suite
Solution

#### Note:

This exercise has changed since this solution was written.

Parsing a Smart Game Format string.

SGF is a standard format for storing board game files, in particular go.

SGF is a fairly simple format. An SGF file usually contains a single tree of nodes where each node is a property list. The property list contains key value pairs, each key can only occur once but may have multiple values.

An SGF file may look like this:

``````(;FFC[root]SZ;B[aa];W[ab])
``````

This is a tree with three nodes:

• The top level node has two properties: FF (key = "FF", value = "4") and C[root](key = "C", value = "root"). (FF indicates the version of SGF and C is a comment.)
• The top level node has a single child which has a single property: B[aa]. (Black plays on the point encoded as "aa", which is the 1-1 point (which is a stupid place to play)).
• The B[aa] node has a single child which has a single property: W[ab].

As you can imagine an SGF file contains a lot of nodes with a single child, which is why there's a shorthand for it.

SGF can encode variations of play. Go players do a lot of backtracking in their reviews (let's try this, doesn't work, let's try that) and SGF supports variations of play sequences. For example:

``````(;FF(;B[aa];W[ab])(;B[dd];W[ee]))
``````

Here the root node has two variations. The first (which by convention indicates what's actually played) is where black plays on 1-1. Black was sent this file by his teacher who pointed out a more sensible play in the second child of the root node: `B[dd]` (4-4 point, a very standard opening to take the corner).

A key can have multiple values associated with it. For example:

``````(;FF;AB[aa][ab][ba])
``````

Here `AB` (add black) is used to add three black stones to the board.

There are a few more complexities to SGF (and parsing in general), which you can mostly ignore. You should assume that the input is encoded in UTF-8, the tests won't contain a charset property, so don't worry about that. Furthermore you may assume that all newlines are unix style (`\n`, no `\r` or `\r\n` will be in the tests) and that no optional whitespace between properties, nodes, etc will be in the tests.

The exercise will have you parse an SGF string and return a tree structure of properties. You do not need to encode knowledge about the data types of properties, just use the rules for the text type everywhere.

## Hints

• To parse the text, you could try to use the Sprache library. You can also find a good tutorial here.

## Running the tests

To run the tests, run the command `dotnet test` from within the exercise directory.

## Further information

For more detailed information about the C# track, including how to get help if you're having trouble, please visit the exercism.io C# language page.

## Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

### SgfParsingTest.cs

``````// This file was auto-generated based on version 1.0.0 of the canonical data.

using System;
using System.Collections.Generic;
using Xunit;

public class SgfParsingTest
{
[Fact]
public void Empty_input()
{
var encoded = "";
Assert.Throws<ArgumentException>(() => SgfParser.ParseTree(encoded));
}

[Fact(Skip = "Remove to run test")]
public void Tree_with_no_nodes()
{
var encoded = "()";
Assert.Throws<ArgumentException>(() => SgfParser.ParseTree(encoded));
}

[Fact(Skip = "Remove to run test")]
public void Node_without_tree()
{
var encoded = ";";
Assert.Throws<ArgumentException>(() => SgfParser.ParseTree(encoded));
}

[Fact(Skip = "Remove to run test")]
public void Node_without_properties()
{
var encoded = "(;)";
var expected = new SgfTree(new Dictionary<string, string[]>());
Assert.Equal(expected, SgfParser.ParseTree(encoded));
}

[Fact(Skip = "Remove to run test")]
public void Single_node_tree()
{
var encoded = "(;A[B])";
var expected = new SgfTree(new Dictionary<string, string[]> { ["A"] = new[] { "B" } } );
Assert.Equal(expected, SgfParser.ParseTree(encoded));
}

[Fact(Skip = "Remove to run test")]
public void Properties_without_delimiter()
{
var encoded = "(;A)";
Assert.Throws<ArgumentException>(() => SgfParser.ParseTree(encoded));
}

[Fact(Skip = "Remove to run test")]
public void All_lowercase_property()
{
var encoded = "(;a[b])";
Assert.Throws<ArgumentException>(() => SgfParser.ParseTree(encoded));
}

[Fact(Skip = "Remove to run test")]
public void Upper_and_lowercase_property()
{
var encoded = "(;Aa[b])";
Assert.Throws<ArgumentException>(() => SgfParser.ParseTree(encoded));
}

[Fact(Skip = "Remove to run test")]
public void Two_nodes()
{
var encoded = "(;A[B];B[C])";
var expected = new SgfTree(new Dictionary<string, string[]> { ["A"] = new[] { "B" } } ,new SgfTree(new Dictionary<string, string[]> { ["B"] = new[] { "C" } } ));
Assert.Equal(expected, SgfParser.ParseTree(encoded));
}

[Fact(Skip = "Remove to run test")]
public void Two_child_trees()
{
var encoded = "(;A[B](;B[C])(;C[D]))";
var expected = new SgfTree(new Dictionary<string, string[]> { ["A"] = new[] { "B" } } ,new SgfTree(new Dictionary<string, string[]> { ["B"] = new[] { "C" } } ), new SgfTree(new Dictionary<string, string[]> { ["C"] = new[] { "D" } } ));
Assert.Equal(expected, SgfParser.ParseTree(encoded));
}

[Fact(Skip = "Remove to run test")]
public void Multiple_property_values()
{
var encoded = "(;A[b][c][d])";
var expected = new SgfTree(new Dictionary<string, string[]> { ["A"] = new[] { "b", "c", "d" } } );
Assert.Equal(expected, SgfParser.ParseTree(encoded));
}

[Fact(Skip = "Remove to run test")]
public void Escaped_property()
{
var encoded = "(;A[\\]b\\nc\\nd\\t\\te \\n\\]])";
var expected = new SgfTree(new Dictionary<string, string[]> { ["A"] = new[] { "]b\nc\nd  e \n]" } } );
Assert.Equal(expected, SgfParser.ParseTree(encoded));
}
}``````
``````using System;
using System.Collections.Generic;
using System.Linq;
using Sprache;

public class SgfTree
{
public SgfTree(IDictionary<string, string[]> data, params SgfTree[] children)
=> (Data, Children) = (data, children);

public IDictionary<string, string[]> Data { get; }
public SgfTree[] Children { get; }

public override bool Equals(object obj)
{
var that = obj as SgfTree;
if(that == null)
return false;
if(this.Data.Count != that.Data.Count || this.Children.Length != that.Children.Length)
return false;
if(this.Data.Keys.Any(key => !that.Data.ContainsKey(key) || !this.Data[key].SequenceEqual(that.Data[key])))
return false;
return this.Children.All(child => that.Children.Contains(child));
}

public override int GetHashCode() => base.GetHashCode();
}

public class SgfParser
{
public static SgfTree ParseTree(string input)
{
try { return tree.Parse(input); }
catch(ParseException) { throw new ArgumentException("invalid input"); }
}

private static readonly Parser<SgfTree> tree =
from _ in Parse.Char('(')
from node in node
from __ in Parse.Char(')')
select node;

private static readonly Parser<SgfTree> node =
from _ in Parse.Char(';')
from attributes in Parse.Many(attribute)
from children in Parse.Once(node).Or(Parse.Many(tree))
select new SgfTree(attributes.ToDictionary(o => o.Item1, o => o.Item2), children.ToArray());

private static readonly Parser<(string, string[])> attribute =
from name in Parse.Many(Parse.Char(Char.IsUpper, "upper only")).Text()
from values in Parse.AtLeastOnce(attributeValue)
select (name, values.ToArray());

private static readonly Parser<string> attributeValue =
from _ in Parse.Char('[')
from value in Parse.Until(validPropValues, Parse.Char(']')).Text()
select value;

private static readonly Parser<char> validPropValues =
(Parse.String("\\n").Return('\n'))
.Or(Parse.String("\\t").Return(' '))
.Or(Parse.Char('\\').Then(c => Parse.AnyChar))
.Or(Parse.Char(' '))
.Or(Parse.Letter);
}``````