Programming Forums - Problem solving

Programming Forums (http://www.programmingforums.org/forumindex.php)

- Software Design and Algorithms (http://www.programmingforums.org/forum64.html)

- - Problem solving (http://www.programmingforums.org/showthread.php?t=14861)

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. :)

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.

Re: Problem solving

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

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 :P

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!

Re: Problem solving

Quote:

Originally Posted by ReggaetonKing (Post 139099)

@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 :)

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.

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;

}

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! :$