第27回オフラインリアルタイムどう書くの問題をC#で

問題はこちら
http://qiita.com/Nabetani/items/23ebddb44f0234e7fb15

非循環有向グラフ(DAG)探索。グラフ構造を作るにあたって、NuGetの System.Collections.Immutable パッケージを使いましたが、グラフライブラリは使ってないです。

グラフを「切る」のが面倒だったので、ルートを数え上げてから絞り込むことにしました。

Program.cs

using System;
using System.Collections.Generic;
using System.Collections.Immutable; // from NuGet
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        Test("befi", "14,16,24,26");
        Test("abc", "14,15,16,24,25,26,34,35,36");
        Test("de", "14,15,16,24,26,34,35,36");
        Test("fghi", "14,15,16,24,25,26,34,35,36");
        Test("abcdefghi", "-");
        Test("ag", "24,25,26,34,35,36");
        Test("dh", "14,15,16,34,35,36");
        Test("bf", "14,15,16,24,25,26");
        Test("ch", "15,25,35");
        Test("be", "14,16,24,26,34,36");
        Test("ci", "14,15,24,25,34,35");
        Test("cgi", "15,24,25,35");
        Test("acgi", "24,25,35");
        Test("cdefghi", "15,35");
        Test("acdefghi", "35");
        Test("cdegi", "15,24,35");
        Test("bcdegi", "24");
        Test("afh", "14,15,16,24,25,26,34,35,36");
        Test("abfh", "14,15,16,24,25,26");
        Test("dfh", "14,15,16,34,35,36");
        Test("cdfh", "15,35");
        Test("deh", "14,15,16,34,35,36");
        Test("cdeh", "15,35");
        Test("abefgh", "24,26");
        Test("abdefgh", "-");
        Test("acfghi", "25,35");
        Test("acdfghi", "35");
        Test("cegi", "15,24,35");
        Test("abcfhi", "15,25");
        Test("abcefhi", "-");
        Test("abdi", "14,15,16,24,34,35,36");
        Test("abdfi", "14,15,16,24");
        Test("bdi", "14,15,16,24,34,35,36");
        Test("bdfi", "14,15,16,24");
        Test("adfh", "14,15,16,34,35,36");
        Test("adfgh", "34,35,36");
        Test("acdfhi", "15,35");
        Test("bcdfgi", "24");
        Test("bcdfghi", "-");
        Test("defi", "14,15,16,24,34,35,36");
        Test("defhi", "14,15,16,34,35,36");
        Test("cdefg", "15,24,26,35");
        Test("cdefgi", "15,24,35");
        Test("bdefg", "24,26");
        Test("bdefgi", "24");
    }

    static void Test(string input, string expected)
    {
        var actual = Solve(input);
        var success = (expected == actual);
        Console.WriteLine(success ? "Success" : "Failure");
    }

    static string Solve(string input)
    {
        var results = allRoutes
            .Where(p => p.All(x => !input.Contains(x)))
            .Select(x => new string(new[] { x.First(), x.Last() }))
            .OrderBy(x => x)
            .Distinct();
        var result = string.Join(",", results);
        return (result == "") ? "-" : result;
    }

    static IEnumerable<ImmutableStack<char>> allRoutes = Graph.Empty
        .Add(' ', '1').Add(' ', '2').Add(' ', '3')
        .Add('1', 'a').Add('a', 'b').Add('b', 'c').Add('c', '4')
        .Add('2', 'd').Add('d', 'e').Add('e', '5')
        .Add('3', 'f').Add('f', 'g').Add('g', 'h').Add('h', 'i').Add('i', '6')
        .Add('1', 'g').Add('b', '5').Add('c', '6')
        .Add('2', 'h').Add('d', 'c')
        .Add('3', 'b').Add('g', 'e').Add('g', 'c').Add('h', '4')
        .TraverseFrom(' ')
        .ToArray();
}

// DAG
struct Graph
{
    public static readonly Graph Empty =
      new Graph(ImmutableDictionary<char, IImmutableSet<char>>.Empty);

    private ImmutableDictionary<char, IImmutableSet<char>> graph;

    private Graph(ImmutableDictionary<char, IImmutableSet<char>> graph)
    {
        this.graph = graph;
    }

    public Graph Add(char node)
    {
        if (graph.ContainsKey(node))
            return this;
        return new Graph(graph.Add(node, ImmutableHashSet<char>.Empty));
    }

    public Graph Add(char from, char to)
    {
        var g = this.Add(from).Add(to);
        return new Graph(
          g.graph.SetItem(
            from,
            g.graph[from].Add(to)));
    }

    public IImmutableSet<char> Edges(char node)
    {
        return graph.ContainsKey(node) ?
          graph[node] :
          ImmutableHashSet<char>.Empty;
    }

    public IEnumerable<ImmutableStack<char>> TraverseFrom(char start)
    {
        var edges = Edges(start);
        if (edges.Count == 0)
        {
            yield return ImmutableStack<char>.Empty;
        }
        else
        {
            foreach (var node in edges)
                foreach (var path in TraverseFrom(node))
                    yield return path.Push(node);
        }
    }
}