// codesnip-guard: SimulatedAnnealing
#[cfg_attr(any(),rustfmt::skip)]pub use self::simulated_annealing::SimulatedAnnealing;#[cfg_attr(any(),rustfmt::skip)]mod simulated_annealing{use super::Xorshift;#[derive(Debug)]pub struct SimulatedAnnealing{pub iter_count:usize,pub now:std::time::Instant,pub time:f64,pub temperture:f64,pub log_table:Vec<f64>,pub rand:Xorshift,pub is_maximize:bool,pub start_temp:f64,pub end_temp:f64,pub time_limit:f64,pub update_interval:usize}impl Default for SimulatedAnnealing{fn default()->Self{let now=std::time::Instant::now();let log_table=(0..Self::LOG_TABLE_SIZE).map(|i|((i*2+1)as f64/(Self::LOG_TABLE_SIZE*2)as f64).ln()).collect();Self{iter_count:0,now,time:0.,temperture:3e3,log_table,rand:Xorshift::new_with_seed(Self::SEED),is_maximize:true,start_temp:3e3,end_temp:1e-8,time_limit:1.99,update_interval:0xff}}}impl SimulatedAnnealing{pub const LOG_TABLE_SIZE:usize=0x10000;pub const SEED:u64=0xbeef_cafe;pub fn new()->Self{Default::default()}pub fn minimize(mut self)->Self{self.is_maximize=false;self}pub fn set_start_temp(mut self,start_temp:f64)->Self{assert_eq!(self.iter_count,0);self.start_temp=start_temp;self.temperture=start_temp;self}pub fn set_end_temp(mut self,end_temp:f64)->Self{self.end_temp=end_temp;self}pub fn set_time_limit(mut self,time_limit:f64)->Self{self.time_limit=time_limit;self}pub fn set_update_interval(mut self,update_interval:usize)->Self{assert!(update_interval>0);self.update_interval=update_interval;self}pub fn is_accepted(&mut self,current_score:f64,next_score:f64)->bool{let diff=if self.is_maximize{next_score-current_score}else{current_score-next_score};diff>=0.||diff>self.log_table[self.rand.rand(Self::LOG_TABLE_SIZE as u64)as usize]*self.temperture}pub fn accepted_score(&mut self,current_score:f64)->f64{let bound=self.log_table[self.rand.rand(Self::LOG_TABLE_SIZE as u64)as usize]*self.temperture;if self.is_maximize{current_score+bound}else{current_score-bound}}pub fn is_end(&mut self)->bool{self.iter_count+=1;if self.iter_count.is_multiple_of(self.update_interval){self.time=self.now.elapsed().as_secs_f64();let temp_ratio=(self.end_temp-self.start_temp)/self.time_limit;self.temperture=self.start_temp+temp_ratio*self.time;self.time>=self.time_limit}else{false}}}}
// codesnip-guard: Xorshift
#[cfg_attr(any(),rustfmt::skip)]pub use self::xorshift::Xorshift;#[cfg_attr(any(),rustfmt::skip)]mod xorshift{use std::{collections::hash_map::RandomState,hash::{BuildHasher,Hasher},iter::repeat_with};#[derive(Clone,Debug)]pub struct Xorshift{y:u64}impl Xorshift{pub fn new_with_seed(seed:u64)->Self{Xorshift{y:seed}}pub fn new()->Self{Xorshift::new_with_seed(RandomState::new().build_hasher().finish())}pub fn rand64(&mut self)->u64{self.y^=self.y<<5;self.y^=self.y>>17;self.y^=self.y<<11;self.y}pub fn rand(&mut self,k:u64)->u64{self.rand64()%k}pub fn rands(&mut self,k:u64,n:usize)->Vec<u64>{repeat_with(| |self.rand(k)).take(n).collect()}pub fn randf(&mut self)->f64{const UPPER_MASK:u64=0x3FF0_0000_0000_0000;const LOWER_MASK:u64=0x000F_FFFF_FFFF_FFFF;let x=self.rand64();let tmp=UPPER_MASK|(x&LOWER_MASK);let result:f64=f64::from_bits(tmp);f64::from_bits(f64::to_bits(result-1.0)^(x>>63))}pub fn gen_bool(&mut self,p:f64)->bool{self.randf()<p}pub fn shuffle<T>(&mut self,slice:&mut[T]){let mut n=slice.len();while n>1{let i=self.rand(n as _)as usize;n-=1;slice.swap(i,n);}}}impl Default for Xorshift{fn default()->Self{Xorshift::new_with_seed(0x2b99_2ddf_a232_49d6)}}}