Computer programming is an exercise in problem solving. As a programmer, you are presented with the challenge of creating a computerized solution. Using your logic and experience, you craft the solution, and when you're finished, there's a good degree of satisfaction exchanged for your effort. The programming process may even include a clever flash of insight, which is also rewarded with a feeling of accomplishment.
Within the programmer community, there exists an association of folks who take programming and problem-solving to a global level of organization. This is the world of contest programming.
Contest Programming
Contest programming is designed to sharpen programmers' problem-solving and coding skills in a competitive structure. Programmers can compete with others from all over the world to see how well they stack up to one another.
Contest problems can also be taken out of the competitive setting and used as a set of little coding puzzles, available to one and all. These little problems can be a great source of practice for learning a new coding language or for acquiring additional problem-solving skills.
In either case, contest programming consists of problems that are to be solved with a computer, the solution source code that will produce the solution, and a judge that decides whether the solution is correct. A solution is considered to be correct if it produces the correct output. Beyond some loose performance restrictions (your program must run in less than one minute, for instance,) there is no consideration for coding practices. That is, there are no style points in contest programming.
Problem Solving
To the iSeries professional operating within a business environment, "problem solving" usually takes the form of, for example, a call from Debbie in AP: "Hi. How's the family? (No pause.) I've just printed 300 checks on check stock for an account that was closed four months ago. Can you help me? (Now, a pause.) Roll something back, maybe, like last time? Lemme know by 3:00? Soccer night. Thanks."
Well, problem solving can also mean the act of creating a computer solution to a sort of contrived programming challenge. The value in such an enterprise is an increase in logic and coding abilities, plus an exposure to new data structures and programming techniques.
Take, for example, the famous "traveling salesman" problem. That is, what is the shortest route a traveling salesman can take to visit each city in his territory once and then return home? Well, as you would expect, the answer to this problem has been worked out. The solution is also famous and is known as Dijkstra's Shortest Path Algorithm. But still the challenge remains of turning something like Dijkstra's Algorithm into actual working code.
Note that it is not uncommon for some employers (Microsoft among them) to focus on an employment candidate's problem-solving skills when being considered for hire. Many organizations use the contest problems as a test of these skills. Such a test shows how well and how fast you can code.
University Programming Contests
Contest programming has been used within colleges and universities for a long time to teach and recognize good problem-solving skills. The contests range from small internal events where students within a given school compete with each other to large state, regional, and national trials.
Here's how a typical programming contest works within the computer science departments of many universities. Teams of two to four programmers are given five hours to solve as many short, yet challenging, programming problems as they can. Teams are given a list of programming problems as the clock is started. Each problem may be solved with a short C, C++, or Java program, but the solution requires some degree of coding dexterity. Once a solution has been created, the code is submitted to a judge. The judge runs the program against a robust set of test data to expose any flaw in the solution. If the solution is correct, the team scores a point, and the number of minutes since the beginning of the contest is noted and accumulated. At the end of the five hours, the team that has solved the most problems wins. If more than one team has the same number of solved problems, the total minutes taken determines the winner. The fewer minutes taken to solve the problems, the better.
Contestants may bring printed reference materials to the contest, but electronic media and Internet access are not allowed. (Note that the current trend may change to disallow printed reference material as well.)
What a Contest Problem Looks Like
A typical contest problem resembles this popular example, called the "Crypt Kicker II". (The term "crypt" refers to encryption.) This example by Miguel Revilla is from the Universidad de Valladolid contest Web site.
Crypt Kicker II
A common but insecure method of encrypting text is to permute the letters of the alphabet. That is, in the text, each letter of the alphabet is consistently replaced by some other letter. So as to ensure that the encryption is reversible, no two letters are replaced by the same letter.
A common method of cryptanalysis is the known plaintext attack. In a known plaintext attack, the cryptanalist manages to have a known phrase or sentence encrypted by the enemy, and by observing the encrypted text then deduces the method of encoding.
Your task is to decrypt several encrypted lines of text, assuming that each line uses the same set of replacements, and that one of the lines of input is the encrypted form of the plain text
the quick brown fox jumps over the lazy dog
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The input consists of several lines of input. Each line is encrypted as described above. The encrypted lines contain only lower case letters and spaces and do not exceed 80 characters in length. There are at most 100 input lines.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
Decrypt each line and print it to standard output. If there is more than one possible decryption (several lines can be decoded to the key sentence), use the first line found for decoding.
If decryption is impossible, output a single line:
No solution.
Sample Input
1
vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq
Sample Output
now is the time for all good men to come to the aid of the party
the quick brown fox jumps over the lazy dog
programming contests are fun arent they
This example problem is a text-handling puzzle. Other problems focus on other coding challenges like array handling, algorithmic manipulations, or programming concepts such as recursion. In any type of problem, the exact output as described in the problem must be provided by your solution program.
The Solution
The solution to the above problem will take the form of a small Java, C++, or C program (or sometimes Pascal) consisting of a single source file. The program will accept the input from standard in and send the output to standard out. Nothing more and nothing less. Absolutely nothing.
If you're coding in Java, you may use all the tools found in the Java SDK. For example, you may use the Java language function Math.sqrt to get the square root of a number. If you're coding in C/C++, you may use all the functions in the standard libraries.
Universidad de Valladolid
At Spain's Universidad de Valladolid (or UVa) beats the heart of the contest programming scene. As Rochester is to the iSeries, Valladolid is to contest programming (Figure 1).
Figure 1: The Universidad de Valladolid Web site is the center of the contest programming world. (Click image to enlarge.)
In this well-supported Web site is a collection of established problems and an online judging process. The UVa maintains a database of contest problem participants, the problems attempted, and the results. Anyone can join and participate in this free service sponsored by the Association of Computing Machinery (ACM). If you're a programming puzzle enthusiast or if you're trying to hone your instruction-following and problem-solving skills, this is for you.
Part of the UVa Web site for contest programming is the online judge. The online judge is really a program, not a person. Once you've attempted to solve a problem, you submit your program source code to the online judge. The judge first tries to compile your code. If your code compiles, the judge launches your program and feeds it the test data (note that the judge's test data is much more exhaustive than the example input shown in the problem instructions).
Once the judging is complete, the results are made available to you. If your program was found to be unacceptable (and believe me, this can happen even when you're absolutely sure it's correct), you are given a hint as to the nature of the flaw. For example, the return value from the online judge could be CE for compiler error, WA for wrong answer, or TL for time limit exceeded. You then fix the problem and submit it again. Typically, multiple submissions will be required before you've thought of everything and finally pass. See the UVa Web site for more information.
The Programming Challenges Book and Web Site
If you're interested in participating, you may do well to look into the book Programming Challenges by Steven S. Skiena and Miguel A. Revilla. This book is dedicated to contest programming participants and contains very valuable instructions and tips, together with over 100 of the best programming problems from UVa. Also included are discussions of the various programming techniques typically used to solve these types of problems (graph traversal, backtracking, number theory, recursion, etc.). Please see the Programming Challenges Web site.
TopCoder Web Site
Another resource for contest problems deserves mention: the TopCoder Web site. TopCoder is a contest problem Web site where the best programmers from around the world are tracked and ranked. These sponsored competitions are handled in a variety of ways. Some are directed at collegiate level programmers, some are sponsored by organizations (like Sun Microsystems), and then there are the ones by special invitation only for the coding elite. This site is for true red-meat programmers only.
Some of the sharpest programmers in the world participate in contest programming, and you might be surprised at how they stack up. Take a look at the world rankings sometime. You have to go quite a way down the list before finding the first entry from the United States. As of this writing, a young man from Poland with the handle "Tomek" is the world's best contest programmer. Tomek has earned over $50,000 in coding competitions.
Chris Peters has 26 years of experience in the IBM midrange and PC platforms. Chris is president of Evergreen Interactive Systems, a software development firm and creators of the iSeries Report Downloader. Chris is the author of The OS/400 and Microsoft Office 2000 Integration Handbook, The AS/400 TCP/IP Handbook, AS/400 Client/Server Programming with Visual Basic, and Peer Networking on the AS/400 (MC Press). He is also a nationally recognized seminar instructor. Chris can be reached at
Chris Peters has 32 years of experience with IBM midrange and PC platforms. Chris is president of Evergreen Interactive Systems, a software development firm and creators of the iSeries Report Downloader. Chris is the author of i5/OS and Microsoft Office Integration Handbook, AS/400 TCP/IP Handbook, AS/400 Client/Server Programming with Visual Basic, and Peer Networking on the AS/400. He is also a nationally recognized seminar instructor and a lecturer in the Computer Science department at Eastern Washington University. Chris can be reached at
MC Press books written by Chris Peters available now on the MC Press Bookstore.
 |
||
 |
|
i5/OS and Microsoft Office Integration Handbook Harness the power of Office while exploiting the i5/iSeries database. List Price $79.95 Now On Sale
|
More than ever, there is a demand for IT to deliver innovation. Your IBM i has been an essential part of your business operations for years. However, your organization may struggle to maintain the current system and implement new projects. The thousands of customers we've worked with and surveyed state that expectations regarding the digital footprint and vision of the company are not aligned with the current IT environment.
TRY the one package that solves all your document design and printing challenges on all your platforms. Produce bar code labels, electronic forms, ad hoc reports, and RFID tags – without programming! MarkMagic is the only document design and print solution that combines report writing, WYSIWYG label and forms design, and conditional printing in one integrated product. Make sure your data survives when catastrophe hits. Request your trial now! Request Now.
Forms of ransomware has been around for over 30 years, and with more and more organizations suffering attacks each year, it continues to endure. What has made ransomware such a durable threat and what is the best way to combat it? In order to prevent ransomware, organizations must first understand how it works.
Disaster protection is vital to every business. Yet, it often consists of patched together procedures that are prone to error. From automatic backups to data encryption to media management, Robot automates the routine (yet often complex) tasks of iSeries backup and recovery, saving you time and money and making the process safer and more reliable. Automate your backups with the Robot Backup and Recovery Solution. Key features include:
Business users want new applications now. Market and regulatory pressures require faster application updates and delivery into production. Your IBM i developers may be approaching retirement, and you see no sure way to fill their positions with experienced developers. In addition, you may be caught between maintaining your existing applications and the uncertainty of moving to something new.
IT managers hoping to find new IBM i talent are discovering that the pool of experienced RPG programmers and operators or administrators with intimate knowledge of the operating system and the applications that run on it is small. This begs the question: How will you manage the platform that supports such a big part of your business? This guide offers strategies and software suggestions to help you plan IT staffing and resources and smooth the transition after your AS/400 talent retires. Read on to learn:
LATEST COMMENTS
MC Press Online