Facebook Hacker Cup – Beautiful Strings

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 i^th 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