Programming Praxis

Today’s exercise comes from Albert H. Beiler’s book Recreations in the Theory of Numbers Chapter 1, Problem 2):

One side of a right-angled triangle is 48. Find ten pairs of whole numbers which may represent the other two sides.

Your task is to find the solution to Beiler’s problem. 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

In 1976, Volker Strassen, working with John Pollard, developed a factoring algorithm that is still the fastest proven deterministic factoring algorithm, with time complexity O(n^1/4 log n); unfortunately, it is generally slower than other similar algorithms, even Pollard’s rho algorithm. The basic idea is that if you have the product f_i of a consecutive set of integers modulo the number to be factored n, and that set of integers contains one of the factors of n, then gcd(f_i, n) will be greater than 1. Here’s the algorithm:

1. Compute c = n^1/4 and define an array f containing c integers, each initially 1.
2. In each array element f_i, compute the product modulo n of the integers from i c + 1 to c(i+1).
3. Compute the greatest common divisor of each of the f_i with n, stopping when you find a (possibly-composite) factor.

The second loop, in Step 3, takes time O(n^1/4 log n), so the trick is to compute the products of Step 2 in less time than O(n²). That can be done using product trees, as Berstein suggests, but that’s messy and a little bit complicated, and even if you manage to implement it, Strassen’s algorithm still isn’t competitive, so we won’t bother.

Your task is to implement Strassen’s factoring algorithm 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 have a simple task today, intended for those students just starting a new semester who are learning programming for the first time:

Given an array of positive integers, determine if the array can be split into two pieces, without re-ordering the elements of the array, so that both pieces have the same sum. If it is possible, return the two pieces. If not, you should so indicate. For instance, the array [1, 2, 3, 4, 5, 15] can be split into two pieces, [1, 2, 3, 4, 5] and [15], each with sum 15.

Your task is to write the program to split an array into two pieces with equal sums. 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 robot can move any number of steps in the four cardinal directions. Given the robot’s initial position and a string of moves given as, for instance, N3E5S2W6 (any of the four cardinal directions, followed by any number of steps, as many commands as desired), determine the ending position of the robot.

Your task is to write a program to determine the ending position of a robot, given a starting position and a string of move commands. 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

I don’t watch a lot of television, but the YouTube channel Numberphile is one of the places I am careful not to miss. Numberphile recently had an episode called “The Square-Sum Puzzle” that makes a good exercise:

Rearrange the numbers from 1 to 15 so that any two adjacent numbers must sum to a square number.

Your task is to write a program to solve the Numberphile square-sum puzzle. 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 binary gap is a sequence of 0-bits between 1-bits in the binary representation of a number. For instance, 20₁₀ = 10100₂ has a binary gap of length 1 between its first and third bits; the two 0-bits that end the number are not part of a binary gap because there is no trailing 1-bit. Thus, the length of the maximal binary gap in 20 is 1. The length of the maximal binary gap in 529₁₀ = 1000010001₂ is 4.

Your task is to write a program that finds the length of the maximal binary gap in a number. 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

In today’s exercise we are given a file and asked to find the userid’s of customers that appeared on three successive days. The input file contains a date in MM/DD/YYYY format, a tab character, and a userid (a four-digit integer):

01/11/2018\t0003
01/12/2018\t0003
01/13/2018\t0004
01/13/2018\t0003

In this case, customer 3 appeared on three successive days, 1/11, 1/12 and 1/13. You may assume the input is properly formed.

Your task is to write a program that finds customers who appeared on three successive days. 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 have another homework question today, as I continue clearing out my backlog of people who sent me email asking for homework help last fall:

You are given an array with duplicates, and are to sort the array by decreasing frequency of elements. If two elements have the frequency, sort them in increasing order of value. For instance, the input (2 3 5 3 7 9 5 3 7) is sorted as (3 3 3 5 5 7 7 2 9).

Your task is to write a program that sorts by frequency. 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 have today two simple exercises on lists:

1. Given a list of lists of integers, all the same length, return a list of the sums of the lists. For instance, given the list ((1 2 3 4) (2 3 4 5) (3 4 5 6)), return the list ((+ 1 2 3) (+ 2 3 4) (+ 3 4 5) (+ 4 5 6)), which is (6 9 12 15).
2. Given a list of integers of length n = k × m, return a list of k items, each containing the sum of the next m integers from the original list. For instance, given the list, (1 2 3 4 2 3 4 5 3 4 5 6) and sub-list length m = 4, return the list (10 14 18).

Your task is to write programs that perform the two tasks. 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