Programming Exercise #8: Parking

[Mark Sir Link]

The length of the array is increased to units + 1 to reconcile the idea of each element of the array scaling from the beginning of that index that index to the beginning of the next, IE, 0-1, 1-2, ..., 100-0

It doesn't matter if temp.isgap starts as true or false, and it's possible to see a sort of representation of how the cars align by returning lot instead of this.parkedcars.




Code:

PHP Code:

function onCreated(){
  this.gapmax = 1;
  this.gapmin = 0;
  temp.val1 = findMin(100, 2);
  temp.val2 = findMax(100, 2);
  echo(val1);
  echo(val2);
  for(temp.i = 0; i < 100; i++){
    temp.val3 += findRand(100, 2);
  }
  echo(val3/100);
}

function findMin(units, carlength){
  this.parkedcars = 0;
  temp.isgap = false;
  for(temp.i = 0; i < units+1; i++){
    temp.lot.add("E");
  }
  for(temp.i = 0; i < lot.size(); i++){
    temp.isgap = !temp.isgap;
    if(!temp.isgap){
      lot = parkCar(lot, i);
      i++;
    }
  }
  return this.parkedcars; 
}

function findRand(units, carlength){
  temp.i = int(random(0,2));
  if(i == 0){
    return findMin(units, carlength);
  }
  else{
    return findMax(units, carlength);
  }
}

function parkCar(arr, i){
  if(i + 1 == arr.size()){
    temp.val = 0;
  }
  else{
    temp.val = i + 1;
  }
  if(arr[i] == "E" && arr[val] == "E"){
    arr[i] = "C";
    arr[val] = "C";
    this.parkedcars++;
  }
  return arr;
}

function findMax(units, carlength){
  return int((units+1)/carlength); 
} 


Output:

PHP Code:

34
50
42.96 


[Tolnaftate2004]

Originally Posted by Mark Sir Link

The length of the array is increased to units + 1 to reconcile the idea of each element of the array scaling from the beginning of that index that index to the beginning of the next, IE, 0-1, 1-2, ..., 100-0

snip

As best as I can tell, this is just an expensive way to compute (min+max)/2, which isn't right.

My hint would be to first consider the lot when it is empty; the first car comes along and parks anywhere at all. After this event, we have 1 car in the lot and the lot is now linear (the endpoints being the front and end of our first car). On top of that, the size of the lot has shrunken to N-2. Then you just have to consider every possible arrangement of cars in a linear lot of length N-2.

What do you have after the next car arrives?