use db ::{ MemoryLayoutDB , SqliteLayoutDB , LayoutDB , SavedLayout } ;
use city ::{ City , House , HouseLayout , get_price } ;
use itertools ::Itertools ;
use rand ::{ thread_rng , Rng , SeedableRng } ;
use rand ::rngs ::StdRng ;
use rayon ::prelude ::* ;
mod city ;
mod db ;
mod combine ;
mod subcity ;
mod optimization ;
mod population ;
fn main ( ) {
let mut sqlite_db = SqliteLayoutDB ::from_file ( "layouts.sqlite" , false ) . expect ( "Failed to load the DB" ) ;
eprintln ! ( "Loaded the DB, {} stored layouts" , sqlite_db . layouts ( ) . len ( ) ) ;
let city = City ::read_from_file ( "01.in" , city ::INPUT_CITY_WIDTH , city ::INPUT_CITY_HEIGHT ) ;
eprintln ! ( "Loaded the city file, {} houses" , city . get_house_count ( ) ) ;
let best_layout : SavedLayout = sqlite_db . layouts ( ) . iter ( )
. sorted_by ( | x , y | get_price ( & city , x . houses ( ) ) . cmp ( & get_price ( & city , y . houses ( ) ) ) )
. map ( | layout | ( * layout ) . clone ( ) )
. next ( ) . expect ( "No best layout found" ) ;
eprintln ! ( "Found best layout, ID {}, price {}" , best_layout . id ( ) , get_price ( & city , best_layout . houses ( ) ) ) ;
//let x_range = 5533..=12000;
//let y_range = 4750..=12500;
//let x_range = 9500..=14100;
//let y_range = 10300..=14400;
//let x_range = 14900..=16200;
//let y_range = 7720..=10400;
//let x_range = 9982..=16383;
//let y_range = 0..=2720;
//let x_range = 7720..=12000;
//let y_range = 5608..=11000;
//let x_range = 3542..=8423;
//let y_range = 4832..=8423;
//let x_range = 1200..=9200;
//let y_range = 9000..=16383;
//let x_range = 9200..=16383;
//let y_range = 9200..=16383;
//let x_range = 9201..=16383;
//let y_range = 0..=7500;
//let x_range = 11100..=13333;
//let y_range = 14700..=16383;
//let x_range = 0..=7500;
//let y_range = 0..=7500;
let x_range = 0 . . = 7500 ;
let y_range = 9500 . . = 16383 ;
//let x_range = 9500..=16383;
//let y_range = 0..=7500;
eprintln ! ( "X {}-{}, Y {}-{}" , x_range . start ( ) , x_range . end ( ) , y_range . start ( ) , y_range . end ( ) ) ;
let static_houses : Vec < House > = best_layout . houses ( ) . iter ( )
. filter ( | house | ! ( x_range . contains ( & house . x ) & & y_range . contains ( & house . y ) ) )
. map ( | & house | house )
. collect ( ) ;
let removed_houses : Vec < House > = best_layout . houses ( ) . iter ( )
. filter ( | house | x_range . contains ( & house . x ) & & y_range . contains ( & house . y ) )
. map ( | & house | house )
. collect ( ) ;
let removed_price : u32 = removed_houses . iter ( ) . map ( | x | city . get_price ( * x ) as u32 ) . sum ( ) ;
eprintln ! ( "Price of all removed houses: {}" , removed_price ) ;
let subcity = subcity ::build_subcity ( & city , & static_houses ) ;
eprintln ! ( "Built subcity, width {}, height {}, {} houses, offset ({},{})" ,
subcity . city ( ) . width ( ) ,
subcity . city ( ) . height ( ) ,
subcity . city ( ) . get_house_count ( ) ,
subcity . x_offset ( ) ,
subcity . y_offset ( )
) ;
//let mut subcity_db = MemoryLayoutDB::new();
let filename = format ! ( "X{}_{}Y{}_{}ID{}.sqlite" , x_range . start ( ) , x_range . end ( ) , y_range . start ( ) , y_range . end ( ) , best_layout . id ( ) ) ;
let mut subcity_db = SqliteLayoutDB ::from_file ( & filename , true ) . unwrap ( ) ;
// The following part merges best subcity layouts back into the global layout and
// inserting them into the database
// Setting this value allows attempts at improving suboptimal subcities after merging them back.
// A subcity may result in a better score than original even if the subcity is worse than the
// original if global improvements improve the cost.
//const SUBOPTIMAL_SUBCITY_COST_MARGIN: u32 = 5000;
//const CHECKED_CITY_LIMIT: usize = 50;
//for layout in subcity_db.layouts().iter()
// .filter(|x| get_price(subcity.city(), x.houses()) < removed_price + SUBOPTIMAL_SUBCITY_COST_MARGIN)
// .sorted_by(|x, y| get_price(subcity.city(), x.houses()).cmp(&get_price(subcity.city(), y.houses())))
// .take(CHECKED_CITY_LIMIT) {
// let price = get_price(subcity.city(), layout.houses());
// let mut full_houses = subcity.to_full_houses(layout.houses());
// assert!(city::is_valid(&city, &full_houses).is_some());
// let mut house_layout = HouseLayout::new(&city);
// for house in &full_houses {
// house_layout.add_house(*house);
// }
// let seed: u64 = thread_rng().gen();
// let mut rng = StdRng::seed_from_u64(seed);
// optimization::iterate_improvements(&mut house_layout, &mut rng, true, false);
// eprintln!("Improvements finished");
// assert!(house_layout.is_valid());
// let improved_price = city::get_price(&city, house_layout.houses());
// if improved_price < city::get_price(&city, &full_houses) {
// eprintln!("Found improvement, new price {}, updating houses", improved_price);
// full_houses = house_layout.houses().clone();
// }
// assert!(city::is_valid(&city, &full_houses).is_some());
// println!("Layout {}, price {}, full price {}", layout.id(), price, city::get_price(&city, &full_houses));
// if improved_price < city::get_price(&city, best_layout.houses()) {
// eprintln!("Found a new best layout for the full city");
// println!("Found a new best layout for the full city");
// println!("Layout {}, price {}, full price {}", layout.id(), price, city::get_price(&city, &full_houses));
// }
// //eprintln!("NOT inserting into the DB");
// // Be careful with duplicates here
// sqlite_db.add_layout(&full_houses, true);
// eprintln!("Inserted into the global DB");
// println!("Inserted into the global DB");
// //}
//}
//return;
// Architecture:
// Build `FULL_RANDOM_LAYOUTS` random layouts
// loop {
// Try combining `CUT_COMBINE_TOP_LAYOUTS` top layouts using vertical/horizontal cuts
// Generate `WEIGHTED_RANDOM_LAYOUTS` layouts weighted by scores from existing layouts
// }
const FULL_RANDOM_LAYOUTS : usize = 200 ;
const DB_CHOICE_PROBABILITY : f64 = 0.95 ;
const WEIGHTED_RANDOM_LAYOUTS : usize = 100 ;
const CUT_COMBINE_TOP_LAYOUTS : usize = 500 ;
const IGNORED_WEIGHT_RATIO : f64 = 0.5 ;
const THREAD_COUNT : usize = 12 ;
rayon ::ThreadPoolBuilder ::new ( ) . num_threads ( THREAD_COUNT ) . build_global ( ) ;
if subcity_db . layouts ( ) . len ( ) = = 0 {
let mut full_random_layouts = Vec ::new ( ) ;
full_random_layouts . par_extend ( ( 0 . . FULL_RANDOM_LAYOUTS ) . into_par_iter ( ) . map ( | i | {
let seed : u64 = thread_rng ( ) . gen ( ) ;
let mut rng = StdRng ::seed_from_u64 ( seed ) ;
let mut layout = HouseLayout ::new ( subcity . city ( ) ) ;
//eprintln!("Starting random population {}", i);
population ::populate_random ( & mut layout , & mut rng ) ;
//eprintln!("Finished random init {}, price: {}, houses: {}", i, layout.price(), layout.houses().len());
optimization ::iterate_improvements ( & mut layout , & mut rng , false , false ) ;
//eprintln!("Finished iterated improvements {}, price: {}, houses: {}", i, layout.price(), layout.houses().len());
layout . houses ( ) . clone ( )
} ) ) ;
for houses in & full_random_layouts {
subcity_db . add_layout ( houses , true ) . expect ( "Failed to add new layout" ) ;
}
eprintln ! ( "Finished initial full random population" ) ;
} else {
eprintln ! ( "Skipping initial full random population because DB is non-empty [{} layouts]" , subcity_db . layouts ( ) . len ( ) ) ;
}
fn print_status < TDB : LayoutDB > ( db : & TDB , subcity : & City ) {
let best_price : u32 = db . layouts ( ) . iter ( ) . map ( | layout | layout . houses ( ) . iter ( ) . map ( | h | subcity . get_price ( * h ) as u32 ) . sum ( ) ) . min ( ) . unwrap ( ) ;
let worst_price : u32 = db . layouts ( ) . iter ( ) . map ( | layout | layout . houses ( ) . iter ( ) . map ( | h | subcity . get_price ( * h ) as u32 ) . sum ( ) ) . max ( ) . unwrap ( ) ;
eprintln ! ( "Best {}, worst {} [{} layouts]" , best_price , worst_price , db . layouts ( ) . len ( ) ) ;
}
print_status ( & subcity_db , subcity . city ( ) ) ;
let mut cache = combine ::CompatibilityCache ::new ( ) ;
// TODO: Deduplication of the DB
loop {
// This is a bottleneck when it comes to multithreading, it only runs on a single thread
combine ::iterate_combines ( & mut subcity_db , CUT_COMBINE_TOP_LAYOUTS , subcity . city ( ) , & mut cache , false ) ;
eprintln ! ( "Finished cut combines" ) ;
print_status ( & subcity_db , subcity . city ( ) ) ;
let mut weighted_random_layouts = Vec ::new ( ) ;
// Only using the underlying memory-based DB is required here as the SqliteLayoutDB
// is not thread-safe. We are only reading in the parallel iterator, so that's fine.
let memory_db = subcity_db . memory_db ( ) ;
weighted_random_layouts . par_extend ( ( 0 . . WEIGHTED_RANDOM_LAYOUTS ) . into_par_iter ( ) . map ( | i | {
let seed : u64 = thread_rng ( ) . gen ( ) ;
let mut rng = StdRng ::seed_from_u64 ( seed ) ;
let mut layout = HouseLayout ::new ( subcity . city ( ) ) ;
let best_price : u32 = memory_db . layouts ( ) . iter ( ) . map ( | layout | layout . houses ( ) . iter ( ) . map ( | h | subcity . city ( ) . get_price ( * h ) as u32 ) . sum ( ) ) . min ( ) . unwrap ( ) ;
let worst_price : u32 = memory_db . layouts ( ) . iter ( ) . map ( | layout | layout . houses ( ) . iter ( ) . map ( | h | subcity . city ( ) . get_price ( * h ) as u32 ) . sum ( ) ) . max ( ) . unwrap ( ) ;
let price_range = worst_price - best_price ;
let max_price = best_price as f64 + ( price_range as f64 * ( 1. - IGNORED_WEIGHT_RATIO ) ) ;
//eprintln!("Starting random weighted population {}, using DB, score range {}-{}, DB use probability {}...", i, best_price, worst_price, DB_CHOICE_PROBABILITY);
population ::populate_using_db ( & mut layout , & mut rng , memory_db , best_price as f64 , max_price as f64 , DB_CHOICE_PROBABILITY ) ;
//eprintln!("Finished random init {}, price: {}, houses: {}", i, layout.price(), layout.houses().len());
optimization ::iterate_improvements ( & mut layout , & mut rng , false , false ) ;
//eprintln!("Finished iterated improvements {}, price: {}, houses: {}", i, layout.price(), layout.houses().len());
layout . houses ( ) . clone ( )
} ) ) ;
for houses in & weighted_random_layouts {
subcity_db . add_layout ( houses , true ) . expect ( "Failed to add new layout" ) ;
}
let w_best : u32 = weighted_random_layouts . iter ( ) . map ( | houses | houses . iter ( ) . map ( | h | subcity . city ( ) . get_price ( * h ) as u32 ) . sum ( ) ) . min ( ) . unwrap ( ) ;
let w_worst : u32 = weighted_random_layouts . iter ( ) . map ( | houses | houses . iter ( ) . map ( | h | subcity . city ( ) . get_price ( * h ) as u32 ) . sum ( ) ) . max ( ) . unwrap ( ) ;
eprintln ! ( "Finished weighted random population, price range {}-{}" , w_best , w_worst ) ;
print_status ( & subcity_db , subcity . city ( ) ) ;
}
}