Xenharmonic Wiki

Code for billiard scales: Difference between revisions

← Older edit
VisualWikitext
Inthar (talk | contribs)
autopatrolled, emailconfirmed
15,668 edits
Undo revision 220438 by Inthar (talk)
Inthar (talk | contribs)
autopatrolled, emailconfirmed
15,668 edits
 
(2 intermediate revisions by the same user not shown)
Line 502: Line 502:
//! 3. For each region, trace a trajectory and record which coordinate changes
//! 3. For each region, trace a trajectory and record which coordinate changes
//! 4. The sequence of changes (0=L, 1=m, 2=s) forms the scale word
//! 4. The sequence of changes (0=L, 1=m, 2=s) forms the scale word
//!
//! # Examples
//!
//! ```
//! use ternary::billiard::billiard_scales;
//!
//! // Generate all billiard scales with signature 5L 2m 2s
//! let scales = billiard_scales(5, 2, 2);
//! assert!(!scales.is_empty());
//!
//! // Each scale has the correct number of steps
//! for scale in &scales {
//!    assert_eq!(scale.len(), 9);  // 5 + 2 + 2 = 9 notes
//! }
//! ```
//!
//! # Properties
//! # Properties
//!
//!
Line 531: Line 515:
use crate::helpers::gcd;
use crate::helpers::gcd;
use crate::plane_geometry::{ConvexPolygon, Line, Point, PointLineConfiguration, Slope};
use crate::plane_geometry::{ConvexPolygon, Line, Point, PointLineConfiguration, Slope};
use crate::words::{Letter, least_mode};
 
pub type Letter = usize;


// ERRORS
// ERRORS
Line 563: Line 548:


impl std::error::Error for BadBilliardState {}
impl std::error::Error for BadBilliardState {}
/// Rotate a scale word left by `degree` positions (change mode).
pub fn rotate<T: std::clone::Clone>(slice: &[T], degree: usize) -> Vec<T> {
    let degree = degree % slice.len();
    if degree == 0 {
        slice.to_vec()
    } else {
        [&slice[degree..slice.len()], &slice[0..degree]].concat()
    }
}
/// The lexicographically least mode of a word (where the letters are in their usual order).
pub fn least_mode(scale: &[Letter]) -> Vec<Letter> {
    rotate(scale, booth(scale))
}
/// The rotation required from the current word to the
/// lexicographically least mode of a word.
/// Booth's algorithm requires at most 3*n* comparisons and *n* storage locations where *n* is the input word's length.
/// See Booth, K. S. (1980). Lexicographically least circular substrings.
/// Information Processing Letters, 10(4-5), 240–242. doi:10.1016/0020-0190(80)90149-0
pub fn booth(scale: &[Letter]) -> usize {
    let scale_len = scale.len();
    // `failure_func` is the failure function of the least rotation; `usize::MAX` is used as a null value.
    // null indicates that the failure function does not point backwards in the string.
    // `usize::MAX` will behave the same way as -1 does, assuming wrapping unsigned addition
    let mut failure_func = vec![usize::MAX; 2 * scale_len];
    let mut least_rotation: usize = 0;
    // `scan_pos` loops over `scale` twice.
    for scan_pos in 1..2 * scale_len {
        let mut match_len = failure_func[scan_pos - least_rotation - 1];
        while match_len != usize::MAX
            && scale[scan_pos % scale_len]
                != scale[least_rotation.wrapping_add(match_len).wrapping_add(1) % scale_len]
        {
            // (1) If the scan_pos-th letter is less than s[(least_rotation + match_len + 1) % scale_len] then change least_rotation to scan_pos - match_len - 1,
            // in effect left-shifting the failure function and the input string.
            // This appropriately compensates for the new, shorter least substring.
            if scale[scan_pos % scale_len]
                < scale[least_rotation.wrapping_add(match_len).wrapping_add(1) % scale_len]
            {
                least_rotation = scan_pos.wrapping_sub(match_len).wrapping_sub(1);
            }
            match_len = failure_func[match_len];
        }
        if match_len == usize::MAX
            && scale[scan_pos % scale_len]
                != scale[least_rotation.wrapping_add(match_len).wrapping_add(1) % scale_len]
        {
            // See note (1) above.
            if scale[scan_pos % scale_len]
                < scale[least_rotation.wrapping_add(match_len).wrapping_add(1) % scale_len]
            {
                least_rotation = scan_pos;
            }
            failure_func[scan_pos - least_rotation] = usize::MAX;
        } else {
            failure_func[scan_pos - least_rotation] = match_len.wrapping_add(1);
        }
        // The induction hypothesis is that
        // at this point `failure_func[0..scan_pos - least_rotation]` is the failure function of `s[least_rotation..(least_rotation+scan_pos)%scale_len]`,
        // and `least_rotation` is the lexicographically least subword of the letters scanned so far.
    }
    least_rotation
}


fn projected_constraint_planes(a: u32, b: u32, c: u32) -> (Vec<Line>, Vec<Line>, Vec<Line>) {
fn projected_constraint_planes(a: u32, b: u32, c: u32) -> (Vec<Line>, Vec<Line>, Vec<Line>) {
Line 761: Line 811:
/// * `b` - Number of m (medium) steps
/// * `b` - Number of m (medium) steps
/// * `c` - Number of s (small) steps
/// * `c` - Number of s (small) steps
///
/// # Examples
///
/// ```
/// use ternary::billiard::billiard_scales;
///
/// // Generate billiard scales for 5L 2m 2s
/// let scales = billiard_scales(5, 2, 2);
/// assert!(!scales.is_empty());
///
/// // All scales are in canonical form (sorted)
/// for scale in &scales {
///    assert_eq!(scale.iter().filter(|&&x| x == 0).count(), 5);  // 5 L steps
/// }
/// ```
///
/// # Returns
/// # Returns
///
///
Line 823: Line 857:
}
}
</syntaxhighlight>
</syntaxhighlight>
=== lib.rs ===
=== lib.rs ===
<syntaxhighlight lang="rs">use std::collections::BTreeSet;
<syntaxhighlight lang="rs">use std::collections::BTreeSet;
Line 1,134: Line 1,169:
name = "billiard_scales"
name = "billiard_scales"
version = "0.0.0"
version = "0.0.0"
edition = "2021"
edition = "2024"


# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
Retrieved from "https://en.xen.wiki/w/Code_for_billiard_scales"