Binary search passable with other forms of search

[tomerarnon]

One student submitted an algorithm which proceeded as follows:

julia> binarysearch([1, 2, 3, 4, 5, 6, 7], 1)
book = [1, 2, 3, 4, 5, 6, 7]
book = [1, 2, 3, 4, 5, 6]
book = [1, 2, 3, 4, 5]
book = [1, 2, 3, 4]
book = [1, 2, 3]
book = [1, 2]
book = [1]
1:1

The reason was that their middle index calculation was incorrect, but the point is all the tests actually passed, so this went unnoticed. Is there a way to only allow a proper binary search to pass?

[cmcaine]

We don't necessarily want the tests to be comprehensive every time, so long as mentors are likely to spot the issue when reviewing the code it's okay. I don't have a good intuition for whether this is something that mentors are likely to spot or not.

If we could encourage the students to always write some of their own tests that would actually be pretty good, imo, but it goes a bit more towards learning how to program versus exercism's stated mission objective of teaching familiarity or fluency with a language.

https://exercism.io/mentoring-faqs

FWIW, I am fine with us teaching programming and think that it's realistically what we're doing a lot of the time anyway.

[tomerarnon]

Fair enough, I definitely agree with that philosophy. I wonder if a nudge or suggestion to print-debug could be helpful though in some cases?

[cmcaine]

Yeah, I tried to put a nudge like that in the description of robot-name, but I think I wasn't explicit enough.

We could introduce the idea earlier on in the core track and explicitly tell students to write and submit some of their own tests? I don't know if that's going too far or not?

[SaschaMann]

We could add something like "it's a good idea to print intermediate results to verify that your algorithm works as intended"?

[cmcaine]

Shall we try to resolve this? Here are three options:

1. Do nothing and trust mentors to notice
2. Add a test that will take too long if your algorithm is bad (we do this on e.g. pythagorean-triangle) / a test with an array with a custom getindex that validates that you only retrieve the correct indices
3. Add a hint to the instructions

My slight preference is for 1, but I don't care much either way.

[SaschaMann]

I don't have a preference. I'm happy to accept PRs that add 2/3 but I'm happy with 1 too.

[tomerarnon]

2 is quite an interesting idea! Something like that hadn't occurred to me. It might be simple to make a type that does this, but I think overloading getindex would break in case the student passes views through the iterations (something I suggested doing). Presumably we could also overload view to return an array (defeating the purpose, but oh well) to avoid this. Here's a sketch:

using MacroTools

struct MiddleIndexChecker{V <: AbstractVector}
    v::V
end

MacroTools.@forward MiddleIndexChecker.v  Base.setindex!, Base.length, Base.IteratorSize, Base.size, Base.iterate, Base.firstindex, Base.lastindex, Base.keys, Base.pairs  # etc... extend as many method as needed/reasonable

function Base.getindex(m::MiddleIndexChecker, i...)
    N = length(m)÷2
    if iseven(length(m))  # if even, it doesn't matter whether their method picks right or left (I think)
        @assert abs(N - i) <= 1 "not binary search. The middle index is $N ($(N+1) is fine too). Got index $i"
    else
        @assert N+1 == i "not binary search. The middle index is $N. Got index $i"
    end
    m.v[i...]
end

# Not at all a view!
function Base.view(m::MiddleIndexChecker, i...)
    MiddleIndexChecker(m.v[i...])
end

[cmcaine]

Another simpler option might be to provide ones(9) and check that we get index 5 and not anything else?

---

I think your code will fail if the student does arr[5:10] (a bad solution, but probably not something that should fail the tests?) rather than view(arr, 5:10), so it would need a little bit of work, probably?

We'd probably want to provide our own definition of @forward, too (or just do that bit with a for loop and @eval)

Otherwise looks okay :)

If we wanted to check deeper without requiring the use of views, then we can have the constructor take a vector of expected indices or we could fill the vector with mostly missing and make it an error to access any index whose value is missing.

[tomerarnon]

Another simpler option might be to provide ones(9) and check that we get index 5 and not anything else?

I quite like this idea! Simple.

[cmcaine]

It was a good idea :) A reason not to do it:

For simplification, you can assume that all elements of the list to be searched are unique. Feel free to implement a solution that works on lists with non-unique elements as a bonus task.

We could still put the test in, but we'd need to explain in the tests file or instructions or something what we're doing.