Early Interesting Problems - Happy Ladybugs

We all love interesting problems. The trouble is that it's hard to find suitably interesting problems for students when they're just learning the basics. In the very beginning the problems practically dictate the solution:

  • loop over a list and add all the elements or calculate the sum of a list of integers.
  • Determine if number is prime
  • Convert a word into pig-Latin

It's not that there's no thought involved in solving these but the students already know the mechanics of solving these by hand so it's a direct translation into a program.

This isn't a bad thing and it is important but it's fun when we get to the next level. I've found that a number of the Hacker Rank archived competitions have "easy" problems that can be a good fit for beginners. One that I found and really like is Happy Ladybugs problem.

The problems is basically as follows:

You get a string of letters. Each letter represents a ladybug of a different color. Each letter also represents a location of the ladybug. A space (or underscore in the actual problem) represents a free space. For example "AABC DDA" is a line of 2 A colored ladybugs followed by a B colored one, C colored one, a blank space, 2 D colored and then one more A colored.

You can rearrange the line of ladybugs by swapping any ladybug with a blank space.

A ladybug is happy if it is next to another ladybug of the same color. The challenge is to determine if all the ladybugs can be made happy.

I like this problem because while it is non-trivial it is very approachable.

To me, the key is that while you can rearrange the list you don't have to. You only have to determine if it is possible to make the ladybugs happy. You don't actually have to do so.

The edge cases are pretty easy to deal with - a string of length one or two but then a little thought is required.

The first insight is that if there are no spaces, you can't rearrange the ladybugs so all you have to do is scan through the string to test to see if every ladybug has a neighbor of the same color.

The next insight, and the big one is that if you have at least one space you can arbitrarily re-order the string. You can show this is possible by using a single space to swap any two elements.

space = someletter
someletter = someotherletter
someotherletter = space

The final insight is that since you can arbitrarily re-order the ladybugs as long as you have at least 2 of each color, you can make them all happy.

Since my class is currently just starting dictionaries in Python we solved this with lists and then transitioned to dictionaries.

Here's a dictionary based solution:

def are_happy(s):
    This might miss some of the real edge cases in the hackerrank
    problem. I haven't read the problem carefully in over a year and 
    forget what it specified for things like lists of only spaces,
    lists with only one bug etc.

    Also, the Hackerrank question uses an underscore (_) instead of a space.
    # handle a string of less than 2 ladybugs
    if len(s)<2:
	return False

    # handle the string of 2 ladybugs - both must be the same and not a space
    if len(s)==2:
	return s[1]==s[0] and s[1] != ' '

    # handle the case of no spaces 
    if s.count(' ') == 0:
	# no spaces, every item must be next to one of the same color
	# so we loop from 1 to len-1 and for each item
	# check the one before and the one after
	# if we ever have an unhappy bug, we can just return False
	for i in range(1,len(s)-1):
	    if s[i] != s[i+1] and s[i] != s[i-1]:
		return False

	# if we ever get here every bug has at least one neighbor of the same color
	return True

    # if we get here it means there's at least one space so we can rearrange the bugs
    # however we please so as long as there are at least 2 bugs of each color
    # we can make them all happy

    # replace the spaces with "" since we don't want to count them
    # Since we know they were in the string we can rearrange but
    # they're no longer needed
    s = s.replace(" ","")

    # tally up all the bugs to see if there are at least 2 of each
    bugcounts = {}
    for bug in s:
	bugcounts.setdefault(bug,0) # set to 0 the first time we see this key

    counts = list(bugcounts.values())

    # if there is any value of 1 in the counts then there's a lone ladybug
    # that can't be made happy
    # so we return True (happy) if there are 0 counts of 1 in our list 
    return counts.count(1) == 0 

bugs="abaccbe ff eggggggg"

I love problems like these.

I just wish there was an easy way to find all contest problems of a certain level like "easy" or "medium." If anybody knows please share in the comments.

Catskills Conf 2017


Fall in the northeast is a special time. It's the apple harvest, the leaves change colors, and the air is crisp and clean. One of the best places to enjoy it is up in the Hudson Valley. That's why I love going to Catskills Conf each year.

I've written about Catksills Conf before and I usually describe it as "light tech conference meets summer camp." I love the event but I love being able to bring my students even more.

Hunter's a great place but it's a commuter school. That makes it harder for the students to get to know each other than if they all lived in the dorms. Getting away as a group for the weekend helps us jumpstart the process.



Then there's the conference itself. In addition to a great assortment of talks it has all the amazing extras.

Jonathan "Song a Day" Mann has been with us all three years of the conference to write summary songs for each day.

There are hikes


Workshops like blacksmithing


a live birds of prey show


not to mention folk music and square dancing.

All of this makes for a great experience but maybe the best part is that everyone is living together in the Ashokan Center. The conference doesn't allow questions after talks because the speakers are all living with the attendees for the weekend. We eat in the same cafeteria, go on the same hikes, relax at the same bonfire, and sleep in the same bunkhouses. As one of my students said:

There’s just something about sharing a conversation on the cloud computing network with someone who’s visiting from London while shooting basketball hoops in the middle of the woods that makes for a real take away experience!

I've had the good fortune to be able to bring my students up to Catskills Conf in the Fall for each of the last three years. Here's hoping that the tradition can continue for many more.

It's nice to be appreciated

Today was my 50th Birthday. I'm usually pretty low key on birthdays and today was no different. I got up, exercised, went to work, taught my class and went back to my office for office hours.

What a great surprise when all of a sudden my students from last year appeared at my office with a Happy Birthday a card and a cake: cake.jpg

It felt pretty terrific. I wasn't expecting this and was really moved.

We don't make the big bucks but little things like this make me feel pretty terrific as a teacher.

There's always something to learn (from your students)

One thing I've learned from teaching is that there's always something new to learn. For the kids, yes, but I'm talking about for the teacher.

The other day, I taught a lesson I've taught many times. Find the mode of a data set. That's the problem that they solve but the lesson is really about run time complexity, hidden complexity and using data structures in alternate ways.

I blogged about this before so you can get an earlier take there although the code isn't formatted correctly due to blog conversions.

As with the last time, the students had already written code to find the largest value in a list and also to find the frequency of an item in a list.

import random

def build_list(size,low,high):
    for i in range(size):
    return l

def get_max_value(l):
    for index,value in enumerate(l):
	if value > max_val:
	    max_index = index
	    max_val = value
    return max_val

def get_freq(l,requested_val):
    for value in l:
	if requested_val == value:
	    count = count + 1
    return count

They had to write mode prior to the class. In the past, students would generally come up with something like this:

def get_mode_1(l):
    mode_val = l[0]
    mode_freq = get_freq(l,mode_val)
    for index,value in enumerate(l):
	f = get_freq(l,value)
	if f > mode_freq:
	    mode_freq = f
	    mode_val = value
    return mode_val


They'd use their existing knowledge and the 'find the largest' idiom to find the mode by:

  • find the frequency of the first item and assume it's the mode so far
  • for each item in the list
    • find the frequency of that idem
    • if it occurs more than the mode so far then it becomes the new mode so far

There's a lot of good in this solution. The kids incrementally develop a solution, they use and exctend code and concepts they already know and understand and it's clear and understandable.

We would then run the code on larger and larger data sets and notice that it gets slow pretty quickly. This leads to an informal discussion of run time and the fact that there's hidden complexity – the call to freq in the main loop introduces a linear component so we have a loop within a loop and an N2 routine.

The big takeaway is get a feel for run time and to be aware of hidden complexity. We then move to a linear solution by using a list as buckets. You can read more about that in the original post.

What was interesting this time around was that most of the kids came up with a solution more like this:

def get_mode_2(l):
    freqs = []
    for item in l:
       f = get_freq(l,item)
    mode_count  = freqs[0]
    mode_value = l[0]
    for index,value in enumerate(freqs):
       if value > mode_count:
	   mode_count = value
	   mode_value = l[index]
    return mode_value

l = build_list(20,1,20)
m = get_mode_2(l)

Instead of calculating the frequency inside the loop they made a list of frequencies. freq[0] had the frequency of l[0], freq[1] the frequency of l[1] etc. They then loop through that freq list to find the largest element and that's the index of the mode value in the original list.

It's functionally the same as the first solution but in some ways it's very different. They built the data set they needed ahead of time instead of calculating the data on the fly and they used the concept of parallel lists.

I like the solution and it didn't prevent us from getting to the run time stuff but this did give me something to think about.

Why did this class led them largely to a different solution than the classes I've taught in the class. There are a lot of things to ponder since it's a college class that meets twice a week with kids from a range of backgrounds (CS and otherwise) vs a high school class that meets 5 days a week and the kids all had the same in class experience prior to this lesson. Did I do something differently before hand? Some assignments? Something I modeled? I'm not sure but it's something I'm going to ponder.

It will interesting to see if this was a one shot deal and my current class will solve problems as I predict moving forward or if I'm going to get to see a lot of new things.

A test result is just a test result

This past weekend was Catskillsconf - my favorite event of the year. I spent the weekend up in Ulster County with a bunch of my students. some great friends old and new, and Devorah. It was a great weekend but I was mostly offline.

As a result I missed a rather heated discussion in the CS Ed Facebook groups. The debate was over whether or not Strong AP CSP exam results are indicative of a good curriculum or good professional development (PD).

TL;DR - NO!!!!!

Further, anyone who thinks that a set of exam results can tell you that a particular PD sequence or curriculum is good shouldn't be allowed to call themselves a teacher and I don't want them anywhere near my kids.

I guess that language is strong, even for me but it's true.

Tests are designed to assess students and many tests don't even do that well. They shouldn't be used to measure something further removed.

The last time this idea made its rounds was using student test results for teacher evaluation. They do that in NY. A judge called the practice "capricious" and "arbitrary." My friend and former colleague Gary Rubinstein showed a year or so ago that standardized test scores varied enough from year to year so as to make the ratings useless 1

Using test scores to say a PD sequence is good? What if that PD focused on test prep? What if it did nothing in particular? When I was at Stuy and when I was at Seward Park the Calc teachers' students had great AP results. I can tell you that none of those teachers had any quality PD specific to AP Calc.

Curriculum? My mentor and friend Danny Jaye told me many times - "A great teacher can save a class from a horrible curriculum but a great curriculum will do nothing for a class with a horrible teacher." He was right. Again, what if the curriculum encourages test prep. What if pressure on the teacher encourages them to focus on test prep regardless of curriculum or PD (see my recent post).

An AP test measures one thing - how well the student did on the AP test. There are so many variables that go into a class:

  • Is it first period at 8:00am?
  • Is it the last class of the day?
  • Is it before lunch or right afterwards?
  • What about right after Gym.
  • What's the mix of students - every class is different
  • Is the teacher teaching the subject once a day? Two times? Five times?
  • How large is the class
  • How many other classes are the kids taking?

The list goes on and on. There are so many contributing factors that you just can't say "Good test results = good curriculum" or "good test results = good PD."

Want to know if a curriculum is good - have experienced teachers who know their subject run it a few times through and ask them. Same for PD.

Teachers know education a lot better than test makers, curriculum developers and PD providers. How about listening to them for a change?


sorry, I just got back from the weekend trip and am too tired to find the link. You can go to his site and search and while you're there, there's lots of good stuff to read.

Standards - Who are they for?

The big push at last year's CSTA conference was the release of the new CSTA K12 standards. It seemed that every other session was pushing them in one way or another. I've been meaning to share my thoughts about them or, more specifically, learning standards in general for a while but with announcement about federal funding for CS coming from the White House last week I thought it was time.

Before diving into CS standards lets talk about math.

To start I have yet to meet a math teacher that needs "the Standards" to know what to teach. Some how or other math teachers know they're supposed to teach in an algebra or geometry class. When NY moved to "integrated math" teachers were able to re-sequence classes without the benefit of "the standards" and when NY went back to Algebra, Geometry, then Alg 2 and Trig, teachers had no problem reorganizing classes again.

New teachers didn't go to "the Standards" to learn the ropes. Schools defined syllabi, teachers observed each other, shared resources, used lesson plan books and in general knew what they were supposed to teach and at what level.

In my quarter century of teaching, always in a math department we spent a lot of time talking about what we taught, when we taught it, how we taught it and at what level but until common core was forced down our throats we NEVER discussed "the Standards." We discussed our students, where we thought we could take them, and how to get them there. Somehow our students did alright.

More recently, the push has been on "The Standards," common core in particular.

Common standards sound good - kids in every school will learn the same things at the same level - but I contend that they aren't about learning. They're about testing.

Let's look at a few of the math standards. These were pulled directly from the Common Core:

Derive the equation of a circle of given center and radius using the Pythagorean Theorem; complete the square to find the center and radius of a circle given by an equation.

Use coordinates to prove simple geometric theorems algebraically. For example, prove or disprove that a figure defined by four given points in the coordinate plane is a rectangle; prove or disprove that the point (1, √3) lies on the circle centered at the origin and containing the point (0, 2).

Derive using similarity the fact that the length of the arc intercepted by an angle is proportional to the radius, and define the radian measure of the angle as the constant of proportionality; derive the formula for the area of a sector.

These aren't about deep thinking and problem solving. They're about very specific skills or techniques. They're also easy to put on a test. Much easier then assessing a students real problem solving ability.

Common Core comes hand in hand with standardized testing which is then used to punish students, teachers, and schools.

We keep hearing about individualized instruction - meeting the kids where they are but the standards tell us that kids MUST know specific things at specific times. You can't have both. In the best case, with "the standards" we can only meet students "where they are" within annual bands.

What has this led to? Narrowing curriculum for one thing. Since schools are evaluated based on the standardized exam in core subjects focus narrows and other subjects fall by the wayside.

Arguably worse is selective teaching within common core subjects.

Take for example, Geometry. The course is really "Logic and Deductive Reasoning using Euclidean Geometry as a Platform" but it's generally called Geometry. This class is supposed to be about getting kids to think. I've already shared a few standards above but let me tell you about an open secret - many schools don't really teach proof - arguably the most important part of the class.

In my last year at Stuy I graded Geometry regents for the city. I graded exams for two highly regarded unscreened schools. One that was lauded in a State of the Union address and the other equally hyped. I graded all of each school's students geometry regents so it wasn't just a sampling. Out of all the papers, only two or three scored more than 2 out of 9 points for the proof question and most were entirely left blank.

What happened? Proof is hard to teach and hard to learn but it's also only a small part of the standardized exam. It's critical for a school's survival and for the student to graduate that a passing score is earned. Rather than spending a large amount of time on few points and probably get a limited return I've been told that many schools spend much more time on topics that area easier to teach and have more weight on the exam. This makes the school look better and helps the student graduate but arguably the most important aspect of the course has been minimized.

High stakes testing leads to gaming the system. Common core standards come hand in hand with high stakes testing. We see the same with AP exams - there are schools that force students to take exams even when they are woefully prepared and mostly fail because this helps the school shoot up in the ratings.

This is what the common core math standards have given us. They're not for teachers - we don't need them - we know what to teach and only wish that the bean counters would indeed allow us to meet students where they are. Standards are about testing.

Let's move on to CS standards.

It might not be fair to compare CS to math since K12 math education has been around much longer and is more well defined and in theory having a set of standards gives us a common language to discuss, compare, and contrast all the content providers and curriculum developers out there. On the other hand, I also believe that with well prepared teachers who understand content and pedagogy the value isn't all that great. It's also worth considering the fact that nothing really makes the CSTA Standard writers special. There's no reason to think that another group - be they a handful of teachers or a content provider can't do a comparable job.

Here are some selections from the CSTA standards:

Design and develop a software artifact working in a team.

Compare and contrast various software licensing schemes (e.g., open source, freeware, commercial).

Design, develop, and implement a computing artifact that responds to an event (e.g., robot that responds to a sensor, mobile app that responds to a text message, sprite that responds to a broadcas

Demonstrate the value of abstraction for managing problem complexity (e.g., using a list instead of discrete variables).

Design algorithms u sing sequence, selection, and iteration.

Discuss techniques used to store, process, and retrieve different amounts of information (e.g., files, databases, data warehouses).

Compare and debate the positive and negative impacts of computing on behavior and culture (e.g., evolution from hitchhiking to ridesharing apps, online accommodation rental services).

Use simple encryption and decryption algorithms to transmit/receive an encrypted message.

Decompose a problem by creating new data types, functions, or classes.

Evaluate algorithms (e.g., sorting, searching) in terms of their efficiency, correctness, and clarity.

Use data analysis to identify significant patterns in complex systems (e.g., take existing data sets and make sense of them).

There's nothing wrong with these. They aren't specific enough to develop lessons from but, they can provide a consistent framework to discuss different offerings. Were the much more specific, we'd have the same issue I railed about with the math standards so this is a good thing.

Actually, in general, I don't have a problem with these standards. I might agree with some parts and disagree with others but that's neither here nor there.

To me the big concern on standards is what will they actually be used for. It's nice to think that it's a set of guidelines from which we can develop strong local experiences but I think this is somewhat naive. As states and the federal government bring CS Education into the fold there's no reason to believe that CS will be special. CS Ed will go the way of other subject areas. That means that whatever standards governments adopt, they will likely be used for high stakes tests rather than for true education. If you look to see how the sausage is made you can see the harm standards and standardized testing has wrought in subjects like math. CS Ed won't be far behind.

While we should be proud of all the work that's going on in our community it's more important now than ever to keep an eye on the overall big picture and be aware of how work intended for one purpose within the community can be used very differently by those outside of it. This is particularly important for advocates not in public schools. Public schools educate the majority of American students so CS4All means public schools. Standardized testing won't affect private schools (or private charters in many cases) nor will they affect colleges and in fact will be a boon to EdTech companies selling there wares. Many of the loudest voices in CSEd come from these contingents - it's important that they look to the greater issues, form their own opinions, and then act on what they believe is right.

Programming Idioms

I just read Jeff Yearout's recent post titled The Beginner's Garden of Concepts. Not directly related but it got me thinking about programming idioms.

I've been using the phrase "programming idiom" for years to describe a short useful recurring code construct. I didn't realize that it was officially "a thing" until doing a web search on the phrase years later.

As our students grow from newbies on I think it's helpful for them to see recurring and related patterns and programming idioms gives us a name to apply to many beginner patterns. An early idiom might be "finding the smallest in a list:"

dataset = [5,3,8,12,2,7]

min_index  = 0
for i in range(1,len(dataset)):
    if dataset[i] < dataset[min_index]:
	min_index = i

Another is the very similar and more general "do something on every item in a list:"

for i in range(len(dataset)):
    # do something to or with dataset[i]

By talking about constructs like these as idioms it helps students see and develop coding patterns. It also helps them to build mental abstractions. Each of the above idioms are a few lines of code but each are also a single concept. Students learn to think of them as the concept.

When students learn about list comprehensions in python they'll rewrite the "do something…" more like this:

[ f(x) for x in dataset]

but the pattern or idea is the same.

Other early idioms might include swapping variables:

tmp = a
a = b
b = tmp

and loops until an exit condition are met:

while (not_exit_condidtion):
    # do stuff
    modify variable that checks exit condition

Even more difficult concepts like recursion can be described in an idiomatic way:

def f(x):
    if BASE_CASE:
	return something
	new_x = modify_to_eventually_get_to_base_case(x)

Patterns like these, or idioms, come up over and over again. We don't have to explicitly mention them in our teaching but I think it's helpful to our students if we do.

NYC CS4All - This Is Not The CS We're Looking For

It's no secret that I'm something of an old curmudgeon in the K12 CS Education world and I've been critical of a number of initiatives and organizations over the years but I've been pretty quiet on the CS4All movement in NYC Department of Education. I've had and any number of concerns though.

This past week at the inaugural meeting of New York City's CSTA chapter we got a taste of the NYC CS4All Blueprint. A highlight was this video:

Along with the supporting web page.

TL;DR - in a elementary school CS class, the students kept tapping out drumbeats on the desk because they had drumming class the period prior. Now the drumming teacher is teaching rhythms that match segments of HTML so the students can tap and chant the line as a memory aid.

Sure, it's nice when teachers can work together to support each other but at the end of the day this is a mnemonic aid to memorize HTML. Nothing particularly innovative here. Mnemonics like this are great until there are too many to keep track of or ones that are too similar.

The part that saddened me was that this was the video that was chosen as a highlight, an exemplar. It was OK but there was nothing new or innovative. What was worse was that there was no computer science.

The kids were memorizing HTML. As we watched the video, my neighbor nudged me and asked "why are they memorizing HTML?" I would ask the same question. Now, I do think that HTML or some other mechanism to create content that can be shared with the world is important. Having students get there work out in the word can be tremendously rewarding and motivating. Also, although I'm not sold on it, some say that HTML is a good stepping stone to CS but still.

Let's try an experiment.

Imagine that lesson but instead of HTML the kids were learning Microsoft word so instead of a chant for <a href=""></a> you have a chant for putting a link into a word document or instead of a chant for <b>somethingbold</b> you have a chant like control-b-typestuff-then-control-b. Same lesson, same technique, still no CS. You could also say that this was just one video and maybe most of the year is about real CS. Maybe, but then why highlight this on the CS4All web site as a featured resource.

This was disappointing but not surprising.

Some will say that kids aren't ready for hardcore CS at that age. That's fine. We can have that discussion but if CS is appropriate for whatever grade was in the video then it should be real CS. We can also have endless discussing about what that is but memorizing HTML is not it.

I wondered if the video was representative so I looked at another. It turned out this was also a lesson on HTML and again the video could of been about any number of subject areas. I will give this one credit for highlighting that you can do "unplugged" activities but it wasn't really a CS activity.

Then there was this one. No video here but how we structure a CS lesson. We have this outline:

  • Warm-up
  • Mini lesson
  • Independent work time
  • Share session

Or, as we used to say back in the stone age:

  • Do Now
  • Instructional activity
  • practice
  • summary

Nothing new and nothing CS here. I used that model when I taught math but deviated from it more and more as I developed my CS teaching chops.

Finally I looked at this one. For full disclosure I have to say that Eric, the teacher, is a friend of mine and I know he's a dynamite teacher and I know he knows his stuff.

This video, however was all about differentiation. Just like the other resources, there's nothing wrong with them per se but there's not really about CS. You could reskin them for any subject.

I also agree with a lot of what Eric says in the video but as CS Standards take hold and standardized exams become the norm we'll find that individualized instruction and meeting students where they are is in direct conflict with the testing that comes with standards. I'll talk more about that in my standards rant that I keep putting off writing.

Sure, the resources site has a page with concepts like algorithms and many schools, for better or worse, in the upper grades just fall back on AP offerings but the more I dig the more it's apparent to me that CS4All in NY will be more about getting something into every classroom rather than something appropriate and good.

Using Emacs 37 - Treemacs file browser

I've been meaning to get back to making Emacs videos but I've been having trouble figuring out what to record.

People have asked for Magit but I only use the basics and I think there are already some great videos on it out there. I'd also like to get more comfortable with DIRED mode and then do a video on it but I'm not there yet. I've also been looking into packages that manage workspaces like Eyebrowse and Persp-mode but neither are really doing it for my workflow.

This morning I saw an post on the Emacs subreddit about Treemacs - a sidebar file browser similar to what the Atom editor has. It's pretty slick. I particularly like the integration with projectile.

I suspect I won't integrate a file browser side bar into my workflow - I've probably spent too many years with Emacs built in buffer commands but if like that type of interface, definitely check Treemacs out.

Awesome Cs Revisited

Saw this tweet the other day so I though I would try to plug the Awesome CS Education list I started on GitHub:

To answer the tweet, the closet thing I know to a list is Alfred Thompson's blog roll which is actually a post he wrote on his blog in 2012. Unfortunately his list can be hard to find and is somewhat out of date.

The idea of an "awesome" list is publicly hosting a simple site that is community driven and anyone can suggest additions and edits.

I put up a starter here and a few people have contributed but I'd love to get more people involved. Awesome lists have a number of advantages over other repositories.

  • Unlike blog posts, the site is easy to find.
  • Unlike private mailing lists or Facebook, anyone can see the content.
  • Anyone can suggest additions (although you need to create a Github account).
  • Anyone can download or fork the site.
  • It's essentially plain text and is easy to edit (just read the contribution guide).

So, there you have it. If you have a blog or resource to share please submit a pull request. Over time this could be a terrific single starting point for educators to get to a wealth of resources.

Enter your email address:

Delivered by FeedBurner

Google Analytics Alternative