Programming Forums
User Name Password Register
 

RSS Feed
FORUM INDEX | TODAY'S POSTS | UNANSWERED THREADS | ADVANCED SEARCH

Reply
 
Thread Tools Display Modes
Old Jan 3rd, 2008, 5:55 PM   #1
ReggaetonKing
Sexy Programmer
 
ReggaetonKing's Avatar
 
Join Date: Nov 2005
Location: New Jersey
Posts: 891
Rep Power: 3 ReggaetonKing is on a distinguished road
Send a message via AIM to ReggaetonKing
Problem solving

I've been participating in TopCoder.com's online algorithm competitions. Actually, I've only been doing practice problems for the past two weeks. I'm really addicted to solving these types of problems. You guys should give it a try!

Anyway, after I solved this one problem, I looked at how other's did their and made me realize, I approach problems awkward. >_> First, I try to understand the problem. Second, I look at the examples and see how the program should run. Then, I try solving the problem which data structure would be best or something along those lines.

For example, here's one the problem I did today when i got home
Quote:
Problem Statement

Rumor has it that Russians don't obey speed limits. That may be because the speed limits are sometimes specified implicitly in Russia.
More specifically, every road in a city has a default speed limit of 60 kilometers per hour, and usually doesn't have any road signs to remind drivers of that. Analogously, every road outside the city has a default speed limit of 90 kilometers per hour.
The speed limit can still be specified with road signs, like '30' or '95'. There is also a special road sign, 'start of default speed limit zone', that tells you that the default speed limit is now in place. The signs are sometimes also used to remind drivers of the current speed limit, so you can meet several same signs in a row.
To summarize, one should pay attention to the following road signs to monitor the speed limit changes:
Speed limit X - marks the start of a zone with speed limit X kilometers per hour.
Start of default speed limit zone - marks the start of a zone with the default speed limit, either 60 if inside a city or 90 if outside.
City boundary - means the default speed limit changes from 60 to 90 or vice versa. If you are inside a special speed limit zone, this zone also ends, so the speed limit always becomes equal to the new default.
Given the list of road signs you met on your way as a String[] signs (in the order you met them), return the current speed limit. Each element of signs will be either a positive integer number X without leading zeros, denoting the sign 'Speed limit X', a string "default" denoting the sign 'start of default speed limit zone', or a string "city", denoting the sign 'city boundary' (quotes for clarity only). You start your journey inside a city, and outside any special speed limit zone.
Definition

Class: RussianSpeedLimits
Method: getCurrentLimit
Parameters: String[]
Returns: int
Method signature: int getCurrentLimit(String[] signs) (be sure your method is public)


Constraints
-
signs will contain between 1 and 50 elements, inclusive.
-
Each element of signs will be "default", "city" or a positive integer without leading zeros, between 1 and 100, inclusive (quotes for clarity only).
Examples
0)


{"80"}
Returns: 80
On highways, speed limits may be above the default value.
1)


{"40", "70", "default", "20", "50"}
Returns: 50
The limits are specified in the order you meet them, so you're interested in the last one.
2)


{"40", "70", "default"}
Returns: 60
The default limit is still 60.
3)


{"40", "80", "city"}
Returns: 90
The first "city" means we've left the city, thus the 90 limit.
4)


{"city", "60"}
Returns: 60
Speed limits can be overridden outside the city too.
5)


{"city", "50", "default"}
Returns: 90
The default value changes when outside the city.
6)


{"city", "city", "city", "city"}
Returns: 60
You've crossed four city boundaries. The first time, you left a city. Then, you entered a city. Then, you left that city. Finally, you entered another city.
7)


{"20", "city", "city", "50", "60"}
Returns: 60
The default speed limit may be specified with a usual sign.


This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
It took me ~15 minutes to come up with a solution that compiles and runs correctly 100% with the given examples. After, I submitted my solution, the system is able to run a series of test on the solution and see if it works 100% as expected. My solution passed with 141 out of 141 test cases.

Here's my solution to the problem above
public class RussianSpeedLimits
{
    public int getCurrentLimit(String[] signs)
    {
        int numCities = 0;
        //count cities
        for(int x = 0; x < signs.length; x++)
             if(signs[x].equals("city")) ++numCities;
            
        
        if(signs.length == 1 && isNumber(signs[0])) return Integer.parseInt(signs[0]);
        else if(signs.length == 1 && insideCity(numCities)) return 60;
        else if(signs.length == 1) return 90;
            
        if(isNumber(signs[signs.length - 1])) return Integer.parseInt(signs[signs.length - 1]);
        else if (insideCity(numCities)) return 60;
        else return 90;
    }
    private boolean insideCity(int numCities)
    {
        if(numCities % 2 == 0) System.out.println("Inside City!");
        return (numCities % 2 == 0 ? true : false);
    }
    private boolean isNumber(String n)
    { //go easy on me with this method.... (>_<)
        try
        {
            Integer.parseInt(n);
            return true;
        }
        catch(Exception e)
        {
            return false;
        }
    }
}
This would give you some what of an idea on how I think. Can you guys (and girls ) please give me tips on how I could have solved it better? Any suggestions? It would be more appreciated.
__________________
I would love to change the world, but they won't give me the source code!
ReggaetonKing is offline   Reply With Quote
Old Jan 4th, 2008, 12:56 AM   #2
Salem
Programmer
 
Join Date: Nov 2007
Posts: 33
Rep Power: 0 Salem is on a distinguished road
Re: Problem solving

Your approach and answer look perfect to me.

> First, I try to understand the problem.
Yes, because solving a different problem won't get you your marks now, and won't get you paid later.

> Second, I look at the examples and see how the program should run.
Also good. It might produce the correct answer, but if all the detail of the program I/O is wrong, then it's still a failure.

> Then, I try solving the problem which data structure would be best or something along those lines.
Also good. The choice of good algorithms + data structures vs. bad ones can turn mere seconds on run-time into days or weeks.

> how I could have solved it better?
What would you consider "better"?
Less lines of code. Doesn't work for me, since I value readability above pretty much everything else. Being a good coder is not about writing the shortest and most cryptic bit of code possible.
Commercially, your code might last for 20 years or more, and be read by hundreds of different programmers in that time. Communicating clearly with all of them is paramount.
__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
Salem is offline   Reply With Quote
Old Jan 4th, 2008, 4:15 AM   #3
Jimbo
Battle Programmer
 
Jimbo's Avatar
 
Join Date: Feb 2006
Location: Bellevue, WA, USA
Posts: 748
Rep Power: 3 Jimbo is on a distinguished road
Re: Problem solving

First, I LOLed when I saw the copyright notice you posted.

Then I decided this would be kinda fun. I haven't tested my solution, but I'll put it up anyways (I'm off to bed so maybe I'll test it tomorrow if I remember; by the way, did they provide a test file/framework or did you just do a bunch by hand?)

using System;

namespace SwitchTest
{
    class Program
    {
		public static void Main(String[] args)
		{
			Program p = new Program();
			Console.WriteLine("Current speed limit is: " + p.GetSpeedLimit(args));
		}

		const int defCity = 60;
		const int defHighway = 90;
		bool inCity;
		int currentSpeed;

		private int GetSpeedLimit(String[] signs)
		{

			inCity = true;
			currentSpeed = defCity;
			foreach (String s in signs)
			{
				switch (s)
				{
					case "city":
						ToggleCity();
						SetToDefaultSpeed();
						break;
					case "default":
						SetToDefaultSpeed();
						break;
					default:
						try
						{
							currentSpeed = int.Parse(s);
						}
						catch (Exception) // bad style, but assuming valid input I shouldn't need try-catch anyways
						{
							Console.WriteLine(String.Format(@"Invalid input received, skipping.  Input was: {0}", s));
						}
						break;
				}
			}
			return currentSpeed;
		}

		private void SetToDefaultSpeed()
		{
			if (inCity)
				currentSpeed = defCity;
			else
				currentSpeed = defHighway;
		}

		private void ToggleCity()
		{
			inCity = !inCity;
		}
    }
}

If it doesn't work, my lame excuse is that I spent about 5 minutes thinking and typing combined, and it's 2 in the morning. [edit:] Just noticed the part about the class name and signature, but I was too lazy to name mine
__________________
<insert disclaimer here>
<insert shameless plug for Visual Studio here>
Jimbo is offline   Reply With Quote
Old Jan 4th, 2008, 9:46 AM   #4
ReggaetonKing
Sexy Programmer
 
ReggaetonKing's Avatar
 
Join Date: Nov 2005
Location: New Jersey
Posts: 891
Rep Power: 3 ReggaetonKing is on a distinguished road
Send a message via AIM to ReggaetonKing
Re: Problem solving

@Salem: By better, I actually mean more efficient. Regardless what language I progam in, I still want the most efficient solution for any problem I approach.

@Jimbo: Your solution looks good! A lot better than mine!

Thanks for the replies, guys!
__________________
I would love to change the world, but they won't give me the source code!
ReggaetonKing is offline   Reply With Quote
Old Jan 4th, 2008, 10:51 AM   #5
Jimbo
Battle Programmer
 
Jimbo's Avatar
 
Join Date: Feb 2006
Location: Bellevue, WA, USA
Posts: 748
Rep Power: 3 Jimbo is on a distinguished road
Re: Problem solving

Quote:
Originally Posted by ReggaetonKing View Post
@Salem: By better, I actually mean more efficient. Regardless what language I progam in, I still want the most efficient solution for any problem I approach.
I'm going to agree with Salem on this one. Unless you have severe performance constraints, maintainable code is so much more valueable than fastest code. It's a different kind of efficiency, but from a development standpoint usually more important. Thinking about it last night, I actually think that things like Top Coder can be a bad influence because they place more emphasis on differences in speed - even small ones - and less on code quality.

Quote:
@Jimbo: Your solution looks good! A lot better than mine!
Thanks
__________________
<insert disclaimer here>
<insert shameless plug for Visual Studio here>
Jimbo is offline   Reply With Quote
Old Jan 4th, 2008, 12:30 PM   #6
Salem
Programmer
 
Join Date: Nov 2007
Posts: 33
Rep Power: 0 Salem is on a distinguished road
Re: Problem solving

> By better, I actually mean more efficient.
The reduced argument is why are you writing in anything other than assembler then? Mostly the answer is you don't, because it would take too long, and the result is in no way portable.

Read this before going all gung-ho over trying to squeeze every last uS out of your code.

> I still want the most efficient solution for any problem I approach.
Unless you have an infinite amount of time, you're not going to find it. There'll always be someone else who can get that little bit extra.

Other efficiency measures:
- time it takes to write, 20 minutes (C) or a month (asm)
- time it takes to test and debug, similar extremes. Your clever asm code may be very fast, use lots of obscure technique, but if you make a mistake, you're hosed.
- time it takes to explain it to the maintenance guy, similar extremes.

You've got to run the code a hell of a lot to make several months of effort (compared to a couple of hours) pay off.

As soon as you start programming against any kind of a deadline (like professionally), then you'll realise than 99% of the program is nowhere near the program critical performance path, so busting a gut to make it microseconds quicker is a waste of effort.

Further, predicting where the performance bottleneck is is a black art, never mind the problems of figuring out the true cause.
For example, if your profile shows say strcpy() being called a lot, the answer isn't "rewrite strcpy", it's investigate why it's being called so many times in the first place. The fastest code of all is the code which isn't called.

Single function quiz assignments on the other hand are much easier to write, and much easier to profile. With some skill, and plenty of time, you can usually make a pretty "optimal" job, in terms of run-time performance.

> I actually think that things like Top Coder can be a bad influence
Probably because something like "performance" is dead easy to measure. All you need is a clock to time it, and 'diff' to compare the outputs.
Measuring "code quality" is an altogether different prospect, one which machines are currently useless at. Nor are they capable of measuring with any accuracy the amount of effort spent on the program.
__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
Salem is offline   Reply With Quote
Old Jan 4th, 2008, 1:10 PM   #7
null_ptr0
11 years old
 
Join Date: Nov 2007
Posts: 79
Rep Power: 1 null_ptr0 is on a distinguished road
Re: Problem solving

Some of your stuff is redundant, for example, for insideCity, just return num mod 2 equals 0, no need for ternary operators.
My attempt that I haven't tested:
public int getCurrentLimit(String[] signs) {
   if(signs.length == 1) {
      if(isNumeric(signs[0]))
         return Integer.parseInt(signs[0]);
      else if(signs[0].equals("city"))
         return 60;
   } else {
      String lastEntry = signs[signs.length - 1];
      if(isNumeric(lastEntry))
         return Integer.parseInt(lastEntry);
      else if(isEven(find("city", signs)))
         return 60;
   }
   return 90;
}

private boolean isNumeric(String str) {
   str = str.trim();
   for(char c : str.toCharArray())
      if((c < 0x30 || c > 0x40) && c != 0x2D && c != 2B)
         return false;
   return true;
}

private int find(Object val, Object[] arr) {
   int found = 0;
   for(Object val2 : arr)
      if(val.equals(val2))
         found++;
   return found;
}

private boolean isEven(int num) {
   return num % 2 == 0;
}
__________________
iload_0 iconst_1 ishl or
iload_0 iconst_2 idiv or
iload_0 iconst_2 iconst_1 imul idiv
[1] & [2] use the smallest stack size
null_ptr0 is offline   Reply With Quote
Old Jan 4th, 2008, 1:49 PM   #8
ReggaetonKing
Sexy Programmer
 
ReggaetonKing's Avatar
 
Join Date: Nov 2005
Location: New Jersey
Posts: 891
Rep Power: 3 ReggaetonKing is on a distinguished road
Send a message via AIM to ReggaetonKing
Re: Problem solving

I respect and agree with your responses. Although, my question and comments was towards this kind of programming problems and not high budget projects were code quality matters more. I'm aware of code quality due to the fact I debug my code approximately half of the day at work.

Quote:
The reduced argument is why are you writing in anything other than assembler then? Mostly the answer is you don't, because it would take too long, and the result is in no way portable.
I'm not writing in assembly because I'm more functional in my preferred languages which I spent more time learning and solving problems with. Another reason is, as you said, the time it would take versus using my preferred high level languages.

@null_ptr0: lol when I was going through Jimbo's code and comparing it with mine, I realize the same thing!
__________________
I would love to change the world, but they won't give me the source code!
ReggaetonKing is offline   Reply With Quote
Reply

Bookmarks

« Previous Thread in Forum | Next Thread in Forum »

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Challenging Programming Problem - "Pinball Ranking" Sane Coder's Corner Lounge 38 Jan 15th, 2008 5:16 PM
Storing BLOBs in a database - problem jonyzz Other Programming Languages 8 Jan 31st, 2007 4:38 AM
cgi/perl script + IE problem joyceshee Perl 2 Jan 24th, 2006 11:10 AM
problem with user defined class mixed with functions willj729 C++ 4 Oct 9th, 2005 3:26 PM
string problem when passing in linked list quantz C++ 0 Feb 27th, 2005 10:11 AM




DaniWeb IT Discussion Community
All times are GMT -5. The time now is 5:42 PM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC