10k Hours of Code: October 2012

Wednesday, October 24, 2012

Splitting a python list into groups of n

Say you have a list L, that you want broken into sublists l1, l2, ... lm of length n. What's the best way to go about doing this in python?

One simple idiom works as follows:

>>> groupn = lambda l, n: zip(*(iter(l),) * n)
>>> groupn(range(12), 3)
[(0, 1, 2), (3, 4, 5), (6, 7, 8), (9, 10, 11)]

So, how exactly does this work?

First, let's take a look at an alternate, but more syntactically revealing version of the groupn function:

>>> alt_groupn = lambda l, n: zip(*[iter(l)] * n)
>>> alt_groupn(range(12), 3)
[(0, 1, 2), (3, 4, 5), (6, 7, 8), (9, 10, 11)]

The key thing to note here is the [iter(l)] * n. This is creating a list of length n of references to the *same* iterator.

>>> l = range(10)
>>> [ iter(l) ] * 3
[<listiterator object at 0x10a1d6310>, <listiterator object at 0x10a1d6310>, <listiterator object at 0x10a1d6310>]

Unpacking this list as an argument to zip is equivalent to:

>>> i = iter(range(10))
>>> zip(i, i, i)
[(0, 1, 2), (3, 4, 5), (6, 7, 8)]

The magic happens because zip draws elements from the same iterator to fill the different positions of each tuple!

Tuesday, October 9, 2012

How to use highlight.js with Blogger

This is simple walkthrough of how to add syntax highlighting to a Blogger blog. Specifically, we will use the highlight.js javascript/css sources. This will turn boring code snippets like this:

#include 
int main() {
    printf("Hello, world!\n");
}

into highlighted beauties like this:

#include 
int main() {
    printf("Hello, world!\n");
}

The steps are loosely defined at the highlight.js home here.

Click the "Template" link on your Blogger page.
Click "Edit HTML"

Add the following to your <head>...</head>:

    <link href='http://yandex.st/highlightjs/7.2/styles/ir_black.min.css' rel='stylesheet'/>
    <script src='http://yandex.st/highlightjs/7.2/highlight.min.js'/>
    <script>
      hljs.initHighlightingOnLoad();
    </script>

Wrap your code in <pre><code> # YOUR CODE HERE </code></pre> tags.
There is no step five. That's it!

Friday, October 5, 2012

UVa : 100 (The 3n + 1 Problem)

Pitfalls:

1. i can be greater than j
2. If you use an array, recall that large odd values (e.g. 999999) will map to 3*n + 1

Verdict: Accepted
Runtime: 0.956


// START CODE
#include <iostream>
#include <stdio.h>
#include <stack>
#include <map>
#include <algorithm>

#define MAX 1000000

using namespace std;

map<int, int> m;

int next(int n) {
  if (n % 2 == 1)
    return 3 * n + 1;
  else
    return n / 2;
}

int cycleLength(int n) {
  int save = n;
  stack<int> s;
  while (m.find(n) == m.end()) {
    s.push(n);
    n = next(n);
  }
  while (!s.empty()) {
    m[s.top()] = 1 + m[n];
    n = s.top();
    s.pop();
  }
  return m[save];
}

int main() {
  m[1] = 1;

  while (1) {
    int i, j;
    cin >> i >> j;
    if (cin.eof())
      break;
    printf("%d %d ", i, j);
    if (i > j)
      swap(i, j);
    int m = 1;
    for (; i <= j; i++)
      m = max(m, cycleLength(i));
    printf("%d\n", m);
  }
}
// END CODE