I did a quick matrix to compare various mobile JS frameworks in late May. It is probably a little outdated, especially with the recent Sencha merger, and I did not know DashCode could create web applications at the time, but maybe it will help someone. Enjoy! http://bit.ly/d6Gsaj
Here’s a great wrapper that really simplifies working with KeyChain in iOS http://log.scifihifi.com/post/55837387/simple-iphone-keychain-code. The code is on GitHub as well http://github.com/ldandersen/scifihifi-iphone/tree/master/security/.
Apple’s official documentation is here, and there is also a sample project, but it’s not a good example for getting up and running quickly. The version of the project (last updated 10/2009) doesn’t even run on the simulator.
I was having big issues deploying to an iPad from XCode tonight. There was an error concerning invalid entitlements.
The executable was signed with invalid entitlements.
The entitlements specified in your application’s Code Signing Entitlements file do not match those specified in your provisioning profile.
(0xE8008016)
I was able to fix this by making sure a valid provisioning profile existed, adding this profile to Organizer, and then making sure the application identifier created in the Apple Developer portal matched the bundle identifier field in my applications Info.plist file.
Here are some of the references I used:
Find the sum of all the primes below N.
Brute-forced it again, but it still runs in less than 30 seconds (at least on my MacBook Pro). This one was simple using the Sieve of Eratosthenes from problem 7.
The sieve, collapsed because it’s the same as from problem 7:
; a
; http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
;1. Create a list of consecutive integers from two to n: (2, 3, 4, ..., n),
;2. Initially, let p equal 2, the first prime number,
;3. While enumerating all multiples of p starting from p2, strike them off from the original list,
;4. Find the first number remaining on the list after p (it's the next prime); let p equal this number,
;5. Repeat steps 3 and 4 until p2 is greater than n.
;6. All the remaining numbers in the list are prime.
; returns a lazy-sequence of the multiples of n
(defn sieve-of-eratosthenes
[n]
; step 1 Create a list of consecutive integers from two to n: (2, 3, 4, ..., n),
(defn sieve [rng p]
;(print "range: " rng "\n")
(
; this lambda used to perform the actual recursion
(fn [new-rng]
; step #5 Repeat steps 3 and 4 until p^2 is greater than n.
(if (<= (* p p) n)
; recurse
(sieve new-rng
; step # 4 Find the first number remaining on the list after p
; (it's the next prime); let p equal this number,
(first (filter #(> % p) new-rng))
)
; end recursion otherwise
new-rng
)
)
; this is an argument to the lambda above
; step #3 While enumerating all multiples of p starting from p2,
; strike them off from the original list,
(filter
#(or
(not= ; divisible by p
(rem % p)
0
)
; greater than p^2
(< % (* p p))
)
rng
)
)
)
(sieve
(range 2 n)
2 ; step #2 Initially, let p equal 2, the first prime number
)
)
The new code:
(defn problem10 [max-nbr]
(reduce + (sieve-of-eratosthenes max-nbr)) ; brute!
)
Find the greatest product of five consecutive digits in the 1000-digit number.
73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450
I decided to store the data in a text file. Not only would it save me from embedding the number in the source, but also give me an opportunity to try some simple file handling in Clojure. There is nothing super notable here, it’s another brute-force attempt.
; use to reduce a list into a string
(defn str-join [delim l]
(reduce (fn [res cur] (str res delim cur)) l)
)
; use to parse an integer out of a string
(defn parseInt [n]
(Integer/parseInt n)
)
(defn problem08 [filename digit-count]
; used to read the file and remove any newlines
(defn get-normalized-file-contents [filename]
(str-join "" (remove #(= % \newline) (slurp filename)))
)
; used to obtain the maximum product
(defn find-numbers [haystack max-number]
; compute the product of the first 5 numbers in haystack
(def tmp (reduce *
(map parseInt (map str (take digit-count haystack)))
))
; are there more digits to try? if so, recurse
(if (>= (count haystack) digit-count)
; work with the rest of the list
(find-numbers
(rest haystack)
; pass to this function the greater of the current
; maximum and the product of the first 5 digits in
; the current list
(if (> tmp max-number) tmp max-number)
)
; otherwise, return what we have determines to be the max number
max-number
)
)
(find-numbers
(get-normalized-file-contents filename)
-99
)
)
(problem08 "/pathtofile/data.txt" 5)
There exists exactly one Pythagorean triplet for which a + b + c = N. (N is known.)
Find the product abc.
This was a quick once since I just brute-forced it. I think there are some optimizations possible related to the idea that a^2 + b^2 < c^2.
; flattens a nested list
(defn flatten [x] (let [s? #(instance? clojure.lang.Sequential %)] (filter (complement s?) (tree-seq s? seq x))))
; returns the result of the pythagorean equation
(defn pythagorean-triplet-c [a b]
(. java.lang.Math
(sqrt
(+ (* a a)
(* b b)
)
)
)
)
; returns the c term of a pythagorean triple
; nil if natural term does not exist
(defn pythagorean-triplet-c-natural [a b]
(def result (pythagorean-triplet-c a b))
(if (zero? (- result (int result)))
(int result)
nil
)
)
(defn problem09 [sum]
(def res
(map
(fn [a]
(map
(fn [b]
(def c (pythagorean-triplet-c-natural a b))
(if (and (not (nil? c))
(= sum (+ a b c))
)
(* a b c)
nil
)
)
(range 100 sum)
)
)
(range 100 sum)
)
)
(first (distinct (filter #(not (nil? %)) (flatten res))))
)
What is the n-th prime number?
This was simple to solve using the Sieve created for the solution to problem #3. To make the program variable, we start with finding all primes less than 1000. If that is not enough to solve the problem, we double this “maximum” value, and search for all primes less than 2000. Rinse, repeat.
The old stuff:
; http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
(defn multiples
[n]
(lazy-cat
[1 n]
(map
(fn [a] (+ a n))
(rest (multiples n))
)
)
)
(defn sieve-of-eratosthenes
[n]
; step 1 Create a list of consecutive integers from two to n: (2, 3, 4, ..., n),
(defn sieve [rng p]
;(print "range: " rng "\n")
(
; this lambda used to perform the actual recursion
(fn [new-rng]
; step #5 Repeat steps 3 and 4 until p^2 is greater than n.
(if (<= (* p p) n)
; recurse
(sieve new-rng
; step # 4 Find the first number remaining on the list after p
; (it's the next prime); let p equal this number,
(first (filter #(> % p) new-rng))
)
; end recursion otherwise
new-rng
)
)
; this is an argument to the lambda above
; step #3 While enumerating all multiples of p starting from p2,
; strike them off from the original list,
(filter
#(or
(not= ; divisible by p
(rem % p)
0
)
; greater than p^2
(< % (* p p))
)
rng
)
)
)
(sieve
(range 2 n)
2 ; step #2 Initially, let p equal 2, the first prime number
)
)
The new stuff:
(defn problem07 [nth]
(defn try-find-nth-prime [primes max-number]
(if (< (count primes) nth)
; if the list of primes is not long enough,
; double the maximum search number
(try-find-nth-prime
(sieve-of-eratosthenes (* max-number 2))
(* max-number 2)
)
; otherwise, take the nth member of the list
(last (take nth primes))
)
)
(try-find-nth-prime (sieve-of-eratosthenes 1000) 1000)
)
I found out about a feature in SQL Server 2005 I didn’t know about (having come from a SQL Server 2000 shop). Cross Apply! It’s for when you want to feed the value of a table row into a function and join on the results. This is different than a cross join, because you cannot pass a table column value into a function when you do a cross join.
I whipped up a simple example. Let’s say we want the states that state with a certain letter (this is a trivial example because we could do this with a simple query as well).
select * from letters cross apply dbo.get_StateByFirstLetter ( letters.letter ) where letters.letter between 'L' and 'M' -- equivalent to select * from dbo.get_StateByFirstLetter ( 'L' ) UNION select * from dbo.get_StateByFirstLetter ( 'M' ) -- equivalent to (which makes the above trivial) select * from [states] where left(state_name, 1) between 'L' and 'M'
Full script to setup everything (pardon the sloppiness)
-- setup the states table
CREATE TABLE [states] (
state_name varchar(25),
state_abbr char(2)
)
INSERT INTO states VALUES ('Alaska', 'AK');
INSERT INTO states VALUES ('Alabama', 'AL');
INSERT INTO states VALUES ('American Samoa', 'AS');
INSERT INTO states VALUES ('Arizona', 'AZ');
INSERT INTO states VALUES ('Arkansas', 'AR');
INSERT INTO states VALUES ('California', 'CA');
INSERT INTO states VALUES ('Colorado', 'CO');
INSERT INTO states VALUES ('Connecticut', 'CT');
INSERT INTO states VALUES ('Delaware', 'DE');
INSERT INTO states VALUES ('District of Columbia', 'DC');
INSERT INTO states VALUES ('Florida', 'FL');
INSERT INTO states VALUES ('Georgia', 'GA');
INSERT INTO states VALUES ('Guam', 'GU');
INSERT INTO states VALUES ('Hawaii', 'HI');
INSERT INTO states VALUES ('Idaho', 'ID');
INSERT INTO states VALUES ('Illinois', 'IL');
INSERT INTO states VALUES ('Indiana', 'IN');
INSERT INTO states VALUES ('Iowa', 'IA');
INSERT INTO states VALUES ('Kansas', 'KS');
INSERT INTO states VALUES ('Kentucky', 'KY');
INSERT INTO states VALUES ('Louisiana', 'LA');
INSERT INTO states VALUES ('Maine', 'ME');
INSERT INTO states VALUES ('Marshall Islands', 'MH');
INSERT INTO states VALUES ('Maryland', 'MD');
INSERT INTO states VALUES ('Massachusetts', 'MA');
INSERT INTO states VALUES ('Michigan', 'MI');
INSERT INTO states VALUES ('Minnesota', 'MN');
INSERT INTO states VALUES ('Mississippi', 'MS');
INSERT INTO states VALUES ('Missouri', 'MO');
INSERT INTO states VALUES ('Montana', 'MT');
INSERT INTO states VALUES ('Nebraska', 'NE');
INSERT INTO states VALUES ('Nevada', 'NV');
INSERT INTO states VALUES ('New Hampshire', 'NH');
INSERT INTO states VALUES ('New Jersey', 'NJ');
INSERT INTO states VALUES ('New Mexico', 'NM');
INSERT INTO states VALUES ('New York', 'NY');
INSERT INTO states VALUES ('North Carolina', 'NC');
INSERT INTO states VALUES ('North Dakota', 'ND');
INSERT INTO states VALUES ('Ohio', 'OH');
INSERT INTO states VALUES ('Oklahoma', 'OK');
INSERT INTO states VALUES ('Oregon', 'OR');
INSERT INTO states VALUES ('Palau', 'PW');
INSERT INTO states VALUES ('Pennsylvania', 'PA');
INSERT INTO states VALUES ('Puerto Rico', 'PR');
INSERT INTO states VALUES ('Rhode Island', 'RI');
INSERT INTO states VALUES ('South Carolina', 'SC');
INSERT INTO states VALUES ('South Dakota', 'SD');
INSERT INTO states VALUES ('Tennessee', 'TN');
INSERT INTO states VALUES ('Texas', 'TX');
INSERT INTO states VALUES ('Utah', 'UT');
INSERT INTO states VALUES ('Vermont', 'VT');
INSERT INTO states VALUES ('Virgin Islands', 'VI');
INSERT INTO states VALUES ('Virginia', 'VA');
INSERT INTO states VALUES ('Washington', 'WA');
INSERT INTO states VALUES ('West Virginia', 'WV');
INSERT INTO states VALUES ('Wisconsin', 'WI');
INSERT INTO states VALUES ('Wyoming', 'WY');
GO
-- create the function which we are applying
create function dbo.get_StateByFirstLetter(@firstLetter char(1))
RETURNS @rtn TABLE (
state_name varchar(25),
state_abbr char(2)
)
AS
bEGIN
insert into @rtn
select state_name, state_abbr from states where left(state_name,1) = @firstLetter
return
END
GO
-- generate letters table
create table letters ( letter char(1) PRIMARY KEY )
with gen_letters as
(
select 65 as ascii_val
UNION ALL
SELECT ascii_val + 1 from gen_letters where ascii_val + 1 <= 90
)
insert into letters
select char(ascii_val) from gen_letters
-- get results by cross applying
select *
from letters
cross apply dbo.get_StateByFirstLetter ( letters.letter )
where letters.letter between 'L' and 'M'
-- equivalent to
select * from dbo.get_StateByFirstLetter ( 'L' )
UNION
select * from dbo.get_StateByFirstLetter ( 'M' )
And for good measure, using the WITH clause to generate a table of letters:
with gen_letters as ( select 65 as ascii_val UNION ALL SELECT ascii_val + 1 from gen_letters where ascii_val + 1 <= 90 ) insert into letters select char(ascii_val) from gen_letters
Find the largest palindrome made from the product of two 3-digit numbers
I couldn’t think of many optimizations for this problem, other than avoiding duplicates when calculating the products of numbers. That’s why I just brute-forced it. The only (barely) interesting thing I did here was to write a function which recognized palindromes. Thinking about the problem now, I suppose we can predict whether the first and last digits of a product will be the same by looking at the hundreds and tens digits of the factors.
; flattens a nested list
(defn flatten [x] (let [s? #(instance? clojure.lang.Sequential %)] (filter (complement s?) (tree-seq s? seq x))))
(defn palindrome? [s]
(if (or
; all 1 letter strings or
; nils are palindromes
(<= (count s) 1)
(nil? s)
)
true
(and
(= (first s) (last s))
(palindrome? (take (- (count s) 2) (rest s)))
)
)
)
(defn problem04 []
(def x (range 100 1000))
; sort, then take the last
(last (sort
; filter to only palindromes
(filter
#(palindrome? (str %))
; distinct products of all 3-digit numbers
(distinct (flatten
(map
(fn [n]
(map (fn [a] (* a n)) x))
x
)
))
)
))
)
What is the largest prime factor of the number N?
In previous problems, I was using a list of primes I got somewhere else. I figured it would be relevant to implement a prime-finding algorithm. I decided to go with simplicity, and implement the Sieve of Eratosthenes. It’s basically the algorithm you would come up with yourself if you wanted to figure out how to find all the prime numbers within a certain range.
Say we want to find all the prime numbers between 1 and 100. Start with the first prime number 2. Remove from the list all multiples of 2. Work with the next prime number 3. Remove from the list all multiples of 3. Continue until the square number you pick is greater than the last number in the list. This is because no number after that will have a multiple in the list.
For the part where we factor primes, I used the algorithm I came up with for problem 5, even though it is inelegant and has a kludgy fix.
Overall, I was happy with my solution. I think I am beginning to think more “functionally.”
; flattens a nested list
(defn flatten [x] (let [s? #(instance? clojure.lang.Sequential %)] (filter (complement s?) (tree-seq s? seq x))))
; http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
(defn sieve-of-eratosthenes
[n]
(defn sieve-of-eratosthenes-helper
[n]
; step 1 Create a list of consecutive integers from two to n: (2, 3, 4, ..., n),
(defn sieve [rng p]
(
; this lambda used to perform the actual recursion
(fn [new-rng]
; step #5 Repeat steps 3 and 4 until p^2 is greater than n.
(if (<= (* p p) n)
; recurse
(sieve new-rng
; step # 4 Find the first number remaining on the list after p
; (it's the next prime); let p equal this number,
(first (filter #(> % p) new-rng))
)
; end recursion otherwise
new-rng
)
)
; this is an argument to the lambda above
; step #3 While enumerating all multiples of p starting from p2,
; strike them off from the original list,
(filter
#(or
(not= ; divisible by p
(rem % p)
0
)
; greater than p^2
(< % (* p p))
)
rng
)
)
)
(sieve
(range 2 n)
2 ; step #2 Initially, let p equal 2, the first prime number
)
)
(sieve-of-eratosthenes-helper n)
)
(defn problem03 [n]
; begin by generating primes below the sqrt of the number.
; I'm just guessing this will be good enough. I started
; with a guess of 1000, which was woefully small
(def prime-cache (sieve-of-eratosthenes (. java.lang.Math (sqrt n))))
(defn prime?
[n]
(not (nil? (some #(= n %) prime-cache)))
)
; prime-factorization algorithm from solving previous
; project Euler problems such as #5
(defn prime-factorization
[n]
(defn pf-helper
[]
(def first-divisible
(first (filter
#(zero?
(rem n %)
)
(rest prime-cache))
)
)
(def result (/ n first-divisible))
(def new-result
(if (not (prime? result))
(prime-factorization result)
[result]
)
)
; i don't know why I need to set this again.
; the recursion seems to mutate a value that
; should not be in its scope
(def first-divisible
(first (filter
#(zero?
(rem n %)
)
(rest prime-cache))
)
)
(if (nil? new-result)
nil
(if (nil? first-divisible)
[new-result]
(flatten [new-result first-divisible])
)
)
)
(if (prime? n)
[n]
(pf-helper)
)
)
; factor!
(prime-factorization n)
)
