Gnome Sort
July 29, 2016
A garden gnome sorts flower pots by the following method:
The gnome looks at the flower pot next to him and the flower pot just behind him. If they are correctly ordered, so the flower pot just behind him is smaller than the flower pot next to him, he steps one pot forward; otherwise, he swaps the two flower pots and steps one pot backward. If there is no flower pot just behind him (thus, he is at the start of the line of flower pots), he steps forward to the next pot. If there is not flower pot next to him (thus, he is at the end of the line of flower pots), he is done.
Your task is to implement a program that sorts by the gnome method. 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.
Changing Gender
July 26, 2016
The culture wars have my head spinning so fast that I need a computer to help me out. One day I might say “He is my brother.” and the very next day, speaking about the same person, say “She is my sister.”
Your task is to write a program that changes the gender of the words in a string. 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.
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.
Highly Composite Numbers, A Sieving Approach
July 19, 2016
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.
Highly Composite Numbers, Using Priority Queues
July 15, 2016
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.
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.
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.
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.
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.
Programming Praxis 