Count the size of the Levenshtein neighborhood

Question

Input

A binary string \$s\$ of length \$n\$ and a positive integer \$k \leq n\$.

Output

The number of binary strings with Levenshtein distance exactly \$k\$ from the string \$s\$.

Example outputs

Each example gives the largest possible output for the given \$(n, k)\$ pair.

k=1, s=1010, output=14

k=2, s=1010, outupt=55

k=3, s=1101, output=112

k=4, s=1001, output=229

k=1, s=1010101010, output=32

k=2, s=1010110101, output=362

k=3, s=1010110101, output=2016

k=4, s=1011001101, output=6538

k=5, s=1011001101, output=16223

k=6, s=1001100110, output=37620

k=7, s=1001100110, output=85028

k=8, s=1001100110, output=187667

k=9, s=1001100110, output=406183

k=10, s=1001100110, output=864793

k=1, s=101010101010, output=38

k=2, s=101010010101, output=533

k=3, s=101010010101, output=3804

k=4, s=101001100101, output=15708

k=5, s=101100110010, output=45717

Score

The score will be the highest \$n, k\$ pair your code outputs the correct answer for on my Ubuntu desktop in one minute. The order should be (1,1), (2,1), (2,2), (3,1),(3,2), (3,3), (4,1), (4,2), (4,3), (4,4), (5,1) etc. The time is the total running time and not just for the last pair.

Your code should work for all strings but I will time it using random binary strings.

As always, this is a competition per language so Python coders don't need to worry about C competitors.

Leaderboard

• (28, 23) in Rust by Anders Kaseorg
• (12, 11) in Rust by corvus_192.
• (12, 10) in Pypy by Jonathan Allen.
• (11, 10) in Pypy by Value Ink.
• (11, 9) in Python by Value Ink.
• (11, 9) in Python by Jonathan Allen.
• (7,6) in Charcoal by Neil.

Edit

I noticed this related question which has a link that suggests there is a fast algorithm

Answer 1

Rust, score ≈ (28, 23)

The number of strings at distance \$k\$ from \$s\$ with some given prefix \$p\$ is a function of \$s\$, \$k\$, and the last column of the Wagner–Fischer table of \$s\$ and \$p\$. We use a recursive search on prefixes \$p\$, caching results based on this last column.

Build with cargo build --release, run with target/release/levenshtein-neighborhood <s> <k>.

Cargo.toml

[package]
name = "levenshtein-neighborhood"
version = "0.1.0"
edition = "2021"

[dependencies]
hashbrown = "0.14.0"
rustc-hash = "1.1.0"
typed-arena = "2.0.2"

src/main.rs

use hashbrown::hash_map::HashMap;
use rustc_hash::FxHasher;
use std::env;
use std::hash::{BuildHasher, BuildHasherDefault};
use typed_arena::Arena;

type Count = u64; // For n + k > 64, change this to u128
type Cache<'a> = HashMap<&'a [u8], Count, BuildHasherDefault<FxHasher>>;

fn count_state<'a>(
    target: &[bool],
    distance: u8,
    arena: &'a Arena<u8>,
    cache: &mut Cache<'a>,
    state: &mut [u8],
) -> Count {
    let hash = cache.hasher().hash_one(&state);
    if let Some((_, &count)) = cache.raw_entry().from_key_hashed_nocheck(hash, state) {
        count
    } else {
        let new_state = state;
        let state = arena.alloc_extend(new_state.iter().copied());
        let mut count = Count::from(state[target.len()] == distance);
        for symbol in [false, true] {
            let mut z = state[0].min(distance) + 1;
            new_state[0] = z;
            for (((o, &c), &x), &y) in new_state[1..]
                .iter_mut()
                .zip(target)
                .zip(&state[..state.len() - 1])
                .zip(&state[1..])
            {
                z = (x + u8::from(symbol != c)).min(y.min(z).min(distance) + 1);
                *o = z;
            }
            count += count_state(target, distance, arena, cache, new_state);
        }
        cache
            .raw_entry_mut()
            .from_hash(hash, |_| false)
            .insert(state, count);
        count
    }
}

fn count(target: &[bool], distance: u8) -> Count {
    let arena = Arena::new();
    let state = arena.alloc_extend((0..=target.len()).map(|i| (i as u8).min(distance + 1)));
    let mut cache = Cache::default();
    cache.insert(
        &arena.alloc_extend((0..=target.len()).map(|_| distance + 1))[..],
        0,
    );
    count_state(target, distance, &arena, &mut cache, state)
}

fn main() {
    if let [_program, target, distance] = &Vec::from_iter(env::args())[..] {
        let target = Vec::from_iter(target.chars().map(|c| c == '1'));
        let distance = distance.parse().unwrap();
        println!("{}", count(&target, distance));
    } else {
        panic!("usage: levenshtein-neighborhood <s> <k>");
    }
}

Answer 2

Python, (11, 8); with Python PyPy (12, 10)

New version of Value Ink's answer using bit twiddling in place of string manipulation.

from collections import deque

def countFixedDistance(s: str, k: int) -> int:
    n = int('1' + s, 2)
    distances: dict[int, int] = {n: 0}
    queue = deque(((n, len(s)),))
    valid: set[int] = set()
    while len(queue) > 0:
        current, bit_count = queue.popleft()
        next_dist = distances[current] + 1
        next_bit_count = bit_count - 1
        for next_gen in (
            ((current >> e + 1 << e) + current % (1 << e) for e in range(bit_count)),
            (current ^ (1 << e) for e in range(bit_count)),
            (((current >> e << 1 | b) << e) + current % (1 << e) for b in (0, 1) for e in range(bit_count + 1)),
        ):
          for next in next_gen:
              if next in distances: continue
              distances[next] = next_dist
              if next_dist < k:
                  queue.append((next, next_bit_count))
              else:
                  valid.add(next)
          next_bit_count += 1
    return len(valid)

Attempt This Online!

---

With a lot of tweaks to do fewer operations, it does get further but still not to completion of (11, 9) on ATO, so it may also be worth benchmarking too:

from collections import deque

def countFixedDistance(s: str, k: int) -> int:
    n = int('1' + s, 2)
    distances: dict[int, int] = {n: 0}
    queue = deque(((n, len(s)),))
    valid: set[int] = set()
    while len(queue) > 0:
        current, bit_count = queue.popleft()
        next_dist = distances[current] + 1
        for e in range(bit_count):
            left = current >> e
            left_1 = left << 1
            pow = 1 << e
            right = current % pow
            bp1 = bit_count + 1
            for next, next_bit_count in (
                ((left >> 1 << e) | right, bit_count - 1),
                (current ^ pow, bit_count),
                ((left_1 << e) | right, bp1),
                (((left_1 | 1) << e) | right, bp1),
            ):
                if next in distances: continue
                distances[next] = next_dist
                if next_dist < k:
                    queue.append((next, next_bit_count))
                else:
                    valid.add(next)
        for next in (
            pow << 2 | current,
            3 << bit_count ^ current,
        ):
            if next in distances: continue
            distances[next] = next_dist
            if next_dist < k:
                queue.append((next, bit_count + 1))
            else:
                valid.add(next)
    return len(valid)

Attempt This Online!

Answer 3

Rust, (12, 11)

This is basically a line-by-line port of Jonathan Allan's answer, with is already very good. Thanks! I wrote this to practice some Rust.

It uses the nohash-hasher crate for extremely fast HashMap lookups, with take up the vast majority of the time.

Try it online on rustexplorer.com. Runs an unoptimized debug build, so don't rely on it for measurements.

I have a github repo with build instructions.

#![warn(clippy::all)]

use std::collections::VecDeque;
use std::collections::hash_map::Entry;
use std::time::Instant;

use nohash_hasher::{IntMap, IntSet};

fn count_fixed_distance(s: &str, k: u32) -> usize {
    let n = i32::from_str_radix(&format!("1{s}"), 2).unwrap();
    let mut distances = IntMap::with_capacity_and_hasher(1 << (s.len() + k as usize), Default::default());
    distances.insert(n, 0);
    let mut queue = VecDeque::from([(n, s.len())]);
    // capacity is just experimentation
    let mut valid = IntSet::with_capacity_and_hasher(1 << (k + 1), Default::default());
    while let Some((current, bit_count)) = queue.pop_front() {
        let next_dist = distances.get(&current).unwrap() + 1;
        let mut pow = 0;
        for e in 0..bit_count {
            let left = current >> e;
            let left_1 = left << 1;
            pow = 1 << e;
            let right = current % pow;
            let bp1 = bit_count + 1;
            for (next, next_bit_count) in [
                ((left >> 1 << e) | right, bit_count - 1),
                (current ^ pow, bit_count),
                ((left_1 << e) | right, bp1),
                (((left_1 | 1) << e) | right, bp1)
            ] {
                match distances.entry(next) {
                    Entry::Vacant(ve) => {
                        ve.insert(next_dist);
                    }
                    Entry::Occupied(_) => continue,
                }
                if next_dist < k {
                    queue.push_back((next, next_bit_count));
                } else {
                    valid.insert(next);
                }
            }
        }

        for next in [pow << 2 | current, 3 << bit_count ^ current] {
            match distances.entry(next) {
                Entry::Vacant(ve) => {
                    ve.insert(next_dist);
                }
                Entry::Occupied(_) => continue,
            }
            if next_dist < k {
                queue.push_back((next, bit_count + 1));
            } else {
                valid.insert(next);
            }
        }
    }
    valid.len()
}

fn main() {
    let start = Instant::now();
    let mut s = String::with_capacity(32);
    s.push('0');
    let mut v = 0;
    while s.len() <= 12 { // approx 2 minutes for profiling
        for k in 1..(s.len() + 1) {
            println!("{} {} {}", s.len(), k, count_fixed_distance(&s, k as u32));
        }
        s.push(['1', '1', '0', '0'][v % 4]);
        v += 1;
        println!("{}", s)
    }
    println!("{} seconds", start.elapsed().as_secs_f32());
}

Answer 4

Python, ~(11,6)

Direct adaptation of my answer on Pick a random string at a fixed edit distance with a minor optimization of generating the sets inline instead of each one being a function call. ATO seems to flip-flop between (11,6) and (11,7) for me right now.

from collections import deque

def countFixedDistance(s: str, k: int) -> int:
  if k <= 0: return s

  chars: set[str]          = set('01')
  distances: dict[str,int] = {s: 0}
  queue                    = deque((s,))
  valid: set[str]          = set()

  while len(queue) > 0:
    current = queue.popleft()
    nextdist = distances[current] + 1
    for nxt in {current[:i] + c + current[i:] for c in chars for i in range(len(s)+1)} \
               | {current[:i] + c + current[i+1:] for c in chars for i in range(len(s)) if c != s[i]} \
               | {current[:i] + current[i+1:] for i in range(len(s))}:
      if nxt in distances: continue
      distances[nxt] = nextdist
      if nextdist < k:
        queue.append(nxt)
      else:
        valid.add(nxt)

  return len(valid)

Attempt This Online!

Answer 5

Charcoal, 81 bytes

⊞υη≔⦃η¹⦄ζＦＮ«≔υε≔⟦⟧υＦεＦΣ⁺Ｅκ⟦⭆κ¬⁼Ｉν⁼μξ⭆κ⎇⁼μξων⟧Ｅ²Ｅ⊕Ｌκ⁺⁺✂κ⁰ν¹λ✂κν¿¬§ζλ«⊞υλ§≔ζλ¹»»ＩＬυ

Attempt This Online! Link is to verbose version of code. Can handle results of up to about 20000 on ATO, so 5 1011001101 or 4 101001100101. Explanation:

⊞υη

Start with one string of distance 0.

≔⦃η¹⦄ζ

Start with one string found so far.

ＦＮ«

Loop k times.

≔υε≔⟦⟧υＦε

Start collecting strings of distance i+1.

ＦΣ⁺Ｅκ⟦⭆κ¬⁼Ｉν⁼μξ⭆κ⎇⁼μξων⟧Ｅ²Ｅ⊕Ｌκ⁺⁺✂κ⁰ν¹λ✂κν

Loop over all strings of edit distance 1 from the current string of distance i.

¿¬§ζλ«⊞υλ§≔ζλ¹»

If this string is new then mark it as seen and add it to the list of strings of edit distance i+1.

»ＩＬυ

Output the count of strings of edit distance k.