example lottery model kata

lotterymodel.cpp

/*
This is an example of modelling someone's lottery ticket collection.

I find this an interesting/worthwhile problem domain as the constraints are easy to understand,
but detials in both design and implementation prove more difficult than intuition might suggest.
Also, it is a sufficiently isolated to tend well towards existing as a TDD kata.

The constraints are as follows:

1. A lottery ticket takes the form of 6 balls. The first 5 range from 1-59, and the final ranges from 1-35.
2. The user must be able to purchase any number up to a maximum of 25,022,350,465 tickets (all possible combos).
3. The user cannot purchase duplicates.
4. The user has 3 ways of purchasing tickets:
  4a. Individually specifying a single ticket
  4b. Specifying a starting ticket and a "run" of subsequent tickets (ie "ticket 23 55 01 12 49 21 and the next 5 Billion")
  4c. Choosing a number of tickets to be randomly assigned (ie "give me 5 Billion tickets at random")
5. The set of owned tickets must be queryable for a given winning ticket
6. The winning ticket is NOT known at the time of purchase
7. EVERYTHING MUST RUN IN REASONABLE SPACE + TIME ON A MODERN SMARTPHONE
(hint- storing a list of all tickets given a ticket = unsigned char[6] will require ~125GB memory)

8. CHALLENGE- the user must be able to request an invalid range of tickets.
you must correctly give them the max amt of tickets they can validly purchase within that range.
(either fully/partially containing already owned tickets, more tickets than they have money for, etc...)

9. CHALLENGE- the user must be able to browse all owned tickets (for example, in a list similar to a contacts application)

Questions/Hints:
What data structures should I use?
How can I represent a ticket?
How can I "compress" this data?
What can I reasonably "hide" from the user without violating any constraints?


--SPOILERS--
I recommend thinking about how YOU could implement this before continuing. 


What I did:
A ticket is simply a long long, with 0ll corresponding to ticket 01 01 01 01 01 01. 
Unfortunately, a long is JUST short of having enough bits to store this, so admittedly quite a bit of data is wasted.
However, our methods of 'compression' make up for it more than sufficiently for that to truly be a problem.
We store 'runs' of tickets in a variable length array as ordered 'ticket_from','ticket_to' pairs
When the user purchases a single ticket, it is stored as a run from x to itself.
All purchases are merged as necessary. (ex, owning run [0,10] and purchasing [11-20] results in 1 run of [0,20])
For requests of random tickets, we simply keep track of how many we own, NO ACTUAL TICKETS ARE STORED
At the time of the winning ticket draw, we search the list of runs if it exists.
If not, we calculate the number of possible tickets NOT in the list of runs.
We pick a random number between 0 and that number; if it is below the number of random tickets we own, we say we win.
When a user is browing the tickets in their list, we show them each ticket as owned in the list of runs.
When that list runs out, we start -in real time- decrementing the number of owned random tickets, choose a random ticket, add it to the list of runs (NOT IMPLEMENTED- See notes further down for problems with this strategy)

Problems with what I did:
The user can still use way more memory than we have by purchasing individually every-other ticket.
However, for them to blow our memory allotment, that would take a massive amount of time on their part so I don't really care.
With selecting a random ticket in real time as the list is exhausted, we run into the problem of ordering the list.
If we wait to generate random tickets until after we get to the end of their intentionally bought ones, that means that we're only
choosing random tickets that are GREATER than their largest ticket. Also, if they bought the max ticket intentionally (59 59 59 59 59 35)
we run out of space to choose tickets randomly. Or, we resort to picking tickets randomly between their owned runs, 
which will cause the list to jitter from the middle when we're at the end of the list. OR we pick the tickets randomly, but always append
them to the END of the list, but this invalidates ordering which means we need an additional data structure to keep track of that.
The RIGHT way to do this (to the best of my knowledge) is instead of at the end of the list, we generate the tickets randomly at the end of every RUN
calculating how likely (given number of random tickets) it is that such a random ticket will fall in between the current run and the next one.

Some interesting struggles I came across in my implementation:

Converting ticket indexes to human readable tickets (ie "ticket 0" to "01 01 01 01 01 01") is kind of an amusing process.
It's similar to converting an int to a decimal string, but is 'base 35' for the first place, and 'base 59' for the others.
PLUS, they are '1' indexed- 0 is an invalid place. Smells like an interview question (tee hee).

Merging a range into a list of ranges has A TON of edge cases. SO many opportunities for off-by-1 errors. I initially thought
it should be pretty straightforward- ended up taking me much longer than I'm comfortable admitting. (TDD proved by far most helpful here)
Tried three different implementations before I got it right (from set-theory-esque [more complicated than neccessary] to discrete iteration 
[super simple, but runtime is astronomical] to finally KISS [you can see for yourself below]). Highly recommend taking a second
to think about the best way to do it (also, VERY open to people informing me of easier ways to do it).

OK. So without further ado, here's my implemenation.
*/

#include "var_array.h" //this is just a very simple variable length array
#include <stdlib.h>

#define MAX_TICKET 25022350465ll //25,022,350,465 //max ll is 9,223,372,036,854,775,807
#define TICKET_MASK 0x0000000EFFFFFFFF //max bits required to hold MAX_TICKETS (gah look how much wasted data...)

#define MIN_BALL 1
#define MAX_BALL 59
#define MAX_SUPER_SPHERE 35

typedef long long ticket;
typedef long long ticket_i; //index of ticket (must be able to address any ticket)
const ticket null_ticket = -1;
const ticket_i null_ticket_i = -1;

struct ticket_run
{
  ticket ticket_from;
  ticket ticket_to;
  ticket_run() : ticket_from(0), ticket_to(0) {};
  ticket_run(ticket from, ticket to) : ticket_from(from), ticket_to(to) {};
};

//don't store these en masse- just use for simpler human readability
//even though these are technically more space efficient, a long long is easier to do math on
union ticket_human
{
  unsigned char ball[6];
  struct
  {
    unsigned char ball_1; //1-59 (MIN_BALL - MAX_BALL)
    unsigned char ball_2; //1-59
    unsigned char ball_3; //1-59
    unsigned char ball_4; //1-59
    unsigned char ball_5; //1-59
    unsigned char super_sphere; //1-35 (MIN_BALL - MAX_SUPER_SPHERE)
  } human;
};

class Model
{
  private :
    void print();
    void printRuns();

  public :
    ticket_i dollars;
    ticket_i tickets_owned;
    vArray<ticket_run> ticket_runs;
    ticket_i num_random;

    ticket_i purchaseTicket(ticket t, ticket_i run); //returns num purchased
    ticket_i purchaseRandom(ticket_i num); //returns num purchased

    ticket getTicket(ticket_i t);
    ticket_human humanReadableTicket(ticket t);
    ticket ticketFromHuman(ticket_human h);

    int testWin(ticket t);

    int run_tests();
};




//absolutely covered with edge cases
ticket_i Model::purchaseTicket(ticket t, ticket_i run_length)
{
  if(run_length < 1) return 0;
  if(t+run_length-1 > MAX_TICKET) run_length = MAX_TICKET-t+1;
  ticket_run run(t, t+run_length-1); //the run to attempt purchase

  int l = ticket_runs.length();
  ticket_i bought = 0;

  int i = 0; //first ticket that starts after run starts
  while(i < l && ticket_runs[i].ticket_from < run.ticket_from) i++;

  if(i > 0 && ticket_runs[i-1].ticket_to >= run.ticket_from-1) //run will merge with previous
    i--;
  else //run is created new
  {
    ticket_run tmp(run.ticket_from,run.ticket_from);
    bought++;
    dollars--;
    ticket_runs.insert(i,tmp);
  }

  //at this point, ticket_runs[i] is a ticket with run length at least 1 (already payed for)
  //and must be extended for the full length of the run, potentially merging with further runs

  ticket bought_til = ticket_runs[i].ticket_to;
  while(bought_til < run.ticket_to)
  {
    ticket affordable_to = (dollars < run.ticket_to-bought_til) ? bought_til+dollars : run.ticket_to;
    if(i == ticket_runs.length()-1 || affordable_to < ticket_runs[i+1].ticket_from-1) //free to purchase rest of run
    {
      bought  += affordable_to-bought_til;
      dollars -= affordable_to-bought_til;
      ticket_runs[i].ticket_to = affordable_to;
      bought_til = ticket_runs[i].ticket_to;

      tickets_owned += bought;
      return bought;
    }
    else //purchase until conflict
    {
      bought  += ticket_runs[i+1].ticket_from-bought_til-1;
      dollars -= ticket_runs[i+1].ticket_from-bought_til-1;
      ticket_runs[i].ticket_to = ticket_runs[i+1].ticket_to;
      bought_til = ticket_runs[i].ticket_to;
      ticket_runs.remove(i+1);
    }
  }

  tickets_owned += bought;
  return bought;
}

ticket_i Model::purchaseRandom(ticket_i num)
{
  if(num > dollars) num = dollars;
  if(tickets_owned+num > MAX_TICKET) num = MAX_TICKET-tickets_owned;

  dollars -= num;
  num_random += num;
  tickets_owned += num;
  return num;
}

ticket Model::getTicket(ticket_i t)
{
  for(int i = 0; i < ticket_runs.length(); i++)
  {
    if((ticket_runs[i].ticket_to-ticket_runs[i].ticket_from)+1 < t)
      t -= (ticket_runs[i].ticket_to-ticket_runs[i].ticket_from)+1;
    else
      return ticket_runs[i].ticket_from+t;
  }
  return null_ticket;
}

int Model::testWin(ticket t)
{
  for(int i = 0; i < ticket_runs.length(); i++)
  {
    if(t > ticket_runs[i].ticket_to) break;
    if(t >= ticket_runs[i].ticket_from && t <= ticket_runs[i].ticket_to) return 1;
  }
  ticket_i tickets_not_in_runs = MAX_TICKET - tickets_owned + num_random;
  if(rand() % tickets_not_in_runs < num_random) return 1;
  return 0;
}

/*
0                  : 1 1 1 1 1 1
1                  : 1 1 1 1 1 2
n<MAX_SUPER_SPHERE : 1 1 1 1 1 n+1
MAX_SUPER_SPHERE-1 : 1 1 1 1 1 MAX_SUPER_SPHERE
MAX_SUPER_SPHERE   : 1 1 1 1 2 1
*/
ticket_human Model::humanReadableTicket(ticket t)
{
  ticket_human h;
  h.human.super_sphere = t%MAX_SUPER_SPHERE;
  t -= h.human.super_sphere;
  t /= MAX_SUPER_SPHERE;
  for(int i = 4; i >= 0; i--)
  {
    h.ball[i] = t%MAX_BALL;
    t -= h.ball[i];
    t /= MAX_BALL;
  }

  for(int i = 0; i < 6; i++) //wait to add min til now for easier math
    h.ball[i] += MIN_BALL;

  return h;
}

ticket Model::ticketFromHuman(ticket_human h)
{
  ticket t = 0;
  //clearer to just write it out than use a for loop
  t += (h.human.super_sphere-MIN_BALL);
  t += (h.ball[4]-MIN_BALL)*MAX_SUPER_SPHERE;
  t += (h.ball[3]-MIN_BALL)*MAX_SUPER_SPHERE*MAX_BALL;
  t += (h.ball[2]-MIN_BALL)*MAX_SUPER_SPHERE*MAX_BALL*MAX_BALL;
  t += (h.ball[1]-MIN_BALL)*MAX_SUPER_SPHERE*MAX_BALL*MAX_BALL*MAX_BALL;
  t += (h.ball[0]-MIN_BALL)*MAX_SUPER_SPHERE*MAX_BALL*MAX_BALL*MAX_BALL*MAX_BALL;
  return t;
}










//
// TESTING / DEBUGGING
//

void Model::print()
{
  printf("Dollars: %lld",dollars);
  printf("Owned: %lld",tickets_owned);
  this->printRuns();
}
void Model::printRuns()
{
  for(int i = 0; i < ticket_runs.length(); i++)
    printf("[%lld,%lld]",ticket_runs[i].ticket_from,ticket_runs[i].ticket_to);
}

int Model::run_tests()
{
  //currently using this to actually test the model, not test whether we won
  printf("Test:");

  dollars = 100;
  ticket_i bought = 0;
  ticket t;
  ticket_human h;
  bool success = true;

  //get invalid ticket index
  t = this->getTicket(0);
  success = (t == null_ticket);
  if(success) printf("Succeeded Get invalid!");
  else { printf("Failed Get invalid!"); return 1; }

  //first purchase
  bought = this->purchaseTicket(0, 10);
  success = (
    bought == 10 &&
    dollars == 90 &&
    tickets_owned == 10 &&
    ticket_runs.length() == 1 &&
    ticket_runs[0].ticket_from == 0 &&
    ticket_runs[0].ticket_to == 9
  );
  this->print();
  if(success) printf("Succeeded first purchase!");
  else { printf("Failed first purchase!"); return 1; }

  //get valid ticket index
  t = this->getTicket(0);
  success = (t == 0);
  if(success) printf("Succeeded Get valid!");
  else { printf("Failed Get valid!"); return 1; }

  //get valid end ticket index
  t = this->getTicket(9);
  success = (t == 9);
  if(success) printf("Succeeded Get valid end!");
  else { printf("Failed Get valid end!"); return 1; }

  //second purchase
  bought = this->purchaseTicket(20, 10);
  success = (
    bought == 10 &&
    dollars == 80 &&
    tickets_owned == 20 &&
    ticket_runs.length() == 2 &&
    ticket_runs[1].ticket_from == 20 &&
    ticket_runs[1].ticket_to == 29
  );
  this->print();
  if(success) printf("Succeeded second purchase!");
  else { printf("Failed second purchase!"); return 1; }

  //get valid multi-run ticket index
  t = this->getTicket(14);
  success = (t == 24);
  if(success) printf("Succeeded Get valid multi-run!");
  else { printf("Failed Get valid multi-run!"); return 1; }

  //front overlap
  bought = this->purchaseTicket(19, 5);
  success = (
    bought == 1 &&
    dollars == 79 &&
    tickets_owned == 21 &&
    ticket_runs.length() == 2 &&
    ticket_runs[1].ticket_from == 19 &&
    ticket_runs[1].ticket_to == 29
  );
  this->print();
  if(success) printf("Succeeded front overlap!");
  else { printf("Failed front overlap!"); return 1; }

  //back overlap
  bought = this->purchaseTicket(25, 6);
  success = (
    bought == 1 &&
    dollars == 78 &&
    tickets_owned == 22 &&
    ticket_runs.length() == 2 &&
    ticket_runs[1].ticket_from == 19 &&
    ticket_runs[1].ticket_to == 30
  );
  this->print();
  if(success) printf("Succeeded back overlap!");
  else { printf("Failed back overlap!"); return 1; }

  //full overlap (buy engulfs run)
  bought = this->purchaseTicket(18, 14);
  success = (
    bought == 2 &&
    dollars == 76 &&
    tickets_owned == 24 &&
    ticket_runs.length() == 2 &&
    ticket_runs[1].ticket_from == 18 &&
    ticket_runs[1].ticket_to == 31
  );
  this->print();
  if(success)printf("Succeeded full overlap (ber) !");
  else { printf("Failed full overlap (ber)!"); return 1; }

  //full overlap (run engulfs buy)
  bought = this->purchaseTicket(22, 2);
  success = (
    bought == 0 &&
    dollars == 76 &&
    tickets_owned == 24 &&
    ticket_runs.length() == 2 &&
    ticket_runs[1].ticket_from == 18 &&
    ticket_runs[1].ticket_to == 31
  );
  this->print();
  if(success)printf("Succeeded full overlap (reb) !");
  else { printf("Failed full overlap (reb)!"); return 1; }

  //purchase 1
  bought = this->purchaseTicket(40, 1);
  success = (
    bought == 1 &&
    dollars == 75 &&
    tickets_owned == 25 &&
    ticket_runs.length() == 3 &&
    ticket_runs[2].ticket_from == 40 &&
    ticket_runs[2].ticket_to == 40
  );
  this->print();
  if(success) printf("Succeeded Buy 1!");
  else { printf("Failed Buy 1!"); return 1; }

  //buy begins at run of 1
  bought = this->purchaseTicket(40, 5);
  success = (
    bought == 4 &&
    dollars == 71 &&
    tickets_owned == 29 &&
    ticket_runs.length() == 3 &&
    ticket_runs[2].ticket_from == 40 &&
    ticket_runs[2].ticket_to == 44
  );
  this->print();
  if(success) printf("Succeeded front overlap 1!");
  else { printf("Failed front overlap 1!"); return 1; }

  //purchase 1 (again)
  bought = this->purchaseTicket(50, 1);
  success = (
    bought == 1 &&
    dollars == 70 &&
    tickets_owned == 30 &&
    ticket_runs.length() == 4 &&
    ticket_runs[3].ticket_from == 50 &&
    ticket_runs[3].ticket_to == 50
  );
  this->print();
  if(success)printf("Succeeded Buy 1 (redux) !");
  else { printf("Failed Buy 1 (redux)!"); return 1; }

  //buy ends at run of 1
  bought = this->purchaseTicket(46, 5);
  success = (
    bought == 4 &&
    dollars == 66 &&
    tickets_owned == 34 &&
    ticket_runs.length() == 4 &&
    ticket_runs[3].ticket_from == 46 &&
    ticket_runs[3].ticket_to == 50
  );
  this->print();
  if(success) printf("Succeeded back overlap 1!");
  else { printf("Failed back overlap 1!"); return 1; }

  //take over the whole thing
  bought = this->purchaseTicket(0, 60);
  success = (
    bought == 26 &&
    dollars == 40 &&
    tickets_owned == 60 &&
    ticket_runs.length() == 1 &&
    ticket_runs[0].ticket_from == 0 &&
    ticket_runs[0].ticket_to == 59
  );
  this->print();
  if(success) printf("Succeeded takeover!");
  else { printf("Failed takeover!"); return 1; }

  //run out of money
  bought = this->purchaseTicket(70, 50);
  success = (
    bought == 40 &&
    dollars == 0 &&
    tickets_owned == 100 &&
    ticket_runs.length() == 2 &&
    ticket_runs[1].ticket_from == 70 &&
    ticket_runs[1].ticket_to == 109
  );
  this->print();
  if(success) printf("Succeeded run out of money!");
  else { printf("Failed run out of money!"); return 1; }

  dollars = 100; //REPLENISH FUNDS FOR MORE TESTING

  //start next to run
  bought = this->purchaseTicket(60, 2);
  success = (
    bought == 2 &&
    dollars == 98 &&
    tickets_owned == 102 &&
    ticket_runs.length() == 2 &&
    ticket_runs[0].ticket_from == 0 &&
    ticket_runs[0].ticket_to == 61
  );
  this->print();
  if(success) printf("Succeeded start next!");
  else { printf("Failed start next!"); return 1; }

  //finish next to run
  bought = this->purchaseTicket(68, 2);
  success = (
    bought == 2 &&
    dollars == 96 &&
    tickets_owned == 104 &&
    ticket_runs.length() == 2 &&
    ticket_runs[1].ticket_from == 68 &&
    ticket_runs[1].ticket_to == 109
  );
  this->print();
  if(success) printf("Succeeded finish next!");
  else { printf("Failed finish next!"); return 1; }

  //fill gap exactly
  bought = this->purchaseTicket(62, 6);
  success = (
    bought == 6 &&
    dollars == 90 &&
    tickets_owned == 110 &&
    ticket_runs.length() == 1 &&
    ticket_runs[0].ticket_from == 0 &&
    ticket_runs[0].ticket_to == 109
  );
  this->print();
  if(success) printf("Succeeded fill gap!");
  else { printf("Failed fill gap!"); return 1; }

  //final test- a combination of a ton of BS
    //first, just buy a bunch of runs to set up the scene (no need to verify validity- previous tests should suffice)
  this->purchaseTicket(120, 12);
  this->purchaseTicket(140, 5);
  this->purchaseTicket(150, 1);
  this->purchaseTicket(199, 1);
    //purchase will start in middle of a run, merge/engulf multiple runs of various lengths, and run out of money on the ticket before final run
  bought = this->purchaseTicket(10, 10000);
  success = (
    bought == 71 &&
    dollars == 0 &&
    tickets_owned == 200 &&
    ticket_runs.length() == 1 &&
    ticket_runs[0].ticket_from == 0 &&
    ticket_runs[0].ticket_to == 199
  );
  this->print();
  if(success) printf("Succeeded fill gap!");
  else { printf("Failed fill gap!"); return 1; }

  //lose lottery draw
  success = !this->testWin(200);
  if(success) printf("Succeeded losing draw!");
  else { printf("Failed losing draw!"); return 1; }

  //win lottery draw
  success = this->testWin(199);
  if(success) printf("Succeeded winning draw!");
  else { printf("Failed winning draw!"); return 1; }

  //STATELESS TESTS
  //get human ticket 0
  h = this->humanReadableTicket(0);
  success = (
    h.ball[0] == MIN_BALL &&
    h.ball[1] == MIN_BALL &&
    h.ball[2] == MIN_BALL &&
    h.ball[3] == MIN_BALL &&
    h.ball[4] == MIN_BALL &&
    h.ball[5] == MIN_BALL
    );
  if(success) printf("Succeeded Get human ticket 0!");
  else { printf("Failed Get human ticket 0!"); return 1; }

  //convert human 0 back
  t = this->ticketFromHuman(h);
  success = (t == 0);
  if(success) printf("Succeeded ticket from human 0!");
  else { printf("Failed Get ticket from human 0!"); return 1; }

  //get human ticket MAX_SUPER_SPHERE
  h = this->humanReadableTicket(MAX_SUPER_SPHERE);
  success = (
    h.ball[0] == MIN_BALL &&
    h.ball[1] == MIN_BALL &&
    h.ball[2] == MIN_BALL &&
    h.ball[3] == MIN_BALL &&
    h.ball[4] == MIN_BALL+1 &&
    h.ball[5] == MIN_BALL
    );
  if(success) printf("Succeeded Get human ticket MAX_SUPER_SPHERE!");
  else { printf("Failed Get human ticket MAX_SUPER_SPHERE!"); return 1; }

  //convert human MAX_SUPER_SPHERE back
  t = this->ticketFromHuman(h);
  success = (t == MAX_SUPER_SPHERE);
  if(success) printf("Succeeded ticket from human MAX_SUPER_SPHERE!");
  else { printf("Failed Get ticket from human MAX_SUPER_SPHERE!"); return 1; }

  //get human ticket MAX_BALL*MAX_SUPER_SPHERE
  h = this->humanReadableTicket(MAX_BALL*MAX_SUPER_SPHERE);
  success = (
    h.ball[0] == MIN_BALL &&
    h.ball[1] == MIN_BALL &&
    h.ball[2] == MIN_BALL &&
    h.ball[3] == MIN_BALL+1 &&
    h.ball[4] == MIN_BALL &&
    h.ball[5] == MIN_BALL
    );
  if(success) printf("Succeeded Get human ticket MAX_BALL*MAX_SUPER_SPHERE!");
  else { printf("Failed Get human ticket MAX_BALL*MAX_SUPER_SPHERE!"); return 1; }

  //convert human MAX_BALL*MAX_SUPER_SPHERE back
  t = this->ticketFromHuman(h);
  success = (t == MAX_BALL*MAX_SUPER_SPHERE);
  if(success) printf("Succeeded ticket from human MAX_BALL*MAX_SUPER_SPHERE!");
  else { printf("Failed Get ticket from human MAX_BALL*MAX_SUPER_SPHERE!"); return 1; }

  printf("Success");
}