Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Lottery
//Rextester.Program.Main is the entry point for your code. Don't change it. //Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5 /******************************************************************************************** * Arp's Code - Lottery * Written by Arpana Mansfield for a Coding Challenge * * Requirement: Given a string of numbers, generate 7 lottery numbers between 1-59. Each * number should be unique and may only utilitize a number next to it. Only * return valid solutions. * Input: a string of numbers in the format: ["xxxx","xxxx",...] (requirment) * solution will accept other formats: "xxxx","xxxx",... and xxxx,xxxx,... * Output: 1234567 -> 1 2 3 4 5 6 7 * 564871245 -> 5 6 4 8 7 12 45 * * Description of implementation: I take a two step process: * 1) Find which joints are valid and which ones aren't. * The string of digits that are connected with valid possible joints, "words". The way I determine the words is * by traversing. For example, "123497123" would produce these words "12349", "7", "124". * This also lets me know the minimal number of words required.For example, "9876129183711" would produce * "9","8","7","6","129","18","37","11" and no valid lottery number would be produced because the * minimum number of words is 8. * 2) Determining the frequency of each digit and each digit pair. I apply the most frequent pair to the * shortest word first and continue. If a viable solution is not found, then I try the next frequent * pair. I select the shortest word because they have the fewest joints to manipulate. For example, * "123" could become only "12","23", or "1 2 3"; while "1234" could become "1 23 4","12 34","12 3 4","1 2 34", * "1 2 3 4". So making sure "123" is right early is more important than "1234". I select the most * frequent pair because I need to make sure they are used in double-digit words as possible. * *****************************************************************************************************/ using System; using System.Collections.Generic; using System.Linq; using System.Text.RegularExpressions; using System.IO; namespace Rextester { public class Program { public class pointers { public int position = 0; public int joints = 0; } public class frequencies { public int value = 0; public List<int> positions = new List<int>(); public int freq = 0; } public class lottery{ public int[] inputArray; public int[] jointArray; public List<pointers> pointerList = new List<pointers>(); public List<frequencies> frequencyList = new List<frequencies>(); public int frequencyCount = 0; public lottery(){} // Constructor /******************************************************************* ** GenerateLotteryNumbers ** Creates the Lottery Numbers and if returns ** ** TRUE if it was successful ** FALSE if a suitable solution could not be found ********************************************************************/ public bool GenerateLotteryNumbers(int[] numberArray) { //If the number is too big or too small, fail if (numberArray.Length<7 || numberArray.Length>14) { return false; } //Assign input to class variable inputArray = numberArray; //Get a pattern of the viable joints. This will show the minimum number of "words" the string //will allow. if the minimum is >7 then fail because there is not way to reduce further jointArray = GetJointPattern(); //Get a list of points that represent the number of "word" and the number of joints //in the word pointerList = GetPointers(); if (pointerList == null) return false; //The frequency of each digit and each pair frequencyList = GetFrequency(); //Check the frequent pair ApplyFrequency(); //if the most frequent pair didn't work, then check the other pairs in order of frequency if ((pointerList==null || pointerList.Count!=7) && frequencyCount>1) { //once a viable solution is found or pairs are exhausted stop for (int i = 1; (i<frequencyCount) && (pointerList==null || pointerList.Count!=7);i++) { jointArray = GetJointPattern(); pointerList = GetPointers(); frequencyList = GetFrequency(); ApplyFrequency(i); } } //return whether a viable solution was found or not return (pointerList!=null && pointerList.Count==7); } /******************************************************************* ** GetJointPattern ** Traverses the numberstring to find the possible joints. This will ** be used later to find the words and create pointers to the word. ** Returns: ** the joint Array ********************************************************************/ public int[] GetJointPattern () { int[] jointTemp = new int[inputArray.Length]; if (inputArray.Length == 7) { return new int[7]{0,0,0,0,0,0,0}; } else { for (int i=0; i<inputArray.Length-1; i++) { if (inputArray[i]*10+inputArray[i+1]<=59) { jointTemp[i]=1; } } return jointTemp; } } /******************************************************************* ** PrintPointers ** Formats the PointerList for printing as a String. ** ** Returns: the formatted String ********************************************************************/ public String PrintPointers() { String temp=""; foreach (pointers p in pointerList) { for (int i=0; i<=p.joints;i++) {; temp = temp + inputArray[p.position+i].ToString(); } temp = temp + " "; } return temp; } /******************************************************************* ** PrintFrequencies ** Formats the FrequencyList for printing as a String. ** ** Returns: the formatted String ********************************************************************/ public String PrintFrequencies() { String temp=""; foreach (frequencies f in frequencyList) { temp = temp + f.value.ToString() + " " + f.freq.ToString(); temp = temp + " :: " ; } return temp; } /******************************************************************* ** PrintJointPattern ** Formats the JointArray for printing as a String. ** ** Returns: the formatted String ********************************************************************/ public String PrintJointPattern() { String temp=""; for (int i=0; i<jointArray.Length;i++) { temp = temp + jointArray[i].ToString(); } return temp; } /******************************************************************* ** GetPointers ** Generated the PointerList using the JointArray. ** ** Returns: List<pointers> ********************************************************************/ public List<pointers> GetPointers() { int currentJoints = 0; int totalJoints = 0; int jointsRequired = 0; List<pointers> pointerList = new List<pointers>(); for (int i = jointArray.Length-1; i>0; i--) { currentJoints += jointArray[i]; totalJoints += jointArray[i]; //00 - indicates that the second value must be single digit number as it cannot be paired // with the number in front of it or after it. So place a pointer at the second number. if ( jointArray[i-1]==0 && jointArray[i]==0) { pointers p = pointerList.Find(x=>x.joints==0 && inputArray[x.position]==inputArray[i]); if (p!=null) return null; pointers temp = new pointers(); temp.position = i; temp.joints = 0; pointerList.Add(temp); currentJoints = 0; //if at the beginning then place a pointer at the start showing the beginning is a single //digit if (i-1==0) { pointers r = pointerList.Find(x=> x.joints==0 && inputArray[x.position]==inputArray[i-1]); if ( r!=null) return null; pointers temp1 = new pointers(); temp1.position = 0; temp1.joints = 0; pointerList.Add(temp1); } } //01 - Indicates the second number is the start of the new number sequence that may be more // than 2 digits and the joints between cannot be determined right now else if ( jointArray[i-1]==0 && jointArray[i]==1) { jointsRequired += currentJoints/2; pointers temp = new pointers(); temp.position = i; temp.joints = currentJoints; pointerList.Add(temp); currentJoints = 0; //if at the beginning then place a pointer at the start showing the beginning is a single //digit if (i-1==0) { pointers p = pointerList.Find(x=> x.joints==0 && inputArray[x.position]==inputArray[i-1]); if ( p!=null) return null; pointers temp1 = new pointers(); temp1.position = 0; temp1.joints = 0; pointerList.Add(temp1); } } //the second number is not the start of the number sequence, but at the beginning of the string //so the start is the beginning of the sequence string. else if (i-1==0) { currentJoints += jointArray[i-1]; totalJoints += jointArray[i-1]; jointsRequired += currentJoints/2; pointers temp = new pointers(); temp.position = 0; temp.joints = currentJoints; pointerList.Add(temp); } } //if the minimum required numbers is more than 7 then not good if (pointerList.Count>7) return null; //the number for joints required is less than allowed words if (jointsRequired>(7-pointerList.Count)) return null; pointerList = pointerList.OrderBy(x => x.position).ToList(); return pointerList; } /******************************************************************* ** ScrubPrintJoints ** In the PointerList, sets the number of joints based on the pointer ** positions. This is important when the pointers are changed and ** impacts of the joints need to synced with neighbors ********************************************************************/ public void ScrubPointerJoints() { //Sort the pointer list by position pointerList = pointerList.OrderBy(x => x.position).ToList(); //Clean up the joints for (int i=0; i<pointerList.Count; i++) { if (pointerList.Count > i+1 ) pointerList[i].joints = (pointerList[i + 1].position - pointerList[i].position) - 1; else pointerList[i].joints = inputArray.Length - pointerList[i].position - 1; } } /******************************************************************* ** HasDuplicates ** Returns whether or not the PointerList contains any duplicates in ** its digits or pairs. ** ** Returns: TRUE if duplicates are found ********************************************************************/ public bool HasDuplicates () { return (pointerList.FindAll(x => x.joints==0).GroupBy(x => inputArray[x.position]).Where(group => group.Count() > 1) .Count() + pointerList.FindAll(x => x.joints==1).GroupBy(x => inputArray[x.position]*10 + inputArray[x.position+1] ) .Where(group => group.Count() > 1) .Count()) > 0 ; } /******************************************************************* ** SplitDoubles ** Traverses the PointerList to find any pairs that can be split into single digits. ** ** Input: numNeeded, the number of splits needed to do ********************************************************************/ public void SplitDoubles (int numNeeded) { List<pointers> doubleList = pointerList.FindAll(x => x.joints==1).ToList(); for (int i=0; i<doubleList.Count && numNeeded>0;i++) { //Make sure the digits are not equal because 55 => 5 5 would not be valid if ( inputArray[doubleList[i].position] != inputArray[doubleList[i].position+1] ) { pointers firstPos = pointerList.Find(x=> x.joints==0 && (inputArray[x.position]==inputArray[doubleList[i].position])); pointers secondPos = pointerList.Find(x=> x.joints==0 && (inputArray[x.position]==inputArray[doubleList[i].position+1])); if (firstPos==null && secondPos==null ) { doubleList[i].joints=0; pointers temp = new pointers(); temp.position = doubleList[i].position+1; temp.joints = 0; pointerList.Add(temp); numNeeded--; } } } //Clean up the joints in the pointerList that was messed up by the additions ScrubPointerJoints(); //return numNeeded==0; } /******************************************************************* ** GetFrequency ** Builds the list of the frequencies for all the single and double ** digits in the NumberString ** ** Returns: List<frequencies> ********************************************************************/ public List<frequencies> GetFrequency() { //sort the pointers by those that have joints and ascending. Ascending because the shorter number //sequences have less options available List<pointers> digitList = pointerList.FindAll(x => x.joints>1).OrderBy(x => x.joints).ToList(); foreach ( pointers p in digitList) { // go through all the characters in the pointer into the frequency table for( int i = 0; i<(p.joints+1); i++) { bool isDigitAllowed = pointerList.Where(x=>x.joints==0 && inputArray[x.position]==inputArray[p.position+i]).Count()==0; if (isDigitAllowed) { frequencies singleValueFrequency = frequencyList.Find(x=>x.value==inputArray[p.position+i]); if (singleValueFrequency!=null) { singleValueFrequency.positions.Add(p.position+i); singleValueFrequency.freq++; } else { frequencies ftemp = new frequencies(); ftemp.value = inputArray[p.position+i]; ftemp.positions.Add(p.position+i); ftemp.freq++; frequencyList.Add(ftemp); } } //if the current digit isn't the last pointer, then at the current digit + next digit to the frequency table if ( i < p.joints) { bool isDoubleDigitAllowed = pointerList.Where(x=>x.joints==1 && (inputArray[x.position]==inputArray[p.position+i]) && (inputArray[x.position+1]==inputArray[p.position+i+1])).Count()==0; if (isDoubleDigitAllowed) { frequencies doubleValueFrequency = frequencyList.Find(x=>x.value==(inputArray[p.position+i]*10+inputArray[p.position+i+1])); if (doubleValueFrequency!=null) { doubleValueFrequency.positions.Add(p.position+i); doubleValueFrequency.freq++; } else { //int freqOfDigits = frequencyList.Where(x=>x.value==numberString[p.position+i] || x.value==numberString[p.position+i+1] ).Sum(s=>s.freq); frequencies ftemp = new frequencies(); ftemp.value = inputArray[p.position+i]*10+inputArray[p.position+i+1]; ftemp.positions.Add(p.position+i); ftemp.freq++; //freqOfDigits + 1; frequencyList.Add(ftemp); } } } } } frequencyCount = frequencyList.FindAll(x => x.value>9).OrderByDescending(y=>y.freq).Count(); return frequencyList; } /******************************************************************* ** ApplyFrequency() and ApplyFrequency(int) ** Uses the FrequencyList to split the numberString into lottery numbers. ** Adds pointers to the PointerList ** ********************************************************************/ public void ApplyFrequency() { ApplyFrequency(0); } public void ApplyFrequency(int step) { List<frequencies> frequencySingleList = frequencyList.FindAll(x => x.value<10).OrderByDescending(y=>y.freq).ToList(); List<frequencies> frequencyDoubleList = frequencyList.FindAll(x => x.value>9).OrderByDescending(y=>y.freq).ToList(); if (step>0 && step<frequencyDoubleList.Count) { frequencies temp = frequencyDoubleList[0]; frequencyDoubleList[0] = frequencyDoubleList[step]; frequencyDoubleList[step] = temp; } foreach ( frequencies f in frequencyDoubleList) { if (f.positions.Count>0) { int currentPos = f.positions.First(); if (currentPos>0 && jointArray[currentPos]==1 && jointArray[currentPos-1]==1) jointArray[currentPos-1]=0; if (currentPos+1<jointArray.Length) jointArray[currentPos+1] = 0; jointArray[currentPos]=1; pointers firstPosition = pointerList.Find(x=> x.position==currentPos); if (firstPosition!=null) { pointers lastPosition = pointerList.Find(x=> x.position==currentPos+2); if (lastPosition==null && currentPos+2<inputArray.Length) { pointers temp = new pointers(); temp.position = currentPos+2; temp.joints = firstPosition.joints-2; pointerList.Add(temp); } firstPosition.joints=1; } else { jointArray[currentPos+1] = 0; pointers temp = new pointers(); temp.position = currentPos; temp.joints = 1; pointerList.Add(temp); } frequencyDoubleList.ForEach(x => { x.positions.Remove(currentPos); x.positions.Remove(currentPos+1); x.freq--; }); frequencySingleList.ForEach(x => { x.positions.Remove(currentPos); x.positions.Remove(currentPos+1); x.freq = x.positions.Count; }); } } //Check if there any remaining single digits that needs to be assigned foreach ( frequencies f in frequencySingleList) { //if the digit needs to be assigned once, then do it. if (f.freq==1) { int currentPos = f.positions.First(); pointers firstPosition = pointerList.Find(x=> x.position==currentPos); jointArray[currentPos]=0; if (firstPosition==null) { pointers temp = new pointers(); temp.position = currentPos; temp.joints = 0; pointerList.Add(temp); } else { firstPosition.joints=0; } } } pointerList = pointerList.OrderBy(x => x.position).ToList(); //Quick adds were done to allow for checking and this cause joints values, sort order inconsistencies //so need to rebuild pointer list based on jointArray that was created by the frequency pointerList = GetPointers(); //If more digits are required to create 7 pointers, then start splitting some pairs if (pointerList!=null && pointerList.Count<7) { int diff=7-pointerList.Count; SplitDoubles(diff); } } } /******************************************************************* ** CleanUp ** Scrubs the string of unnecessary chararacters ** ** Input: s, the string to scrub ********************************************************************/ public static String CleanUp(String s) { //clean up - remove extra characters TODO: utilize patterns s = s.Replace("[", ""); s = s.Replace("]", ""); s = s.Replace("”", ""); s = s.Replace("\"", ""); s = s.Replace("“", ""); s = s.Replace(" ",""); //validation - remove 0's rather than throwing error because assuming uncle has large fingers and the rest of numbers are fine s = s.Replace("0",""); return s; } public static void Main(string[] args) { String s = Console.ReadLine(); //Doing some quick clean up on the string s = CleanUp(s); String[] inputArray = s.Split(','); for (int i=0;i<inputArray.Length;i++) { char[] ar_temp = inputArray[i].ToCharArray(); int[] ar = Array.ConvertAll(ar_temp, c => (int)Char.GetNumericValue(c)); lottery lotto = new lottery(); if (lotto.GenerateLotteryNumbers(ar)) { Console.Write(inputArray[i] + " -> "); Console.Write(lotto.PrintPointers()); Console.WriteLine(); } } } } }
run
|
edit
|
history
|
help
0
codejam1a1
Knapsack Problem - recursive
Typeing
c++online
Nested Namespace
linked list (add to end and beginning, and looking for cycles based on Floyd's algorithm)
Fibbonachi number by LINQ expression
4.4.20
D112
Create id