/// Check if the given sequence of tokens can reach the target value
/// when combined by multiplication or addition (always processed left-to-right)
/// If 'can_concat' is true, also check concatenation as one of the valid operations
fn is_solveable(target: u64, tokens: &[u64], can_concat: bool) -> bool {
    match tokens.len() {
        // At the end of the list: did it reach the target?
        i if i < 2 => target == tokens[0],
        // Try each operator and recurse
        _ => {
            let (&last, rest) = tokens.split_last().unwrap();
            // Stop early if target is already greater than the last element of the list
            // Try addition first
            (target > last) && is_solveable(target - last, rest, can_concat)
            // Try multiplication. Short-circuit if target is not a multiple of the last element
                || (target % last == 0 && is_solveable(target / last, rest, can_concat))
            // Try concatenation if its enabled
                || (can_concat && try_concat(target, tokens))
        }
    }
}

/// Check if its possible for a solution to exist where the last element
/// is concatenated onto the result of the other values
/// Short-circuit if the target value doesn't end with the last element (as a string)
/// Or if the target value _matches_ the last element
fn try_concat(target: u64, tokens: &[u64]) -> bool {
    let (&last, rest) = tokens.split_last().unwrap();
    let target = target.to_string();
    let last = last.to_string();
    match target.strip_suffix(&last) {
        Some(prefix) => {
            (!prefix.is_empty()) && is_solveable(prefix.parse::<u64>().unwrap(), rest, true)
        }
        None => false,
    }
}