Fun Programming Quizzes
Okay, since I know several members are into programming, I thought about sharing a few resources that contain fun logical/mathematical problems to solve via programming.
This is a cool one (but it's a bit more advanced generally, so if you're entirely new to programming don't start here :P ) :
https://projecteuler.net/archives
And this one is more towards beginners, but it's fun - I've done most of the problems there, some of them a few times and in different ways (you can code it and try it out on the website itself - either Java or Python - this may be cool for you @Question) :
http://codingbat.com/python
Feel free to post questions, share problems, etc. here.
This is a cool one (but it's a bit more advanced generally, so if you're entirely new to programming don't start here :P ) :
https://projecteuler.net/archives
And this one is more towards beginners, but it's fun - I've done most of the problems there, some of them a few times and in different ways (you can code it and try it out on the website itself - either Java or Python - this may be cool for you @Question) :
http://codingbat.com/python
Feel free to post questions, share problems, etc. here.
Comments (42)
233,168.
Although, I remember I didn't get the right answer the first time, because I thought I had to include 1000 in the calculation (so I used 1001 as total). Then I was very puzzled why I'm not getting the right answer >:O
I've used it before - it's really good for creating things that involve geometry and graphics (both 2D and 3D). I've made a professional software with it for a client - and I also made a physics simulator with it for fun lol.
Quoting VagabondSpectre
Java* :P
Right now I'm building a thermodynamics simulator as a learning project, it's coming along fairly nicely. You mentioned web development, have you used P5.js ? It's like processing but new and with CSS/DOM/HTML functionality so you can more easily structure page design. I use brackets for P5.js...
I completed a slightly more difficult problem:
I would be very impressed if someone could get a solution in shorter code (although the run time is a bit high on this one)...
No never used it before! But I would imagine it's more useful for things like designing the front-end of games/applications rather than just website development. Looks pretty much like a Processing version for the web :P
Quoting VagabondSpectre
That's cool! I'm not very familiar with it, as you can see, haven't used it before.
Quoting VagabondSpectre
That's because you have two loops nested inside each other. That should preferably be avoided. I'm not a computer scientist so I don't understand the theory very precisely, but I do know that having loops nested increases run-time significantly.
Well, nested loops are the bread and butter of writing concise code!
Can you show me an example solution to that problem which does not use a nested loop?
The one I did was similar - I looked into Brownian motion.
Quoting VagabondSpectre
I will think about it, haven't solved that one yet. But I did say:
Quoting Agustino
Of course there are some situations where this wouldn't be feasible.
Yeah Coda2 is my favourite on Mac. Atom is surprisingly good amongst the free ones though - better than the others I've tested.
If you need to find the n'th prime for a large n, you would first calculate an approximate answer (there is a mathematical method for that), find the number of primes below that number (there are methods for that as well), and then zero in on the exact answer, perhaps using a more efficient primality test than your nested loop. That would most certainly be more lines of code than what you wrote though, and not something you could pull off on an interview, unless you really know this stuff.
I don't think there's anything inherently wrong with nested loops other than it carries the chance of iterating through index values which are redundant or need not be checked. If I stored each prime as I found it and used that data (along with other rules and exceptions) to rule out future testPrimes and indexes of the loop that checks it's factors, it could be made faster still.
Creating a robust guess is really the rub of such a strategy. If you know you're in the ballpark of an Nth prime, and you check up and down from your guess value until you find a prime, then the closest prime to your guess should be your prime value.
But what if your estimation is low and the prime you're looking for happens to be the higher value of a mersennes pair? You would need to know exactly how many primes are below the prime you're looking for and whether or not your estimation is above or below the target prime. In other words you need to calculate or know the Nth-1 prime. Calculating higher primes from low known prime values needs to happen using a recursive/repeating algorithm not unlike the one I created, but it can be made much more efficient by adding exceptions to rule out bad testPrime and factor-index checks. As you say though, this requires much more actual code.
P.S: Is there really a way to know the number of primes below any integer without having to actually calculate or iterate through those primes? (I'm almost positive this is not the case, otherwise we could calculate primes of almost arbitrarily high N values by just picking a ridiculously high number, finding the number of primes beneath it, and then counting up until we hit a prime).
Are you familiar with Big-O notations? Two loops inside each other would be O(n[sup]2[/sup]) as opposed to O(n) for a single loop if I'm not mistaken. Again I never studied computer science - I took courses on it - but never studied it properly (I have a degree in Civil Engineering), these are just some things I've picked up with regards to algorithms. Big-O is used to classify the time efficiency of an algorithm.
Say I have two loops, each making n calculations, one inside the other. That would effectively be n[sup]2[/sup] calculations, because for each calculation in loopOne, there need to be n calculations in loopTwo. If I had two loops independently one after the other, then that would be 2n calculations. Generally if at all possible I tend to avoid loops (though this is rarely possible) - and I very much try to avoid nested loops where possible.
If you need to actually hit all of those index values then dividing the work pf two nested loops into a single un-nested would just create a loop of proportionally exponential length. For instance, say I want to compare every value in one array to every value in another array. The nested version looks something like this:
But the un-nested single loop version version would look like this:
You need to perform the same number of checks either way, so there is no loss or gain either way except to keep it concise...
http://codingbat.com/prob/p191363
Solve it without any loops :P (your processing code should pretty much work fine for the purposes you need it inside the Java version there).
The way you've written them that's true, there is no loss or gain. But there might be a better way to do what you're trying to do there (and that would be the way you avoid using nested loops). Arrays for example are just one data structure that you can use to hold your values. Depending what you want/need to do with the values, arrays may not be the best way to store the data... (for example - why do you want to compare every datapoint from one to every datapoint from the other? Are you looking for something? What's the goal in that comparison?) There's also binary trees, hashmaps, treemaps, stacks and more... You may just need a different type of data structure for your project. So you'll either use a library that already has the data structure you need, or you have to create it yourself.
The array processing paradigm of R (and other, older languages like APL) allows for compact coding of such problems. Here's an R coding that spits out the answer:
The %% symbol is for the 'mod' operation and '|' means OR.
This is 101 non-blank characters, compared to 204 non-blank chars in the one above. Part, if not all, of that reduction comes from the fact that R does not require declaration of variables, and printout of the value of an expression is automatic, thereby removing the need for a print statement.
Depending on how the recursion is implemented, the code may generate a stack overflow. Mine worked OK for the 101st prime but complained about over-deep nesting in the search for the 1001st prime.
If I could remember LISP I'd try to write it in that, as that enables concise recursive expression.
The examples of code you gave are both sexy and terrifying. I think programmers moved way from languages like these because they can be harder to read at a glance compared to higher level languages (although I can definitely appreciate short and well organized code). FORTH was the first programming language I ever got into, which is a very low level language which can build very specific and concise/efficient programs...
C code. Only two conditionals, not four.
it's between quote and strike out (looks like this: <> )
It's also not as straight-forward as that either. Take caching for example; code runs faster from the cache and smaller routines (in terms of machine instructions) are more cache-friendly - so depending on the platform and the specifics of the algorithm, shorter code that appears to be less efficient on paper might actually run faster.
In practice, you test and benchmark for these things, rather than adhering to generalised rules.
Anyway. After you guys were talking about writing the 10001st prime code without nested loops, I just couldn't resist. This code is mortifying (I got bored/tired by the time I got it working) and completely impractical, but satisfies the condition of having 'just one loop'. :P
PS. If you're more interested in writing shorter code than efficient code, there is code golf.
Edit: I forgot to explain (for what it's worth) that the code works by using a sieve to find the prime numbers up to an assumed number and continues to increase that number until enough primes have been found e.g. it'll find the primes between 0 and 50,000, then between 50,000 and 100,000, etc.
I think it can be done with no loops at all.
Challenge accepted.
Side note: The language requires the empty else { } clauses? Not used to that as a C person.
I have a harder time thinking in C anymore since I'm pure C++ now.
Prime-counting function
I used Sublime for a long time, but now I use Visual Studio Code. There's not a huge difference, but it seems more solid, and looks prettier with less fiddling around.
The sum of multiples of 3 below 1000:
3 + 6 + 9 + ... + 999 = 3 * (1 + 2 + 3 + ... + 333) = 3 * 333 * 334 / 2
Likewise, the sum of multiples of 5 below 1000 is 5 * 199 * 200 / 2
But we also need to subtract the sum of multiples of 15, since we counted them in both sums: - 15 * 66 * 67 / 2
Total: 233,168
Though I will say that one of your conditions is redundant (below is the shorter version with that condition removed):
That depends on (1) what is your programming assignment, (2) what programming language are we talking about, (3) how much are you paying? and (4) if that person is fine with the ethics of the situation. But in short - we need more details.
Quite often I see people asking for something generally like that, and it's not helpful to anyone - I don't even know if I can help you based on the info you have provided for example.
Quoting darthbarracuda
And another important question is how are you paying... because Paypal payments aren't very secure, there is no seller protection for digital goods (but there is buyers' protection though - very messed up). Many programmers aren't even aware of this lol.
Hire a programmer, get the work done, and then go to your bank and file a chargeback aimed at Paypal :P - that's what a ruthless businessman would do >:O
So programmers need to be careful with Paypal as a payment option.
So I was trying to solve that last night. I had solved the previous one which involved a smaller triangle awhile ago through an evolutionary algorithm - see below (all are written and run in the Processing java-based language).
The evolutionary algorithm works by making a "first guess" at the solution, which is a greedy algorithm, which chooses the best path to take down the triangle at each juncture, without any looking into the future. It records this path as 0s and 1s, with 0 = take a left, and 1 = take a right. Then it takes this first guess at a path, creates copies of it, mutates them (with certain probabilities), and then tests which one from that generation is the best. It selects it, and returns to the beginning by re-creating copies of it, modifying them, testing, etc.
Now, this evolutionary algorithm doesn't manage to solve Problem 67 (although I expected it to, that's why I chose to use it for the first problem, instead of trying brute force), though it gets very close to the answer - gets to around ~7200 and the answer is 7273.
Here's a dynamic programming way to solve it, also written in Processing. Basically, it solves each "small" triangle starting at the very bottom, and then records that answer on the row above.
Note - to run this one, you must download the .txt file from the first link and then save it in the same folder as the program.
Altering the probabilities of the evolutionary one, the limit of numGens (number of generations tested) in the while loop, and size (the size of the gene pool), can alter the results obtained. Does anyone have a way to make the evolutionary one more efficient to reach the answer?