Archive | Tutorials RSS feed for this section

3 October 2011 Comments Off

13 tips on how to comment your source code

This article was written by José M. Aguilar in Spanish on his excellent blog Variable Not Found, and was translated, edited and republished here by Timm Martin (and Google Translator) with permission from Mr. Aguilar.

Following are 13 tips on how to comment your source code so that it is easier to understand and maintain over time.

1. Comment each level

Comment each code block, using a uniform approach for each level.  For example:

  • For each class, include a brief description, author and date of last modification
  • For each method, include a description of its purpose, functions, parameters and results

Adopting comment standards is important when working with a team.  Of course, it is acceptable and even advisable to use comment conventions and tools (such as XML in C# or Javadoc for Java) to facilitate this task.

2. Use paragraph comments

Break code blocks into multiple “paragraphs” that each perform a single task, then add a comment at the beginning of each block to instruct the reader on what is about to happen.

// Check that all data records
// are correct
foreach (Record record in records)
{
if (rec.checkStatus()==Status.OK)
{
. . .
}
}
// Now we begin to perform
// transactions
Context ctx = new ApplicationContext();
ctx.BeginTransaction();
. . .

3. Align comments in consecutive lines

For multiple lines of code with trailing comments, align the comments so they will be easy to read.

const MAX_ITEMS = 10; // maximum number of packets
const MASK = 0x1F;    // mask bit TCP

Some developers use tabs to align comments, while others use spaces.  Because tab stops can vary among editors and IDEs, the best approach is to use spaces.

4. Don’t insult the reader’s intelligence

Avoid obvious comments such as:

if (a == 5)      // if a equals 5
counter = 0; // set the counter to zero

This wastes your time writing needless comments and distracts the reader with details that can be easily deduced from the code.

5. Be polite

Avoid rude comments like, “Notice the stupid user has entered a negative number,” or “This fixes the side effect produced by the pathetically inept implementation of the initial developer.” Such comments do not reflect well upon their author, and you never know who may read these comments in the future: your boss, a customer, or the pathetically inept developer you just insulted.

6. Get to the point

Don’t write more in comments than is needed to convey the idea.  Avoid ASCII art, jokes, poetry and hyperverbosity.  In short, keep the comments simple and direct.

7. Use a consistent style

Some people believe that comments should be written so that non-programmers can understand them.  Others believe that comments should be directed at developers only.  In any event, as stated in Successful Strategies for Commenting Code, what matters is that comments are consistent and always targeted to the same audience.  Personally, I doubt many non-developers will be reading code, so comments should target other developers.

8. Use special tags for internal use

When working on code as a team, adopt a consistent set of tags to communicate among programmers.  For example, many teams use a “TODO:” tag to indicate a section of code that requires additional work:

int Estimate(int x, int y)
{
// TODO: implement the calculations
return 0;
}

Tag comments don’t explain code; rather they seek attention or deliver a message.  But if you use this technique, remember to follow up and actually do what the message is asking.

9. Comment code while writing it

Add comments while you write code and it’s fresh in your memory.  If you leave comments until the end, it will take you twice as long, if you do it at all.  “I have no time to comment,” “I’m in a hurry,” and “The project is delayed” are all simply excuses to avoid documenting your code.  Some developers believe you should write comments before code as a way to plan out your ultimate solution.  For example:

public void ProcessOrder()
{
// Make sure the products are available
// Check that the customer is valid
// Send the order to the store
// Generate bill
}

10. Write comments as if they were for you (in fact, they are)

When it comes to commenting code, think not only about the developers who will maintain your code in the future, but also think about yourself.  In the words of the great Phil Haack:

“As soon as a line of code is laid on the screen, you’re in maintenance mode on that piece of code.”

As a result, we ourselves will be the first beneficiaries (or victims) of our good (or bad) comments.

11. Update comments when you update the code

There is no point in commenting correctly on code if the comments are not changed with the code.  Both code and comments must move in parallel, otherwise the comments will actually make life more difficult for developers who maintain your code.  Pay special attention to refactoring tools that automatically update code but leave comments unchanged and hence obsolete in the same instant.

12. The golden rule of comments: readable code

One of the basic principles for many developers: Let your code speak for itself. Although one suspects this movement is led by programmers who do not like to write comments, it is true that self-explanatory code can go a long way toward making code that’s easier to understand and can even render comments unnecessary.  For example, the code in my Fluid Interfaces article shows how clear self-explanatory code can be:

Calculator calc = new Calculator();
calc.Set(0);
calc.Add(10);
calc.Multiply(2);
calc.Subtract(4);
Console.WriteLine( "Result: {0}", calc.Get() );

In this example, comments are not needed and would likely violate tip #4.  To facilitate readable code, you might consider using proper names (as described in the classic Ottinger’s Rules), ensure correct indentation, and adopt coding style guides.  Failure to comply with this tip may result in comments that seem to apologize for bad code.

13. Share these tips with your colleagues

Although tip #10 shows how we ourselves benefit immediately from good comments, these tips will benefit all developers, especially in the context of team working together.  Therefore, feel free to share these commenting tips with your colleagues to create code that is easier to understand and maintain.

Tags: ,
1 June 2011 Comments Off

QuestToSolve.Com | A nice attempt to improve problem solving skills

A nice attempt to improve problem solving skills: http://www.questtosolve.com/

“(…)In the spirit of Steven Halim’s World of Seven: Methods to Solve website, that posted the solutions to hundreds of problems for the University of Valladolid (UVa) Online Judge website, we have decided to not only tackle UVa problems in preparation of ACM ICPC competition, but also to post the answers that we find for each problem in the hope that our repository of solutions will be as great an informational resource to programmers everywhere as Steven’s was.

Who are we? Two students majoring in Computing Science from Simon Fraser University in British Columbia, Canada.(…)”

1 June 2011 Comments Off

ACM-ICPC World Final 2011 Problems – by Petr Mitrichev

I couldn’t stop myself from sharing a nice post from Petr Mitrichev’s blog:

“(…) I’ve taken some time to reflect on the World Finals problems – hopefully that will be interesting for you to read. If you were not following the World Finals closely, you should probably skip this post :)

The problems are at http://cm.baylor.edu/digital/icpc2011.pdf, the unofficial solutions from Per at http://www.csc.kth.se/~austrin/icpc/finals2011solutions.pdf.

I’ve really liked the problemset, so please don’t take my words below as criticism – I’ve just tried to look at the problems from different angles and classify them in different ways, and maybe suggest some improvements for the future.

Problem A – To Add or to Multiply – ad-hoc (number theory?) (by ad-hoc I mean “need creative thinking to solve but no necessary prior algorithm/mathematics knowledge or experience solving similar problems”), most difficulty in corner cases and finding the lexicographically smallest answer.
Problem B – Affine Mess – exhaustive search (do what’s described in the problem statement) + solving a system of 2 linear equations, most difficulty in corner cases.
Problem C – Ancient Messages – ad-hoc, out-of-format problem, as there’s no precise definition of valid input.
Problem D – Chips Challenge – maximum flow (reduction to flow is the most difficult part).
Problem E – Coffee Central – exhaustive search (do what’s described in the problem statement) + the набившая оскомину idea about using inclusion-exclusion for rectangle sums. Most difficulty in finding the lexicographically smallest answer.
Problem F – Machine Works – DP plus incremental convex hull within one quadrant. The key to producing NlogN solution is the somewhat well-known idea about incremental convex hull to find the maximum of a set of linear functions. Most difficulty is inventing this speedup (if not known in advance) and implementing incremental convex hull.
Problem G – Magic Sticks – ad-hoc, geometry. The solution has two main parts – inventing and then proving (or believing) the key mathematical fact about throwing away the longest edge, and solving a sub-problem where you have to maximize the area of the polygon with the given sides. The sub-problem is again quite well-known and was a significant advantage to the teams who saw it before. However, I believe the most difficult part was the longest edge fact. There was also a catch about one edge taking more than Pi angle which many teams forgot to account for.
Problem H – Mining Your Own Business – graph theory, ad-hoc. The most mathematically beautiful problem of the contest in my opinion. The main difficulty is constructing the “if and only if” condition for the set of escape shafts.
Problem I – Mummy Madness – interval trees (or priority queues), ad-hoc. The main difficulty is realizing (a.k.a proving or believing) the problem can be reduced to checking if a square is completely covered by a set of squares. The NlogN solution to that sub-problem is very well-known and should be very easy for top teams.
Problem J – Pyramids – quite straightforward DP (backtracking should also work). I don’t see any significant difficulty at all here, but if I were to choose the main difficulty, it would be building the lexicographically largest answer in the DP solution.
Problem K – Trash Removal – a well-known problem. Solvable in NlogN using rotating calipers, but since the constraints were so low, that solution is an overkill. The only difficulty with such small constraints was to realize that the line should be parallel to the line connecting some pair of vertices. The main difficulty is the geometric formulas, but those are very easy as well.

Problem H was really standing out from the problemset, in my view, because it required graph theory thinking but at the same time involved no heavyweight algorithms or implementation difficulties. I would love to see more problems like this, but they are very hard to come up with. Problem C is unusual (so one might argue it gets close to the boundary of teams might reasonably expect) but still good. Problems E, F, I, J, K are “professional” problems – the most difficult part of each lies in a “standard set of tools” that most competitive programmers hone from contest to contest. This is not a negative thing – those ideas form the standard set of tools exactly because they’re most useful “building blocks” of various algorithms. Problem K may be too well-known though. Problem G is borderline as it combines a beautiful ad-hoc part with quite difficult algorithm that might be well-known to some teams but not others. Problem D is borderline (but still very good in my opinion) because the “reduce to maximum flow” trickery can also be viewed as a part of “standard set of tools”, and thus the problem is quite “professional” too. Problems A, E, J require relatively little thought, and have main difficulty in figuring out the corner cases and careful implementation, which is not exciting, and I’d say 3 such problems is too much (but maybe I’m too subjective after several teams I’ve supported got buried in those issues).

To spice up the long text, here’s my picture with the World Champions:

Please share your thoughts :) …”

29 May 2011 Comments Off

Some Cheatsheet/download

http://code.google.com/p/acmudec/downloads/list

Some ACM Sample Problems

Tags:
6 May 2011 Comments Off

Tips and Tricks

- Chua Hock-Chuan (ehchua@ntu.edu.sg)

(C/C++) Avoiding “if (i=0) {…}” error – This is probably C++ Tips Number 1

If you are comparing with a constant, you could place the constant on the LHS (instead of the usual RHS). That is, instead of writing "if (i == 0) {...}“, write “if (0 == i) {...}“. The compiler will flag out a syntax error if you inadvertently write "if (0 = i) {...}". [Java introduces a new data type called boolean, which kills this problem.]

[Contributed by Nguyen Trung Nghia]

(C/C++/Java) switch is better than nested-if

Instead of writing:

if (0 == i)
   //do something
else if (1 == i)
   //do something
else if (2 == i)
   //do something
else if (3 == i)
   //do something
else
   //do something

It is better to write:

switch(i) {  // for int and char only
   case 0:
      //do something
      break;
   case 1:
      //do something
      break;
   case 2:
      //do something
      break;
   case 3:
      //do something
      break;
   default:
      //do something
}

[Contributed by Nguyen Trung Nghia]

(C/C++) The dreaded #define

Nghia recommends the following #define to speed up your programming in the contest:

#define REP(i,a) for(i=0;i<a;i++)
#define FOR(i,a,b) for(i=a;i<b;i++)
#define VE vector<int>
#define SZ size()
#define PB push_back

My Note: Beware of #define in normal programming. You could use #define to change the C++ language into C--, a useless language that only you can understand (in other words, this is not a good software engineering practice).

(C/C++/Java) Bit Manipulation

From http://en.wikipedia.org/wiki/Bit_manipulation:

To “set” a bit (where n is the bit number, and bit 0 is the least significant bit):

unsigned char a |= (1 << n);   // '|' is bitwise OR, '<<' is bit left-shift

To “clear” a bit:

unsigned char b &= ~(1 << n);  // '&' is bitwise AND

To “toggle” a bit:

unsigned char c ^= (1 << n);   // '^' is bitwise XOR

To “test” a bit:

unsigned char e = d & (1 << n); //d has the byte value.

(Training Problem) Prime Numbers

The simplest, most elegant algorithm is perhaps the sieve of Eratosthenes. This pseudo-code is given in http://en.wikipedia.org/wiki/Prime_number:

// arbitrary search limit
limit ← 1000000                   

// assume all numbers are prime at first
is_prime(i) ← true, i ∈ [2, limit] 

for n in [2, √limit]:
   if is_prime(n):
      // eliminate multiples of each prime,
      // starting with its square
      // 2n, 3n, ..., (n-1)n already eliminated
      // nn, (n+1)n, (n+2)n, ... to be eliminated
      is_prime(i) ← false, i ∈ {n^2, n^2+n, n^2+2n, ..., limit}

for n in [2, limit]:
   if is_prime(n): print n

Nghia wrote: with this simple algorithm, you can solve quite a number of problems in acm.uva.es. You should use bit operations to reduce the size of memory used.

  • http://acm.uva.es/p/v1/136.html (warming up)
  • http://acm.uva.es/p/v1/160.html
  • http://acm.uva.es/p/v4/406.html
  • http://acm.uva.es/p/v5/583.html
  • http://acm.uva.es/p/v103/10394.html
  • http://acm.uva.es/p/v105/10539.html
  • http://acm.uva.es/p/v108/10858.html
  • http://acm.uva.es/p/v108/10856.html (this problem needs prime generator + very simple DP + very useful and basic search technique)

(Training Problem) To find B^P mod M

B^P means B raise to the power of P. B and P are integers in the range 0 to 2147483647 inclusive. M is an integer in the range 1 to 46340 inclusive.

Hint:

  • P = a0 x 2^0 + a1 x 2^1 + a2 x 2^2 + a3 x 2^3 + … + an x 2^n (n<32)
  • Find B^a0 mod m, B^a1 mod m, B^a2 mod m, B^a3 mod m, …, B^an mod m (32 term only)
  • B^ai mod m can be found by using the result from B^aj mod m, j = i – 1 (this is called Dynamic Programming)
  • Please remember (axb) mod m = ((a mod m) x (b mod m)) mod m (to avoid overflow errors)
  • The complexity of this algorithm is log(P)
  • try to make your source code as short as possible. In order to do that, you may need to use bit operation and only one for/while loop.

Try these problems:

  • http://acm.uva.es/p/v3/374.html
  • http://online-judge.uva.es/p/v102/10229.html ( try to represent f[n] as = [ a b ; c d ]^n )
Tags: , ,
6 May 2011 Comments Off

Step by Step..ACM ICPC

Step by Step..ACM ICPC

- Chua Hock-Chuan (ehchua@ntu.edu.sg)
Step 1 – Try PKU Online Judge

  1. Register with PKU online judge @ http://acm.pku.edu.cn/JudgeOnline/.
  2. Read the FAQ to understand to submission rules – IMPORTANT!
  3. Read the FAQ AGAIN.
  4. The programming rules for ICPC are:Java Language
    • Input comes form System.in and output goes to System.out (no File IO allowed).
    • The source file must contain a class called Main with the entry-method main:
      public static void main(String[] args) { ... }.

    C++ Language

    • Input comes form std:cin and output goes to std:cout (no File IO allowed).
    • The source file must contain the entry-function int main() { ... }.
  5. Try the first problem “1000 (A+B)” with the solution provided in FAQ. The purpose of this problem is to let you understand the above programming rules. In your submission, make sure you specify the language used (“Java”, “G++” for GNU C++ compiler, or “C++” for VC6 compiler).For Java programmers
    You should program at JDK 1.5 or above. Use Scanner, in.nextInt(), in.nextDouble(), in.next() for inputting int, double, and String, and C-like System.out.printf("formatString", args...) for output.
    JDK 1.5 Program Template for ICPC Online Judge

    import java.util.Scanner;
    
    public class Main {   // save as Main.java
       public static void main(String[] args) {
          Scanner in = new Scanner(System.in);
    
          int    i = in.nextInt();    // read int
          double d = in.nextDouble(); // read double
          String s = in.next();       // read String
          // There is no nextChar(), use next() and charAt()
          char c = s.charAt(2);
          // Read whole line (or rest of the line past '\n')
          String line = in.nextLine();
    
          System.out.printf("%4d, %6.2f, %s, %c\n", i, d, s, c);
          // Use %f for double (not %lf)
          // Don't forget to print the '\n'
       }
    }
    
  6. Try another few (extremely) simple problems (you can look at the percentages to estimate the difficulty of the problems)
    • Read the programming rules AGAIN before trying these problems.
    • You input and output must strictly follow the description given. You need not and CANNOT print input prompting message such as “Please enter a number” (because nobody is sitting at the online judging system to read these prompts).
    • Do “1004 (Financial Management)” – Simply averaging 12 numbers
      Hints: To test this program, you have two options: (a) key in the 12 numbers slowly, or (b) save the 12 numbers in a file, says “in.txt“, start a Command shell (“cmd“), and use the “pipe” operator “<” to re-direct the input from the file “in.txt” to the stdin as follows:
      For Java Programmers
      Assume that the source file is called Main.java

      > javac Main.java
      > java Main < in.txt
      

      For C++ programmers
      Assume that the source file is called test.cpp

      > g++ -o test.exe test.cpp
      > test < in.txt
      
    • “1003 (Hangover)” – Compute the sum of a harmonic series and compare…
    • “1005 (I think I need a house boat)” – Compute the area of a semi-circle and compare…

Step 2 – Try UVA Online Judge: This site is meant for C/C++ programmers. Java programmers can forget about this site (as there is no support for JDK 1.5). For C programs, you cannot use // comments.

  1. Register with UVA online judge @ http://online-judge.uva.es/problemset/.
  2. Read the HOWTOs, especially on how to submit solution.
  3. Try the first problem Volume 1 Problem 100 (3n+1) with the solution provided in HOWTOs.

The above steps are meant for you to familiarize with the contest process. Here come the “serious” training…

Step 3 – Try USACO Training Problem

  1. Register with USACO Training Program @ http://train.usaco.org/usacogate/.
  2. Read “Section 1.0 Text Introduction” and “Section 1.1 Submitting Solutions”.
    As mentioned, this site is meant for IOI instead of ICPC, the submission requirements are different from the online judges.
    You are required to read from an input file named “xxxx.in” and write to an output file named “xxxx.out” where “xxxx” is the name of the problem.
    Try the “First Challenge” (or “test” problem). If you encounter problem in File IO under VC++ or Eclipse, read “VC++ File Input/Output” or “Eclipse File Input/Output“, respectively.
    For Java programmers
    The sampled Java solution given is based on JDK 1.2, which is rather clumsy in IO processing. I provide the sample solution in JDK 1.5 is as follows:JDK 1.5 Program Template for USACO

    /*
    ID: yourID
    LANG: JAVA
    TASK: test
    */
    
    import java.util.Scanner;
    import java.util.Formatter;
    import java.io.File;
    import java.io.IOException;
    
    public class test {  // saved as test.java
       public static void main (String [] args) throws IOException {
          Scanner in = new Scanner(new File("test.in"));        // file input
          Formatter out = new Formatter(new File("test.out"));  // file output
    
          int a = in.nextInt();
          int b = in.nextInt();
          out.format("%d\n",a+b);  // format() has the same syntax as printf()
    
          out.close();    // flush the output and close the output file
          System.exit(0); // likely needed in USACO
       }
    }
    
  3. Continue and try to complete the training problem. As mentioned, this site provides systematic training for the frequently used algorithms encountered in contests (IOI as well as ICPC).

Read More: http://www.ntu.edu.sg/home/ehchua/programming/icpc/icpc_getting_started.html

Resources:

Training ICPC Teams: A Technical Guide
ACM International Collegiate Programming Contest
International Collegiate Programming Contest: Getting Started
Policies and Procedures for the ACM International Collegiate Programming Contest

Tags: