Ccc 2012
Author |
Message |
Yves
|
Posted: Fri Mar 02, 2012 6:52 pm Post subject: Re: Ccc 2012 |
|
|
bl0ckeduser @ Fri Mar 02, 2012 6:42 pm wrote: Can anyone explain how the grade is calculated ?
Someone seems to have mentionned "full 75", but I only see 27 test files on the Robart website.
BTW my unoptimal S1, S2, S5 C solutions are here:
http://sites.google.com/site/bl0ckeduserssoftware/ccc-2012-partial-sols.zip
(I messed up S3, didn't know what to do for S4)
For S1 to S4, there are 5 cases each with 3 points awarded per case. Partial marks are not awarded for partially correct cases.
For S5, there are 7 cases. The first four are worth 2 each, the second-to-last worth 1, and the remaining two 3 each. |
|
|
|
|
|
Sponsor Sponsor
|
|
|
ihsh
|
Posted: Fri Mar 02, 2012 10:27 pm Post subject: Re: Ccc 2012 |
|
|
I finally coded a working solution for S4, which involves a DFS, and states represented like this:
code: |
1344 //coin '1' is in location 1, coin '2' is in location 3, coin '3' is in location 4, and coin '4' is in location 4
|
And since it's a brute-force DFS, I had to limit the the number of steps to 50 for it to run in time... |
|
|
|
|
|
danc
|
Posted: Fri Mar 02, 2012 10:34 pm Post subject: RE:Ccc 2012 |
|
|
But why not just use BFS with the same state? BFS, I believe, would run much faster and be not much more difficult to code?
But I probably don't know best. |
|
|
|
|
|
ihsh
|
Posted: Fri Mar 02, 2012 10:51 pm Post subject: Re: RE:Ccc 2012 |
|
|
danc @ Fri Mar 02, 2012 10:34 pm wrote: But why not just use BFS with the same state? BFS, I believe, would run much faster and be not much more difficult to code?
But I probably don't know best.
Because I don't know how to implement a BFS.
Oh, and I just noticed that my java IDE doesn't support the Queue class. Hmm, it seems like I should really switch to another IDE; no Scanner, no ArrayList, no HashMap, and now no Queue. Also, please allow me to ask a very ignorant question: without queues, is it possible to (easily) code a BFS? |
|
|
|
|
|
crossley7
|
Posted: Fri Mar 02, 2012 11:19 pm Post subject: RE:Ccc 2012 |
|
|
create a manual queue with an array and index of where you started. Ideally a flexible array/vector would be best to use for this purpose or at least something that you can quickly remove elements/indexes from. In C++ I normally use vectors for my queue in a bfs, but you can use makeshift ways of creating a queue. |
|
|
|
|
|
VK_eipi
|
Posted: Sat Mar 03, 2012 1:26 am Post subject: Re: RE:Ccc 2012 |
|
|
NeilV @ Fri Mar 02, 2012 2:54 pm wrote: see this is why I love python. For S4 I just kept the state as a list and stored it in a dictionary, which has constant lookup time. In other words, I let python hash it for me
To clarify, were you referring to a tuple instead of an actual Python list? Lists in Python are not hashable and cannot be used as dictionary keys. |
|
|
|
|
|
danc
|
Posted: Sat Mar 03, 2012 7:52 am Post subject: Re: RE:Ccc 2012 |
|
|
crossley7 @ Fri Mar 02, 2012 11:19 pm wrote: create a manual queue with an array and index of where you started. Ideally a flexible array/vector would be best to use for this purpose or at least something that you can quickly remove elements/indexes from. In C++ I normally use vectors for my queue in a bfs, but you can use makeshift ways of creating a queue.
So do you usually just leave all the elements in the vector and simply shift your index of access variable? Why not just use a queue?
And BFS is not too hard. Sounds like maybe you do know how to implement it if you're asking about a queue. You push your starting state onto the queue, and loop until some condition is true (in this case, whether you win, or queue is empty). Inside the loop, you access the next state, and then find all the possible moves from there and push them onto the back of the queue. It is also necessary to keep track of which states you have already examined, in order to prevent pushing and repushing useless states back onto the queue. Maybe you didn't need that explanation, but I hope that helps. |
|
|
|
|
|
crossley7
|
Posted: Sat Mar 03, 2012 8:47 am Post subject: RE:Ccc 2012 |
|
|
I normally index the value at the end of a depth then remove the first element as I check it. Once it reaches that value that I know is the last one of a depth, I increase my depth counter and reset the index to the end of the vector. |
|
|
|
|
|
Sponsor Sponsor
|
|
|
danc
|
Posted: Sat Mar 03, 2012 9:19 am Post subject: RE:Ccc 2012 |
|
|
How much faster is that than actually using a queue? |
|
|
|
|
|
crossley7
|
Posted: Sat Mar 03, 2012 11:17 am Post subject: RE:Ccc 2012 |
|
|
Not sure since I never have used Java and I'm not sure of exact efficiency. It is more that I know how a vector works and haven't used a queue type if that even exists in C++. My knowledge of the language is relatively primitive and so I make do with what I do know |
|
|
|
|
|
danc
|
Posted: Sat Mar 03, 2012 11:23 am Post subject: RE:Ccc 2012 |
|
|
Oh. I was referring to the queue in C++. Makes life pretty easy. You can store pairs in it etc. |
|
|
|
|
|
NeilV
|
Posted: Sat Mar 03, 2012 11:33 am Post subject: Re: RE:Ccc 2012 |
|
|
VK_eipi @ Sat Mar 03, 2012 1:26 am wrote: NeilV @ Fri Mar 02, 2012 2:54 pm wrote: see this is why I love python. For S4 I just kept the state as a list and stored it in a dictionary, which has constant lookup time. In other words, I let python hash it for me
To clarify, were you referring to a tuple instead of an actual Python list? Lists in Python are not hashable and cannot be used as dictionary keys.
Yeah actually I did convert it to a tuple for the dictionary. But then I worked with it as a list since tuples are immutable. |
|
|
|
|
|
crossley7
|
Posted: Sat Mar 03, 2012 12:49 pm Post subject: RE:Ccc 2012 |
|
|
ok, danc. Well, now after the last dwite and this, I have learned 2 new types in c++
Didn't know about pairs or queue. Both of those would make some problems much easier |
|
|
|
|
|
ultimatebuster
|
Posted: Sat Mar 03, 2012 1:06 pm Post subject: RE:Ccc 2012 |
|
|
Ah this is embarassing.. I have a 54 according to my teachers. I failed at question 3 and 4, where question 3 it's a matter of just being stupid: all of my own test cases are really the same case.. and here's the incorrect line:
CODE: |
return max(secondreadings) - topreadings[0]
|
Where as the correct is
CODE: |
if min(secondreadings) < topreadings[0]:
return min(secondreadings) - topreadings[0]
else:
return max(secondreadings) - topreadings[0]
|
... Can't believe I made a stupid error especially since i instantly saw my problem when i ran through the first test case.. damnit.
Something went wrong in my BFS algorithm or my hashing algorithm for S4. It looks like all of the test cases gave incorrect answers for my solution in S4, even though all my own tests passed.
It's probably going to turn out to be something really really dumb as well.. so I don't even want to spend hours debugging my BFS algorithm.. |
|
|
|
|
|
danc
|
Posted: Sat Mar 03, 2012 1:12 pm Post subject: Re: RE:Ccc 2012 |
|
|
crossley7 @ Sat Mar 03, 2012 12:49 pm wrote: ok, danc. Well, now after the last dwite and this, I have learned 2 new types in c++
Didn't know about pairs or queue. Both of those would make some problems much easier
haha, and i guess while you're at it, i'll mention priority queues too! useful for dijkstra's, but top element is always the largest value, so you have to negate them. both are in <queue>. useful stuff, yo! |
|
|
|
|
|
|
|