ACM-ICPC 2010/2011 Programming Problem – High Score
It’s getting closer and closer to the ACM-ICPC Programming contest in UCC this year so now more then ever we need practice. If you’re not up to speed on what it’s all about check out Carl’s first post on another ACM problem. So let’s get straight to the problem. I will present the problem in as clear and simple manner as I can, as the actual problem sheet is a little off putting if you ask me. You can download the pdf for it here.
The problem is all about entering your name into a high score table using a joystick. Quite like old video games where you would be presented with an initial string of A’s which moving the Joystick right and left selected a different character. Moving up and down cycled though the alphabet. Both these movements wrap around. Eg: If you move left at “A” you get to “Z” and if you move right at the last character you get to the first. So if I want to input the string “JAN” how many moves will it take me to do this? (23 😀 ) Moving left, right, up, down is counted as a move. So your task is to develop an algorithm that will find the shortest amount of moves to achieve this. For more information and sample input download the ACM problem sheet.
So there are the basics of the problem, though my explanation is not complete so do download the ACM problem sheet. I solved this problem myself today and I will post the solution in the next few days. I need to refine my solution as its quite crude. Oh, and my solution is written in JavaScript as I solved the problem by coding, so I needed something that would let me program loosely. So anyway, I challenge you, dear reader, to attempt this problem and post your solution in the comments.
Some words of inspiration and motivation. Anyone can solve these problems if they put their mind too it. I wouldn’t count myself as smart individual, but I worked at it and solved a programming problem from a prestigious contest. So, give it a go, even if you can’t solve it, the experience of thinking about the problem and an algothrim to solve is great exercise for your brain. Watch this place or follow me on twitter to keep up-to-date @C_McCann
PS: I have a live demo of my solution below. The JavaScript is obfuscated so you can’t peek (at my horrible solution). Oh, and beware that I haven’t refined the solution yet so it could crash.
WARNING: (Only works with WebKit atm)
There are bugs and certain inputs will crash the script, just to warn you. A refined solution with bugs fixed will be posted in the coming days with source code and explaination. Follow @Flaxproject and @C_McCann for updates
[ad#adsence_inline_banner_468*60]
About the Author
Ciarán McCann
Flax Project Founder - Ciarán McCann is an extremely passionate and motivated programmer who has been programming for about 4 years now. Currently attending Carlow I.T studying computer games development. He has experience in many different programming languages, markup languages and general technologies. His role in the Flax Project is as a blogger/Web Designer and Flax Engine programmer. Please excuse any bad grammar/spelling, I am a bit on the Dyslexic side. Follow me on Twitter for info on what I am working on.
Related Posts
-
Flax HTML5 Game Engine Development Diary Part 11
Well it’s that time again, it’s been just about three weeks since the first iteration of the Flax HTML5 Game Engine 0.1 and as promised […]
Catch up with the Flax Project – Busy times!
Hey everyone, so it’s been nearly 5 weeks since we last posted. It’s been a crazy 5 weeks and it’s not over just yet. Unfortunately we […]
14 Comments
Trackbacks for this post
-
[…] the ability to think logically to solve a problem, I have even entered logic solving programming competitions. Simply the approach to teaching something makes all the difference. There needs to be […]
I have a possible solution. Should I post it here?
Ah great stuff, yes post away. I will be posting my solution near the end of the week as will Carl.
Here’s my solution (in Ruby). It’s a complete rewrite from my previous attempt. This version should handle the tough cases, like “AAAABAAAAAAABA”, where you must go backwards to B, then back around to B == 10.
Just drop it in in an .rb and run.
http://pastie.org/1663177
Nice one, well done. That seems a lot shorter then my solution.
Thanks. You going to post your solution in a new post? I’m curious to see how you went about it.
I can’t seem to find any problems with this (yet). Have you tested yours with the case where it is cheaper to go: back then forward again (looping back around twice)? Like in the AAAABAAAAAAABA case? The js version inline here hangs the browser for me (chrome).
I ended up using a circular doubly-linked list to eliminate the index headaches. Even with Ruby’s magic negative indexing on arrays, it was still tough to get it working. With the DLL I was able to find the shortest distance to the next unresolved in any direction by just going “next” or “prev”. See move_next. I use min there to determine direction, take that route, then the found object becomes the becomes the current object and the process starts over until all are resolved, or we’re back to the initial object again.
My last solution was taking a major shortcut. It was resolving each UP/DOWN on all non-A, then using some rules with simple calculations to determine the moves required to get there. It actually ended up working in _almost_ all cases and was all but 10 lines of code. Those edge cases couldn’t be solved with rules though…
This was a cool exercise.
I just writing up an article on it now. Though I might do a video to explain all the setps I took and why. I always like looking at videos explain things like that. So it should be up today or at lastest 2moro.
Yes my live demo does hang in that case I forgot a i+1 in an array index which was casing the solution to never be found and so infinite loop. Though I am quite sure it works 100% with that fix.
Yes the negative indexing was a problem for me. Though I solved it by using more loops. There are quite a number of loops in my solution. Though its quite fast.
Yes they are very cool problems indeed.
Ah. A vid would be nice.
I just put up a slightly tighter version btw.
Oh. See your fix. You’re still long on AAAABAAAAAAABA. Can be done in 10 vs 12.
AAAABAAAAAAABA
11112__________22 == 10
or
AABAABA can be done in 7 moves
__21121 == 7
You solution is showing 9 here.
Yea just updated those bugs and it takes uppercase now ha. I don’t agree with the first string AAAABAAAAAAABA I believe 12 is the correct answer, myself and Carl just worked it out manually there and we both got the same answer. Though you are correct with the second one, now I most try find the bug, though I am quite sure I know where it is.
Though for the moment I have a 3D OpenGL project to work on for college. So I will be posting my article and video 2moro.
Thanks for spotting that.
AAAABAAAAAAABA is worked out manually like this:
Left A – 1
Left A+B – 1 + 1(down)
Right A – 1
Right A – 1
Right A – 1
Right A – 1
Right A – 1
Right A+B – 1 + 1(down)
== 10
ah dammit, indeed you are correct. Hmmm I will have to look into this. Here is my code http://pastie.org/1663522
Yeah, last one is a little weird. back then forward.
Wow, you’re right. That is a lot of loops. You should be able to consolidate those down so that you’re performing multiple operations within each loop vs re-looping.
I just updated my version with another optimization. Moved from chars to ordinal ASCII values. That simplifies it a bit. Don’t think it can get much tighter without a complete rethinking.
http://pastie.org/1663177
Oh god yea I could probably consolidate it down into like 3 loops or less. Though I just wanted to get a solution more so then do it in like 4 lines of JS like some crazy people can do ha.
Anyway have to move on to the next problem soon, so I am not going to spend time optimizing this solution. The busy life of a student games developer ha.