In the early phases, find_fills returns many results. Currently, other threads are starved while this big list of results is processed. If we stream these fills, other threads can begin working sooner.

https://nnethercote.github.io/perf-book/heap-allocations.html#reusing-collections

Remove mutex on state

Maybe prune results if there isn't at least 1 valid fill?

cargo build --examples --target wasm32-unknown-unknown currently fails b/c of pprof

Word boundaries don't change while filling occurs; parse 1x.

Word boundary info can be used to allocate string capacities more intelligently.

• support for different fillers
• support loading a file
• interactive finding of grids / file editing

Consider N queues, one per thread, where each output goes to a randomly assigned queue

This should:

1. improve determinism
2. perhaps improve perf

• Cache it
• Explore different data structures

Should make test data more legible.

https://github.com/bheisler/iai

Intuitively, we want to avoid spending resources on partially filled candidates which have rare or nonexistent n-shingles (https://en.wikipedia.org/wiki/N-gram). We can assign n-grams frequency scores based on the wordlist, and can score candidates based on the frequency scores (accounting for " " and * somehow).

Issue

Filler prints some statistics when filling takes some time.

It's not really an issue when called from command-line but it's not desirable when integrating it as a library. (I've been working on integrating it in my own small tool. For now I've just patched it to remove the calls to println! from filler.)

Steps to reproduce

1. Create the following grid in grids/empty_12x10.txt:

            
    *       
          * 
    *   *   
    *       
       *    
      *   * 
  *  *   *  
   *    *   
            

2. Calls filler from command line: ./target/debug/xwords --width 12 --height 10 --input grids/empty_12x10.txt

Expected result

No progress output, unless specified otherwise (e.g. with an option from command-line). Ideally API would provide some kind of progress notification mechanism.

Actual result

After a while, some outputs starts to be printed periodically:

    C       
    *       
    C     *C
    *   *   
    *       
       *    
      *   *C
  *  *   *  
  P* O  *   
PHILOSOPHIST

(...)

today we use

return 2 * word.contents.len() as i32 - empty_squares;

This seems directionally right, but a bit loose

Consider using https://github.com/doshea/nyt_crosswords

This will help choose words early.

There are a number of algorithmic tricks to make the state-space search dramatically faster, for example variable ordering, value-ordering, forward-pruning, backjumping, LDS/DDS. Here's a paper by my PhD advisor Matt Ginsberg describing Dr Fill, which is probably currently the world's fastest crossword-filler. A Rust implementation of the solver described here would be a really interesting project.

Issue

Filler panics when given grid is already filled. That's a very minor corner case but still :)

Steps to reproduce

1. Create the following file in grids/filled_4x4.txt

CFOS
BIRI
CCCV
SASA

2. Call the filler using command-line interface: ./target/debug/xwords --input grids/filled_4x4.txt

Expected result

The grid is returned as is since it is valid.

Actual result

> ./target/debug/xwords --input grids/filled_4x4.txt 
thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', src/fill/filler.rs:76:18
stack backtrace:
   0: rust_begin_unwind
             at /rustc/90743e7298aca107ddaa0c202a4d3604e29bfeb6/library/std/src/panicking.rs:575:5
   1: core::panicking::panic_fmt
             at /rustc/90743e7298aca107ddaa0c202a4d3604e29bfeb6/library/core/src/panicking.rs:65:14
   2: core::panicking::panic
             at /rustc/90743e7298aca107ddaa0c202a4d3604e29bfeb6/library/core/src/panicking.rs:115:5
   3: core::option::Option<T>::unwrap
             at /rustc/90743e7298aca107ddaa0c202a4d3604e29bfeb6/library/core/src/option.rs:778:21
   4: <xwords::fill::filler::Filler as xwords::fill::Fill>::fill
             at ./src/fill/filler.rs:65:27
   5: xwords::main
             at ./src/bin/xwords.rs:66:18
   6: core::ops::function::FnOnce::call_once
             at /rustc/90743e7298aca107ddaa0c202a4d3604e29bfeb6/library/core/src/ops/function.rs:251:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
>

Environment

stable-x86_64-unknown-linux-gnu (default)
rustc 1.66.1 (90743e729 2023-01-10)

Otherwise any puzzle with words outside of the word list will repeatedly warn about viability

Current strategy involves a lot of lock contention i believe