simu.rs (20861B)
1 mod elo; 2 mod rand; 3 4 use elo::Elo; 5 use rand::{Lehmer, Rand, RandOutput, YesNo}; 6 7 pub type Error = Box<dyn std::error::Error>; 8 pub type Result<T> = std::result::Result<T, Error>; 9 10 trait Getter<T> { 11 fn idxmut(&mut self, idx: usize) -> &mut T; 12 } 13 14 #[cfg(not(feature = "use_unsafe"))] 15 impl<T> Getter<T> for Vec<T> { 16 fn idxmut(&mut self, idx: usize) -> &mut T { 17 &mut self[idx] 18 } 19 } 20 21 #[cfg(feature = "use_unsafe")] 22 impl<T> Getter<T> for Vec<T> { 23 fn idxmut(&mut self, idx: usize) -> &mut T { 24 unsafe { &mut *self.as_mut_ptr().add(idx) } 25 } 26 } 27 28 trait CloseEnough<T> { 29 fn lossy_from(other: T) -> Self; 30 } 31 32 impl CloseEnough<f64> for u32 { 33 #[allow( 34 clippy::cast_precision_loss, 35 clippy::cast_possible_truncation, 36 clippy::cast_sign_loss 37 )] 38 fn lossy_from(other: f64) -> Self { 39 other as Self 40 } 41 } 42 43 trait FirstLast { 44 type Item; 45 46 fn first_last<F: FnMut(Self::Item) -> bool>(self, f: F) -> Option<(usize, usize)>; 47 } 48 49 impl<T, I: std::iter::IntoIterator<Item = T>> FirstLast for I { 50 type Item = T; 51 52 fn first_last<F: FnMut(Self::Item) -> bool>(self, mut f: F) -> Option<(usize, usize)> { 53 self.into_iter().enumerate().fold(None, |acc, (i, e)| { 54 (f(e)).then_some((acc.map_or(i, |(a, _)| a), i)).or(acc) 55 }) 56 } 57 } 58 59 #[derive(Debug)] 60 struct Options { 61 pub threads: usize, 62 pub iterations: usize, 63 pub home_advantage: f64, 64 pub overtime_prob: f64, 65 pub elo_k: f64, 66 pub regression: f64, 67 } 68 69 impl Default for Options { 70 fn default() -> Self { 71 Self { 72 threads: 1, 73 iterations: 100_000, 74 home_advantage: 58., 75 overtime_prob: 0.23, 76 elo_k: 32., 77 regression: 0.005, 78 } 79 } 80 } 81 82 #[derive(Debug)] 83 struct PlayedGame { 84 pub home_id: usize, 85 pub away_id: usize, 86 pub home_score: usize, 87 pub away_score: usize, 88 pub overtime: bool, 89 } 90 91 impl std::str::FromStr for PlayedGame { 92 type Err = Error; 93 94 fn from_str(s: &str) -> Result<Self> { 95 let mut parts = s.split_ascii_whitespace(); 96 let home_id = parts.next().ok_or("Missing field")?.parse()?; 97 let away_id = parts.next().ok_or("Missing fields")?.parse()?; 98 let home_score = parts.next().ok_or("Missing fields")?.parse()?; 99 let away_score = parts.next().ok_or("Missing fields")?.parse()?; 100 let overtime = parts.next().is_some_and(|s| s == "OT" || s == "SO"); 101 102 Ok(Self { 103 home_id, 104 away_id, 105 home_score, 106 away_score, 107 overtime, 108 }) 109 } 110 } 111 112 #[derive(Clone, Copy, Debug)] 113 struct Game { 114 pub home_id: usize, 115 pub away_id: usize, 116 } 117 118 #[derive(Clone, Copy, Debug)] 119 struct UpcomingGame<R: Rand> { 120 pub home_id: usize, 121 pub away_id: usize, 122 pub expected: R::Output, 123 _phantom: std::marker::PhantomData<R>, 124 } 125 126 impl Game { 127 pub fn into_upcoming<R>( 128 self, 129 map: &[usize], 130 teams: &mut [Team], 131 opts: &Options, 132 ) -> Result<UpcomingGame<R>> 133 where 134 R: Rand, 135 R::Output: Into<f64> + CloseEnough<f64>, 136 { 137 if let Some(&home_id) = map.get(self.home_id) 138 && let Some(&away_id) = map.get(self.away_id) 139 { 140 let [home, away] = teams.get_disjoint_mut([home_id, away_id])?; 141 let ug = UpcomingGame { 142 home_id, 143 away_id, 144 expected: R::Output::lossy_from( 145 home.simulated(away, opts.home_advantage, opts.elo_k, opts.regression) 146 * R::MAX.into(), 147 ), 148 _phantom: std::marker::PhantomData, 149 }; 150 Ok(ug) 151 } else { 152 Err(Error::from("Invalid team id")) 153 } 154 } 155 } 156 157 impl std::str::FromStr for Game { 158 type Err = Error; 159 160 fn from_str(s: &str) -> Result<Self> { 161 let mut parts = s.split_ascii_whitespace(); 162 let home_id = parts.next().ok_or("Missing fields")?.parse()?; 163 let away_id = parts.next().ok_or("Missing fields")?.parse()?; 164 165 Ok(Self { home_id, away_id }) 166 } 167 } 168 169 #[derive(Default, Clone, Debug)] 170 struct Team { 171 pub name: String, 172 pub id: usize, 173 pub points: u64, 174 pub games: u64, 175 pub wins: u64, 176 pub pointssum: u64, 177 pub gamessum: u64, 178 pub winssum: u64, 179 pub elo: Elo, 180 pub elo0: Elo, 181 pub poscounts: Vec<(usize, bool)>, 182 } 183 184 #[derive(Clone, Copy, Debug)] 185 enum NormalizedProb { 186 Zero, 187 Epsilon, 188 Percentage(f64), 189 Always, 190 } 191 192 impl std::fmt::Display for NormalizedProb { 193 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { 194 use NormalizedProb as N; 195 match self { 196 N::Zero => write!(f, "-"), 197 N::Epsilon => write!(f, "0"), 198 N::Percentage(p) => write!(f, "{p:e}"), 199 N::Always => write!(f, "+"), 200 } 201 } 202 } 203 204 #[allow(dead_code)] 205 struct NormalizedTeam { 206 pub name: String, 207 pub points: u64, 208 pub games: u64, 209 pub wins: u64, 210 pub final_points: f64, 211 pub final_games: f64, 212 pub final_wins: f64, 213 pub elo: Elo, 214 pub poscounts: Vec<NormalizedProb>, 215 } 216 217 impl std::cmp::PartialEq for Team { 218 fn eq(&self, other: &Self) -> bool { 219 self.points * other.games == self.games * other.points 220 } 221 } 222 impl std::cmp::Eq for Team {} 223 224 impl std::cmp::Ord for Team { 225 fn cmp(&self, other: &Self) -> std::cmp::Ordering { 226 (other.points * self.games) 227 .cmp(&(self.points * other.games)) 228 .then_with(|| (other.wins * self.games).cmp(&(self.wins * other.games))) 229 } 230 } 231 232 impl std::cmp::PartialOrd for Team { 233 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> { 234 Some(self.cmp(other)) 235 } 236 } 237 238 impl Team { 239 pub fn new(name: String, id: usize, n_teams: usize) -> Self { 240 Self { 241 name, 242 id, 243 poscounts: vec![(0, false); n_teams], 244 ..Default::default() 245 } 246 } 247 248 pub fn simulated(&mut self, other: &mut Self, adv: f64, elo_k: f64, regress: f64) -> f64 { 249 self.elo.simulated(&mut other.elo, adv, elo_k, regress) 250 } 251 252 pub fn game(&mut self, gf: usize, ga: usize, ot: bool) -> u64 { 253 self.games += 1; 254 let points = match (gf > ga, ot) { 255 (true, false) => { 256 self.wins += 1; 257 3 258 } 259 (true, true) => 2, 260 (false, true) => 1, 261 (false, false) => 0, 262 }; 263 self.points += points; 264 points 265 } 266 267 #[allow(clippy::cast_precision_loss)] 268 pub fn normalize(self, iterations: usize) -> NormalizedTeam { 269 let Team { 270 name, 271 points, 272 games, 273 wins, 274 pointssum, 275 gamessum, 276 winssum, 277 elo0: elo, 278 poscounts, 279 .. 280 } = self; 281 NormalizedTeam { 282 name, 283 points, 284 games, 285 wins, 286 elo, 287 final_points: pointssum as f64 / iterations as f64, 288 final_games: gamessum as f64 / iterations as f64, 289 final_wins: winssum as f64 / iterations as f64, 290 poscounts: poscounts 291 .into_iter() 292 .map(|count| match count { 293 (0, false) => NormalizedProb::Zero, 294 (0, true) => NormalizedProb::Epsilon, 295 (count, _) if count == iterations => NormalizedProb::Always, 296 (count, _) => { 297 NormalizedProb::Percentage(100. * (count - 1) as f64 / iterations as f64) 298 } 299 }) 300 .collect(), 301 } 302 } 303 304 fn add_result(&mut self, rhs: &SimulationResult) { 305 for ((w, _), &r) in self.poscounts.iter_mut().zip(&rhs.position_counts) { 306 *w += r; 307 } 308 self.gamessum += rhs.games; 309 self.pointssum += rhs.points; 310 } 311 312 fn add_winlose_result(&mut self, rhs: &WinLoseSimulationResult) { 313 for ((_, p), &r) in self.poscounts.iter_mut().zip(&rhs.positions) { 314 *p |= r; 315 } 316 } 317 } 318 319 impl std::fmt::Display for NormalizedTeam { 320 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { 321 let NormalizedTeam { 322 name, 323 games, 324 points, 325 final_games, 326 final_points, 327 elo, 328 poscounts, 329 .. 330 } = self; 331 write!( 332 f, 333 "{name} {games} {points} {final_games:.0} {final_points:.1} {elo:.0}" 334 )?; 335 for count in poscounts { 336 write!(f, " {count}")?; 337 } 338 Ok(()) 339 } 340 } 341 342 trait IteratorArgExt { 343 fn get_arg<E, T>(&mut self) -> Result<T> 344 where 345 E: std::error::Error + 'static, 346 T: std::str::FromStr<Err = E>; 347 } 348 349 impl<S: AsRef<str>, I: Iterator<Item = S>> IteratorArgExt for I { 350 fn get_arg<E, T>(&mut self) -> Result<T> 351 where 352 E: std::error::Error + 'static, 353 T: std::str::FromStr<Err = E>, 354 { 355 Ok(self.next().ok_or("Missing argument")?.as_ref().parse()?) 356 } 357 } 358 359 impl Options { 360 fn from_args<T: IntoIterator<Item = String>>(iter: T) -> Result<Self> { 361 let mut iter = iter.into_iter(); 362 let mut rv = Self::default(); 363 while let Some(flags) = iter.next() { 364 let mut chars = flags.chars(); 365 chars 366 .next() 367 .filter(|c| *c == '-') 368 .ok_or("Invalid argument")?; 369 for c in chars { 370 match c { 371 'i' => rv.iterations = iter.get_arg()?, 372 't' => rv.threads = iter.get_arg()?, 373 'a' => rv.home_advantage = iter.get_arg()?, 374 'o' => rv.overtime_prob = iter.get_arg()?, 375 'k' => rv.elo_k = iter.get_arg()?, 376 'r' => rv.regression = iter.get_arg()?, 377 _ => Err(format!("Invalid option {c}"))?, 378 } 379 } 380 } 381 Ok(rv) 382 } 383 } 384 385 #[derive(Clone, Debug, Copy)] 386 struct SimulationTeam<R> 387 where 388 R: Rand, 389 R::Output: Ord + Copy + std::fmt::Debug, 390 { 391 id: usize, 392 points: u64, 393 games: u64, 394 wins: u64, 395 random: R::Output, 396 } 397 398 impl<R: Rand> std::cmp::PartialEq for SimulationTeam<R> { 399 fn eq(&self, other: &Self) -> bool { 400 self.points * other.games == other.points * self.games 401 && self.wins * other.games == other.wins * self.games 402 } 403 } 404 405 impl<R: Rand> std::cmp::Eq for SimulationTeam<R> {} 406 407 impl<R: Rand> std::cmp::Ord for SimulationTeam<R> { 408 fn cmp(&self, other: &Self) -> std::cmp::Ordering { 409 (other.points * self.games) 410 .cmp(&(self.points * other.games)) 411 .then_with(|| { 412 (other.wins * self.games) 413 .cmp(&(self.wins * other.games)) 414 .then_with(|| self.random.cmp(&other.random)) 415 }) 416 } 417 } 418 419 impl<R: Rand> std::cmp::PartialOrd for SimulationTeam<R> { 420 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> { 421 Some(self.cmp(other)) 422 } 423 } 424 425 impl<R: Rand> SimulationTeam<R> { 426 pub fn copy_with(&self, rand: &mut R) -> (Self, Self) { 427 let r = rand.rand(); 428 ( 429 Self { random: r, ..*self }, 430 Self { 431 random: R::MAX - r, 432 ..*self 433 }, 434 ) 435 } 436 437 pub fn game(&mut self, win: bool, ot: bool) { 438 self.games += 1; 439 self.points += (3 * u64::from(win)) ^ u64::from(ot); 440 } 441 } 442 443 impl<R: Rand> From<(usize, &Team)> for SimulationTeam<R> { 444 fn from((id, team): (usize, &Team)) -> Self { 445 Self { 446 id, 447 points: team.points, 448 games: team.games, 449 wins: team.wins, 450 random: Default::default(), 451 } 452 } 453 } 454 455 #[derive(Clone)] 456 struct WinLoseSimulationResult { 457 positions: Vec<bool>, 458 } 459 460 #[derive(Clone)] 461 struct SimulationResult { 462 position_counts: Vec<usize>, 463 games: u64, 464 points: u64, 465 wins: u64, 466 } 467 468 impl SimulationResult { 469 fn new(n_teams: usize) -> Self { 470 Self { 471 position_counts: vec![0; n_teams], 472 games: 0, 473 points: 0, 474 wins: 0, 475 } 476 } 477 } 478 479 fn simulate<T, R>( 480 teams: &[Team], 481 upcoming_games: &[UpcomingGame<R>], 482 rand: &mut R, 483 opts: &Options, 484 ) -> (usize, Vec<SimulationResult>) 485 where 486 T: RandOutput + CloseEnough<f64> + Into<f64>, 487 R: YesNo<T> + Rand<Output = T>, 488 { 489 let simulationteams0: Vec<SimulationTeam<R>> = 490 teams.iter().enumerate().map(From::from).collect(); 491 let mut result: Vec<_> = (0..teams.len()) 492 .map(|_| SimulationResult::new(teams.len())) 493 .collect(); 494 let otprob = R::Output::lossy_from(opts.overtime_prob * R::MAX.into()); 495 let mut simulationteams = simulationteams0.clone(); 496 let mut antisimulationteams = simulationteams0.clone(); 497 for _ in 0..opts.iterations / 2 { 498 for ((s, antis), s0) in simulationteams 499 .iter_mut() 500 .zip(antisimulationteams.iter_mut()) 501 .zip(simulationteams0.iter()) 502 { 503 (*s, *antis) = s0.copy_with(rand); 504 } 505 506 for game in upcoming_games { 507 let (res, antires) = rand.yesno(game.expected); 508 let (ot, antiot) = rand.yesno(otprob); 509 510 simulationteams.idxmut(game.home_id).game(res, ot); 511 simulationteams.idxmut(game.away_id).game(!res, ot); 512 antisimulationteams 513 .idxmut(game.home_id) 514 .game(antires, antiot); 515 antisimulationteams 516 .idxmut(game.away_id) 517 .game(!antires, antiot); 518 } 519 520 simulationteams.sort_unstable(); 521 antisimulationteams.sort_unstable(); 522 523 for (i, t) in simulationteams 524 .iter() 525 .enumerate() 526 .chain(antisimulationteams.iter().enumerate()) 527 { 528 let res = result.idxmut(t.id); 529 res.position_counts[i] += 1; 530 res.games += t.games; 531 res.points += t.points; 532 res.wins += t.wins; 533 } 534 } 535 536 (opts.iterations & (usize::MAX - 1), result) 537 } 538 539 #[derive(Debug, Clone, Copy)] 540 enum WinLose { 541 WinAll(usize), 542 LoseAll(usize), 543 } 544 545 enum Winner { 546 Undefined, 547 Home, 548 Away, 549 } 550 551 impl WinLose { 552 pub fn check<T>(&self, game: &UpcomingGame<impl Rand<Output = T>>) -> Winner { 553 use WinLose as WL; 554 use Winner as W; 555 match self { 556 WL::WinAll(id) if &game.home_id == id => W::Home, 557 WL::WinAll(id) if &game.away_id == id => W::Away, 558 WL::LoseAll(id) if &game.home_id == id => W::Away, 559 WL::LoseAll(id) if &game.away_id == id => W::Home, 560 _ => W::Undefined, 561 } 562 } 563 } 564 565 fn simulate_winall<T, R>( 566 teams: &[Team], 567 upcoming_games: &[UpcomingGame<R>], 568 rand: &mut R, 569 opts: &Options, 570 winlose: WinLose, 571 ) -> Vec<SimulationResult> 572 where 573 T: RandOutput + CloseEnough<f64> + Into<f64>, 574 R: YesNo<T> + Rand<Output = T>, 575 { 576 let mut teams = Vec::from(teams); 577 let upcoming: Vec<_> = upcoming_games 578 .iter() 579 .filter(|game| { 580 !match winlose.check(game) { 581 Winner::Home => Some((game.home_id, game.away_id)), 582 Winner::Away => Some((game.away_id, game.home_id)), 583 Winner::Undefined => None, 584 } 585 .is_some_and(|(winner, loser)| { 586 teams[winner].game(1, 0, false); 587 teams[loser].game(0, 1, false); 588 true 589 }) 590 }) 591 .copied() 592 .collect(); 593 simulate(&teams, &upcoming, rand, opts).1 594 } 595 596 fn simulate_winloseall<T, R>( 597 teams: &[Team], 598 upcoming_games: &[UpcomingGame<R>], 599 rand: &mut R, 600 opts: &Options, 601 ) -> Vec<WinLoseSimulationResult> 602 where 603 T: RandOutput + CloseEnough<f64> + Into<f64>, 604 R: YesNo<T> + Rand<Output = T>, 605 { 606 let opts = Options { 607 iterations: opts.iterations / teams.len() / 2, 608 ..*opts 609 }; 610 (0..teams.len()) 611 .map(|idx| { 612 let (whigh, wlow) = 613 simulate_winall(teams, upcoming_games, rand, &opts, WinLose::WinAll(idx))[idx] 614 .position_counts 615 .iter() 616 .first_last(|&p| p != 0) 617 .unwrap(); 618 let (lhigh, llow) = 619 simulate_winall(teams, upcoming_games, rand, &opts, WinLose::LoseAll(idx))[idx] 620 .position_counts 621 .iter() 622 .first_last(|&p| p != 0) 623 .unwrap(); 624 WinLoseSimulationResult { 625 positions: (0..teams.len()) 626 .map(|p| p >= whigh.min(lhigh) && p <= wlow.max(llow)) 627 .collect(), 628 } 629 }) 630 .collect() 631 } 632 633 fn simulate_parallel( 634 teams: &mut [Team], 635 games: &[UpcomingGame<Lehmer>], 636 rnd: &mut Lehmer, 637 opts: &Options, 638 ) -> usize { 639 let opts = Options { 640 iterations: opts.iterations / opts.threads, 641 ..*opts 642 }; 643 let results = std::thread::scope(|s| { 644 (0..opts.threads) 645 .map(|_| { 646 let teams = &teams; 647 let games = &games; 648 let opts = &opts; 649 let mut rnd = Lehmer::new_with(rnd); 650 651 s.spawn(move || { 652 ( 653 simulate(teams, games, &mut rnd, opts), 654 simulate_winloseall(teams, games, &mut rnd, opts), 655 ) 656 }) 657 }) 658 .collect::<Vec<_>>() 659 .into_iter() 660 .map(|t| t.join().expect("Thread panicked")) 661 .collect::<Vec<_>>() 662 }); 663 let mut iterations = 0; 664 for ((iters, simulated), simulatedwl) in results { 665 iterations += iters; 666 for (team, simu) in teams.iter_mut().zip(&simulated) { 667 team.add_result(simu); 668 } 669 for (team, simu) in teams.iter_mut().zip(&simulatedwl) { 670 team.add_winlose_result(simu); 671 } 672 } 673 iterations 674 } 675 676 fn main() -> Result<()> { 677 let opts = Options::from_args(std::env::args().skip(1))?; 678 let mut lines = std::io::stdin() 679 .lines() 680 .filter(|r| !r.as_ref().is_ok_and(|s| s.trim().is_empty())); 681 682 let n_teams: usize = lines.next().ok_or("Missing team count")??.trim().parse()?; 683 let mut teams = (0..n_teams) 684 .map(|id| { 685 Ok(Team::new( 686 lines.next().ok_or("Missing teams")??.trim().to_owned(), 687 id, 688 n_teams, 689 )) 690 }) 691 .collect::<Result<Vec<_>>>()?; 692 let n_games: usize = lines.next().ok_or("Missing game count")??.trim().parse()?; 693 for game in (0..n_games).map(|_| lines.next().ok_or("Missing game")??.parse::<PlayedGame>()) { 694 let PlayedGame { 695 home_id, 696 away_id, 697 home_score, 698 away_score, 699 overtime, 700 } = game?; 701 let [home, away] = teams.get_disjoint_mut([home_id, away_id])?; 702 703 away.game(away_score, home_score, overtime); 704 #[allow(clippy::cast_precision_loss)] 705 let actual = home.game(home_score, away_score, overtime) as f64 / 3.; 706 707 home.elo 708 .update(&mut away.elo, opts.elo_k, actual, opts.home_advantage); 709 } 710 711 teams.sort(); 712 let mut team_map = vec![0; n_teams]; 713 for (i, team) in teams.iter_mut().enumerate() { 714 team_map[team.id] = i; 715 team.elo0 = team.elo; 716 } 717 718 let mut rnd = Lehmer::default(); 719 720 let n_games: usize = lines.next().ok_or("Missing game count")??.trim().parse()?; 721 let games: Vec<_> = (0..n_games) 722 .map(|_| { 723 lines 724 .next() 725 .ok_or("Missing games")?? 726 .parse::<Game>()? 727 .into_upcoming::<Lehmer>(&team_map, &mut teams, &opts) 728 }) 729 .collect::<Result<_>>()?; 730 731 let iterations = if opts.threads == 1 { 732 let (iterations, simulated) = simulate(&teams, &games, &mut rnd, &opts); 733 let simulatedwl = simulate_winloseall(&teams, &games, &mut rnd, &opts); 734 for (team, simu) in teams.iter_mut().zip(&simulated) { 735 team.add_result(simu); 736 } 737 for (team, simu) in teams.iter_mut().zip(&simulatedwl) { 738 team.add_winlose_result(simu); 739 } 740 iterations 741 } else { 742 simulate_parallel(&mut teams, &games, &mut rnd, &opts) 743 }; 744 745 teams.sort_by(|a, b| { 746 (b.pointssum * a.gamessum) 747 .cmp(&(a.pointssum * b.gamessum)) 748 .then_with(|| (b.winssum * a.gamessum).cmp(&(a.winssum * a.gamessum))) 749 }); 750 751 for team in teams.into_iter().map(|team| team.normalize(iterations)) { 752 println!("{team}"); 753 } 754 755 Ok(()) 756 }