[ SB Coded ]

My first encounter with the apparently long-lived Zawinski’s Law has only been from skimming through “Version Control by Example”. I feel that the law has a new corollary.

Original

Every program attempts to expand until it can read mail. Those programs which cannot so expand are replaced by ones which can.

My take:

Every program attempts to expand until it can read mail integrate with social.  Those programs which cannot so expand are replaced by ones which can.

I’m a little surprised that I wasn’t able to find someone else who’s already added this corollary. But I have a feeling that I must have just missed it somewhere. Please let me know in the comments!

A cool little puzzle was handed to some high school freshmen. Take a look at the following triangle:

The values for a through i each map to a unique integer in the range of (1-9) such that a + b + c + d = d + e + f + g = g + h + i + a = x. Summing all of the values along each edge should add up to some value x. Find all values for the letters a through i such that satisfy the condition.

It was a little sad that that my first instinct was to just brute force the answer but now here it is:

#!/usr/bin/python3

import itertools

numbers = itertools.permutations(range(1,10))

def isValid(vals):
 a = sum(vals[:4])
 b = sum(vals[3:7])
 c = sum(list(vals[6:]) + [vals[0]])
 return (a==b) and (b==c)

solutions = filter(isValid, numbers)

# solutions has all of the answers, but I want to remove some of the duplicates
alreadyseen = []
def isUnique(s):
 sol = (s[0], set([s[1], s[2]]), s[3], set([s[4],s[5]]), s[6], set([s[7], s[8]]))
 if sol not in alreadyseen:
   alreadyseen.append(sol)
   return True
 else:
   return False

solutions = filter(isUnique, solutions)
for solution in solutions:
 print("a=%d, b=%d, c=%d, d=%d, e=%d, f=%d, g=%d, h=%d, i=%d" % solution)

This program spits out 108 solutions. I don’t remove triangles that are “rotations” of one another, but I don’t allow cases where the second and third value of an edge are swapped.

I imagine that this could be a really good code golf problem assume that a much simple solution doesn’t exist. (Which there probably does…)

As a TA for a C++ class way too much of my time has to be dedicated to saying things: “I’m sorry, but that’s just how it is with C++”. I’ve never had to deal with coding large projects in C++ (I like to think that’s what keeps me sleeping soundly at night) so I don’t feel justified in vilifying C++ in front of the students. But I just don’t know how much longer I can keep up the charade; do I really need to keep on pretending? No language is perfect but having to explain why

DerivedClass d; SuperClass a = d; 

doesn’t always work like expected… well it just brings tears to my eyes. The students have every reason to facepalm. Or why they don’t need to explicitly call that super class’s destructor.  Or why do the errors mention v-tables and do I need to know about them? What the hell is static_cast<>() anyway? Why are these error messages about templates all about? I don’t remember Java errors being this bad…  But the class definition doesn’t say virtual! How is it being overridden?

I’m sorry class, I’m sorry…

But these are growing pains and sadly learning how to decipher your tools is just as much part of coding as is deciphering your algorithms. I just wish that g++ was more forgiving.  I wish that it’s error messages held the same amount of sympathy for it’s users that I do for the students. One day, perhaps even one day soon, Clang will be able to save the day…

I think that constructors should not be allowed to be declared public. This would require classes to have static Creational functions instead of allowing users the direct ability to allocate memory. Doesn’t it feel a bit wrong being able to control when an external API allocates memory? I’ve always thought that one of the major goals of java was to abstract away the idea of memory management, and this would be a significant step towards that.

If the language doesn’t publicly expose the ability to create a new instance of an object, but instead requires object creation to be done through an API call then the API designer has much more flexibility down the road. At anytime the API could switch to using a Singleton or Pool implementation to manage object creation, with the client being none the wiser.

Not having “new” be public also has another advantage: named creator functions. Many times the class name is actually a bad name for the constructor, or too verbose of a name. What is also gained is the ability to have multiple creational functions with the same parameter list.

I’m sold on this idea, Smalltalk in practice seems to implement this idea. I wonder how long it will take before the other OO languages follow suit.

You’re grading two pieces of code handed to you; which of the two gets a better grade?

• The code that sorts a list of items in O(nlg(n)) for all n
• The code that sort in O(n²) but performs faster for n < 100

Should students be graded on the real-world performance of their programs? I am a TA for a data structures/C++ course and someone asked: “Do we grade performance?” The knee jerk answer was an unequivocal: “YES!“. But now, I’m not so sure anymore. The data structures that are taught and used to give structure to our data; sometimes we get lucky and that structure gives as faster running programs.

Do we ever ask students to write fast code instead of theoretically fast code? How should something like timsort ( O(nlg(n)) for large values of n, but behaves like O(n²) for small values of n) be graded versus the more theoretically pure mergesort?

I find quicksort to be a great example when thinking about real world versus theory world. Quicksort is a magical algorithm that theory tells us runs in  O(n²) but in the real world it tends to behave nicely and within the bounds of O(nlg(n)). But now comes the weird part: Quicksort can actually be implemented to run in honest-to-goodness O(nlg(n)) (An algorithm does exist to find the median of a list in O(n) see wikipedia here). But that implementation is such a pain to code and the constants hidden in that O(n) are so evil, that you would mad to implement it. In fact, I would probably much rather implement timsort. But I would then have to be weary of my algorithms professor ever looking at my code. Specifically, I had a professor who very specifically ingrained into my mind that bubblesort is NEVER the answer. But maybe the right answer is: never bubble sort large arrays.

We teach our students things like debuggers and memory checkers, does it make sense to add “profiler” to their arsenal of tools? Should real-world performance of their code also be factored into their grades? Do we have so little faith in our students that we’re afraid that they’ll create horrific messes of code if we focus on making them write faster code?

Spoiler #2: It’s actually a chat log with my friend Brian that goes over all of the features that I use on a daily basis. Should take no more than 15 minutes to play along with it.

The tutorial is here: http://sbcoded.com/tutorials/a-quick-introduction-to-screen/

So I ended up giving a friend a quick tutorial on screen. Since the chat played so well as a tutorial. I figured that I might as well put in the extra 15 minutes and post it in online for anyone else that might want to learn something about screen . (If I get to save explaining this to one person I’ll already have a net gain of time). As always, comments welcome. I wouldn’t be apprehensive to the idea of adding to the chat log to make it a bit more complete.

After being dormant for far too long I’ve decided to bring SBCoded back from the dead I’m thinking of paying a little attention to my programming scrapbook again. I’ll be uploading and documenting some new projects up here, the old ones are basically dead (Aside from the JPF stuff). So I hope that you find some use out of what I have done and what I have to say.