# Programming Challenge: Two Wizards algorithm challenge

I'm running out of ideas, if you have any, please make your own programming challenge.

This challenge is about designing algorithm to solve this problem.

Let's have game field of size x, y (like in chess). There are two wizards, that are standing at `[ 0, 0 ]`

and are teleporting themselves using spells. The goal is to *not* be the one who teleports them outside of the map. Each spell teleports wizard by at least +1 tile. Given map size and collection of spells, who wins (they do not make any mistakes)?

Here are few examples:

**Example 1**

`x:4,y:5`

Spells: `{ 0, 2 }`

Output: `false`

Description: Wizard A starts, teleporting both of them to 0, 2. Wizard B teleports them to 0, 4. Wizard A has to teleport them to 0,6, which overflows from the map, so he loses the game. Because starting wizard (wizard A) loses, output is `false`

.

**Example 2**

`x:4,y:4`

Spells: `{ 1,1 }`

Output: `true`

**Example 3**

`x:4,y:5`

Spells: `{ 1,1 },{ 3,2 },{ 1,4 },{ 0,2 },{ 6,5 },{ 3,1 }`

Output: `true`

**Example 4**

`x:400,y:400`

Spells: `{9,2},{15,1},{1,4},{7,20},{3,100},{6,4},{9,0},{7,0},{8,3},{8,44}`

Ouput: `true`

Good luck! I'll comment here my solution in about a day.

Note: This challenge comes from fiks, programming competition by Czech college ČVUT (CTU).

Why are there two wizards if they both move together? Can any spell be used at any time by any player (given it's their turn)?

Because it's used to say who won. You can just count turns and say if it's even/odd to say who won and it'll work the same. But the version with two wizards might make it feel more natural and easier to design the algorithm.

Yes, there are no limits to spell usage, you can use whatever you want.

If I'm understanding this correctly you basically just create a search tree with each level being all the possible spells - excluding the spells that would make you lose the game. First wizard to run out of options loses.

And although that is definitely doable, it's not particularly intelligent, interesting or creative, which is why I'm so confused at the OP. Are you sure you're not missing any details maybe?

The only "cool" gimmick I can find with this is that you can insta-win by moving the wizards to the edge of the board - and as long as any other spell will result in crossing the border, your opponent will lose. But that does not lend itself to generalization or anything like that. EDIT: I mean, it's easier to write for the general case than to use this gimmick as part of your solving...

Also it's really complicated to say wizards make no "mistakes". If you're trying to write a generic algorithm with any number of spells/board sizes you're basically asking people to create a relatively complex AI or an extremely brute-force one, which again, is definitely doable but not really interesting as a challenge? I don't get it.

I'm not asking anyone to make AI, this can be done in an elegant way without too much brute force. I like this one because there is very nice solution to problem, that might look very complex at first.

The optimal solution has time complexity

`O(x*y*spellsCount)`

.I'm not sure how would your search tree work - would you mind adding small example?

Do you know there is an elegant solution to this? If you know why are you asking people for an answer? I'm so confused by this post.

I'll be the first to admit that I might be missing the elegant solution but I don't see it.

EDIT ah this is a challenge for the community, not one you're trying to solve! When I read "I'm running out of ideas" I thought you wanted help solving it!

This is programming challenge, the point is to share interesting problems and interesting solutions to them. I have the optimal solution which I'll comment here tomorrow.

Your search tree might be the elegant solution, I'll tell you if you write how it works.

Btw, I always liked to draw simmilar problems into some kind of tree. For example the factorial tree. It makes you think how to solve the easiest problem and then you can solve the harder problem with solution of the previous problem.

Edit: If you are confused by the first paragraph, I simply enjoy these challenges but I made like 3 last ones. And if someone else made them, I could participate in them.

I think you've missed my edit: I was confused because I thought you wanted help solving this challenge, I didn't get that this was a challenge for the community.

My search would basically be to construct all possible moves from [0,0], alternating the players, with a recursive function. That would seem to indicate that either player could win/lose depending on the moves that are made and there doesn't seem to be a concept of an "optimal move" to discard "mistakes" (except outright losing the game, which could always be discarded).

In that sense, this solution doesn't really seem elegant. Am I missing something obvious here?

When I got this task, I created exactly this algorithm, but I couldn't make it any further.

The key is to do it backwards. Think backwards, step by step. Draw it on a piece of paper, this coud help you to optimize the solution.

SolutionWhen does wizard win? When the other wizard have to make move outside of the map. So if we take example 1:

The only position when wizard have to make move that makes him loose are marked as

`1`

:If we want to win, we have to make the other wizard go to position marked with

`1`

. How do we do it? We have to start our turn on tiles marked as`2`

.And we continue with this.

Now, position

`[0][0]`

has assigned number 1. We see, that number 1 is loosing position, so we output`false`

.Here's code in dart:

Edit: When I look at the code, there is one part that could be better. Part 2 (in code commented "Else if every next move goes into tile labeled 1" should be changed to "Else if

anynext move goes into tile labeled 1". I'll change the code and the comment tomorrow, but it shouldn't do too much difference.Edit: Done

Edit: Added syntax highlighting

This is such an unintuitive approach for me. I've been writing a recursive takeTurn() function that simulates the state of the game from beginning to end, making a spell choice each time, repositioning the wizards after every teleport, and returning who the winner is when they go out of bounds.

You've just bypassed that whole process using a deterministic winner-identifying algorithm. I would've never jumped to that solution and honestly I'm having trouble wrapping my head around how it works. Nowhere in your code is a single spell selected or turn simulated. I'm agog.

I highly recommend taking a look at the following problem:

Imagine that you have a pile of sticks of arbitrary size. You and your opponent each take turns removing between 1 and 3 sticks from the pile. The person who takes the last stick loses. What is the winning strategy?

If you want to try solving the problem first, stop reading now and come back later. Otherwise, here's how you solve it:

We know for certain that in order to win, we need to take the turn that allows us to leave exactly 1 stick behind. This means that if there are 2-4 sticks on our turn, we win. In order to force that to happen, we need to have left exactly 5 sticks behind in our previous turn. Notice that this changes our winning condition from leaving 1 stick behind to leaving 5 sticks behind. Following this same logic, this means that if there are 6-8 sticks remaining on our turn, we win, so in the turn prior we need to have left 9 sticks behind.

Continuing this pattern, you should notice that the series of "sticks remaining after our turn ends" is {1, 5, 9, 13, 17, ..., 4k + 1} for some arbitrary integer k. In other words, each correct remaining count is a multiple of 4 plus 1.

Why, though? What's so special about the number 4? It's actually quite simple: Your smallest option is 1 and your largest option is 3. Thus, no matter what your opponent chooses, you can choose its polar opposite and achieve a total sum of 4.

Since we can force a sum of 4 on any turn, we can force the winning 4k + 1 series.

Note that you can generalize this solution for any maximum and minimum turn selections, so long as you can enforce a consistent guaranteed sum.

The two wizards problem is admittedly more complicated, but you can think of this as a special case of the two wizards problem where you have a board {n, 1} and moves {1, 0}, {2, 0}, {3, 0}.

Edit: An important note is that you lose if you're unlucky enough to have 4k + 1 sticks left at the start of your own turn. Thus, you have a 75% chance of starting with the winning condition, and a 25% chance for the losing condition.

Lots to chew on here, thanks for the thoughtful post. When I have some time I'll go through the exercise.

I've put together a JS implementation which includes your edit (changing part 2 from "every next move" to "any next move"). My results for examples 1-3 are consistent with your expected output, but I'm getting

`true`

for example 4 and I'm not sure if it's a problem with my code or your scenario. Mind taking a look?Note that I'm using

`false`

,`true`

, and`undefined`

where your implementation used`1`

,`2`

, and`0`

respectively.Hm, you're right. I'll change it in the post, the result is

`true`

for me as well. Thank youThis is a great approach. Determine losing positions and back-propagate winning and losing positions from there until you reach the origin point.

The only point I think needs clarifying is what happens if none of your three conditions hold? That is, what if different next moves land on different labeled tiles? If this never occurs, it's not immediately intuitive to me as to why.

I have actually mistake in the 2nd condition in my code, it should be if

any, notevery, I'll fix it tomorrow.I don't think it can happen, but maybe I'm wrong, I'd be grateful if you find input where my code doesn't work. Tomorrow I'll try to prove if it can/cannot happen, I'm really curious about it.

I agree with balooga... I never would have thought to do this by anything other than brute force. Thanks for posting your solution!

You say the wizards make no mistakes but don't state what their goals are. Is Wizard A actively trying to sabotage Wizard B? Or should we assume both are playing to prolong the game for as many turns as possible?

They are playing to win, it doesn't matter when. In each game, one of the wizards has sequence(s) of turns, if he plays this sequence of turns, he wins. You have to find the sequence(s) of turns to say who win.

Am I misunderstanding this? wouldn't the first wizard always win. Just teleport to the top right corner of the grid then the next move will always take them out.

They have defined set of moves. In first example, wizards have only one spell which moves them 2 tiles down.

In 4th example, they can choose any of available spells.

One of the things that wasn't obvious to me on the first read was that the size of the board and the spells available are pre-defined; as a wizard, you cannot change the spells to set the board.

Example: the board size is 5 x 5, and you have two spells: {0,1} and {1,0}. The wizards play perfectly, so who wins? This is one you can figure out on paper.

Once you've made a programmatic solution to the above, you can make a solution that's generic; input any field size, and then any set of spells, and you should immediately know who wins.

Is there purely a math solution to this? I have a feeling it wouldn't be too difficult if the the spells just move in one x or y direction - but am not sure about diagonal moves like (1,2).

There is almost certainly a functional way to describe the solution, but it seems easier to find a recursive algorithm. The algorithm for determining which wizard wins is not particularly complex. For small values, it can be done with pencil and paper, but it gets onerous pretty quickly when the number of spells or the size of the board increases.