Facebook Hacker Cup – Beautiful Strings

[This article was first published on Frank Portman, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
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
<span class="line"><span class="c1">###### My solution:</span>
</span><span class="line">inputs <span class="o"><-</span> <span class="kp">readLines</span><span class="p">(</span><span class="s">"inputs.txt"</span><span class="p">,</span> n <span class="o">=</span> <span class="m">-1</span><span class="p">)</span>
</span><span class="line">
</span><span class="line">m <span class="o"><-</span> inputs<span class="p">[</span><span class="m">1</span><span class="p">]</span>
</span><span class="line">m <span class="o"><-</span> <span class="kp">as.numeric</span><span class="p">(</span>m<span class="p">)</span>
</span><span class="line">inputs <span class="o"><-</span> inputs<span class="p">[</span><span class="m">2</span><span class="o">:</span> <span class="p">(</span>m <span class="o">+</span> <span class="m">1</span><span class="p">)]</span>
</span><span class="line">
</span><span class="line">outputs <span class="o"><-</span> <span class="kt">c</span><span class="p">()</span>
</span><span class="line">
</span><span class="line"><span class="kc">letters</span> <span class="o"><-</span> <span class="kc">letters</span>
</span><span class="line">
</span><span class="line">
</span><span class="line"><span class="kr">for</span> <span class="p">(</span>i <span class="kr">in</span> <span class="m">1</span><span class="o">:</span>m<span class="p">)</span> <span class="p">{</span>
</span><span class="line">
</span><span class="line">  x <span class="o"><-</span> inputs<span class="p">[</span>i<span class="p">]</span>
</span><span class="line">  x <span class="o"><-</span> <span class="kp">tolower</span><span class="p">(</span>x<span class="p">)</span>
</span><span class="line">
</span><span class="line">  y <span class="o"><-</span> <span class="kp">unlist</span><span class="p">(</span><span class="kp">strsplit</span><span class="p">(</span>x<span class="p">,</span> split<span class="o">=</span><span class="s">""</span><span class="p">))</span>
</span><span class="line">  y <span class="o"><-</span> y<span class="p">[</span><span class="kp">which</span><span class="p">(</span>y <span class="o">%in%</span> <span class="kc">letters</span><span class="p">)]</span>
</span><span class="line">
</span><span class="line">  table <span class="o"><-</span> <span class="kp">table</span><span class="p">(</span>y<span class="p">)</span>
</span><span class="line">  table <span class="o"><-</span> <span class="kp">sort</span><span class="p">(</span><span class="kp">table</span><span class="p">,</span> decreasing <span class="o">=</span> <span class="kc">TRUE</span><span class="p">)</span>
</span><span class="line">
</span><span class="line">  table <span class="o"><-</span> <span class="kp">as.numeric</span><span class="p">(</span><span class="kp">table</span><span class="p">)</span>
</span><span class="line">
</span><span class="line">  <span class="kr">for</span> <span class="p">(</span>j <span class="kr">in</span> <span class="m">1</span><span class="o">:</span><span class="kp">length</span><span class="p">(</span><span class="kp">table</span><span class="p">))</span> <span class="p">{</span>
</span><span class="line">
</span><span class="line">      <span class="kp">table</span><span class="p">[</span>j<span class="p">]</span> <span class="o"><-</span> <span class="p">(</span><span class="m">27</span> <span class="o">-</span> j<span class="p">)</span> <span class="o">*</span> <span class="kp">table</span><span class="p">[</span>j<span class="p">]</span>
</span><span class="line">
</span><span class="line">  <span class="p">}</span>
</span><span class="line">
</span><span class="line">  outputs<span class="p">[</span>i<span class="p">]</span> <span class="o"><-</span> <span class="kp">paste</span><span class="p">(</span><span class="s">"Case #"</span><span class="p">,</span> i<span class="p">,</span> <span class="s">": "</span><span class="p">,</span> <span class="kp">sum</span><span class="p">(</span><span class="kp">table</span><span class="p">),</span> sep <span class="o">=</span> <span class="s">""</span><span class="p">)</span>
</span><span class="line">
</span><span class="line"><span class="p">}</span>
</span><span class="line">
</span><span class="line">outputs <span class="o"><-</span> <span class="kp">as.character</span><span class="p">(</span>outputs<span class="p">)</span>
</span><span class="line">
</span><span class="line"><span class="kp">writeLines</span><span class="p">(</span>outputs<span class="p">,</span> con <span class="o">=</span> <span class="s">"output.txt"</span><span class="p">,</span> sep <span class="o">=</span> <span class="s">"\n"</span><span class="p">)</span>
</span>

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
<span class="line"><span class="c1">###### The output:</span>
</span><span class="line">Case <span class="c1">#1: 2138</span>
</span><span class="line">Case <span class="c1">#2: 5113</span>
</span><span class="line">Case <span class="c1">#3: 6469</span>
</span><span class="line">Case <span class="c1">#4: 5433</span>
</span><span class="line">Case <span class="c1">#5: 5991</span>
</span><span class="line">Case <span class="c1">#6: 2081</span>
</span><span class="line">Case <span class="c1">#7: 1358</span>
</span><span class="line">Case <span class="c1">#8: 4877</span>
</span><span class="line">Case <span class="c1">#9: 5982</span>
</span><span class="line">Case <span class="c1">#10: 348</span>
</span><span class="line">Case <span class="c1">#11: 6004</span>
</span><span class="line">Case <span class="c1">#12: 3555</span>
</span><span class="line">Case <span class="c1">#13: 3593</span>
</span><span class="line">Case <span class="c1">#14: 754</span>
</span><span class="line">Case <span class="c1">#15: 1336</span>
</span><span class="line">Case <span class="c1">#16: 5495</span>
</span><span class="line">Case <span class="c1">#17: 5749</span>
</span><span class="line">Case <span class="c1">#18: 3897</span>
</span><span class="line">Case <span class="c1">#19: 3191</span>
</span><span class="line">Case <span class="c1">#20: 646</span>
</span>

To leave a comment for the author, please follow the link and comment on their blog: Frank Portman.

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.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)