Spiral Wrapping

October 14, 2014

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

No Exercise Today

July 9, 2013

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.

Back Home

May 12, 2010

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

Taking A Break

May 9, 2010

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.

Merry Christmas

December 25, 2009

The Adoration by Correggio[ 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

Update: The Daily WTF

August 14, 2009

Alex Papadimoulis has agreed to change the name of his series of programming exercises, thus ending the dispute between us. I thank him for agreeing to the change, and wish him well.

To all of my regular readers: I apologize again for involving you in this dispute. The next exercise will be published in a few hours, and I hope you are as anxious to get back to programming as I am.

To all those people who found my blog for the first time: Welcome! Please stay. Enjoy the exercises. And please post your solutions, so we may all learn from your work.

The Daily WTF, a web site that chronicles “curious perversions in information technology,” recently introduced a new feature called Programming Praxis in which simple programming exercises are assigned to readers who post their solutions and discuss the exercise in the comments. Alex Papadimoulis runs The Daily WTF.

On June 23rd, Programming Praxis published an exercise based on one of the stories at The Daily WTF. That was done only after consulting with The Daily WTF to ensure there was no copyright violation, and credited The Daily WTF as the source of the exercise, even providing a link back to the original The Daily WTF article.

Papadimoulis liked what he saw at Programming Praxis, and began discussing with me some kind of collaboration between the two web sites. After some discussion, on July 22nd The Daily WTF published a programming exercise of its own, based on the Russian peasant multiplication algorithm. That article used the phrase “Programming Praxis” in its title, and credited me with the idea, but did not refer to the Programming Praxis web site. That article was a success, generating over seven hundred comments with a high signal-to-noise ratio, and Papadimoulis and I began seriously discussing a collaboration.

While we were discussing how a collaboration would work, on July 29th The Daily WTF published a second programming exercise second article that also used the phrase “Programming Praxis” in its title, and borrowed the exercise from one previously discussed at Programming Praxis, but did not credit me or refer to the Programming Praxis web site.

At that point discussions about collaboration broke down. The problem was that the two sites had different goals: The Daily WTF is primarily entertainment, and Programming Praxis is primarily educational. The difference was highlighted by the decision to use the Josephus problem; Papadimoulis selected that problem because he thought of a neat way to use an animated gif to show how the soldiers die. I notified Papadimoulis that no collaboration was possible, and asked him not to use the name “Programming Praxis” in any future exercises he might publish.

Papadimoulis never responded to my email, but did respond on The Daily WTF by publishing on August 5th another exercise based on a common mathematical problem. The problem used the phrase “Programming Praxis” in its title, and Papadimoulis wrote, in the first comment, that “Programming Praxis” now had its own category on The Daily WTF; he also asked readers to submit tips for future “Programming Praxis” articles.

The name “Programming Praxis” belongs to me, not Papadimoulis. I have been publishing under that name twice a week for six months, and own the programmingpraxis.com domain. Papadimoulis is using the name without my permission, and against my expressed wishes.

Papadimoulis’ improper use of the name has already caused confusion in the marketplace of ideas. At proggit (http://www.reddit.com/r/programming/comments/95o33/programming_praxis_josephus_circle/), a reader named “bhrgunatha” says “I think the real WTF here is they are taking these exercises from the actual programming praxis site apparently against the license.”

After publication of the third exercise, I sent an email demanding that Papadimoulis cease and desist from using the phrase “Programming Praxis” to describe his weekly programming exercises. After four days, Papadimoulis responded that it is now too late to change the name, and that we would have to be happy to share it. I am not happy to share my name, and on Monday I sent a registered letter for next-day delivery demanding that Papadimoulis cease and desist from using the phrase “Programming Praxis.” However, The Daily WTF continues to use the phrase “Programming Praxis,” publishing yet another exercise under that name today.

A log of emails between Papadimoulis and me, complete except for a few emails arranging the time of our telephone conversation, appears on the next page. The emails show the history of the situation as it transpired.

I must defend my name. Thus, I am publishing this account of what happened. I will also explore trademark protection for my name, and such other legal action as may be required.

Thank you to all my regular readers for listening to my story. If you wish to help, you may act to provide wide attention to this situation in the blogosphere; feel free to post a link to this blog entry to your favorite forum, and add your comments. Your code, your comments and your private emails inspire me to continue publishing Programming Praxis. I apologize that I must engage you in this ugliness.

/s/ Philip L. Bewig

Pages: 1 2

A Golden Exercise

July 12, 2009

Copyright eyehook.com.  Used under a Creative Commons Attribution 2.5 License.The exercise that will be published on Tuesday will be the fiftieth exercise published at Programming Praxis, marking our Golden Anniversary. My thanks to all you readers, and especially those who contributed code and other comments, for making this blog special. I am always delighted to hear from my readers, especially if they are contributing an idea for an exercise (hint, hint). It’s a lot of fun writing these exercises, but also a lot of work, and your contributions make it worthwhile. <grin>I can tell that the blog is starting to be successful because spam comments, which I must delete manually, now exceed ham comments.</grin>

Tuesday’s exercise will also introduce a change in the structure of the exercises. The suggested solution will be on a separate page published forty-eight hours after the exercise. That gives regular readers a chance to work on their own solutions without being influenced by the suggested solution. Comments will be attached to the exercise, not the solution.

Our first fifty exercises have developed several themes: related sequences of exercises involving prime numbers and cryptography, exercises in data structures like ternary search tries and exercises in algorithms like modular arithmetic, some exercises simple and others not-quite-so simple, and puzzles like sudoku and Feynman. The next fifty exercises will be more of the same, featuring some new sequences of related exercises, some old friends, and the odd puzzle or two. And I am always open to suggestions!

To celebrate our Golden Anniversary, Tuesday’s exercise will be somewhat more ambitious than normal, so get those compilers revving. Happy coding! And please enjoy a piece of virtual anniversary cake!

And now, may I ask for your help. I would like to move the site from wordpress.com to its own host, still running WordPress software, so that I can finally fix the theme and, more importantly, automate some processes that I am currently doing by hand (and some others I am not doing at all). But I have never blogged before, and have no experience with hosting, or migrating a domain registration, or maintaining a WordPress installation. If some reader would like to offer advice, please contact me at programmingpraxis@gmail.com.

Programming Praxis has a new web address: programmingpraxis.com. For the moment, Programming Praxis is still hosted at wordpress.com, so the old address at programmingpraxis.wordpress.com will still work (it maps the old address to the new address), but that will change sometime in the future. Please update your bookmarks. The RSS feed moves to programmingpraxis.com/feed. All existing content, including your comments, remains.

Programming Praxis also has a new theme, and a logo, which was designed by Remco Niemeijer. Thanks, Remco! Some of the pages have moved, others will be moving shortly, some will change, and there will soon be some new additions.

Thanks to all my readers for their patience during this transition. Please let me know if you see anything that breaks, or if you have suggestions for other changes. You can contact me at programmingpraxis@gmail.com.

Follow

Get every new post delivered to your Inbox.

Join 643 other followers