Programming Praxis

In the previous exercise we studied a simple cryptographic hash. Today we will use that hash to write an equally-simple blockchain, which is the algorithm underneath Bitcoin and other cryptocurrencies.

A blockchain is a publicly-readable database in which data items are stored in blocks in an immutable, verifiable chain. The database admits two operations: adjoin, to add a new data item to the database, and validate, to verify that the database is complete and incorrupt. There is no delete operation; once a datum is added to the database, it can never be removed. There is no update operation; once a datum is added to the database, it can never be modified. And there is no sort operation; once a datum is added to the database, it can never be moved within the chain.

In our implementation, each block in the chain contains four fields: an index number, which starts from zero and is incremented each time a new datum is added; a datum, which can be anything (for simplicity, we restrict the data to strings); the previous hash number, and the current hash number, which we will discuss below.

The adjoin operation takes a blockchain and a datum and returns a new blockchain, which is a linked list of blocks; the first block in a blockchain has index 0, datum “Genesis Block”, and previous hash number 0. The current hash number is a Pearson hash of the concatenated block number, the datum, and the previous hash number. To adjoin a new block, compute the current hash number, allocate a block, attach it to the head of the blockchain, and return the new blockchain.

The validate operation recalculates the current hash number at each block in the chain. If any is incorrect, it halts and reports the blockchain is corrupt. Otherwise, if it reaches the genesis block without finding an error, it reports the blockchain is valid.

Your task is to write a program that implements the simple blockchain 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

Cryptographic hashes, also called message digests, are ubiquitous in modern cryptography — Brce Schneier calls them “the workhorses of modern cryptography” — used among other things in digital signatures, message authentication codes, as fingerprints to detect duplicate data, and as checksums to detect data corruption. Today we look at a simple example of a hash function, not suitable for cryptography, but useful for non-cryptographic purposes.

Peter Pearson describes a hash function based on a permutation table Tof the numbers 0 inclusive to 256 exclusive. Starting from an initial hash of 0, each byte of the message is accessed in order, added to the current hash mod 256, then the hash is replaced by the value in the permutation table corresponding to that sum. In some implementations, including Pearson’s original, the two bytes are XOR’ed rather than added mod 256.

If eight bits isn’t enough, Pearson gives a simple algorithm for extending the algorithm to sixteen bits. First, compute the normal 8-bit hash. Then, add 1 (mod 256) to the first character of the string, and compute the normal 8-bit hash of the modified string; since a modification to a single bit provides a large change in the hash value, the two hashes will be independent of each other. Finally, concatenate the two hashes. Pearson doesn’t mention it, but this scheme can be extended to any multiple of eight bits.

Your task is to write a program that computes the 8-bit and 16-bit Pearson hashes of an input string, given a suitable permutation table. 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 noticed the other day this list of the Top 75 Programming Interview Questions. I’m not sure of the origin of the list, and it does have a Java feel to it, but I was happy to see that we’ve covered almost all the questions on the list. One of the questions we missed is Number 57:

Write a program to print Floyd’s Triangle.

I wasn’t familiar with Floyd’s Triangle, so I had to peek at the solution. Floyd’s Triangle lists the numbers in order, in lines of increasing length, so a Floyd’s Triangle of size 5 looks like this:

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15

Your task is to write two programs that print Floyd’s Triangle; you must write two different programs that use two fundamentally different methods. 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’m not sure of the origin of today’s exercise, but given the contrived nature of the calculation, I suspect it’s a programming exercise for beginning programming students:

Our merchants receive “weekly” invoices, following these rules:

• Each Saturday marks the beginning of a new billing period.
• Each 1st of a month marks the begining of a new billing period.
• Within a year, billing periods are numbered consecutively, starting with billing period 1 on January 1st.

Thus, a billing period can be referenced by a year and period number.

Your task is to write a program that calculates the billing period for a given date. 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

It’s mid-May, so at most universities the semester has ended and it is safe for me to solve some of the exercises that students sent to me over the last few months. Here’s a fun little one:

Given a string containing embedded numbers, find the sum of the embedded numbers. For instance, given the string “11aa22bb33cc44”, the desired sum is 11 + 22 + 33 + 44 = 110. You may not use regular expressions.

Although the problem statement doesn’t say so, you may assume that the numbers of interest are non-negative integers. Thus, the purpose of the exercise is for students to iterate through a string, identify the digits in the string, and manipulate them numerically.

Your task is to write a program that sums the numbers embedded 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.

Pages: 1 2

Regular readers of this blog know that in my day job I am a programmer charged with maintaining an enterprise-wide database system, running on HP-UX (we’re switching to Linux next year) and Oracle 12g. We are in the process of replacing our existing report-writing software with a new, user-friendly product. Personally, I think it’s crazy to train non-technical people how to join tables and produce aggregates (the very first example in the training manual tripled my age to 183 because a one-to-many join was done incorrectly), but the users are excited because they will be able to get their data themselves instead of relying on the IT department to produce reports. I won’t tell you which reporting software we bought (you would recognize the name) or how much it cost (you will cry).

Some of the reports that we produce (probably a quarter to a third of them) can’t be done using the new software because the necessary fields aren’t in the data warehouse. The IT department (I am one of six programmers) will have to rewrite those reports using some combination of Oracle SQL*Plus and PL/SQL; the result will be plain-ascii reports delivered as LIS files in our standard enterprise software. Yes, 1960s-era reports, 132 columns by 66 rows per page, printed on a modern laser printer instead of green-bar fan-fold paper — that’s called progress where I work.

I’ve been looking at report-writing software. SQL*Plus actually isn’t bad — it must have been written in the 1960s for 1960s-era reports — but I still have to count the print columns to specify the linesize. SQL*Plus provides report headers and footers, page headers and footers that can include values drawn from the data, and control-breaks with record counts and totals. The one feature that is missing is proper headers and footers on each control-break; the field that caused the break must be included in the body of the report (on each detail line) rather than on a break header (so it takes horizontal space on the report, which may be in short supply), and there is no provision to include the break value in the total line of the break.

So I am in the market for a simple report generator. It must work with Oracle and produce plain-ascii output. Features include reprt headers and footers, page headers and footers, break headers and footers, all of which must be able to include values from the output. It has to be callable from a Unix shell script so it will fit with our enterprise system.

I’ve been looking for something suitable, and surprised I can’t find it. All of the solutions I have found are some combination of expensive, overly feature-full, or hard to use. I don’t want to use MS-Access with an ODBC connection. I looked at Jasper and BIRT; neither is suitable. I looked at every old Unix book in my library; I figured Don Libes would have something in his useful book, but he doesn’t. I’m looking for something at the level of a Unix shell script, something like Awk but with more of a report-writing flavor. On the next page you will see a sample report specification for a real report that I will need to write; SQL*Plus can handle most of that, but not the breakheader and breakfooter elements.

So I come to my readers and ask for help. Does anyone know of a simple 1960s-era Unix report generator?

Maybe I’ll write one.

Many thanks.

Pages: 1 2

We worked on linked lists in the previous exercise, so today we will work on arrays:

Given an array of distinct integers, replace each element of the array with its corresponding rank in the array. For instance, the input array [10,8,15,12,6,20,1] is replaced by the output array [4,3,6,5,2,7,1] because element 1 has rank 1, element 6 has rank 2, element 8 has rank 3, element 10 has rank 4, element 12 has rank 5, element 15 has rank 6, and element 20 has rank 7.

Your task is to write a program to replace array elements by their rank. 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 like to do exercises on linked lists. In languages like C, linked lists provide good drill for students who are uncertain about structures and pointers; in any language, lists provide good drill on recursion. Today’s exercise is about linked lists; we’ve seen some of these before, but it’s good to review:

1. Take a list of integers and rearrange it so all the even integers appear before all the odd integers, with both evens and odds appearing in the output in the same order as the input.
2. Take a list of integers, split it into two lists each containing alternate elements from the input list, then join the two lists back together.
3. Take a list of integers and rearrange it so alternate nodes are each greater than their two adjacent nodes; in other words, the integers are in alternating high-low order.

Your task is to perform the three linked list exercises 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

Yesterday was the 241st anniversary of the birth of Carl Gauss, who is perhaps the greatest mathematician who ever lived. In his honor, I picked a small task based on some mathematics that he discovered. Gauss’s Criterion states:

Let p be an odd prime and b a positive integer not divisible by p. Then for each positive integer 2 k − 1 < p, let r_k be r_k ≡ ( 2 k − 1) b (mod p) with 0 < r_k < p, and let t be the number of even r_k s. Then (b/p) = (-1)^t, where (b/p) is the Legendre symbol.

Your task is to write a program to compute Gauss’s criterion, and confirm that it is the appropriate power of the Legendre symbol. 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