Programming Praxis

In an array A, the term inversions refers to the number of items that are out of order; each i < j for which A[j] < A[i] counts as a single inversion. For instance, the array [1 4 3 2 5] has three inversions: (4,3), (4,2) and (3,2). Inversions are a measure of the disorder of an array: an ordered array has no inversions and a reversed array has the maximum n(n−1)/2 number of inversions.

Your task is to write programs that count the number of inversions in an array and make an enumeration of them. 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

The prime ant (A293689) is an obstinate animal that navigates the integers and divides them until there are only primes left, according to the following procedure:

An infinite array A is initialized to contain all the integers greater than 1: [2, 3, 4, 5, 6, …].

Let p be the position of the ant on the array. Initially p = 0, so the ant is at A[0] = 2.

At each turn, the ant moves as follows:

• If A[p] is prime, move the ant one position forward, so p ← p + 1.
• Otherwise (if A[p] is composite), let q be its smallest divisor greater than 1. Replace A[p] with A[p] ÷ q. Replace A[p−1] with A[p−1] + q. Move the ant one position backward, so p ← p − 1.

Your task is to write a program that computes the position of the prime ant after n turns; for instance, after 47 turns the prime ant will be at p = 9. 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 continue today working through my backlog of homework problems:

Given an array of at least three distinct positive integers sorted in ascending order, find all triples of array elements that form an arithmetic progression, so that the difference between the first and second elements is the same as the difference between the second and third elements. For instance, in the array (1 2 3 4 6 7 9) there are five triplets in arithmetic progressions: (1 2 3), (2 3 4), (2 4 6), (1 4 7), and 3 6 9).

Your task is to write a program that finds all the arithmetic progressions in an array; for extra credit, do the same thing for geometric progressions, where the ratios of the first to second element and the second to third elements are the same. 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 problem today:

Replace each element of an array with the product of every other element of the array, without using the division operator. For instance, given array (5 3 4 2 6 8), the desired output is (1152 1920 1440 2880 960 720).

Your task is to write a program to replace each element of an array with the product of every other element of the array, without performing division. 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

Zeros And Ones

This is somebody’s homework problem:

Given an array containing only zeros and ones, find the index of the zero that, if converted to one, will make the longest sequence of ones. For instance, given the array [1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,0,1,1], replacing the zero at index 10 (counting from 0) forms a sequence of 9 ones.

Your task is to write a program that determines where to replace a zero with a one to make the maximum length subsequence. 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

This interesting little question comes from Career Cup:

Given an array that contains only the elements -1 and 1, find the number of sub-arrays with a sum of zero. For instance, given the array [-1, 1, -1, 1], there are four sub-arrays that sum to zero: [-1, 1], [1, -1], [-1, 1] and [-1, 1, -1, 1].

Your task is to count the sub-arrays of a -1/1 array that sum to zero. 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

Pat Ballew is a retired math teacher who writes a blog On This Day In Math that gives a day-by-day history of mathematics. The blog is odd, quirky, and unquestionably fun. On October 7th, Ballew wrote:

The 280th day of the year…. The sum of the first 280 consecutive primes, mod 280, is prime.

Since I like to play with prime numbers, that got my attention, and I quickly went to determine how many such days there are in a year.

Your task is to determine how many days in a year share the characteristic that on the nth day the sum of the first n primes, mod n, is prime. 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

Many of the people who read my blog are programming students. It is October, about the middle of the Fall Semester at many universities, and my student readers need exercises to cement their understanding of their studies. Here are two exercises about palindromes.

1. A number like 123454321 is palindromic; it decimal digits are the same left-to-right as they are right-to-left. Write a program that determines if a given input number is palindromic.
2. Given a list of strings, for instance {“a” “bcd” “ef” “g” “f” “ed” “c” “ba”}, write a program to determine if the individual letters of the strings form a palindrome. Note that the letters might be distributed into the individual words differently when read in opposite directions.

Your task is to write two programs that recognize palindromes. 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 continue today with the recent series of exercises about how I configured my new computer. Chez Scheme is a remarkable Scheme compiler/interpreter, very fast, and remarkably bug-free, but it includes limited libraries, so users must create their own. This note describes some of the libraries I use.

The primary library is my Standard Prelude, described at https://programmingpraxis.com/standard-prelude, loaded each time Chez Scheme starts up. Chez Scheme resides in two executable files in /usr/local/bin called scheme and petite. I provide a shell script /usr/local/bin/chez that loads scheme (the full compiler) and the Standard Prelude as part of the interactive-system startup:

    #! /usr/local/bin/scheme

    ; standard prelude
    (load "~/scheme/lib/prelude.ss")

    ; literate programming
    (load "~/scheme/lib/tangle.ss")

    ; interactive editing
    (define *edfile* #f)
    (define (lload . args)
      (when (pair? args) (set! *edfile* (car args)))
      (when (not *edfile*) (error 'lload "file not found"))
      (when (not (file-exists? *edfile*) (error 'lload "file not found"))
      (let* ((ss (tangle *edfile*)) (i (open-input-string ss)))
        (let loop ((obj (read i)))
          (if (eof-object? obj) (close-input-port i)
            (begin (eval obj (interaction-environment))
                   (loop (read i))))))))
    (define (ed . args)
      (when (pair? args) (set! *edfile* (car args)))
      (when (not *edfile*) (error 'ed "file not found"))
      (system (string-append "ed " *edfile*))
      (lload *edfile*))
    (define (vi . args)
      (when (pair? args) (set! *edfile* (car args)))
      (when (not *edfile*) (error 'vi "file not found"))
      (system (string-append "vi " *edfile*))
      (lload *edfile*))
    (define (sh . args)
      (system (if (null? args) "sh -l" (string-join #\space args)))
      (if #f #f))

    ; go home
    (cd "~/scheme")

Documentation of the Standard Prelude is provided on the web page noted above. I defer to Chez Scheme for hash tables, structures and random numbers, rather than using the versions in my Standard Prelude, and also defer to Chez Scheme for the Standard Prelude functions that Chez Scheme provides natively. The only part of the Standard Prelude that is not loaded is avl trees, which are removed to their own library. Also loaded at each run of Chez Scheme are my literate programming environment described at https://programmingpraxis.com/2010/08/10/literate-programming and my interactive editing environment described at https://programmingpraxis.com/2017/04/07/edit-files-in-a-repl.

The only thing that hasn’t been discussed previously in my blog is the sh command. On my desktop computer, the screen is large enough that I can have both a Scheme REPL and a system shell window open at the same time, and move between them as needed. On my tablet, the screen is simply too small, so it is convenient to have a way to quickly exit to the system shell, execute some command, and return to the REPL. The sh command, called with no arguments, opens a login shell, and returns to the REPL when it is exited; called with arguments, it executes the command specified by the arguments, then returns to the REPL immediately. The (if #f #f) that ends the function is the standard way to return void from a function; it is used here to suppress the return code that sh normally returns.

Other libraries that I commonly use appear on the pages that follow; all are stored in ~/scheme/lib, and loaded by (load "~/scheme/lib/xxx.ss"):

    avl.ss      -- avl trees
    priqueue.ss -- priority queues
    textfile.ss -- input, processing and output of text file databases
    pregexp.ss  -- Dorai Sitaram's portable regular expression matcher
    streams.ss  -- SRFI-41 streams - lazy lists (I am the author)
    match.ss    -- Kent Dybvig's pattern matcher

My normal habit is to work in the interpreter with the current directory set to ~/scheme. I create a directory for each project, then use (lload "project/xxx.ss") to load project file xxx.ss into the interpreter and either (ed) or (vi) to edit the file. Directory ~/scheme has no files, only project directories.

Your task is to implement this environment on your system, if you are a Scheme user, or to describe your own programming environment. When you are finished, you are welcome to discuss the exercise in the comments below.

Pages: 1 2 3 4 5 6 7 8 9 10