четверг, 7 августа 2014 г.

Google hiring task (first 10-digit prime in e) in bash one-liner

Hi All,
I was on a bit of short vacation, and according to my vacation rules I'm trying to not to think about my work-related stuff, or any computer-related stuff overall. I was not successfull completely with that target thanks to my smartphone :) but tried to. But during my train voyage I was quite bored, so, I was thinking about task which my friend and fellow colleague master Victor mentioned - it was famous foto of billboard which was used by Google for hiring purposes back in 2004 -

And master Victor said - "assuming you know about the e constant, solve in a Bash one-liner to get a job @Google :)" - and I was thinking about that during my trip. And I was succeded - with some remarks, of course.
Disclaimer: IMHO solving this thask in Bash is NOT GOOD, because it violates first principle of engeneering - "choosing the right tool for the job" - and bash definitely is not good for that task.
So, first I tried to find is that task could be solved in "pure bash" and I found that it is not. You can check that thorough investigation to find out that calculating e with required precision is not posible in bash because of integer overflow.
So, let's "cheat" - i.e. use some tools with bash. Which tools are suitable and not count as cheating? I think bc is absolutely required for math operations, also other unix tools, like sed and coreutils are also OK.
Let's divide task into pieces:

1. Generate e with enough precision (1000 digits)?
I found that you can easily do it with bc:
root@ubuntu:~# echo "scale=100;e(1)" | bc -l 2.718281828459045235360287471352662497757247093699959574966967627724\ 0766303535475945713821785251664274

2. We need to go through digits of e and take each 10 digits to check, then move to 1 digit forward and repeat, and so forth. We can do it using temporary file and "cut -cX..Y" syntax, but I found that using bash variable and bash string manipulation (${string:X:10}) is much convenient.

3. We need to check is current number prime or not. We can do it on "pure bash" too, but I found that we can use infamous factor tool from coreutils to do that task:

root@ubuntu:~# factor 100 100: 2 2 5 5
root@ubuntu:~# factor 177 177: 3 59
root@ubuntu:~# factor 179 179: 179

As you can see, factor tool make number factorization for any not really big integer number - it's quite enough for our purposes.
So, let's glue everything together:

And output is:
7427466391
7413596629
6059563073
3490763233
2988075319
1573834187
7021540891
5408914993
6480016847
9920695517
1838606261
6062613313
3845830007
1692836819
4425056953
2505695369
5490598793
1782154249
8215424999
9229576351
9519366803
5193668033
1825288693
8294887933
1730123819
4039701983
4804295311
8194558153
9455815301
1332069811
6181881593
1881593041
5930416903
1934580727
3858942287
4841984443
1978623209
3140934317
3640546253
8887070167
7683964243
4563549061
Answer is 7427466391. And we can also fold it to one-liner of course:



Misson accomplished. :)

1 комментарий:

Unknown комментирует...

absolutely legit! awesome stuff, didn't expect anyone to go "challenge accepted" on me like that lol

/bow

//V