Peczenyj's Blog

Just Another /Perl|Ruby|C++|Java|Python|JavaScript|Flash|Bash/ Hacker

Codility Equi Task Solution in Modern Perl

Codility is one of the most common services used to apply test codes (for job applications, for example). Here you can find a task sample to pratice before try the real test. The present sample is the Equi Task, and the propose is very simple.

Imagine an array with N elements. There is a P value (0 <= P <= N) who solve the problem below?

A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].

In other words, where is the equilibrium index of this array?

For example, consider the following array A consisting of N = 7 elements:

A[0] = -7   A[1] =  1   A[2] = 5
A[3] =  2   A[4] = -4   A[5] = 3
A[6] =  0

P = 3 is an equilibrium index of this array, because:

A[0] + A[1] + A[2] = A[4] + A[5] + A[6]

The task is build one subroutine called equi who will receive the array should return the value of P, or -1 if there is no equilibrium index.

Easy? Well, there is another challenge: create a O(n) solution.

Here is my solution in Perl:

Spell Correct in GNU AWK

Based on Peter Norvig Spell Correct

small spell corrector in gawklink to gist
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# Usage: gawk -v word=some_word_to_verify -f spelling.awk [ big.txt [ big2.txt ... ]]
# Gawk version with 15 lines -- 04/13/2008
# Author: tiago (dot) peczenyj (at) gmail (dot) com
#         about.me/peczenyj
# Based on : http://norvig.com/spell-correct.html
function edits(w,max,candidates,list,        i,j){
       for(i=0;i<  max ;++i) ++list[substr(w,0,i) substr(w,i+2)] # deletes
       for(i=0;i< max-1;++i) ++list[substr(w,0,i) substr(w,i+2,1) substr(w,i+1,1) substr(w,i+3)] # transposes
       for(i=0;i<  max ;++i) for(j in alpha) ++list[substr(w,0,i) alpha[j] substr(w,i+2)] # replaces
       for(i=0;i<= max ;++i) for(j in alpha) ++list[substr(w,0,i) alpha[j] substr(w,i+1)] # inserts
       for(i in list) if(i in NWORDS) candidates[i] = NWORDS[i] }

function correct(word            ,candidates,i,list,max,temp){
       edits(word,length(word),candidates,list)
       if (!asort(candidates,temp)) for(i in list) edits(i,length(i),candidates)
       return (max = asorti(candidates)) ? candidates[max] : word }

BEGIN{ if (ARGC == 1) ARGV[ARGC++] = "big.txt" # http://norvig.com/big.txt
       while(++i<=length(x="abcdefghijklmnopqrstuvwxyz")) alpha[i]=substr(x,i,1)
       IGNORECASE=RS="[^"x"]+" }

{      ++NWORDS[tolower($1)]   }

END{   print (word in NWORDS) ? word : "correct("word")=> " correct(tolower(word)) }

This is my version of the Norvig’s Spell Corrector in gnu awk.

Follow the code we can find 2 functions and 3 blocks of code. Awk is a oriented to data flow, I’m always reading something, in this case I read a huge file big.txt with many words. It is a good sample of word frequency distributions, the most common words should be present in more number than rare words.

Hello

Hello World!

Mudando De Endereço

Foram centenas de posts desde que comecei a usar o blogspot como valvula de escape.

Agora adquiri um domínio próprio e estou usando o wordpress como engine de blog, com MediaWiki para salvar os posts mais importantes daqui.

Atualizem os seus feeds: pacman.blog.br, estou desativando este site. Obrigado a todos pela audiência :)