"Perfect" Advent Calendars

README.md

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?

Cargo.toml

[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"

main.rs

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);
}