DokuWiki

x2010:extra

Extra! Extra!

This page contains extra challenges for students who are looking for more than the course assignments offer. These exercises do not count for the exam.

Send your solutions to contact2ip65@gmail.com with “Extra” in the subject line.

Shortest

What is the shortest Java program that produces some output on the console? Write one class that compiles and uses only classes from the standard package (java.lang).

One thousand stars

Write the shortest possible Java program that prints one thousand stars on the output.

No loops

This challenge is very much like the previous one. So let's make it a little bit more interesting: don't use loops or recursive methods.

For better or for worse (tough)

Warm-up

Do you know the game “higher lower” (hoger lager)? Computer picks a Secret Number between 0 and, say, 999 and for you the task to find it in as few guesses as possible. After each guess, the computer says “Higher”, “Lower”, or “Correct”, if the Secret Number is resp. greater than, smaller than, or equal to the guess. Now the roles are changed. The computer guesses and an adversary picks the random number. For you the task to write a program that minimizes the number of guesses in the worst case, i.e., if the adversary always gives an answer that is as bad as possible for you, but always consistent with the answers given before.

B or W or N

We present a variant of this game. The adversary now tells you whether your current guess is closer (B for Better) to the Secret Number than the prvious guess, or farther away (W for Worse), or at equal distance (N for No improvement). At the first guess, he gives no information and he always answers N.

At the beginning of the game the interval for the Secret Number is chosen, e.g., from 0 to 499. The guesses have to be within this interval. (This complicates matters.)

Write a program that will always find the secret number in at most 18 guesses (not counting the final “guess” when it knows the number) for the interval 0-499.

Optimal BWS

Assume the interval is of size N, from 0 to N-1. Write a program that will always find the secret number in at most G guesses, where 2^G ≤ 3N.