Skip to content

Instantly share code, notes, and snippets.

@jffry
Last active Dec 13, 2018
Embed
What would you like to do?
"Perfect" Advent Calendars

Inspired by this article

This is some EXTREMELY rough-and-ready Rust and likely has huge problems. I basically dabbled with Rust 2 years ago, shelved that knowledge, dusted it off today, and built this.

Using f32 instead of f64 gave me some nice speed improvements, then I can go back through and get final scores with f64.

Misc speed improvements: The numerator in the sum purely depends upon coordinate pairs so we can go ahead and precompute that and stash it in a lookup table.

Results

Here's the lowest score I've found so far:

[[14  7 19 12  5 17]
 [21  9  2 24 22 10]
 [ 4 16 23  1  3 15]
 [11 18  6 13 20  8]]

375.923809971073

Notice the vertical symmetry. I conjecture that is a property of the best solutions. And here's the highest score I have found, just to tip the problem on its head:

[[ 6  7 10 11 23 24]
 [ 5  8  9 12 22 21]
 [ 4  3 13 16 17 20]
 [ 1  2 14 15 18 19]]

529.6200384399018

It's rotationally symmetric, and the numbers carve out what looks like a squished Hilbert curve.

Future Questions

  • Is there a way to show either of these solutions to be optimal?
  • How do things look in other size grids that aren't 6x4?
  • Does the pattern of Hilbert-like curves continue to show up in maximal-measure solutions of other grids?
[package]
name = "advent-calendar"
version = "0.1.0"
authors = ["Jeffrey Stanton <jffry@users.noreply.github.com>"]
edition = "2018"
[dependencies]
rand = "0.6"
time = "0.1"
use rand::thread_rng;
use rand::seq::SliceRandom;
use std::sync::{Mutex, Arc};
use std::thread;
extern crate time;
use time::PreciseTime;
type SCORE = f64;
fn location(index:usize) -> (u8, u8) {
((index / 6) as u8,
(index % 6) as u8)
}
fn absdelta(a:u8, b:u8) -> u8 {
if b > a { b - a } else { a - b }
}
fn distance(n1:usize, n2:usize) -> SCORE {
let (r1, c1) = location(n1);
let (r2, c2) = location(n2);
let dr = absdelta(r1, r2);
let dc = absdelta(c1, c2);
((dr * dr + dc * dc) as SCORE).sqrt()
}
fn numerator_table() -> [[SCORE; 24]; 24] {
let max = distance(0, 23); //corner to corner
let mut table = [[0.0; 24]; 24];
for n1 in 0..24 {
for n2 in 0..24 {
table[n1][n2] = max - distance(n1, n2);
}
}
table
}
fn score_pair(table:[[SCORE; 24]; 24], n1:usize, v1:u8, n2:usize, v2:u8) -> SCORE {
let numer = table[n1][n2];
let denom = absdelta(v1, v2) as SCORE;
numer / denom
}
fn score_calendar(table:[[SCORE; 24]; 24], calendar:[u8;24]) -> SCORE {
let mut total:SCORE = 0.0;
for n1 in 0..24 {
let v1 = calendar[n1];
for n2 in 0..n1 {
let pair_score = score_pair(table, n1, v1, n2, calendar[n2]);
total += pair_score + pair_score;
}
}
total
}
//swap the specified element with all other elements and keep the configuration with the best score
fn best_swap(table:[[SCORE; 24]; 24], calendar: &mut [u8;24]) -> (usize, usize) {
let mut best_score = score_calendar(table, *calendar);
let mut best_swap = (0, 0);
//TODO: can we compute some partial information to reduce the amount of work needed to score every swap?
for n1 in 0..24 {
for n2 in 0..n1 {
calendar.swap(n1, n2);
let score = score_calendar(table, *calendar);
if score < best_score {
best_score = score;
best_swap = (n1, n2);
}
calendar.swap(n2, n1);
}
}
best_swap
}
fn optimize(table:[[SCORE; 24]; 24], calendar: &mut [u8;24]) {
for n in 0..100 {
let (n1, n2) = best_swap(table, calendar);
if n1 != n2 {
calendar.swap(n1, n2);
} else {
return;
}
}
println!("gave up after 100 swaps: {:?}", calendar);
}
fn search_worker(table:[[SCORE; 24]; 24], worker_id:usize, shared_best: Arc<Mutex<SCORE>>) {
let worker_start = PreciseTime::now();
let mut rng = thread_rng();
let mut calendar = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24];
for block in 1.. {
let block_start = PreciseTime::now();
for _ in 0..1000 {
calendar.shuffle(&mut rng);
optimize(table, &mut calendar);
let score = score_calendar(table, calendar);
let mut best = shared_best.lock().unwrap();
if score < *best {
let elapsed = worker_start.to(PreciseTime::now());
println!("LOWER, elapsed: {}, score: {}, worker: {}, calendar: {:?}", elapsed, score, worker_id, calendar);
*best = score;
}
}
let block_end = PreciseTime::now();
println!("worker {} completed block {} in {}", worker_id, block, block_start.to(block_end));
}
}
fn search_parallel(table:[[SCORE; 24]; 24], worker_count:usize) {
let mut x = (1, 2);
let shared_best = Arc::new(Mutex::new(9999999.0 as SCORE));
let mut workers = vec![];
for worker_id in 0..worker_count {
let shared_best = Arc::clone(&shared_best);
workers.push(thread::spawn(move || {
search_worker(table, worker_id, shared_best);
}));
}
for thread in workers {
let _ = thread.join();
}
}
fn main() {
let table = numerator_table();
search_parallel(table, 8);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment