Facebook Hacker Cup – Beautiful Strings
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
Now that the Facebook Hacker Cup is coming to an end I figured I’d post my solution to one of the challenges. Unfortunately I only made it to Round 1, but I was able to answer this rather interesting Qualification Round problem.
The Problem:
When John was a little kid he didn’t have much to do. There was no internet, no Facebook, and no programs to hack on. So he did the only thing he could… he evaluated the beauty of strings in a quest to discover the most beautiful string in the world.
Given a string s, little Johnny defined the beauty of the string as the sum of the beauty of the letters in it.
The beauty of each letter is an integer between 1 and 26, inclusive, and no two letters have the same beauty. Johnny doesn’t care about whether letters are uppercase or lowercase, so that doesn’t affect the beauty of a letter. (Uppercase ‘F’ is exactly as beautiful as lowercase ‘f’, for example.)
You’re a student writing a report on the youth of this famous hacker. You found the string that Johnny considered most beautiful. What is the maximum possible beauty of this string?
The input file consists of a single integer m, followed by m lines.
You can find the input file here.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | ###### My solution: inputs <- readLines("inputs.txt", n = -1) m <- inputs[1] m <- as.numeric(m) inputs <- inputs[2: (m + 1)] outputs <- c() letters <- letters for (i in 1:m) { x <- inputs[i] x <- tolower(x) y <- unlist(strsplit(x, split="")) y <- y[which(y %in% letters)] table <- table(y) table <- sort(table, decreasing = TRUE) table <- as.numeric(table) for (j in 1:length(table)) { table[j] <- (27 - j) * table[j] } outputs[i] <- paste("Case #", i, ": ", sum(table), sep = "") } outputs <- as.character(outputs) writeLines(outputs, con = "output.txt", sep = "\n") |
To start, I read the input.txt (as provided by Facebook) into R, saving each line of input as a separate character string in the ‘inputs’ vector. I then saved the first entry of ‘inputs’ as m in accordance with Facebook’s description of the problem and then subsetted the whole vector to only include the actual strings we are to analyze.
After allocating some memory for an outputs vector and using R’s built in letters variable (it might have been redundant to name it as a variable) I began a for loop to actually calculate the maximum beauty of each string. Inside the for loop, I created local variables x and y. x was simply the ith input in all lowercase (for homogeneity). I then created y to split the strings into vectors which contained one character per entry and removed all non-letter components through subsetting.
From there, I created a table to look at the number of times each letter appeared in the i’th string and sorted it by decreasing. A nested for loop assigned values to the elements in the table that I had constructed. I assigned 26 to the letter that appeared most frequently, 25 to the second most frequent, and so on. In this way we calculate the MAXIMUM POSSIBLE beauty of each string.
Finally, I filled the outputs vector by creating a string in correspondence with Facebook’s requirements. Once we rinse and repeat this process a total of m times, we have a complete outputs vector that stores the maximum beauty of each string in inputs.txt.
In order to produce the outputs as a .txt file to upload to Facebook, I employed a simple writeLines
function which placed every element of the outputs vector on a separate line.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | ###### The output: Case #1: 2138 Case #2: 5113 Case #3: 6469 Case #4: 5433 Case #5: 5991 Case #6: 2081 Case #7: 1358 Case #8: 4877 Case #9: 5982 Case #10: 348 Case #11: 6004 Case #12: 3555 Case #13: 3593 Case #14: 754 Case #15: 1336 Case #16: 5495 Case #17: 5749 Case #18: 3897 Case #19: 3191 Case #20: 646 |
R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.