It took a little bit to get this right:
choices :: Int -> Int-> [[Int]]
m `choices` n
| n == 0 = [[]]
| m == n = [[m,m-1..1]]
| otherwise = [m : c | c <- (m - 1) `choices` (n - 1)]
++ ((m - 1) `choices` n)
The gotcha is the n == 0 case; if you have it return [] the list comprehension gives the wrong result (i.e. an empty list!) with n == 1. (I didn't really need to make the m == n case go in descending order, but it looked nicer.)
Shouldn't take long to recast the palindrome program now; the idea, as alluded to earlier, is to represent half-Ys (aside from the easy-to-generate twoTwos) not by an Integer but by a list of the positions where we place 1s. Then backwards doesn't have to take the half-palindrome apart decimal digit by decimal digit, but can just reflect the positions and directly add up the corresponding powers of ten... but OTOH, do I really want to churn out a bunch of lists? For 50-digit Ys, that's up to 25 choose 3, or 2,300. If I go to representing them as a bit mask, I'm just chugging through bits rather than decimal digits--which would be faster, so perhaps that's the thing to do... or we generate both halves at the same time, while we have the information.
random notes and thoughts, mostly about Haskell these days, of a rather past middle-aged programmer
Subscribe to:
Post Comments (Atom)
Riddler Classic, May 23, 2020—Holy Mackerel!
Another one using Peter Norvig's word list . It turns out that the word "mackerel" has a curious property: there is exactly ...
-
"Why I'm Interested in Haskell" --not the writing of a fanboy, but of someone who I think fairly assessed the state of the pro...
-
Another one using Peter Norvig's word list . It turns out that the word "mackerel" has a curious property: there is exactly ...
-
So, how about that tree? It's tempting to do something like van Laarhoven describes, though I'd be tempted to put maxima on the left...
No comments:
Post a Comment