« Musikutmaning: Tolv låtar - eller snarare: N musikinspelningar | Main | Isomorfa ord (Isomorphic Words) - programmet »
januari 04, 2009
Programspråket Icon och några Project Euler problem
Programspråket Icon och dess något mer aktiva objektorienterade dialekt Unicon (the Unified Extended Dialect of Icon) är ett underskattat språk. Tyvärr utvecklas det inte längre lika aktivt som tidigare av dess grundare (och det är säkert en orsak till underskattningen), men Unicon-projektet håller fortfarande på med skoj utökningar, t.ex. en SNOBOL-liknande strängmatchning.
Icon/Unicon är ett trevlig programspråk med flera ganska unika egenskaper:
- strängmatchningen. Det finns stöd för reguljära uttryck via regex.icn, men man bör först lära känna Icons egen variant som är en utveckling av SNOBOLs patterns
- "målinriktad" programmering, där success och fail avgör programmets flöde (via t.ex. en slags backtracking)
- generatorer med every och "alternattion" (se mina Mankell-skriverier nedan för mer exempel)
- co-expressions (används inte här nedan)
- det har ett drag av funktionsprogramming som tilltalar mig
- det finns ett stort antal exempel och moduler
Project Euler
Jag tänkte här inte prata så mycket om språket som visa några exempel rakt av (se referenserna nedan för mer introducerande material om språket). För detta används de tio första problemen från Project Euler, en sajt med veckoliga programmerings-/matematiska problem där man måste ange lösningen (i form av ett tal) för att komma vidare och läsa andras ofta kreativa lösningar (och p.g.a. detta visas endast programkoden, inte resultatet). De samlade Euler Project-problemen finns här.
Tilläggas kan att mitt Project Euler-ande började under mitt Lisp-skov för några år sedan och jag tenderar att göra åtminstone de första - säg - 20 problemen i programmeringsspråk som jag vill kolla in (såsom t.ex. Pop-11 i höstas; eventuellt kommer en snarlik bloggning om detta).
Nedanstående exempel antyder möjligen att Icon är ett språk för att hantera tal, vilket är lite olyckligt eftersom dess styrka snarare ligger i att hantera text/strängar (och datastrukturer). Detta sagt så skrevs flera artiklar i Icon Analyst om generering av olika talsekvenser.
Hursomhelst, här är programkoden för de 10 första Project Euler-problemen. I vissa fall visas även några (bortkommenterade) varianter av lösningar.
# some libraries used
link patterns, scan, factors, numbers, matrix, math
#
# The mandatory main procedure
#
procedure main()
problem1()
# problem2()
# problem3()
# problem4()
# problem5()
# problem6()
# problem7()
# problem8()
# problem9()
# problem10()
end
Problem 1
# If we list all the natural numbers below 10 that are multiples of 3 or 5,
# we get 3, 5, 6 and 9. The sum of these multiples is 23.
#
# Find the sum of all the multiples of 3 or 5 below 1000.
procedure problem1()
s := 0;
every s +:= mult3_or_5(1 to 999)
write(s)
end
procedure mult3_or_5(n)
# if n % 3 == 0 | n % 5 == 0 then
if n % (3|5) == 0 then
suspend n
end
Problem 2
# Each new term in the Fibonacci sequence is generated by adding the
# previous two terms. By starting with 1 and 2, the first 10 terms will be:
#
# 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
#
# Find the sum of all the even-valued terms in the sequence which do not
# exceed four million.
procedure problem2()
local s := 0
every s +:= fib_test(1 to 100)
write(s)
end
# For problem 2
procedure fib_test(n)
if (f := fib(n)) % 2 == 0 & f < 4000000 then return f
end
procedure fib(n)
nfib := 2;
prevfib :=1
currfib :=1
while nfib
currfib +:= prevfib
nfib +:= 1
}
return currfib
end
Problem 3
# The prime factors of 13195 are 5, 7, 13 and 29.
# What is the largest prime factor of the number 600851475143 ?
# pfactors from ipl/procs/factors.icn
procedure problem3()
L := pfactors(600851475143)
write(L[*L]) # write the last value
end
Problem 4
# A palindromic number reads the same both ways. The largest palindrome made
# from the product of two 2-digit numbers is 9009 = 91 × 99.
#
# Find the largest palindrome made from the product of two 3-digit numbers.
procedure problem4()
# Three different versions
## List solution:
# L := []
# every push(L, numeric(palindrome(string( (100 to 999) * (100 to 999)))))
# write(myMax(L))
## Hash table solution:
# H := table(0)
# every H[numeric(palindrome(string( (100 to 999) * (100 to 999))))]:=1
## sort(H,3) sorts on values och returns a list of
## 2*keys entries [key1, value2, key2, value2, etc]
# We want the penultimate element keyxxx in [...,keyxxx, valuexxx]
# L := sort(H,3)
# write(L[*L-1])
# Set solution
local S := set()
every insert(S, numeric(palindrome(string( (100 to 999) * (100 to 999)))))
L := []
every push(L, !S) # and converts to a list
write(myMax(L))
end
procedure myMax(L)
local maximum := get(L)
every maximum <:= !L
return(maximum)
end
procedure palindrome(s)
if s == reverse(s) then return s
end
Problem 5
# 2520 is the smallest number that can be divided by each of the numbers
# from 1 to 10 without any remainder.
#
# What is the smallest number that is evenly divisible by all of the numbers
# from 1 to 20?
procedure problem5()
L:= [];
every put(L, (1 to 20))
write(myLCM(L))
# alternative solution using lcml from library factors.icn
# write(lcml(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20))
end
# inspired by lcml in numbers.icn
procedure myLCM(L)
i := get(L)
while j := get(L) do
i := lcm(i, j)
return i
end
Problem 6
# The sum of the squares of the first ten natural numbers is,
# 1^(2) + 2^(2) + ... + 10^(2) = 385
#
# The square of the sum of the first ten natural numbers is,
# (1 + 2 + ... + 10)^(2) = 55^(2) = 3025
#
# Hence the difference between the sum of the squares of the first ten
# natural numbers and the square of the sum is 3025 − 385 = 2640.
#
# Find the difference between the sum of the squares of the first one
# hundred natural numbers and the square of the sum.
procedure problem6()
L := []
sum_squares := 0;
square_sum := 0;
every put(L, (1 to 100))
every sum_squares +:= !L^2
every square_sum +:= !L
square_sum := square_sum^2
d := square_sum - sum_squares
write(square_sum, " - ", sum_squares, " = ", d)
end
Problem 7
# By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see
# that the 6^(th) prime is 13.
#
# What is the 10001^(st) prime number?
procedure problem7()
local p;
# prime() is from numbers.icn and is defined thusly:
# suspend 2 | ((i := seq(3, 2)) & (not(i = (k := (3 to sqrt(i) by 2)) * (i / k))) & i)
# Generate the primes and stop at the 10001:th
every p := prime() \ 10001
write(p)
end
Problem 8
# 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
procedure problem8()
n := "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
## using lists
# L := []
# every i := (1 to (*n)-5 ) do {
# s := n[i:i+5] # string segment
# p := 1
# every p *:= !s # converts automatically to numbers
# put(L, p)
# }
# write(myMax(L))
# using string matching
this_max := 0
n ? {
while x := move(5) do {
move(-4)
p := product(x)
if p > this_max then
this_max := p
}
}
write("this_max: ", this_max)
end
Problem 9
# A Pythagorean triplet is a set of three natural numbers,
# a < b < c, for which, a^(2) + b^(2) = c^(2)
#
# For example, 3^(2) + 4^(2) = 9 + 16 = 25 = 5^(2).
#
# There exists exactly one Pythagorean triplet for which a + b + c = 1000.
# Find the product abc.
procedure problem9()
every c := 1 to 500 &
b := 1 to c &
a := 1 to b &
a + b + c = 1000 &
a^2 + b^2 = c^2
do {
write(a, "^2 + ", b, "^2 = ", c, "^2", " : ", a*b*c) & fail
}
end
Problem 10
# The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
#
# Find the sum of all the primes below two million.
procedure problem10()
s := 0
n := 2000000
every p := p10(n) & p < n & s +:= p
write(s)
end
procedure p10(n)
# prime() from factors.icn
suspend p:= prime() do
if p > n-1 then fail
end
Se även
Tidigare skriverier om Icon:
Programspråket Icon och stavningen av "Henning Mankell"
Fortsatt stavning av "Henning Mankell". Samt lite om agrep
Skapa strängar från reguljära uttryck - eller: Tystnaden de senaste dagarna
Education och där speciellt Books där referensverken finns nedladdningsbara. Se speciellt The Icon Analyst var en tidskrift som innehöll intrikata artiklar om Icon såväl på bredden som på djupet.
Nyhetsgruppen comp.lang.icon ("Låg aktivitet")
För Unicon:
The Unicon book (PDF)
Mailing lista
Se även Wikipediasidorna
Icon (programming language)
Unicon (programming_language)
SNOBOL (som för övrigt råkade ut för en liten Wikipedia-skärmytsling förra veckan).
Posted by hakank at januari 4, 2009 09:53 FM Posted to Pyssel | Systemutveckling