David Tran’s blog

iPhone project is almost done.

Good Flex Tutorial on Adobe Web Site: Flex in a week

Day 1 : done. (2009-04-25)
Day 2 : done. (2009-04-27)
Day 3 : done. (2009-04-29)
Day 4 : done. (2009-05-05)
Day 5 : done. (2009-05-08)

Book “Getting Started with Flex 3″ can be downloaded from the “Flex in a week” training page : done. (2009-05-10)

My power set solution is defined.
I just found there is challenge question about get the power set in “order” without using sort.
For example:

subsets [] = [[]]
subsets [1,2,3] = [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

My solution for this challenge is simply reuse my combination function.

combination :: [a] -> Int -> [[a]]
combination _   0    = [[]]
combination []  _    = []
combination (x:xs) n = map (x:) (combination xs (n-1)) ++ combination xs n

subset :: [a] -> [[a]]
subset xs = concat [combination xs k | k <- [0..n]] where n = length xs

/*
 * Author : David Tran
 * Date   : 2008-04-03
 * Quiz   : CountPaths
 */

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Quiz4 {
    
    public static void main(String[] args) throws Exception {
        new Quiz4().solve();
    }

    public void solve() {
        long start = System.currentTimeMillis();
        loadProblem();
        BigInteger solutions = BigInteger.ZERO;
        for (int index : starts) {
            solutions = solutions.add(findSolution(index / cols, index % cols, 0));
        }
        System.out.println("Total Solution = " + solutions);
        System.out.println("Total time (msec) to solve = " + (System.currentTimeMillis() - start));
    }
    
    public Quiz4() throws Exception {
        rows = 50;
        cols = 50;
        cellLength = 1;
        goal = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"; // 50x"A"
        gridData = new String[rows][cols];  // 50×50x"A"
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                gridData[i][j] = "A";
            }
        }
    }
    
    private int rows;
    private int cols;
    private int lastNumber;
    private List<Integer> starts;
    private Map<Integer, BigInteger>[][] grid;

    private int cellLength;
    private String goal;
    private String[][] gridData;
    
    
    @SuppressWarnings("unchecked")
    private void loadProblem() {
        // split goal string to build up dictionary
        Map<String, List<Integer>> dictionary = new HashMap<String, List<Integer>>();
        for (int nb = 0, position = 0, length = goal.length(); position < length; nb++, position += cellLength) {
            String substring = goal.substring(position, position + cellLength);
            if (dictionary.containsKey(substring)) {
                dictionary.get(substring).add(nb);
            } else {
                List<Integer> values = new ArrayList<Integer>();
                values.add(nb);
                dictionary.put(substring, values);
            }
        }
        if (dictionary.size() <= 0) {
            throw new IllegalArgumentException("No input data ?!");
        }
        
        lastNumber = (goal.length() / cellLength) - 1;
        starts = new ArrayList<Integer>();
        grid = (Map<Integer, BigInteger> [][]) new Map[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                String key = gridData[i][j];
                if (dictionary.containsKey(key)) {
                    Map<Integer, BigInteger> map = new HashMap<Integer, BigInteger>();
                    for (int nb : dictionary.get(key)) {
                        map.put(nb, null);
                        if (nb == 0) {
                            starts.add(i * cols + j);
                        }
                    }
                    grid[i][j] = map;
                }
            }
        }
    }
    
    private BigInteger findSolution(int i, int j, int nb) {
        if (nb == lastNumber) {
            return BigInteger.ONE;
        } else {
            BigInteger solutions = grid[i][j].get(nb);
            if (solutions == null) {
                solutions = BigInteger.ZERO;
                for (int index : findNeighbors(i, j, nb)) {
                    solutions = solutions.add(findSolution(index / cols, index % cols, nb + 1));
                }
                grid[i][j].put(nb, solutions);
            }
            return solutions;
        }
    }
    
    private List<Integer> findNeighbors(int i, int j, int nb) {
        int nextNb = nb + 1;
        List<Integer> neighbors = new ArrayList<Integer>();
        addNeighbor(i - 1, j - 1, nextNb, neighbors);
        addNeighbor(i - 1, j    , nextNb, neighbors);
        addNeighbor(i - 1, j + 1, nextNb, neighbors);
        addNeighbor(i    , j - 1, nextNb, neighbors);
        addNeighbor(i    , j + 1, nextNb, neighbors);
        addNeighbor(i + 1, j - 1, nextNb, neighbors);
        addNeighbor(i + 1, j    , nextNb, neighbors);
        addNeighbor(i + 1, j + 1, nextNb, neighbors);
        return neighbors;
    }
    
    private void addNeighbor(int i, int j, int nb, List<Integer> list) {
        if (i >= 0 && i < rows && j >= 0 && j < cols && 
                grid[i][j] != null && grid[i][j].containsKey(nb)) {
            list.add(i * cols + j);
        }
    }
}

Result on my machine:

A:>java Quiz4
Total Solution = 303835410591851117616135618108340196903254429200
Total time (msec) to solve = 562

# Author : David Tran
# Date   : 2008-04-02
# Quiz   : http://davidtran.doublegifts.com/blog/?p=139
# File   : quiz.rb

class Quiz

  def initialize(grid_file, goal_file)
    grid_data = IO.readlines(grid_file).map {|e| e.chomp}.map {|e| e.split(/\s+/)}
    goal = IO.read(goal_file).chomp
  
    @rows = grid_data.size
    @cols = grid_data[0].size
    cell_size = grid_data[0][0].size
  
    # split goal string to build up dictionary
    dictionary = Hash.new {|h, e| h[e] = []}
    index = 0
    goal.scan(/#{'.' * cell_size}/).each do |w|
      dictionary[w] << index
      index += 1
    end
  
    @last_nb = (goal.size / cell_size) - 1
    @grid = Array.new(@rows) { Array.new(@cols) { Hash.new } }
    starts = []
  
    @rows.times do |r|
      @cols.times do |c|
        dictionary[grid_data[r][c]].each do |v|
          @grid[r][c][v] = -1
          starts << [r,c] if v == 0
        end
      end
    end

    solutions = starts.inject(0) { |s, (i,j)| s += find_solution(i, j, 0) }
    puts "Total Solution = #{solutions}"
  end
  
  def find_solution(i, j, nb)
    return 1 if nb == @last_nb
    return @grid[i][j][nb] if @grid[i][j][nb] >= 0
    @grid[i][j][nb] = get_neighbors(i, j, nb).inject(0) { |s, (x, y)| s += find_solution(x, y, nb+1) }
  end
  
  def get_neighbors(i, j, nb)
    [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]].inject([]) do |a, (x,y)|
      a << neighbor(i+x, j+y, nb+1)
    end.compact
  end
  
  def neighbor(i, j, nb)
    (i >= 0 && i < @rows && j >= 0 && j < @cols && @grid[i][j].key?(nb)) ? [i, j] : nil
  end
  
end

if $0 == __FILE__
  (puts "Usage: ruby quiz.rb  grid_file  goal_file"; exit) if ARGV.size < 2
  Quiz.new(ARGV[0], ARGV[1])
end

# ============================== #

# Author : David Tran
# Date   : 2008-04-02
# File   : test.rb
# Object : find the maximum solutions

open('grid.txt', 'w') {|f| 50.times { f << 'A ' * 50 << "\n"}}
max = 0
index = -1
50.times do |i|
  i += 1
  open('goal.txt', 'w') { |f| f << 'A' * i }
  result = %x{ ruby quiz.rb grid.txt goal.txt }
  if result =~ /Solution = (\d+)/
    solutions = $1.to_i
    puts "#{i.to_s.rjust(2, '0')} => #{solutions}"
    if (solutions > max)
      max = solutions
      index = i
    end
  end
end

puts
puts "Maximum => #{index} => #{max}"


__END__
Result:

01 => 2500
02 => 19404
03 => 152292
04 => 1198512
05 => 9453300
06 => 74662104
07 => 590305088
08 => 4670864544
09 => 36982919796
10 => 292979734056
11 => 2322050158968
12 => 18410909224368
13 => 146024921567904
14 => 1158535320863088
15 => 9194071282628352
16 => 72981174038164224
17 => 579439667561976564
18 => 4601415854638476552
19 => 36547133286285125864
20 => 290326968106929048336
21 => 2306684143572560961624
22 => 18329503368942296048880
23 => 145670217447616179975600
24 => 1157829208250036601664992
25 => 9203827271760017849641312
26 => 73171094997928920840845904
27 => 581774919929278927886179248
28 => 4626070561470449649010421664
29 => 36788241251602079481574654656
30 => 292579041503607826263355150176
31 => 2327088439774693588696558829376
32 => 18510420519854069350331486524800
33 => 147248802959429409354656962751220
34 => 1171434060031010511872752993856328
35 => 9319939961558447074697552088702600
36 => 74154290207123230340766878367722064
37 => 590046376097012157795995971369959624
38 => 4695281006073221324094307242033576432
39 => 37364705320671553187068052340260719824
40 => 297361737077320616265561468778248253728
41 => 2366634780471229416464762512469663693592
42 => 18836455040472517436022242181973614080112
43 => 149929836577708085403038515575864523777776
44 => 1193430584532300786500980677298194867380832
45 => 9500046751158181070821773471417360223448304
46 => 75626347587870791654047249972768528120486752
47 => 602058474789522292652482399670191674941123040
48 => 4793158368431771829259255859223541964804203200
49 => 38161186114402617099716572074367083097283018976
50 => 303835410591851117616135618108340196903254429200

Maximum => 50 => 303835410591851117616135618108340196903254429200

/*
 * Author : David Tran
 * Date   : 2008-03-31
 * Quiz   : see  http://davidtran.doublegifts.com/blog/?p=140
 * Note   : Revise previous version, improve it to use less memory and much faster.
 *          Instead of caching neighbors, this time it caches the solutions number. 
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Quiz2 {
    
    public static void main(String[] args) {
        new Quiz2().solve();
    }

    public void solve() {
        loadProblem();
        int solutions = 0;
        for (int index : starts) {
            solutions += findSolution(index / cols, index % cols, 0);
        }
        System.out.println("Total Solution = " + solutions);
    }
    
    private int rows;
    private int cols;
    private int lastNumber;
    private List<Integer> starts;
    private Map<Integer, Integer>[][] grid;  // key=position in goal;value=number solutions
    
    @SuppressWarnings("unchecked")
    private void loadProblem() {
        // to simplify, we hard-coded the problem data for now.
        // and skip all preconditions checking:
        // *   0 < rows, cols, goal’s length, cell’s length <= 50
        // *   all cell have the exact cellLength length
        // *   goal’s length modulo cell’s length == 0
        
        rows = 3;
        cols = 3;
        int cellLength = 2;
        String[][] gridData = {
            {"AA", "BB", "CZ"},
            {"FF", "EE", "DD"},
            {"GX", "AA", "IY"},
        };
        String goal = "AAEEAA";

        // split goal string to build up dictionary
        Map<String, List<Integer>> dictionary = new HashMap<String, List<Integer>>();
        for (int nb = 0, position = 0, length = goal.length(); position < length; nb++, position += cellLength) {
            String substring = goal.substring(position, position + cellLength);
            if (dictionary.containsKey(substring)) {
                dictionary.get(substring).add(nb);
            } else {
                List<Integer> values = new ArrayList<Integer>();
                values.add(nb);
                dictionary.put(substring, values);
            }
        }
        if (dictionary.size() <= 0) {
            throw new IllegalArgumentException("No input data ?!");
        }
        
        lastNumber = (goal.length() / cellLength) - 1;
        starts = new ArrayList<Integer>();
        grid = (Map<Integer, Integer> [][]) new Map[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                String key = gridData[i][j];
                if (dictionary.containsKey(key)) {
                    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
                    for (int nb : dictionary.get(key)) {
                        map.put(nb, null);
                        if (nb == 0) {
                            starts.add(i * cols + j);
                        }
                    }
                    grid[i][j] = map;
                }
            }
        }
    }
    
    private int findSolution(int i, int j, int nb) {
        int solutions = 0;
        if (nb == lastNumber) {
            solutions = 1;
        } else {
            if (grid[i][j].get(nb) != null) {
                solutions = grid[i][j].get(nb);
            } else {
                for (int index : findNeighbors(i, j, nb)) {
                    solutions += findSolution(index / cols, index % cols, nb + 1);
                }
                grid[i][j].put(nb, solutions);
            }
        }
        return solutions;
    }
    
    private List<Integer> findNeighbors(int i, int j, int nb) {
        int nextNb = nb + 1;
        List<Integer> neighbors = new ArrayList<Integer>();
        addNeighbor(i - 1, j - 1, nextNb, neighbors);
        addNeighbor(i - 1, j    , nextNb, neighbors);
        addNeighbor(i - 1, j + 1, nextNb, neighbors);
        addNeighbor(i    , j - 1, nextNb, neighbors);
        addNeighbor(i    , j + 1, nextNb, neighbors);
        addNeighbor(i + 1, j - 1, nextNb, neighbors);
        addNeighbor(i + 1, j    , nextNb, neighbors);
        addNeighbor(i + 1, j + 1, nextNb, neighbors);
        return neighbors;
    }
    
    private void addNeighbor(int i, int j, int nb, List<Integer> list) {
        if (i >= 0 && i < rows && j >= 0 && j < cols && 
                grid[i][j] != null && grid[i][j].containsKey(nb)) {
            list.add(i * cols + j);
        }
    }
}

/*
 * Author : David Tran
 * Date   : 2008-03-29
 * Quiz   : see  http://davidtran.doublegifts.com/blog/?p=139
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class Quiz {
    
    public static void main(String[] args) {
        new Quiz().solve();
    }

    public void solve() {
        loadProblem();
        for (int index : starts) {
            findSolution(index / cols, index % cols, 0);
        }
        System.out.println("Total Solution = " + solutions);
    }
    
    private int rows;
    private int cols;
    private int lastNumber;
    private int solutions;
    private List<Integer> starts;
    private Map<Integer, List<Integer>>[][] grid;
    
    @SuppressWarnings("unchecked")
    private void loadProblem() {
        // to simplify, we hard-coded the problem data for now.
        // and skip all preconditions checking:
        // *   0 < rows, cols, goal’s length, cell’s length <= 50
        // *   all cell have the exact cellLength length
        // *   goal’s length modulo cell’s length == 0
        
        rows = 3;
        cols = 3;
        int cellLength = 2;
        String[][] gridData = {
            {"AA", "BB", "CZ"},
            {"FF", "EE", "DD"},
            {"GX", "AA", "IY"},
        };
        String goal = "AAEEAA";

        /* - - - - - - - - - - - - 
        int cellLength = 1;
        String[][] gridData = {
            {"A", "B", "C"},
            {"D", "E", "F"},
            {"G", "A", "I"},
        };
        String goal = "AEA";
         - - - - - - - - - - - - */
        
        // split goal string to build up dictionary
        Map<String, List<Integer>> dictionary = new HashMap<String, List<Integer>>();
        for (int nb = 0, position = 0, length = goal.length(); position < length; nb++, position += cellLength) {
            String substring = goal.substring(position, position + cellLength);
            if (dictionary.containsKey(substring)) {
                dictionary.get(substring).add(nb);
            } else {
                List<Integer> values = new ArrayList<Integer>();
                values.add(nb);
                dictionary.put(substring, values);
            }
        }
        if (dictionary.size() <= 0) {
            throw new IllegalArgumentException("No input data ?!");
        }
        
        lastNumber = (goal.length() / cellLength) - 1;
        starts = new ArrayList<Integer>();
        grid = (Map<Integer, List<Integer>> [][]) new Map[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                String key = gridData[i][j];
                if (dictionary.containsKey(key)) {
                    Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
                    for (int nb : dictionary.get(key)) {
                        map.put(nb, null);
                        if (nb == 0) {
                            starts.add(i * cols + j);
                        }
                    }
                    grid[i][j] = map;
                }
            }
        }
    }
   
    private Stack<String> stack = new Stack<String>();
    private void findSolution(int i, int j, int nb) {
        stack.push("(" + i + "," + j + ") ");
        if (nb == lastNumber) {
            solutions++;
            System.out.println(stack);
        } else {
            if (grid[i][j].get(nb) == null) {
                findNeighbors(i, j, nb);
            }
            for (int index : grid[i][j].get(nb)) {
                findSolution(index / cols, index % cols, nb + 1);
            }
        }
        stack.pop();
    }
    
    private void findNeighbors(int i, int j, int nb) {
        int nextNb = nb + 1;
        List<Integer> neighbors = new ArrayList<Integer>();
        addNeighbor(i - 1, j - 1, nextNb, neighbors);
        addNeighbor(i - 1, j    , nextNb, neighbors);
        addNeighbor(i - 1, j + 1, nextNb, neighbors);
        addNeighbor(i    , j - 1, nextNb, neighbors);
        addNeighbor(i    , j + 1, nextNb, neighbors);
        addNeighbor(i + 1, j - 1, nextNb, neighbors);
        addNeighbor(i + 1, j    , nextNb, neighbors);
        addNeighbor(i + 1, j + 1, nextNb, neighbors);
        grid[i][j].put(nb, neighbors);
    }
    
    private void addNeighbor(int i, int j, int nb, List<Integer> list) {
        if (i >= 0 && i < rows && j >= 0 && j < cols && 
                grid[i][j] != null && grid[i][j].containsKey(nb)) {
            list.add(i * cols + j);
        }
    }
}

/* ============================================================================
 
The problem: count the ways to find a word by walking on a grid

You are given a rectangular grid of letters and a word to find. 
You must compute the number of ways to find the word within the grid using the following rules:

* start at any cell within the grid
* from there, move to any of the cell’s eight neighboring cells
* continue moving from that neighbor to its neighbors, and so on, until you have spelled out the word
* you may visit cells more than once, but you cannot visit the same cell twice in a row (i.e., you must move for each turn)

Constraints:
* grid will contain between 1 and 50 elements, inclusive.
* Each element of grid will contain between 1 and 50 uppercase (’A’-’Z’) letters, inclusive.
* Each element of grid will contain the same number of characters.
* find will contain between 1 and 50 uppercase (’A’-’Z’) letters, inclusive.  
 
 
For instance, consider the following grid, taken from the examples in the problem statement:

ABC
FED
GAI

If you were asked to find the word “AEA” on this grid, you could do it in four ways:

1:
*BC ABC *BC
FED F*D FED
GAI GAI GAI

2:
*BC ABC ABC
FED F*D FED
GAI GAI G*I

3:
ABC ABC *BC
FED F*D FED
G*I GAI GAI

4:
ABC ABC ABC
FED F*D FED
G*I GAI G*I

If you were asked to find “ABCD”, you could do it in only one way:

1:
*BC A*C AB* ABC
FED FED FED FE*
GAI GAI GAI GAI

If you were asked to find “AAB”, you could not: 
there are no “A” cells on the grid that have other “A” cells as neighbors. 
  
============================================================================ */

/*
 *  Author :  David Tran
 *  Date   :  2008-03-28
 */
using System;
using System.Collections.Generic;
using System.Text;

namespace Quiz
{
    class Quiz
    {
        static void Main(string[] args)
        {
            new Quiz().Solve();
        }

        public void Solve()
        {
            LoadProblem();
            foreach (Index index in starts)
            {
                FindSolution(index.i, index.j, 0);
            }
            Console.WriteLine("Total Solution = {0}", solutions);
        }

        struct Index
        {
            public readonly int i;
            public readonly int j;
            public Index(int i, int j)
            {
                this.i = i;
                this.j = j;
            }
        }

        int rows;
        int cols;
        Dictionary<int, List<Index>>[,] grid;
        int lastNumber;
        List<Index> starts;
        int solutions = 0;

        private void LoadProblem()
        {
            // to simplify, we hard-coded the problem data for now.
            rows = 3;
            cols = 3;
            int cellLength = 2;
            string[,] gridData = {
                {"AA", "BB", "CZ"},
                {"FF", "EE", "DD"},
                {"GX", "AA", "IY"},
            };
            string goal = "AAEEAA";

            // split goal string to build up dictionary
            IDictionary<string, List<int>> dictionary = new Dictionary<string, List<int>>();
            for (int nb = 0, position = 0; position < goal.Length; nb++, position += cellLength)
            {
                string substring = goal.Substring(position, cellLength);
                if (!dictionary.ContainsKey(substring))
                {
                    dictionary[substring] = new List<int>();
                }
                dictionary[substring].Add(nb);
            }

            if (dictionary.Count <= 0)
            {
                throw new Exception("No input data ?!");
            }

            lastNumber = (goal.Length / cellLength) - 1;
            starts = new List<Index>();
            grid = new Dictionary<int, List<Index>>[rows, cols];

            // build up grid and starts
            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < cols; j++)
                {
                    string key = gridData[i, j];
                    if (dictionary.ContainsKey(key))
                    {
                        grid[i, j] = new Dictionary<int, List<Index>>();
                        foreach (int nb in dictionary[key])
                        {
                            grid[i, j].Add(nb, null);
                            if (nb == 0)
                            {
                                starts.Add(new Index(i, j));
                            }
                        }
                    }
                }
            }
        }

        private void FindSolution(int i, int j, int nb)
        {
            if (nb == lastNumber)
            {
                solutions++;
            }
            else
            {
                // build neighbors when needed, and memorize after builded.
                if (grid[i, j][nb] == null)
                {
                    FindNeighbors(i, j, nb);
                }

                foreach (Index index in grid[i, j][nb])
                {
                    FindSolution(index.i, index.j, nb + 1);
                }
            }
        }

        private void FindNeighbors(int i, int j, int nb)
        {
            int nextNb = nb + 1;
            List<Index> neighbors = new List<Index>();
            AddNeighbor(i - 1, j - 1, nextNb, neighbors);
            AddNeighbor(i - 1, j    , nextNb, neighbors);
            AddNeighbor(i - 1, j + 1, nextNb, neighbors);
            AddNeighbor(i    , j - 1, nextNb, neighbors);
            AddNeighbor(i    , j + 1, nextNb, neighbors);
            AddNeighbor(i + 1, j - 1, nextNb, neighbors);
            AddNeighbor(i + 1, j    , nextNb, neighbors);
            AddNeighbor(i + 1, j + 1, nextNb, neighbors);
            grid[i, j][nb] = neighbors;
        }

        private void AddNeighbor(int i, int j, int nb, List<Index> list)
        {
            if (i >= 0 && i < rows &&
                j >= 0 && j < cols &&
                grid[i, j] != null &&
                grid[i, j].ContainsKey(nb))
            {
                list.Add(new Index(i, j));
            }
        }
    }
}

import EX_7_8 hiding (channel, transmit)

channel :: [Bit] -> [Bit]
channel = tail

-- need to redefine transmit to force it use this new verion of channel
transmit :: String -> String
transmit = decode . channel . encode

main = do 
       putStrLn $ transmit "Haskell is fun!"

{-
$> ghci
GHCi, version 6.8.2: http://www.haskell.org/ghc/  :? for help
Loading package base ... linking ... done.
Prelude> :l ex.7.9  ex.7.8
[1 of 2] Compiling EX_7_8           ( ex.7.8.hs, interpreted )
[2 of 2] Compiling Main             ( ex.7.9.hs, interpreted )
Ok, modules loaded: EX_7_8, Main.
*Main> main
*** Exception: Parity checking fail.
*Main>
-}

module EX_7_8 where

import Data.Char

type Bit = Int

bin2int :: [Bit] -> Int
bin2int = foldr (\x y -> x + 2 * y) 0

int2bin :: Int -> [Bit]
int2bin 0 = []
int2bin n = n `mod` 2 : int2bin (n `div` 2)

make8 :: [Bit] -> [Bit]
make8 bits = take 8 (bits ++ repeat 0)

addParityBit :: [Bit] -> [Bit]
addParityBit bits = bits ++ [parity]
                    where parity = length (filter (==1) bits) `mod` 2

checkParityBit :: [Bit] -> [Bit]
checkParityBit bits =
  if last bits == length (filter (==1) (init bits)) `mod` 2
  then init bits
  else error "Parity checking fail."

encode :: String -> [Bit]
encode = concat . map (addParityBit . make8 . int2bin . ord)

chop :: Int -> [Bit] -> [[Bit]]
chop _ []   = []
chop n bits = take n bits : chop n (drop n bits)

decode :: [Bit] -> String
decode = map (chr . bin2int . checkParityBit) . (chop 9)

transmit :: String -> String
transmit = decode . channel . encode

channel :: [Bit] -> [Bit]
channel = id