## Fibonacci and Primes

October 20, 2010

The middle challenge was to find the first prime Fibonacci number greater than 227000, add one to it, and then sum the prime numbers which were its factors. Here’s my first implementation:

sub is-prime($a) { return Bool::True if$a == 2;
! [||] $a <<%%<< (2, 3, *+2 ... * >$a.sqrt);
}

my @fib := (1, 1, *+* ... *);

my $cutoff = 227000; my$least-prime = 0;
for @fib -> $f { next if$f <= $cutoff; next unless is-prime($f);
$least-prime =$f;
last;
}

my $x =$least-prime + 1;
say [+] (2, 3, *+2 ... * > $x.sqrt).grep({$x %% $^a && is-prime($a) });


Despite what seems like an obvious inefficiency (approximating the prime numbers with the odd numbers), this is pretty snappy, executing in 12.5 seconds.

I was planning to go on and talk about my new Math::Prime module here, but looking at this code, I think it can be expressed rather more nicely with a tweak or two here. Let’s see.


sub is-prime($a) { return Bool::True if$a == 2;
! [||] $a <<%%<< (2, 3, *+2 ... * >$a.sqrt);
}

my @fib := (1, 1, *+* ... *);
my $cutoff = 227000; my$least-prime = @fib.first({ $_ >$cutoff && is-prime($_) }); my$x = $least-prime + 1; say [+] (2, 3, *+2 ... * >$x.sqrt).grep({ $x %%$^a && is-prime($a) });  So that’s what the first method is good for! I did indeed write Math::Prime just so I could use it here. It’s not a huge change from the previous version, really: use Math::Prime; my @fib := (1, 1, *+* ... *); my$cutoff = 227000;
my $least-prime = @fib.first({$_ > $cutoff && is-prime($_) });
my $x =$least-prime + 1;
say [+] (primes() ... * > $x.sqrt).grep({$x %% $^a });  Unfortunately, Math::Prime isn’t optimized yet, and so this version, while a bit nicer, is actually slower than the previous version. Update: With Moritz’s help I did some optimizations to Math::Prime, and the script using it is now very significantly faster than the others. ## 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.

    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…