using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("-------------");

        SortTest();

        AnagramTest();

        ListNodeReverseRecursiveTest();

        ListNodeReverseDirectTest();

    }

    public static void SortTest()

    {

        Console.WriteLine("Sorting");

        var range = new[] {1, 342, 3523, 123, 646, -564};

        Array.ForEach(range, x => Console.Write(x + ", "));

​

        Console.WriteLine("\nSorted:");

        range.QuickSort(x => x).ToList().ForEach(x => Console.Write(x + ", "));

​

        Console.WriteLine("\n-------------");

    }

​

    public static void AnagramTest()

    {

        Console.WriteLine("Searching anagrams");

​

        var str1 = new[] { "abc", "bac", "cab", "wsr", "rsw", "bca", "bvc", "cvb", "no"};

        var t = str1.FindAnagrams();

​

        Array.ForEach(str1, x => Console.Write(x + ", "));

        Console.WriteLine("\nAnagrams:");

​

        foreach (var list in t)

        {

            foreach (var s in list)

            {

                Console.Write(s + ", ");

            }

​

            Console.WriteLine();

        }

​

        Console.WriteLine("-------------");

    }

​

    public static void ListNodeReverseRecursiveTest()

    {

        Console.WriteLine("Recursive reversing");

        var range = Enumerable.Range(0, 10).ToList();

​

        var directNode = new ImmutableLinkedListNode<int>(range);

​

        PrintListNode(directNode);

        PrintListNode(directNode.ReverseRecursive());

​

        Console.WriteLine("-------------");

    }

​

    public static void ListNodeReverseDirectTest()

    {

        Console.WriteLine("Non-recursive reversing");

        var range = Enumerable.Range(0, 10).ToList();

​

        var directNode = new ImmutableLinkedListNode<int>(range);

​

        PrintListNode(directNode);

        PrintListNode(directNode.ReverseDirect());

​

        Console.WriteLine("-------------");

    }

​

    private static void PrintListNode(ImmutableLinkedListNode<int> head)

    {

        while (head != null)

        {

            Console.Write(head.Value + ", ");

            head = head.Next;

        }

​

        Console.WriteLine();

    }

}

​

public class ImmutableLinkedListNode<T>

{

    public ImmutableLinkedListNode(T value, ImmutableLinkedListNode<T> next)

    {

        Value = value;

        Next = next;

    }

    public ImmutableLinkedListNode(IReadOnlyList<T> source)

    {

        var prev = new ImmutableLinkedListNode<T>(source.Last(), null);

        for (var i = source.Count - 1; i > 0; i--)

        {

            prev = new ImmutableLinkedListNode<T>(source[i - 1], prev);

        }

        Value = prev.Value;

        Next = prev.Next;

    }

    public T Value { get; private set; }

    public ImmutableLinkedListNode<T> Next { get; private set; }

    public ImmutableLinkedListNode<T> ReverseRecursive()

    {

        return ReverseImpl(this, null);

    }

    private static ImmutableLinkedListNode<T> ReverseImpl(

        ImmutableLinkedListNode<T> current,

        ImmutableLinkedListNode<T> prev)

    {

        var revNode = new ImmutableLinkedListNode<T>(current.Value, prev);

        return current.Next == null ? revNode : ReverseImpl(current.Next, revNode);

    }

    public ImmutableLinkedListNode<T> ReverseDirect()

    {

        var revNode = new ImmutableLinkedListNode<T>(Value, null);

        for (var i = Next; i != null; i = i.Next)

        {

            revNode = new ImmutableLinkedListNode<T>(i.Value, revNode);

        }

        return revNode;

    }

}

​

public static class Sorter

{

    public static IEnumerable<T> QuickSort<T, TKey>(this IEnumerable<T> source, Func<T, TKey> selector)

    {

        return QuickSort(source, selector, Comparer<TKey>.Default);

    }

    public static IEnumerable<T> QuickSort<T, TKey>(IEnumerable<T> source, Func<T, TKey> selector, IComparer<TKey> comparer)

    {

        var values = source.ToList();

        if (!values.Any())

        {

            return new List<T>();

        }

        //split the list into the first element and the rest

        var firstElement = selector(values.First());

        var rest = values.Skip(1).ToList();

        //get the smaller and larger elements

        var smallerElements = rest

            .Where(x => comparer.Compare(selector(x), firstElement) < 0)

            .QuickSort(selector);

        var largerElements = rest

            .Where(x => comparer.Compare(selector(x), firstElement) >= 0)

            .QuickSort(selector);

        //return the result

        return smallerElements

            .Concat(new List<T> {values.First()})

            .Concat(largerElements);

    }

}

​

​

public static class Anagram

{

    public static IReadOnlyList<IReadOnlyList<string>> FindAnagrams(this IReadOnlyList<string> source)

    {

        return source

            .GroupBy(s => s.Length)

            .Where(g => g.Key > 1)

            .SelectMany(g => g.GroupBy(s => s.OrderBy(c => c), CharSequenceComparer.Instance)

                        .Where(g1 => g1.ElementAtOrDefault(1) != null) // Count > 1

                        .Select(g1 => g1.ToList()))

            .ToList();

    }

    private class CharSequenceComparer : IEqualityComparer<IEnumerable<char>>

    {

        public static readonly CharSequenceComparer Instance = new CharSequenceComparer();

        private CharSequenceComparer()

        {

        }

        public bool Equals(IEnumerable<char> x, IEnumerable<char> y)

        {

            return x.SequenceEqual(y);

        }

        public int GetHashCode(IEnumerable<char> obj)

        {

            // will always call Equals

            return 0;

        }

    }

}

​