Stripe CTF3: Distributed Systems is live
stripe-ctf.com
stripe-ctf.com
But seriously, spacing would be awesome.
I'm sure Stripe has a similar story.
We all agree, more careful spacing would be great. Oh well! :)
Props in general, I just feel like Level1 was kind of a brick wall for me.
Jura vaibxvat tvg va n furyy ybbc, lbh'er jnfgvat lbhe gvzr sbexvat. Qbvat guvf va n fvatyr cebprff jvyy fcrrq vg hc n ybg.
It is possible in ruby, that's what I used first, though the ref implementation is in ruby, so a single process may not cut it unless you are lucky. Keep trying too if you are solving it but not quite making it in time as you're competing against a variable time to complete on the other side.
It is a bit tricky because you're competing against random timings for the bot miners, but you need to mine before the bots do, so you need to speed up finding a commit hash, then do the commit. I hope that is useful without giving too much away.
remote: > Your submission has been placed in the queue. remote: > Kicking off a build for your submission (running `./build.sh`). remote: > `./build.sh` succeeded remote: > Kicking off 3 trials. Here goes... remote: > Started running Trial 0 remote: > Started running Trial 1 remote: > ERROR: There was an internal error scoring Trial 0. If this error persists, please let us know at ctf@stripe.com and include the following error token: err_3MRLt7sxWqqD4C To lvl0-xkzdabbt@stripe-ctf.com:level0 7fcfd3d..17d0e35 master -> master
My code looks to be working because the test ./test/harness says that tests pass.
I don't know Ruby, but I can guess what it is doing basically:
1. Read a list of words from a file with an input path or a default path
2. Take the runtime input from the user with any number of words before carriage return (I guess the words are separated by spaces)
3. Do a loop to compare each of the input words to lower case against the words in the list loaded from the file. If there is a match print out the original word, other wise print out something wrap up the word.
It's a O(NxM) algorithm. If the data set is small, we won't see to much difference. Otherwise, we need to concern about better algorithm to improve the speed.
1. Sort the list from the file (remove duplicates)
2. Always check the either half to reduce the number of checking in the list
3. Sort the input list (save the number of duplicates)
4. Print the duplicates directly without comparison again etc.
This way the runtime can be improved to O(N*lg M). This may not be the best algorithm. I'd like to hear from you about better solutions.
You can google it more. I don't have time to find out about the Big O footprint for both now. Here is one link discussing about it:
http://stackoverflow.com/questions/7975802/when-to-use-hashm...
We usually implement code on the application level, so we don't really care about the underlying algorithms. But if we have to implement on the system level, we do care about the how to manipulate the memory and number of executions, like Big O.
Look at my another comment, hash may not be always better than list.
For me, it makes more sense to receive the detailed information, especially the system condition and restriction for trouble shooting and problem solving, followed by brainstorming, instead of going directly to fix code. Because we are used to the pattern to make minimum code change, especially in production. If the code should be completely changed, then we need to know the requirement and re-implement it. Sounds like we have different convention though.
If there is no language constraint and the system resource constraint, to the problem we have understand so far, using Java will be the fastest and easiest way without hashmap.
Load the complete file as a string (depending on how the size of the data set, up to 2^31 - 1), then using string.indexOf() function will get the best result.
The underlying algorithm for indexOf() is implemented by JVM in C code which is must fast than any other implementation.
My gut told me that it's weird to use hashmap to do string lookup. Everybody knows hashmap is used to lookup key-value pairs. The real reason for not using hashmap here are:
1. hashmap's lookup Big O is O(n), but not the build cost. if the data set size is huge, it takes long time to build the hashmap since every new element exceeded the initialCapacity being added needs a rehash
2. the underlying implementation of indexOf() will use a sort of algorithm called "automata" or something else to do a fast search within a string.
So there are lots of alternative solutions. Don't always think there is only one. I'm not in this field, and I'm not interesting to get into to it too much. But I don't think the best answer is that tiny change.
This is why I suggested to consider if you are doing application level optimization or changing system level algorithm. Building software is a lot more than code manipulation. Understanding requirement is the first step in the SDLC (Software Development Life Cycle).
The best answer is one that passes the test, and using ruby it is pretty easy to do so, but you could do it any way you like.
1) Hashmap 2) string index
which is better? I think about it what I'm going to do if I'm using it in my web application.
First the answer is still relying on the size of the data set. If the dictionary is huge, say up to 4G, I'd use string index vs hashmap, because the memory space is expensive. And how to break into mutiple sub strings is another performance tuning issue.
If the problem is simple enough with not too large data set, hash will be working.
When I mentioned "one way", I mean the "best way". So now you are talking about "The best answer is one that passes the test". So do you mean that all the answers which can pass the test are the best answers, or there is only one best answer which can pass the test? I don't put my personal preference on the problem solving. I'm always looking for the best solution for a particular problem under certain condition and constraints. Once we figure out the answer, coding implementation using which language does not matter that much, unless Ruby does not support the same algorithm of string.indexOf() as Java does.
Hope this discussion helps.
Yes, what I was trying to say was that the performance required is just that to pass the test, not more, and the dataset is a few MB here, not 4GB. This is actually really similar to a lot of problems in real life; you can spend ages trying to find a platonic solution when a simple solution works fine given the dataset and requirements (return an answer within 200ms for example). Sometimes simpler is better, and even if you can improve the solution, it won't really matter to whoever pays the bills.
There are lots of solutions though, I tried a few just out of curiosity and you can of course improve on a hashmap - the possible solutions to a problem this small are pretty similar whatever language you choose, and sometimes when a dataset is this small other more complex solutions are slower (unless you preindex).
I don't need to spend too much time on finding the solutions, they are on top of my head. Depending on different conditions I'll use different solutions. 4GB is the upper bound of string indexing, if it's being used for web indexing, it's still not enough. If in this case it is used in document indexing for enterprise level with a few MG, it's fine for using any of them. But the difference is the score you get.
I guess eventually you will pick hashmap solution because you have the indexes built in the lookup, which makes more sense over other solutions, but you (or they) don't give the condition out in the first place. How can we discuss based on that? Looks like I pretty much wasted my time on this issue and was taught to learn that making things simple is better. Thank you.
Coding is the last thing we need to concern since various languages are available to implement. System architecture design, data modeling, application performance, security and algorithms are more important.
Regarding the language itself, I understand that Ruby and Python are quick and easy, but that's not for real production systems. Lots of teenagers are using it now. Maybe you are not happy to hear like that. Here are two blog articles regarding it:
http://bingobo.info/blog/contents/do-not-rely-on-other-platf...
http://bingobo.info/blog/contents/having-a-solid-foundation-...
The original words was "You're giving them a throat to choke". The minimum set of tools is always necessary either on Windows or Linux, especially from Open Source. Just make sure don't take the risk of your application to do re-implementation later.
:)
BTW, if you are not happy to hear that, I'd like to know your opinion.
There are tons of high-profile sites using ruby or python in production. Reddit is written in Python, Twitter got quite a bit of mileage out of Ruby...
What I'm talking to are the hackers who are aiming for running startup companies and those who are going to grow to be software engineers.
I don't see the original code is a huge issue per se which requires 19 levels? of improvement? I'm curious about how you guys move on though. Will appreciate if you can keep post your solution and progress.
I guess at the end of the entire program, people may learn how to send the query to multiple indexing servers in a concurrent (I prefer this than "distributed") system and then gather together of all the results. At the end of it, it shows how advanced algorithms Google search engine is used to index terabyte of data.
Is that the ultimate solution for a web of data? Take a look of the discussion: http://bit.ly/1f7xIve
From the "best" score I was worse than it by 150 or something. Not that I care really.
http://www.algolist.net/Algorithms/Binary_search
This is my original answer! I should not sort the input list though since it's not necessary.
But is string.indexOf() will be even faster?
Edit: And to be clear, you should use the hash solution anyway since it is O(n+m).
http://stackoverflow.com/questions/1055243/is-a-java-hashmap...
But I couldn't agree with you about O(n+m) because we cannot hash on the input set as well since that way we will lost the sequence order. Then the caching may help or use LinkedHashmap.
However according to the Big O, linear increase does not count. So the Big O is anyway O(n) when n is near m, it's O(2n) then it's O(n), or n >> m or n << m, it is O(n) or O(m). But runtime, there might be some difference. Again, in most of the normal applications using relational database, we will not use huge memory to store extremely large hashmap. We'll put a cap of the size. Indexing unstructured data is a different story.
The time required to do a hashmap lookup should be small and of constant time. If you did cache it somehow, you would need a way to do lookups of what was cached (which might require another hashmap lookup.)
Edit: I'm saying that trying to cache hashmap lookups might not save you any time and is probably not worth thinking about. Another poster has indicated that the solution described above (without trying to do some kind of caching of duplicates) should be sufficient to pass the Stripe CTF stage, so I would recommend just implementing that.
If the size of the input data set m << dictionary data size n, it's a worth trying for caching.
Otherwise, the input word list should be loaded into LinkedList instead of ArrayList which is the most expensive list to be used when we need to access by its index number. Using Set will lose its order.
(I'm just brainstorming the steps for discussion instead of writing code. I'd like to know the best solution and steps to improve it from you guys.)
It does not affect the Big O level I mentioned in sorting of the word list loaded from the file. Looks like it's the necessary step.
It looks like you have another in-progress Git operation, and we limit you to one concurrent operation. Waiting 2s (attempt 1/3) It looks like you have another in-progress Git operation, and we limit you to one concurrent operation. Waiting 2s (attempt 2/3) It looks like you have another in-progress Git operation, and we limit you to one concurrent operation. Waiting 2s (attempt 3/3) ERROR: Timed out waiting for your other Git operation to complete. Try again once it has finished. fatal: Could not read from remote repository.
Please make sure you have the correct access rights and the repository exists.
first push:
git push warning: push.default is unset; its implicit value is changing in Git 2.0 from 'matching' to 'simple'. To squelch this message and maintain the current behavior after the default changes, use:
git config --global push.default matching
To squelch this message and adopt the new behavior now, use: git config --global push.default simple
See 'git help config' and search for 'push.default' for further information.
(the 'simple' mode was introduced in Git 1.7.11. Use the similar mode
'current' instead of 'simple' if you sometimes use older versions of Git)Counting objects: 37, done. Delta compression using up to 4 threads. Compressing objects: 100% (33/33), done. Writing objects: 100% (36/36), 897.66 KiB | 0 bytes/s, done. Total 36 (delta 4), reused 14 (delta 0)
When I make an account.
EDIT I probably already had one. Maybe I failed level -1 for that.
version `GLIBCXX_3.4.18' not found (required by ./level0)
:-(And then the output of ldd on ./level0
linux-vdso.so.1 => (0x00007fff5cdca000) libstdc++.so.6 => /lib64/libstdc++.so.6 (0x0000003337400000) libgcc_s.so.1 => /lib64/libgcc_s.so.1 (0x0000003333c00000) libc.so.6 => /lib64/libc.so.6 (0x0000003332800000) libm.so.6 => /lib64/libm.so.6 (0x0000003332c00000) /lib64/ld-linux-x86-64.so.2 (0x0000003332400000)
I know the problem is I am still dynamically linking glibc and whatever system I am running on doesn't have a new enough glibc. I am going to take another crack at it later and try to get it fully statically linked, but once you get to statically linking the C runtime I need to invoke my google foo and it is more time then I had on my lunch break.
contents = ARGV.length > 1 ? File.read(ARGV[1]) : $stdin.read
That's just allowing you to send the test files in on the command line. From there, you can measure the time using PowerShell's Measure-Command like so:
Measure-Command {ruby .\level0 "test/data/words" "long.txt"}
Assuming ruby is in your PATH and the "test/data/words" is a renamed words dictionary file. It's a little work but you can definitely do it on Windows. I'm working on getting the python test harness to work on Windows.
It's a bit of a shame the test harness isn't Windows compatible; it's rather small, and it doesn't look like the fixes required would have been very difficult.
[error] import java.nio.file._
Isn't it supposed to start with a TXT file and a sample?
Which I find alternatingly very frustrating and very hilarious.
Going to understand git internals a lot more before I'm done with this.
> I might have to switch to a faster language :(
Probably not, I did it in python.
There's a systems problem in how the miner is architected that you can tweak to give you a better chance of winning the race.
meh.
Just make sure that the level0 file is an executable file and change the crunchbang to run python instead of ruby.