Problem:
Consider a list of lottery tickets where the only information available is the ticket number, and the contact/verification details of the purchaser. The tickets are sold as per 4 regions, East/West/North/South, and have the same as the first letter of the ticket number. Given that one has to traverse through all ticket numbers only once, design a lottery system to pick a winner.

Solution:
We are given that the list of all tickets has to be traversed and only once. Thus, our lottery winner cannot be based on a random selection amongst the list. Because, first we won't be traversing through the entire list and second that a person buying 1000 tickets will have a better chance at winning.

Given the constraint, we need to iterate over all tickets. Let's assume there are 100 tickets and we have iterated over 10 tickets by now. We need a winner amongst these 10 tickets, assuming these were the only ones. As we read 11th ticket, we need to choose a winner amongst the winner of 10 tickets, and the 11th ticket. This way we can define an approach where with every ticket processing we keep choosing between the current winner (till the last ticket) and the ticket being processed.

Thus, the solution can be coded as under,
/**
 * Copyright (C) 2011, Sandeep Gupta
 * http://www.sangupta.com
 * 
 * The file is licensed under the the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * 
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * 
 */

/**
* A simple solution to the lottery problem.
* 
* @author sangupta
* @since 27 Jun 2011
*/
public class Lottery {
 
 public static void main(String[] args) {
  List tickets = new ArrayList();
  tickets.add(new Ticket("E123", "A"));
  tickets.add(new Ticket("E345", "B"));
  tickets.add(new Ticket("N672", "C"));
  tickets.add(new Ticket("S642", "D"));
  tickets.add(new Ticket("W945", "E"));
  
  Ticket winner = selectWinner(tickets);
  System.out.println("Winner: " + winner.contactDetails);
 }
 
 /**
  * The method selects a winner amongst the given lottery tickets.
  * 
  * @param tickets
  * @return
  */
 public static Ticket selectWinner(List tickets) {
  // Usual checks
  if(tickets == null || tickets.size() == 0) {
   System.out.println("No ticket sold, thus no winner.");
   return null;
  }
  
  if(tickets.size() == 1) {
   System.out.println("Only one ticket sold, the winner is the same.");
   return tickets.get(0);
  }
  
  // iterate over all ticket
  Ticket currentWinner = tickets.get(0);
  long currentWinnerHash = ticketToHash(currentWinner);
  for(int index = 1; index < tickets.size(); index++) {
   Ticket candidate = tickets.get(index);
   
   long hash =  ticketToHash(candidate);
   double random;
   do {
    random = Math.random();
   } while(random == 0.5);
   
   if((random < 0.5) && (hash < currentWinnerHash)) {
    currentWinner = candidate;
   } else if(hash > currentWinnerHash) {
    currentWinner = candidate;
   }
   
   if(currentWinner == candidate) {
    currentWinnerHash = hash;
   }
  }
  
  return currentWinner;
 }
 
 /**
  * Store ticket details.
  */
 public static class Ticket {
  
  String ticketNumber;
  
  String contactDetails;
  
  public Ticket(String number, String details) {
   this.ticketNumber = number;
   this.contactDetails = details;
  }
  
 }

}

Consider a buyer who buys 1000 tickets. As he will buy from the same region, all his tickets will land up in the same region code. Thus, we need to randomize the region within the ticket as well and this can be done inside our ticketToHash method, as under,

  /**
  * Convert the ticket number to a long hash value
  * 
  * @param currentWinner
  * @return
  */
 private static long ticketToHash(Ticket currentWinner) {
  String number = currentWinner.ticketNumber;

  // replace the region of the ticket with a digit first
  int digit = (int) (Math.random() * 10);
  number = String.valueOf(digit) + number.substring(1);
  
  // randomize all digits
  number = shuffle(number.toCharArray());
  
  // return the hash of the number
  Long num = Long.parseLong(number);
  long randomHash = (long) ((double)num.hashCode() * new Random().nextInt(1000000));
  return randomHash;
 }

Another randomization way is to randomize the obtained digits itself. This will make sure that large ticket numbers do not necessarily produce a larger hash.

  /**
  * Shuffle for array length * 5 times, picking any two positions and swapping them
  * 
  * @param charArray
  * @return
  */
 private static String shuffle(char[] charArray) {
  if(charArray.length == 1) {
   return charArray.toString();
  }

  Random random = new Random(new Random().nextLong());
  int length = charArray.length;
  int limit = length * 5;
  for(int i = 0; i < limit; i++) {
   int position1 = random.nextInt(length);
   int position2;
   do {
    position2 = random.nextInt(length);
   } while(position1 == position2);
   
   // swap these two positions
   char temp = charArray[position1];
   charArray[position1] = charArray[position2];
   charArray[position2] = temp;
  }
  
  return String.valueOf(charArray);
 }
The above solution holds good for all conditions as mentioned in the problem statement. Improvement Areas: The part where the ticket number is converted to hash, and the hash compared to other hashes can be modified to make sure that a very high value of hash does not keeps intact as the current winner. The part may again be randomized for the same.

Hope this helps.

written by Sandeep Gupta

Monday, June 27, 2011 at 3:33 PM

Comments

0 responses to ' Lottery Ticket Winner Problem '

Post Comments