Haha, seems correct 🙈

When I run your benchmark with a 10M random file, I get 307.73ms, 37.92ms and 74.46ms, which is close to what I had. However, when I run it without --release, I get 7.26s, 319.00ms, 206.36ms, which is similar to your result. So maybe you were missing the compiler optimizations?

fn main() {
    let string = std::fs::read_to_string("string.txt").unwrap();
    let time_before = std::time::Instant::now();
    // Benchmarked block
    {
        let answer = arrow_search(&string);
        println!("Answer: {}", answer);
    }
    println!("Elapsed time: {:.2?}", time_before.elapsed());
}

I wasn't actually very experienced at this stuff, so I used plain std::time and manually ran the code multiple times to check the variance. Benchmarking println!("Answer: {}", answer); looks very weird, but I probably didn't know about black_box and needed to make sure that the code actually did the work.

I don't remember why I saved a fixed generated string to disk. I don't have the code that generated it, but I still have string.txt. It looks like it was the same b".-=<>".choose(&mut rng), but 10 MB in size rather than 1 KiB.

On my current machine, here are the timings from this bench:

• My regex solution: 29.35s
• My table solution: 347ms
• Your solution: 223ms

The speedup is still 84x, even though I'm on a different machine now

In my benchmark I get:

your regex solution: 20,933.28 ns/iter
your table solution: 2,174.62  ns/iter
my solution:         1,590.12  ns/iter

Here I see a 10x boost instead of a 90x boost.
So may I know how your benchmark is organized?
Mine is as follows:

#![feature(test)]

extern crate test;
use core::array;
use finding_arrows_in_a_string::arrow_search;
use rand::seq::SliceRandom;
use rand_pcg::Pcg64Mcg;
use test::{black_box, Bencher};

#[bench]
fn bench(bencher: &mut Bencher) {
    let mut rng = Pcg64Mcg::new(0xcafe_f00d_d15e_a5e5);
    let string: [_; 1024] = array::from_fn(|_| *b".-=<>".choose(&mut rng).unwrap());
    let string = core::str::from_utf8(&string).unwrap();
    bencher.iter(|| arrow_search(black_box(string)));
}

Yep, I agree that it should be (u32, u32)

Finally i found deficiency of my code.

the empty spaces surrounded by moshpit was not always marked as part of moshpit.

The following group of tests could filter it out:

It(all_moshpit_joints_possible)
    {
      const std::vector<std::pair<size_t, size_t>> expected = {{3,4}};
      int j=0;
      for(int i=0;i<8;i++){
        std::vector<std::string> dance_floor = {
            "z??zz",
            "?  ?z",
            "?  ?z",
            "z??z "
        };
        for(auto& row:dance_floor){
          for(auto& col: row){
            if(col == '?'){
              if(i==j++){
                col=' ';
              }
              else{
                col = 'z';
              }
            }
          }
        }
        const auto actual = best_place(dance_floor);
        AssertThat(actual, IsOneOf(expected));
        }
    }

Wow, discussion. :)

1. If C++ is not known and /or solved there is no point to search for deficiency in the test cases any way.
2. Forfeiting difficulties is not how real "Samurai" shall move his path, thus agree with Hobovsky.
3. Already stated the language required.
4. Will do my best to find the problem, if i would have enough time and self motivation resources.
5. I do not know what was the issue, and thus could not provide any specific portion of the solution and or relevant test case.

"hob has to learn C++" is a secondary matter. in the first place, i have to know it's C++ because if I don't know this, which language should I learn? :D

I believe both of those doesn't know how "Show solution" button work. It can only show the solution of the user in the selected language (next to the name of the kata). So, hobovsky can't read the solution of the OP using the button because he hasn't done it in C++. It would make him has to learn C++ first, and then solving the kata. Meanwhile, the OP can just send their solution here with the spoiler flag (so that other people that haven't solved the kata can't read it) so that he can just start researching on the part of code that doesn't meet the criteria of the kata. The latter would be a faster way to get this kata fixed.

Oh come on, i will not forfeit a kata only to find a piece of information which OP can already provide with 0 effort. If I forfeited every kata i want to fix, i would have nothing left to solve.

To see your solution, I have to complete tha kata in the same language as you. And since I do not know your language... I would have to complete the kata in three languages to see your solution. And I know only one of them. So I have to solve the kata in two languages which I do not even know to see your solution. I wold have to use a lot of google and a lot of reading to solve it. The kata is 5 kyu, which means not easy. I would have to solve a non-trivial kata in three languages, including two languages which I do not know.

But the "unlock solutions" button exists. The whole paragraph is incorrect. Although I agree that the OP could be nicer and at least mention the language from the start.

For a years of wars i noticed the you are the only person who somehow reacted on my comments.

My solution is in C++ (Clang8 C++17).

I believe i can not publish it here. So looking for you in c++ branch.

And yes, i was much more lasy in this case.

Dear Hobovsky, Seems as before you had read my comment a bit too literally.

Oh this is possible, I read so many comments I can't keep track anymore which are serious and which are not :)

Actually, if you were interested to identify the language of tests which pass or not pass you might simply pass the kata, and thereafter look at my only solution.

This, unfortunately, does not work this way. To see your solution, I have to complete tha kata in the same language as you. And since I do not know your language... I would have to complete the kata in three languages to see your solution. And I know only one of them. So I have to solve the kata in two languages which I do not even know to see your solution. I wold have to use a lot of google and a lot of reading to solve it. The kata is 5 kyu, which means not easy. I would have to solve a non-trivial kata in three languages, including two languages which I do not know. On your end, however, all it takes is to paste your solution in code blocks, put a spoiler flag, and voila! done. Knowing your language, and using your solution for reference, I can start searching for the bug and fix it.

You marked the post as ISSUE. Issues mean kata bugs, and bugs need to be fixed. I want to fix the bug. But I cannot fix it, because to even start fixing it I need to solve a not easy kata in three languages (two of which I do not know). If you want the kata to be fixed, help me to fix it. If you do not want the kata to be fixed, do not use the ISSUE label.

Dear Hobovsky,
Seems as before you had read my comment a bit too literally.

Indeed you are right - my comment did not help the author to make the kata better. ( And for that i already stated it is useless and sorry for that )
Actually, if you were interested to identify the language of tests which pass or not pass you might simply pass the kata, and thereafter look at my only solution.
Start it couple of times or even cycle it for hundred times and get the conditions at which it would fail.

Unfortunately i just run my solution once, it pass all the tests, i executed it second time it fail some tests, i was not wondered what was the problem and run the submission for the third time and it pass all the tests again.

So we know that random test cases coud generate failing tests. Either because some error in authors own solution or in mine. Mine was performed without due care, thus i assume that there is error in it and thus i think that test cases does not cover the solution effectively.

I believe simple two colums 1000 rows 'moshpit' scene which will end op with ' ','xx',' ' would trigger failure for my solution. But i believe it is not what triger referred error on my submission.

I.e. i was as laysy as youself and did not performed search by myself, but stated, that isssue exists. And might be someone more motivated would find it out. Otherwise if i knew the answers on your questions i would definitely propose what test must be included...

Thank you for your bug report, now I know literally nothing what would help me to fix the tests:

• I do not know the language of tests which pass (or fail) but should not,
• I do not know what is your solution, or any other solution which passes (or fails) tests but should not,
• I do not know what is the input of the test which passes (or fails) but should not.

Make your post useful! Share some details about the error so I can fix it! :D