Project Euler
projecteuler.net
projecteuler.net
The same company also had regular hack night where everyone drinks a lot of Tecate, agress on a Project Euler problem and a language no one knows, and races. Fun times.
EDIT: Just realized that the problem asks for the odds of being a billionaire, not f. So there are probably a good number of f that work, but they all produce the same odds.
P.S. I must apologize for abstractly referring to a solution approach as "this", but I didn't want to create a spoiler in case anyone else had felt inspired.
http://forum.projecteuler.net/viewtopic.php?f=50&t=1982
I don't see this problem listed, but I didn't look through the whole thread.
Solved it with pencil and paper, if "pencil and paper" includes asking Wolfram Alpha a few questions :)
For one coint toss, I get:
(previous winnings) x (1+f) if I win
(previous winnings) x (1-f) if I lose
Thus, w being the number of times I win, I get the total $$ we would have:
(1+f)^w x (1-f)^(1000-w)
But those cases are not equally likely, so we have to ponderate them with a normal law centered at 1000/2, variance at sqrt(1000/4):
(1/(sqrt(2xPi)xsqrt(250))) x exp(-(500-w)^2/500)
So, now we can take an f, calculate the number of w's that put us above 1B$, and sum up the ponderation for each case. Then find the right f that optimized the chance of being a billionaire. This chance is the solution.
You're using the normal approximation to the binomial distribution. It may or may not be a good enough approximation. Better to do the binomial thing exactly. This requires arbitrary-precision integer arithmetic, but that's pretty easily available.
I hope the corporate culture is friendly to those of us who choose not to consume alcohol.
Edit: http://projecteuler.net/problem=98 was the problem, so it wasn't in the 100's like I misremembered.
The way I learned to code was working my way through Project Euler problems in Python, eventually getting to a score of about 55 before I was at the point where I decided to try making "real" programs like Android apps.
When you learn to code people tell you that X or Y is bad for performance, and you should do A or B instead. The problem is that most beginner-type programs run in a few milliseconds and there is no way to see the performance either way. When you're doing a PE problem, a performance tweak can change your answer from a 1-minute runtime to a 1-second runtime. That's something anyone can appreciate, and it lets you experiment with performance on interesting math problems.
Another advantage of Project Euler is it makes you realize just how powerful a computer can be in the right hands. These are problems that nobody in their right mind would try to solve by hand, but they're so tractable with programming knowledge. That was a very exciting realization to me and it pushed me towards a career in software.
It doesn't heavily challenge you to advance past a most basic level of a programming language. For example, most Project Euler problems are solved in Java most efficiently by using the features of Java that map 1:1 to features in C. You could do pretty much the entire suite of problems without even understanding the motivation of a language like Java.
I did find it better as a tool for learning functional programming languages (like Haskell) however, perhaps unsurprisingly.
Stop doing that and its a lot more fun. It annoys me when a PE problem is specifically designed to make it impossible if you do it the "wrong" way. Most PE problems allow crazy solution strategies. The bad ones only have the one true way that is computationally feasible.
A few posts up someone liked problem 267. I would pick random numbers, run them, then keep the winner and make n-1 new random numbers for round 2 and keep running rounds of multiple threads until bored, remembering the best result so far. Yes, that is not a very smart way to solve the problem, but its a very fun way to exercise the heck out of your knowledge of threads in some new language. Or you could make an insane thousand thread pipeline and hope for convergence. Or a thousand processes on a parallel cluster pipelined together. Could I write my random processor using BASH to baby sit a bunch of octave instances? Newtons method at least at first glance would be too easy. Could I solve it graphically, literally, by graphing some results and doing image manipulation and analysis of the generated graphic file to obtain the numerical result and feeding back for more "zoom" detail? Totally ridiculous unless the whole point is some weird computer vision project. Given an emulator for a IBM1620 mini-mainframe from the 60s, could I write a perl script that output random Fortran-II test runs for the emulated mini-mainframe to compile and process and then another perl script to eat the virtual "printer" output of the mini-mainframe to get random run results? Problem 267 looks like a fun one to solve the wrong way.
This is the unfortunate part of PE becoming popular at interviews. First of all it surely has nothing remotely to do with almost all programming jobs, secondly, "having fun while doing crazy things" is probably not the ideal IT department mission statement or employee selection criteria (although it would explain some things I've seen over the years...)
The proper tool for 99% or so of PE problems isn't a programming language anyway, its octave/mathematica/parigp. So its not too far out of the spirit to try crazy stuff.
Now for the points I would like to make, primarily for the benefit of the few who actually think as you claim to think:
Women are actually similar to men in a number of novel ways.
We have eyes, and those eyes are intricately connected to very powerful and compact organic computers—capable of independent thought—called brains.
That's right, men and women can both have brains.
And those of us women fortunate enough to be blessed with brains are quite capable not only of independent thoughts, but even decision-making. And yet another way in which we women are similar to men is that each of us, as individuals, comes to have certain aptitudes, preferences and values.
Some of us, like myself, discover to their amazement that they can understand mathematics and even think mathematically about pretty much anything, and develop an interest in technology and computation because of the possibilities it opens up for mathematics and because of the ways mathematics can reflexively provide insights into computer science and programming.
Other women have an aptitude/preference for: polishing nails; answering telephones; designing cute little things that men can give to women at Christmas; and so on. Are women like myself a minority? Perhaps, but it isn't because we have to be shown things like maths and programming with striking adverts, responsive websites and pretty flyers.
I'm not going to pretend that society has been engineered into a patriarchy, over thousands of years, as part of a sinister plot by the Illuminati to preclude the success and independence of the children of the mother-goddess.
I'm likewise not going to pretend to think that there are men with power who purposefully keep women from rising up, or give preferential treatment to male candidates for scholarships/whatever without even realising it. Because ultimately I have no proof of such things and neither do I care about some male-dominant society, because in my experience, what matters is the talent; if you have it, if you have an original idea, a way how to implement it, or if you're simply the best at what you do, you will succeed if you want to, male or female. I do not care why my boss, my clients or my investors choose me, I just want the opportunity to do what I do best, what I like doing.
If you think women simply haven't been exposed to the magical and fun possibilities of mathematics and computers, think again. If women were ignorant to these fields and what they involve, they wouldn't laugh at you for being a "nerd" or date muscular/rich guys instead of you.
They know what maths is, and they know what programming is, and they'll never want to visit a forum and tell everyone how awesome it was when they elegantly solved some mathematical problems or came up with a new proof for some random theorem. They will on the contrary yearn to talk about shoes, interior design, literature, art, perfume, TV shows, movies, diets and so on.
The select few women who prefer mathematics/compsci and find it genuinely fun and inspiring were already posting on newsgroups, were already on IRC, were already subscribed to ars technica and slashdot on google reader, were already here; and they are already here; or they will be here in the future, or wherever else that such subjects can be discussed in the future.
It is not a case of marketing the idea to a mass of women who have no idea what makes their iPhone so useful, or how their cars' brakes are engineered. Women do not go to fashion forums and tell everyone about how much I wish I could expose men to the glories of haute couture. Women do not tell their nutritionists how much they wish they could entice their male friends with raw food diets and veganism.
There are the lost, unwashed masses who will never amount to anything, who will become a carbon copy of their parents and aspire to nothing beyond some repetition-of-basic-tasks job in an office or in retail, and the members of these masses are of both genders. You will fail to "market" math/compsci to these people, regardless of gender, because they cannot do it. Women who aspire to something and want to succeed do not generally want to do it with math and programming.
So, to all of you who think women need to have math/compsci marketed to them: kindly stop talking crap and just ignore the gender issue. It doesn't do you any credit. Women are here. We don't typically scream that we're women because why should we? We're just professionals or students trying to succeed and learn, no different to you gents.
If you want to encourage women to get into math/compsci, have a daughter and buy her a cheap laptop and "The C Programming Language" when she's young. If she takes to it, bang, she had an aptitude that would have gone unnoticed and you saved her from a life of instagram and film studies.
If she deletes some system folders she doesn't think she needs, watches make-up tutorials on youtube and checks facebook every 2 hours, you know you've got yourself a typical woman.
Protip: I don't think the statistics of how many women study math/compsci will be much different in the aforementioned compsci-introduced generation of daughters.
Kids don't magically decide that math or science or computer programming is fun. They're heavily influenced by what they're exposed to and what they see other people they respect doing. Yes, that's "marketing" or perhaps better call it education.
And no, giving a kid the "C programming language" isn't going to cut it unless they've previously had enough exposure to math or engineering to understand why it's interesting. (Based on what I've heard, Minecraft seems to be working a lot better.)
And that's a standard subject taught in high school. I think if instead you look at why kids learn music or art or dance or drama or sports or a foreign language or religion, you'll find that the parents and relatives and friends often (not always) have a lot to do with it. And even with parental support, often the kids decide it's not for them. And that's fine; at least they got the chance.
I don't see computer programming as being all that different; not every kid is going to be into any given activity, but if they're not exposed to it in a way that makes it seem interesting, that's going to drastically reduce the number of kids who even try it. And that exposure is going to vary pretty dramatically depending on where you grew up.
Yeah, they do. That's why it is so important to expose kids to lots of things. You never know what is going to capture their imagination.
CS is a sausage fest as we all know here on HN. What most HN readers don't know is around 46% to 48% of all math undergrad degrees in the USA have gone to women since the early 80s.
You can read some hilarious articles online about the "crisis" that women have declined to a mere 45% in some years. I make fun of it because my EE classes had zero female grads, everyone knows CS is a sausagefest, why I remember a decade ago in an advanced C++ class I got to work with "the" girl in the class, all true stories, but if there's one thing not to fret about, its that an office staffed by recent math grads (McDonalds? Applebees?) would have either 10 of each or at worst 11 men to 9 women, hardly a staggering imbalance like you see in CS/IT.
Still even 64% is hardly EE at Research I (85% male), so your overall point stands.
I don't think marketing tech to women or girls is "the solution" either, but I don't make every effort to steer other men away from thinking about it and slur people for trying. That's intellectually malicious.
A part of me doesn't actually believe you're a woman, given how many men put effort into anonymously impersonating women in political debates, but I lean toward believing you
there are plenty of women who think gender is an issue
If you think me bitter, you're wrong. I am just tired of the trend to think of women as people with "special needs". I am perhaps concerned with gender more, after all.
I want to play with new programming languages, and see if the output is correct while I'm at it.
Although it has Clojure (my target language), you still send code instead of an answer, and you get problems like not knowing what's available in terms of libs and whatnot.
Also, you can usually find information about that kind of stuff in their IRC or even e-mail. They are usually pretty responsive.
I never had a PhD near by to get help from, but many problems involved doing research online about a theorem, sequence or some sort of mathematical concept.
It's fun, I encourage everybody to do a few. Get past the easy ones at least.
My favorite problems is 98. This problem, along with the Sudoku one at 96, require much more careful programming than some of the others due the drastically fewer number of people who solved it compared to the surrounding problems.
If you don't know what to look for off the top of your head (which you probably wouldn't without a math degree), try to google around for math that looks relevant to your problem.
I find http://mathworld.wolfram.com/ and http://oeis.org/ to be very helpful for this.
Do you have an example of such a problem?
But lot of those harder ones - as far as I can tell - required pretty deep knowledge of number theory, which even though I studied math (10 years ago), didn't have. I think it would be nice if there was sometimes a hint about what the people should study to be able to solve it.
http://projecteuler.net/problem=436
and couldn't solve it. I found an article on mathworld that says the number of expected rolls is e so that the sum is over 1. I don't know how to figure out what the value of the roll that gets you over 1 is, it's something like 0.64 from simulation but what does that number mean and why?
That may be what you want. However, a lot of these are outside my math knowledge/ability, without really expanding my programming ability.
I've spent a lot of time reading wikipedia articles for algorithms that I don't understand trying to solve some these problems.
I enjoy Project Euler, but as with many people slowly got annoyed by lack of specific mathematical knowledge as opposed to programming. One thing I believe would really help with this would be a resource that discussed the problem in the abstract. As an example, for most of the programs that rely on using primes, whether it be iterating them (e.g. first 1M primes) or the unique prime factorization of a number, discuss the known algorithms in pseudocode. Perhaps this is a bit much, as I would be satisfied with just knowing the words I need to go find resources for myself. This is what I tend to do anyway after I have taken a fair stab at a problem: "Oh, I'm doing prime factorization. I wonder if there are better algorithms than I have used." Indeed, one resource for this is the forums that are made available after the problem is solved.
Some might see this as ruining the fun, but I would personally have more fun and solve more problems if this was available.
[Edit] Just found it going through my history: https://www.hackerrank.com/
[1] http://uva.onlinejudge.org/index.php [2] http://uhunt.felix-halim.net/id/339
Then I remember that I only took a little bit of math, so then there's the research, the papers to read and decipher, the code to write, and I finally solve the problem and swear I'll never come back.
So, yeah, I just finished a batch of problems last week so I could get a couple of ego badges just within reach. 75 down, 379 to go!
On the one hand, it is a good lesson in how hard it can be to write correct code.
On the other hand, real world problems aren't black boxes where you try an integer until you get the right one. Problems with multiple tests needed to pass (like topcoder) are much more realistic.
I used to do these problems years ago when I was still a student and later when commuting to London. I did as many as I could on paper before trying to program solutions. I'll have to log in sometime and finish the few I missed.
I've been a little busy lately so it's been neglected somewhat. Why is Prolog so hard?
I enjoyed solving a few of those problems using SQL, that was fun.
How much work are you comfortable making your candidates do before they even know whether they're getting an interview?
I'm particularly sore because I spent a bunch of time working on learning something domain-specific for a potential employer who verbally indicated the interview process would be proceeding, but then forgot to tell me for a week they had decided to end the process.
No. Solving the first 12 PE problems should not take a competent programmer more than 30 minutes.
I (deliberately) didn't use a programming language with, e.g., facilities for prime factorization built in; that would have made it much quicker but would also have made the whole thing useless as a programming test. So I had to implement the sieve of Eratosthenes, the number-of-divisors function (via prime factorization), etc.
I estimate that about 8 minutes of that time was the result of a couple of silly bugs. (It's surprising how many seconds one can lose to forgetting that 16 is less than 20.) That figure could easily have been zero or twice as much. I lost perhaps two minutes to spousal distraction.
These are all straightforward problems; in no case did I have to spend more than a few seconds thinking how to proceed, though in a couple of cases my response to having written buggy code was to replace it with something more simple-minded.
recursive, I invite you to actually sit down and implement solutions to the first 12 PE problems in, say, Python or Ruby or some similar language and tell us how comfortably under 30 minutes you come in. For the avoidance of doubt, I'm not at all saying you won't manage it -- I wasn't far off and you may very well be quicker than me. But I'll be surprised if you're so far ahead that after the exercise you still think every competent programmer should finish in at most 30 minutes.
(My rough timings for the 12 problems, in order, in minutes: 1, 1.5, 1.5, 1, 3, 1, 3, 2, 1, 4, 5, 10. These figures include bugfixing and checking against the PE site. Total lines of code: about 115.)
Duly chastened, I take it back. But if the numbers were changed to 8 problems, and 1 hour, I still don't think that's unreasonable.
... I am kicking myself that I have never done that.
http://united-coders.com/christian-harms/10-one-line-solutio...