Thank you for answering me. I will try to implement it, but I haven't programmed in a while, so it will take some time and head bumping on how I get it into the machine.

I guessed (10,10) once at the 4th move and once at the 5th move. That seems valid to me. The solution would be like exhaustively creating these paths while pruning the resulting tree by remembering what locations I already visited at which steps in a data structure.

In my above example is actually an error in my 5th guess: I let him walk (3,3) -> (1,1) -> (2,2) -> (3,3) -> (1,1) but at the 3rd move he would end up at (6,6) which I already guessed as wrong for the 3rd move. The correct algorithm would result into this list and go like this:

[(1,1),(3,3),(6,6),(10,10),(11,11)]

Evil Genius 1st move: (1,1)                                                     => (1,1)
EG 2nd move: (2,2) -> (1,1)                                                     => (3,3)
EG 3rd:      (2,2) -> (3,3) -> (1,1)                                            => (6,6)
EG 4th:      (2,2) -> (3,3) -> (2,2) -> (3,3)                                   => (10,10)
EG 5th:      (2,2) -> (2,2) -> (2,2) !(sum = (6,6) already guessed)
             (3,3) -> (1,1) -> (2,2) !(sum = (6,6) already guessed)
             (3,3) -> (1,1) -> (3,3) -> (1,1) -> (3,3)                          => (11,11)
EG 6th:      (3,3) -> (2,2) -> (3,3) -> (2,2) !(sum = (10,10) already guessed)
paths exhausted

One of these guesses has to be correct i.e.
Either he went to (1,1) on his first move
or (3,3) on his second move
or (6,6,) on his third move
or (10,10) on his fourth move
or (11,11) on his fifth move.

There is no path you can go for which none of these statements is true.
At least thats how I understood the problem.

Uhm, I'm not sure if it's the right word to use "step" because it seems you are still confusing the "step" with the "resulting location on the board" - remember, your guess isn't "Was your x_th step = something" but rather "Is the piece currently at (location)".

But yes the above walk through example seems to be on the right track if that's what you mean - you are trying to systematically rule out which move patterns may or may not have been used.

And as you correctly identified previously, if you do this naively (combinatorially) you will need a very large number of guesses >>> 500, so you need to be smarter.

Also, as your above example shows, it may actually be the case that you decide to guess each "step" (again - better to use the word location) more than once. For example, your own example leads to you guessing the location (10,10) more than once as part of your strategy.

So I can guess each step only once, but can guess 500 steps in total?
e.g. for [(1,1),(2,2),(3,3)]
Was your first step (1,1)?
No
Was your second step (2,2) + (1,1) = (3,3,)?
No
Was your 3rd step (2,2) + (3,3) + (1,1) = (6,6)?
No
Was your 4th step (2,2) + (3,3) + (2,2) + (3,3) = (10,10)?
No => He didn't start with (2,2) or (1,1)
Was your 5th step (3,3) + (1,1) + (2,2) + (3,3) + (1,1) = (10,10)?
...\

and so on, search the space efficiently enough to make it in 500 steps for 8 moves\

Hi @suuujuuus - first of all, thank you for your interest in this Beta kata.

Most of what you said is correct - except for part b) : I think where you're confused (or maybe my description isn't clear enough) is that you don't have to deduce the full "move pattern" that the genius is using -- all you have to guess/find is one location at the right time/step.

So you're not trying to guess e.g. that the genius is performing the move pattern [ (+1,-1), (+3,-99), (-5,-60) ] repeatedly - you are trying to "catch" the piece at one single correct location.

That's why your solution list (of length 500) is therefore 500 2-tuples; each one is a location on the board, not a move pattern.

Hence, to be clear, when you say:

But how do I figure out if a single guess is correct, so I can build on that?

you don't need to worry, as the kata will compare your solution list to the actual trajectory of each game, and as long as one single location guess is correct, you will win.

After each of the supervillain's moves, you must guess the location of where you think the chess piece currently is on the chessboard. If your guess correctly matches the current location of the piece, you win.

You are guessing the current location of the piece after each time it was moved, not the moveset that was used.

And the move of the piece will follow the unknow moveset.

So my understanding of the problem is:
a) I get a list of moves
b) I have to guess a random pattern of moves, which can't have the same move twice

But how do I figure out if a single guess is correct, so I can build on that?

If we take the example:
known inputs:
moves = [(-1, 1), (1, 0), (0, -1), (0, 1), (-1, 0), (1, -1), (-1, -1), (1, 1)]

unknown to you:
actual_length_of_move_pattern = 2
actual_move_pattern_chosen = [(1,0),(0,-1)]
actual_moves = [(0,0),(1,0),(1,-1),(2,-1),(2,-2)...]

I'll start my first guess: "Is your first move to (1,1)?"
And he answers: "no"
2nd guess: "Is it (1,0)?"
Evil Genius: "yes"
3rd guess: "Is your second move to (2,-1)?"
EG: "no"
...
until 500 guesses

How do I get that feedback?
If there is no feedback, the only way to "guess" the moveset - I currently see - is to caluculate all possible movesets which would be worst case 322560 guesses with a moveset of 8 moves. I need some other information than just the list of moves.

what the hell

"-" <* s

( or, equivalently, s *> "-" )

https://projecteuler.net/problem=92

join (***) length == (***) length length

length *** length == \ (xs,ys) -> (length xs,length ys)

join functions as the W-combinator, W f x = f x x ( it's used here in the (->) r Monad ( Reader? ), which I think of as the Function Monad ). I don't even know how (***) works exactly; it's also used in some specific Arrow I guess ( well, of course it is ). It just works is all I know.

I'll readily admit it adds very little but confusion. But it means I don't have to have length twice ( at the cost of just another function, which I have to import to boot. I said it doesn't add much ); it defines that length is applied to both tuple elements.

I don't really get what happens at

join (***) length ([...], [...])

join just strips a Monad m => m (m a)) of its first monad container, the (***) -function takes two arrows and joins them via a tuple/the (,) function. All in all that should be the same as

(***) length length ([...], [...])

But how it works is a miracle for me.

join :: Monad m => m (m a) -> m a
(***) :: Arrow a =>  a b c -> a d e -> a (b,d) (c,e)
length :: Foldable t => t a -> Int
(***) length :: (Foldable t, Arrow a) => a d e -> a (t b, d) (Int, e)
--so join somehow makes (***) into a (Arrow a => a b c -> a (b,b) (c,c))-type