Learning languages through problem-solving

Sunday, July 13th, 2008

My preferred approach to learning anything is by diving in. Give me problems to solve. This approach has, at times, brought complication and peril into my life. But not with programming languages. This is still the way I like to go. So now that I’ve finally come up with some time to tackle a bit of functional programming, I went and found me a couple of tutorials (Erlang and Haskell), and started to cast about for problems.

Fortunately, the Web is full of problems. I mean that last statement in so many different ways. Particularly, though, new programmers have many options for taking on new languages and algorithms through problem sets. TopCoder is a great choice (with a very cool competition applet, but a limited choice of languages), and there may be nothing better than the Online Judge from la Universidad de Valladolid.

Project Euler is extremely good, however, for first getting your feet wet with a new language because the mathematically oriented problems typically have well-defined constraints and checking the answer is trivial. Also, because you only submit answers and not code, there’s no language limitation. Use whatever your heart desires.

Project Euler’s first problem is a cakewalk, but it was a good start for my Haskell hacking. The problem — to add all the numbers below 1000 which are multiples of 3 or 5 — is solved with a one-liner in the Haskell interpreter, although the standalone program requires a few extra lines for setup.

  1. module Main where
  2.  
  3. problem_1 = sum [x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]
  4.  
  5. main = putStrLn (show(problem_1))

The Erlang version is almost identical.

  1. -module(problem1).
  2. -export([solve/0]).
  3.  
  4. solve() -> lists:sum([X X <- lists:seq(1,999),
  5.                                   (X rem 3 == 0) or (X rem 5 ==0)]).

Please keep in mind that I don’t claim anything like proficiency in either of these two languages, and it’s highly likely that there are better ways to solve these problems. But I was forced to go searching through tutorials and docs in order to figure out how to get the answer, and in the process I learned a lot.

The power and ease of list comprehensions in Haskell and Erlang blows me away. Of course, list comprehensions are available in Python as well. The Python solution is, once again, almost identical to the other two languages, suggesting that if there’s more than one way to skin a cat, well, there’s also a best way, too.

  1. print sum([x for x in range(1,1000) if x%3 == 0 or x%5 == 0])

So head on over to Project Euler and knock some of those problems out of the park using the language you’ve been meaning to learn for some time now.

Filed in Problem Sets, Project Euler | Tagged , , , , | Permalink | Comments (1)

Changing Emacs’s default font

Saturday, July 12th, 2008

Well here’s one more. My relationship with Emacs is completely dysfunctional. I struggle with the platform, but I like struggling with it and it doesn’t seem to really mind. It is what it is.

As with any software package which is as powerful as Emacs, sometimes the simple things aren’t so simple. Take changing the default font, for example. I’m certainly not a Linux newcomer, but I’ve always despised the way X11 handles fonts. Resisting any documentation which contained words like xfontsel didn’t help out much, and I’m sorry to say that there was some trial and error involved. I am, occasionally, my own worst enemy. C’est la vie.

X11’s font selector, xfontsel, offers font choices and samples based on foundry, family, etc., but font size choices are limited. It took a frustrated near-last attempt to get something working which caused me to simply insert my own font size and see if I could get a result. I did. Yay. Were I so motivated, I might deeply investigate the arcane font physics of the Ubuntu universe. I am not so motivated. For those of you who are likewise unmotivated, but still want to change your default font, simply put something like this in your .emacs file:

  1.  
  2. ;; Font preference
  3. (add-to-list ‘default-frame-alist
  4.              ’(font . "-bitstream-bitstream vera sans mono-medium-r-normal-*-14-*-100-100-*-*-iso8859-*"))
  5.  

That 14 is the font size setting. Experiment with it until you get something you like. This works with Emacs 22.0.91.1 on Ubuntu Feisty without any issues.

If you want to try something other than Bitstream Vera Sans Mono (and, hey, go for it, man) then you can use xfontsel, too, but be sure to also use the -scaled option to give you the full range of scaled font sizes. Yes, it helps to read the man page.

Filed in Emacs | Tagged | Permalink | Comments (0)

Emacs CPU-hogging madness

Saturday, July 12th, 2008

Madness I tell you.

So I’m working with Emacs, having at a little Java hackage, and I break to go bring some Pepsi One into my day. When I come back, my CPU is whirring like the little hamster inside is amped on three cups of coffee.

Googling around for about three minutes turns up a likely suspect. The Semantic Bovinator, an Emacs-based parser generator in the same vein as bison, apparently likes to eat cycles like they’re made of peanut butter.

A solution for the problem is given here: http://www.togaware.com/linux/survivor/Emacs_Using.html.

I made the changes and, yay, life seemed to be good again. If this doesn’t fix the issue I guess I’ll have to look deeper, but so far so good.

Filed in Emacs | Tagged , , , | Permalink | Comments (0)

Vallodolid, Problem 10267 — Graphical Editor

Saturday, July 12th, 2008

Link: http://acm.uva.es/p/v102/10267.html

A simulation. Details, details, details. Simple simulations are nothing, more or less, than a test of how well you can pay extremely close attention to the problem statement. This problem was no different. I managed to nail it after three or four submissions, but they were painstaking submissions and in the end I felt more annoyance at the problem than anything like a sense of accomplishment. Meh. Still, giving a problem statment due respect has a very real application to “real life” programming, and “real life” in general, so maybe this was all worthwhile in the end, and maybe I’m a better person for it, maybe, yeah, maybe. Whatever.

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. void fill_region(vector<string>& img, int x, int y, char c, char m) {
  9.     if (img[y][x]!=m or img[y][x]==c) return;
  10.     img[y][x]=c;
  11.  
  12.     if ((y-1)>=0) fill_region(img, x  , y-1, c, m);
  13.     if ((x-1)>=0) fill_region(img, x-1, y  , c, m);
  14.     if ((x+1)<img[y].size()) fill_region(img, x+1, y  , c, m);
  15.     if ((y+1)<img.size())    fill_region(img, x  , y+1, c, m);
  16. }
  17.  
  18. int main (int argc, char const* argv[]) {
  19.  
  20.     vector<string> image;
  21.     int m, n;
  22.  
  23.     char C;
  24.     while (scanf("%c", &C)) {
  25.         if (C==‘X’) break; // game over
  26.  
  27.         switch(C) {
  28.             case ‘C’ :
  29.             case ‘I’ : { // make a new image
  30.                          scanf("%d %d", &m, &n);
  31.                          string t(m,‘O’);
  32.                          image=vector<string>(n,t);
  33.                          break;
  34.                        }
  35.             case ‘L’ : { // color a pixel
  36.                          int x, y; char c;
  37.                          scanf("%d %d %c", &x, &y, &c);
  38.                          image[y-1][x-1]=c;
  39.                          break;
  40.                        }
  41.             case ‘V’ : { // color a vert segment
  42.                          int x, y1, y2, ytmp; char c;
  43.                          scanf("%d %d %d %c", &x, &y1, &y2, &c);
  44.                          if (y1>y2) { ytmp=y2; y2=y1; y1=ytmp; }
  45.                          for (int i=y1-1; i!=y2; ++i)
  46.                              image[i][x-1]=c;
  47.                          break;
  48.                        }
  49.             case ‘H’ : { // color a horizontal segment
  50.                          int x1, x2, xtmp, y; char c;
  51.                          scanf("%d %d %d %c", &x1, &x2, &y, &c);
  52.                          if (x1>x2) { xtmp=x2; x2=x1; x1=xtmp; }
  53.                          for (int i=x1-1; i!=x2; ++i)
  54.                              image[y-1][i]=c;
  55.                          break;
  56.                        }
  57.             case ‘K’ : { // color a rect
  58.                          int x1, y1, x2, y2, xtmp, ytmp; char c;
  59.                          scanf("%d %d %d %d %c", &x1, &y1, &x2, &y2, &c);
  60.                          for (int i=y1-1; i!=y2; ++i)
  61.                              for (int j=x1-1; j!=x2; ++j)
  62.                                  image[i][j]=c;
  63.                          break;
  64.                        }
  65.             case ‘F’ : { // fill a region
  66.                          int x, y; char c, match;
  67.                          scanf("%d %d %c", &x, &y, &c);
  68.                          match=image[y-1][x-1];
  69.                          fill_region(image, x-1, y-1, c, match);
  70.                          break;
  71.                        }
  72.             case ‘S’ : { // save (display) the image
  73.                          string fn;
  74.                          cin >> fn;
  75.                          cout << fn << endl;
  76.                          for (int i=0; i<image.size(); ++i)
  77.                              cout << image[i] << endl;
  78.                          break;
  79.                        }
  80.             default  : { break; }
  81.         }
  82.     }
  83.  
  84.     return 0;
  85. }
Filed in C & C++, Online Judge | Tagged , , | Permalink | Comments (0)

Vallodolid, Problem 706 — LCD Display

Saturday, July 12th, 2008

Link: http://online-judge.uva.es/p/v7/706.html

Eh. Of all the problems in the archive, this is one of them. This type of problem — figuring out how to output difficult data displays, such as these LCD-styled numbers, or vertical histograms — is a common one, but that doesn’t make it any less annoying in a contest-problem setting. This one wasn’t especially difficult, but it wasn’t particularly interesting either. An ad hoc approach coupled with straightforward logic makes for straightforward tedium. When you get it working though, it does give a few minutes of fun.

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. int main (int argc, char const* argv[]) {
  8.  
  9.     string s, n;
  10.  
  11.     int key[][5] = {
  12.         { 1,2,0,2,1 }, // 0
  13.         { 0,0,0,0,0 }, // 1
  14.         { 1,0,1,1,1 }, // 2
  15.         { 1,0,1,0,1 }, // 3
  16.         { 0,2,1,0,0 }, // 4
  17.         { 1,1,1,0,1 }, // 5
  18.         { 1,1,1,2,1 }, // 6
  19.         { 1,0,0,0,0 }, // 7
  20.         { 1,2,1,2,1 }, // 8
  21.         { 1,2,1,0,1 }, // 9
  22.     };
  23.  
  24.     while (cin>>s>>n) {
  25.         if (s=="0" and n=="0") break;
  26.  
  27.         int S;
  28.         sscanf(s.c_str(), "%d", &S);
  29.  
  30.         for (int i=0; i<5; ++i) {
  31.             if (i%2==0) {
  32.                 // output a dashes row
  33.                 for (int j=0; j<n.length(); ++j) {
  34.                     cout << ‘ ‘;
  35.                     char ch=‘ ‘;
  36.                     int t=key[n[j]-48][i];
  37.                     if (t) ch=‘-’;
  38.                     for (int k=0; k<S; ++k) cout << ch;
  39.                     cout << ‘ ‘;
  40.                     if (j<n.length()-1) cout << ‘ ‘;
  41.                 }
  42.                 cout << endl;
  43.             } else {
  44.                 // output a set of pipe rows
  45.                 for (int j=0; j<S; ++j) {
  46.                     for (int k=0; k<n.length(); ++k) {
  47.                         int t=key[n[k]-48][i];
  48.                         char ch=‘ ‘;
  49.                         if (t==1 or t==2) ch=‘|’;
  50.                         cout << ch;
  51.                         for (int w=0; w<S; ++w) cout << ‘ ‘;
  52.                         ch=‘ ‘;
  53.                         if (t==0 or t==2) ch=‘|’;
  54.                         cout << ch;
  55.                         if (k<n.length()-1) cout << ‘ ‘;
  56.                     }
  57.                     cout << endl;
  58.                 }
  59.             }
  60.         }
  61.         cout << endl;
  62.     }
  63.     return 0;
  64. }
Filed in C & C++, Online Judge | Tagged , , | Permalink | Comments (0)

Valladolid, Problem 10137 — The Trip

Saturday, July 12th, 2008

Link: http://online-judge.uva.es/p/v101/10137.html

This problem is a trip. It’s annoyingly difficult to get just the right answer for this one, and I found no approach which was very elegant. Finally I opted for integer division and an “evening out” phase. What can I say? It works.

  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <iostream>
  5. #include <numeric>
  6. #include <string>
  7.  
  8. using namespace std;
  9.  
  10. int main()
  11. {
  12.     int A, amounts[1000], d, e, i, h, j, k, n, p, R, S, T;
  13.     string a, b, ch;
  14.  
  15.     cin >> n;
  16.     while (n) {
  17.         for (i=0; i<n; ++i) {
  18.             d=0;
  19.             p=0;
  20.             cin >> a;
  21.             S=a.size();
  22.             for (j=0; j<S; ++j) {
  23.                 if (d) ++p;
  24.                 if (a[j]!=‘.’) b+=a[j];
  25.                 else ++d;
  26.             }
  27.             sscanf(b.c_str(), "%d", &h);
  28.             for (k=0; k<2-p; ++k)
  29.                 h*=10;
  30.             amounts[i]=h;
  31.             b.erase();
  32.         }
  33.         T=accumulate(amounts, amounts+n, 0)/n;
  34.         sort(amounts, amounts+n);
  35.         A=0;
  36.         R=0;
  37.         e=0;
  38.         for (i=0; i<n; ++i)
  39.             if (amounts[i]<T)
  40.                 R+=(T-amounts[i]);
  41.  
  42.         if (accumulate(amounts, amounts+n, 0)%n) {
  43.             for (i=0; i<n; ++i)
  44.                 if (amounts[i]>T) {
  45.                     A+=(amounts[i]-T);
  46.                     ++e;
  47.                 }
  48.  
  49.             e = e > A-R ? 0 : (A-R)-e;
  50.             R+=e;
  51.         }
  52.         ch = R%100<10 ? ".0" : ".";
  53.         cout << "$" << R/100 << ch << R%100 << endl;
  54.         cin >> n;
  55.     }
  56.     return 0;
  57. }
Filed in C & C++, Online Judge | Tagged , , | Permalink | Comments (0)

Vallodolid, Problem 10189 — Minesweeper

Saturday, July 12th, 2008

Link: http://acm.uva.es/p/v101/10189.html

Fun problem. Given the many hours I’ve wasted playing minesweeper, it’s only fitting that there should be the problem of addressing the game’s logic. The problem itself is more about the simple char[][] data structure than anything else. The algorithm is as straightforward as it gets, although there are other ways to do this.

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     int r, c, i, j, fn=0, sep=0;
  8.     char field[100][100], t, n;
  9.     while (1) {
  10.         ++fn;
  11.         cin>>r>>c;
  12.         if (r==0 && c==0) break;
  13.         if (sep) cout << endl;
  14.         for (i=0; i<r; ++i) {
  15.             for (j=0; j<c; ++j) {
  16.                 cin>>t;
  17.                 field[i][j]=t;
  18.             }
  19.         }
  20.         cout<<"Field #"<<fn<<":"<<endl;
  21.         for (i=0; i<r; ++i) {
  22.             for (j=0; j<c; ++j) {
  23.                 n=‘0′;
  24.                 if (field[i][j]==‘*’) {
  25.                     cout << ‘*’;
  26.                     continue;
  27.                 }
  28.                 for (int chkr=-1; chkr<=1; ++chkr) {
  29.                     for (int chkc=-1; chkc<=1; ++chkc) {
  30.                         if (chkr==0 && chkc==0) continue;
  31.                         if (i+chkr<0 || i+chkr>=r) continue;
  32.                         if (j+chkc<0 || j+chkc>=c) continue;
  33.                         if (field[i+chkr][j+chkc]==‘*’) ++n;
  34.                     }
  35.                 }
  36.                 cout << n;
  37.             }
  38.             cout << endl;
  39.         }
  40.         sep=1;
  41.     }
  42.     return 0;
  43. }
Filed in C & C++, Online Judge | Tagged , , | Permalink | Comments (0)

1.12 — Pascal’s Triangle

Saturday, July 12th, 2008

Ah, Pascal’s Triangle.

I fumbled on the second recursive call, thinking (+ position 1) instead of just position — I suppose because the visual of the triangle shows that for any arbitrary element not part of a side, the second element in the row above is to the right of the chosen element. Stoopid triangles and their dumb three sides.

But this one does a good job of showing how intuitive it is to think in recursive terms. The forms of the input and output didn’t seem immediately obvious, though, so I winged it. This function barfs out the value of the element at the given row and position, beginning with 0.If you wanted, changing the starting index of the row and position to 1 is accomplished by changing the first condition to ((= position 1) 1). This changes the row index too because, hey, it’s a triangle.

  1. (define (pascals-triangle row position)
  2.   (cond ((= position 0) 1)
  3.         ((= position row) 1)
  4.         (else (+ (pascals-triangle (- row 1) (- position 1))
  5.                  (pascals-triangle (- row 1) position)))))
Filed in SICP | Tagged , , | Permalink | Comments (0)

1.11 — Recursion vs. iteration

Saturday, July 12th, 2008

Where some function f is:

Some function f

This exercise did a good job of illustrating the intuitive nature of a recursive implementation. Managing state in the iterative version requires a little more setup.

It’s a fun trade-off, too, because the iterative version demolishes, performance-wise, the tree in the recursive version which develops in higher values of n.

  1. (define (r n)
  2.   (if (< n 3)
  3.       3
  4.       (+ (r (- n 1))
  5.         (* 2 (r (- n 2)))
  6.         (* 3 (r (- n 3))))))
  7.  
  8. (define (i n)
  9.   (define (i-iter fn-1 fn-2 fn-3 counter)
  10.     (if (= counter n)
  11.         (+ fn-1 (* 2 fn-2) (* 3 fn-3))
  12.         (i-iter (+ fn-1 (* 2 fn-2) (* 3 fn-3))
  13.                 fn-1
  14.                 fn-2
  15.                 (+ counter 1))))
  16.   (if (< n 3)
  17.       3
  18.       (i-iter 3 3 3 3)))
Filed in SICP | Tagged , , | Permalink | Comments (0)

1.8 — Newton’s cube roots

Saturday, July 12th, 2008

Nothin’ much going on here. This solution is essentially a modification of an explanation rendered in the text. The most difficult thing to do is to code Newton’s formula for improving the guess:

Newton’s Cube Root Improvement Equation

Still, Newton’s method is interesting, so here goes …

  1. (define (cbrt x)
  2.   (cbrt-iter 1.0 x 0.0))
  3.  
  4. (define (cbrt-iter guess x last-guess)
  5.   (if (good-enough? guess last-guess)
  6.       guess
  7.       (cbrt-iter (improve guess x)
  8.                  x guess)))
  9.  
  10. (define (good-enough? guess last-guess)
  11.   (< (abs (- guess last-guess)) 0.0001))
  12.  
  13. (define (improve guess x)
  14.   (/ (+  (/ x (* guess guess)) (* 2 guess)) 3))
Filed in SICP | Tagged , , | Permalink | Comments (0)