Posts

Showing posts from 2014

Flashback, Part Two

Last time we found that our program to count ways to make change, while much better than the engineering class's brute force nested DO loops, isn't up to snuff.

There is a better way, it turns out. If you look at the Rosetta Code entry for this problem, which they call "Count the Coins", you'll find a number of approaches. For Haskell, there are two. The first "naive" program is essentially what we wrote (save that there's no explicit case for a one-element list; it's a little less efficient, but the recalculation may well swamp that difference).

The other Haskell program takes a different approach:

count = foldr addCoin (1:repeat 0)
        where addCoin c oldlist = newlist
              where newlist = (take c oldlist) ++ zipWith (+) newlist (drop c oldlist)

and if you look at the main for the program,

main = do
    print (count [25,10,5,1] !! 100)

    print (count [100,50,25,10,5,1] !! 100000)

you see that count returns a list that one indexes by t…

Flashback

Back in the Cretaceous era I worked at the University of Oklahoma as a student assistant at Remote 1. OU was a [shudder] IBM big iron shop at the time, and beginning students typically got a job class that limited CPU time to thirty seconds, lest a beginner submit a program with an endless loop and chew up serious resources. (And when the computer everyone's sharing is a 370 of mid-1970s vintage, it doesn't take much to be considered serious resources. According to the Hercules FAQ, a Celeron 300 can emulate a 370 at speeds greater than a 3033, which was at least twice as fast as what OU had at the time.)

One day one of the instructors assigned his charges the following problem: count the number of ways to make change for a dollar assuming you have a generous supply of half dollars, quarters, dimes, nickels, and pennies. (The language is a bit loose; there wasn't any buying going on, just figuring out how to get coinage adding up to a dollar.) They all headed off to punch …

2010 Code Jam problem: "Store Credit"

A fellow on the haskell-beginners mailing list asked for suggestions on how to improve code he'd written to solve a 2010 Code Jam qualifying problem, "Store Credit". Here's the problem statement:
"You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first)." Then the format of the input is described, and among the things we learn are:
The prices are all integers."Each test case will have exactly one solution." But then one of the examples for which a solution is shown has a credit amount of 8 and this list of prices:

2 1 9 4 4 56 90 3

and the solution "4 5". At first one would--well, I did--think that violates the promise of only…

Look and say sequence

If I don't already have the Haskell subreddit link over on the right, I'll add it ASAP.

This evening a Haskell beginner posted about some trouble he was having writing code to generate a particular sequence. I didn't catch on to the sequence he was going for, but I should have from a comment in his code:

enunBlock :: [Int] -> [Int] -- [2,2,2] -> [3,2] | [3] -> [1,3]

Someone did catch on, though, and asked "Are you trying to make a look and say sequence?" The poster said yes... and off to Wikipedia I went.

Said sequence starts 1, 11, 21, 1211, 111221, ... and the way you get the next term is to take the current one and sort of run-length encode it. The first term would be "one one", i.e. a run of ones of length one, so the second term is 11. That in turn would be described as "two ones", hence the third term is 21, or "one two, one one", giving 1211, and so on.

If each digit were on its own line, you could get the next term of …

Fun with pattern matching

I just noticed that I did something almost without thinking.

I'm still being lazy about dealing with inputs. I haven't gotten around to using one of the many elegant parser packages that Haskell makes possible, and the Code Jam problems I've tried so far haven't required much more than skipping the leading line--kids, ask your grandparents about the card decks they would feed to their FORTRAN programs that started with a card that said how many sets of input values followed!--and handing back a list of values per line of input afterwards.

A particular Cookie Clicker Alpha input has three values, and so I passed cookieTime a list I knew would always have three elements, so that the pattern

cookieTime [farmCost, farmRate, goal] = ...

matches it and also splits out the elements of the list and binds them to names--just the way that introductory Haskell texts always mention that you could make yourself comfortable if you're used to languages that want parameter lists pa…

Well, drat... *spoiler alert*

I didn't do well in the qualifying round of Code Jam this year, alas. Part of it I can thank the IRS for, in a way, because we paid our annual last-minute visit to H&R Block today. But really it's my fault; I didn't arrange to have the interval during which one could enter solutions clear to devote to it.

I didn't get my improved version of Cookie Clicker Alpha done in time to count, but it did check out, so I have a moral victory at least. I probably should have devoted the time needed to do the simplest of the qualifying problems, Magic Trick, rather than just sketching out the solution.
A quick summary of the problem: in the problem's version of the game "Cookie Clicker" (inspired by a real game of that name) is parametrized by three values: X, a goal number of cookies to accumulateC, the cost in cookies of a "cookie farm"F, the rate at which one can "harvest" cookies from a cookie farm once bought OK, actually, there's a fou…

Letting the compiler do it for you

A while back I posted about how looking at the type can give you hints or even tell you what a function has to do, giving the simple example of function composition and pointing at a video by Matthew Brecknell showing how you can enlist ghci to help you in that respect.

Here's another example, provoked by a comment on a reddit question, namely map. If you only knew

map :: (a -> b) -> [a] -> [b]

could you write map? The signature says "give me a function that maps as to bs and a list of as, and I'll give you back a list of bs". Well, you could be a wise guy and write

map _ _ = []

and if anyone complained, say "Hey, the empty list is a list of bs", but in your heart you'd know you were cheating. The only way you're given to get a b given an a is to use the function, so the obvious thing to write is

map f xs = [f x | x <- xs]

(Yes, you could be a wise guy at the next level up and write

map f xs = reverse [f x | x <- xs]

but again, your consc…

It's in the papers...

I don't necessarily agree with the New York Times's editorial position, but I applaud this fellow.
"Haskell in the Newsroom" is worth your time.

IMVU and Haskell

Check out "What it's Like to Use Haskell" over on the IMVU Engineering Blog. The author is enthusiastic, with enthusiasm based on, but also tempered by, the results of real-world use. Thank you, Mr. Friesen.

Another thing someone's probably done before

In part it comes from still being fairly new to the language, but I think it also has to do with the seriously cool high level of abstraction Haskell lends itself to. When I come up with a useful function, it's already been implemented, and far more generally. The first time around I wrote a special case of sequence. Here's my next function, and I am sure I just have to come up with the right monadic way to think of it to get the right string to hand to Hoogle to find the official version.

maybeIterate :: (a -> Maybe a) -> a -> [a]
maybeIterate f x = x : maybeIterate' (f x)
  where maybeIterate' Nothing   = []
        maybeIterate' (Just fx) = fx : maybeIterate' (f fx)

So in the background I will keep an eye out for blog posts like the one that clued me in to sequence, and I will continue the study of monads.

Numerical methods and C++

I sometimes have to use C++. What I'm curious about is numerical methods code for C++. Functions for finding zeroes or fixed points of functions, or numerical integration or differentiation, typically take as a parameter (a pointer to) the function being integrated, differentiated, or whatever. Here comes the fun part: what if that function is a member function?

You can't pass a pointer to a member function to something wanting a plain old pointer to function. The C++ FAQ section 33.2 answers the question "How do I pass a pointer-to-member-function to a signal handler, X event callback, system call that starts a thread/task, etc?" with the one word "Don't", followed by a hack to give the effect involving a function that returns the result of calling the member function via a global pointer to an object of the appropriate class that you have to assign to. Note the use of the "G word" there--so you can kiss the hack goodbye if multiple threads t…

NixOS

If you are a Linux user, you probably have heard at least a bit about the package manager/format hoohah. .rpm, .deb, etc.... It's been blamed for dissuading companies from porting their apps to Linux, and one must admit that it's a pain when a package isn't available using the package manager your distribution uses (*cough*Java*cough*).

It's only recently that I've found out about the Nix package manager. I'm somewhat embarrassed, because it's based on a lazy, pure functional language. You can have multiple versions of a package installed at the same time, eliminating what in the Windows world is called "DLL hell". It supports multiple users, so non-privileged users can install packages. (And if two users happen to install the same package, there will only be one instance of it.)

The Nix package manager is the basis for the Linux distribution NixOS. It may not be for everybody; there are programs out there that still have wired-in assumptions abou…

Getting fed up...

Sigh. First streams, now matrices. The Ubuntu repositories don't have all the Haskell packages one would like. I guess it's going to come to removing the Ubuntu packages and building ghc and associated code myself or via.... [cue ominous music]... cabal.

I may combine that with a switch to Sabayon Linux, which will let me get back into Gentoo with minimal hassle, and also return to Enlightenment.

Once I can get the packages I want, it should be pretty easy to do Project Euler #11; the main trick for me is reading the input, and I think something like this should do the trick:

import qualified Data.Matrix as M
import qualified Data.ByteString.Char8 as B

parseLine :: B.ByteString -> [Int]
parseLine s = case B.parseInt s of
                Nothing      -> []
                Just (n, s') -> n : parseLine s'

main = do
         s <- getContents
         let m = M.fromLists $ map (parseLine . B.pack) (lines s)

and then it's just how to generate the contiguous portions …