Programming Praxis

There was no exercise Monday, and there is no exercise today. I’ve been very busy at work on the implementation of a major upgrade to our primary application, with go-live scheduled for early December. I’m responsible for a major component of the system, which unfortunately hasn’t yet worked properly. I’ll be sure to write an exercise this weekend for next Tuesday.

There will be no exercise today. To all my readers in the United States: Happy Thanksgiving!

Long-time readers of this blog will remember that five years ago I suffered a bi-lateral pulmonary embolism that nearly killed me; my right lung was 100% blocked, my left lung 60%. This past Tuesday evening I suffered a second pulmonary embolism. It was not nearly as serious as the first, I even went to work as normal on Wednesday, but with growing pain during the day I went to the hospital on Wednesday evening, was diagnosed, received medication to break up the clots — two shots in the belly, twelve hours apart, no fun I assure you — and came home Thursday afternoon.

Broadly speaking, there are two contributing factors to pulmonary embolism. The primary factor is blood chemistry, and that’s genetic; there’s nothing you can do about it, though if you know you are predisposed to blood clots, as I am, there is medication that can attenuate the risk — I’ll be talking to a hematologist in about two weeks. The secondary factor is lifestyle: smoking and obesity are both contra-indicated, as is a sedentary lifestyle. Sedentary in this context doesn’t mean sitting in front of a computer monitor for hours a day — recall that Serena Williams, one of the greatest tennis players of all time, had a pulmonary embolism a few years ago — it just means that you spend a few or several hours a day sitting still.

I assume that most of my readers are computer programmers, as I am, and spend much time sitting still. I urge you to get out of your chair every forty-five minutes or so and walk around for five or ten minutes to get your blood moving. It may save your life.

I’ll have another exercise for you next Tuesday.

Today’s exercise won’t ask you to write code. Let me tell you why.

I bought a new printer to replace my old printer that had failed. Both the salesman at Micro Center and the printer manufacturer’s sales rep, who was in the store that day, assured me that the printer would work with my Debian Linux system, and the manufacturer’s sales rep even gave me the web page where I could download the driver. I bought the printer, took it home, and installed the driver.

It didn’t work. My computer would no longer boot. I took computer and printer to the Knowledge Bar at Micro Center, but they don’t have sufficient Linux experience to figure out what’s wrong. After a few days, I resigned myself to re-installing the operating system.

That’s when I found out what had happened. At the point where the Linux installer asks you to specify the partition table, it told me that I had an invalid partition table and asked me to fix it, manually, before proceeding with the installation. Somehow, installing a printer driver corrupted the partition table. I won’t tell you the name of the printer manufacturer that was stupid enough to manage that trick, but it’s a big name that you would certainly recognize. Needless to say, I will be returning the printer and buying a different printer from a different manufacturer.

But before I do that, I have to fix my partition table, re-install my operating system, and restore my data from backups. As I write this on Thursday afternoon, I’m partway through that process, but I have already verified that I have a list of all installed software and that my file backup is readable.

Your task is to make sure that your backup and restore procedures are effective; if they aren’t, fix them. You should at least perform a single-file restore to demonstrate that your backup and restore procedure has at least a minimal chance of working when you need it. It looks like I will end up okay, but not without a lot of worry and a few choice words directed at a printer manufacturer that ought to know better.

Today’s exercise appears regularly on lists of interview questions. We’ve done something similar in the past, but since it’s so common we’ll do it again.

Given a matrix, print a list of elements of the matrix. Start in the top-right corner of the matrix, move left across the top row, then down the left column, then across the bottom row, then up the right column to the element below the top row, then left, then down, then right, and so on, collecting the elements of the matrix as it goes. For instance, with this matrix

     1  2  3  4
     5  6  7  8
     9 10 11 12
    13 14 15 16
    17 18 19 20

the elements are collected in order 4, 3, 2, 1, 5, 9, 13, 17, 18, 19, 20, 16, 12, 8, 7, 6, 10, 14, 15, 11.

Your task is to write a program to unwrap the elements of a matrix in the indicated spiral. 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

There is no exercise today.

My mother, who is eighty-eight years old, was the bottom of three people who fell down some stairs a few days ago, and sustained a cut on her head that required five stitches, four broken ribs in her left back, and one bruise that runs from her left forearm, up to her left shoulder, and down the left side of her back, all the way to her left calf. Her injuries aren’t serious, but at her age neither are they simple, and it’s been difficult.

I’ve spent two recent overnights in hospital emergency rooms, and have been taking care of my mother during the day, so I haven’t had time to write an exercise for today. I do hope to have one ready for Friday.

In the meantime, none of my readers has done all the exercises. So pick an exercise you haven’t done and post your solution in the normal way.

We introduce today a new feature of Programming Praxis: essays. An essay isn’t an exercise; it doesn’t present a task for you to perform, but instead provides extended discussion and complete source code. Though essays may be based on exercises, the idea is that an essay can delve more deeply into a topic than is possible in the limited space and time of an exercise.

Our first essay is about a topic dear to my heart: programming with prime numbers. The essay presents two versions of the Sieve of Eratosthenes, uses trial division to identify primes and factor composites, and provides the Miller-Rabin pseudoprime checker and Pollard rho factoring algorithm. Source code is given in five languages: C, Haskell, Java, Python, and Scheme.

Please read the essay, and feel free to comment on it below; comments on the essay itself are closed. Let me know if you see any errors. And feel free to link to the essay on the internet if you know of places where it is appropriate.

Wow. Now I know the secret to getting lots of page hits and reader comments.

Thanks to all who sent their best wishes in comments and private emails. It’s comforting to know that so many of you care. Thanks also to Remco for posting exercises in my absence. Still, though I appreciate your words, what would really make me feel good is for you to solve an exercise and post the solution.

I’ve been home for a day now, and I’m fine. The blood clots are completely dissolved, and my blood chemistry is nearly correct to prevent future clots — another few days of medication and blood tests should get it exactly right. I’ll be returning to work next Monday, and I’ll likely return to blogging the week after that.

Thanks again,

Phil

I write this from my hospital bed, where I am recovering from blood clots in both lungs; my right lung was 100% blocked, my left lung 60%. I am doing well, and expect a complete recovery.

However, I will not be blogging for a while, probably for two to four weeks. Until I resume, your task is to visit Programming Praxis every Tuesday and Friday morning and do any exercise you have not yet done; I want to see those comment queues filling up.

[ Programming Praxis wishes a very merry Christmas to all my readers and their families. There will be no exercise today. Exercises will return on their normal schedule next Tuesday. ]

In those days a decree went out from Caesar Augustus that the whole world should be enrolled. This was the first enrollment, when Quirinius was governor of Syria. So all went to be enrolled, each to his own town.

And Joseph too went up from Galilee from the town of Nazareth to Judea, to the city of David that is called Bethlehem, because he was of the house and family of David, to be enrolled with Mary, his betrothed, who was with child. While they were there, the time came for her to have her child, and she gave birth to her firstborn son. She wrapped him in swaddling clothes and laid him in a manger, because there was no room for them in the inn.

Now there were shepherds in that region living in the fields and keeping the night watch over their flock. The angel of the Lord appeared to them and the glory of the Lord shone around them, and they were struck with great fear. The angel said to them, “Do not be afraid; for behold, I proclaim to you good news of great joy that will be for all the people. For today in the city of David a savior has been born for you who is Messiah and Lord. And this will be a sign for you: you will find an infant wrapped in swaddling clothes and lying in a manger.”

And suddenly there was a multitude of the heavenly host with the angel, praising God and saying: “Glory to God in the highest and on earth peace to those on whom his favor rests.”

When the angels went away from them to heaven, the shepherds said to one another, “Let us go, then, to Bethlehem to see this thing that has taken place, which the Lord has made known to us.” So they went in haste and found Mary and Joseph, and the infant lying in the manger. When they saw this, they made known the message that had been told them about this child. All who heard it were amazed by what had been told them by the shepherds.

And Mary kept all these things, reflecting on them in her heart. Then the shepherds returned, glorifying and praising God for all they had heard and seen, just as it had been told to them. — Luke 2:1-20