Array Manipulation

July 22, 2016

Our task today comes from Geeks for Geeks:

Given an array of positive integers, replace every element with the least greater element to its right. If there is no greater element to its right, replace it with -1. For instance, given the array [8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28], the desired output is [18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1].

Your task is to write the program that manipulates an array as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We’ve seen programs to compute the sequence of highly composite numbers in two previous exercises. Today, we look at a third algorithm, based on the Sieve of Eratosthenes.

If you have to find a the divisors of a number, or count them, you can employ the brute-force method of testing each possible divisor from 1 to n, as in the first solution to this problem, or you can factor n and compute the divisors, as we have done in a previous exercise. But if you have to find the divisors of a bunch of numbers, in sequence, you can sieve for them; we also did that in a previous exercise. Once you know the divisor-count for each number from 1 to n, a simple sequential scan looking for successive records will create the list of highly composite numbers.

Your task is to write a program to calculate highly composite numbers less than a limit n using a sieving algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

A different solution to the previous exercise exploits the form of highly composite numbers, which always consists of small primes to large exponents, so we can specify the highly composite number using only the exponents; for instance, 64221111 represents the number 26 · 34 · 52 · 72 · 111 · 131 · 171 · 191 = 293318625600. Since the exponents must be non-increasing, there are five possibilities for a larger highly composite numbers, represented using the power-notation as 74221111, 65221111, 64321111, 64222111, and 642211111. Thus, we find composite numbers by starting with the null power-list, which equates to the number 20 = 1, then add all possible successors to a priority queue, pop the successors in order, check each for a new record number of divisors, and push the successors of that number back on to the priority queue.

Your task is to generate the sequence of highly composite numbers using a priority queue. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Highly Composite Numbers

July 12, 2016

[ Today’s exercise was written by Zacharias Voulgaris, based on a Numberphile video. Guest authors are always welcome; contact me if you wish to write an exercise. ]

A highly composite number, also called an anti-prime, is a number n for which d(m) < d(n) for all m < n, where d(x) is the divisor function that gives a count of the number of divisors of x; in other words, a highly composite number has more divisors than any smaller number. Thus, a highly composite number, which has many divisors, is the opposite of a prime number, which has only two divisors. The sequence of highly composite numbers, which begins 1, 2, 4, 6, 12, 24, 36, … (A002182), has been studied by Ramanujan and Erdös, among others, and is a continuing object of study by number theorists. A famous highly composite number, known to Plato, is 5040.

Your task is to write a program that returns all highly composite numbers less than a given limit. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Greek Time

July 8, 2016

The modern day is divided into 24 hours, each with an equal number of minutes. In ancient times, before the invention of mechanical timepieces, the day was also divided into 24 hours, but not of equal length; there were 12 daytime hours, each of equal length, and 12 nighttime hours, each of equal length, but the length of a daytime hour and a nighttime hour differed, except on the two equinoxes.

For example, today, where I live, the sun will rise at 5:45 and set at 20:29, giving 884 minutes of sunlight, so there will be 73 2/3 minutes per daylight hour. Starting from sunrise at 5:45, the hours are 6:59, 8:12, 9:26, 10:40, 11:53, 13:07, 14:21, 15:34, 16:48, 18:02, and 19:15, with sunset at 20:29.

Your task is to write a program that calculates the daylight hours of the greek clock. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Depth Charge

July 5, 2016

Creative Computing was a staple of my programming education; I remember typing in the games to run on a friend’s computer. Here’s a game from the very first issue of the magazine, written by 18-year old Dana Noftle:

In this program, you are the captain of the destroyer, USS Digital. An enemy submarine has been causing trouble and your mission is to destroy it. You may select the size of the “cube” of water you wish to search in. The computer then determines how many depth charges you get to destroy the submarine.

Each depth charge is exploded by you specifying a trio of numbers; the first two are the surface coordinates, the third is the depth. After each depth charge, your sonar observer will tell you where the explosion was relative to the submarine.

Here’s a sample game:

DEPTH CHARGE GAME

DIMENSION OF SEARCH AREA? 10

YOU ARE CAPTAIN OF THE DESTROYER USS DIGITAL.
AN ENEMY SUB HAS BEEN CAUSING YOU TROUBLE. YOUR
MISSION IS TO DESTROY IT. YOU HAVE 4 SHOTS.
SPECIFY DEPTH CHARGE EXPLOSION POINT WITH A
TRIO OF NUMBERS -- THE FIRST TWO ARE THE
SURFACE COORDINATES; THE THIRD IS THE DEPTH.

GOOD LUCK !

TRIAL # 1 ? 5,5,5
SONAR REPORTS SHOT WAS SOUTHEAST AND TOO HIGH.

TRIAL # 2 ? 3,7,7
SONAR REPORTS SHOT WAS SOUTHEAST AND DEPTH OK.

TRIAL # 3 ? 1,9,7
SONAR REPORTS SHOT WAS NORTHEAST AND DEPTH OK.

TRIAL # 4 ? 0,8,7

B O O M ! !  YOU FOUND IT IN FOUR TRIES!

The first coordinate is east/west, the second coordinate is north/south. Here is the program that appeared in Creative Computing (pages 18-19):

10 PRINT "DEPTH CHARGE GAME" \ PRINT
20 INPUT "DIMENSION OF SEARCH AREA"; G \ PRINT
30 N = INT(LOG(G)/LOG(2))+1 \ RANDOMIZE
40 PRINT "YOU ARE CAPTAIN OF THE DESTROYER USS DIGITAL."
50 PRINT "AN ENEMY SUB HAS BEEN CAUSING YOU TROUBLE. YOUR"
60 PRINT "MISSION IS TO DESTROY IT.  YOU HAVE"N"SHOTS."
70 PRINT "SPECIFY DEPTH CHARGE EXPLOSION POINT WITH A"
80 PRINT "TRIO OF NUMBERS -- THE FIRST TWO ARE THE"
90 PRINT "SURFACE COORDINATES; THE THIRD IS THE DEPTH."
100 PRINT \ PRINT "GOOD LUCK !" \ PRINT
110 A=INT(G*RND) \ B=INT(G*RND) \ C=INT(G*RND)
120 FOR D=1 TO N \ PRINT \ PRINT "TRIAL #"D, \ INPUT X,Y,Z
130 IF ABS(X-A)+ABS(Y-B)+ABS(Z-C)=0 THEN 300
140 GOSUB 500 \ PRINT \ NEXT D
200 PRINT \ PRINT "YOU HAVE BEEN TORPEDOED! ABANDON SHIP!"
210 PRINT "THE SUBMARINE WAS AT"A","B","C" \ GOTO 400
300 PRINT \ PRINT "B O O M ! !  YOU FOUND IT IN "D"TRIES!"
400 PRINT \ PRINT \ INPUT "ANOTHER GAME (Y OR N)", A$
410 IF A$="Y" THEN 100
42O PRINT "OK.  HOPE YOU ENJOYED YOURSELF." \ GOTO 600
500 PRINT "SONAR REPORTS SHOT WAS ",
510 IF Y>B THEN PRINT "NORTH",
520 IF Y<B THEN PRINT "SOUTH",
530 IF X>A THEN PRINT "EAST",
540 IF X<A THEN PRINT "WEST",
550 IF Y<>B OR X<>A THEN PRINT " AND",
560 IF Z>C THEN PRINT " TOO LOW."
570 IF Z<C THEN PRINT " TOO HIGH."
580 IF Z=C THEN PRINT " DEPTH OK."
590 RETURN
600 END

Your task is to rewrite the program in your favored programming language. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Clock Angles

July 1, 2016

We have a fun little program for a lazy summer Friday:

Write a program that, given a time as hours and minutes (using a 12-hour clock), calculates the angle between the two hands. For instance, at 2:00 the angle is 60°.

Your task is to write a program that calculates clock angles. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Curious Numbers

June 28, 2016

Today’s exercise is in the style of Project Euler, so the rules are that your solution must not use more than a minute of computer time and that you can’t peek at the solution until you have the answer yourself.

Some numbers have the curious property that when they are squared, the number appears in the least-significant digits of the product. For instance, 6252 = 390625, and 71063762 = 50543227109376.

What is the sum of all numbers less than 1020 that have this curious property?

Your task is to find the sum described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2 3

John Cook is a mathematician and programmer who runs a fascinating blog that I frequent.

Cook recently had an article about the prime factors of telephone numbers. He explained that, for 10-digit telephone numbers as used in the United States, the average number of distinct prime factors is 3.232 and the distribution is between 1 and 5 distinct prime factors about 73% of the time.

Your task is to write a function that determines the number of distinct prime factors of a number, and use that function to explore the distribution of the number of distinct prime factors in a range of telephone numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Two Interview Questions

June 21, 2016

I like to read a web site called Career Cup, both to enjoy solving some of the programming exercise given there and to find exercise for Programming Praxis. As I write this exercise, here are the two most recent exercises on Career Cup:

  • Given a function rand2 that returns 0 or 1 with equal probability, write a function rand3 that returns 0, 1 or 2 with equal probability, using only rand2 as a source of random numbers.
  • Given a set of characters and a dictionary of words, find the shortest word in the dictionary that contains all of the characters in the set. In case of a tie, return all the words of the same (shortest) length.

Your task is to write the two programs described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2