iPhone Application
April 25th, 2009iPhone project is almost done.
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