Summing Subsets

October 9, 2010

So, the third challenge was to count the number of subsets of a set of numbers such that the largest number in the subset is the sum of the rest of the numbers in the subset. My first attempt was very straightforward: create all the subsets and check to see if they have the desired property:

my @a = 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92,
 95, 97, 99;

my $hits = 0;

for 1..(2 ** +@a) -> $key {
    my @b = gather for 0..+@a -> $i { take @a[$i] if $key +& (2 ** $i); }
    my $test = @b.pop;
    next if $test != [+] @b;
    $hits++;
    say (@b, $test).join(' ');
}

say "$hits hits";

I think this works correctly, but it will be a long time before we know — as I type this, it’s been running for ten hours on my fastest computer, and I don’t anticipate it finishing any time soon.

My second attempt relies on recursion, the fact the list is sorted, and skipping fruitless branches to get the job done much faster — 47 seconds, to be precise.

sub CountSumSets($target, @a) {
    my $sets = 0;
    for ^ +@a -> $i {
        if @a[$i] < $target {
            $sets += CountSumSets($target - @a[$i], @a[($i + 1) .. (@a - 1)]);
        } elsif @a[$i] == $target {
            $sets += 1;
        }
    }
    $sets;
}


my @a = 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99;
@a .= reverse;

my $hits = 0;

for ^ +@a -> $i {
    $hits += CountSumSets(@a[$i], @a[($i + 1) .. (@a - 1)]);
}

say $hits;

Longest palindrome

October 9, 2010

Via Hacker News, I found the Greplin Programming Challenge, and couldn’t resist trying it in Perl 6. If you’re the sort of person who enjoys that sort of thing, I highly encourage you to stop reading here and go try it yourself!

I’m going to blog about all three challenges one-by-one. I suppose the third will be the most interesting, if for no other reason than my current implementation looks like it will take ~32 hours to run, so I’m probably going to need to find a more clever solution.

Basically, the first challenge is to find the longest palindrome in a string without spaces. As stated, I thought the challenge implied it was case-sensitive; obviously it’s easiest enough to add a call to lc to get a case-insensitive version.

I was pretty sure a naive version would bring Rakudo to its knees, so I tried to be slightly clever. My solution is still O(N^2), but N is the number of occurrences of a given letter rather than the full length of the string, so that’s fairly reasonable.

sub longest-palindrome($string) {
    my @c = $string.comb(/./);
    my %hc;
    for ^ +@c -> $i {
        if %hc{@c[$i]} {
            %hc{@c[$i]}.push($i);
        } else {
            %hc{@c[$i]} = [$i];
        }
    }

    my @candidates := gather for %hc.keys.sort -> $c {
        say "Checking $c";

        my $list = %hc{$c};
        say :$list.perl;
        for $list.list -> $i1 {
            for $list.reverse -> $i2 {
                last if $i2 <= $i1;
                my $j1 = $i1;
                my $j2 = $i2;
                my $candidate = Bool::True;
                while ++$j1 < --$j2 {
                    if @c[$j1] ne @c[$j2] {
                        $candidate = Bool::False;
                        last;
                    }
                }
                if $candidate {
                    say @c[$i1..$i2];
                    take @c[$i1..$i2].join('');
                }
            }
        }
    };

    @candidates.sort({$^a.chars <=> $^b.chars}).perl.say;
}

Basically, my notion was to store all the occurrences of each letter in a hash of arrays, then pair up every two occurrences of the same letter and see if they are a palindrome. This probably isn’t the most elegant solution, nor the fastest, but it was fast enough to get solve the challenge problem in a minute or two, and easy enough to code I could do it in under an hour at three in the morning.

Interestingly, I think there might be a way to solve this using regular expressions…

Update: Moritz has a solution which blows this one out of the water, both much faster and more elegant. (The key idea was using the regex engine to find the center of potential palindromes.) I’ll let him tell you about it

Taking a Rest

October 4, 2010

Once I was reasonably happy with ABC::Duration and ABC::Note, I went ahead and added ABC::Rest, which was truly easy thanks to the magic of code reuse. It actually turned out to be quite a struggle to implement, but that was only because I accidentally typed is $.type rather than has $.type and spent a couple hours trying to sort out what the LTA error message meant.

class ABC::Rest does ABC::Duration {
    has $.type;

    method new($type, ABC::Duration $duration) {
        self.bless(*, :$type, :ticks($duration.ticks));
    }

    method Str() {
        $.type ~ self.duration-to-str;
    }
}

There are several sorts of rests in ABC, which is why ABC::Rest has a $type attribute. In practice, I’ve only implemented “z” rests so far, as they are the basic type.

Rests were already in the grammar, and adding an action to support them was dead easy:

    method rest($/) {
        make ABC::Rest.new(~$<rest_type>, $<note_length>.ast);
    }

After a trivial refactor to make the Lilypond duration handling code easily available, it was just took one line to add rests to the Lilypond output:

when “rest” { print ” r{ DurationToLilypond($context, $element.value) } ” }

That’s for the output section of the code. No changes were required to make rests work in the “figure out the overall duration” section of the code, because it looks for elements which do ABC::Duration, and so it automatically found the rests and correctly handled them.

To me, this looks like a solid win for treating duration as a role.

Hesitant Steps Forward

October 1, 2010

So, I just dived in and started trying to implement duration as a role.

role ABC::Duration {
    has $.ticks;

    our multi sub duration-from-parse($top) is export {
        ABC::Duration.new(:ticks($top.Int || 1));
    }

    our multi sub duration-from-parse($top, $bottom) is export {
        if +($top // 0) == 0 && +($bottom // 0) == 0 {
            ABC::Duration.new(:ticks(1/2));
        } else {
            ABC::Duration.new(:ticks(($top.Int || 1) / ($bottom.Int || 1)));
        }
    }

    our method Str() {
        given $.ticks {
            when 1 { "---"; } # for debugging, should be ""
            when 1/2 { "/"; }
            when Int { .Str; }
            when Rat { .perl; }
            die "Duration must be Int or Rat, but it's { .WHAT }";
        }
    }
}

The corresponding action for an explicit note length is

    method note_length($/) {
        if $<note_length_denominator> {
            make duration-from-parse($<top> ?? $<top>[0] !! "", $<note_length_denominator>[0]<bottom>[0]);
        } else {
            make duration-from-parse($<top> ?? $<top>[0] !! "");
        }
    }

I messed around a bunch trying to make "e" does Duration work as a type, but eventually gave up and just coded an ABC::Note type:

class ABC::Note does ABC::Duration {
    has $.pitch;
    has $.is-tie;

    method new($pitch, ABC::Duration $duration, $is-tie) {
        say :$duration.perl;
        self.bless(*, :$pitch, :ticks($duration.ticks), :$is-tie);
    }
}

with corresponding action

    method mnote($/) {
        make ABC::Note.new(~$<pitch>,
                           $<note_length> ?? $<note_length>[0].ast !! ABC::Duration.new(1),
                           $<tie> eq '-');
    }

So… that seems to work okay so far. But it does raise some issues for me.

1. I’m finding this $<top> ?? $<top>[0] !! "" pattern to be very repetitive. Surely there must be a better way to do it? (errr… wait a minute, could that be just $<top>[0] // ""?)

2. I don’t mind the proliferation of small classes in my code, that corresponds nicely to what we are modeling. But I am starting to mind the corresponding proliferation of small source files. Is there a better way to organize things?

… and that’s all I can remember at the moment. I think I’ll wander off and have breakfast.

Durations vs Roles

September 30, 2010

So, I patched in some dodgy but working for this example code to handle the duration of notes. And then I started to think about how to do it properly.

About half of the musical elements in an ABC tune have a duration. So my first thought was, oooo, define an ABC::Duration role! I was excited, because this seemed like the first really good example I’d seen in my own work of where a role was appropriate and seemed superior to class inheritance.

So I started out defining a duration role with a Real attribute for its length, and two new methods, one which took a Real, and one which took the parsed bits of the note_length regex as strings. But then I started thinking about what that meant. If you define a class which does a role, how do you call that role’s new method? If I’m building up the AST, I’m going to want to create a duration before I have an element to attach it to — how do you build an element around an existing duration? And half of the objects which have durations are perhaps not best represented using a stored duration value — for instance, a triplet element’s duration is the total duration of its three wrapped notes, times 2/3 — making the stored duration value redundant.

So, this is one of those posts which I make before I’ve figured out what the answer is. I’ve verified that you can create a standalone role object in Rakudo:

> role Duration { has $.duration; }; my $a = Duration.new(:duration(10)); say :$a.perl
"a" => .new(duration => 10)

So that’s one piece of the second point addressed. (Though surely that .perl is wrong?) But I’m not seeing how to do the rest of it at the moment.

Any ideas out there?

First Sheet Music!

September 19, 2010

There were a number of comments on #perl6 on how to improve the code from my last post, but I’m ignoring them all today and forging ahead to get an actual ABC to Lilypond translator up and running. Here’s the core of the code:

sub StemToLilypond(Context $context, $stem) {
    my $match = ABC::Grammar.parse($stem, :rule<mnote>); # bad in at least two ways....
    my $pitch = ~$match<pitch>;
    my $length = ~$match<note_length>;
    
    print " { %note-map{$pitch} }{ %cheat-length-map{$length} } ";
}
   
sub BodyToLilypond(Context $context, @elements) {
    say "\{";
    
    for @elements -> $element {
        given $element.key {
            when "stem" { StemToLilypond($context, $element.value); }
            when "barline" { say " |"; }
        }
    }
    
    say "\}";
}

This code is wrong for a host of reasons. But the cool thing is, for simple tunes, it very nearly works. Basically, we go through the list of musical elements in the tune. When we see a barline, we output a bar line to Lilypond. When we see a stem, we parse it again (ugh) assuming it is the simple form a a stem, then map the pitch portion to the equivalent Lilypond note (ignoring key signature and accidentals), and the rhythm portion to the equivalent Lilypond duration (assuming that the ABC is notated in 8ths, and ignoring almost all potential complexity). This crude approximation almost suffices to properly notate “The Star of Rakudo”!

Here’s the PDF Lilypond outputs when feed the output of this script. At first glance this looks pretty good, but actually it’s got one major issue (as well as a host of minor ones). I think it might be obvious even to those who don’t read sheet music if it is compared to this proper PDF: the notes are all correct, but they are shifted one eighth note off in the measures! This is because Lilypond apparently treats bar lines in the source code as a mere debugging aid — if they don’t agree with what it thinks they should be, it will issue a warning and then go with what it thinks rather than what you said. I guess that behavior might make sense in big orchestral scores, but it is just annoying at this level.

So, what needs to be done to make this tune work:
1) Detect pick up bars and send the \partial command to Lilypond so that it keeps the bar lines in the correct places.

2) Preprocess the music looking for repeats, so that the repeated section can be properly marked for Lilypond.

3) Handle the key signature correctly.

4) Handle the ~ gracing, which in should generate a turn symbol over the note. (Used here to indicate an Irish-style roll.)

It appears to me that these are straightforward programming problems, so I’m going to forge ahead and see what I can do…

Regretting My Actions

September 18, 2010

I liked the array of pairs structure for the header so much I decided to do the same sort of thing for the music part itself. Here’s the bit of the grammar this post talks about:

    regex element { <broken_rhythm> | <stem> | <rest> | <gracing> | <grace_notes> 
                    | <nth_repeat> | <end_nth_repeat> | <spacing> }
    
    regex barline { ':|:' | '|:' | '|' | ':|' | '::' }
    
    regex bar { <element>+ <barline>? }
        
    regex line_of_music { <barline>? <bar>+ }
    
    regex music { [<line_of_music> \s*\v?]+ }

As a crude first approximation, I transformed each element into a Pair with the name of the rule that made the element as the key, and the actual string parsed as the value. Likewise each barline becomes a Pair with the key “barline” and the string for the value. In the long run, I’m going to have an ABC::Element class (or something like one), but this version ought to be enough to get simple ABC translation up and running.

That all worked fine right from the start. But the next bit was trouble:

    method bar($/) {
        my @bar = @( $<element> )>>.ast;
        @bar.push($<barline>>>.ast);
        make @bar;
    }
    
    method line_of_music($/) {
        my @line = $<barline>>>.ast;
        my @bars = @( $<bar> )>>.ast;
        for @bars -> $bar {
            for $bar.list {
                @line.push($_);
            }
        }
        @line.push("endline" => "");
        make @line;
    }
    
    method music($/) {
        my @music;
        for @( $<line_of_music> )>>.ast -> $line {
            for $line.list {
                @music.push($_);
            }
        }
        make @music;
    }

That’s what I ended up with, and it works. But when I started, each of those action methods was a simple one-liner. Alas, that version built up a structure in the results, when I wanted to end up with a nice, flat list of elements. I spent an hour trying different variations to remove that structure, finally ending up with the inelegant mess here. I’m hoping someone out there has a better way to do it.

At this point, this project is really close to being able to do useful things. Given a sufficiently simple tune (and many in ABC are very simple indeed!) this framework should make it easy to translate to Lilypond. I don’t know if I’ll get the chance to code it today, but if not, tomorrow for sure, I think….

First Actions

September 16, 2010

I renamed the old ABC class ABC::Grammar. Then I created a simple ABC::Header class to represent the header of an ABC file. At its heart, an ABC::Header object is just an Array of Pairs, each of which consists of a header field name (like “T” for title) and a header field value. (Why an Array instead of a Hash? Because certain header fields can appear more than once, and order is important.)

Then I constructed a very simple actions set to test my understanding. For the two rules

    
regex header_field { ^^ <header_field_name> ':' \s* <header_field_data> $$ }
regex header { [<header_field> \v]+ }

I constructed the following actions:

class ABC::Actions {
    method header_field($/) {
        make ~$<header_field_name> => ~$<header_field_data>;
    }
    
    method header($/) { 
        my $header = ABC::Header.new;
        for @( $<header_field> ) -> $field {
            $header.add-line($field.ast.key, $field.ast.value);
        }
        make $header;
    }
}

So when the parser constructs a header_field, it makes a Pair with the header field’s name as the key and its data as the value. The Pair is stored in the .ast for the header_field. Then when the parser makes a header, it constructs an ABC::Header object and fills it with the Pairs from the various header fields. Whee!

This is passing my initial tests, so I’m going to move on to some more complicated actions next…

Back to ABCs

September 16, 2010

I’ve been itching to get back to work on the ABC module (originally by SF from lastofthecarelessmen.blogspot.com, but my fork is the only version seeing current development work). A reference in an HN comment to Lilypond has provided the perfect. Lilypond is a long-lived open source project for music notation with very ambitious goals. In the past I’d tinkered with it a bit, but always come away unsatisfied. Today, though, I had a notion for an interesting project, so I thought I’d give it a whirl.

So, here’s a PDF of my tune “The Star of Rakudo” done with my usual slightly hacked version of jcabs2ps. And here’s a quick stab at a Lilypond version (with completely unnecessary 1st and 2nd endings added just so I can see what they look like). The Lilypond version has a heaviness to it I’m not wild about, but I think it’s pretty arguable that the various elements each look better than the other version. In addition, Lilypond appears to have good support for a more complicated musical elements. My inability to get jcabs2ps to portably generate all the musical elements I need has been a longstanding stumbling block to a side project of mine, so Lilypond is intriguing.

I don’t particularly like Lilypond’s music “language”, but that’s okay. My idea is to have the Perl 6 ABC code automatically translate ABCs to Lilypond for me, in effect generating good-looking notation from them. It will then be the best of both worlds — the lightweight, easy-to-type ABC format generating professional-looking output from Lilypond.

So, now I need to figure out how add actions to a Perl 6 grammar…

Series, Memoization, and Limits

September 3, 2010

Out on Reddit, my last post got some interesting comments. In particular, one commenter creates a finite series of squares, and then asks “That’s all well and good, but what would I have to do to say ‘up to 900′ instead of saying ‘up to 30^2’?” That’s a great question, and I’d like to explore the answer to it, though I’m going to stick with the Fibonacci series for my examples.

First, there’s a very quick and dirty answer to this. If you modify the original series, it is easy to add a limit term:

> my @Fibonacci := (0, 1, -> $a, $b { $a + $b } ... 900);
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

That gives you all the Fibonacci numbers less than or equal to 900. But the list is no longer expandable; with this one, if you say @Fibonacci[100], rather than calculating the 100th value of the series, it will just act like it’s a normal out-of-bounds array access.

In an ideal world, we’d have an easy way of looking at just part of an infinite series. What tools do we have in our toolbox? Well, there’s grep:

>  my @Fibonacci := (0, 1, -> $a, $b { $a + $b } ... *); 1;
1
> my @F-low := @Fibonacci.grep(* < 900); 1;
1
> say @F-low[10]
55
> say @F-low[20]

…and that last one is where the trouble starts, because it never comes back. By 20, we’re already well over 900. But grep’s been fed an infinite list, and it doesn’t know anything about it, so it just keeps on looking forever. So that won’t do.

The next tool we have is the first method.

> my @Fibonacci := (0, 1, -> $a, $b { $a + $b } ... *); 1;
1
> say @Fibonacci.first(* <= 900)
0
> say @Fibonacci.first(* > 900)
987

As you can see, first is great at finding the first Fibonacci number greater than 900. It’s pretty useless for finding all the numbers less then 900, though.

So, the bad news here is that, as I write this, Perl 6 does not have a method which can give us a finite portion of an infinite list based on some test, other than “give us the first N elements”. The good news is that the function we want is dead simple to write:

sub take-while(@a, Mu $test) {
    gather {
        for @a.list {
            last unless $_ ~~ $test;
            take $_;
        }
    }
}

This is actually a straightforward modification of the normal grep code. $test is defined as Mu so it can be anything that can be smartmatched against, including junctions. Then we scan the list, exiting if a smartmatch against the current element fails, and otherwise returning the element in our output list.

This is just the trick for the problem in question:

> my @Fibonacci := (0, 1, -> $a, $b { $a + $b } ... *); 1;
1
> take-while(@Fibonacci, * < 900)
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
> take-while(@Fibonacci, * < 400000)
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811
> take-while(@Fibonacci.grep(* %% 2), * < 400000)
0 2 8 34 144 610 2584 10946 46368 196418
> take-while(@Fibonacci, Int)
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903

So here we have it: we’ve still got the efficiency of the de facto memoized solution, but we can also carve off portions of the list based on some criteria. I threw in the last one there just to show it didn’t have to be a Code block passed in; in this case, it shows us how far we get down the series with Int values before our current limited integer math throws in the towel and gives you back a Num instead. (Note that once we get arbitrarily large Ints in Rakudo, that line will no longer work, because take-while(@Fibonacci, Int) will return an infinite list!)

And now for the even slightly better news: as of today, take-while is available in the List::Utils module.


Follow

Get every new post delivered to your Inbox.