I just want to do some benchmarking of different programming languages. So here is a tip: You can use as many characters as you want. In the end there is only the time your program needed.
So, here is the Task:
Task
After searching for a good task that would require a lot of computation, I came up with the problem Is a word in a given Type-1 grammar?
For people not knowing what this is: Formal Grammar Chomsky-Hierarchy
Maybe there is a better algorithm but I came only up with brute forcing.
So, write a code that brute forces the Grammars as fast as possible.
Rules
- Parallel execution is allowed
- Delete your cache after every tested word
- Add your complete compiler command for optimized result
- You can use any algorithm and language you want, as long as the job gets done.
- Add to your answer what files are read/how to set the files that should be read.
I Guarantee
- Input is always well formatted
- Variables are always capital letters, Terminals always small ones
- Words only consist of Terminals
- No empty Word
Input
For equal footing we need to define what the input looks like. The input is a file. I write multiple grammars and words in one file. The structure can be described with following Pseudocode:
foreach(Grammar G) do
write('{');
foreach (Variable V in G) do
write(T + ',');
od
deleteLast();
write('}');
linebreak();
write('{');
foreach (Terminal T in G) do
write(V + ',');
od
deleteLast();
write('}');
linebreak();
write('{');
foreach(Production P in G) do
write(P + ',');
od
write('}');
linebreak;
write(StartSymbol(G));
linebreak;
foreach(Word W for G) do
write(W + ',');
od
deleteLast();
linebreak;
od
deleteLastLinebreak();
Output
The output has to be put in a file as well. The formatting of the output does not matter. It should be recognizable which result belongs to which word.
Example
Here is an example written in C# by myself.
Test System
The system the code will run on is following:
- Arch Linux
- RunTime you need (if available; Please add in answer)
- Intel i7-4700MQ 3.4GHz
- 16GB RAM
How do I test
After the code is compiled I'll run a bash script that runs your program a certain amount of times and calculates the average and median run time.
Good Luck and may the best code win.
My Benchmark: Not completed after 8-9 hours of runtime.
My Benchmark (after changing some words):
- mean: 39.5157
- median: 39.448687194
PS: Here is the originally planned input, which took ages with my program. Grammars are slightly changed in the new input and words are way shorter.