Skip to content

Latest commit

 

History

History
 
 

level0

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
problem
problem
 
 
README.md
README.md
 
 
level0
level0
 
 

README.md

Stripe CTF3: level0

Challenge

Your challenge is to make this code run much faster, without altering its output. In particular, you need to get it running at least as fast as our reference solution — when you submit a revision, we’ll tell you how our solution compares.

Write-up

The provided level0 file is a Ruby script that accepts text as input, and then returns that text with any words that are not in the dictionary wrapped in angle brackets.

#!/usr/bin/env ruby

# Our test cases will always use the same dictionary file (with SHA1
# 6b898d7c48630be05b72b3ae07c5be6617f90d8e). Running `test/harness`
# will automatically download this dictionary for you if you don't
# have it already.

path = ARGV.length > 0 ? ARGV[0] : '/usr/share/dict/words'
entries = File.read(path).split("\n")

contents = $stdin.read
output = contents.gsub(/[^ \n]+/) do |word|
  if entries.include?(word.downcase)
    word
  else
    "<#{word}>"
  end
end
print output

Running the provided test harness yields the following output:

$ ./test/harness
No test case supplied. Randomly choosing among defaults.
Fetching. URL: https://stripe-ctf-3.s3.amazonaws.com/level0/level0-znKqYRKUDB.json
About to run test case: level0-znKqYRKUDB
Beginning run.
Finished run
Test case passed. Your time: 5.291982 seconds. Benchmark time: 0.672016 seconds. You/Benchmark: 7.874785

The goal of the level was to make this code more efficient, so that it’s faster than the benchmark.

The improvement that first comes to mind is to use a set or a hash table instead of an array to store the dictionary entries. That way, any lookups can be performed in O(1) (constant time).

diff --git a/level0 b/level0
index f320a7d..1333337 100755
--- a/level0
+++ b/level0
@@ -7,10 +7,11 @@

 path = ARGV.length > 0 ? ARGV[0] : '/usr/share/dict/words'
 entries = File.read(path).split("\n")
+table = Hash[entries.zip(Array.new(entries.size, true))]

 contents = $stdin.read
 output = contents.gsub(/[^ \n]+/) do |word|
-  if entries.include?(word.downcase)
+  if table[word.downcase]
     word
   else
     "<#{word}>"

This solution is already faster than the reference solution:

$ ./test/harness
No test case supplied. Randomly choosing among defaults.
About to run test case: level0-znKqYRKUDB
Beginning run.
Finished run
Test case passed. Your time: 0.254984 seconds. Benchmark time: 0.672016 seconds. You/Benchmark: 0.379432

Level solved!

For more points, you could implement a trie data structure such as a MARISA trie to store the dictionary entries.

Other write-ups or solutions