{-#####################################################

HOMEWORK 10

ALAIN V. DE LARA

#####################################################-}

module HW10 where

import Hugs.Prelude

{-#####################################################

exercise 17.2

SUBSEQUENCES AND SUBLISTS

* nonsubsequences are obtained by omitting elements inside the string

* subsequences are obtained by removing strings of various length in the

original strings respecting the order

* LIST= nonsubsequences + subsequences

##################################################### -}

{-

pairs::[a]->[b]->[(a,b)]

pairs xs ys=[ (x,y) | x<-xs, y<-ys ]

-}

-- mixup does the same as "pairs" but for list of list

-- mixup [[1,2],[3,4]] [[5,6],[7,8]] ==>

-- [[1,2,5,6],[1,2,7,8],[3,4,5,6],[3,4,7,8]]

mixup::[[a]]->[[a]]->[[a]]

mixup xs ys =[ x++y | x<-xs,y<-ys]

-- genleft [1,2,3,4]=> [4],[3,4],[2,3,4],[1,2,3,4]

genleft::[a]->[[a]]

genleft ls=[ subtake (s-l) l ls | l<-[1..s] ]

where s=(length ls)

-- genright [1,2,3,4]=> [1],[1,2],[1,2,3],[1,2,3,4]

genright::[a]->[[a]]

genright ls=[ subtake 0 l ls | l<-[1..s] ]

where s=(length ls)

getr::Int->[a]->[a]

getr pos ls=drop pos ls

getl::Int->[a]->[a]

getl pos ls= take (pos-1) ls

-- this algorithm omit the [first,last] case

nonsub::[a]->[[[a]]]

nonsub ls=[[head ls,last ls]:mixup(genleft(getl i ls)) (genright(getr i ls)) |i<-[2..s-1]]

where s=(length ls)

-- ***************************************************************

-- subtake: get sub-string eg:

-- subtake 2 3 "abcdefgh" => "cde" ( string "cde" returned )

-- ***************************************************************

subtake= (\ start len ls->take len (drop start ls) )

subseq::[a]->[[a]]

subseq ls=[subtake i j ls| i<-[0..(s-1)], j<-[1..(s-i)]]

where s=(length ls)

-- ***************************************************************

-- cutoff : return the remaning string, eg:

-- cutoff 2 3 "abcdefgh" => "abfgh" ( cut "cde" from string )

-- ***************************************************************

sublists::[a]->[[[a]]]

sublists ls=[(subseq ls)] ++ (nonsub ls)

{-#####################################################

exercise 17.23

FACTORS AND HAMMING NUMBERS

####################################################### -}

{- ******* Sample of Hamming numbers *********

1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,

48,50,54,60,64,72,75,80,81,90,96,100,108,120,125,128,135,

144,150,160,162,180,192,.........

definition of hamming number=2^i*3^j*5^k for i, j, k >0

other definition of hamming number=a number that does have

prime factors other than 2,3,5

********************************************** -}

-- ####### FIRST VERSION #######

-- slowest version of isprime

isprime1::Int->Bool

isprime1 n=(factors1 n==[1,n])

factors1::Int->[Int]

factors1 n=1:[q | q<-[2..n],(mod n q)==0]

-- does a list have prime numbers other than 2,3,5 ?

-- return true if list has prime numbers 7,11,13,19,23,29.....

badprime1::[Int]->Bool

badprime1 []=False

badprime1 (x:xs)

| x==2 || x==3 || x==5 =badprime1 xs

| (isprime1 x)=True -- primality test

| otherwise=badprime1 xs

ham1=1:[ i | i<-[2..] , not(badprime1(factors1 i)) ]

-- reaches 4320 (138th) in 30 seconds

-- ####### OPTIMIZED VERSION ######

-- fast isprime

-- return [] if the number is prime >=7

-- if n=a x b then either a or b must be <sqrt(n+1)

-- only checks odd numbers

isprime2 ::Int->[Int]

isprime2 n

|(n>2) && not(mod n 2==0)=[i |i<-[3,5..floor(sqrt (fromInt n))+1],(mod n i)==0] -- test for oddness

| otherwise=[n]

-- modified factors to improve speed

-- only checks odd factors

factors2::Int->[Int]

factors2 n=[q | q<-[3,5..n],(mod n q)==0]

-- does a list have prime numbers other than 2,3,5 ?

-- return true if list has prime numbers 7,11,13,19,23,29.....

-- use fast version of isprime

badprime2::[Int]->Bool

badprime2 []=True

badprime2 (x:xs)

| x==2 || x==3 || x==5 =badprime2 xs

| (isprime2 x)==[]=False -- primality test

| otherwise=badprime2 xs

ham2=1:2:3:4:5:[ i | i<-[6..] , badprime2(factors2 i) ]

-- reaches 10000 (175th) in 30 seconds

{-#####################################################

exercise 17.24

INFINITE RUNNING SUMS

differents solutions for finite and infinite running sums

####################################################### -}

-- special case "[0..]"

-- implementation with function mapping

runsum1 x= if (x==0) then 0

else x + runsum1 (x-1)

runningsum1 = map runsum1 [0,1..]

-- COMMENTS about runningsum1, very slow

-- reaches 3,260,181 in 15 seconds

-- ************************************************************

-- Implementation of the running sum the recursive way

-- still for special case "[0..]"

runsum2 x y= x: runsum2 (x+y) (y+1)

runningsum2=runsum2 0 1

-- COMMENTS about runningsum2, very fast

-- about 200 times faster than "runningsum1"

-- ************************************************************

-- If the list is finite and with few elements

-- eg runsum3 [1,2,3,4,5,6]=>[1,3,6,10,15,21]

-- using substring of a list: sum(subtake 0 3 [1,2,3,4,5,6])=>sum([1,2,3])=>6

runsum3::[Int]->[Int]

runsum3 ls=[sum (subtake 0 index ls) | index<-[1..s] ]

where s=length ls

-- ************************************************************

-- If the list is infinite

-- the algorithm slows down when the list become "big"

runsum4::[Int]->[Int]

runsum4 ls=[sum (subtake 0 len ls) | len<-[1..] ]

-- ************************************************************

-- final solution

-- same algorithm like "runsum2"

-- the processing speed remain the "same" at any moment

runsum5::[Int]->[Int]

runsum5 []=[0]

runsum5 (s:ls)=runsumrecursiv s ls

runsumrecursiv::Int->[Int]->[Int]

runsumrecursiv s []=[s]

runsumrecursiv s ls =s: runsumrecursiv (s+head(ls)) (tail ls)

{-#####################################################

LIST OF FOUR SQUARES PROBLEM

####################################################### -}

{-

page 365:

pythagtriples=[(x,y,z) | z<-[2..],y<-[2..z-1], x<-[2..y-1], x*x+y*y==z*z]

-}

-- first solution with squares,but there are problems

-- EG:squares 23 give [4,2,1,1,1] for 23

-- because the answer should be (23, [3, 3, 2, 1]).

squares 0 = []

squares n =

let m = (floor (sqrt (fromInt n))) in

m : squares (n - m*m)

foursquares=[(k,squares k) | k<-[0..] ]

-- ######## FIXED #########################################

-- makeclean: cleanup the zeros:

-- makeclean [1,2,3,4]=>[1,2,3,4]

-- makeclean [0,1,2,3]=>[1,2,3]

-- makeclean [0,0,1,2]=>[1,2]

-- makeclean [0,0,0,1]=>[1]

-- makeclean [0,0,0,0]=>[]

makeclean::[Int]->[Int]

makeclean [0]=[]

makeclean (x:xs)

| x==0=makeclean xs

| otherwise =x:xs

-- will return lots of solution==> only take the first one

fsq n=head[makeclean[s,t,u,v] | s<-[0..(sqint n)],t<-[0..(sqint n)],u<-[0..(sqint n)],v<-[0..(sqint n)],n==s*s+t*t+u*u+v*v]

where sqint x= floor(sqrt(fromInt x))

lfsq=[(k,fsq k) |k<-[0..]]

{-######################################################-}

{-######################################################-}