(ns euler
(:use clojure.test))
(defn
^{:test #(are [x y] (= x y) 9 (square 3) 81 (square 9) 100 (square 10))}
square
[x]
(* x x))
(defn
^{:test #(are [x y] (= x y) 385 (sum-of-squares 10) 55 (sum-of-squares 5))}
sum-of-squares
[n]
(/ (* (* n (+ n 1)) (+ 1 (* 2 n))) 6))
(defn
^{:test #(are [x y] (= x y) 3025 (square-of-sums 10) 225 (square-of-sums 5))}
square-of-sums
[n]
(square (/ (* n (+ n 1)) 2)))
(defn
^{:test #(is (= 2640 (problem-6 10)))}
problem-6
[n]
(- (square-of-sums n) (sum-of-squares n)))euler=> (run-tests)
Testing euler
Ran 4 tests containing 8 assertions.
0 failures, 0 errors.
{:type :summary, :test 4, :pass 8, :fail 0, :error 0}
euler=> (problem-6 100)
25164150
Permanent link to this article: http://stekodyne.com/?p=196
Just as a note. Pollard P1 can fail to factor some values. Also, the exponent function is not the fastest implementation.
(ns factoring
(:use clojure.test))
(defn
^{:test #(are [x y] (= x y) 9 (abs -9) 9 (abs 9) 0 (abs 0) 'a (abs 'a))}
abs [x]
(if (number? x)
(if (not (neg? x))
x
(- x))
x))
(defn
^{:test #(are [x y] (= x y) 17 (gcd 119 544) 17 (gcd 544 119) 119 (gcd 119 0))}
gcd [m n]
(let [m (abs m) n (abs n)]
(if (zero? n)
m
(if (< m n)
(recur n m)
(let [r (rem m n)]
(if (zero? r)
n
(recur n r)))))))
(defn
^{:test #(are [x y] (= x y) 9 (square 3) 81 (square 9) 100 (square 10))}
square
[x]
(* x x))
(defn
^{:test #(are [x y] (= x y) 9 (exponent 3 2) 81 (exponent 3 4) 27 (exponent 3 3))}
exponent
[b n]
(cond
(= n 0) 1
(even? n) (square (exponent b (/ n 2)))
:else (* b (exponent b (- n 1)))))
; http://www.connellybarnes.com/documents/factoring.pdf
(defn
^{:test #(is (= 445 (modular-exponentiation 4 13 497)))}
modular-exponentiation
[a b m]
(loop [answer 1 a (rem a m) k 0]
(if (> (exponent 2 k) b)
answer
(let [new-answer (rem (* answer a) m) new-a (rem (square a) m)]
(if (> (bit-and b (exponent 2 k)) 0)
(recur new-answer new-a (inc k))
(recur answer new-a (inc k)))))))
(defn
^{:test #(is (= (list 7 1885) (pollard-p1 13195)))}
pollard-p1
[value]
(loop [two-k-factorial (exponent 2 1) k 2]
(let [rk (gcd (- two-k-factorial 1) value)]
(if (and (not (= rk 1)) (not (= value rk)))
(list rk (/ value rk))
(recur (modular-exponentiation two-k-factorial (inc k) value) (inc k))))))factoring=> (run-tests)
Testing factoring
Ran 6 tests containing 15 assertions.
0 failures, 0 errors.
{:type :summary, :test 6, :pass 15, :fail 0, :error 0}
Permanent link to this article: http://stekodyne.com/?p=192
; Site - http://projecteuler.net/problem=4
(ns euler
(:use clojure.test))
(defn
^{:test #(is (= true (palindrome? 13131)))}
palindrome?
[n]
(let [reverse (loop [remaining (int (/ n 10)) digit (rem n 10) accumulator 0 ]
(if (< remaining 1 )
(+ digit (* accumulator 10))
(recur
(int (/ remaining 10))
(rem remaining 10)
(+ digit (* accumulator 10)))))]
(if (= n reverse)
true
false)))
(defn
^{:test #(is (= 9009 (problem-4 10 100)))}
problem-4
[start end]
(reduce
(fn [x y] (if (> x y) x y))
(for [x (range start end) y (range start end)]
(let [answer (* x y)]
(if (palindrome? answer) answer 0)))))euler=> (run-tests)
Testing euler
Ran 2 tests containing 2 assertions.
0 failures, 0 errors.
{:type :summary, :test 2, :pass 2, :fail 0, :error 0}
euler=> (problem-4 100 1000)
906609
Permanent link to this article: http://stekodyne.com/?p=186
Categories:
Clojure
February 16, 2012
(defn
^{:test #(is (= true (palindrome? 13131)))}
palindrome?
[n]
(let [reverse (loop [remaining (int (/ n 10)) digit (rem n 10) accumulator 0 ]
(if (< remaining 1 )
(+ digit (* accumulator 10))
(recur
(int (/ remaining 10))
(rem remaining 10)
(+ digit (* accumulator 10)))))]
(if (= n reverse)
true
false)))
Permanent link to this article: http://stekodyne.com/?p=182
(use 'clojure.contrib.sql 'incanter.core)
(def db {:classname "oracle.jdbc.OracleDriver"
:subprotocol "oracle:thin"
:subname "@host:port:sid"
:user ""
:password "" })
(with-data
(dataset ["Fibonacci" "X"]
(with-connection db
(with-query-results
rs
["SELECT x, ((1 / SQRT (5)) * POWER (((1 + SQRT (5)) / 2), x))
- ((1 / SQRT (5)) * POWER (((1 - SQRT (5)) / 2), x)) fibonacci
FROM ( SELECT LEVEL x
FROM DUAL
CONNECT BY LEVEL < 20)"]
(vec
(map #(vector (:fibonacci %) (:x %)) rs)))))
(view (xy-plot :X :Fibonacci)))
Permanent link to this article: http://stekodyne.com/?p=175
I took the easy way out by using the lazy-seqs primes.
; Site - http://projecteuler.net/problem=3
(ns euler
(:use clojure.test clojure.contrib.math clojure.contrib.lazy-seqs))
(defn
^{:test #(is (= 29 (problem-3 13195)))}
problem-3
[n]
(last
(filter
#(= 0 (rem n %))
(take-while
#(< % (+ (sqrt n) 1))
primes))))euler=> (run-tests)
Testing euler
Ran 1 tests containing 1 assertions.
0 failures, 0 errors.
{:type :summary, :test 1, :pass 1, :fail 0, :error 0}
euler=> (problem-3 600851475143)
6857
Permanent link to this article: http://stekodyne.com/?p=169
; Site - http://projecteuler.net/problem=2
(ns euler
(:use clojure.test))
(defn
^{:test #(is (= (list 0 1 1 2 3 5 8 13 21 34) (take 10 (fibonacci))))}
fibonacci
([]
(concat [0 1] (fibonacci 0 1)))
([current next]
(let [n (+ current next)]
(lazy-seq
(cons n (fibonacci next n))))))
(defn
^{:test #(is (= 88 (problem-2 (fn [x] (not (nil? x))) 10)))}
problem-2
[predicate max]
(reduce + (filter predicate (take max (fibonacci)))))euler=> (problem-2 even? 34)
4613732
Permanent link to this article: http://stekodyne.com/?p=163
Categories:
SQL
January 26, 2012
Here is a little SQL snippet for generating a the Fibonacci Sequence using:
SELECT x, ((1 / SQRT (5)) * POWER (((1 + SQRT (5)) / 2), x))
- ((1 / SQRT (5)) * POWER (((1 - SQRT (5)) / 2), x)) fibonacci
FROM ( SELECT LEVEL x
FROM DUAL
CONNECT BY LEVEL < 100);
Permanent link to this article: http://stekodyne.com/?p=130
I have finally got around to reading The Art of Computer Programming Vol. 1 by Donald Knuth, and in the effort to better understand the algorithms defined within I plan on implementing them here in Clojure. I know that abs can be found in the contrib library, but so can gcd. The gcd algorithm hold mostly true to the steps that were presented in the book. The only real changes were taking the abs values of negative numbers and checks for working with integers.
Here is Algorithm 1.1E
(ns euclid
(:use clojure.test))
(defn
^{:test #(are [x y] (= x y) 9 (abs -9) 9 (abs 9) 0 (abs 0) 'a (abs 'a))
:doc "Returns the absolute value for an integer, else it will just return
what was passing in to the function."}
abs [x]
(if (number? x)
(if (not (neg? x))
x
(- x))
x))
(defn
^{:test #(are [x y] (= x y) 17 (gcd 119 544) 17 (gcd 544 119) 119 (gcd 119 0))
:doc "Returns the GCD for two given integers."}
gcd [m n]
(let [m (abs m) n (abs n)]
(if (zero? n)
m
(if (< m n)
(recur n m)
(let [r (rem m n)]
(if (zero? r)
n
(recur n r)))))))euclid=> (run-tests)
Testing euclid
Ran 2 tests containing 7 assertions.
0 failures, 0 errors.
{:type :summary, :test 2, :pass 7, :fail 0, :error 0}The following version is a modified gcd to count the steps of E1 as well as finding the gcd.
(defn
^{:test #(are
[x y]
(= x y)
(list 5 1) (gcd-with-e1-steps 5 5 0)
(list 1 4) (gcd-with-e1-steps 3 5 0)
(list 1 2) (gcd-with-e1-steps 1 5 0))
:doc "Returns the GCD for two given integers and the number of E1 steps."}
gcd-with-e1-steps [m n i]
(let [m (abs m) n (abs n)]
(if (zero? n)
(list m i)
(if (< m n)
(recur n m (inc i))
(let [r (rem m n) i (inc i)]
(if (zero? r)
(list n i)
(recur n r i)))))))euclid=> (run-tests)
Testing euclid
Ran 3 tests containing 10 assertions.
0 failures, 0 errors.
{:type :summary, :test 3, :pass 10, :fail 0, :error 0}So now to anwser problem 6 on page 9 would be something like the follow.
euclid=> (let [steps (map #(last (gcd-with-e1-steps % 5 0)) (range 1 6))]
(/
(apply + steps)
(count steps)
1.0))
2.6
Permanent link to this article: http://stekodyne.com/?p=110
Categories:
PL/SQL
November 30, 2011
This is just a simple test to see the feasibility of generating a PDF from PL/SQL. This will create a very simple single page PDF with a red border and “Hello World” in grey. It also assumes that one knows what to pass in to various functions. This knowledge would be derived from the PDF Reference documentation found on Adobe’s site.
NOTE – This is by no way consided to be even remotely production ready. It was just created to see what it would take, and I thought I would share my notes.
DECLARE
TYPE pdf_objects IS TABLE OF VARCHAR2 (32767);
objects pdf_objects := pdf_objects ();
crlf VARCHAR2 (2) := CHR (13) || CHR (10);
text VARCHAR2 (120)
:= 'BT'
|| crlf
|| '/F1 24 Tf'
|| crlf
|| '100 100 Td'
|| crlf
|| '0 Tr'
|| crlf
|| '0.5 g'
|| crlf
|| '( Hello World ) Tj'
|| crlf
|| 'ET';
frame VARCHAR2 (1000)
:= '1.0 0.0 0.0 RG'
|| crlf
|| '1.0 1.0 1.0 rg'
|| crlf
|| '30 30 552 732 re'
|| crlf
|| 'B';
-----------------------------------------------------------------------------
-- Takes in a PDF'ed string and creates an string that will represent a
-- PDF object, that will need to have an object index (<<XX>>) assigned.
-----------------------------------------------------------------------------
FUNCTION create_object (content IN VARCHAR2)
RETURN VARCHAR2
AS
BEGIN
RETURN '<<XX>> 0 obj' || crlf || content || crlf || 'endobj';
END create_object;
-----------------------------------------------------------------------------
-- Takes a string that represents a PDF object and a nested tables of objects
-- and creates a new nested table that will have the new object added with
-- the object index assigned.
-----------------------------------------------------------------------------
FUNCTION add_object (object IN VARCHAR2, objects IN pdf_objects)
RETURN pdf_objects
AS
l_objects pdf_objects;
BEGIN
l_objects := objects;
l_objects.EXTEND (1);
l_objects (l_objects.LAST)
:= REPLACE (object, '<<XX>>', (l_objects.LAST - 1));
RETURN l_objects;
END add_object;
-----------------------------------------------------------------------------
-- Wraps a string as a PDF Dictionary.
-----------------------------------------------------------------------------
FUNCTION create_dictionary (content IN VARCHAR2)
RETURN VARCHAR2
AS
BEGIN
RETURN '<< ' || content || ' >>';
END create_dictionary;
-----------------------------------------------------------------------------
-- Wraps a string as a PDF stream.
-----------------------------------------------------------------------------
FUNCTION create_stream (content IN VARCHAR2)
RETURN VARCHAR2
AS
BEGIN
RETURN create_dictionary ('/Length ' || LENGTH (content))
|| crlf
|| 'stream '
|| crlf
|| content
|| crlf
|| 'endstream';
END create_stream;
-----------------------------------------------------------------------------
-- Adds some static text to the objects table to be later added to the PDF.
-- This does not wrap the text as a PDF object.
-----------------------------------------------------------------------------
FUNCTION add_meta (object IN VARCHAR2, objects IN pdf_objects)
RETURN pdf_objects
AS
l_objects pdf_objects;
BEGIN
l_objects := objects;
l_objects.EXTEND (1);
l_objects (l_objects.LAST) := object;
RETURN l_objects;
END add_meta;
-----------------------------------------------------------------------------
-- Creates a simple PDF header that takes in the PDF version, for example
-- 1.4, 1.7, ...
-----------------------------------------------------------------------------
FUNCTION create_header (version IN FLOAT)
RETURN VARCHAR2
AS
BEGIN
RETURN '%PDF-' || version;
END create_header;
-----------------------------------------------------------------------------
-- Creates the PDF trailer that gives the number of objects in the PDF as
-- well as a pointer to the catalog object.
-----------------------------------------------------------------------------
FUNCTION create_trailer (objects IN pdf_objects)
RETURN VARCHAR2
AS
l_content VARCHAR2 (32767) := 'trailer' || crlf;
l_size NUMBER := 0;
BEGIN
l_content
:= l_content
|| create_dictionary ( '/Size '
|| (objects.COUNT () - 1)
|| ' /Root 1 0 R' )
|| crlf;
FOR i IN objects.FIRST .. objects.LAST
LOOP
EXIT WHEN i = objects.COUNT ();
l_size := l_size + LENGTH (objects (i));
END LOOP;
l_content := l_content || 'startxref' || crlf || l_size || crlf || '%%EOF';
RETURN l_content;
END create_trailer;
-----------------------------------------------------------------------------
-- Creates a xref table for the PDF that has the byte offset to the PDF
-- objects in the file.
-----------------------------------------------------------------------------
FUNCTION create_xref (objects IN pdf_objects)
RETURN VARCHAR2
AS
offset NUMBER := 0;
xref VARCHAR2 (32767) := '';
BEGIN
xref := 'xref' || crlf;
xref := xref || '0 ' || objects.COUNT () || crlf;
xref := xref || LPAD ('0', 10, '0') || ' 65535 f' || crlf;
FOR i IN objects.FIRST .. objects.LAST
LOOP
IF i > 1
THEN
xref
:= xref
|| LPAD (offset, 10, '0')
|| ' '
|| LPAD ('0', 5, '0')
|| ' n';
IF i <> objects.LAST
THEN
xref := xref || crlf;
END IF;
END IF;
offset := offset + LENGTH (objects (i));
END LOOP;
RETURN xref;
END create_xref;
-----------------------------------------------------------------------------
-- Spit out a string that represents the PDF document.
-----------------------------------------------------------------------------
FUNCTION dump_document (objects IN pdf_objects)
RETURN VARCHAR2
AS
output VARCHAR2 (32767) := '';
BEGIN
FOR i IN objects.FIRST .. objects.LAST
LOOP
output := output || objects (i) || crlf;
END LOOP;
RETURN output;
END dump_document;
--------------------------------------------------------------------------------
--
--------------------------------------------------------------------------------
BEGIN
-- Create the header of the PDF passing in the PDF version to the used.
objects := add_meta (create_header (1.4), objects);
-- Create the Catalog PDF object that points to the Outlines and Pages object.
objects := add_object (
create_object (
create_dictionary (
'/Type /Catalog /Outlines 2 0 R /Pages 3 0 R')), objects);
-- Create the Outlines object.
objects := add_object (
create_object (
create_dictionary ('/Type Outlines /Count 0')), objects);
-- Create the Pages object that points to the Page objects.
-- In this case, it only has one page.
objects :=
add_object (
create_object (
create_dictionary ('/Type /Pages /Kids [ 4 0 R ] /Count 1')), objects);
-- Create the Page object. This will include the page size (i.e. the MediaBox),
-- as well as pointing to the Contents of the page.
objects :=
add_object (
create_object (
create_dictionary ( '/Type /Page'
|| '/Parent 3 0 RPage'
|| '/MediaBox [ 0 0 612 792 ]Page'
|| '/Contents 5 0 RPage'
|| '/Resources '
|| create_dictionary ( '/ProcSet 6 0 R'
|| ' /Font '
|| create_dictionary (
'/F1 7 0 R')))),
objects);
-- Create a PDF Stream object that draws a frame on the page along
-- with some text.
objects := add_object (
create_object (
create_stream (frame || crlf || text)), objects);
-- Still need to look to see what exactly this line does.
objects := add_object (
create_object (
create_dictionary ('[ /PDF /Text ]')), objects);
-- Set up the Font object for the text stream.
objects :=
add_object (
create_object (
create_dictionary ( '/Type /FontPage'
|| '/Subtype /Type1Page'
|| '/Name /F1Page'
|| '/BaseFont /HelveticaPage'
|| '/Encoding /MacRomanEncoding')),
objects);
-- Create the xref table for the document.
objects := add_meta (create_xref (objects), objects);
-- Create the trailer.
objects := add_meta (create_trailer (objects), objects);
-- Print out the PDF for testing.
DBMS_OUTPUT.put_line (dump_document (objects));
END;
Permanent link to this article: http://stekodyne.com/?p=94