Rubik’s Cube as STEM education tool?

Rubik’s Cube as STEM education tool?

STEM is an acronym for Science, Technology, Engineering, Math. Folks seem to often assert that what is wrong with contemporary education is lack of emphasis on STEM topics. There are forecasts of dire shortages of “technical” folks in the future. As a holder of an MSE from a reputable university who was involuntarily retired at age 50 along with tens of thousands of my co-workers, I find myself having some trouble accepting the word of “industry spokespeople” on this matter. It would be a shame to push people to going to all the trouble and expense of getting a technical degree only to find themselves unable to secure a relevant job. Sometimes I think it is an industry gambit to just tamp down the salary they have to pay for an engineer by taking care to have the supply outstrip the demand.

But having gotten those doubts and worries out in the open, I’ll confess to my belief that STEM emphasis is good for schools. I’ll not suggest that it is key to producing our next filthy rich Mark Zuckerberg, Steve Jobs or Bill Gates (each of whom dropped out of college anyhow). Time: Top 10 College Dropouts.   But I believe that it will help produce people who are better equipped to rationally assess claims that are made in the media.   Are GMO ingredients worth identifying on labels?   Could the “system” supporting our elections be tampered with?  Is the earth only 4000 years old?  Are vaccines worth their risk?  The list of issues that can be subjected to STEM-based consideration goes on and on.

Anyhow, there’s a Google+ “community” that is focused on the topic of STEM.  STEM on Google+.   Erno Rubik, creator of the Rubik’s cube puzzle, is a member of that community. Erno Rubik Google+ Home Page.   Today he shared to that community an interesting article that he found that asserts Rubik’s cubes can be a useful STEM education tool. Rubik’s Cube fits right in with STEM education goals.   Interesting reading.  I suppose I should confess that I’ve never actually mastered solving a Rubik’s cube myself, not even with the aid of the available YouTube how-to tutorials that the article mentioned.

Sharing that link to the article about the value of the Rubik’s cube in STEM education was the purpose of this blog post.   But if you wonder about that article’s use of the word “grit”, you might want to visit my old book report on the book by Paul Tough, How Children Succeed.

Unrelated to Rubik’s cube, but very much related to STEM education, you might also be interested in this item I recently shared with the Google+ STEM community: Yes We Code

What do you think?   Is STEM given proper emphasis in our school’s today?

Advertisements

Actual Code – C vs. Python for a Small Problem

Actual Code – C vs. Python for a Small Problem

For an embarrassing number of months now, I’ve been promising an article about a Python 3 solution to Project Euler Problem 2.  I’ve actually got it written and typed up into a file, but it is way too long.   So I’ve convinced myself I need to re-edit it into a short coherent series of articles, but somehow I’ve never gotten around to finishing that editing drudgery.   I will get to it Real Soon Now.   Honest.

Meanwhile, I don’t want this blog to look like I’ve abandoned it, so today I’m republishing here the most popular article yet from https://rdrewd.blogspot.com.   This article was originally published on 09/27/2014, and has, according to blogspot.com’s stats, had 2959 pageviews there, and received 46 +1 votes from readers (Yay!) and drawn 140 comments, far more than has been typical for my posts.

I’m not at all sure how to bring the blogspot.com comments over here to the wordpress incarnation of my blog, but the comment threads were quite interesting.   See http://rdrewd.blogspot.com/2014/09/actual-code-c-vs-python-for-small.html if you’d like to rummage in the comments.  Many other programming languages were dragged into solving the same problem, and the runtime performance was compared, and the problem was ratcheted up for find millions of prime numbers instead of just 20.  All in all, it was a great deal of fun for me to follow the comments.  Heck the comment thread even found a runtime performance surprise in the implementation of Go, and may have caused some improvement in x86 runtime performance of later Go implementations.

The picture at the top of this article is a Ulam spiral, borrowed from Wikipedia:  https://en.wikipedia.org/wiki/Ulam_spiral.  I wanted something pretty to lighten the page, something that had to do with prime numbers.  Full-disclosure:  the programs I’m about to describe have nothing to do with the Ulam spiral, except that the programs find prime numbers and the Ulam spiral shows surprising patterns in prime numbers when you lay them out on a number line that you’ve spiraled that way.

And so without further adieu, here’s a re-run of my most popular blog post so far…


If you aren’t much interested in writing software, this post is probably not for you. If you read the post without following the links to the example implementations, then I’m not sure what you are doing here, though you are certainly welcome to ask questions.

Recently on Quora.com someone asked to see C code to find the first 20 prime numbers. Seemed like an easy enough question,
but the first guy who answered it, gave a C++-based pseudocode and some tips on how to convert that to C. That answer didn’t make me happy. Heck, I figure if you’re going to write in some other language, why not Python as a sort of testable pseudocode, but the question really needs that answer to then be re-stated in C.

So I sat down and banged out a Python 2 program to find and print the first 20 prime numbers. That code is here: find20primes.py

I used a list to hold the list of primes. When the list grows to 20 items, I’m done. I start the list by telling it 2 is a prime number. I then only consider odd numbers as additional candidates. If the candidate is divisible by any of the prime numbers we’ve found so far, it is not a prime number. If the candidate isn’t divisible by any of the prime numbers we’ve found so far, then the candidate is a prime number so we append it to our list of primes and, in either case, add 2 to the candidate number to get the next candidate number to be tested. In C, we’ll need a little more book keeping for the list, but since the max size of the list is bounded (20 items), things should translate from Python to C pretty easily. One trick that isn’t entirely obvious is the use I made of Python’s for…else control structure to catch the case of the for loop not exiting via break. We can paper that over with a goto in C, or you can add some flags

I was thinking that C has labeled break statements to let me do sort of the same thing as that for…else. But much to my chagrin, that’s a feature of Java, not C. Oops. So, goto it is in my C translation of the program.

So I sat down with that Python listing open in one window and typed up find20primes.c.  That code is here: find20primes.c

I believe it is a straight-forward translation of the Python program into C. Of course, the C program is bigger in the sense of it has more lines of code. There are lines added to delimit the blocks and loops in the program, and lines added for variable declarations and lines added for the annoying book-keeping that C needs me to do where Python just handles those chores. I did run into some trouble where I didn’t get the book keeping entirely correct the first time through. The program outputted 20 primes, but it started with 2, followed by 73, followed by 3, and it left out 71 at the end of the list. Huh? Turned out I was mistakenly incrementing primecnt before I’d used it to fill in the next slot in the primes array, so I skipped the primes[1] slot and just got 73 there by bad luck. Python would have told me about an uninitialized variable if there’d been a spot in the Python program for me to have committed that same kind of error.

Having finally gotten both programs working, conventional wisdom is that the C code should be much faster than the Python code.
So I used the “time” command to see how the timings compare.

Using cygwin Python 2.7.8 on Windows 7 on a PC with an i5 processor and 8GB of RAM,

$ time python find20primes.py

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

real 0m0.136s
user 0m0.000s
sys 0m0.062s

Using cygwin cc 4.8.3 on that same Windows 7 PC:

$ time cc find20primes.c

real 0m0.238s
user 0m0.045s
sys 0m0.185s

$ time ./a.exe
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71

real 0m0.064s
user 0m0.015s
sys 0m0.015s

The execution time for the compiled C program was way less than the total time for the Python run, but if you add in the compile time for the C program, Python comes out ahead. Your mileage may vary.

By the way, if I throw in a -O option (“optimize the generated code”) on the cc command, it further slows the compile down, while the run time is about the same.

$ time cc -O find20primes.c

real 0m0.336s
user 0m0.031s
sys 0m0.185s

$ time ./a.exe
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71

real 0m0.086s
user 0m0.000s
sys 0m0.015s

(the “real” elapsed time varies a lot from run to run. These run times are so short the variability makes it hard to make fair comparisons in races between the programs). I suspect that the real time is dominated by the console I/O to print the results, so optimizing the details of the loops isn’t going to do much improving of things.

Now to make things more interesting, suppose I wanted to pass in as a command line argument the number of primes to be found. So long as the primes are still in the range of ints that only needs a malloc of the array in C but if the program is ever asked to get up into really big primes, the Python code will keep on chugging while the C code will need substantial rework to pull in an arbitrary precision integer library module. This blog article is already long enough, so I’ll leave that generalization to “findNprimes” up to you. How big does N have to be to break the C code’s use of ints? I suppose that with relatively minor surgery, you could convert over to use of long ints (or if your compiler supports them, to long long ints) in the C program.
Looking into it lightly, it appears that the cc included with Cygwin supports long long ints. The format strings will need adjusting. Use %lld instead of %d.

If you’ve feeling anxious to try further experiments, see how pypy does in handling the find20primes.py program. That’ll probably be more interesting with findNprimes.py with a really big value for N.

The moral to the story is that C may not be the best choice of programming language for this kind of problem.

Did you enjoy this article or was it too technical? Please add a comment down below so I know what you think about this sort of writing.

A great opinion piece on a career as a Unix sysadmin

A great opinion piece on a career as a Unix sysadmin

Computerworld has published a wonderful opinion piece by Sandra Henry-Stocker, a person who, like me, spent decades doing system administration.  A career in Unix: The best and the worst.   My brief blog article here is just to call her article to your attention.   I think it is well worth reading, especially if you are early in a career in the computer field.

(Credit where credit is due, the image I’ve shared here is borrowed [without explicit permission, but under a Creative Commons license] from the article to which I’m pointing.  That article gives credit for the photo to flickr/Courtney Carmod.  My interpretation of the picture is that it shows someone trying to grab hold of a fountain of water – not likely that they will succeed in grabbing much of the water, but on a hot summer day, a great deal of fun can be had in the trying.  See how nicely that ties to the material in Sandra’s opinion-piece?).

Enjoy!

Increasing Innovative Work Behavior

Increasing Innovative Work Behavior

This article was originally posted by me on March 8, 2010 on https://rdrewd.blogspot.com/2010/03/increasing-innovative-work-behavior.html and I’m re-posting it here on rdrewdblog.wordpress.com as part of my trying out wordpress in place of blogspot.com. Now on the one hand, it is a fairly minimalist blog post, barely more than a link to someone else’s online slide presentation. But on the other hand, it’s still a pretty good slide presentation, and it bothers me that this article has only been tallied as having 20 page views by people other than me (from 03/08/2010 thru 05/27/2016) and no one, it seems, has bothered to add a comment to it in all those years on blogspot.com.

In my opinion, Innovation is vitally important to our country and to the world. It is sad that a growing chunk of our economy and government seems to be focused on blocking new things. Ever extending copyrights, for instance to keep stuff from getting into the public domain, is beneficial to a few corporate interests, but the whole purpose of copyright law is to encourage creation of new works. But that’s drifting away from the original article’s point. So without further adieu…

real-innovators

Image used without permission, but with grateful acknowledgement of my source:  http://www.businesscomputingworld.co.uk/will-the-real-innovators-please-stand-up/

Increasing Innovative Work Behavior

Pretty much random travels on the web this morning brought me to an interesting little presentation on Increasing Innovative Work Behavior by  Gisela Jönsson.    The slide show is on her blog, http://www.mindspark.se/blog/, and though the slide show is in English, her blog is mostly in Swedish, which I can’t read.  So, for all I know, she may have lots of other wonderful things to say, but they whizzed right by my English-only head.

As summarized on her opening slide:

Fear does not make fertile soil for ideas.  To succeed at innovation, you must learn to embrace failure.

The posting I’m recommending is dated 3/7/2010.  Based on this sample of 1, I’m impressed with the results she got from using the presentation tool http://prezi.com/, which I confess I hadn’t heard of before.  I’d have been happier if I could have figured a way to snag a copy of her slide show instead of having to depend on the lifespan of the URL I referenced for you to be able to see Gisela’s slide show.  Anyhow, enjoy.

A link to another place for her slide show outside her blog:  http://prezi.com/fmwnrxxhje3c/increasing-innovative-work-behaviour/.

In closing

So, in closing, I ask “What innovative things have you tried lately?”.  Was it scary to try?  Too scary to try?

Please comment on this blog post to keep the discussion interesting.  If you enjoyed reading this brief blog post, please invite others to read it and comment here too.

Thanks,
Drew

 

Project Euler Problem 1 – In Python

This article originally was posted to http://rdrewd.blogspot.com/2016/02/project-euler-problem-1-in-python.html on 02/16/2016.  As part of trying to shift my blogging from blogspot.com to wordpress.com, I’m reposting the article here.  A follow-on article about Project Euler Problem 2 is coming here Real Soon Now.  There were some comments on that original post that I didn’t drag over with the body of the article itself.

Project Euler

Project Euler is a web site with hundreds of problems for you to tackle however you want to solve them. Some of them, if you are sufficiently adroit mathematically, can be solved on the back of an envelope. Most of them clearly need a piece of software to grind through the calculations. You can use whatever programming language you prefer. the site asks only for the answer. Each problem yields a numeric answer. If you provide the correct answer, the site credits you for solving the problem and grants you access to a discussion page. The discussions are mostly people bragging how they solved the problem. The bragging isn’t anything important, but it can be useful to look at other people’s approaches to see other ways of looking at the problem that perhaps hadn’t occurred to you.

The one “guideline” is that a good solution should need no more than a minute of time on your computer. If your solution needs way more time than that, then you should look for a better solution.

Tell Ya What I’m Gonna Do…

I’m going to show you how to solve some of the project Euler problems using the Python 3 programming language. Instead of having you install Python 3 on your computer, I’ll be using the “Python in the cloud” facilities of pythonanywhere.com. You can sign up for a free account of your own there. For small programs like ours, they offer their service for free. If you use their site to build something that becomes enormously popular (say, the next “Farmville” game), you’ll be needing to pay for their services, but we’re far, far from crossing that line between trivial computing load and significant computing burden.

It’d be useful if you figure out a good way to prepare your Python programs in a file, but you can start with notepad or whatever simple editor you are most comfortable with. If you tell us in the comments on this blog post what editor or IDE (“Integrated Development Environment”) you prefer, it may influence whether I write future articles addressing that editor or IDE.

Project Euler Problem 1

The first problem on project Euler is one that calls for very little code. I’ll tell you that I approached the problem as a computer programmer, but in the discussion page for the problem there were people who knew how to compute sums of a series using a simple formula and they were able to readily solve problem 1 using only pencil and paper. That’s just proof that although I’ve worked with mathematicians, I’m a software guy, not a mathematician.

The crux of problem 1 is: Find the sum of all the multiples of 3 or 5 below1000.

The example given makes clear that they are only asking us to consider positive integers. So no need to worry about negative 3 and negative 5 and so on. (“If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.”).

Spoiler Alert.

I’m going to talk here about how I solved the problem.  If you want to solve the problem on your own, stop reading here and go solve that problem. Feel free to come back later and tell us in comments how your solution is better than mine. Better in what sense?

Solving Problem 1 in Python

At this point, I am tempted to show you the small program that I used to solve the problem, but that is so small a program that you’d probably glance at it and walk away grumbling “nothing to learn here”, so I’ve decided to creep up on the solution a bit more slowly. I hope you pick up some comfort with Python programming along the way.

The General Shape of the Program.

Generally, the way to write a program is to start out with a rough idea of what the program should look like.  You can write this down in “pseudo-code” – a mixture of your native language and whatever bits of programming language structure you are comfortable to stir in. One of the delights of Python is that Python code looks a lot like pseudo-code, so if you nudge your pseudo-code into being real Python code, you can test out your pseudo-code by running the program. When it works, perhaps you are done, but if your actual target language isn’t supposed to be Python, then you have a working prototype that you need to re-code into your intended target language (Perhaps C or C++ or even some assembler language). It is worth noting that in the real world, often a manager faced with a working prototype that works well enough, will suddenly decide that a Python implementation is plenty good enough to declare the problem solved, even if it’s the first instance of Python code admitted into “production” use in that shop.

This program is going to need an iteration (loop) to consider all the natural numbers less than 1000.  And inside that loop it is going to need a conditional statement (if statement) to select the numbers that are multiples of 3 or of 5 (which for whatever reason are the numbers that this problem considers to be interesting). And for the numbers that are multiples of 3 or 5, we’ll need a little arithmetic to accumulate the sum of the selected numbers.

There’s more than one way to do it. For example, we could loop through all the non-negative integers <1000 and build up a list of the numbers that meet the criteria of being “interesting”. Then we could take the sum of that list to get the desired answer. But we have no further use for the list in this problem, so I assert it is simpler to just accumulate the sum as we go.

Another approach would be to generate the multiples of 3 and to generate the multiples of 5 that are less then 1000, and then tally up the generated lists, but you’d need to be careful not to include any numbers twice. Some numbers (e.g. 15) are multiples of both 3 and of 5, but only should get added into the sum for this problem once, so I assert it is simpler to just consider each of the candidate numbers and accumulate the ones that meet the criteria for being interesting.

Got another plausible shape for the solution of this problem?

So, I’m going to stick with my initial proposal which in Python-like pseudo-code looks like this:

sum=0
for num in numbers 1 thru 999:
    if num is "interesting":
       sum += num
print(sum)

Note that in Python, indentation is used to delineate the blocks of code. My Python-like pseudo-code follows that same convention. Thus the body of the loop statement is indented under the “for” that introduces the loop.
The body of the “then” clause that is made conditional by the “if” statement is indented inside the “if”. Since the “if” is inside the “for” loop, the accumulation of the sum is doubly indented. The initialization of sum to zero is outside of the “for” loop so it isn’t indented at all. The “print” statement is also not indented. We don’t want to print the partial sum on each iteration of the loop, so it is important not to indent that final “print”. But maybe when you are debugging, a print statement inside the loop would be a helpful addition. That would be done by adding another print statement and indenting it so it is inside the loop. You might want to include a comment on your debugging code so you can trim the debugging code out when your program is in good working order.

The “sum += num” statement is Python short-hand for “sum = sum + num”, since accumulating totals is such a frequently needed operation.

I hope you’ve noticed that the pseudo-code is not quite working python, so we aren’t done yet.  The most glaring magic is how do we really decide if a given number, which we’ve named “num”, is “interesting”?

How to test if a number is a multiple of some value

So we need to consider how to test a number to see if it a multiple of 3 (or of whatever number we want to test to see if it is a multiple of). Python has a modulo operator (%) that is documented here. x % y is how you ask Python to compute the remainder of dividing the number stored in x by the number stored in y. So all you need to realize is that if x is a multiple of y, that the remainder will be 0, and if x is not a multiple of y, then the remainder will not be zero.

So if we have a number to test named num, then we can test if num is a multiple of 3 by using this Python code:

num % 3 == 0

The result of that test expression is a True or False value (True if the remainder is 0. False if the remainder is not 0).
But we want to know if the number is divisible by 3 or is divisible by 5. Happily, Python has an “or” operator that will let us combine 2 True/False values in exactly the way we need.

Here’s a copy/paste of my pythonanywhere session where I tried this out:

>>> num=27
>>> num % 3
0
>>> num % 3 == 0
True
>>> num % 5
2
>>> num % 5 == 0
False
>>> num % 3 == 0 or num % 5 == 0
True

As you can see, the Python rules for operator precedence did exactly the right thing for us here, but I find that long expression a bit hard to read, so I added some un-necessary parentheses to make it easier for a human to parse.

>>> (num % 3 == 0) or (num % 5 == 0)
True

How to conjure up a list of numbers?

In many programming languages, Fortran for instance, the way you conjure up a sequence of numbers is you have a variable to serve as a counter. You initialize the counter to a starting value, then you increment the counter to get the next value and you need a test to decide when you’ve gone as far as you want to go. If you’ve programmed in C, that’s what a “for” loop in C does. But there’s a more Pythonic way to do this in Python, so please take care not to write Fortran (or C) code in Python syntax.  A Python “for” loop looks like

for x in list:
    do something with x

Where x is an arbitrary variable name that takes on each of the values in the list and the body of the loop (which I’ve represented as “do something with x”) processes each of the values as x is stepped through the list.

If you want to read more about looping in Python, especially if you are comfortable with looping in other languages, I strongly recommend Ned Batchelder’s blog post
Loop like a native“.

Not only does Python have a statement to consider each of the values in a list of values. It also has a built-in generator of a list of values. In Python 2, “range” is a built-in function to return a list of integers, but such a list takes up space. So “xrange” was introduced to return a generator that’ll provide the desired sequence of integer values on demand without ever actually creating the list as a whole in memory. xrange worked well enough and explaining the distinction between range and xrange was ugly enough that in Python 3, xrange became range and you only need to know its a generator if you’re interested in the details of how stuff works. So just say range(1000) to conceptually whip up a list of numbers 0 through 999.

So now our pseudo-code has morphed into runnable Python code:

sum=0
for num in range(1000):
    if (num % 3)==0 or (num % 5) == 0:
       sum += num

print(sum)

And we’re done, except for running the code to get the answer. I’ll not reveal the numeric answer here, so please learn how to run this yourself.

Mystified? Please tell me if I’ve confused you so I can polish things up before my next blog post.

Should I move the blog to wordpress.com?

if-at-first-you-dont-succeed-failure-may-be-your-style-3I’ve been irregularly blogging for several years now, mostly about software, particularly programming in the Python programming language.   There are 101 articles in my blog at https://rdrewd.blogspot.com, which is a site operated by Google, but I’ve found my confidence in their administration is slipping lately:

  1. blogspot.com provides statistics on pageviews of my articles.  But I’ve noticed inconsistencies in the data.   e.g. lately they have been reporting around 50 pageviews/day from Russia (which is a bunch, since I normally only see perhaps 3 dozen pageviews in any given day unless I’ve recently put up an article that for whatever reason is super popular).   But the statistics don’t seem to have those Russian pageviews allocated to the per-article statistics.My best guess is that the mysterious Russian page views (which are said to be coming from Internet Explorer running on Windows) are some kind of indexing or page-scraping visit that somehow isn’t counted as having viewed a particular article.I also have a feedjit widgit on my page’s sidebar boilerplate.   But lately that has stopped working.   I’m not sure if that’s from a recent update to my Chrome browser or to something that happened on the blogspot.com server or something that feedjit broke themselves.  So if I have to pick a new basis for statistics gathering, I might as well shop around for a new blog site server.
  2. blogspot.com seems to often lose the comments attached to the article.  I don’t know why that’s happening, but it is darn annoying.  Getting comments back about something I wrote is valuable to me, so I hate it when the comments vanish.

Will wordpress.com serve me better?   I won’t really know until I at least try it out.   So here’s a try.  How’s the format of this article look to you?   Any problems encountered when you leave me a comment?