Garmin Programming Competition 2014

Yesterday at my university, Garmin was hosting the Programming Competition.

Competition like that is a great opportunity to practice programming, algorithms and problem solving skills.

We could form teams of 1-2 students. My partner was Daniel Wang. We could use following languages: C++, C#, Java and Python. We chose Java. We were using Eclipse IDE and git to share the code.

Organizers prepared very real-life problems.

Competitions had two parts:

  1. Read and perform simple input conversion (1 hour).
  2. Reuse code from Program 1 and do more complicated operations with input (3 hours).

We solved part 1 without any problems. Part 2 required two programs: 2A and 2B. We solved both, but our programs didn’t pass all test cases. In 2A: 3/5 test cases passed, in 2B: 4/5. There were points for correct solution and bonus points (depended on the time when solution was submitted). Additionally, there was a timer showing how many bonus points we could earn sending solution now.

You can find problems description here. Our solutions are available on Bitbucket repository. Be aware that it is bad code, written under time pressure and never refactored. However, efficient enough to pass required time constraints. This is how you write code during programming contests 🙂

After competition we asked organizers about test input sets and they sent it to us.

This is the description of the bug we had and how we fix it (you can skip this part if you don’t want to read the description of problems):

The issue we had, was reading (shift mod 26) straight from the input file. Because e.g. shift = 45 should be effectively shift = 19 (45 mod 26). The program should stop when shift = 0. Then, when original shift was e.g. 52 we had stored shift=0 and we stopped (which was wrong). We thought that we should stop when the ‘effective shift’ is 0. Unfortunately, the test cases were stopping when the ‘original shift’ was 0. Fix was pretty easy (we just store two values: shift and shiftOrig for each cell). It would be very hard to fix this without test cases from organizers 😉 It was like in real-life: small detail caused significant error.

The challenge during programming competitions is that you cannot get all test cases. This time, there were 1 sample input per program. Which make sense, because otherwise everybody could just hardcode expected solution 🙂 What is worse, you cannot see the program output (in case of runtime error). Fortunately, guys form Garmin were nice and when we asked, they were showing us the output (on their machine). It helped us (a lot) in fixing the runtime errors (during the competition).

The next event I am looking forward is Google Code Jam. It starts in April 11, 2014 (Friday). Registration begins in March 11. I really encourage you to sign up. You can learn what various problems you can face and what you should consider during writing your programs. Additionally you can practice, apply your programming skills and compete with the best programmers in the World.

Compilers course I had

In the last semester (Fall 2013) I had a pleasure to take course CIS706 – Translator Design (aka Compilers) with Dr Robby at Kansas State University. It was great experience! I think it is the best course I have ever taken.

The way how this course is designed is just amazing. During course about compilers you will also learn many other useful things:

  • Java
  • Eclipse
  • Source Control (git)
  • Unit Testing (JUnit) and TDD
  • Reading legacy code
  • Java Byte Code

How? You have to build the compiler for simple, Java based language called ExtendedStaticJava. You have 4 homeworks: parsing, building AST (Abstract Syntax Tree), type checking and byte code generation. For each of them you have ‘legacy’ code, which implements compiler for StaticJava. Your task is to extend it to handle ExtendedStaticJava syntax. For each homework you get around 100 Unit Tests. Your grade depends on number of passing tests. If all test are passing you get 100%. Implementation does not matter…but you might need to pay for workarounds later, because each homework is based on the code from previous one. I experienced this. I made a few hacks in first homework and then I needed to fix them during homework 2. It cost me extra time and I had to send incomplete solution. It is exactly how it goes in “Real World”!

For final project (last month of semester) we needed to create ExtendedStaticJava to C transpiler with Garbage Collector. Transpiler is source-to-source compiler. In other words: resulting code was C with Garbage Collector calls (GC was also implemented by us in C). We reused our homeworks (without byte code generation part) and generated C code (with GC calls) using StringTemplate.

Let’s take a look how all above help us to be better developers.

Most of students probably already know Java. If not – this course is the best time to learn. Java and C# are the most popular, static typing programming languages (today). When you learn one of them – it is easy to catch up with another. Java is still the most popular language in case of job offers (source):

traditional Language Job Trends - Indeed

Thus, probability that you will be programming in Java after you graduate is pretty high. When you will be programming in Java, you will be probably using Eclipse – its most popular IDE. Another ‘standard’ in industry is Source Control. If the company you are working for is not using it – you should change your company(!), because something wrong is going on there. If you are not familiar with git (leader in Open Source community, now being adapted by the industry) then this course is the best time to learn. Nowadays, even big companies (e.g. Microsoft) open sourcing their code (e.g. ASP.NET or SignalR), which is available through git.

Unit testing is very popular nowadays. Lots of commercial projects use this technique to ensure software quality and development stability. Many projects are also using TDD (Test Driven Development) approach. First your write the test (as the requirement) and then code. When test pass, you refactor the code. During the course we were using JUnit (for now: No.1 Unit Test Framework for Java). Additionally, when you learn how to work with Unit Tests, then picking up a different framework is very easy (even in different language).

Software Development is a team work. Because of that, you will need to read code of other developers everyday. In most of courses during your University career you need to create some applications from scratch. Sometimes you are working in team of 2 or 3 people. Then in your first job, you get 100 000 lines of code written by somebody else. Often without documentation and sometimes people who wrote this code are not working there anymore. In other words – you’re screwed. Compilers class will prepare you for that. During the course you will need to understand the existing code (StaticJava compiler), extend it and introduce some changes to get ExtendedStaticJava compiler working and Unit Tests passing.

Besides learning Java, you will also learn how JVM (Java Virtual Machine) and ByteCode are working. The idea of intermediate code is also used in C#: code is compiled to an Intermediate Language (IL) which then runs in the Common Language Runtime (CLR). It is very helpful for understanding how high-level code is translated to Assembly language.

It is also worth to mention about the essence of the course: compilers. The course is based on the popular Dragon Book. You will learn about every stage of compiling: lexical analysis, parsing, creating AST (Abstract Syntax Tree), semantic analysis, optimization and code generation. For parsing and AST creation you will use ANTLR, which is the most popular tool for such purpose nowadays. Finally you will get understanding, what is going on between your high-level code and electrical impulses flowing in your computer.

Even if you know all of these things (Java, Eclipse, git, Unit testing) it is still worth to take this class. You will apply your knowledge in practice and learn about compilers. This knowledge is useful not only to understand how computers work, but also to learn about algorithms and data structures, which are applied there.

You can find more information about CIS706 on compilers website. Moreover the StaticJava code is available on github: There is also nice Compilers Course by Stanford University on Coursera, which can be used as supplement for this class.