Fun Programming Quizzes

Agustino

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.

Michael

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

$sum = 0;

for ($i = 1; $i < 1000; ++$i)
{

  if (0 == $i % 3 || 0 == $i % 5)
  {
    $sum += $i;
  }

}

echo $sum;

233,168.

Agustino

↪Michael

Yah that was quite an easy one :P . Mine in JS:

var total = 1000;
var sum = 0;
for (var i = 0; i < total; i++) {
  sum += checkDivisibility(i);
}
console.log(sum);

function checkDivisibility(num){
  if (num%5==0 || num%3==0) {
    return num;
  } else {
    return num=0;
  }
}

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

Efram

I've had quite a bit of fun with HackerRank in the past; it covers a good range of subjects and difficulty levels. I wrote about one of my solutions here.

VagabondSpectre

Whiles and elses just to be different (this code is called "processing", which is a library of functions for javascript)...

int count= 1;
float sum = 0;


while (count<1000) {

  if (count%5 ==0) {
    sum+=count;
    count+=1;
  } else if (count%3 ==0) {
    sum += count;
    count+=1;
  } else {
    count+=1;
  }
}
println(sum);

Agustino

processing — VagabondSpectre

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.

library of functions for javascript)... — VagabondSpectre

Java* :P

Agustino

Btw for the web developers among you, which text editor do you use? Atom, Coda, Sublime, Textastic, Brackets or something else?

VagabondSpectre

I've used it before - it's really good for creating things that involve geometry and graphics. I've made a professional software with it for a client - and I also made a physics simulator with it for fun lol. — Agustino

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:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

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)...

int primePosition =6;
float testPrime = 13;

while (primePosition < 10001) {
  testPrime +=2;
  for (int i = 2; i < testPrime/2; i++) {
    if (testPrime%i == 0) {
      break;
    }
    if (i == floor(testPrime/2)) {
      primePosition +=1;
      break;
    }
  }
}
println(testPrime);
println (primePosition);

Agustino

You mentioned web development, have you used P5.js ? — VagabondSpectre

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

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... — VagabondSpectre

That's cool! I'm not very familiar with it, as you can see, haven't used it before.

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)... — 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.

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. — Agustino

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?

Agustino

Right now I'm building a thermodynamics simulator as a learning project — VagabondSpectre

The one I did was similar - I looked into Brownian motion.

Can you show me an example solution to that problem which does not use a nested loop? — VagabondSpectre

I will think about it, haven't solved that one yet. But I did say:

That should preferably be avoided. — Agustino

Of course there are some situations where this wouldn't be feasible.

Michael

↪Agustino

Sublime on Windows, Coda on Mac.

Agustino

Coda on Mac. — Michael

Yeah Coda2 is my favourite on Mac. Atom is surprisingly good amongst the free ones though - better than the others I've tested.

SophistiCat

↪VagabondSpectre

I don't know about more concise; in practice, for problems like this efficiency is a lot more important. There are more efficient methods of calculating the n'th prime, but that is more of a mathematical problem than a programming one.

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.

VagabondSpectre

I will think about it, haven't solved that one yet. But I did say:

That should preferably be avoided. — Agustino

Of course there are some situations where this wouldn't be feasible. — Agustino

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.

↪SophistiCat

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).

Agustino

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 to rule out future testPrimes and indexes of the loop that checks it's factors, it could be made faster still. — VagabondSpectre

Are you familiar with Big-O notations? Two loops inside each other would be O(n²) 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.

Agustino

↪VagabondSpectre

But if you think about it, it makes sense. For each value of loopOne, the whole of loopTwo needs to be completed. That's a lot more calculations than having, say, two independent loops.

Say I have two loops, each making n calculations, one inside the other. That would effectively be n² 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.

VagabondSpectre

But if you think about it, it makes sense. For each value of loopOne, the whole of loopTwo needs to be completed. That's a lot more calculations than having, say, two independent loops — Agustino

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:

int[] array1 = { 1, 2, 3, ..., n}
int[] array2 = { 1, 2, 3, ..., n}

for (int i=0; i <array1.length; i++) {
  for (int j = 0; j <array2.length; j++) {
    if (array1[i] == array2[j]) {
      playGongNoise();
    }
  }
}

But the un-nested single loop version version would look like this:

int[] array1 = { 1, 2, 3, 4, ..., n}
int[] array2 = { 1, 2, 3, 4, ..., n}

for (int i=0; i <array1.length; i++) {
  if (array1[i] == array2[0]) {
      playGongNoise();
    }
  if (array1[i] == array2[1]) {
      playGongNoise();
    }
  if (array1[i] == array2[2]) {
      playGongNoise();
    }
  if (array1[i] == array2[3]) {
      playGongNoise();
    }
...
...
  if (array1[i] == array2[n-1]) {
      playGongNoise();
    }
}

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...

Agustino

↪VagabondSpectre

Have a go at this one:
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).

Agustino

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... — VagabondSpectre

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.

andrewk

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

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:

sum((x<-1:1000)[x %% 3 ==0 | x %% 5 == 0)

The %% symbol is for the 'mod' operation and '|' means OR.

andrewk

↪VagabondSpectre

Throwing ALL consideration for efficiency out of the window, there is a more concise coding using recursion. Here it is in R:

(findprime<-function(x,n)
  if (sum(x %%  1:x == 0)<3)
    if (n>1) findprime(x+1,n-1) else
      x else
        findprime(x+1,n)
)(2,10001)

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.

VagabondSpectre

↪Agustino

Here is the best I can do in short time and without loops!

public int makeChocolate(int small, int big, int goal) {
  int remainder = goal%5;

  if (goal > big*5+small || big*5 < goal - small || remainder > small) { 
    return -1;
  }
  if (big*5 < goal) {   
    return goal-big*5;
  }
  return remainder;
}

VagabondSpectre

↪andrewk

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...

noAxioms

int makeChocolate(int small, int big, int goal) {
  if (goal < big*5)
     big = goal / 5;
  goal -= big * 5;
  return goal > small ? -1 : goal;
}

C code. Only two conditionals, not four.

VagabondSpectre

↪noAxioms

You need to use the code function in the Post Comment editor

it's between quote and strike out (looks like this: <> )

noAxioms

Best prime finding program I ever saw was an algorithm that would solve your problem above (10001st prime) with instant runtime. The code included itself and all the work (Sieve of Eratosthenes) took place in the preprocessor. The code compiled to one line that printed the answer, but it took hours to compile on some compilers.

noAxioms

↪VagabondSpectre

Awesome. I fixed it.

Efram

As has been vaguely covered already, there's nothing wrong with nested loops when they're doing their job; it's just usually more efficient to avoid them when possible.

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.

noAxioms

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 — Efram

Technically one loop. Still 0(n squared), but implemented as a state machine instead of loops.

Efram

↪noAxioms

It's purely a pisstake. ;) I'm aware it doesn't necessarily run more efficiently than the other implementations.

Fun Programming Quizzes

Welcome to The Philosophy Forum!

Categories

More Discussions