RealFrac provides truncate, round, ceiling and floor, all of which are quite unnecessary on the provided Int.

Remove the function that needs the RealFrac instance from your solution, and remove the type constraint from your sierpinski. That should do it.

( I know you probably figured this out yourself by now. Hopefully. :P But someone else might benefit. )

Great! Thanks.

If the ratio's importance is not clear in the description, I would definitely like to fix that. In the current description I have:

The greedy solution is that which always adds an item to the collection if it has the highest value-to-size ratio.

What is unclear and how would you suggest I clarify that point?

I have modified my "greedy thief" example to include a brief calculation of the ratio:

For example, if a "greedy thief" with a 10-Liter knapsack sees two types of items

• a 6-Liter item worth $9 (1.5 $/L)

• a 5-Liter item worth $5 (1.0 $/L)

the thief will take 1 of the 6-Liter items instead of 2 of the 5-Liter items. Although this means the thief will only profit $9 instead of $10, the decision algorithm is much simpler. Maybe the thief is bad at math.

Hopefully that helps :-)

The regexp (re) takes a digit and any number of repeated instances after it. The substitution takes the regexp match (specified by m in the lambda expression) and replaces it with the length of the full match followed by the digit used.

• m.group(0) is the part of the string that the regular expression matched in full.
• m.group(1) is the part of the string that the '(\d)' part of the regular expression matched (putting something in parentheses makes it a group).

Think of '111333'

• \d matches a single digit. I.e. 1 11333 is what would be matched.
• (\d) matches a single digit and creates a group.
• A group causes \1 (a reference to the full match of the 1st group) to represent the digit 1 in this case.
• \1* refers to an arbitrary number of whatever was in the set of parenthesis matched (* means 0 to N repetitions).
• In this case there are two repetitions of the digit 1, so it matches both of them. I.e. 1 11 333.
• This makes the full match 111 with group(0) representing the full match, and group(1) representing what was matched inside the parenthesis 1 11.
• The substitution method calls the lambda expression with each match (this repeats for the the 3s).
• The lambda expression returns the look say for each full match (length of the full match, what the original number was).