Trailing zeroes

A week or so ago someone mentioned the following problem:
How many trailing zeroes does 1000! have [when written out in base ten, of course]? Easy enough to find...

Prelude> length $ takeWhile (== '0') $ reverse (show (product [1..1000])) 

But is there a better way? Yes, there is. After reading that someone said he did it in his head, the way to do it in your head occurred to me. *slaps forehead*
1000!, like any positive integer, has a unique prime factorization. In particular, we're interested in the primes 5 and 2, because 10 is 5 * 2. They certainly both appear in the prime factorization of 1000!, and they thus have positive exponents in said factorization. Let m be the exponent for 5, and let n be the exponent for 2. How to calculate them? Let's start with five. There are 200 multiples of 5 between 1 and 1000.There are 40 multiples of 25 between 1 and 1000.There are 8 multiples of 125 between 1 and 1000.There's 1 multiple of 625 between 1 and 10…

Sum of multiples problem

One of the problems generalizes a Project Euler problem: what's the sum of multiples of 3 and 5 less than 1000? Seems simple enough:
sum [3, 6..999] + sum [5, 10..999] but that's too big; it counts some values twice. With a little thought, though, you'll realize that the duplicates are the multiples of 15, so
sum [3, 6..999] + sum [5, 10..999] - sum[15, 30..999] will do the trick. Why 15? Well, it's 3 * 5... but more on that later.

The problem makes the upper bound a parameter, and allows an array (or list, depending on the language) of factors. Looking around (which you can do on the site after you've submitted your own solution), one sees two typical approaches:
Go through [1..limit - 1], pick out the values that are multiples of one or more of the factors, and add up the result.Create a set or hash table from [[f, 2*f..limit - 1] f <- factors] (thus getting rid of the duplicates), and add up the elements of the set/keys of the hash table.…

a longest path problem has a weekly column, "The Riddler". The Riddler poses two problems in each column. The first, "Riddler Express", is intended to be an easier problem that one can solve quickly, while the second, "Riddler Classic", is more difficult. Modulo vacations, it appears each Friday, and if you submit a solution by the end of the following Sunday (Eastern Time) , you will be among those who might be given credit for the solution in the next column.

The August 28th column's Classic problem is as follows: what's the longest sequence of integers x[i] for 1 ≤  i ≤  n such that
for all i, 1 ≤ x[i] ≤ 100for all i < n, either x[i+1] is a multiple of x[i] or x[i+1] is a factor of x[i]for all i, j, x[i] = x[j] iff i = j, i.e. the x[i] are all distinct (The last constraint avoids trivial sequences like 2, 4, 2, 4, 2, 4... which can go on forever if repeats are permitted.)

One way to characterize this problem is to look at it as a graph with a hu…

Bikeshedding leap years

Darn it, I fell into the trap. An early exercise in Python at wants a function that in Haskell would have the type Int -> Bool and indicate whether a year is a leap year (under Gregorian rules, ignoring when various locales made the switch to keep it simple).

Some submissions are from people not yet comfortable with assigning/returning Booleans other than the constants True or False, or maybe not comfortable with the lazy nature of Python's and and or. Their versions are full of if statements. I bashed out
defis_leap_year(year):returnyear%(400ifyear%100==0else4)==0 and it worked fine... but then I fell in. How about
return year % 16 == 0 if year % 25 == 0 else year % 4 == 0 Nah... no need to make the next guy, who could be me, do the prime factorization of 100 again and figure out how that ties to the leap year rules? OK, here's one way to look at it...
return (year // 100 if year % 100 == 0 else year) % 4 == 0i.e. on century boundaries, the century has to be divis…

Restaurants shooting themselves in the foot

It's pet peeve time, and here it is: restaurants that display graphic images of their menu on the web. Sometimes it's a PDF made up of graphics, sometimes it's just graphics.
I wish I had a nickel for each restaurant I really like whose web site suffers from this problem... though perhaps I should shoot for more than that by offering my services to fix their web sites. A few examples: Abelardo's5 de MayoLina's Mexican RestaurantSpectators (though their main menus are PDFs that actually have text) How wrong is this? Let me count the ways... You say you want people to be able to search your menu? Good luck (though someday the code that lets Google Translate read text from images may get good enough to deal with the wonky display fonts people tend to use on menus or text superimposed on food photos).You say you want search engines to find your restaurant's web site? Good luck again, though as above, maybe someday...You say you want your web site to support travelers…

No tutorial, I swear...

After grinding through much of the "20 Intermediate Exercises" and just about all of the Monad Challenges, Monads make much more sense to me.

Therefore, I will follow the excellent advice of Stephen Diehl, and will not write a monad-analogy tutorial. Instead, I will say: do the 20 Intermediate Exercises, and take the Monad Challenges. To paraphrase Euclid, there is no royal road to Monads; the exercises and challenges take you down that road at whose end you'll see at least part of why Monads are so useful.

If you were trying to learn group theory and people were standing around you saying "groups are like the integers",  "groups are like Rubik's Cube", "groups are like m x n matrices", "groups are like baryons and mesons", your situation would be much like the student of Haskell amidst all the monad analogy tutorials. In a sense they're backwards. All those things are groups, just as burritos et al. can at least be thought…

Flipping out

I came across the excellent Monad Challenges, a collection of exercises designed to take you through what have become some of the standard example monads and take you through the process that motivates monads as a way to handle these seemingly diverse data structures. Both the Monad Challenges and the 20 Intermediate Exercises are well worth your time. Doing them both is helping me a lot.

That said, they don't quite match up. 20IE's banana is flip bind and apple is flip ap. (This isn't unique; the also excellent Learning Haskell from first principles has as an exercise writing bind in terms of fmap and join, but the declaration it gives has the type of flip bind. The authors do point this out.) As a result, I find myself with something that there's got to be some way to simplify, of the form

foo = flip $ (flip mumble) . (flip frotz)

I'd like to think there's some sort of distributive-like law to be found and used here... watch this space.