Have you ever seen the rain?

Euler #47

Euler #46

#!/usr/bin/env python

from libeuler import is_prime, primes
from math import sqrt

if __name__ == '__main__':
    P = primes(100000)
    n = 1
    while True:
        found = False
        for p in P[1:]:
            a2 = n - 0.5*(p - 1)
            if a2 < 0:
                break
            
            if sqrt(a2) == float(int(sqrt(a2))):
                print "%d -> %d + 2*%d^2" % (2*n + 1, p, sqrt(a2))
                found = True
                n += 1
                break

        if not found and not (2*n+1) in P:
            print 2*n + 1
            break

Euler #44

Euler #43

Euler #42

#!/usr/bin/env python

def word_value(w):
    return sum(map(lambda x: ord(x) - ord('A') + 1, w))

def triangle_numbers(l):
    res = []
    n = 1
    t = 1
    while t < l:
        t = n*(n+1)/2
        res += [t]
        n += 1
    return res

if __name__ == '__main__':
    f = open('words.txt', 'r')
    words = f.read()
    f.close()
    words = map(word_value, map(lambda x: x[1:-1], words.split(',')))
    triangles = triangle_numbers(max(words))
    n = 0
    for w in words:
        if w in triangles: n += 1
    print n
    

Euler #41

#!/usr/bin/env python

from libeuler import is_prime, pandigital

if __name__ == '__main__':
    res = []
    for i in xrange(1, 10):
        res += filter(lambda x: is_prime(x), pandigital(i))
    print max(res)

Euler #40

#!/usr/bin/env python

def create_fraction():
    f = ''
    cnt = 1
    while len(f) < 1000000:
        f += str(cnt)
        cnt += 1
    return f

if __name__ == '__main__':
    fraction = create_fraction()
    d1 = int(fraction[0])
    d10 = int(fraction[9])
    d100 = int(fraction[99])
    d1000 = int(fraction[999])
    d10000 = int(fraction[9999])
    d100000 = int(fraction[99999])
    d1000000 = int(fraction[999999])
    print d1 * d10 * d100 * d1000 * d10000 * d100000 * d1000000

Well, obviously we can use arrays and powers of 10

Euler #39

#!/usr/bin/env python

from math import sqrt

def n_triangles(p):
    res = []
    for a in xrange(1, p):
        for b in xrange(a, p):
            c = sqrt(a*a + b*b)
            if a + b + c == p:
                res += [(a, b, c)]
    return res

for p in xrange(3, 1000):
    t = n_triangles(p)
    if len(t) > 0:
        print p, len(t), t

Euler #38

#!/usr/bin/env python

from libeuler import is_pandigital

def concatenated_product(n, l):
    return reduce(lambda x, y: str(x) + str(y), map(lambda x: x*n, l), '')

if __name__ == '__main__':
    r = []
    n = 1
    m = 9
    while True:
        p = concatenated_product(n, range(1, m+1))
        print "%d -> %s" % (n, p), range(1, m+1)
        if len(p) > 9:
            m -= 1
            if m < 2:
                break
            continue
        if is_pandigital(int(p)):
            r += [int(p)]
        n += 1
    print max(r)

Euler #36

#!/usr/bin/env python

def is_palyndrome(s): return (s == reduce(lambda x,y: x+y, reversed(s), ''))

def right_number(n):
    c1 = is_palyndrome(str(n))
    c2 = is_palyndrome(bin(n)[2:])
    if c1 and c2:
        return n
    else:
        return 0
    
if __name__ == '__main__':
    print reduce(lambda x, y: x+y, map(right_number, range(1000000)), 0) 

Generating badges for upcoming seminar ;)

#!/usr/bin/env python

import sys
from csv import reader
from mako.template import Template

def help(script_name):
    print "Usage: %s <csv-file> <badge-template>" % script_name

def write_page(template, num, person):
    f = open('badges%05d.svg' % num, 'w')
    f.write(template.render(**person))
    f.close()

def process_file(csv_file, template_file):
    rows = reader(open(csv_file, "rb"))
    template = Template(filename=template_file)
    person_cnt = 0
    pages_cnt = 1
    person = dict()
    for row in rows:
        person['name%d' % person_cnt] = row[0].strip()
        person['surname%d' % person_cnt] = row[1].strip()
        person['organization%d' % person_cnt] = row[2].strip()
        person_cnt += 1
        if person_cnt == 4:
            write_page(template, pages_cnt, person)
            person_cnt = 0
            pages_cnt += 1
    if person_cnt != 0:
        write_page(template, pages_cnt, person)

if __name__ == '__main__':
    if len(sys.argv) < 3:
        help()
    else:
        process_file(sys.argv[1], sys.argv[2])

FOP & Jython

#!/usr/bin/env jython

import sys

from java.io import File, FileOutputStream, BufferedOutputStream

# JAXP
from javax.xml.transform import Transformer, TransformerFactory, Source, Result
from javax.xml.transform.stream import StreamSource
from javax.xml.transform.sax import SAXResult

# FOP
from org.apache.fop.apps import FOUserAgent, Fop, FopFactory, MimeConstants

xmlfile = File("projectteam.xml")
xsltfile = File("projectteam2fo.xsl")
pdffile = File("out.pdf")

fopFactory = FopFactory.newInstance()
foUserAgent = fopFactory.newFOUserAgent()

out = FileOutputStream(pdffile)
out = BufferedOutputStream(out)

fop = fopFactory.newFop(MimeConstants.MIME_PDF, foUserAgent, out)
factory = TransformerFactory.newInstance()
transformer = factory.newTransformer(StreamSource(xsltfile))
transformer.setParameter("versionParam", "2.0");
src = StreamSource(xmlfile)
res = SAXResult(fop.getDefaultHandler())
transformer.transform(src, res)

out.close()

Quite funny, but there's the bug in Jython ClassLoader so we have to place all FOP jars in CLASSPATH instead of sys.path.append(...) way.

Project Euler #35

let is_prime n =
  if n < 0 then
    false
  else
    let lim = int_of_float (sqrt (float_of_int n)) in
    let rec check_mod i l =
      if i > l then
        true
      else
        if n mod i = 0 then
          false
        else
          true && (check_mod (succ i) l)
    in
    check_mod 2 lim;;

let primes n =
  let rec inner_primes i =
    if i > n then
      []
    else
      if is_prime i then
        [i] @ inner_primes (succ i)
      else
        inner_primes (succ i)
  in
  inner_primes 2;;

let circulations n = 
  let rec circulate str =
    let str_len = String.length str in
    if str_len = 1 then
      [int_of_string n]
    else
      let variant = (String.sub str 1 (str_len - 1)) ^ (String.sub str 0 1) in
      if variant = n then
        [(int_of_string variant)]
      else
        [(int_of_string variant)] @ (circulate variant)
  in
  circulate n;;

(*
let is_circular n primes = 
  let number_string = string_of_int n in
  let variants = circulations number_string in
  List.fold_left 

    (&&) 

    true 

    (List.map 

      (fun x -> List.exists (fun y -> (x = y)) primes) 

      variants);;
*)

let is_circular n =
  let number_string = string_of_int n in
  let variants = circulations number_string in
  List.fold_left (&&) true (List.map (is_prime) variants);;

let primes_till_1e6 = primes 1000000;;
let test_primes = primes_till_1e6;;

Printf.printf "%d\n" 
    (List.fold_left 
       (+) 
       0 
       (List.map 
         (fun x -> if (is_circular x) then 1 else 0 ) 
         test_primes));;

Strange thing: List.exists is quite slow, so when I switched from using List.exists (commented out) to just plain is_prime in is_circular it became possible to get result in a minute. Or maybe I just can't use List.exists properly.

Project Euler #27

#load "nums.cma"

open Big_int;;

type triple = { a: big_int; 
                b: big_int; 
                len: big_int };;

let is_prime n =
  if lt_big_int n zero_big_int then
    false
  else
    let lim = sqrt_big_int n in
    let rec check_mod i l =
      if gt_big_int i  l then
        true
      else
        if eq_big_int (mod_big_int n i) zero_big_int then
          false
        else
          true && (check_mod (succ_big_int i) l)
    in
    check_mod (big_int_of_int 2) lim;;
      
let primes n =
  let rec inner_primes i =
    if gt_big_int i n then
      []
    else
      if is_prime i then
        [i] @ inner_primes (succ_big_int i)
      else
        inner_primes (succ_big_int i)
  in
  inner_primes (big_int_of_int 2);;

let make_form a b = 
  fun n -> 
    add_big_int 
      (mult_big_int n n) 
      (add_big_int (mult_big_int a n) b);;

let sequence_length f =
  let rec advance_sequence n =
    if not (is_prime (f n)) then
      zero_big_int
    else
      add_big_int 
        unit_big_int (advance_sequence (succ_big_int n))
  in
  advance_sequence (big_int_of_int 0);;

let triple_max a b =
  if gt_big_int a.len b.len then
    a
  else
    b;;

let find_longest_sequence i1 i2 n =
  let rec make_lengths_list i =
    if gt_big_int i i2 then
      []
    else
      [{ a=i; b=n; len=sequence_length (make_form i n); }] @ 
      (make_lengths_list (succ_big_int i))
  in
  List.fold_left (triple_max) 
    { a=zero_big_int; b=zero_big_int; len=zero_big_int; } 
    (make_lengths_list i1);;

let bs = primes (big_int_of_int 1000);;
let a1 = big_int_of_string "-999";;
let a2 = big_int_of_string "999";;

let max_ab = List.fold_left (triple_max) 
    { a=zero_big_int; b=zero_big_int; len=zero_big_int; } 
    (List.map (find_longest_sequence a1 a2) bs);;

Printf.printf "%s\n" 
    (string_of_big_int (mult_big_int max_ab.a max_ab.b));;

Project Euler #29

#load "nums.cma";;

open Big_int;;

let rec generate_combinations a1 a2 b1 b2 =
  let rec generate_single_number a b lim =
    if gt_big_int b lim then
      []
    else
      [power_big_int_positive_big_int a b] @ 
      generate_single_number 
        a (succ_big_int b) lim
  in
  if gt_big_int a1 a2 then
    []
  else
    (generate_single_number 
       a1 b1 b2) @ 
    (generate_combinations 
       (succ_big_int a1) a2 b1 b2);;

let rec uniq lst = match lst with
  [] -> []
| hd :: tl when List.exists (fun x -> eq_big_int x hd) tl -> uniq tl
| hd :: tl -> [hd] @ uniq tl;;

let a1 = big_int_of_int 2;;
let a2 = big_int_of_int 100;;
let b1 = big_int_of_int 2;;
let b2 = big_int_of_int 100;;
Printf.printf "%d\n" 
    (List.length 
       (uniq 
   (generate_combinations a1 a2 b1 b2)));;

Quick to come up but not so fast uniq function.

Project Euler #28

let make_spiral n =
  if n mod 2 = 0 then
    raise (Invalid_argument "Size should be odd");
  let res = Array.make_matrix n n 0 in
  let last_value = n * n in
  let current_value = ref 1 in
  let i = ref (n / 2) in
  let j = ref (n / 2) in
  let shift = ref 1 in
  let delta = ref 1 in
  res.(!i).(!j) <- !current_value;
  while !current_value < last_value do
    for k = 1 to !shift do
      if !current_value < last_value then
        begin
          j := !j + !delta;
          current_value := !current_value + 1;
          res.(!i).(!j) <- !current_value;
        end;
    done;
    for k = 1 to !shift do
      if !current_value < last_value then
        begin
          i := !i + !delta;
          current_value := !current_value + 1;
          res.(!i).(!j) <- !current_value;
        end;
    done;
    delta := - !delta;
    shift := !shift + 1;
  done;
  res;;

let sum_diagonals arr = 
  let size = Array.length arr in
  let sum = ref 0 in
  for i = 0 to size - 1 do
    sum := !sum + arr.(i).(i) + arr.(i).(size - 1 - i)
  done;
  !sum - 1;;
    
Printf.printf "%d\n" (sum_diagonals (make_spiral 1001));;

Very bad OCaml ;)

Project Euler #23

(* generates array with values [1..n] *)
let rec range_array n =
  if n == 1 then
    [| n |]
  else
    Array.append (range_array (n - 1)) [| n |];;

(* calculates sum of proper divisors of given number *)
let sum_of_proper_divisors n =
  let limit = n / 2 in
  let rec sum_divisors k l =
    if k > l then
      0
    else
      if n mod k = 0 then
        k + sum_divisors (k + 1) l
      else
        sum_divisors (k + 1) l
  in
  if n = 1 then
    1
  else
    sum_divisors 1 limit;;

(* checks whether given number is abundant*)
let is_abundant n =
  n < sum_of_proper_divisors n;;

(* generates array of abundant number less than given number *)
let find_abundant_numbers n =
  let rec gen_numbers k =
    if k = n then
      [||]
    else
      if is_abundant k then
        Array.append [| k |] (gen_numbers (k + 1))
      else
        gen_numbers (k + 1)
  in
  gen_numbers 12;;

let binary_search (data:'a array) elem =
  let rec iter a b =
    if a = b then -1
    else
      let median = a + (b - a)/2 in
      match data.(median) with
      | value when value = elem -> median
      | value when value < elem -> iter (median + 1) b
      | _                       -> iter a median
  in
  iter 0 (Array.length data);;

let make_possible_sums a =
  let len = (Array.length a) - 1 in
  let res = Array.make_matrix (len + 1) (len + 1) 0 in
  for i = 0 to len do
    for j = i to len do
      res.(i).(j) <- a.(i) + a.(j)
    done
  done;
  res;;

(* sets all elements of a found in s to 0 *)
let refine_array a s =
  let to_delete = Array.make (Array.length a) false in
  let l1 = Array.length s in
  let l2 = Array.length s.(0) in
  for i = 0 to l1 - 1 do
    for j = 0 to l2 - 1 do
      let idx = binary_search a s.(i).(j) in
      if idx != -1 then
        to_delete.(idx) <- true
    done
  done;
  for i = 0 to (Array.length to_delete) - 1 do
    if to_delete.(i) then
      a.(i) <- 0
  done;;

let all_numbers = range_array 28123;;
let abundant_numbers_sums = make_possible_sums (find_abundant_numbers 28123);;
refine_array all_numbers abundant_numbers_sums;;

Printf.printf "%d\n" (Array.fold_left (+) 0 all_numbers);;

Straightforward and very slow but correct solution ;)

Project Euler #25

Quite obvious

Project Euler #21

let proper_divisors_sum n =
  let limit = n / 2 in
  let rec proper_divisors_list n k =
    if k > limit then
      []
    else
      if n mod k = 0 then
        [k] @ (proper_divisors_list n (k + 1))
      else
        proper_divisors_list n (k + 1)
  in
  List.fold_left (+) 0 (proper_divisors_list n 1);;

let amicable_numbers_sum n =
  let rec amicable_numbers k =
    if k > n then
      []
    else
      let b = proper_divisors_sum k in
      let a = proper_divisors_sum b in
      if (a != b) && (a = k) then
        [k] @ (amicable_numbers (k + 1))
      else
        amicable_numbers (k + 1)
  in
  List.fold_left (+) 0 (amicable_numbers 2);;

Printf.printf "%d\n" (amicable_numbers_sum 10000);;

Quite straightforward and surely using lists ;) Actually we can sum without intermediate lists.

Project Euler #24

(* swaps elements of indexes i and j in array a*)
let swap a i j =
  let t = a.(i) in
  a.(i) <- a.(j); a.(j) <- t;;

(* reverses part of array a from index i to the end of array*)
let reverse a i =
  let l = (Array.length a) - 1 in
  for k = 0 to (l - i)/2 do
    swap a (i + k) (l - k)
  done;;

(* generates next permutation of array *)
let make_next_permutation a =
  let j = ref 0 in
  let l = ref 0 in
  for i = 0 to (Array.length a) - 2 do
    if a.(i) < a.(i+1) then
      j.contents <- i
  done;
  for i = 0 to (Array.length a) - 1 do
    if a.(!j) < a.(i) then
      l.contents <- i
  done;
  swap a !j !l; 
  reverse a (!j+1);;

let make_permutations a =
  let t = ref 1 in
  while !t < 1000000 do
    make_next_permutation a; 
    t := (!t + 1); 
  done;;

let t = [| 0; 1; 2; 3; 4; 5; 6; 7; 8; 9 |];;
make_permutations t;;
Array.iter (Printf.printf "%d") t;;
Printf.printf "\n";;

http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations
Весьма императивное решение, с использованием ссылок.

Project Euler #22

#load "str.cma";;

let char_value c = (int_of_char c) - (int_of_char 'A') + 1;;

let word_value s =
  let word_length = String.length s in
  let rec sum_letters s n =
    if n == 0 then
      char_value s.[0]
    else
      (char_value s.[n]) + (sum_letters s (n-1))
  in
  sum_letters s (word_length - 1);;

let line_stream_of_channel channel =
  Stream.from
    (fun _ -> 
      try Some (input_line channel) 
      with End_of_file -> None);;

let lines datafile =
  let xs = ref [] in
  Stream.iter
    (fun x -> xs := x :: !xs)
    (line_stream_of_channel (open_in datafile));
  List.rev !xs;;

let content = List.sort (String.compare)
    (List.map 
       (fun x -> 
     let l = String.length x 
     in 
     String.sub x 1 (l - 2)) 
       (List.concat 
      (List.map
         (Str.split 
        (Str.regexp_string ","))
             (lines (Sys.argv.(1))))));;

let rec sum l n = match l with
  h :: t -> ((word_value h) * n) + (sum t (n+1))
| [] -> 0;;
       
Printf.printf "%d\n" (sum content 1)

Project Euler #18 and #67

#load "str.cma";;
#load "nums.cma";;

let array_of_string delim s = 
  Array.of_list 
    (List.map 
       (int_of_string) 
       (Str.split (Str.regexp_string delim) s));;

let line_stream_of_channel channel =
  Stream.from
    (fun _ -> 
      try Some (input_line channel) 
      with End_of_file -> None);;

let lines datafile =
  let xs = ref [] in
  Stream.iter
    (fun x -> xs := x :: !xs)
    (line_stream_of_channel (open_in datafile));
  List.rev !xs;;

let content = Array.of_list
    (List.map 
       (array_of_string " ") 
       (lines (Sys.argv.(1))));;

(* r1 - long array, r2 - short array *)
let max_row r1 r2 = 
  let lr2 = Array.length r2 in
  let sum = Array.make lr2 0 in
  for i = 0 to lr2 - 1 do
    sum.(i) <- max (r1.(i) + r2.(i)) (r1.(i+1) + r2.(i))
  done;
  sum;;

let calc_sum tr =
  let tl = Array.length tr in
  for n = tl - 1 downto 1 do
    tr.(n-1) <- (max_row tr.(n) tr.(n-1))
  done;
  tr.(0).(0);;
    
Printf.printf "%s\n" (string_of_int (calc_sum content))

Project Euler #20

#load "nums.cma";;

open Big_int;;

let rec factorial n =
  if eq_big_int n unit_big_int then
    unit_big_int
  else
    mult_big_int n (factorial (pred_big_int n));;

let int_list_of_string s =
  let len = String.length s in
  let rec chars_of_string s n =
    if n == 0 then
      [int_of_char s.[0] - int_of_char '0']
    else
      (chars_of_string s (n - 1)) @ [(int_of_char s.[n]) - int_of_char '0']
  in
  chars_of_string s (len - 1);;
  
Printf.printf "%d\n" 
    (List.fold_left 
       (+) 
       0 
       (int_list_of_string 
      (string_of_big_int 
         (factorial 
        (big_int_of_int 100)))));;

Project Euler #6

#load "nums.cma"

open Big_int;;

let rec sum_of_squares n = 
  if eq_big_int n unit_big_int then
    unit_big_int
  else
    add_big_int (square_big_int n) (sum_of_squares (pred_big_int n));;

let square_of_sum n =
  let rec sum n =
    if eq_big_int n unit_big_int then
      unit_big_int
    else
      add_big_int n (sum (pred_big_int n))
  in
  square_big_int (sum n);;

let s1 = sum_of_squares (big_int_of_int 100);;
let s2 = square_of_sum (big_int_of_int 100);;

let result = sub_big_int s2 s1;;

Printf.printf "%s\n" (string_of_big_int result);;

Сначала написал с использованием встроенных int, перепутал местами суммы при вычитании, получил отрицательный результат, подумал, что проблема с переполнением int, переписал при помощи Big_int, после чего и обнаружил, что перепутал суммы местами.

Project Euler #4

(* Checks if int is palindrome *)
let is_palindrome n = 
  let str = string_of_int n in
  let len = String.length str in
  let rec check_char s n =
    if n == len - 1 then
      (String.get s n == String.get s 0)
    else
      (String.get s n == String.get s (len - 1 - n)) && (check_char s (n + 1))
  in
  check_char str 0;;

(* check if n is a product of two 3-digit numbers *)
let is_product n = 
  let rec check_numbers i j n =
    let rest = n mod i in
    let modulo = n / i in
    let mod_length = String.length (string_of_int modulo) in
    if i = j then
      false
    else if (rest == 0) && (mod_length == 3) then 
      begin
        Printf.printf "%d %d\n" i modulo;
        true
      end
    else
      check_numbers (i+1) j n
  in
  check_numbers 100 999 n;;

(* looks for palindromes which a products of two 3-digit numbers*)
let rec check_range n m =
  if n == m then
    -1
  else if (is_palindrome n) && (is_product n) then
    n
  else
    check_range (n-1) m;;

Printf.printf "%d\n" (check_range 998001 10000)

Изначально пытался просто переделать двойной цикл с проверкой в рекурсию, в итоге оказалось проще перебрать числа в одной рекурсии.