30 Days of Code: Day 4

The day 4 challenge was more on logical operators and then classes vs instances. R wasn’t available, so I completed the challenge in Scala. Although it was a fairly trivial program, I took this as an opportunity to learn about primary and auxiliary constructors in Scala. 🙂 Another great thing about this challenge is that it required the programmer to do some data validation.

30 Days of Code: Day 3/Project Euler 125

The day 3 challenge was about if-else statements. Not much to say here. The syntax for if-else statements and logical operators in R is pretty much the same as it is in Java. The code is very simple and straightforward, so I’m not going to bother posting it.

In more interesting news, I decided to sign up for the ProjectEuler+ contest on HackerRank. From what I can gather, the challenges in this contest correspond to actual Project Euler challenges with minor differences, if any. I didn’t realize all this last night, so even though I had intended to do the Project Euler problems in order (which means I should be working on #15 next), I ended up solving #125. And actually since I did the HackerRank version, I ended up solving a more general and more difficult problem than what’s given on Project Euler.

In the interest of space and time, I will discuss only the problem as it’s stated on Project Euler here. My solution is on GitHub, written in Java. A few notes about this solution:

• The final answer will lie outside the range of an int, so another type such as long or BigInteger must be used.
• My first attempt at a solution checked all integers less than the cap to see if they were palindromes, and then if they were, checked to see if they could be expressed as the sum of consecutive squares. This is very slow. It is much quicker to construct sums of consecutive squares, and then to check if any of these are palindromes. However…
• … this introduces the potential problem of overcounting palindromes if they can be expressed as the sum of consecutive squares in two or more distinct ways. But does this actually happen? The answer is yes: 554455 = 9² + 10² … + 117² + 118² and also 554455 = 331² + 332² + 333² + 334² + 335². Another one to look out for is 9343439.* This problem is easily dealt with by caching the results. I needed something pretty speedy, so I used a HashSet.

That’s all for the problem as stated on Project Euler. As I mentioned before, the corresponding problem on HackerRank is similar but more general and more difficult. I would be happy to post and/or discuss my solution to the HackerRank version upon request.

* Extra Credit: Is there a palindrome that can be expressed as the sum of consecutive squares in three distinct ways?

30 Days of Code: Day 2

The day 2 challenge was all about arithmetic operators. The task was pretty simple: given the (raw) price of a meal, the tip percentage, and the tax percentage, calculate the final price rounded to the nearest dollar. Initially R was not in the list of programming languages for this challenge, but a moderator kindly added it later. Thus I have two implementations: one in Scala, and one in R. My solution in R may be found here.

Things I learned about R while doing this challenge:

• Stdin != Stdin(). At least 75% of my time was spent on figuring out how to pipe stdin to R.
• Vectors in R use 1-based indexing.
• The modulus operator in R is %% as opposed to % as it is in several other languages (e.g. Java).
• R documentation is … difficult for me to understand. It seems like it was written for experts by experts. And frankly when I was reading through help forums, responses to questions were less than gracious, to say the least.
• Along those lines, I think the default separator for the cat function is a space, as opposed to no separator at all. I can’t find any documentation to confirm this though.

30 Days of Code: Day 1

This challenge was somewhat confusing.

First, the description of the 30 days contest says that “The tutorial is based on Java, but you can also choose other popular languages to submit your solution.” Ergo I was expecting language-agnostic challenges, but the day 1 challenge is based on data types in Java.

I read through the discussion board and many people, especially those who prefer languages other than Java, simply hard-coded the expected output. Some argued that this challenge was intended to be a cognitive exercise (given a piece of data, identify the type) and not a programming challenge per se, thus the solution was intended to be hard-coded. I’m not sure what the intent was, which is a shortcoming of the challenge.

In any case, as I mentioned in the last post I intended to do all of the challenges in R. However R was not available for this challenge, so I completed it in Scala, which before this challenge was completely foreign to me. I’m not going to bother posting my code because, frankly, it’s stupid and not representative of my skills.

Here’s hoping tomorrow’s challenge will be better. I was disappointed with this one, although I did learn some of the basics of Scala, so it wasn’t a complete loss.

Happy New Year/30 Days of Code: Day 0

To be kicking off the new year, I’ll be participating in HackerRank’s 30 Days of Code. Funny story: I signed up for this contest by accident and didn’t see a way to withdraw from it. It’s meant for introductory programmers, so it’s probably below my skill level for both Java and Python. Since I can’t figure out how to withdraw, I might as well do it, but I also wanted to at least get something out of it. So I’ve decided to depart from my usual coding in Java/Python/C++ and do all 30 challenges in R.

I’ve worked with R a little bit for some data mining projects (e.g. I’ve always used R to do k-means clustering), but I have relatively little exposure. Hopefully this challenge will help me to get more familiar with the language.

The first challenge was a variant of Hello World. Since it’s so short and trivial, I’m not going to bother putting it on GitHub. Here you go:

cat("Hello World.", "Welcome to 30 Days of Code.", sep="\n")

We Wish You a Mathy Christmas

Greetings from Chicago. This is just a brief post to say that I’m not dead and I haven’t abandoned this blog. I’ve been on vacation taking a much-needed break to recharge my batteries. I’ve actually done a fair bit of coding on HackerRank – it really passes the time on the train – but most of it has been fairly trivial so I haven’t been blogging about it.

In other news, Springer has made several math and physics books available for free just in time for some post-Christmas acquisitions, and they’re available here. I browsed the titles and noticed that Bollobás’ Modern Graph Theory book is one of the free downloads. I have an hard copy of this book, as it was the text for a graph theory course I took as an undergrad while studying abroad in Budapest. Then when I was a graduate student at the University of Nebraska-Lincoln, Bollobás was giving a guest lecture so I went and spoke with him afterwards. I greeted him in Hungarian, told him about studying in Budapest, and asked him to autograph my book (he obliged). My text is in Omaha right now; I can post a picture of the autograph when I return in January.

As a final note, I had planned on summarizing my Fall 2015 semester in a post, but there has been a snafu with my grades, so I’m waiting for that to be resolved before I do the recap.

Project Euler 7 – 14

Happy Thanksgiving from Chicago! I’ve uploaded a slew of Project Euler problems. For most of these, a brute force method worked out okay:

• Project Euler 7 (solution in Java)
• Project Euler 8 (solution in Java): Another Project Euler problem where the BigInteger class must be used. My advice to other Project Euler coders and to my future self: if you’re sure about the correctness of your method, and your program works correctly with the example data but comes up with the incorrect solution for the test data, check your types!
• Project Euler 9 (solution in Java)
• Project Euler 10 (solution in Java): I got into a bit of trouble with this one trying to make my solution efficient early on instead of going for something that works and optimizing later. Reminds me of Knuth’s observation from his 1974 Turing Award lecture that “premature optimization is the root of all evil (or at least most of it) in programming.”
• Project Euler 11 (solution in Java)
• Project Euler 12 (solution in Java): While it’s not necessary for an acceptable solution, a simple summation formula can be used to generate triangle numbers.
• Project Euler 13 (solution in Java)
• Project Euler 14 (solution in Java): My brute force method took about 27 seconds to run. This is an acceptable time, but I was feeling feisty when I wrote this program, so I did some optimization. I observed that if a number is part of, but not the first number in a Collatz sequence, then it cannot produce a longest chain. So I created an array of one million numbers and every time I generated a sequence, I marked the numbers less than one million that were part of the sequence (other than the first number). Then there is no need to generate the Collatz sequences that begin with the marked numbers. For example: 13 produces the chain 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1. In this case we know that 40 and 20 do not generate longest chains, so we need not bother generating the Collatz sequences that begin with 20 or 40. Kind of sieve of Eratosthenes-ish, no? Anyway, this optimization cut about 10 seconds off my runtime.

Tools of the Trade: ShareLaTeX

I decided to take a break from posting my code and write about something else. A while back one of my friends from undergrad – now a postdoc at the University of Arizona – posted this on facebook:

This inspired me to start what will hopefully become a series of posts about tools that are useful to grad students and people in the tech field. To kick off this series, I’ll be singing the praises of ShareLatex, an online collaborative LaTeX editor.

A brief background for those unfamiliar with LaTeX: Back in late 60’s, a very awesome man named Don Knuth was in the early stages of writing a very awesome set of books called The Art of Computer Programming, affectionately known as TAOCP. The first three volumes had all been published by 1973, and in 1976 Knuth was working on some second editions and realized that he was very unhappy with the typesetting options at the time. So he did what any reasonable person would do: he went away and within 2 years had invented his own typesetting language called TeX, which he continued to develop and improve over the next decade. TeX is widely (and in some fields, almost exclusively) used today.

LaTeX is a TeX-based document preparation preparation system (kind of like a cross between a word processor and a markup language) and it basically makes TeX way easier to use. ShareLaTeX, as I’ve already mentioned, is a LaTeX editor that is both online and collaborative.

I gotta say, I love ShareLaTeX. Before I knew about its existence I used MikTeX, and while I could get by with it, I wouldn’t say that it’s particularly user-friendly. Then one of my fellow grad students told me about ShareLaTeX, and I wondered how I ever got by without it. All of the conference and journal papers I write are done in ShareLaTeX. Sometimes I share them with co-authors so we can collaborate. All of my exams and assignments for the probability models course I’m taking this semester are done in ShareLaTeX. My justification for my solution to the Rosalind IPRB problem that I shared in the last post was created in LaTeX. ShareLaTeX can be used to create other kinds of documents as well. My CV, for example, was created in ShareLaTeX. I use ShareLaTeX on an almost daily basis now. If you do any sort of academic/mathematical/technical writing, you should be using TeX. And unless you spend a lot of time working offline or you to collaborate with multiple people (see my list of cons below), you should be using ShareLaTeX.

Pros:

• Free. Kinda. There are, of course, plans that come with a price tag. I have always used the free version, and this has *almost* always done everything that I have needed and wanted to do. The paid plans still look pretty reasonably priced to me, especially with the student discount.
• Nothing to download. This was a major plus for me. You just create a free account and you’re ready to go.
• Beginner-friendly. With a library of templates to choose from and excellent documentation (which helps even seasoned LaTeX users like me), ShareLaTeX is a perfect place for a beginner to learn TeX.
• Collaboration. While this is a feature that ShareLaTeX likes to put front and center, I actually don’t use it all that much. It’s a pretty neat feature – two people can be editing the same document at the same time and you can see what the other one is doing, but most of my projects as of late have been solo projects. There’s also the restriction that with the free version, you can only collaborate with one other person.

Cons:

• Online. If you want to work offline, you have to use another TeX editor. Earlier this semester I had to download a project from ShareLaTeX to work offline when I was finishing up a conference paper on an international flight. 
• Limited collaboration (free version only). As I mentioned above, unless you’re willing to shell out some money, you’re limited to only one collaborator per document. Since I haven’t been using this feature anyway, it’s not that big of an issue for me.

 

 

Project Euler 6 & Rosalind IPRB

I decided to post my solutions to the sum square difference problem from Project Euler (solution, written in Java) and Mendel’s First Law from Rosalind (solution, written in Python) together because both of them have very nice O(1) solutions.

The sum square difference problem doesn’t require any math beyond Calculus I, or wherever students learn summation formulas nowadays:

The Mendel’s First Law problem requires some knowledge about conditional probability. The mathematical justification for my solution can be found here.

Rosalind: HAMM Problem

My solution to the Counting Point Mutations Rosalind problem is here, written in Python.

Even though this is a fairly trivial problem, it caught my eye about a month ago when I was reading a paper titled “Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems” for my MS in CS capstone course. I had seen Levenshtein distance before and last summer I received a crash course in quantum computing, but it was still a rough paper for me to get through. When I come across a tough paper, I try to do four things:

1. reassure myself that it’s okay if I can’t understand everything in the paper
2. understand the problem statement
3. understand the results
4. pick up at least one new technical idea

If I can do those four things – especially the last three – then I consider it a successful reading of the paper.