using System; using System.Collections.Generic; using System.Drawing; using System.Linq; namespace PaperFoldingCoord { class Program { static void Main(string[] args) { HashSet oldVisited = new HashSet(); HashSet visited = new HashSet(); HashSet visiting = new HashSet(); visiting.Add(Point.Empty); for (int n=0; ; n++) { Console.WriteLine($"{n} {visiting.Count}"); if (visiting.Any(p => Math.Max(p.X, p.Y)==Max)) { break; } else { oldVisited = visited; visited = visiting; HashSet newVisiting = new HashSet(); foreach (Point p in visiting) { foreach (Point q in Neighbours(p)) { Point r = Follow(p, q); if (!visited.Contains(r) && !oldVisited.Contains(r)) { newVisiting.Add(r); } } } visiting = newVisiting; } } } static Point Follow(Point p, Point q) { while (true) { Point[] r = Neighbours(q).ToArray(); if (r.Length==1 || r.Length==3) { return q; } else if (r[0]==p) { p = q; q = r[1]; } else if (r[1] == p) { p = q; q = r[0]; } } } static IEnumerable Neighbours(Point p) { if (Right(p)) { yield return new Point(p.X + 1, p.Y); } if (Up(p)) { yield return new Point(p.X, p.Y + 1); } if (Left(p)) { yield return new Point(p.X - 1, p.Y); } if (Down(p)) { yield return new Point(p.X, p.Y - 1); } } // Right - left - up - down point connected to point at p? static bool Right(Point p) { if (p.X < 0 || p.Y < 0) { return false; } else if (p.Y == 0) { return true; } else { return (p.X >> val2[p.Y]) % 2 != pf[p.Y]; } } static bool Left(Point p) { return Right(new Point(p.X - 1, p.Y)); } static bool Up(Point p) { if (p.X < 0 || p.Y < 0) { return false; } else if (p.X == 0) { return true; } else { return (p.Y >> (val2[p.X] + 1)) % 2 != pf[p.X]; } } static bool Down(Point p) { return Up(new Point(p.X, p.Y - 1)); } const int N = 14; // maximum number of double-folds const int Max = 1 << N; static readonly int[] val2 = new int[Max + 1]; // 2-adic valuation ~ A007814 static readonly int[] pf = new int[Max + 1]; // regular paper-folding sequence ~ A014577 with a leading 0 static readonly int[] bits = new int[Max + 1]; // number of bits ~ A070939 with a(0) = 0 static Program() { val2[0] = int.MaxValue; pf[0] = 0; bits[0] = 0; for (int n = 1; n <= Max; n++) { int m = n; while (m % 2 == 0) { val2[n]++; m /= 2; } if ((m & 2) == 0) { pf[n] = 1; } if (n == 1) { bits[n] = 1; } else { bits[n] = 1 + bits[n / 2]; } } } } }