// C# で解く「なぜ関数プログラミングは重要か」
// H27.1/15 SUZUKI Hisao
// cf. http://www.sampou.org/haskell/article/whyfp.html

using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

// 5. 人工知能からの例
static class WhyFp5
{
    // ラベル付き順序ツリー
    class Tree<T> {
        public readonly T Label;
        public readonly IEnumerable<Tree<T>> Subtrees;

        public Tree(T x, IEnumerable<Tree<T>> y) {
            Label = x;
            // if (y != null) y = new Cached<Tree<T>>(y);
            Subtrees = y;
            // Console.WriteLine(" -- Tree({0}, {1})", x,
            //                   (y == null) ? 0 : y.GetHashCode()); 
        }

        public R Reduce<U, R>
            (Func<T, U, R> f, Func<IEnumerable<R>, U> g, U a) {
            if (Subtrees == null) {
                return f(Label, a);
            } else {
                IEnumerable<R> yy = Subtrees.Select(t => t.Reduce(f, g, a));
                U b = g(yy);
                return f(Label, b);
            }
        }
    }


    static Tree<R> maptree<T, R>(Func<T, R> f, Tree<T> tree) {
        return tree.Reduce((x, yy) => new Tree<R>(f(x), yy),
                           yy => yy,
                           (IEnumerable<Tree<R>>) null);
    }


    // 一度評価した値をキャッシュする列 (≒ lazy list)
    class Cached<T>: IEnumerable<T> {
        List<T> cache = new List<T>();
        IEnumerator<T> generator;
        int index = -1;         // generator で生成した値の添え字位置

        public Cached(IEnumerable<T> sequence) {
            generator = sequence.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }

        // 注意: 要素の評価時に this を lock する。
        public IEnumerator<T> GetEnumerator() {
            for (int i = 0;; i++) {
                T e;
                lock (this) {
                    if (i <= index) {
                        e = cache[i];
                    } else {
                        if (! generator.MoveNext())
                            break;
                        e = generator.Current;
                        cache.Add(e);
                        index++;
                    }
                }
                yield return e;
            }
        }
    }

    // 三目並べの 1 状態
    class Position {
        private int[] board = new int[9];
        /* 0 1 2
           3 4 5
           6 7 8 の各添え字位置が -1 なら x, 0 なら空き, +1 なら o
         */

        public Position() {}

        public Position(int[] otherBoard) {
            for (int i = 0; i < 9; i++)
                board[i] = otherBoard[i];
        }

        public override string ToString() { // "xx_|_o_|__" など
            var sb = new System.Text.StringBuilder();
            for (int i = 0; i < 9; i++) {
                if (i == 3 || i == 6)
                    sb.Append('|');
                int e = board[i];
                char ch = (e == -1) ? 'x' : (e == 1) ? 'o' : '_';
                sb.Append(ch);
            }
            return sb.ToString();
        }

        // 可能な次の局面の列を返す。先手を x とする。
        public IEnumerable<Position> moves() {
            int count = board.Select(e => (e == 0) ? 0 : 1).Sum();
            int teban = (count % 2 == 0) ? -1 : 1; // 偶数なら x の手番
            if (evalFor(-teban) == 20) {
                // Console.WriteLine("  {0} --> #", this);
                yield break;    // 相手に詰まされているなら何も打たない。
            }
            for (int i = 0; i < 9; i++) {
                if (board[i] == 0) { // 空いた場所に打った局面を次々に返す。
                    Position next = new Position(board);
                    next.board[i] = teban;
                    // Console.WriteLine("  {0} --> {1}", this, next);
                    yield return next;
                }
            }
        }

        public int staticEval() { // 静的評価: マイナスならば x 優勢
            return evalFor(1) - evalFor(-1);
        }

        // 詰みになる配置
        private int[][] lines = {
            new int[]{0, 3, 6}, new int[]{1, 4, 7}, new int[]{2, 5, 8},
            new int[]{0, 1, 2}, new int[]{3, 4, 5}, new int[]{6, 7, 8},
            new int[]{0, 4, 8}, new int[]{2, 4, 6}
        };

        // 手番に対する評価値 (詰みで勝っているならば 20)
        private int evalFor(int teban) {
            int r = 0;
            foreach (var line in lines) {
                int score = 0;
                foreach (int i in line) {
                    int e = board[i];
                    if (e == teban)
                        score += 1;
                    else if (e == -teban) // 線上に相手のコマがあればダメ
                        goto EXIT;
                }
                if (score == 3)
                    return 20;  // 詰み
                r += score;     // あと1手または2手打てれば詰み
                EXIT:;
            }
            return r;
        }
    }

    static Tree<T> reptree<T>(Func<T, IEnumerable<T>> f, T a) {
        var seq = f(a);
        if (seq == null) {
            return new Tree<T>(a, null);
        } else {
            return new Tree<T>(a, seq.Select(e => reptree(f, e)));
        }
    }

    static Tree<Position> gametree(Position p) {
        return reptree(pos => pos.moves(), p);
    }

    static int maximise(Tree<int> tree) {
        if (tree.Subtrees == null) {
            return tree.Label;
        } else {
            var m = tree.Subtrees.Select(minimise);
            try {
                return m.Max();
            } catch (InvalidOperationException) { // m has no elements
                return tree.Label;
            }
        }
    }

    static int minimise(Tree<int> tree) {
        if (tree.Subtrees == null) {
            return tree.Label;
        } else {
            var m = tree.Subtrees.Select(maximise);
            try {
                return m.Min();
            } catch (InvalidOperationException) { // m has no elements
                return tree.Label;
            }
        }
    }

    static Tree<T> prune<T>(int n, Tree<T> tree) {
        if (n == 0 || tree.Subtrees == null) {
            return new Tree<T>(tree.Label, null);
        } else {
            return new Tree<T>(tree.Label,
                               tree.Subtrees.Select(t => prune(n - 1, t)));
        }
    }

    static int evaluate_v1(Position pos) {
        var g = prune(5, gametree(pos)); // 5 手まで先を読む
        var m = maptree(p => p.staticEval(), g);
        return maximise(m);
    }

    static IEnumerable<int> maximise_dash(Tree<int> tree) {
        if (tree.Subtrees == null) {
            yield return tree.Label;
        } else {
            bool empty = true;
            foreach (int i in mapmin(tree.Subtrees.Select(minimise_dash))) {
                empty = false;
                yield return i;
            }
            if (empty)          // Subtrees が空リストだったならば
                yield return tree.Label;
        }
    }

    static IEnumerable<int> minimise_dash(Tree<int> tree) {
        if (tree.Subtrees == null) {
            yield return tree.Label;
        } else {
            bool empty = true;
            foreach (int i in mapmax(tree.Subtrees.Select(maximise_dash))) {
                empty = false;
                yield return i;
            }
            if (empty)
                yield return tree.Label;
        }
    }

    static IEnumerable<int> mapmin(IEnumerable<IEnumerable<int>> numss) {
        bool isFirst = true;
        int pot = 0;
        foreach (var ii in numss) {
            var nums = ii;
            if (isFirst) {
                isFirst = false;
            } else {
                nums = new Cached<int>(nums); // Any と Min で使われるから
                if (nums.Any(i => (i <= pot)))
                    continue;
            }
            pot = nums.Min();
            yield return pot;
        }
    }

    static IEnumerable<int> mapmax(IEnumerable<IEnumerable<int>> numss) {
        bool isFirst = true;
        int pot = 0;
        foreach (var ii in numss) {
            var nums = ii;
            if (isFirst) {
                isFirst = false;
            } else {
                nums = new Cached<int>(nums);
                if (nums.Any(i => (i >= pot)))
                    continue;
            }
            pot = nums.Max();
            yield return pot;
        }
    }

    static int evaluate_v2(Position pos) {
        var g = prune(8, gametree(pos));
        var m = maptree(p => p.staticEval(), g);
        return maximise_dash(m).Max();
    }

    static Tree<int> highfirst(Tree<int> tree) {
        if (tree.Subtrees == null) {
            return tree;
        } else {
            var subtrees = tree.Subtrees.Select(lowfirst)
                .OrderByDescending(t => t.Label);
            return new Tree<int>(tree.Label, subtrees);
        }
    }

    static Tree<int> lowfirst(Tree<int> tree) {
        if (tree.Subtrees == null) {
            return tree;
        } else {
            var subtrees = tree.Subtrees.Select(highfirst)
                .OrderBy(t => t.Label);
            return new Tree<int>(tree.Label, subtrees);
        }
    }

    static int evaluate_v3(Position pos) {
        var g = prune(8, gametree(pos));
        var m = maptree(p => p.staticEval(), g);
        return maximise_dash(highfirst(m)).Max();
    }


    static Tree<T> taketree<T>(int n, Tree<T> tree) {
        return tree.Reduce((x, yy) => new Tree<T>(x, yy),
                           yy => yy.Take(n),
                           (IEnumerable<Tree<T>>) null);
    }

    static int evaluate_v4(Position pos) {
        var g = prune(8, gametree(pos));
        var m = maptree(p => p.staticEval(), g);
        return maximise_dash(taketree(3, highfirst(m))).Max();
    }

    static void Main() {
       Console.WriteLine(new Position()); // => ___|___|___
       Console.WriteLine(new Position().staticEval()); // => 0

       var pos = new Position(new int[]{-1, 1, 0,  0, -1, 0, 0, 0, 0});
       Console.WriteLine("{0}: {1}", pos, evaluate_v1(pos));
       Console.WriteLine("{0}: {1}", pos, evaluate_v2(pos));
       Console.WriteLine("{0}: {1}", pos, evaluate_v3(pos));
       // => xo_|_x_|___: -18

       foreach (var p in new Position().moves()) {
           Console.WriteLine("{0}: {1}", p, evaluate_v4(p));
       }
       /* =>
         x__|___|___: 0
         _x_|___|___: 0
         __x|___|___: 0
         ___|x__|___: 0
         ___|_x_|___: 0
         ___|__x|___: 0
         ___|___|x__: 0
         ___|___|_x_: 0
         ___|___|__x: 0
       */
    }
}