1c.js

#!/usr/bin/env node
var util = require('util');

process.stdin.resume();
process.stdin.setEncoding('utf8');

var chunks = [];

function unique_chars(str) {
  var seen = {},
      count = 0,
      chr;

  for (var i = 0, l = str.length; i < l; i++) {
    chr = str[i];
    if (!(chr in seen)) {
      seen[chr] = 1;
      count++;
    }
  }

  return count;
}

function min_int_val(str, base) {
  var max_val = 2,
      found_one = false,
      found_zero = false,
      char_map = {},
      value = 0,
      v,
      chr;

  for (var i = 0, l = str.length; i < l; i++) {
    chr = str[i];

    if (chr in char_map) {
      v = char_map[chr];

    } else {
      if (!found_one) {
        found_one = true;
        v = 1;

      } else if (!found_zero) {
        found_zero = true;
        v = 0;

      } else {
        v = max_val;
        max_val++;
      }

      char_map[chr] = v;
    }

    value += Math.pow(base, l - i - 1) * v;
  }

  return value;
}

function interpret_string(str) {
  var best_base = unique_chars(str);
  if (best_base == 1) {
    best_base = 2;
  }
  return min_int_val(str, best_base);
}

function end_trigger() {
  var lines = chunks.join('').split('\n'),
      line_count = parseInt(lines[0], 10);

  for (var i = 1; i <= line_count; i++) {
    console.log('Case #%d: %d', i, interpret_string(lines[i]));
  }
}

process.stdin.on('data', function(chunk) {
  chunks.push(chunk)
});

process.stdin.on('end', end_trigger);

// time cat small.in | node 1c.js > small.out
// real 0m0.098s
// user 0m0.050s
// sys  0m0.015s

1c.py

import sys

chunks = []

def unique_chars(s):
    return len(set(s))

def min_int_val(s, base):
    max_val = 2
    found_one = found_zero = False
    char_map = {}
    length = len(s)
    value = 0

    for i, char in enumerate(s):
        if char in char_map:
            v = char_map[char]
        else:
            if not found_one:
                found_one = True
                v = 1
            elif not found_zero:
                found_zero = True
                v = 0
            else:
                v = max_val
                max_val += 1

            char_map[char] = v

        value += base**(length - i - 1) * v

    return value

def interpret_string(s):
    best_case = unique_chars(s)
    if best_case == 1:
        best_case = 2
    return min_int_val(s, best_case)

first_line = True
lines_to_read = 0
line_num = 0
for line in sys.stdin:
    if first_line:
        first_line = False
        lines_to_read = int(line.strip())
        continue

    if line_num == lines_to_read:
        break

    line_num += 1
    print 'Case #{0}: {1}'.format(line_num, interpret_string(line.strip()))

p024.hs

($>) = flip ($)

fact k = foldl (*) 1 [2..k]

-- returns a tuple of the ith element, and the list without the ith element
--
-- example:
-- excise 0 [1, 2, 3] = (1, [2, 3])
-- excise 1 [2, 9, 7] = (9, [2, 7])
--
excise :: Num a => a -> [t] -> (t, [t])
excise i l = excise' i l (\x y -> (x, y))
    where excise' i (a:as) c
              | i == 0    = c a as
              | otherwise = excise' (i - 1) as (\x y -> c x (a:y))


-- returns the kth permutation of the list l
--
-- observing the permutations of [0, 1, 2]
--    012    021    102    120    201    210
-- the first character repeats (n - 1)! times, and appear in the same order
-- as the original list.
--
-- The integral quotient of the permutation number k and (n - 1)! gives the
-- index of the first item in the permutation. This can then be extended
-- recursively
--
permutation_k :: Int -> [a] -> [a]
permutation_k k l = permutation_k' k l (length l)
    where permutation_k' _ [] _ = []
          permutation_k' k l  s = v:(permutation_k' k' l' s')
              where s'      = s - 1
                    (i, k') = divMod k (fact s')
                    (v, l') = excise i l

main = do
    permutation_k 999999 ['0'..'9']
        $> putStrLn


-- time ./p024
-- real    0m0.003s
-- user    0m0.001s
-- sys     0m0.002s

p025.hs

($>) = flip ($)

-- infinite fibonacci sequence
fibs = fibs' 1 1
    where fibs' x y = x:(fibs' y (x + y))

-- finds the index of the first item that satisfies the predicate
nth_satisfies p l = nth_satisfies p l 1
    where nth_satisfies p (x:xs) i
              | p x       = i
              | otherwise = nth_satisfies p xs (i + 1)

main = do
    fibs
        $> nth_satisfies (> 10^999)
        $> show
        $> putStrLn

-- time ./p025
-- real    0m0.007s
-- user    0m0.002s
-- sys     0m0.003s

p026.hs

import qualified Data.Map

($>) = flip ($)

origApply f v = (v, f v)

chooseMaxBy p a b
    | p a > p b = a
    | otherwise = b

-- returns the number of repeating digits via long division
longDiv n d = longDiv' n d Data.Map.empty 0
    where longDiv' 0 _ _ _ = 0
          longDiv' n d s i
              | Data.Map.member n s = i - Data.Map.findWithDefault 0 n s
              | otherwise           = longDiv' n' d (Data.Map.insert n i s) i'
              where n' = 10 * (mod n d)
                    i' = i + 1

main = do
    [3,5..999] -- even number K will yield same repeat length as K / 2
        $> map (origApply (longDiv 1))
        $> foldl (chooseMaxBy snd) (0, 0)
        $> fst
        $> show
        $> putStrLn

-- time ./p026
-- real    0m0.125s
-- user    0m0.038s
-- sys     0m0.003s