6
\$\begingroup\$

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

\$\endgroup\$
12
  • \$\begingroup\$ How is the highest (n,k) pair counted? Is it total runtime to generate up to (n,k) or is it individual runtime for the one (n, k) pair? \$\endgroup\$ Sep 16, 2023 at 16:07
  • \$\begingroup\$ @ToAskOrNotToAsk It is the total runtime. \$\endgroup\$
    – Simd
    Sep 16, 2023 at 16:15
  • \$\begingroup\$ Is the alphabet limited to '0' and '1'? \$\endgroup\$
    – RootTwo
    Sep 16, 2023 at 18:37
  • \$\begingroup\$ @RootTwo Yes it is. \$\endgroup\$
    – Simd
    Sep 16, 2023 at 18:39
  • 1
    \$\begingroup\$ It’s linear in \$|P|\$ but exponential in \$k\$. “The downside of the method, however, is that it requires the computation of the DFA \$\mathrm{DULA}(k)\$, whose size increases exponentially with the number of errors \$k\$.” \$\endgroup\$ Sep 20, 2023 at 20:20

5 Answers 5

8
+50
\$\begingroup\$

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>");
    }
}
\$\endgroup\$
12
  • \$\begingroup\$ Could you modify it so that it runs on the 11001100... type strings so I can compare the outputs to the other answers? \$\endgroup\$
    – Simd
    Sep 18, 2023 at 21:25
  • 1
    \$\begingroup\$ @Simd It runs on any string you want, e.g., target/release/levenshtein-neighborhood 1001100110 9. \$\endgroup\$ Sep 18, 2023 at 22:26
  • \$\begingroup\$ Unless I am running your code wrong, it seems to get way higher than 28, 27 and also suffers from overflow because of the huge counts. I get to (37, 35) with bpa.st/ASBA \$\endgroup\$
    – Simd
    Sep 19, 2023 at 9:08
  • \$\begingroup\$ @Simd You'd have to change to u128 for the count: github.com/jendrikw/levenshtein-neighbourhood/blob/main/src/… \$\endgroup\$
    – corvus_192
    Sep 19, 2023 at 14:34
  • \$\begingroup\$ @corvus_192 Did you mean to link to a version using u128? \$\endgroup\$
    – Simd
    Sep 19, 2023 at 16:50
4
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ It seems to give 7 for countFixedDistance('10',1) where it should be 8 \$\endgroup\$
    – Simd
    Sep 17, 2023 at 18:46
  • 1
    \$\begingroup\$ @Simd I used the same footer, I've updated to use flush=True. There was a bug in the second link which meant a prefix of 0 was not being applied for the insertions (in the for next in (... loop, which only handles the two prefix insertion cases) - pow << 2 ^ current was incorrect it should have been 3 << bit_count ^ current. \$\endgroup\$ Sep 18, 2023 at 12:04
3
\$\begingroup\$

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());
}
\$\endgroup\$
3
  • \$\begingroup\$ What Cargo.toml do I need? I don't know rust. \$\endgroup\$
    – Simd
    Sep 18, 2023 at 21:15
  • 1
    \$\begingroup\$ I pushed my code to github: github.com/jendrikw/levenshtein-neighbourhood \$\endgroup\$
    – corvus_192
    Sep 18, 2023 at 21:27
  • \$\begingroup\$ I got it to work as you can see from the update to the question. \$\endgroup\$
    – Simd
    Sep 18, 2023 at 21:28
3
\$\begingroup\$

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!

\$\endgroup\$
15
  • \$\begingroup\$ Changing queue from a deque into a list appears to be very slightly faster, although ATO's own variance might be messing me up. \$\endgroup\$
    – Neil
    Sep 16, 2023 at 23:53
  • \$\begingroup\$ Also, prefixes of 011001100110.... seem to have the biggest neighbourhood. \$\endgroup\$
    – Neil
    Sep 16, 2023 at 23:57
  • \$\begingroup\$ Upped to (10, 9) with inlining of the function calls with a little rearrangement of order and prefix/postfix variables ATO (via tinyurl). (Does not look like the c != s[i], or in my update c != v, is having much effect yet.) \$\endgroup\$ Sep 17, 2023 at 1:32
  • \$\begingroup\$ (Oh and I switched to the prefixes Neil suggested in the footer) \$\endgroup\$ Sep 17, 2023 at 1:37
  • 1
    \$\begingroup\$ @Simd Best I can do is k=1 no pairs; k=2 or k=3 one pair; higher numbers usually mean more pairs but sometimes you skip a number of pairs; no more than n//2-1 pairs. \$\endgroup\$
    – Neil
    Sep 17, 2023 at 15:58
2
\$\begingroup\$

Charcoal, 81 bytes

⊞υη≔⦃η¹⦄ζFN«≔υε≔⟦⟧υFεFΣ⁺Eκ⟦⭆κ¬⁼Iν⁼μξ⭆κ⎇⁼μξων⟧E²E⊕Lκ⁺⁺✂κ⁰ν¹λ✂κν¿¬§ζλ«⊞υλ§≔ζλ¹»»ILυ

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.

FN«

Loop k times.

≔υε≔⟦⟧υFε

Start collecting strings of distance i+1.

FΣ⁺Eκ⟦⭆κ¬⁼Iν⁼μξ⭆κ⎇⁼μξων⟧E²E⊕Lκ⁺⁺✂κ⁰ν¹λ✂κν

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.

»ILυ

Output the count of strings of edit distance k.

\$\endgroup\$
5
  • \$\begingroup\$ Now you are challenging me to install charcoal! Remember this is fastest-code so the score you should be quoting is the highest n, k you get to in one minute \$\endgroup\$
    – Simd
    Sep 16, 2023 at 16:45
  • \$\begingroup\$ @Simd I don't know what you mean by n in this context. If you set k=1 then you can have a ridiculously long input string and it will still run in under a second. With k=2 you can input strings of at least 75 and it will still run in under a minute. With k=3 it starts struggling at length 25. And it can manage k=6 if the string only has length 6. \$\endgroup\$
    – Neil
    Sep 16, 2023 at 17:25
  • \$\begingroup\$ Actually I can't count, it can manage k=7 with a string of length 7, but only just. \$\endgroup\$
    – Neil
    Sep 16, 2023 at 17:28
  • \$\begingroup\$ I fixed the order you have to consider the pairs. Thank you for pointing out the problem. \$\endgroup\$
    – Simd
    Sep 16, 2023 at 17:58
  • 1
    \$\begingroup\$ @Simd My test suite reaches 7,6 on ATO in just under a minute. \$\endgroup\$
    – Neil
    Sep 16, 2023 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.