assert_eq!(beer::verse(0), "No more bottles of beer on the wall, no more bottles of beer.\nGo to the store and buy some more, 99 bottles of beer on the wall.\n");

	assert_eq!(beer::verse(0), "No more bottles of beer on the wall, no more bottles of beer.\nGo to the store and buy some more, 99 bottles of beer on the wall.\n");

    assert_eq!(beer::verse(1), "1 bottle of beer on the wall, 1 bottle of beer.\nTake it down and pass it around, no more bottles of beer on the wall.\n");

	assert_eq!(beer::verse(1), "1 bottle of beer on the wall, 1 bottle of beer.\nTake it down and pass it around, no more bottles of beer on the wall.\n");

    assert_eq!(beer::verse(2), "2 bottles of beer on the wall, 2 bottles of beer.\nTake one down and pass it around, 1 bottle of beer on the wall.\n");

	assert_eq!(beer::verse(2), "2 bottles of beer on the wall, 2 bottles of beer.\nTake one down and pass it around, 1 bottle of beer on the wall.\n");

    assert_eq!(beer::verse(8), "8 bottles of beer on the wall, 8 bottles of beer.\nTake one down and pass it around, 7 bottles of beer on the wall.\n");

	assert_eq!(beer::verse(8), "8 bottles of beer on the wall, 8 bottles of beer.\nTake one down and pass it around, 7 bottles of beer on the wall.\n");

    assert_eq!(beer::sing(8, 6), "8 bottles of beer on the wall, 8 bottles of beer.\nTake one down and pass it around, 7 bottles of beer on the wall.\n\n7 bottles of beer on the wall, 7 bottles of beer.\nTake one down and pass it around, 6 bottles of beer on the wall.\n\n6 bottles of beer on the wall, 6 bottles of beer.\nTake one down and pass it around, 5 bottles of beer on the wall.\n");

	assert_eq!(beer::sing(8, 6), "8 bottles of beer on the wall, 8 bottles of beer.\nTake one down and pass it around, 7 bottles of beer on the wall.\n\n7 bottles of beer on the wall, 7 bottles of beer.\nTake one down and pass it around, 6 bottles of beer on the wall.\n\n6 bottles of beer on the wall, 6 bottles of beer.\nTake one down and pass it around, 5 bottles of beer on the wall.\n");

    assert_eq!(beer::sing(3, 0), "3 bottles of beer on the wall, 3 bottles of beer.\nTake one down and pass it around, 2 bottles of beer on the wall.\n\n2 bottles of beer on the wall, 2 bottles of beer.\nTake one down and pass it around, 1 bottle of beer on the wall.\n\n1 bottle of beer on the wall, 1 bottle of beer.\nTake it down and pass it around, no more bottles of beer on the wall.\n\nNo more bottles of beer on the wall, no more bottles of beer.\nGo to the store and buy some more, 99 bottles of beer on the wall.\n");

	assert_eq!(beer::sing(3, 0), "3 bottles of beer on the wall, 3 bottles of beer.\nTake one down and pass it around, 2 bottles of beer on the wall.\n\n2 bottles of beer on the wall, 2 bottles of beer.\nTake one down and pass it around, 1 bottle of beer on the wall.\n\n1 bottle of beer on the wall, 1 bottle of beer.\nTake it down and pass it around, no more bottles of beer on the wall.\n\nNo more bottles of beer on the wall, no more bottles of beer.\nGo to the store and buy some more, 99 bottles of beer on the wall.\n");

use std::convert::TryInto;
const DICT: [&str; 24] = [
	"N", // 0
	"o m", // 1
	"ore", // 2
	" bottle", // 3
	"s", // 4
	" of beer", // 5
	" on", // 6
	" th", // 7
	"e ", // 8
	"wall", // 9
	", ", // 10
	"n", // 11
	".\n", // 12
	"Go to", // 13
	"st", // 14
	" and ", // 15
	"buy som", // 16
	"m", // 17
	"99", // 18
	"Take", // 19
	" it ", // 20
	"down", // 21
	"pass", // 22
	"around", // 23
];
// Length for verse 3 onwards is just for the common substrings (i.e., excluding `n` and `n - 1`, so these need to be added back).
const LENGTHS: [usize; 4] = [129, 118, 114, 112];
fn integer_length(a: usize) -> usize {
	((a as f64).log10() as usize) + 1
}
struct IndicesWithPrefixes<'a>(&'a [(&'a str, &'a [usize])]);
impl IndicesWithPrefixes<'_> {
	fn generate_verse(&self, n: u32) -> String {
		let n = n as usize;
		let mut out = String::with_capacity(if n > 2 {
			LENGTHS[3] + 2 * integer_length(n) + integer_length(n - 1)
		} else { LENGTHS[n] } );
		self.0.iter().for_each(|(prefix, indices)| {
			out.push_str(prefix);
			indices.iter().for_each(|index| out.push_str(DICT[*index]));
		});
		out
	}
}

    unimplemented!("emit verse {}", n)

	match n {
		0 => {
			let mut out = String::with_capacity(LENGTHS[0]);
			[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1, 2, 3, 4, 5, 12, 13, 7, 8, 14, 2, 15, 16, 8, 17, 2, 10, 18, 3, 4, 5, 6, 7, 8, 9, 12].iter().for_each(|index| out.push_str(DICT[*index]));
			out
		}
		1 => {
			let n_string = n.to_string();
			IndicesWithPrefixes(&[(&n_string, &[3, 5, 6, 7, 8, 9, 10]), (&n_string, &[3, 5, 12, 19, 20, 21, 15, 22, 20, 23, 10, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12])]).generate_verse(n)
		}
		2 => {
			let (n_string, m_string) = (n.to_string(), (n - 1).to_string());
			IndicesWithPrefixes(&[(&n_string, &[3, 4, 5, 6, 7, 8, 9, 10]), (&n_string, &[3, 4, 5, 12, 19, 6, 8, 21, 15, 22, 20, 23, 10]), (&m_string, &[3, 5, 6, 7, 8, 9, 12])]).generate_verse(n)
		}
		_ => {
			let (n_string, m_string) = (n.to_string(), (n - 1).to_string());
			IndicesWithPrefixes(&[(&n_string, &[3, 4, 5, 6, 7, 8, 9, 10]), (&n_string, &[3, 4, 5, 12, 19, 6, 8, 21, 15, 22, 20, 23, 10]), (&m_string, &[3, 4, 5, 6, 7, 8, 9, 12])]).generate_verse(n)
		}
	}
}
fn integer_range_length(start: usize, end: usize) -> usize {
	let (start_digits, end_digits) = (integer_length(start), integer_length(end));
	let (a, b) = ((10_f64.powi(start_digits.try_into().unwrap()) - 1.0) as usize, 10_f64.powi((end_digits - 1).try_into().unwrap()) as usize);
	(integer_length(a + 1)..=integer_length(b - 1)).fold(0, |acc, elem| acc + 9 * elem * (10_f64.powi((elem - 1).try_into().unwrap()) as usize)) + ((a - start + 1) * start_digits) + ((end - b + 1) * end_digits)

    unimplemented!("sing verses {} to {}, inclusive", start, end)

	let (mut s, mut e) = (start, end);
	if start < end {
		s = end;
		e = start;
	}
	match (s, e) {
		(0, 0) => verse(0),
		(1, 1) => verse(1),
		(2, 2) => verse(2),
		(_, _) => {
			let mut out = String::with_capacity(
				match (s, e) {
					(1, 0) => LENGTHS[0] + LENGTHS[1],
					(2, 0) => LENGTHS[0] + LENGTHS[1] + LENGTHS[2],
					(2, 1) => LENGTHS[1] + LENGTHS[2],
					(_, _) => (s as usize - 2) * LENGTHS[3] + integer_range_length(3, s as usize) + match e {
						0 => LENGTHS[0] + LENGTHS[1] + LENGTHS[2],
						1 => LENGTHS[1] + LENGTHS[2],
						2 => LENGTHS[2],
						_ => 0,
					},
				} + ((s - e) as usize)
			);
			if start < end {
				out.push_str(&verse(e));
				(e + 1..=s).for_each(|a| {
					out.push_str("\n");
					out.push_str(&verse(a));
				});
			} else {
				out.push_str(&verse(s));
				(e..=s - 1).rev().for_each(|a| {
					out.push_str("\n");
					out.push_str(&verse(a));
				});
			}
			out
		}
	}