/sci/ - Science & Math

[Anonymous No.2187052]

Would /sci/ be interested in a programming puzzle? I have one that I think is great. It's just for fun - not a sneaky attempt to get my homework done or anything.

Game starts with a even length of sequence of numbers. Player 1 picks to remove a number from either beginning or end. This number is added to his score. Then Player 2 picks one from remaining numbers. This is continued until all numbers are taken. Player with higher score wins.

Make a program to play as Player 1 as well as possible.

Skeleton of player class would be something like this in java. Test program would not send incorrect parameters or out of order method calls.

public class GamePlayer() {
public static final int MOVE_BEGINNING = 1;
public static final int MOVE_END = 2;

public GamePlayer(int[] sequence) {
...
}

public int getFirstMove() {
...
}

public int getMove(int asResponseToMove) {
...
}

}

[Anonymous No.2187103]

No one is interested?

[Anonymous No.2187116]

This can be solved in a straightforward way using dynamic programming.

[Anonymous No.2187129]

>>2187116
What do you mean? Why dynamic programming?

[Anonymous No.2187130]

>hurr durr do my homework for me

[Anonymous No.2187124]

>not a sneaky attempt to get my homework done or anything
>but i've specified a language and method prototypes for implementing an algorithm for no fucking reason

[Anonymous No.2187135]

>>2187124
I thought I just post a puzzle. Don't really care what language or just a pseudocode.

I would think it is clever enough that it would NEVER be given as homework in any school. (also some other reasons)

[Anonymous No.2187141]

>>2187135
It is not clever. If you think it is, well... ask for the remedial class.

[Krakengineer !!5XY+x7grkpt No.2187150]

>>2187116
This is actually a problem Waterloo gave out in their national competition a while ago. The thing is you don't want to just take the highest of the two cards, you want to make sure your opponent can't pick up a high card you uncover. Also since you have no control over your opponent you can't make direct predictions of how your actions will ultimately play out.

I solved it by sticking every possible scenario into a decision tree, and going down the branche with the the highest possibility of winning.

[Anonymous No.2187167]

>>2187150
This would be the obvious solution and would be wrong. It would fail if given large sequences as you'd just run out of time.

It was a problem from Programming Olympiade for schools (don't know what these are called in english) I attended years ago. The solution was so cool, that I just love this puzzle.

[Anonymous No.2187171]

>>2187141
If you don't think it is clever, then please post a description of algorithm within 10 minutes.

[Anonymous No.2187179]

>>2187150
That's a surprisingly easy problem for a national competition then.

[Anonymous No.2187183]

>>2187171
See >>2187116 (samefag).

[Anonymous No.2187200]

>>2187183
You mean trying out all possible scenarios? This would be a limited solution as it would just take forever with large sequences.

[Anonymous No.2187205]

>>2187200
I suggest you go read the wikipedia article on dynamic programming.

[Anonymous No.2187207]

>>2187179
Post your solution then. It would have to work within reasonable time for large sequences.

[Anonymous No.2187210]

>>2187205
post your solution or admit defeat.

[Anonymous No.2187215]

>>2187207
As I said twice already, see >>2187116. O(n^2) to find out the best strategy for each subsequence.

[Anonymous No.2187219]

>>2187210
I have posted the solution. Any more detail and it might just as well be java code.

[Anonymous No.2187237]

>>2187219
There is O(n) solution. Some things about your responses make me think you are note even able to provide O(n^2) solution.

[Anonymous No.2187248]

>>2187237
Sigh.

let "best strategy" for a given sequence be the sequence such that the worst case score difference is maximized.

i = (1 if sequence.length is odd, 2 if sequence.length is even)
for all subsequences of length i, find the trivial best strategy if you have to make the first move and store the result
i += 2
while(i <= sequence.length):
for all subsequences of length i:
find the best strategy for the subsequence by looking at all 4 pairs of (your move, enemy move) and looking up the best result attainable for the remaining subsequence of length i-2. store the result.
i += 2

There, O(n^2). O(n) does require a little more thought though, and may be interesting.

[Anonymous No.2187265]

> a even length of sequence of numbers
beg your pardon?

[Anonymous No.2187274]

>>2187265
Must be my english.

I meant the sequence length is even number. Sequences of 4,8,12,6000 nubers are ok 3,9,34561 are not ok.

[Anonymous No.2187276]

its just a very simple algorithm and OP is a troll?

[Anonymous No.2187285]

>>2187248
It was confusing and hard to follow and probably not even O(n^2). Could you please write the algorithm in language of your choosing or pseudocode and I show you why you were wrong.

Also. All sequences have even number of elements.

[Anonymous No.2187293]

>>2187285
>implying that's not pseudocode

[Anonymous No.2187297]

doesnt this work by taking the highest element left each time?

[Anonymous No.2187307]

>>2187297
No. Let the sequence be [2, 100, 0, 1].

[Anonymous No.2187310]

>>2187276
I am not a troll. It might not have turned out as I wanted. I pictured it like this.
1. I post a cool (solvable) puzzle
2. People try to solve it until best solution is achieved
3. Everybody has their day enriched a bit

Troll would post
>What is the next number in sequence 1, 7, 14, 15, 18, 21

[Anonymous No.2187313]

>>2187307
sorry, i misread the problem.

>iamretarded.jpg

[Anonymous No.2187321]

>>2187293
could you write it in java, c, python, whatever

I admit my english is bad and this might be the case of me not following but I think if you try that you will realize your error.

[Anonymous No.2187328]

>>2187297
>greedy algorithm
>actually solves anything
>my face

[Anonymous No.2187336]

>>2187321
I could, but you can do your own homework.

[Anonymous No.2187370]

>>2187336
Okay. Looks like thread failed. I'll go and have a cigarette and if no-one tells me otherwise (i.e they want to try solving) I'll post the solution and explanation just to prove it is not homework.

Dear Dynamic Programming guy. If I will post my O(n) solution would you be satisfied it is not a homework and post Java,C or Python code of your algorithm?

[Anonymous No.2187384]

>>2187370
Oh, sorry, I meant "homework" in the metaphorical sense there, as in "you should be able to fill in the gaps and I'm too lazy to do it for you". But I guess I could, because I'd like to see the O(n) solution :)

[Anonymous No.2187408]

go down one side, until it becomes mathematical better to go down the other side... if a side becomes worse go back down other side unless it becomes worse-- massive amounts of potential backtracking only in rare cases.

[Anonymous No.2187412]

Ok, here it is. Note I just typed it in without testing. I won't be embarrassed if there is a mistake there. I also didn't include the simple code to wait opponent possibly making a mistake in optimal-strategy-tie-games as I wanted the simplicity to shine.

I liked this puzzle because (at least 15 years ago) the students of every national team were drilled to do recursive solutions in their sleep and this was nice puzzle to reward creativity.

Waiting for you to post your algorithm in C, python, java, javascript, ruby whatever.

[Anonymous No.2187448]

>>2187412
Here it is: http://pastebin.com/0LGk9ihh .

[Anonymous No.2187503]

>>2187448
Ok. I can't understand what it is. I executed it

$ python 1.py
2147
[1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Don't really know what it means.

[Anonymous No.2187509]

>>2187503
It says that for this particular sequence, the best attainable score difference if both players play perfect is 2147, which happens if you first play left (1), then your opponent plays right (2), then you play right (2), etc.

And if you don't understand how the code works, I really suggest you go read the wikipedia article on dynamic programming.

[Anonymous No.2187602]

>>2187509
numbers = [ 34, 34, 23, 56]
results in
56
[2, 1, 1, 1]

Ok - so 56 is wrong. Algorithm does not work for sequence size 4. Not a big deal. We are not nitpickers.

So your algorithm calculates the first move and recursively turns back for a sub sequence.

Let's just try it in old dumb way - I'll just run your program.
n=12
operations = 36*25*16*9*4=518400

That is FAR FROM O(n^2). It is rather something O(2^(n+-something))

You just got schooled hard and you suggest I should go back to school.

[Anonymous No.2187621]

>>2187602
>numbers = [ 34, 34, 23, 56] results in 56 [2, 1, 1, 1]
Ah right, lines 9 and 12 are wrong. Replace them by
bestscores[(i, i + 1)] = numbers[i] - numbers[i + 1]
bestscores[(i, i + 1)] = numbers[i + 1] - numbers[i]

>operations = 36*25*16*9*4=518400
Er, no. What makes you think that? It does a constant amount of work for each subsequence, of which there are O(n^2).

[Anonymous No.2187638]

>>2187621
yep - had something wrong there

[Anonymous No.2187644]

>>2187621
that didn't make it better
numbers = [ 34, 32, 22, 1, 1, 1 ]
results in
23
[1, 1, 1, 2, 1, 1]

[Anonymous No.2187656]

>>2187644
Which is wrong how? Do you see a better strategy?

[Anonymous No.2187678]

Ok, I've taken an Algorithms class before and this is a simple dynamic programming problem.

[Anonymous No.2187689]

>>2187656
Sorry - wrong copypaste

numbers = [ 1,1,1,1,1,1999,1000,1 ]
999
[1, 2, 1, 2, 2, 2, 1, 1]

Clearly the correct solution is to select RIGHT

[Anonymous No.2187695]

>>2187678
nope
see >>2187412

[Anonymous No.2187699]

>>2187689
Oh? Does that lead to a higher score difference?

[Anonymous No.2187725]

>>2187699
fuck

you're smart I'm dumb. you were right.