hashcode_2021/Scorer.php at master · it0243/hashcode_2021 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
<?php

class Scorer {

  protected $data;
  protected $plan;

  public function __construct($data, $plan) {
    $this->data  = $data;
    $this->plan  = $plan;
  }

  /**
   * Calculates the score of the current plan, by simulating the traffic
   * through the duration of the problem.
   */
  public function calculate() {
    $score = 0;

    $plan = $this->plan;
    $cars = $this->data['cars'];
    $streets = $this->data['streets'];
    $D = $this->data['D'];
    $F = $this->data['F'];

    $active_cars = $cars;

    $lights = static::get_lights($D, $plan);
    $traffic = [];
    $queues = [];
    $cars_ended = 0;

    $second = 0;
    $traffic[$second] = [];
    $current_lights = $lights[$second];
    foreach ($active_cars as $car_key => $car) {
      $car_str_index = 0;
      $car_str = $car['streets'][$car_str_index];
      $street = $streets[$car_str];
      $car_pos = $street['time'];
      $car_go = (in_array($car_str, $current_lights) && empty($queues[$car_str]));
      $car_ended = false;
      $queues[$car_str][$car_key] = $car_key;
      $traffic[$second][$car_key] = ['car_str' => $car_str,
        'car_str_index' => $car_str_index, 'car_pos' => $car_pos, 'car_go' => $car_go];
    }

    for ($second = 1; $second <= $D; $second++) {
      $traffic[$second] = [];
      $current_lights = $lights[$second];
      foreach ($active_cars as $car_key => $car) {
        $previous = $traffic[$second - 1][$car_key];
        $prev_car_str = $previous['car_str'];
        $prev_car_str_index = $previous['car_str_index'];
        $prev_street = $streets[$prev_car_str];
        $prev_car_pos = $previous['car_pos'];
        $end_of_prev_str = ($prev_car_pos == $prev_street['time']);
        $car_str_index = $prev_car_str_index;
        //change street
        if ($previous['car_go'] && $end_of_prev_str) {
          $car_str_index++;
          $car_pos = 1;
          unset($queues[$prev_car_str][$car_key]);
        } elseif ($previous['car_go'] && !$end_of_prev_str) {
          $car_pos = $prev_car_pos + 1;
        } else {
          $car_pos = $prev_car_pos;
        }
        $car_str = $car['streets'][$car_str_index];
        $street = $streets[$car_str];
        $car_go = ($car_pos < $street['time']) || (in_array($car_str, $current_lights)
          && (empty($queues[$car_str]) || array_key_first($queues[$car_str]) == $car_key));
        $car_ended = ($car_str == $car['streets'][$car['streets_count'] - 1]) && $car_pos == $street['time'];
        if ($car_ended) {
          $car_score = $F + ($D - $second);
          $cars[$car_key]['score'] = $car_score;
          $score += $car_score;
          unset($active_cars[$car_key]);
          unset($queues[$car_str][$car_key]);
          $cars_ended++;
        } else {
          $traffic[$second][$car_key] = ['car_str' => $car_str,
            'car_str_index' => $car_str_index, 'car_pos' => $car_pos, 'car_go' => $car_go];
          if ($car_pos == $street['time']) {
            $queues[$car_str][$car_key] = $car_key;
          }
        }
      }
    }
    return $score;
  }

  /**
   * Calculates the lights state (the streets with green lights) for the
   * timespan of the problem for each intersection.
   */
  static function get_lights($D, $intersection_plans) {
    $timespans = [];
    foreach ($intersection_plans as $plan_key => $plan) {
      $timespan = [];
      $index = 0;
      while ($index <= $D) {
        foreach ($plan as $key => $value) {
          array_push($timespan, ...array_fill($index, $value, $key));
          $index += $value;
        }
      }
      $timespans[] = $timespan;
    }
    $result = [];
    for ($i = 0; $i <= $D; $i++) {
      $result[$i] = array_column($timespans, $i);
    }
    return $result;
  }

}