using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Threading;
using System.Threading.Tasks;

namespace ConsoleApplication8 {
    class Program {
        static uint[][] _lchecks; // bitmasks for sets of 6 progressive checks involving more than one u32 segment
        static readonly uint[] U32Strings = new uint[437502481]; // all valid 32 bit strings that don't trigger an invalid bit within the next 6 and have high order bit 0

        static void Main(string[] args) {
            var checks = GenerateChecks().ToArray();
            Array.Sort(checks);
            int i;
            var sChecks = GetShortChecks(checks, out i);
            var iChecks = GetIntChecks(checks, ref i);
            _lchecks = GetMultipleQuadChecks(checks, i);

            var local = U32Strings;
            int c = 0;
            foreach (var u in Valid32BitStrings(sChecks, iChecks)) {
                local[c] = u;
                if (c % 1000000 == 0) Console.WriteLine(c);
                c++;
            }

            Console.WriteLine(c);
//            Dive(0x60d11de1);
            var opts = new ParallelOptions {MaxDegreeOfParallelism = 6};
            Parallel.ForEach(local, opts, Dive);
        }

        private static int total = 0;
        [ThreadStatic]
        private static long N = 0;
        private static void Dive(uint prefix) {
            var max = Dive(new List<uint> {prefix}, 1, 0);
            Interlocked.Increment(ref total);
            Console.WriteLine("{0} : {1:x8} : {2}", total, prefix, max);
        }

        private static int Dive(List<uint> canvas, int count, int lcheckLower) {
            N++;
//            int b = 0;
            int max = count;
            int lcheckUpper;
            uint checkIfAny0;
            uint checkIfAny1;
            uint[] checkIfAll0;
            uint[] checkIfAll1;
            if (!ProduceBitmaskChecks(canvas, count, lcheckLower, out lcheckUpper, out checkIfAny0, out checkIfAll0, out checkIfAny1, out checkIfAll1)) return max;
            var u32 = U32Strings;
            if (checkIfAny0 <= int.MaxValue) {
                foreach (var subsequence in u32) {
                    if ((subsequence & checkIfAny1) != 0) continue;
                    var inverted = ~subsequence;
                    if ((inverted & checkIfAny0) != 0) continue;
                    foreach (var mask in checkIfAll1) {
                        if ((subsequence & mask) == mask) {
                            goto next;
                        }
                    }
                    foreach (var mask in checkIfAll0) {
                        if ((inverted & mask) == mask) {
                            goto next;
                        }
                    }

                    canvas.Add(subsequence);
//                    b++;
                    max = Math.Max(max, Dive(canvas, count + 1, lcheckUpper));
                    canvas.RemoveAt(count);
                    next:
                    continue;
                }
            }
            if (checkIfAny1 <= int.MaxValue) {
                foreach (var inverted in u32) {
                    var subsequence = ~inverted;
                    if ((subsequence & checkIfAny1) != 0) continue;
                    if ((inverted & checkIfAny0) != 0) continue;
                    foreach (var mask in checkIfAll1) {
                        if ((subsequence & mask) == mask) {
                            goto next;
                        }
                    }
                    foreach (var mask in checkIfAll0) {
                        if ((inverted & mask) == mask) {
                            goto next;
                        }
                    }

                    canvas.Add(subsequence);
//                    b++;
                    max = Math.Max(max, Dive(canvas, count + 1, lcheckUpper));
                    canvas.RemoveAt(count);
                    next:
                    continue;
                }
            }
//            if (b == 0) {
//                var value = string.Join("", canvas.Select(x => $"{x:x8}"));
//                using (var x = File.OpenWrite(value + ".txt")) {
//                    using (var writer = new StreamWriter(x))
//                    {
//                        writer.WriteLine("any 0: {0:X8}", checkIfAny0);
//                        writer.WriteLine("all 0:");
//                        foreach (var mask in checkIfAll0)
//                        {
//                            writer.WriteLine("{0:x8}", mask);
//                        }
//                        writer.WriteLine("any 1: {0:X8}", checkIfAny1);
//                        writer.WriteLine("all 1:");
//                        foreach (var mask in checkIfAll1)
//                        {
//                            writer.WriteLine("{0:x8}", mask);
//                        }
//                    }
//                }
//            }
            return max;
        }

        private static bool ProduceBitmaskChecks(List<uint> canvas, int count, int lcheckLower, out int lcheckUpper, out uint checkIfAny0, out uint[] acheckIfAll0, out uint checkIfAny1, out uint[] acheckIfAll1) {
            var lchecks = _lchecks;
            lcheckUpper = 0;
            List<uint> checkIfAll0 = new List<uint>();
            checkIfAny0 = 0;
            List<uint> checkIfAll1 = new List<uint>();
            checkIfAny1 = 0;
            acheckIfAll0 = null;
            acheckIfAll1 = null;
            for (int i = lcheckLower; i < lchecks.Length; i++) {
                var bitmask = lchecks[i];
                if (bitmask.Length > count + 1) {
                    // done computing necessary checks at this depth
                    lcheckUpper = i;
                    break;
                }
                var check0 = true;
                var check1 = true;
                for (int j = 0; j < canvas.Count && (check0 || check1); j++) {
                    var subsequence = canvas[j];
                    var mask = bitmask[j];
                    check0 = check0 && (~subsequence & mask) == mask;
                    check1 = check1 && (subsequence & mask) == mask;
                }
                var finalmask = bitmask[count];
                var singlebit = (finalmask & (finalmask - 1)) == 0;
                if (check0) {
                    if (singlebit) {
                        checkIfAny0 = checkIfAny0 | finalmask;
                    } else {
                        checkIfAll0.Add(finalmask);
                    }
                }
                if (check1) {
                    if (singlebit) {
                        checkIfAny1 = checkIfAny1 | finalmask;
                    } else {
                        checkIfAll1.Add(finalmask);
                    }
                }
            }
            if (lcheckUpper == 0) {
                //todo: call out to another function to handle bit strings that are within 32 bits of maximum length
                //last 32 bits handled special
                var value = string.Join("", canvas.Select(x => $"{x:x8}"));
                Console.WriteLine(value);
                return false;
            }
            if (count > 5) {
                // this is completely arbitrary
                var value = string.Join("", canvas.Select(x => $"{x:x8}"));
                UpdateLongest(value);
            }
            // if any single must not be 1 and must not be 0 at the same time, no need to do any of this
            if ((checkIfAny0 & checkIfAny1) != 0) {
                return false;
            }
            // remove covering checks, ex:
            // *.1.1.1.1
            // *.1.1
            // you cannot match the first without also matching the second, so no need for the first check
            acheckIfAll0 = ReduceChecks(checkIfAll0, checkIfAny0);
            acheckIfAll1 = ReduceChecks(checkIfAll1, checkIfAny1);


            foreach (var mask in checkIfAll1) {
                // given mask
                // *.1.1
                // if all are 1, test will fail
                // if any are 0 test will pass
                // thus if all mask bits are in the any0 mask, that test will fail
                if ((checkIfAny0 & mask) == mask) goto fls;
            }
            foreach (var mask in checkIfAll0) {
                if ((checkIfAny1 & mask) == mask) goto fls;
            }
            return true;
            fls:
            return false;
        }

        private static uint[] ReduceChecks(List<uint> list, uint singles) {
            var remove = new bool[list.Count];
            var any = false;
            for (int i = 0; i < list.Count; i++) {
                var c = list[i];
                if ((c & singles) != 0) {
                    //if a single bit covers this mask it will also cover any mask that this mask covers
                    remove[i] = true;
                    any = true;
                    //so no need to do the inner loop
                    continue;
                }
                for (int j = i + 1; j < list.Count; j++) {
                    var d = list[j];
                    var u = c & d;
                    if (u == c) {
                        // if all bits in c are also in d then d is unnecessary
                        remove[j] = true;
                        any = true;
                    } else if (u == d) {
                        // and the reverse
                        remove[i] = true;
                        any = true;
                    }
                }
            }

            if (any) {
                var temp = new List<uint>(list.Count);
                for (int i = 0; i < list.Count; i++) {
                    if (!remove[i]) {
                        temp.Add(list[i]);
                    }
                }
                return temp.ToArray();
            }
            return list.ToArray();
        }

        static readonly object l = new object();
        private static string longest = "";

        private static void UpdateLongest(string value) {
            Console.WriteLine(N);
            if (value.Length > longest.Length) {
                lock (l) {
                    if (value.Length > longest.Length) {
                        longest = value;
                        Console.WriteLine(longest.Length + " : " + longest);
                    }
                }
            }
        }

        private static IEnumerable<uint> Valid32BitStrings(ushort[] sChecks, uint[] iChecks) {
            var u16Strings = Valid16BitStrings(sChecks);
            var hu16Strings = u16Strings.Select(b => (uint) b << 16).TakeWhile(b => b <= int.MaxValue).ToArray();
            uint[] testForce32 = new uint[] {
                0x2082083F, // if a string masked by this ...
                0x218A4A30,
                0x10C52518,
                0x0862928C,
                0x04314946,
                0x0218A4A3,
                0x81031519,
                0x81230C4A,
                0x40918625,
                0x8512450C,
                0x42892286,
                0x21449143
            };
            uint[] checkForce32 = new uint[] {
                0x0000001F, // ... equals this, the next bit in the progression identified here
                0x01084210, // cannot be either 0 or 1
                0x00842108,
                0x00421084,
                0x00210842,
                0x00108421,
                0x81020408,
                0x81020408,
                0x40810204,
                0x81020408,
                0x40810204,
                0x20408102
            };
            foreach (var high in hu16Strings) {
                foreach (var low in u16Strings) {
                    var b = high + low;
                    var nb = ~b;
                    bool g = true;
                    foreach (var check in iChecks) {
                        if ((b & check) == check) {
                            g = false;
                            break;
                        }
                        if ((nb & check) == check) {
                            g = false;
                            break;
                        }
                    }
                    if (g) {
                        for (int i = 0; i < testForce32.Length; i++) {
                            if ((b & testForce32[i]) == checkForce32[i])
                            {
                                g = false;
                                break;
                            }
                            if ((nb & testForce32[i]) == checkForce32[i])
                            {
                                g = false;
                                break;
                            }
                        }
                    }
                    if (g) {
                        // these sequences prevent one of the next 6 bits from being either 0 or 1
                        yield return b;
                    }
                }
            }
        }

        private static ushort[] Valid16BitStrings(ushort[] sChecks) {
            List<ushort> good = new List<ushort>();
            for (ushort b = 0; b < ushort.MaxValue; b++) {
                bool g = true;
                var nb = ~b;
                foreach (var check1 in sChecks) {
                    if ((b & check1) == check1) {
                        g = false;
                        break;
                    }
                    if ((nb & check1) == check1) {
                        g = false;
                        break;
                    }
                }
                if (g) {
                    good.Add(b);
                    if (good.Count % 10 == 0) Console.WriteLine("{0}, {1:x}", good.Count, b);
                }
            }
            Console.WriteLine(good.Count);
            return good.ToArray();
        }

        private static uint[][] GetMultipleQuadChecks(BigInteger[] checks, int i) {
            // checks larger than uint.MaxValue are initially stored in BigInteger values and we need them in uint[] arrays
            // BigInteger provides a method that returns the underlying bytes but they are in the wrong order if we
            // simply reinterpreted the array... given a big endian BigInteger stored like this:
            // hgfedcba87654321
            // we need this (little endian):
            // 12345678abcdefgh
            // ToByteArray returns this:
            // 87654321hgfedcba
            // (each byte is big endian, byte array is little endian)
            List<uint[]> lchecks = new List<uint[]>();
            for (; i < checks.Length; i++) {
                var bytes = checks[i].ToByteArray();
                if (bytes.Length < 5) {
                    throw new Exception("program failure; int check discovered where longer check expected");
                }

                var s = new List<uint>();
                for (int j = 0; j < bytes.Length; j += 4) {
                    uint u1 = j + 3 < bytes.Length ? ReverseBits(bytes[j + 3]) : 0;
                    uint u2 = j + 2 < bytes.Length ? ReverseBits(bytes[j + 2]) << 8 : 0;
                    uint u3 = j + 1 < bytes.Length ? ReverseBits(bytes[j + 1]) << 16 : 0;
                    uint u4 = ReverseBits(bytes[j]) << 24;
                    s.Add(u1 + u2 + u3 + u4);
                }
                if (s[s.Count - 1] == 0) {
                    // remove the extra sign byte that occurs if bytes[bytes.Length-1]>128 && bytes.Length % 4 = 1
                    s.RemoveAt(s.Count - 1);
                }

                // any bitmask that fits inside a single uint is unnecessary because such a result wouldn't be returned from Valid32BitStrings
                if (s.Where(s1 => s1 != 0).Take(2).Count() == 1) continue;
                lchecks.Add(s.ToArray());
            }
            var multipleQuadChecks = lchecks.ToArray();
            return multipleQuadChecks;
        }

        static uint ReverseBits(byte a) {
            return (uint) (((a & 0x1) << 7) | ((a & 0x2) << 5) |
                           ((a & 0x4) << 3) | ((a & 0x8) << 1) |
                           ((a & 0x10) >> 1) | ((a & 0x20) >> 3) |
                           ((a & 0x40) >> 5) | ((a & 0x80) >> 7));
        }

        private static uint[] GetIntChecks(BigInteger[] checks, ref int i) {
            List<uint> iChecks = new List<uint>();
            while (checks[i] < uint.MaxValue) {
                var item = (uint) checks[i];
                if ((item & ushort.MaxValue) != 0) {
                    //we only care about the ones with low bits set (if no low bits are set, the high bits were checked already)
                    iChecks.Add(item);
                }
                i++;
            }
            return iChecks.ToArray();
        }

        private static ushort[] GetShortChecks(BigInteger[] checks, out int i) {
            i = 0;
            List<ushort> sChecks = new List<ushort>();
            while (checks[i] < ushort.MaxValue) {
                sChecks.Add((ushort) checks[i]);
                i++;
            }
            return sChecks.ToArray();
        }

        static IEnumerable<BigInteger> GenerateChecks() {
            BigInteger max = BigInteger.Pow(2, 1134);
            //n ^ 5 + n ^ 4 + n ^ 3 + n ^ 2 + n + 1
            BigInteger n = 2;
            do {
                var n2 = n * n;
                var n3 = n2 * n;
                var n4 = n3 * n;
                var n5 = n4 * n;
                if (n5 > max) yield break;
                var check = n5 + n4 + n3 + n2 + n + 1;
                while (check < max) {
                    yield return check;
                    check <<= 1;
                }
                n <<= 1;
            } while (true);
        }
    }
}