Basketball game @ Facebook hacker cup 2014 qualification round

basketball_game_example_input.txt

5
6 3 2
Wai 99 131
Weiyan 81 155
Lin 80 100
Purav 86 198
Slawek 80 192
Meihong 44 109
7 93 2
Paul 82 189
Kittipat 62 126
Thomas 17 228
Fabien 57 233
Yifei 65 138
Liang 92 100
Victor 53 124
6 62 3
Meihong 33 192
Duc 62 162
Wai 70 148
Fabien 19 120
Bhuwan 48 176
Vlad 30 225
8 59 3
Anil 38 180
Song 7 187
David 65 159
Lin 45 121
Ranjeeth 39 183
Torbjorn 26 181
Clifton 57 158
Phil 3 183
4 72 1
Anh 2 187
Erling 69 226
Purav 0 199
Zejia 29 163

basketball_game_example_output.txt

Case #1: Purav Slawek Wai Weiyan
Case #2: Fabien Kittipat Liang Paul
Case #3: Bhuwan Duc Fabien Meihong Vlad Wai
Case #4: Anil Lin Phil Ranjeeth Song Torbjorn
Case #5: Erling Zejia

basketball_game_input.txt

20
7 93 2
Paul 82 189
Kittipat 62 126
Thomas 17 228
Fabien 57 233
Yifei 65 138
Liang 92 100
Victor 53 124
6 3 2
Wai 99 131
Weiyan 81 155
Lin 80 100
Purav 86 198
Slawek 80 192
Meihong 44 109
25 50 5
Aleksandar 34 200
Zihing 41 124
Andrii 14 226
Voja 91 228
Lin 83 182
Erling 53 150
Liang 74 233
Luiz 49 125
Atol 9 182
Yingsheng 82 170
Nima 71 228
Rudradev 99 142
Song 24 221
Chad 39 195
Bhuwan 54 146
Bhuwan 12 233
Zainab 88 180
Voja 79 135
Purav 79 203
Fabien 90 230
Nathan 12 148
Ranjeeth 75 133
Vladislav 88 148
Viswanath 61 158
Luiz 13 163
11 116 1
Daniel 89 224
Andriy 78 181
Chirag 91 206
Fabien 45 162
Wesley 31 166
Vasily 57 203
Wesley 88 174
Song 91 234
Purav 5 230
Andrei 88 178
Jordan 56 104
29 69 1
Duc 76 228
Ekansh 78 102
Erling 0 125
Wei 46 202
Steaphan 83 119
Zihing 57 175
Andrii 74 239
Fabien 59 177
Zihing 30 122
John 21 113
Roman 32 136
Rudradev 45 213
Rajat 33 138
Weiyan 8 173
Roman 18 182
Yintao 93 234
Erling 10 219
Chad 51 142
Liang 34 200
Ekansh 25 111
Erling 87 147
Zef 22 219
Kittipat 37 108
Tom 17 159
Aravind 4 109
Andriy 5 198
Sanjeet 68 239
Chad 7 220
Zainab 37 205
10 57 3
Fabien 0 111
Duc 49 198
Ekansh 98 121
Zef 30 122
Dmytro 50 124
Chirag 39 209
Doan 20 229
Clifton 50 129
Andrei 91 177
Erling 0 118
25 103 2
Sharad 11 217
Aravind 22 127
Thomas 91 212
John 68 199
Josh 92 160
Doan 43 205
Weiyan 1 125
Dhruv 47 227
John 15 154
Tom 25 141
Viswanath 87 177
Rajat 42 150
Lovro 83 116
Rudradev 19 167
Mehdi 90 213
Paul 10 235
Xiao 27 100
Sharad 89 226
Steaphan 69 228
David 17 111
Steaphan 16 200
Liang 30 206
Victor 61 125
Sanjeet 74 216
Weiyan 64 185
28 15 4
Oleksandr 34 111
Mehdi 62 194
Rudradev 52 123
Chad 9 215
Wenjie 49 197
Doan 86 132
Saransh 68 107
Clifton 34 212
Keegan 48 181
Ekansh 17 162
Purav 96 170
Atol 50 225
Dhruv 39 190
Zhen 47 108
Lovro 49 200
Nathan 39 168
Liang 39 224
Clifton 83 232
Paul 3 131
John 79 121
Ahmed 11 121
Viswanath 31 177
Dhruv 20 235
Song 53 184
Atol 92 195
John 72 123
Clifton 55 115
Rajat 13 214
16 21 5
Andrei 35 112
Andrei 66 130
Nima 42 117
Voja 96 150
Aleksandar 72 117
John 49 225
Roman 50 215
Aravind 28 143
Doan 65 136
Andrii 10 219
Vladislav 49 166
Keegan 66 140
Paul 29 158
Rudradev 2 174
David 47 197
Amol 4 104
24 119 3
Meihong 33 155
Lovro 46 175
Manohar 60 137
Nima 24 233
Erling 67 110
Viswanath 43 162
Andras 69 210
Yintao 59 116
Weitao 12 115
Weiyan 41 198
Erling 40 108
Weiyan 54 160
Yintao 88 211
Xiao 10 106
Chad 95 158
Weitao 28 124
Aleksandar 75 140
Wai 48 176
Anshuman 44 208
Anshuman 10 214
Bhuwan 32 231
Luiz 37 117
Josh 30 145
Lovro 33 175
19 109 3
Atol 21 171
Jan 56 128
Yintao 17 176
Ekansh 44 194
Jan 40 216
Ahmed 26 219
Victor 82 131
Amol 33 174
Doan 16 175
Zejia 9 214
Viswanath 68 139
Kittipat 93 124
Ajay 35 103
Anil 1 185
Paul 6 217
Zihing 34 196
Aravind 60 183
Rudradev 48 163
Wenjie 19 229
18 95 2
Liang 53 146
Wesley 12 197
Wenjie 86 238
Manohar 94 129
Anshuman 27 180
Chi 73 162
David 16 238
Purav 57 227
Wai 42 196
Chad 48 239
Zainab 46 175
Wai 98 114
Chi 45 209
Paul 17 135
Paul 10 171
Atol 23 162
Yifei 99 197
Wei 0 164
4 72 1
Anh 2 187
Erling 69 226
Purav 0 199
Zejia 29 163
7 52 1
John 61 186
Atol 62 231
Nathan 63 138
Lin 37 186
Daniel 37 171
Doan 99 226
Chad 37 196
6 62 3
Meihong 33 192
Duc 62 162
Wai 70 148
Fabien 19 120
Bhuwan 48 176
Vlad 30 225
22 55 1
John 36 138
Mehdi 74 238
Torbjorn 24 240
Weitao 38 180
Roman 37 116
Voja 18 147
Xiao 11 186
Zejia 34 179
Wai 52 230
Yifei 29 114
Dhruv 72 239
Anshuman 67 179
John 35 134
Sharad 28 149
Atol 6 201
Ekansh 4 174
Fabien 93 168
Vasily 61 172
Weiyan 88 127
Ekansh 45 146
Jan 60 182
Josh 30 115
24 80 3
Amol 52 169
David 35 118
Dmytro 37 222
Manohar 40 179
Roman 83 107
Tom 43 238
John 31 220
Tom 60 169
Paul 46 187
Steaphan 81 123
Andriy 26 103
Chad 99 101
Jan 31 129
Torbjorn 84 207
Slawek 28 159
Nathan 40 140
Daniel 61 129
Yintao 52 162
Ekansh 14 223
Sharad 53 232
Josh 51 174
Anil 86 206
Atol 0 218
Torbjorn 40 141
30 104 4
Slawek 65 198
Zhen 15 233
Dmytro 26 215
Yintao 93 225
Oleksandr 35 169
Viswanath 14 197
Rajat 8 219
Anil 72 202
Meihong 97 114
Doan 76 222
Fabien 78 179
Jan 28 131
Chirag 40 233
Tom 98 102
Zejia 47 130
Paul 82 119
Steaphan 41 210
Duc 10 225
Xiao 13 207
Manohar 97 107
Dhruv 17 100
Weiyan 44 214
Anshuman 70 124
Yifei 69 153
Fabien 45 186
Xiao 63 120
Purav 34 157
Bhuwan 39 231
Saransh 51 219
John 35 126
8 59 3
Anil 38 180
Song 7 187
David 65 159
Lin 45 121
Ranjeeth 39 183
Torbjorn 26 181
Clifton 57 158
Phil 3 183
25 98 1
Aravind 7 216
Ekansh 57 142
Zainab 95 117
Josh 83 236
Lin 86 185
Andrei 82 184
Victor 75 130
Doan 81 178
Liang 38 221
Ahmed 44 212
Chirag 62 101
Sarang 9 186
Meihong 76 167
Philip 27 105
John 53 226
Andrii 75 152
Vladislav 75 221
Doan 96 152
Andrei 40 180
Dhruv 73 231
Vladislav 66 195
Jordan 65 231
Slawek 59 124
Anil 5 202
Viswanath 82 136

basketball_game_output.txt

Case #1: Fabien Kittipat Liang Paul
Case #2: Purav Slawek Wai Weiyan
Case #3: Atol Bhuwan Bhuwan Lin Nima Vladislav Voja Voja Yingsheng Zainab
Case #4: Andrei Wesley
Case #5: Aravind Ekansh
Case #6: Andrei Doan Ekansh Erling Fabien Zef
Case #7: Aravind Mehdi Weiyan Xiao
Case #8: Atol Clifton Clifton Doan John John Purav Song
Case #9: Amol Andrei Andrii Aravind David John Nima Paul Rudradev Vladislav
Case #10: Aleksandar Andras Anshuman Erling Manohar Xiao
Case #11: Anil Aravind Jan Jan Victor Viswanath
Case #12: Anshuman Atol Paul Wai
Case #13: Erling Zejia
Case #14: Doan John
Case #15: Bhuwan Duc Fabien Meihong Vlad Wai
Case #16: Fabien Weiyan
Case #17: Andriy David Dmytro Jan John Slawek
Case #18: Anil Doan Duc Fabien Manohar Paul Rajat Yintao
Case #19: Anil Lin Phil Ranjeeth Song Torbjorn
Case #20: Chirag Viswanath

index.php

<?php
/**
 * Facebook Hacker Cup 2014 Qualification Round
 *
 * Basketball game
 *
 * @author Alfonsas Cirtautas
 */

// Read data
$raw = file('basketball_game_input.txt');
$cnt = reset($raw);
$rez = '';

// Play the game.
for ($t = 1, $i=1; $i<count($raw); $i++) {

    list($n, $m, $p) = explode(' ',$raw[$i]);

    $players = array_slice($raw, $i+1, $n);
    $s = game($n, $m, $p, $players);

    $rez.= "Case #{$t}: {$s}".PHP_EOL;

    $i+= $n;
    $t++;
}

// Save results
file_put_contents('basketball_game_output.txt', $rez);

// Where the magic happens ;)
function game($n, $m, $p, $players) {

    // Order and divide players to teams
    list($team1, $team2) = players2teams($players, $p);

    // Everybody plays ?
    if($n/$p !== 2) {
        // Play the game
        for ($t = 0; $t < $m; $t++) {
            $team1 = rotatePlayers($team1);
            $team2 = rotatePlayers($team2);
        }
    }

    // Who is playing
    $playing = playingNames(array_merge($team1, $team2));

    return $playing;
}

function players2teams($raw, $play) {
    $players = array();

    foreach ($raw as $i => $player) {
        $pl = explode(' ', $player);
        $player = array(
            'name'   => trim($pl[0]),
            'shots'  => (int) $pl[1],
            'height' => (int) $pl[2],
            'draft'  => 0,
            'time'   => 0,
            'team'   => 0,
            'play'   => false,
        );
        $players[$i] = $player;
    }

    // Sort players
    $sorter = function($a, $b) {
        if ($a['shots'] == $b['shots']) {
            return ($a['height'] > $b['height']) ? -1 : 1;
        }
        return ($a['shots'] > $b['shots']) ? -1 : 1;
    };
    usort($players, $sorter);

    $teams = array();

    // Divide to teams
    foreach ($players as $i => $player) {
        $team = $i & 1;
        $draft = $i + 1;
        $player['draft'] = $draft;
        $player['play'] = $draft/2 <= $play;
        $player['time'] = $player['play']?1:0;
        $teams[$team][] = $player;
    }

    return $teams;
}

function rotatePlayers($team) {
    // Find change
    $a = nextPlayerToSit($team);
    $b = nextPlayerToPlay($team);

    if($a != $b){
        $team[$a]['play'] = false;
        $team[$b]['play'] = true;
    }

    foreach($team as $p => $player) {
        if($pl = $player['play']) $team[$p]['time'] ++;
    }

    return $team;
}

function nextPlayerToSit($team) {
    $a = -1;
    foreach($team as $p => $player) {
        if($player['play']) {
            // Max time Max draft
            if($a < 0) $a = $p;
            if(($player['time'] >= $team[$a]['time']) && ($player['draft'] > $team[$a]['draft'])) $a = $p;
        }
    }
    return $a;
}

function nextPlayerToPlay($team) {

    $team = array_reverse($team, true);
    $a = -1;
    foreach($team as $p => $player) {
        if(!$player['play']) {
            // Min time Min draft
            if($a < 0) $a = $p;
            if(($player['time'] <= $team[$a]['time']) && ($player['draft'] < $team[$a]['draft'])) $a = $p;
        }
    }

    return $a;
}

function playingNames($players) {
    $playing = array();
    foreach($players as $player) {
        if ($player['play']) $playing[] = $player['name'];
    }
    sort($playing);

    return implode(' ',$playing);
}