Lottery, C# - rextester

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