Dancing algorithms and algorithms for dance apps

Browsing through teaching material a few years ago, I had stumbled upon dancing algorithms, which illustrate common algorithms in computing using dance [1] and couldn’t resist writing about since I used to dance folk dances. More of them have been developed in the meantime. The list further below has them sorted by algorithm and by dance style, with links to the videos on YouTube. Related ideas have also been used in mathematics teaching, such as for teaching multiplication tables with Hip Hop singing and dancing in a class in Cape Town, dancing equations, mathsdance [2], and, stretching the scope a bit, rapping fractions elsewhere.

That brought me to the notion of algorithms for dancing, which takes a systematic and mathematical or computational approach to dance. For instance, the maths in salsa [2] and an ontology to describe some of dance [3], and a few more, which go beyond the hard-to-read Labanotation that is geared toward ballet but not pair dancing, let alone a four-couple dance [4] or, say, a rueda (multiple pairs in a circle, passing on partners). Since there was little for Salsa dance, I had proposed a computer science & dance project last year, and three computer science honours students were interested to develop their Salsational Dance App. The outcome of their hard work is that now there’s a demonstrated-to-be-usable API for the data structure to describe moves (designed for beats that counts in multiples of four), a grammar for the moves to construct valid sequences, and some visualization of the moves, therewith improving on the static information from Salsa is good that counted as baseline. The data structure is extensible to other dance styles beyond Salsa that have multiples of four, such as Bachata (without the syncopations, true).

In my opinion, the grammar is the coolest component, since it is both from a scientific and from an engineering perspective the most novel aspect and it was technically the most challenging task of the project. The grammar’s expressiveness remained within a context-free grammar, which is computationally still doable. This may be because of the moves covered—the usual moves one learns during a Salsa beginners course—or maybe in any case. The grammar has been tested to cover a series of test cases in the system, which all worked well (whether all theoretically physically feasible sequences feel comfortable to dance is a separate matter). The parsing is done by the JavaCC parser, which carries out a formal verification to check if the sequence of moves is valid, and it even does that on-the-fly. That is, when a user selects a move during the planning of a sequence of moves, it instantly re-computes which one(s) of the moves in the system can follow the last one selected, as can be seen in the following screenshot.

Screenshot of planning a sequence of moves.

The grammar thus even has a neat ‘wrapper’ in the form of an end-user usable tool, which was evaluated by several members of Evolution Dance Company in Cape Town. Special thanks go to its owner, Mr. Angus Prince, who served also as external expert on the project. Some more screenshots, the code, and the project papers by the three students—Alka Baijnath, Jordy Chetty, and Micara Marajh—are available from the CS honours project archive.

The project also showed that much more can be done, not just porting it to other dance styles, but also still for salsa. This concerns not only the grammar, but also how to encode moves in a user-friendly way and how to link it up to the graphics so that the ‘puppets’ will dance the sequence of moves selected, as well as meeting other requirements, such as a mobile app as ‘cheat sheet’ to quickly check a move during a social dance evening and choreography planning. Based on my own experiences goofing around writing down moves, the latter (choreography) seems to be less hard to realise [documenting, at least] than the ‘any move’ scenario. Either way, the honours projects topics are being finalised around now. Hopefully, there will be another 2-3 students interested in computing and dance this year, so we can build up a larger body of software tools and techniques to support dance.

 

Dancing algorithms by type

Sorting

– Quicksort as a Hungarian folk dance

– Bubble sort as a Hungarian dance, Bollywood style dance, and with synthetic music

– Shell sort as a Hungarian dance.

– Select sort as a gypsy/Roma dance

– Merge sort in ‘Transylvananian-Saxon’ dance style

– Insert sort in Romanian folk dance style

– Heap sort also as in Hungarian folk dance style

There are more sorting algorithms than these, though, so there’s plenty of choice to pick your own. A different artistic look at the algorithms is this one, with 15 sorts that almost sound like music (but not quite).

Searching

– Linear search in Flamenco style

– Binary search also in Flamenco style

Backtracking as a ballet performance

 

Dancing algorithms by dance style

European folk:

– Hungarian dance for the quicksort, bubble sort, shell sort, and heap sort;

– Roma (gypsy) dance for the select sort;

– Transylvananian-saxon dance for the merge sort;

– Romanian dance for an insert sort.

Latin American folk: Flamenco dancing a binary search and a linear search.

Bollywood dance where students are dancing a bubble sort.

Classical (Ballet) for a backtracking algorithm.

Modern (synthetic music) where a class attempts to dance a bubble sort.

 

That’s all for now. If you make a choreography for an algorithm, get people to dance it, record it, and want to have the video listed here, feel free to contact me and I’ll add it.

 

References

[1] Zoltan Katai and Laszlo Toth. Technologically and artistically enhanced multi-sensory computer programming education. Teaching and Teacher Education, 2010, 26(2): 244-251.

[2] Stephen Ornes. Math Dance. Proceedings of the National Academy of Sciences of the United States of America 2013. 110(26): 10465-10465.

[3] Christine von Renesse and Volker Ecke. Mathematics and Salsa Dancing. Journal of Mathematics and the Arts, 2011, 5(1): 17-28.

[4] Katerina El Raheb and Yannis Yoannidis. A Labanotation based ontology for representing dance movement. In: Gesture and Sign language in Human-Computer Interaction and Embodied Communication (GW’11). Springer, LNAI vol. 7206, 106-117. 2012.

[5] Michael R. Bush and Gary M. Roodman. Different partners, different places: mathematics applied to the construction of four-couple folk dances. Journal of Mathematics and the Arts, 2013, 7(1): 17-28.

Advertisement

Dancing Algorithms

Yes, it appears that the two can go together. Not in that the algorithms are dancing, but one can do a dance with a choreography such that it demonstrates an algorithm. Zoltan Katai and Laszlo Toth from Romania came up with the idea of this intercultural computer science education [1], with a theoretical motivation traced all the way back to Montessori. It has nothing to do with the scope of my earlier post on folk dancing and cultural heritage preservation, yet at the same time, it contributes to it: watching the videos of the dances immerses you in the folk music, rhythm, the traditional clothes of the region, and some typical steps and and movements used in their dances.

The context, in short: learning to program is not easy for most students—as our almost 900 first-year students are starting to experience from next week onwards—and especially understanding the workings of algorithms. Katai and Toth’s approach is to involve ‘playing out’ the algorithm with people, not by clumsily walking around, but using folk dance and music to make students understand and remember it more easily. They took several sorting algorithms to demonstrate the idea, and tested it on their students, demonstrating that it improved understanding significantly [1].

Perhaps because of my bias toward the dancing, I didn’t take note of the algorithm being danced-out when I watched it the first time, or perhaps it is useful to have read the core steps of the algorithm before watching anyway. You choose: watch the video of the selection sort algorithm—given a list, repeatedly select the smallest remaining element and move that to the ‘sorted’ section of the list—with a Gypsy (Roma) folk dance, or read further below what selection sort is. (note: the video goes on double speed in the middle, for it gets a bit repetitive.)

So, what was happening in the dance? We have one ‘comparer’ (x, for short) and one ‘compared with’ (y). The left-most dancer, with number 3 (our first value of x), starts to dance to the front, calls on the second one in line, being the guy with 0 (our first y), he swirls her back in the line in the spot he came from and stays at the front (0 being the new value of x), and calls on the next, the lady with the 1 (the new value of y), who gets back in the line; and so on till the last one (with number 6). Dancer 0 does a solo act and goes to the first spot: he’s now the first one in the ‘sorted’ part, and we have completed one iteration. Starting with the second main iteration: now number 3 is again at the front of the unsorted, and she dances again to the front (so the value of our x is 3 at this point), calling the second one in the unsorted list, who has number 1, so the lady with number 3 goes back in the unsorted again, and the dancer with 1 continues through the remainder of the list, has her solo, and joins the guy with the 0 in the sorted part, having completed the second main iteration. And so on until about 6:20 minutes into the video clip when the list is sorted and the dancers do a little closing act.

A bit more structured, the following is happening in the choreography of the dance in the video:

1. Divide the list into a ‘sorted’ part (initially empty) and an ‘unsorted’ part (initially the list you want to sort)

2. Do for as long as there’s more than one item in the ‘unsorted’ (find the smallest item in that list):

   1. select first element of the unsorted list (with some value, that we refer to with x)

   2. if we’re not at the end of the ‘unsorted’ list, then get the next element of the ‘unsorted’ list (with some value, let’s call that one y)

      1. if x < y, then y is put back in the same spot in the unsorted list, and we return to the start of step (b) to get the next item to test x against (being the one after the one we just tested)

      2. else (i.e., x > y), then the value of x takes y‘s spot in the unsorted list, we assign the value of y to x, and we return to the start of step (b) to get the next element from the unsorted list

   3. else (i.e., we’re at the end of the list and thus x is the lowest value), place (the value of) x in the next available spot in the ‘sorted’ part. Then go back to the start of step 2.

3. Place the last item from ‘unsorted’ at the end of the ‘sorted’.

4. Done (i.e., there’s nothing more in ‘unsorted’ to sort)

The algorithm itself is less cumbersome by not having those “let’s pick out one and come to the front” steps, but direct comparisons. I did not plan to include here, but do after all for it makes a nice sequence of artsy → informal analysis → semi-precise structure → specification the computer can work with. (Never mind that that was not the order things came about). Using our CSC1015F course material (2012 samples) that teaches Python, one of the possible sample code snippets is as follows:

def selection_sort ( values ):
   """Sort values using selection sort algorithm."""
   # iterate over outer positions in list
   for outer in range (len (values)):
      # assume first value is minimum
      minimum = outer
      # compare minimum to rest of list and update
      for inner in range (outer+1, len (values)):
         if values[inner] < values[minimum]:
            minimum = inner
      # swap minimum with outer position
      temp = values[minimum]
      values[minimum] = values[outer]
      values[outer] = temp
   return values

This is not the only way of achieving it, btw, and the 1017F lecture and lab lecture files have another version of achieving the same (I just thought that this one may be more readable by non-CS readers of the post).

Other danced sorting algorithms are insertion sort (video) with Romanian dance, and shell-sort (video) and bubble sort (video) on Hungarian dances, and more information is also available from the Algo-rythmics website. This isn’t new, and dances on many other tunes can be viewed on youtube, e.g., various bubble-sort dances. Reconstructing the bubble-sort algorithm from the dance below (5min, no fastforward) is an exercise left to the reader… likewise making dances on other algorithms (the ICPC’14 solution to the baggage problem seems like a fun candidate line dance-like), and the same dances but with other folk dances and music.

References

[1] Zoltan Katai and Laszlo Toth. Technologically and artistically enhanced multi-sensory computer programming education. Teaching and Teacher Education, 2010, 26(2): 244-251.

Digitizing my cassettes of international folk dancing music

The previous post was about options to use ontologies and semantic web technologies for indigenous knowledge management system/digital preservation of cultural heritage/traditional knowledge systems. There is already some data available for such systems, but still a lot is to be collected, digitized, structured, and so on. Here’s my very modest attempt of “going with my hands in the mud” on the digitization part, both because it’s long overdue and so as to get a first-hand idea what data collectors may face, of which one thing was that, despite searching online quite a bit, there was remarkably little available, and even that was hard to find.

Once upon a time… I spent 1.5-4 hours a week dancing on folk music from many different countries (see below), for 13 years in a row, of which two years also in the Dutch dances demonstration group—the purpose of the latter group was to show off, of the former to have a good time. This was all principally with the Maroesjka folk dancing club in Heeze, the Netherlands. Besides good memories, I have two full cassette tapes of folkdance music covering most of the dances we learned during (school years) 86/87 and 88/89, and a few pictures. The cassettes were originally compiled by Riekje van Hofweegen, our tireless dance teacher, mostly by copying songs from other tapes and LPs. I have digitized the cassette tapes with a cassette-to-mp4 converter, amounting to about 250MB for 49 songs and, as I don’t have a colour scanner readily at hand, I digitised a few pictures of us in action by taking a picture of them with a digital camera. (so, you’re warned about the quality.)

The two cassettes include folkdance music from—using the originally mentioned countries/regions—Bulgaria, Catalonia, Czechoslovakia, Denmark, England, Greece, Hungary, Israel, Mexico, Netherlands, Portugal, Romania, Spain, Turkey, USA, Wales, and Yugoslavia, which, in other years, included dances from other countries, such as Poland and Russia, as well. To give a random example of the music of a dance from each of these countries/regions: Bulgaria with Kopanitsa, Catalonia with ball de pastors del pirineo, Czechoslovakia with ceresnicka, Denmark with gamble gammel nr 12, England with St. Nick’s Jack, Greece with choros mais, Hungary with fercelö, Israel with  mocher prachim, Mexico with la capsula, Netherlands with bravade, Portugal with malhao malhao, Romania with hora femeilor, Spain with el candil, Turkey with kendime, USA with steppin out, Wales with a name unknown, and Yugoslavia Macedonia with kales more dimco, and one of the Russian dances was the troika (which I have only as sheet music). The only ones of which I have not deciphered their origin yet are the vlaski tanz (my guess: one of the new countries from former Yugoslavia) and one with the quasi-readable handwritten name halleluja lufall (or similar), and there are four dances without a name (two from Wales, and two from Portugal). update: Marija Slavkovik, from Macedonia and with whom I shared an office for some time when studying at FUB, refined the “Yugoslavian” ones as follows: the poskos and çaçak are Serbian, kales more dimco is Macedonian, and the Vlaski tanz Serbian, Macedonian or Bulgarian. As an aside, the first folk dance I learned when I was 6 years old was the mayim, and the first one I participated in with a demonstration was the French dance the ‘river the Rhone’ (I’ve only sheet music of them, which I may scan and/or play on the recorder flute another time).

The dances in the directory on my home page are still in the sequence as they were on the tape instead of neatly annotated and sorted by country, genre and so on. Besides, I’m neither a musicologist nor a folk dance expert: aside from the country/region inserted in the mp4’s file name, I can go as far as the basics, like ‘fast’ or ‘slow’ or both (e.g., virgin blanca, Spain), and annotating a song ‘with singing’ (e.g., kendime, Turkey) or ‘instrumental’ (e.g., the kukunesko choro, Bulgaria), or, zooming in on the actual dances, ‘this has some mayim/polka/…-steps’ or ‘arm-waiving’ (e.g., eretz eretz, Israel, malhao malhao, Portugal) in the dance, and a basic configuration of line or string (iirc, the poskos series, Yugoslavia Serbia), circle (many, e.g., rusi kosi, Bulgaria) or square (e.g., St. Nick’s Jack, England), and/or pair dancing, or both square + pair (e.g., bravade, Netherlands), or circle + arm-waiving + moving from circle-to-centre-and-back (nad-ilan, Israel), and so on. One or more ontologies, or at least some basic structured controlled vocabulary, to annotate this could come in useful here, with knowledge represented about choreography, types of steps, dance styles, and so on. The usefulness of that? Among others, subsequent querying of the music files once there are many (e.g., “list the square-dances from country x”, “what are the first 10 opening steps dance y?”), help categorizing dances for which only partial information is available, easily compare dance styles across cultures, mutual influences, analyse the rhythms, variety in steps, difficulty of the dance, etc.

In case you wonder: yes, I did try dancing on the songs again, and I even remembered some steps from most dances, and some of them completely, including the hora he, the okselfris oh yossel yossel, and the bravade. No, I am not going to capture that with the webcam; for one, because it looks silly to dance alone, and, second, some of the dances are quite fast, like the çaçak (Yugoslavia Serbia), Kopanitsa (Bulgaria) or mãnãstîreanca (Romania). To give you an idea nevertheless, here’s a photo where we’re dancing the ball de pastors del pirineo (dance of the herders of the Pyrenees) from Catalonia, when Maroesjka was celebrating its first 10 years (I’m second from left):

Picture of dancing the Ball de pastors del pirineo

This is indeed in full costume, which was, at least when I was in the adult dance groups, always the case when we did dance demonstrations. (Not that I was really an adult at that time—basically, in secondary school—but the only ones left in our age group were Lilian and me; we were too old and experienced for the kids, so the members in the adult group decided they were willing to tolerate us in their group.) One could participate in demonstrations at least once a year, for those who were interested in it, and most notably during the Brabanste Dag when the village turns medieval for a week. The costume in the photo below is one for a set of Jewish dances we performed during one of Brabanste Dag festivals (going by my haircut, I guess it was in August 1988, and the photo certainly was taken in the garden of the building where we danced weekly).

Group photo made before the folkdance demonstration during the Brabanste Dag in 1988

Most of the costumes were hand-made by the female dance groups members, and while they look nice indeed, I still would say that their sewing and needlework expertise showed itself off most with the Dutch costumes. One of the more recent dance instructors of Maroesjka has some ‘old’ (1989) pictures on her website with Maroesjka members and traditional clothes from different Dutch regions and cities (and more pictures). To feed the stereotype, here’s a group photo of our Dutch dances demonstration group when we participated in an international folk dance festival in Antwerp (in 1991?); I’m third from left, with my real hair.

Group photo of the Dutch demonstration group of Maroesjka, during the international dance festival in Antwerp in about 1991.

The clothes may look a bit dull, but it takes about 1.5-2 hours to dress, one needs help with sticking in the pins, and it is hot in there. What seems like a blue striped skirt is actually just an apron. Underneath is a long black, thick, skirt, and underneath that an under-skirt. The colourful top is stiffened and held together with all those pins in different places. Then there’s that cap on our heads, which requires you to muffle away long hair, roll up the ‘fringe’ evenly, and then fasten the cap with as many hairpins as needed to make it unmovable. The men were ready in less than 10 minutes (trousers, blouse, hat).  We skipped the clogs because it is too heavy to dance with, except for one short dance that only the men did during the demonstrations.

Our Dutch folkdance repertoire included, among others, the bravade, mazurka, hakke toone, and the vleegerd. (I only have sheet music for the latter two, and may record it some time later, since I haven’t played the recorder [flute] since a while and was never good at it anyway—btw, there is also a Dutch song database with sheet music). I can’t remember the name of the dance we were dancing in the photo below, but the figure we’re making is that of a windmill, with each couple representing a sail of the windmill that is held together firmly at the centre (hand-to-wrist cf. just holding hands), so that some real dancing speed could be achieved whilst going round.

A few Maroesjka members went on to set up the Platform Nederlandse Floklore, but also that site does not have much information, and is structured about as good or as bad as this post. They have posted a few videos of Dutch folkdances on youtube.

Finally, I am aware the above information is not really readily available in an easy computer-processable format from a knowledge management viewpoint. Nevertheless, perhaps it was an interesting read. Overall, it already took a lot more time to digitise and ‘annotate’ it (well, write this blog post) than I thought it would take even for those two cassettes: one evening digitizing, 1-2 hours online search trying to find related relevant material, two evenings writing this post, and another hour to upload and layout it all. To collect and computerize all of South Africa’s indigenous knowledge in the “national recordal system” NIKMAS (driven by the NIKSO office) surely is going to take a very long time by very many people.