using System; using System.Collections; using System.Collections.Generic; using System.Text; using System.IO; using System.Diagnostics; /* Implementation of A285471. A labyrinth-sequence where the entry is the first digit of the sequence and the exit at infinity. (How to move in the labyrinth is explained in the Comments and Example sections). 1, 3, 0, 5, 7, 9, 2, 20, 13, 15, 4, 18, 31, 38, 33, 35, 21, 8, 34, 37, 23, 17, 19, 6, 11, 78, 28, 50, 51, 25, 61, 39, 29, 81, 10, 16, 53, 27, 80, 14, 55, 57, 22, 59, 83, 30, 58, 85, 65, 12, 43, 70, 40, 71, 32, 52, 41, 73, 45, 47, 72, 42, 75, 49, 24, 54, 77 To move in the labyrinth is easy: - you jump to the right over "o" digits when the digit is odd; - you jump to the left over "e" digits when the digit is even. */ namespace A285471 { class A285471Code { static void Main(string[] args) { int nTerms = 0; string line; Algorithm alg; while (true) { Console.WriteLine("Be aware that above 800 terms, the progress slows down considerably."); Console.WriteLine("The number of terms calculated so far is printed during the execution."); Console.Write("Enter wanted # of terms> "); line = Console.ReadLine(); try { nTerms = int.Parse(line); break; } catch (Exception) { Console.WriteLine("Illegal input!"); } } alg = new Algorithm(); alg.BT(nTerms); Console.Write("Finished (press Enter)..."); Console.ReadLine(); } /* Since there is the lexicographic constraint, I decided to let the selection of terms govern the algorithm and the labyrinth creation follows from that. Doing it the other way around (building the labyrinth and then fulfill the lexicographic contraint) seems to be much more complicated, if at all possible. In general the path of the labyrinth will wind up and down like this A B C D E F >-----------|-----------v v-----|-----------< >-----|------v v--------|------< >--------|----------------... The vertical bar represents the current state of the algorithm. The algorithm starts a path in A with one outgoing path. Digits (odd ones) are successfully added until B is reached when a digit can NOT be added to A. The this digit is inserted with new ingoing and outgoing paths are created. Again two new paths are created in C. When D is reached an outgoing path is concatenated to another ingoing path, and in E this happens once again and the have a single path passing through F. Of course there are several rules that must be obeyed for the paths such as: digits can belong to just one path, no loops, etc. */ #region Algorithm class Algorithm { #region Backtracking public void BT(int nTerms) { BTData data = new BTData(); data.nTerms = nTerms; BTLabyrinth bt = new BTLabyrinth(data); BTItem item; OneTurn turn; // The first value is forced and has only an outgoing path BTData.bt = bt; item = new BTItem(); item.v = 1; turn = new OneTurn(0, true); item.turns.Add(turn); bt.Init(item); bt.Go(); } /* STRATEGY: Terms are selected and stacked and backtracked. But when a term is selected, all the digits must be checked for compatibility, otherwise a new unused term value must be selected. Also note that backing up always gives a lexicographically later sequence so if at all possible we must try to find a value for the current term. The naive approach is to just keep selecting larger numbers. But it may happen that NO number is ok given the current state, so that we in fact must back up. But how do we determine that a backup is needed? It suffices to note which first digits fail. When all have been seen without success and one of them comes back later, (in a number that contains one more digit, since the canditates are returned in ascending order), we know that it cannot succeed since the unused numbers are returned in ascending order. If 143 fails, then so will 143(0..9). */ public class BTData { static public BTLabyrinth bt; public int nTerms; public ListOfLong a; public UsedLong used; public StringBuilder allDigits; // The characters indexed from 0 int lastNTerms = 0; long nNewItem = 0; long nNextValue = 0; long nCheckOneDigit = 0; Stopwatch st; public BTData() { a = new ListOfLong(); used = new UsedLong(0); allDigits = new StringBuilder(); st = new Stopwatch(); st.Start(); } public void AddTerm(long v) { a.Add(v); used.Use(v); allDigits.Append(v.ToString()); } public void RemoveLastTerm() { int len; len = a.LastItem.ToString().Length; allDigits.Remove(allDigits.Length - len, len); used.UnUse(a.LastItem); a.RemoveLast(); } internal void AddInitialTerm(long v) { a.Add(v); used.Use(v); allDigits.Append(v.ToString()); } // Check that the state is consistent private void CheckConsistency() { StringBuilder sb = new StringBuilder(); foreach (long v in a) { sb.Append(v.ToString()); } if (sb.ToString().IndexOf(allDigits.ToString()) != 0) { throw new InvalidOperationException(); } // An index can not occur in two separate turns or twice within the same turn ListOfLong x = new ListOfLong(); ListOfLong y; AllTurns all = bt.TopItem.turns; foreach (OneTurn t in all) { // Check this turn internally if (t.inIx.HasAnyOf(t.outIx)) { throw new InvalidOperationException(); } if (t.inIx.Has(t.turnIx)) { throw new InvalidOperationException(); } if (t.outIx.Has(t.turnIx)) { throw new InvalidOperationException(); } // Check between turns y = t.GetInAndOutPath(); if (x.HasAnyOf(y)) { throw new InvalidOperationException(); } x.AddRange(y); } } // A new term is requested internal BTItem NewItem(BTItem top) { int ix; BTItem item; long x; int ixFailed; nNewItem++; if (a.Count == nTerms) { bt.stopIt = true; return null; } ix = allDigits.Length; if (TooFar(top.turns, ix)) { return null; // Some in- or out-path is too far away } item = new BTItem(); item.StartIterator(used); // Get next unused number while ((x = item.Next()) >= 0) { // Start with the state for the previous term item.turns = top.turns.Clone(); if (CheckAllDigits(x, item, out ixFailed)) { // Book it and return it AddTerm(x); CheckConsistency(); // Provide some feedback if (a.Count > lastNTerms) { Console.WriteLine(a.Count); lastNTerms = a.Count; } return item; } else { if (ixFailed == 0) { // The first digit fails, so prevent iterator from returning more of it item.AvoidFirstChar(x.ToString()[0]); } //item.Avoid(ixFailed, x.ToString()[ixFailed]); if (item.Avoid2(x.ToString()[0])) return null; } } return null; } internal bool NextValue(BTItem item) { long x; int ixFailed; nNextValue++; RemoveLastTerm(); // Find new value while ((x = item.Next()) >= 0) { // Start with the state for the term before the one we want to replace item.turns = bt.TopItem2.turns.Clone(); if (CheckAllDigits(x, item, out ixFailed)) { // Replace it and return ok AddTerm(x); CheckConsistency(); return true; } else { if (ixFailed == 0) { // The first digit fails, so prevent iterator from returning more of it item.AvoidFirstChar(x.ToString()[0]); } //item.Avoid(ixFailed, x.ToString()[ixFailed]); if (item.Avoid2(x.ToString()[0])) return false; } } return false; } // Check if all digits in 'x' are compatible // if so, 'item.turns' are updated // 'ixFailed' is the index of the digit that failed, or -1 private bool CheckAllDigits(long x, BTItem item, out int ixFailed) { string s; s = x.ToString(); return CheckOneDigit(0, s, item, out ixFailed); } // 'k' is the index to character, 's' is the number as a string bool CheckOneDigit(int k, string s, BTItem item, out int ixFailed) { int ix; int dig; bool b; nCheckOneDigit++; ixFailed = -1; if (k >= s.Length) return true; // Alles ok ix = allDigits.Length - 1; dig = s[k] - '0'; if (Compatible(ix + 1, dig, item.turns)) { allDigits.Append(s[k]); Merge(item.turns, ix + 1, dig); // Check next digit b = CheckOneDigit(k + 1, s, item, out ixFailed); allDigits.Remove(allDigits.Length - 1, 1); return b; } else { ixFailed = k; return false; } } internal void BeforePop(BTItem item) { } // Placing a digit after the current one will cause // an end of an in-path more than 8 steps away, // or the last item (k) in an out-path is more than k steps away // Those can never be connected and so will be left as orphans private bool TooFar(AllTurns turns, int ix) { int k; int dig; foreach (OneTurn t in turns) { if (!t.isMain) { k = t.LastIn; if (ix - k - 1 > 8) return true; } k = t.LastOut; dig = allDigits[k] - '0'; if (ix - k - 1 > dig) return true; } return false; } // t is the one created, p is the previous one // ix is the index to fill, dig is the suggested digit private bool Compatible(int ix, int dig, AllTurns p) { int prevIx; // Previous index when pointing backwards List<OneTurn> tlistIn, tlistOut; prevIx = ix - dig - 1; if ((dig & 1) == 0) // Even { // Points backwards if (prevIx < 0) return false; // Points outside // Check if clashes with existing turns foreach (OneTurn v in p) { if (!v.OkToAdd(prevIx, dig)) return false; } tlistIn = p.GetListOfIncoming(prevIx); // More than one incoming links to this if (tlistIn.Count > 1) return false; tlistOut = p.GetListOfOutgoing(ix, allDigits); // More than one outgoing links to this if (tlistOut.Count > 1) return false; if (tlistIn.Count == 1 && tlistOut.Count == 1) { // One each, but cannot be the same if (tlistIn[0] == tlistOut[0]) return false; } return true; } else { tlistOut = p.GetListOfOutgoing(ix, allDigits); // More than one outgoing links to this if (tlistOut.Count > 1) return false; return true; } } // Merge possible turns private void Merge(AllTurns t, int ix, int dig) { int prevIx; List<OneTurn> tlist; OneTurn u; bool wasLinked = false; prevIx = ix - dig - 1; if ((dig & 1) == 0) // Even { // Incoming // Can we attach to (at most 1) incoming tlist = t.GetListOfIncoming(prevIx); if (tlist.Count == 1) { // Perform the merge u = tlist[0]; u.AddToIncoming(prevIx, ix); wasLinked = true; } else if (tlist.Count > 1) throw new InvalidOperationException(); } // Always // Outgoing, does the last of out-path of some turn point here // Can we attach to (at most 1) outgoing tlist = t.GetListOfOutgoing(ix, allDigits); if (tlist.Count == 1) { // Perform the merge u = tlist[0]; u.AddToOutgoing(ix, allDigits); wasLinked = true; } else if (tlist.Count > 1) throw new InvalidOperationException(); if (!wasLinked) { // Cannot be merged so it is a new turn u = new OneTurn(ix); t.Add(u); } // Can some lists be joined? // For example 0:(-)(2) 1:(2)() // One case is where the end of out-path of one == end of in-path of another // combine by reversing the in-path minus the last plus the turnIx bool finished; List<OneTurn> list = t.turns; OneTurn t1, t2; finished = false; while (!finished) { finished = true; for (int i = 0; i < list.Count; i++) { t1 = list[i]; for (int j = i + 1; j < list.Count; j++) { t2 = list[j]; if (t1.LastOut == t2.LastIn) { // Can merge for (int k = t2.inIx.Count - 2; k >= 0; k--) { t1.outIx.Add(t2.inIx[k]); } t1.outIx.Add(t2.turnIx); t1.outIx.AddRange(t2.outIx); list.Remove(t2); finished = false; break; } } if (!finished) break; } } // And the reverse, except for main finished = false; while (!finished) { finished = true; for (int i = 1; i < list.Count; i++) { t1 = list[i]; for (int j = i + 1; j < list.Count; j++) { t2 = list[j]; if (t1.LastIn == t2.LastOut) { // Can merge for (int k = t1.inIx.Count - 2; k >= 0; k--) { t2.outIx.Add(t1.inIx[k]); } t2.outIx.Add(t1.turnIx); t2.outIx.AddRange(t1.outIx); list.Remove(t1); finished = false; break; } } if (!finished) break; } } } internal void DumpState() { string fn; StreamWriter w; ListOfLong path; StringBuilder ix = new StringBuilder(); for (int i = 0; i < allDigits.Length; i++) { ix.Append((i % 10).ToString()); } fn = "A285471-Result-" + nTerms + ".txt"; w = new StreamWriter(fn); w.WriteLine(""); w.WriteLine("Elapsed time " + st.Elapsed); w.WriteLine("Smallest unused = " + used.FirstUnUsed); w.WriteLine("Largest used = " + used.LastUsed); w.WriteLine("Number of backtracks = " + bt.nPops); w.WriteLine("Number of new values without backtrack = " + bt.nNextValue); w.WriteLine("Calls to CheckOneDigit() = " + nCheckOneDigit); w.WriteLine(""); w.WriteLine("Terms"); w.WriteLine(a.ToString()); w.WriteLine("Digits"); w.WriteLine(allDigits.ToString()); w.WriteLine("Path"); path = bt.TopItem.turns.turns[0].GetOutPath(); w.WriteLine(path.ToString()); w.WriteLine(""); w.WriteLine("Terms"); for (int i = 0; i < a.Count; i++) { w.WriteLine((i + 1) + "\t" + a[i]); } w.WriteLine(""); w.WriteLine("Path"); for (int i = 0; i < path.Count; i++) { w.WriteLine((i + 1) + "\t" + path[i]); } w.Close(); Console.WriteLine("Results are in file "+ Environment.CurrentDirectory+"\\" + fn); Console.WriteLine("NOTE: Some of the final terms may be incorrect due to possible future backtracking"); } internal void WrapUp() { DumpState(); } } public class BTItem : BackTrackItem { public long v; // The term value public AllTurns turns; public BTItem() { turns = new AllTurns(); } #region Iterator // The iterator gives new possible values IEnumerator<long> iter; long last; UsedLong used; //List<OneAvoid> avoid; OneAvoid av; char avoidFirstChar; // Return possible candidates internal void StartIterator(UsedLong used) { last = -1; this.used = used; //avoid = new List<OneAvoid>(); iter = GetEnumerator(); av = new OneAvoid(0, ' '); avoidFirstChar = ' '; } public long Next() { if (iter.MoveNext()) { return iter.Current; } return -1; } public IEnumerator<long> GetEnumerator() { string s; while (true) { last = used.NextFreeAfter(last); s = last.ToString(); if (avoidFirstChar == s[0]) { // Avoid this first character continue; } avoidFirstChar = ' '; // Reset yield return last; } } // Return true if no chance (all digits seen and one of them occurs again) internal bool Avoid2(char c) { if (av.IsFull && av.current != c) return true; av.Avoid(c); return false; } internal void AvoidFirstChar(char c) { avoidFirstChar = c; } class OneAvoid { public char current; // The current digit at this position public bool[] avoid; public int avoidCount; int which; public OneAvoid(int which, char c) { this.which = which; current = c; avoid = new bool[10]; // Internal digits may be 0 avoidCount = which == 0 ? 9 : 10; } public bool IsFull { get { return avoidCount == 0; } } internal bool Allowed(char c) { int dig; dig = c - '0'; return avoid[dig]; } internal void Avoid(char c) { int dig; current = c; dig = c - '0'; if (!avoid[dig]) { avoid[dig] = true; avoidCount--; } } public override string ToString() { StringBuilder sb = new StringBuilder(); sb.Append("[" + which + "] " + current + " "); for (int i = which == 0 ? 1 : 0; i <= 9; i++) { sb.Append(avoid[i] ? "T" : "F"); } sb.Append(" " + avoidCount); return sb.ToString(); } internal void Reset(char c) { current = c; Array.Clear(avoid, 0, avoid.Length); } } #endregion public override string ToString() { return "[" + v + "] " + turns.ToString(); } } public class BTLabyrinth : BackTrack<BTItem> { BTData data; public BTLabyrinth(BTData d) : base() { data = d; } // Get a new item consistent with the state public override BTItem NewItem() { return data.NewItem(top); } public override bool NextValue(BTItem item) { return data.NextValue(item); } public override void BeforePop(BTItem item) { data.BeforePop(item); } protected override void WrapUp() { data.WrapUp(); } public override void WasPushed(BTItem item) { } internal void Init(BTItem item) { Push(item); data.AddInitialTerm(item.v); } } #region Turns /* A turn is like this: <- a <- b <- c ... Incoming path (op) abc = 0,2,4,6,8 t The turning value (t) -> x -> y -> z ... Outgoing path (op) xyz = 1,3,5,7,9 A path is described by the sequence of indices it passes in the sequence of digits. For the ip there is an uncertainty if the step should bed 0,2,4,6 or 8. For the op the step is given by the previous digit. The start value has only an op. A turn is denoted t:(a,b,c,...)(x,y,z,...) The collection of turns is stepped together along the digits of the sequence, new ones are created as required and op+ip or ip+op of different turns are merged, if possible. Start with 1 at ix=0 1.x -- 0:(-)() For ix=1 try 2 but 12 causes a step outside, so try 3 13 -- 0:(-)() and add a new turn 1:()() For ix=2 try 0, this adds steps to both turns 012 (ix) 130 -- 0:(-)(2) and 1:(2)() the op from 0 and the ip to 1 both ends in 2 so we can merge: 130 -- 0:(-)(2,1) For ix=3 skip 4, try 5, cannot connect to previous turn, must create new turn 1305 -- 0:(-)(2,1) new 3:()() For ix=4 skip 6, try 7, cannot connect to previous turn, must create new turn 13057 -- 0:(-)(2,1), 3:()() new 4:()() For ix=5 skip 8, try 9, can connect to 0 130579 -- 0:(-)(2,1,5), 3:()() new 4:()() For ix=6 we can use 2 which connects with 3:ip 1305792 -- 0:(-)(2,1,5), 3:(6)() new 4:()() For ix=7 the free ones are 4,6,8,10 and all the rest Try them 01234567 (ix) 13057924 -- points back to ix=2 which is part of 0:(-)(2,1,5) not allowed 13057926 -- points back to ix=0 part of 0:(-)(2,1,5) na 13057928 -- points outside 13057921 -- 0:(-)(2,1,5), 3:(6)(), 4:()() new 7:()() For ix=8, we must use second digit of 10 - add incoming path to 7 012345678 (ix) 130579210 -- 0:(-)(2,1,5), 3:(6)(), 4:()() 7:(8*)() For ix=9, free=4,6,8,11 etc */ // Collect all active turns public class AllTurns : IEnumerable<OneTurn> { public List<OneTurn> turns; public AllTurns() { turns = new List<OneTurn>(); } public void Add(OneTurn t) { turns.Add(t); } public IEnumerator<OneTurn> GetEnumerator() { return ((IEnumerable<OneTurn>)turns).GetEnumerator(); } public override string ToString() { DelimitedString ds = new DelimitedString(" "); foreach (OneTurn t in turns) { ds.Add(t.ToString()); } return ds.ToStringItems(); } internal AllTurns Clone() { AllTurns t; t = new AllTurns(); foreach (OneTurn v in turns) { t.Add(v.Clone()); } return t; } // A list of all turns whose incoming list ends with ix internal List<OneTurn> GetListOfIncoming(int ix) { List<OneTurn> t; t = new List<OneTurn>(); foreach (OneTurn v in turns) { if (!v.isMain) { if (v.inIx.Count == 0) { if (v.turnIx == ix) t.Add(v); } else { if (v.inIx.LastItem == ix) t.Add(v); } } } return t; } // A list of all turns whose outgoing list ends pointing to ix internal List<OneTurn> GetListOfOutgoing(int ix, StringBuilder digits) { List<OneTurn> t; int k; t = new List<OneTurn>(); if (ix < 0) return t; foreach (OneTurn v in turns) { if (v.outIx.Count == 0) { k = v.turnIx; if (k + digits[k] - '0' + 1 == ix) t.Add(v); } else { k = (int)v.outIx.LastItem; if (k + digits[k] - '0' + 1 == ix) t.Add(v); } } return t; } IEnumerator IEnumerable.GetEnumerator() { return ((IEnumerable<OneTurn>)turns).GetEnumerator(); } } // One active turn public class OneTurn { // True if this is the main "turn", it has just an outgoing path public bool isMain; public int turnIx; // The index where the path turns public ListOfLong inIx; // Incoming indices public ListOfLong outIx; // Outgoing indices public OneTurn(int tix, bool m = false) { isMain = m; turnIx = tix; inIx = new ListOfLong(); outIx = new ListOfLong(); } public int LastOut { get { return outIx.Count == 0 ? turnIx : (int)outIx.LastItem; } } public int LastIn { get { return inIx.Count == 0 ? turnIx : (int)inIx.LastItem; } } // Return false if this dig can NOT be added to this // internal bool OkToAdd(int ix, int dig) { int k; if ((dig & 1) == 0) // Even { // ok if we can add to the in-path, otherwise not if (isMain) { if (turnIx == ix) return false; // Points to turn } else { if (inIx.Count > 0) { k = inIx.IndexOf(ix); if (k >= 0 && k < inIx.Count - 1) return false; // Points into inIx (not to the end) if (turnIx == ix) return false; // Points to turn } else { // In-path is empty, is ok } } // Always test if it links anywhere into the out-path if (outIx.IndexOf(ix) >= 0) return false; } else { // Odd values point above the current length, no tests } return true; } internal void AddToIncoming(int prevIx, int ix) { if (!isMain) { if (inIx.Count == 0) { if (turnIx != prevIx) throw new InvalidOperationException(); inIx.Add(ix); } else { if (inIx.LastItem != prevIx) throw new InvalidOperationException(); inIx.Add(ix); } } } internal void AddToOutgoing(int ix, StringBuilder digits) { int k; if (outIx.Count == 0) { k = turnIx; if (k + digits[k] - '0' + 1 == ix) outIx.Add(ix); } else { k = (int)outIx.LastItem; if (k + digits[k] - '0' + 1 == ix) outIx.Add(ix); } } internal OneTurn Clone() { OneTurn t; t = new OneTurn(turnIx, isMain); t.inIx.AddRange(inIx); t.outIx.AddRange(outIx); return t; } // The turnIx plus the outIx internal ListOfLong GetOutPath() { ListOfLong a; a = new ListOfLong(outIx); a.Items.Insert(0, turnIx); return a; } // The Reverse(inIx) plus turnIx plus the outIx internal ListOfLong GetInAndOutPath() { ListOfLong a; a = new ListOfLong(inIx); a.Reverse(); a.Add(turnIx); a.AddRange(outIx); return a; } public override string ToString() { return turnIx + ":(" + (isMain ? "-" : inIx.ToStringClean()) + ")(" + outIx.ToStringClean() + ")"; } } #endregion #endregion ListOfLong a = new ListOfLong("Sequence"); UsedLong used = new UsedLong(0); } #endregion #region Backtrack framework // Backtrack framework, T is the type of items in the stack public class BackTrack<T> where T : BackTrackItem { public List<T> items; // Used as a stack public T top; public bool stopIt = false; public long nPops = 0; public long nNextValue = 0; // How much is on the stack public int Depth { get { return items.Count; } } public T TopItem { get { return items[items.Count - 1]; } } public T TopItem2 { get { return items[items.Count - 2]; } } public int Count { get { return items.Count; } } public BackTrack() { items = new List<T>(); } public void Push(T item) { items.Add(item); WasPushed(item); } // Start the optimizing process public void Go() { T ni; while (true) { if (stopIt) { WrapUp(); return; } top = items[items.Count - 1]; ni = NewItem(); if (ni == null) { // A new item cannot be created in this state of the stack // See if a new value can be assigned for the top item // If not, pop and try again while (true) { if (stopIt) { WrapUp(); return; } if (NextValue(items[items.Count - 1])) { nNextValue++; // There is a new value to work with, break; } else { nPops++; BeforePop(items[items.Count - 1]); // Inform descendant items.RemoveAt(items.Count - 1); if (items.Count == 0) { WrapUp(); return; // No more solutions are possible } } } } else { // We have a new item to put on the stack Push(ni); } } } // When the Go method exits virtual protected void WrapUp() { } // Create a new item to be placed on the stack, or null if none possible virtual public T NewItem() { return null; } virtual public bool NextValue(T top) { return false; } virtual public void BeforePop(T item) { } virtual public void WasPushed(T item) { } } // ------------------------------------------ // From which to derive specific Item classes public class BackTrackItem { } #endregion #region UsedLong // Common interface public interface IUsedLong { void Use(long v); void UseMultiple(long v); void Use(ListOfLong list); void UnUse(long v); void UnUse(ListOfLong list); long Last { get; } System.Collections.IEnumerator GetEnumerator(); long FirstUnUsed { get; } long LastUsed { get; } long Count { get; } long CountUnUsed { get; } bool IsUsed(long v); bool IsAnyUsed(ListOfLong list); ListOfLong GetValues(); long NextFreeAfter(long after); } // Class for managing used longs ALWAYS >= 0! public class UsedLong : IUsedLong { public long FirstFree = 0; HashSet<long> used = new HashSet<long>(); public long First; // The first number that is relevant public UsedLong(long first) { First = first; FirstFree = first; } public void Use(long v) { if (used.Contains(v)) { throw new InvalidOperationException(); } used.Add(v); if (v == FirstFree) { for (long k = v + 1; true; k++) { if (!used.Contains(k)) { FirstFree = k; break; } } } } public void UseMultiple(long v) { if (!IsUsed(v)) { Use(v); } } public void Use(ListOfLong list) { foreach (long v in list) { Use(v); } } public void UnUse(long v) { if (!used.Contains(v)) { throw new InvalidOperationException(); } used.Remove(v); for (long k = First; true; k++) { if (!used.Contains(k)) { FirstFree = k; break; } } } public void UnUse(ListOfLong list) { foreach (long v in list) { UnUse(v); } } public long Last { get { long result = 0; foreach (long v in used) { result = Math.Max(result, v); } return result; } } public IEnumerator GetEnumerator() { long last = Last; // First the range in which there are used items for (long k = First; k <= last; k++) { if (!used.Contains(k)) { yield return k; } } // Then all the rest for (long k = last + 1; true; k++) { yield return k; } } public long FirstUnUsed { get { long last = Last; for (long k = First; k <= last; k++) { if (!used.Contains(k)) { return k; } } return last + 1; // This is the next free } } public long LastUsed { get { return Last; } } public long Count { get { return used.Count; } } public long CountUnUsed { get { return Last - used.Count; } } public bool IsUsed(long v) { if (v < FirstFree) { return true; // All entries up to FirstFree are used } else { return used.Contains(v); } } public bool IsAnyUsed(ListOfLong list) { foreach (long v in list) { if (IsUsed(v)) { return true; } } return false; } public ListOfLong GetValues() { ListOfLong result = new ListOfLong(); result.Items.AddRange(used); result.Sort(); return result; } public long NextFreeAfter(long after) { for (long v = after + 1; true; v++) { if (!used.Contains(v)) { return v; } } } public ListOfLong GetFreeList() { ListOfLong r = new ListOfLong("List of unused numbers"); long last = LastUsed; for (long k = First; k <= last; k++) { if (!used.Contains(k)) { r.Add(k); } } return r; } } #endregion public class ListOfObject<T> where T : IComparable { static public int Next = 1; public string Name; public List<T> Items; public ListOfObject() { Name = "L" + Next; Next++; Items = new List<T>(); } public ListOfObject(string name, List<T> items) { Name = name; Items = new List<T>(items); } public ListOfObject(ListOfObject<T> from) { Name = from.Name; Items = new List<T>(from.Items); } public ListOfObject(string name) { Name = name; Items = new List<T>(); } public void Add(T item) { Items.Add(item); } public void Add(List<T> list) { Items.AddRange(list); } public void Add(ListOfObject<T> list) { Items.AddRange(list.Items); } public int Count { get { return Items.Count; } } public T this[int index] { get { return Items[index]; } set { Items[index] = value; } } public string AsString { get { return ToStringClean(); } } public T LastItem { get { return Items[Items.Count - 1]; } set { Items[Items.Count - 1] = value; } } public T FirstItem { get { return Items[0]; } } public string ToStringClean() { StringBuilder sb = new StringBuilder(); if (Items == null) { return "(null)"; } for (int i = 0; i < Items.Count; i++) { if (sb.Length > 0) { sb.Append(","); } sb.Append(Items[i]); } return sb.ToString(); } public List<T>.Enumerator GetEnumerator() { return Items.GetEnumerator(); } public override string ToString() { return Items.Count + ": " + ToStringClean(); } } public class ListOfLong : ListOfObject<long> { public ListOfLong() : base() { } public ListOfLong(string name, List<long> items) : base(name, items) { } public ListOfLong(string name) : base(name) { } public ListOfLong(ListOfLong from) : base(from) { } public ListOfLong(int size) { for (int i = 0; i < size; i++) { Items.Add(0); } } public ListOfLong(int size, long fillWith) { for (int i = 0; i < size; i++) { Items.Add(fillWith); } } public ListOfLong(long[] from) { Items.AddRange(from); } public ListOfLong(int[] from) { foreach (int v in from) { Items.Add(v); } } public ListOfLong(List<long> from) { Items.AddRange(from); } public ListOfLong(List<int> from) { foreach (int v in from) { Items.Add(v); } } public ListOfLong(IEnumerable<long> from) { Items.AddRange(from); } public ListOfLong(char[] from) { foreach (char c in from) { Items.Add(c); } } public void Reverse() { Items.Reverse(); } public bool HasAnyOf(ListOfLong list) { foreach (long v in list) { if (this.Has(v)) { return true; } } return false; } public void Add() { Items.Add(long.MinValue); } public void AddRange(ListOfLong from) { Items.AddRange(from.Items); } public void AddRange(long[] from) { Items.AddRange(from); } public void AddRange(byte[] from) { foreach (byte b in from) { Items.Add(b); } } public void AddRange(IEnumerable<long> from) { Items.AddRange(from); } public void AddRange(long lo, long hi) { for (long k = lo; k <= hi; k++) { Items.Add(k); } } static public int Comparison(ListOfLong x, ListOfLong y) { if (x.Count < y.Count) { return -1; } else if (x.Count > y.Count) { return +1; } else { for (int i = 0; i < x.Count; i++) { if (x.Items[i] < y.Items[i]) { return -1; } else if (x.Items[i] > y.Items[i]) { return +1; } } } return 0; } public string FirstItemsAsString(int cnt) { return ExtractAsString(0, cnt - 1); } public string LastItemsasString(int cnt) { return ExtractAsString(Items.Count - cnt, Items.Count - 1); } public ListOfLong FirstItems(int cnt) { return Extract(0, cnt - 1); } public ListOfLong LastItems(int cnt) { return Extract(Items.Count - cnt, Items.Count - 1); } public string ExtractAsString(int first, int last) { StringBuilder sb = new StringBuilder(); first = Math.Max(0, first); last = Math.Min(Items.Count - 1, last); for (int i = first; i <= last; i++) { if (sb.Length > 0) { sb.Append(","); } sb.Append(Items[i]); } return sb.ToString(); } public ListOfLong Extract(int first, int last) { ListOfLong result; result = new ListOfLong(); first = Math.Max(0, first); last = Math.Min(Items.Count - 1, last); for (int i = first; i <= last; i++) { result.Add(Items[i]); } return result; } public void RemoveLast() { Items.RemoveAt(Items.Count - 1); } public int IndexOf(long v) { return Items.IndexOf(v); } public bool Has(long v) { return Items.IndexOf(v) >= 0; } public bool HasNot(long v) { return Items.IndexOf(v) < 0; } static public void Sort(List<ListOfLong> list) { list.Sort(Comparison); } public string ToStringTabSep() { DelimitedString ds = new DelimitedString("\t"); foreach (long v in Items) { if (v == long.MinValue) { ds.Add(""); } else { ds.Add(v); } } return ds.ToStringItems(); } public void RemoveFirst() { Items.RemoveAt(0); } public static ListOfLong Generate(long first, long last) { return Generate(null, first, last); } public static ListOfLong Generate(string name, long first, long last) { ListOfLong result; if (name == null) { result = new ListOfLong(); } else { result = new ListOfLong(name); } for (long i = first; i <= last; i++) { result.Add(i); } return result; } public string ToStringCommaSepToMax(int maxlen) { DelimitedString ds = new DelimitedString(", "); string last = ""; foreach (long v in Items) { last = ds.ToString(); ds.Add(v); if (ds.Length >= maxlen) { return last; } } return ds.ToString(); } // Remove all occurrences if items in other from this list public void Remove(ListOfLong other) { foreach (long v in other) { Items.Remove(v); } } public void Remove(long v) { Items.Remove(v); } // Return concatenation of all digits public string ToStringConcat() { StringBuilder sb = new StringBuilder(); foreach (long v in Items) { sb.Append(v); } return sb.ToString(); } // Next to last item public long LastItem2 { get { if (Items.Count >= 2) { return Items[Items.Count - 2]; } else { return -1; } } } // Next to next to last item public long LastItem3 { get { if (Items.Count >= 3) { return Items[Items.Count - 3]; } else { return -1; } } } public int CompareTo(ListOfLong other) { if (this.Count < other.Count) { return -1; } else if (this.Count > other.Count) { return +1; } else { for (int i = 0; i < this.Count; i++) { if (this[i] < other[i]) { return -1; } else if (this[i] > other[i]) { return +1; } } } return 0; } public int CountOf(long i) { int count = 0; foreach (long v in Items) { if (v == i) { count++; } } return count; } public override bool Equals(object obj) { return this.CompareTo(obj as ListOfLong) == 0; } public override int GetHashCode() { return (int)Sum(); } public void Clear() { Items.Clear(); } long Sum() { long r = 0; foreach (long v in Items) { r += v; } return r; } public void Exchange(int ix1, int ix2) { long tmp; tmp = Items[ix1]; Items[ix1] = Items[ix2]; Items[ix2] = tmp; } internal void Sort() { Items.Sort(); } } public class DelimitedString { string Delimiter; StringBuilder sb; int count; bool isEmpty; public int Count { get { return count; } } public int Length { get { return sb.Length; } } public DelimitedString(string delimiter) { Delimiter = delimiter; sb = new StringBuilder(); count = 0; isEmpty = true; } public DelimitedString(char delimiter) { Delimiter = new string(delimiter, 1); sb = new StringBuilder(); count = 0; isEmpty = true; } public void Add(string s) { count++; if (!isEmpty) { sb.Append(Delimiter); } sb.Append(s); isEmpty = false; } public void Add(char c) { Add(new string(c, 1)); } public void Add(long v) { Add(v.ToString()); } public void Add2(long a1, long a2) { Add(a1); Add(a2); } public void Add(string s, int count) { for (int i = 0; i < count; i++) { Add(s); } } public void AddTimes(long v, int count) { if (count > 1) { Add(v.ToString() + "*" + count); } else { Add(v); } } public override string ToString() { return count + ": " + sb.ToString(); } public string ToStringItems() { return sb.ToString(); } public string ToStringParen() { return "(" + sb.ToString() + ")"; } } } }