Instantly share code, notes, and snippets.

# alfaproject/Combinations.csSecret Last active Aug 29, 2015

Best fleet calculator
 // Copyright 2008 Adrian Akison // Distributed under license terms of CPOL http://www.codeproject.com/info/cpol10.aspx using System; using System.Collections.Generic; using System.Text; namespace aLfPoP.Combinatorics { /// /// Combinations defines a meta-collection, typically a list of lists, of all possible /// subsets of a particular size from the set of values. This list is enumerable and /// allows the scanning of all possible combinations using a simple foreach() loop. /// Within the returned set, there is no prescribed order. This follows the mathematical /// concept of choose. For example, put 10 dominoes in a hat and pick 5. The number of possible /// combinations is defined as "10 choose 5", which is calculated as (10!) / ((10 - 5)! * 5!). /// /// /// The MetaCollectionType parameter of the constructor allows for the creation of /// two types of sets, those with and without repetition in the output set when /// presented with repetition in the input set. /// /// When given a input collect {A B C} and lower index of 2, the following sets are generated: /// MetaCollectionType.WithRepetition => /// {A A}, {A B}, {A C}, {B B}, {B C}, {C C} /// MetaCollectionType.WithoutRepetition => /// {A B}, {A C}, {B C} /// /// Input sets with multiple equal values will generate redundant combinations in proprotion /// to the likelyhood of outcome. For example, {A A B B} and a lower index of 3 will generate: /// {A A B} {A A B} {A B B} {A B B} /// /// The type of the values within the list. public class Combinations : IEnumerable> { #region Constructors /// /// No default constructor, must provided a list of values and size. /// protected Combinations() { ; } /// /// Create a combination set from the provided list of values. /// The upper index is calculated as values.Count, the lower index is specified. /// Collection type defaults to MetaCollectionType.WithoutRepetition /// /// List of values to select combinations from. /// The size of each combination set to return. public Combinations(IList values, int lowerIndex) { Initialize(values, lowerIndex, GenerateOption.WithoutRepetition); } /// /// Create a combination set from the provided list of values. /// The upper index is calculated as values.Count, the lower index is specified. /// /// List of values to select combinations from. /// The size of each combination set to return. /// The type of Combinations set to generate. public Combinations(IList values, int lowerIndex, GenerateOption type) { Initialize(values, lowerIndex, type); } #endregion #region IEnumerable Interface /// /// Gets an enumerator for collecting the list of combinations. /// /// The enumerator. public IEnumerator> GetEnumerator() { return new Enumerator(this); } /// /// Gets an enumerator for collecting the list of combinations. /// /// The enumerator.returns> System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return new Enumerator(this); } #endregion /// /// The enumerator that enumerates each meta-collection of the enclosing Combinations class. /// public class Enumerator : IEnumerator> { #region Constructors /// /// Construct a enumerator with the parent object. /// /// The source combinations object. public Enumerator(Combinations source) { myParent = source; myPermutationsEnumerator = (Permutations.Enumerator) myParent.myPermutations.GetEnumerator(); } #endregion #region IEnumerator interface /// /// Resets the combinations enumerator to the first combination. /// public void Reset() { myPermutationsEnumerator.Reset(); } /// /// Advances to the next combination of items from the set. /// /// True if successfully moved to next combination, False if no more unique combinations exist. /// /// The heavy lifting is done by the permutations object, the combination is generated /// by creating a new list of those items that have a true in the permutation parrellel array. /// public bool MoveNext() { bool ret = myPermutationsEnumerator.MoveNext(); myCurrentList = null; return ret; } /// /// The current combination /// public IList Current { get { ComputeCurrent(); return myCurrentList; } } /// /// The current combination /// object System.Collections.IEnumerator.Current { get { ComputeCurrent(); return myCurrentList; } } /// /// Cleans up non-managed resources, of which there are none used here. /// public void Dispose() { ; } #endregion #region Heavy Lifting Members /// /// The only complex function of this entire wrapper, ComputeCurrent() creates /// a list of original values from the bool permutation provided. /// The exception for accessing current (InvalidOperationException) is generated /// by the call to .Current on the underlying enumeration. /// /// /// To compute the current list of values, the underlying permutation object /// which moves with this enumerator, is scanned differently based on the type. /// The items have only two values, true and false, which have different meanings: /// /// For type WithoutRepetition, the output is a straightforward subset of the input array. /// E.g. 6 choose 3 without repetition /// Input array: {A B C D E F} /// Permutations: {0 1 0 0 1 1} /// Generates set: {A C D } /// Note: size of permutation is equal to upper index. /// /// For type WithRepetition, the output is defined by runs of characters and when to /// move to the next element. /// E.g. 6 choose 5 with repetition /// Input array: {A B C D E F} /// Permutations: {0 1 0 0 1 1 0 0 1 1} /// Generates set: {A B B D D } /// Note: size of permutation is equal to upper index - 1 + lower index. /// private void ComputeCurrent() { if (myCurrentList == null) { myCurrentList = new List(); int index = 0; IList currentPermutation = (IList) myPermutationsEnumerator.Current; for (int i = 0; i < currentPermutation.Count; ++i) { if (currentPermutation[i] == false) { myCurrentList.Add(myParent.myValues[index]); if (myParent.Type == GenerateOption.WithoutRepetition) { ++index; } } else { ++index; } } } } #endregion #region Data /// /// Parent object this is an enumerator for. /// private Combinations myParent; /// /// The current list of values, this is lazy evaluated by the Current property. /// private List myCurrentList; /// /// An enumertor of the parents list of lexicographic orderings. /// private Permutations.Enumerator myPermutationsEnumerator; #endregion } /// /// The type of Combinations set that is generated. /// public GenerateOption Type { get { return myMetaCollectionType; } } /// /// The upper index of the meta-collection, equal to the number of items in the initial set. /// public int UpperIndex { get { return myValues.Count; } } /// /// The lower index of the meta-collection, equal to the number of items returned each iteration. /// public int LowerIndex { get { return myLowerIndex; } } #region Heavy Lifting Members /// /// Initialize the combinations by settings a copy of the values from the /// /// List of values to select combinations from. /// The size of each combination set to return. /// The type of Combinations set to generate. /// /// Copies the array and parameters and then creates a map of booleans that will /// be used by a permutations object to refence the subset. This map is slightly /// different based on whether the type is with or without repetition. /// /// When the type is WithoutRepetition, then a map of upper index elements is /// created with lower index false's. /// E.g. 8 choose 3 generates: /// Map: {1 1 1 1 1 0 0 0} /// Note: For sorting reasons, false denotes inclusion in output. /// /// When the type is WithRepetition, then a map of upper index - 1 + lower index /// elements is created with the falses indicating that the 'current' element should /// be included and the trues meaning to advance the 'current' element by one. /// E.g. 8 choose 3 generates: /// Map: {1 1 1 1 1 1 1 1 0 0 0} (7 trues, 3 falses). /// private void Initialize(IList values, int lowerIndex, GenerateOption type) { myMetaCollectionType = type; myLowerIndex = lowerIndex; myValues = new List(); myValues.AddRange(values); List myMap = new List(); if (type == GenerateOption.WithoutRepetition) { for (int i = 0; i < myValues.Count; ++i) { if (i >= myValues.Count - myLowerIndex) { myMap.Add(false); } else { myMap.Add(true); } } } else { for (int i = 0; i < values.Count - 1; ++i) { myMap.Add(true); } for (int i = 0; i < myLowerIndex; ++i) { myMap.Add(false); } } myPermutations = new Permutations(myMap); } #endregion #region Data /// /// Copy of values object is intialized with, required for enumerator reset. /// private List myValues; /// /// Permutations object that handles permutations on booleans for combination inclusion. /// private Permutations myPermutations; /// /// The type of the combination collection. /// private GenerateOption myMetaCollectionType; /// /// The lower index defined in the constructor. /// private int myLowerIndex; #endregion } }
 namespace aLfPoP.Combinatorics { /// /// Indicates whether a Permutation, Combination or Variation meta-collections /// generate repetition sets. /// public enum GenerateOption { /// /// Do not generate additional sets, typical implementation. /// WithoutRepetition, /// /// Generate additional sets even if repetition is required. /// WithRepetition } }
 using System; using System.Collections; using System.Collections.Generic; namespace aLfPoP.Combinatorics { /// /// Permutations defines a meta-collection, typically a list of lists, of all /// possible orderings of a set of values. This list is enumerable and allows /// the scanning of all possible permutations using a simple foreach() loop. /// The MetaCollectionType parameter of the constructor allows for the creation of /// two types of sets, those with and without repetition in the output set when /// presented with repetition in the input set. /// /// /// When given a input collect {A A B}, the following sets are generated: /// MetaCollectionType.WithRepetition => /// {A A B}, {A B A}, {A A B}, {A B A}, {B A A}, {B A A} /// MetaCollectionType.WithoutRepetition => /// {A A B}, {A B A}, {B A A} /// /// When generating non-repetition sets, ordering is based on the lexicographic /// ordering of the lists based on the provided Comparer. /// If no comparer is provided, then T must be IComparable on T. /// /// When generating repetition sets, no comparisions are performed and therefore /// no comparer is required and T does not need to be IComparable. /// /// The type of the values within the list. public class Permutations : IEnumerable> { /// /// A list of T that represents the order of elements as originally provided, used for Reset. /// private readonly List _values; /// /// Parallel array of integers that represent the location of items in the _values array. /// This is generated at Initialization and is used as a performance speed up rather that /// comparing T each time, much faster to let the CLR optimize around integers. /// private readonly int[] _lexicographicOrders; /// /// Create a permutation set from the provided list of values. /// The values will be compared using the supplied IComparer. /// /// /// Copies information provided and then creates a parallel int array of lexicographic /// orders that will be used for the actual permutation algorithm. /// The input array is first sorted as required for WithoutRepetition and always just for consistency. /// This array is constructed one of two way depending on the type of the collection. /// /// When type is MetaCollectionType.WithRepetition, then all N! permutations are returned /// and the lexicographic orders are simply generated as 1, 2, ... N. /// E.g. /// Input array: {A A B C D E E} /// Lexicograhpic Orders: {1 2 3 4 5 6 7} /// /// When type is MetaCollectionType.WithoutRepetition, then fewer are generated, with each /// identical element in the input array not repeated. The lexicographic sort algorithm /// handles this natively as long as the repetition is repeated. /// E.g. /// Input array: {A A B C D E E} /// Lexicograhpic Orders: {1 1 2 3 4 5 5} /// /// List of values to permute. /// The type of permutation set to calculate. /// Comparer used for defining the lexigraphic order. public Permutations(IEnumerable values, GenerateOption type, IComparer comparer) { Type = type; _values = new List(values); _lexicographicOrders = new int[_values.Count]; if (type == GenerateOption.WithRepetition) { for (var i = 0; i < _lexicographicOrders.Length; i++) { _lexicographicOrders[i] = i; } } else { if (comparer == null) { comparer = Comparer.Default; } _values.Sort(comparer); var j = 1; if (_lexicographicOrders.Length > 0) { _lexicographicOrders[0] = j; } for (var i = 1; i < _lexicographicOrders.Length; i++) { if (comparer.Compare(_values[i - 1], _values[i]) != 0) { j++; } _lexicographicOrders[i] = j; } } } /// /// Create a permutation set from the provided list of values. /// If type is MetaCollectionType.WithholdRepetitionSets, then values (T) must implement IComparable. /// If T does not implement IComparable use a constructor with an explict IComparer. /// /// List of values to permute. /// The type of permutation set to calculate. public Permutations(IEnumerable values, GenerateOption type) : this(values, type, null) { } /// /// Create a permutation set from the provided list of values. /// The values will be compared using the supplied IComparer. /// The repetition type defaults to MetaCollectionType.WithholdRepetitionSets /// /// List of values to permute. /// Comparer used for defining the lexigraphic order. public Permutations(IEnumerable values, IComparer comparer) : this(values, GenerateOption.WithoutRepetition, comparer) { } /// /// Create a permutation set from the provided list of values. /// The values (T) must implement IComparable. /// If T does not implement IComparable use a constructor with an explict IComparer. /// The repetition type defaults to MetaCollectionType.WithholdRepetitionSets /// /// List of values to permute. public Permutations(IEnumerable values) : this(values, GenerateOption.WithoutRepetition, null) { } /// /// The type of Permutations set that is generated. /// public GenerateOption Type { get; private set; } /// /// Gets an enumerator for collecting the list of permutations. /// /// The enumerator. public virtual IEnumerator GetEnumerator() { return new Enumerator(this); } /// /// Gets an enumerator for collecting the list of permutations. /// /// The enumerator. IEnumerator> IEnumerable>.GetEnumerator() { return new Enumerator(this); } /// /// The enumerator that enumerates each meta-collection of the enclosing Permutations class. /// public class Enumerator : IEnumerator> { /// /// Single instance of swap variable for T, small performance improvement over declaring in Swap function scope. /// private T _temp; /// /// Single instance of swap variable for int, small performance improvement over declaring in Swap function scope. /// private int _kviTemp; /// /// Flag indicating the position of the enumerator. /// private Position _position = Position.BeforeFirst; /// /// Parallel array of integers that represent the location of items in the _values array. /// This is generated at Initialization and is used as a performance speed up rather that /// comparing T each time, much faster to let the CLR optimize around integers. /// private readonly int[] _lexicographicalOrders; /// /// The list of values that are current to the enumerator. /// private List _values; /// /// The set of permuations that this enumerator enumerates. /// private readonly Permutations _parent; /// /// Internal position type for tracking enumertor position. /// private enum Position { BeforeFirst, InSet, AfterLast } /// /// Construct a enumerator with the parent object. /// /// The source Permutations object. public Enumerator(Permutations source) { _parent = source; _lexicographicalOrders = new int[source._lexicographicOrders.Length]; source._lexicographicOrders.CopyTo(_lexicographicalOrders, 0); Reset(); } /// /// Resets the permutations enumerator to the first permutation. /// This will be the first lexicographically order permutation. /// public void Reset() { _position = Position.BeforeFirst; } /// /// Advances to the next permutation. /// /// True if successfully moved to next permutation, False if no more permutations exist. /// /// Continuation was tried (i.e. yield return) by was not nearly as efficient. /// Performance is further increased by using value types and removing generics, that is, the LexicographicOrder parallel array. /// This is a issue with the .NET CLR not optimizing as well as it could in this infrequently used scenario. /// public bool MoveNext() { switch (_position) { case Position.BeforeFirst: _values = new List(_parent._values); Array.Sort(_lexicographicalOrders); _position = Position.InSet; break; case Position.InSet: if (_values.Count < 2) { _position = Position.AfterLast; } else if (NextPermutation() == false) { _position = Position.AfterLast; } break; } return _position != Position.AfterLast; } /// /// The current permutation. /// public object Current { get { if (_position == Position.InSet) { return new List(_values); } throw new InvalidOperationException(); } } /// /// The current permutation. /// IList IEnumerator>.Current { get { if (_position == Position.InSet) { return new List(_values); } throw new InvalidOperationException(); } } /// /// Cleans up non-managed resources, of which there are none used here. /// public virtual void Dispose() { } /// /// Calculates the next lexicographical permutation of the set. /// This is a permutation with repetition where values that compare as equal will not /// swap positions to create a new permutation. /// http://www.cut-the-knot.org/do_you_know/AllPerm.shtml /// E. W. Dijkstra, A Discipline of Programming, Prentice-Hall, 1997 /// /// True if a new permutation has been returned, false if not. /// /// This uses the integers of the lexicographical order of the values so that any /// comparison of values are only performed during initialization. /// private bool NextPermutation() { int i = _lexicographicalOrders.Length - 1; while (_lexicographicalOrders[i - 1] >= _lexicographicalOrders[i]) { --i; if (i == 0) { return false; } } int j = _lexicographicalOrders.Length; while (_lexicographicalOrders[j - 1] <= _lexicographicalOrders[i - 1]) { --j; } Swap(i - 1, j - 1); ++i; j = _lexicographicalOrders.Length; while (i < j) { Swap(i - 1, j - 1); ++i; --j; } return true; } /// /// Helper function for swapping two elements within the internal collection. /// This swaps both the lexicographical order and the values, maintaining the parallel array. /// private void Swap(int i, int j) { _temp = _values[i]; _values[i] = _values[j]; _values[j] = _temp; _kviTemp = _lexicographicalOrders[i]; _lexicographicalOrders[i] = _lexicographicalOrders[j]; _lexicographicalOrders[j] = _kviTemp; } } } }
 using System; using System.Collections; using System.Collections.Generic; namespace aLfPoP.Combinatorics { /// /// Permutations defines a meta-collection, typically a list of lists, of all /// possible orderings of a set of values. This list is enumerable and allows /// the scanning of all possible permutations using a simple foreach() loop. /// The MetaCollectionType parameter of the constructor allows for the creation of /// two types of sets, those with and without repetition in the output set when /// presented with repetition in the input set. /// /// /// When given a input collect {A A B}, the following sets are generated: /// MetaCollectionType.WithRepetition => /// {A A B}, {A B A}, {A A B}, {A B A}, {B A A}, {B A A} /// MetaCollectionType.WithoutRepetition => /// {A A B}, {A B A}, {B A A} /// /// When generating non-repetition sets, ordering is based on the lexicographic /// ordering of the lists based on the provided Comparer. /// If no comparer is provided, then T must be IComparable on T. /// /// When generating repetition sets, no comparisions are performed and therefore /// no comparer is required and T does not need to be IComparable. /// /// The type of the values within the list. public class PermutationsWithoutRepetition : IEnumerable> { /// /// A list of T that represents the order of elements as originally provided, used for Reset. /// private readonly List _values; /// /// Parallel array of integers that represent the location of items in the _values array. /// This is generated at Initialization and is used as a performance speed up rather that /// comparing T each time, much faster to let the CLR optimize around integers. /// private readonly int[] _lexicographicOrders; /// /// Create a permutation set from the provided list of values. /// The values will be compared using the supplied IComparer. /// /// /// Copies information provided and then creates a parallel int array of lexicographic /// orders that will be used for the actual permutation algorithm. /// The input array is first sorted as required for WithoutRepetition and always just for consistency. /// This array is constructed one of two way depending on the type of the collection. /// /// When type is MetaCollectionType.WithRepetition, then all N! permutations are returned /// and the lexicographic orders are simply generated as 1, 2, ... N. /// E.g. /// Input array: {A A B C D E E} /// Lexicograhpic Orders: {1 2 3 4 5 6 7} /// /// When type is MetaCollectionType.WithoutRepetition, then fewer are generated, with each /// identical element in the input array not repeated. The lexicographic sort algorithm /// handles this natively as long as the repetition is repeated. /// E.g. /// Input array: {A A B C D E E} /// Lexicograhpic Orders: {1 1 2 3 4 5 5} /// /// List of values to permute. /// The type of permutation set to calculate. /// Comparer used for defining the lexigraphic order. public PermutationsWithoutRepetition(IEnumerable values) { _values = new List(values); _lexicographicOrders = new int[_values.Count]; _values.Sort(); var j = 1; if (_lexicographicOrders.Length > 0) { _lexicographicOrders[0] = j; } for (var i = 1; i < _lexicographicOrders.Length; i++) { if (Comparer.Default.Compare(_values[i - 1], _values[i]) != 0) { j++; } _lexicographicOrders[i] = j; } } /// /// Gets an enumerator for collecting the list of permutations. /// /// The enumerator. public virtual IEnumerator GetEnumerator() { return new Enumerator(this); } /// /// Gets an enumerator for collecting the list of permutations. /// /// The enumerator. IEnumerator> IEnumerable>.GetEnumerator() { return new Enumerator(this); } /// /// The enumerator that enumerates each meta-collection of the enclosing Permutations class. /// public class Enumerator : IEnumerator> { /// /// Single instance of swap variable for T, small performance improvement over declaring in Swap function scope. /// private T _temp; /// /// Single instance of swap variable for int, small performance improvement over declaring in Swap function scope. /// private int _kviTemp; /// /// Flag indicating the position of the enumerator. /// private Position _position = Position.BeforeFirst; /// /// Parallel array of integers that represent the location of items in the _values array. /// This is generated at Initialization and is used as a performance speed up rather that /// comparing T each time, much faster to let the CLR optimize around integers. /// private readonly int[] _lexicographicalOrders; /// /// The list of values that are current to the enumerator. /// private List _values; /// /// The set of permuations that this enumerator enumerates. /// private readonly PermutationsWithoutRepetition _parent; /// /// Internal position type for tracking enumertor position. /// private enum Position { BeforeFirst, InSet, AfterLast } /// /// Construct a enumerator with the parent object. /// /// The source Permutations object. public Enumerator(PermutationsWithoutRepetition source) { _parent = source; _lexicographicalOrders = new int[source._lexicographicOrders.Length]; source._lexicographicOrders.CopyTo(_lexicographicalOrders, 0); Reset(); } /// /// Resets the permutations enumerator to the first permutation. /// This will be the first lexicographically order permutation. /// public void Reset() { _position = Position.BeforeFirst; } /// /// Advances to the next permutation. /// /// True if successfully moved to next permutation, False if no more permutations exist. /// /// Continuation was tried (i.e. yield return) by was not nearly as efficient. /// Performance is further increased by using value types and removing generics, that is, the LexicographicOrder parallel array. /// This is a issue with the .NET CLR not optimizing as well as it could in this infrequently used scenario. /// public bool MoveNext() { switch (_position) { case Position.BeforeFirst: _values = new List(_parent._values.Count); _values.AddRange(_parent._values); Array.Sort(_lexicographicalOrders); _position = Position.InSet; break; case Position.InSet: if (_values.Count < 2) { _position = Position.AfterLast; } else if (NextPermutation() == false) { _position = Position.AfterLast; } break; } return _position != Position.AfterLast; } /// /// The current permutation. /// public object Current { get { if (_position == Position.InSet) { return new List(_values); } throw new InvalidOperationException(); } } /// /// The current permutation. /// IList IEnumerator>.Current { get { if (_position == Position.InSet) { return new List(_values); } throw new InvalidOperationException(); } } /// /// Cleans up non-managed resources, of which there are none used here. /// public virtual void Dispose() { } /// /// Calculates the next lexicographical permutation of the set. /// This is a permutation with repetition where values that compare as equal will not /// swap positions to create a new permutation. /// http://www.cut-the-knot.org/do_you_know/AllPerm.shtml /// E. W. Dijkstra, A Discipline of Programming, Prentice-Hall, 1997 /// /// True if a new permutation has been returned, false if not. /// /// This uses the integers of the lexicographical order of the values so that any /// comparison of values are only performed during initialization. /// private bool NextPermutation() { int i = _lexicographicalOrders.Length - 1; while (_lexicographicalOrders[i - 1] >= _lexicographicalOrders[i]) { --i; if (i == 0) { return false; } } int j = _lexicographicalOrders.Length; while (_lexicographicalOrders[j - 1] <= _lexicographicalOrders[i - 1]) { --j; } Swap(i - 1, j - 1); ++i; j = _lexicographicalOrders.Length; while (i < j) { Swap(i - 1, j - 1); ++i; --j; } return true; } /// /// Helper function for swapping two elements within the internal collection. /// This swaps both the lexicographical order and the values, maintaining the parallel array. /// private void Swap(int i, int j) { _temp = _values[i]; _values[i] = _values[j]; _values[j] = _temp; _kviTemp = _lexicographicalOrders[i]; _lexicographicalOrders[i] = _lexicographicalOrders[j]; _lexicographicalOrders[j] = _kviTemp; } } } }
 using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Threading.Tasks; using aLfPoP.Combinatorics; namespace aLfPoP { static class Program { private static readonly object _syncLock = new object(); private static void Main(string[] args) { var rams = new[] { new Unit(800, 0, 0, 0, 0, "Inspiring Figurehead"), new Unit(0, 800, 0, 0, 0, "Spitfire Cannon"), }; var decks = new[] { new Unit(1350, 0, 0, 0, 0, "Eastern Relics"), new Unit(0, 1750, 0, 0, 0, "Ov. Large Cannon x4"), new Unit(0, 0, 1350, 0, 0, "Dragonskin Rigging"), }; var hulls = new[] { new Unit(1400, 500, 500, 600, 0, "Blazing Lantern Hull"), new Unit(500, 1400, 500, 600, 0, "Golden Katana Hull"), new Unit(500, 500, 1200, 400, 0, "Storm Rider Hull"), }; var captains = new[] { new Unit(1450, 770, 850, 800, 10, "Barnabas Wytche", Traits.Seafarer | Traits.ToughAsNails | Traits.FastLearner | Traits.MultiTalented), new Unit(1420, 740, 740, 780, 10, "Sebastian Wytche", Traits.EagleEyed | Traits.MiseryGuts | Traits.Plucky | Traits.QuickFooted), new Unit(650, 1510, 850, 800, 10, "Charlotte Fang", Traits.EagleEyed | Traits.Vapid | Traits.Loyal | Traits.MultiTalented), new Unit(800, 800, 1500, 1050, 10, "Maladetta Hook", Traits.Loyal | Traits.MultiTalented | Traits.Workhorse | Traits.MultiTalented), new Unit(805, 805, 1450, 865, 8, "Maladetta Kidd", Traits.Plucky | Traits.Eager | Traits.MultiTalented | Traits.MultiTalented), }.OrderBy(c => c.Morale + c.Combat + c.Seafar).ToArray(); var roster = new[] { // specials new Unit(900, 900, 910, 0, 10, "Judge of Dice 1", Traits.Solidarity), new Unit(900, 940, 910, 0, 10, "Judge of Dice 2", Traits.Solidarity | Traits.Plucky), new Unit(1030, 1050, 1040, 0, 10, "Oxhead and Horseface 1", Traits.Plucky | Traits.Resurrects), new Unit(1000, 1030, 1000, 0, 10, "Oxhead and Horseface 2", Traits.Resurrects), // morale new Unit(2440, 30, 0, 0, 10, "Travelling Band 1", Traits.Eager), new Unit(2420, 50, 0, 0, 10, "Travelling Band 2", Traits.Plucky), new Unit(2410, 20, 40, 20, 10, "Travelling Band 3", Traits.EagleEyed), new Unit(2410, 0, 0, 0, 10, "Travelling Band 4"), new Unit(2400, 0, 50, 10, 10, "Travelling Band 5"), new Unit(2330, 10, 0, 10, 9, "Travelling Band 6"), new Unit(2280, 0, 0, 0, 9, "Travelling Band 7"), // combat new Unit(-40, 2440, 0, 0, 10, "Ferocious Tiger-Rider 1", Traits.MiseryGuts), new Unit(20, 2410, 0, 0, 10, "Ferocious Tiger-Rider 2"), new Unit(10, 2400, -10, 0, 10, "Ferocious Tiger-Rider 3", Traits.ShortSighted), new Unit(0, 2400, 0, 0, 10, "Ferocious Tiger-Rider 4"), new Unit(0, 2400, 0, 0, 10, "Ferocious Tiger-Rider 5"), new Unit(-40, 2400, 0, 30, 10, "Ferocious Tiger-Rider 6", Traits.MiseryGuts), new Unit(30, 2700, 20, 0, 8, "Sea-fort Guard 1"), // seafaring new Unit(10, 50, 2400, 10, 10, "Harem of Fortune Tellers 1"), new Unit(0, 0, 2400, 10, 10, "Harem of Fortune Tellers 2"), new Unit(0, 40, 2400, 0, 10, "Harem of Fortune Tellers 3"), new Unit(50, 0, 2400, 50, 10, "Harem of Fortune Tellers 4"), new Unit(40, 20, 2430, 0, 10, "Harem of Fortune Tellers 5", Traits.Eager), new Unit(60, 80, 2450, 100, 10, "Harem of Fortune Tellers 6", Traits.MultiTalented), new Unit(0, 70, 2710, 0, 8, "Pearl Diver 1", Traits.Plucky), }.OrderBy(c => c.Morale + c.Combat + c.Seafar); var voyages = new[] { new Voyage(115, 115, 1), new Voyage(115, 1, 115), new Voyage(1, 115, 115), //new Voyage(115, 115, 115), }; var crews = GetCombinationsWithoutRepetition(roster.ToList(), 5).OrderBy(c => c.Sum(m => m.Level)).ToList(); Console.WriteLine("Total crew combinations: " + crews.Count); var stopwatch = new Stopwatch(); stopwatch.Start(); var possibleVoyages = PossibleVoyages(rams, decks, hulls, captains, crews, 50, new List()); foreach (var possibleVoyage in possibleVoyages) { // we need to calculate rating of each ship somehow Console.WriteLine(possibleVoyage.GetHashCode()); } /* // get ship combinations for every voyage Parallel.ForEach(voyages, voyage => { voyage.Ships = voyage.GetPossibleShips(93, rams, decks, hulls, captains, crews).OrderByDescending(s => s.Rate).ToList(); Console.WriteLine(voyage); }); stopwatch.Stop(); Console.WriteLine(stopwatch.ElapsedMilliseconds); stopwatch.Start(); for (var fleetSize = 1; fleetSize <= Math.Min(3, voyages.Length); fleetSize++) { Parallel.ForEach(new Combinations(voyages, fleetSize), voyagesCombo => { Ship[] bestFleet = null; switch (fleetSize) { case 3: bestFleet = GetBestFleet3(voyagesCombo); break; case 2: //bestFleet = GetBestFleet2(voyagesCombo); break; case 1: //bestFleet = GetBestFleet1(voyagesCombo); break; } if (bestFleet == null) { return; } lock (_syncLock) { Console.WriteLine("================================================================="); for (var i = 0; i < fleetSize; i++) { var ship = bestFleet[i]; Console.WriteLine("\n******* {0} *******", voyagesCombo[i]); Console.WriteLine("Ram\t{0}", ship.Ram); Console.WriteLine("Deck1\t{0}", ship.Deck1); Console.WriteLine("Deck2\t{0}", ship.Deck2); Console.WriteLine("Hull\t{0}", ship.Hull); Console.WriteLine("Captain\t{0}", ship.Captain); foreach (var crewMember in ship.Crew) { Console.WriteLine("Crew\t{0}", crewMember); } Console.WriteLine("\t{0}\t{1}\t{2}\t{3}\t{4}%", ship.Morale, ship.Combat, ship.Seafar, ship.Speed, ship.Rate); } Console.WriteLine("\n================================================================="); } }); } */ stopwatch.Stop(); Console.WriteLine(stopwatch.ElapsedMilliseconds); Console.Write("\nPress [q] to quit..."); do { } while (Console.ReadKey().Key != ConsoleKey.Q); } private static Ship[] GetBestFleet3(IList voyages) { // 10771, 10779, 11103, 10859, 10742 ~ 10851 var bestRate = 0; var worstVariance = 100.0; Ship[] fleet = null; foreach (var ship0 in voyages[0].Ships) { foreach (var ship1 in voyages[1].Ships.Where(s1 => !s1.Equals(ship0))) { foreach (var ship2 in voyages[2].Ships.Where(s2 => !s2.Equals(ship0) && !s2.Equals(ship1))) { var variance = Statistics.Variance(ship0, ship1, ship2); var rate = ship0.Rate + ship1.Rate + ship2.Rate; if (rate >= bestRate || rate == bestRate && variance < worstVariance) { bestRate = rate; worstVariance = variance; fleet = new[] {ship0, ship1, ship2}; if (ship0.Rate >= 100 && ship1.Rate >= 100 && ship2.Rate >= 100) { return fleet; } } } } } return fleet; } private static IEnumerable> PossibleVoyages(IList rams, IList decks, IList hulls, IList captains, IList> crews, int voyagesToPrepare, IList fleet) { var possibleVoyages = new List>(); if (voyagesToPrepare == 0) { possibleVoyages.Add(fleet); } if (captains.Count < voyagesToPrepare || crews.Count < voyagesToPrepare) { // We cannot find any valid solution here return possibleVoyages; } foreach (var ram in rams) { foreach (var deck1 in decks) { foreach (var deck2 in decks) { foreach (var hull in hulls) { foreach (var captain in captains) { foreach (var crew in crews) { fleet.Add(new Ship(ram, deck1, deck2, hull, captain, crew)); var newFleet = fleet; possibleVoyages.AddRange( PossibleVoyages( rams, decks, hulls, captains.Where(c => c != captain).ToList(), crews.Where(c => c != crew).ToList(), voyagesToPrepare - 1, newFleet)); } } } } } } return possibleVoyages; } private static Ship[] GetBestFleet2(IList voyages) { var bestRate = 0; var worstVariance = 100.0; Ship[] fleet = null; foreach (var ship0 in voyages[0].Ships) { foreach (var ship1 in voyages[1].Ships.Where(s1 => !s1.Equals(ship0))) { var variance = Statistics.Variance(ship0, ship1); if (ship0.Rate + ship1.Rate > bestRate || ship0.Rate + ship1.Rate == bestRate && variance < worstVariance) { bestRate = ship0.Rate + ship1.Rate; worstVariance = variance; fleet = new[] { ship0, ship1 }; if (ship0.Rate >= 100 && ship1.Rate >= 100) { return fleet; } } } } return fleet; } private static Ship[] GetBestFleet1(IList voyages) { if (voyages[0].Ships.Count == 0) { return null; } return new[] { voyages[0].Ships[0] }; } private static IEnumerable> GetCombinationsWithoutRepetition(IList values, int lowerIndex) { foreach (IList permutation in new PermutationsWithoutRepetition(values.Select((t, i) => i < values.Count - lowerIndex))) { var list = new List(); for (var i = 0; i < permutation.Count; i++) { if (!permutation[i]) { list.Add(values[i]); } } yield return list; } } } }
 using System; using System.Collections.Generic; using System.Threading; namespace aLfPoP { internal class Ship : IEquatable { private static readonly ThreadLocal> _uniques = new ThreadLocal>(() => new List(5)); public Ship(Unit ram, Unit deck1, Unit deck2, Unit hull, Unit captain, IList crew) { Ram = ram; Deck1 = deck1; Deck2 = deck2; Hull = hull; Captain = captain; Crew = crew; Morale = ram.Morale + deck1.Morale + deck2.Morale + hull.Morale + captain.Morale; Combat = ram.Combat + deck1.Combat + deck2.Combat + hull.Combat + captain.Combat; Seafar = ram.Seafar + deck1.Seafar + deck2.Seafar + hull.Seafar + captain.Seafar; //Speed = ram.Speed + deck1.Speed + deck2.Speed + hull.Speed + captain.Speed; const double moraleBonus = 1.03; const double combatBonus = 1.03; var seafaringBonus = 1.05; //const double speedBonus = 1.03; var uniques = _uniques.Value; uniques.Clear(); var solidaryUnits = 0; foreach (var unit in crew) { Morale += unit.Morale; Combat += unit.Combat; Seafar += unit.Seafar; //Speed += unit.Speed; if (!uniques.Contains(unit.Name)) { uniques.Add(unit.Name); } if ((unit.Traits & Traits.Solidarity) != 0) { solidaryUnits += 1; } if ((unit.Traits & Traits.Seafriend) != 0) { seafaringBonus += 0.01; } } if (solidaryUnits != 0) { var solidarityBonus = (uniques.Count + 1) * 100 * solidaryUnits; Morale += solidarityBonus; Combat += solidarityBonus; Seafar += solidarityBonus; } Morale = (int) (moraleBonus * Morale); Combat = (int) (combatBonus * Combat); Seafar = (int) (seafaringBonus * Seafar); //Speed = (int) (speedBonus * Speed); } public Unit Ram { get; private set; } public Unit Deck1 { get; private set; } public Unit Deck2 { get; private set; } public Unit Hull { get; private set; } public Unit Captain { get; private set; } public IList Crew { get; private set; } public int Morale { get; private set; } public int Combat { get; private set; } public int Seafar { get; private set; } public int Speed { get; private set; } public int Rate { get; internal set; } public bool Equals(Ship other) { if (ReferenceEquals(null, other)) { return false; } if (ReferenceEquals(this, other)) { return true; } if (Captain == other.Captain) { return true; } foreach (var member in Crew) { if (other.Crew.Contains(member)) { return true; } } return false; } public override bool Equals(object other) { return Equals(other as Ship); } public override int GetHashCode() { unchecked { var hashCode = Ram.GetHashCode(); hashCode = (hashCode * 397) ^ Deck1.GetHashCode(); hashCode = (hashCode * 397) ^ Deck2.GetHashCode(); hashCode = (hashCode * 397) ^ Hull.GetHashCode(); hashCode = (hashCode * 397) ^ Captain.GetHashCode(); hashCode = (hashCode * 397) ^ Crew.GetHashCode(); hashCode = (hashCode * 397) ^ Rate; return hashCode; } } } }
 namespace aLfPoP { internal class ShipBase { public ShipBase(Unit ram, Unit deck1, Unit deck2, Unit hull) { Ram = ram; Deck1 = deck1; Deck2 = deck2; Hull = hull; Morale = ram.Morale + deck1.Morale + deck2.Morale + hull.Morale; Combat = ram.Combat + deck1.Combat + deck2.Combat + hull.Combat; Seafar = ram.Seafar + deck1.Seafar + deck2.Seafar + hull.Seafar; Speed = ram.Speed + deck1.Speed + deck2.Speed + hull.Speed; } public Unit Ram { get; private set; } public Unit Deck1 { get; private set; } public Unit Deck2 { get; private set; } public Unit Hull { get; private set; } public int Morale { get; private set; } public int Combat { get; private set; } public int Seafar { get; private set; } public int Speed { get; private set; } public override string ToString() { return string.Format("\t{0}\t{1}\t{2}\t{3}", Morale, Combat, Seafar, Speed); } } }
 using System; using System.Collections.Generic; namespace aLfPoP { static class Statistics { public static double StdDev(this IEnumerable values) { double mean = 0.0; double sum = 0.0; double stdDev = 0.0; int n = 0; foreach (double val in values) { n++; double delta = val - mean; mean += delta / n; sum += delta * (val - mean); } if (1 < n) stdDev = Math.Sqrt(sum / (n - 1)); return stdDev; } public static double StdDev(this IEnumerable values) { double mean = 0.0; double sum = 0.0; double stdDev = 0.0; int n = 0; foreach (double val in values) { n++; double delta = val - mean; mean += delta / n; sum += delta * (val - mean); } if (1 < n) { stdDev = Math.Sqrt(sum / n); } return stdDev; } public static double StdDev(this IEnumerable ships) { double mean = 0.0; double sum = 0.0; double stdDev = 0.0; int n = 0; foreach (var ship in ships) { n++; double delta = ship.Rate - mean; mean += delta / n; sum += delta * (ship.Rate - mean); } if (1 < n) { stdDev = Math.Sqrt(sum / n); } return stdDev; } public static double Variance(Ship ship0, Ship ship1) { double mean = (ship0.Rate + ship1.Rate) / 2.0; return (ship0.Rate - mean) * (ship0.Rate - mean) + (ship1.Rate - mean) * (ship1.Rate - mean); } public static double Variance(Ship ship0, Ship ship1, Ship ship2) { double mean = (ship0.Rate + ship1.Rate + ship2.Rate) / 3.0; return (ship0.Rate - mean) * (ship0.Rate - mean) + (ship1.Rate - mean) * (ship1.Rate - mean) + (ship2.Rate - mean) * (ship2.Rate - mean); } } }
 using System; namespace aLfPoP { [Flags] internal enum Traits : long { None = 0x0, Albatross = 0x1, AweInspiring = 0x2, Cowardly = 0x4, Eager = 0x8, EagleEyed = 0x10, FastLearner = 0x20, GoodFortune = 0x40, Landlubber = 0x80, Leader = 0x100, Liability = 0x200, Loyal = 0x400, Merchant = 0x800, MiseryGuts = 0x1000, MultiTalented = 0x2000, Mutinous = 0x4000, Opportunist = 0x8000, Pacifist = 0x10000, Plucky = 0x20000, QuickFooted = 0x40000, RallyingCry = 0x80000, Seafriend = 0x100000, ShortSighted = 0x200000, Slayer = 0x400000, Solidarity = 0x800000, Staunch = 0x1000000, StormMagnet = 0x2000000, Tactician = 0x4000000, ToughAsNails = 0x8000000, Workhorse = 0x10000000, SlowWitted = 0x20000000, Seafarer = 0x40000000, Lookout = 0x80000000, Resurrects = 0x100000000, Vapid = 0x200000000 } }
 namespace aLfPoP { internal class Unit { public Unit(int morale, int combat, int seafaring, int speed, int level, string name, Traits traits) { Morale = morale; Combat = combat; Seafar = seafaring; Speed = speed; Level = level; Name = name; Traits = traits; } public Unit(int morale, int combat, int seafaring, int speed, int level, string name) : this(morale, combat, seafaring, speed, level, name, Traits.None) { } public int Morale { get; private set; } public int Combat { get; private set; } public int Seafar { get; private set; } public int Speed { get; private set; } public int Level { get; private set; } public string Name { get; private set; } public Traits Traits { get; private set; } public override string ToString() { return string.Format("{0}\t{1}\t{2}\t{3}\t{4} ({5})", Morale, Combat, Seafar, Speed, Name, Level); } } }
 using System; using System.Collections.Generic; using System.Linq; using aLfPoP.Combinatorics; namespace aLfPoP { internal class Voyage { public Voyage(int morale, int combat, int seafaring) { Morale = morale; Combat = combat; Seafar = seafaring; } public int Morale { get; private set; } public int Combat { get; private set; } public int Seafar { get; private set; } public List Ships { get; set; } public IEnumerable GetPossibleShips(int minimumRate, IList rams, IList decks, IList hulls, IList captains, IList> crews) { // get best ship base IEnumerable bestShipBases; if (Combat == 1 && Seafar == 1) { // morale bestShipBases = new[] { new ShipBase(rams[0], decks[0], decks[0], hulls[0]) }; } else if (Morale == 1 && Seafar == 1) { // combat bestShipBases = new[] { new ShipBase(rams[1], decks[1], decks[1], hulls[1]) }; } else if (Morale == 1 && Combat == 1) { // seafaring bestShipBases = new[] { new ShipBase(rams[0], decks[2], decks[2], hulls[2]) }; } else if (Seafar == 1) { // morale + combat bestShipBases = from ram in rams from deckCombos in new Combinations(new[] { decks[0], decks[1] }, 2, GenerateOption.WithRepetition) from hull in new[] { hulls[0], hulls[1] } select new ShipBase(ram, deckCombos[0], deckCombos[1], hull); } else if (Combat == 1) { // morale + seafaring bestShipBases = from deckCombos in new Combinations(new[] { decks[0], decks[2] }, 2, GenerateOption.WithRepetition) from hull in new[] { hulls[0], hulls[2] } select new ShipBase(rams[0], deckCombos[0], deckCombos[1], hull); } else if (Morale == 1) { // combat + seafaring bestShipBases = from deckCombos in new Combinations(new[] { decks[1], decks[2] }, 2, GenerateOption.WithRepetition) from hull in new[] { hulls[1], hulls[2] } select new ShipBase(rams[1], deckCombos[0], deckCombos[1], hull); } else { // morale + combat + seafaring bestShipBases = from ram in rams from deckCombos in new Combinations(decks, 2, GenerateOption.WithRepetition) from hull in hulls select new ShipBase(ram, deckCombos[0], deckCombos[1], hull); } foreach (var shipBase in bestShipBases) { foreach (var captain in captains) { foreach (var crew in crews) { var ship = new Ship(shipBase.Ram, shipBase.Deck1, shipBase.Deck2, shipBase.Hull, captain, crew); // calculate ship rating for this voyage var rm = ship.Morale / Morale; var rc = ship.Combat / Combat; var rs = ship.Seafar / Seafar; ship.Rate = rm > rc ? (rc > rs ? rs : rc) : (rm > rs ? rs : rm); if (ship.Rate >= minimumRate && ship.Rate <= 100) { yield return ship; } } } } } public override string ToString() { return string.Format("Voyage ({0}, {1}, {2}) [{3}]", Morale, Combat, Seafar, Ships.Count); } } }