Cinc problemes de programació

Una de les conseqüències de l’ERO a Indra (on encara treballo) és que a …curt? …mig? termini m’incorporaré al mercat laboral, o el que és el mateix, que hauré de buscar feina. I és bastant probable (i em sembla el més sensat) que la feina que busqui estigui relacionada amb el que sé fer, que és, bàsicament, de programador.

Programador? Alguns diran Analista, o en anglès, Software Engineer, o Software Architect, o títols encara més originals… En essència, però, jo crec que el que és distintiu de la meva feina és que sóc capaç de programar ordinadors i fer-los funcionar junts. Per tant, fem-ho fàcil i digues-me programador. Ras i curt.

El cas és que buscant sobre el que em puc esperar a les entrevistes de feina vaig trobar el següent article: “Five programming problems every Software Engineer should be able to solve in less than 1 hour“. Sí,ho heu entès: cinc problemes de programació que tot enginyer de software hauria de ser capaç de resoldre en menys d’una hora. Em va semblar força interessant.

L’autor d’aquest article diu que quan publica una oferta demanant programadors es troba amb candidats que no saben què vol dir “programar”. Aleshores proposa el que, al seu entendre, són cinc problemes bàsics que tot programador “de veritat” hauria de ser capaç de resoldre en menys d’una hora.

Cinc problemes en una hora. Cal fer algunes consideracions. Què ha de fer un programador per superar un repte d’aquest estil? primer de tot, cal comprendre (analitzar) el problema i les seves implicacions, i dissenyar una solució. Encara que sigui en forma de notes mentals. Hi ha alguna forma de validar el disseny de la solució trobada? Un cop analitzat i dissenyat el problema, cal pensar en la implementació de la solució. Probablement serà més eficient un llenguatge específic del domini del problema que un llenguatge de propòsit general. Si es pot triar, en general és més ràpid desenvolupar una resposta amb un intèrpret que amb un compilador (ni que només sigui perquè s’estalvia el temps de compilat); per descomptat, és més eficient disposar d’un bon entorn de desenvolupament, que proporcioni coses com compleció del codi, acoloriment de sintaxi, snippets de codi, generació automàtica de codi, depurador… que fer servir un editor de texts pelat, per molt que per Internet es trobin acudits tan graciosos com aquell que diu que el millor IDE és vi + gcc.

Per descomptat, més enllà de si interpretat o compilat, és clau per a desenvolupar de forma eficient, el conèixer a fons el llenguatge triat per al desenvolupament. Finalment, l’experiència és un grau. És més probable que algú que ha fet moltes hores de programació s’hagi trobat amb problemes similars en algun moment de la seva trajectòria i que els hagi solucionat. En resum: per a millorar l’eficiència cal experiència i coneixement en el llenguatge i les eines a utilitzar.

A més de tot l’anterior, un programador de veritat sap que l’objecte del seu treball, el codi, ha de tenir unes determinades característiques, com per exemple la legibilitat i l’organització. per no parlar de la gestió de recursos, erros i la generació i gestió de casos de proves.

Per si fos poc, el codi, com producte, s’ha d’administrar i segueix uns fluxos dins de les organitzacions. Al menys com usuari, un programador hauria d’estar al cas dels sistemes de Control de Versions, o dels sistemes d’Integració Continua.

Tot això son coneixements tècnics que ha de tenir el programador. Però no només. El programador hauria de tenir unes competències generals que inclourien la capacitat d’auto-organització (tècniques com GTD), l’autonomia, l’auto-didactisme, la bona capacitat de comunicació, oral i escrita (afegiria també audiovisual), la capacitat de treball en equip, i també capacitat didàctica i de lideratge. I segur que em deixo coses.

Bé. De totes aquestes característiques no no en parla l’autor de l’article. Jo trobo que a l’hora de contractar un programador caldria tenir-les en compte. Però el fet és aquest: el que de debò és imprescindible per a un programador és que sàpiga programar.

Tornant al prinicipi: Quins són aquests cinc problemes que tot programador hauria de poder resoldre en menys d’una hora?

Problem 1
Write three functions that compute the sum of the numbers in a given list using

  • a for-loop
  • a while-loop
  • recursion

Problem 2
Write a function that combines two lists by alternatingly taking elements. For example: given the two lists [a, b, c] and [1, 2, 3], the function should return [a, 1, b, 2, c, 3].

Problem 3
Write a function that computes the list of the first 100 Fibonacci numbers. By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two. As an example, here are the first 10 Fibonnaci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34.

Problem 4
Write a function that given a list of non negative integers, arranges them such that they form the largest
possible number. For example, given [50, 2, 1, 9], the largest formed number is 95021.

Problem 5
Write a program that outputs all possibilities to put + or – or nothing between the numbers 1, 2, …, 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

Déu n’hi do! Els problemes 1,2 i 3 són senzills. Ara bé, el 4 i el 5 poden fer-te rumiar una bona estona.

En una actualització de post, el mateix autor de l’article reconeixia que els problemes 4 i 5 havien generat una important controvèrsia.

Bé, jo també trobo que en una hora els cinc problemes és, més aviat, justet.

En el meu cas, em vaig decidir a fer els problemes. Ara bé, no pretenia resoldre’ls en una hora. De fet, el que pretenia és que em servissin per practicar un llenguatge que em fa molta gràcia i que he “descobert”, per dir-ho d’alguna manera, fa poc: amb l’Elisp de l’Emacs.

Sí, he fet servir lisp per resoldre els problemes, què passa? xD (de fet, el problema 5 l’he fet primer amb Python, però ja en parlaré després)

Allà van les meves solucions:

Solució al problema 1 (amb for-loop –> dotimes)

;; The 5 problems
;;
;; Problem 1
;; Write three functions that compute the sum of the numbers in a given list using 
;;  - a for-loop
;;  - a while-loop
;;  - recursion
;;
;; 1.1 - for-loop (dotimes)
(progn 
  (setq nums (list 1 2 3 4 5 6 7 8 9 10))
  (setq N (length nums))
  (setq suma 0)

  (dotimes (i N) 
    (setq suma (+ suma (elt nums i)))
  )

  (insert (format "\nFor loop (with dotimes) sum: %d" suma))
)
For loop (with dotimes) sum: 55

Solució al problema 1 (amb while-loop)

;; 1.2 - while
(progn 
  (setq nums (list 1 2 3 4 5 6 7 8 9 10))
  (setq N (length nums))
  (setq suma 0)
  (setq i 0)
  (while (< i N) 
    (setq suma (+ suma (elt nums i)))
    (setq i (1+ i))
  )

  (insert (format "\nWhile loop sum: %d" suma))
)
While loop sum: 55

Solució al problema 1 (recursiva)

;; 1.3 - recursion
(defun recursiveSum(numsList)
  (setq N (length numsList))
  
  (if (> N 0)
    (+ (car numsList) (recursiveSum (cdr numsList)))  ;; if part
    0                                                 ;; else part
  )
)

(progn 
  (setq nums (list 1 2 3 4 5 6 7 8 9 10))
  (setq suma 0)

  (setq suma (+ (car nums) (recursiveSum (cdr nums)))) 
  
  (insert (format "\nRecursive sum: %d" suma))
)
Recursive sum: 55

Fàcils, no? Anem pel problema 2:

;; Problem 2
;; Write a function that combines two lists by alternatingly taking elements. 
;; For example: given the two lists [a, b, c] and [1, 2, 3], 
;; the function should return [a, 1, b, 2, c, 3].
;;
(defun merger (listData indexListData listUnion) 
  (push (nth indexListData listData) listUnion)
  listUnion   ;; not strictly necessary
)

(progn 
  ;; test data
  (setq list1 (list "a" "b" "c"))
  (setq list2 (list 1 2 3 4 5 6))
  (setq listUnion (list))

  ;; get length of lists
  (setq lengthList1 (length list1))
  (setq lengthList2 (length list2))
  
  ;; length of union list
  (setq lengthUnion (+ lengthList1 lengthList2))

  (setq indexList1 0)
  (setq indexList2 0)

  (dotimes (i lengthUnion)
    ;; list 1
    (if (< indexList1 lengthList1)
      (setq listUnion (merger list1 indexList1 listUnion)) 
    )
    (setq indexList1 (1+ indexList1))
    
    ;; list 2
    (if (< indexList2 lengthList2)
      (setq listUnion (merger list2 indexList2 listUnion)) 
    )
    (setq indexList2 (1+ indexList2))
  )
 
  ;; reverse
  (setq listReversed (reverse listUnion))

  ;; show results
  (print "List merger")
  (print listReversed)
)

Una mica embolicat, no? No és el millor codi que he escrit, la veritat. El codi s’hauria simplificat si en comptes de fer servir list hagués fet servir vectors.

La funció merger no fa mes que posar al principi de la llista unificada l’element enèsim de la llista passada com argument. Com que els elements de les dues llistes es van posar alternativament al començament (push) de la llista unificada, per això cal fer un reverse de la llista unificada al final.

Bé, amb Python o amb Basic m’hauria sortit millor. Seguim.

Solució del problema 3

;; Problem 3
;; Write a function that computes the list of the first 50 Fibonacci numbers. 
;; By definition, the first two numbers in the Fibonacci sequence are 0 and 1, 
;; and each subsequent number is the sum of the previous two. 
;; As an example, here are the first 10 Fibonnaci numbers: 
;; 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34.
;; 
(progn 
  (setq n0 0.0)
  (setq n1 1.0)
  (insert "\n - 50 first Fibonacci numbers -\n")
  (insert "0\n1\n")
  (dotimes (i 50)
    (setq n (+ n1 n0))
    (insert (format "%d\n" n))
    (setq n0 n1)
    (setq n1 n)
  )
)
 - 50 first Fibonacci numbers -
0
1
1
2
3
5
8
13
21
34
...
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074

Un clàssic. La successió de Fibonacci. Aquest problema també és molt senzill.

Solució (errònia) al problema 4

;; Problem 4
;; Write a function that given a list of non negative integers, arranges them such that they form the largest possible number. 
;; For example, given [50, 2, 1, 9], the largest formed number is 95021.
;; 
(defun greater (lower upper)
  (and (not (string< lower upper)) (not (string= lower upper)))
)

(defun swap (row i)
   (setq aux (aref row i))
   (aset row i (aref row (1+ i)))
   (aset row (1+ i) aux)
)

(defun bubble-sort (strNums)
  (setq N (length strNums))
 
   ;; sort array of strings 
  (dotimes (j (- N 1))
    (dotimes (i (- N 1)) 
      (setq lower (aref strNums i))
      (setq upper (aref strNums (1+ i)))
   
      (if (greater lower upper)
        (swap strNums i)
      )
      ;;(show-row strNums)
    )
  )
)

(defun show-row (strNums)
  (setq N (length strNums))
  (dotimes (i N)
    (insert (format "%s " (aref strNums i )))
  )
  (insert "\n") 
)

(defun reverseVector (row)
  (setq N (length row))
  (dotimes (j (/ N 2))
    (setq val1 (elt row j))
    (setq val2 (elt row (- (- N 1) j)))
      
    (aset row (- (- N 1) j) val1)
    (aset row j val2)
  ) 
)

(defun concatVector (row)
  (setq N (length row))
  (setq retvalue "")
  (dotimes (i N)
    (setq retvalue (concat retvalue (elt row i)))
  )
  retvalue  ;; not strictly necessary 
)

(progn
  ;; data: list of non negative integers
  (setq nums (list 9 8 7 6 5 4 3 2 1 0))
 
  ;; convert to array of strings
  (setq N (length nums))
  (setq strNums (make-vector N nil))
  (dotimes (i N) 
    (aset strNums i (number-to-string (elt nums i)))
  )

  (insert "\nGreatest integer\n")
  (insert "\nunsorted array:\n")  
  (show-row strNums)

  (insert "\nsorted array:\n") 
  (bubble-sort strNums)
  (show-row strNums)

  (insert "\nreversed sorted array:\n") 
  (reverseVector strNums)
  (show-row strNums)
 
  ;; string to number
  (setq greatestNumber (string-to-number (concatVector strNums)))
  (insert (format "Greatest integer: %d\n" greatestNumber)) 
)
Greatest integer

unsorted array:
9 8 7 6 5 4 3 2 1 0 

sorted array:
0 1 2 3 4 5 6 7 8 9 

reversed sorted array:
9 8 7 6 5 4 3 2 1 0 
Greatest integer: 9876543210

Doncs bé, resulta que la solució no és correcta! He suposat que n’hi havia prou amb ordenar (funció bubble-sort, com no!) alfabèticament els números, però resulta que aquesta suposició és falsa, com indiquen en aquest altre post:

“A lot of folks have rightly pointed out that this problem can be solved using a lexical comparison of strings. However, that’s not all you need.

Consider the following example: [5, 50, 56]. A lexical comparison returns 56, 50, and 5, but that doesn’t make the larger number (56, 5, 50 does)”

O sigui que: meeec! cal rumiar un altre cop la solució del problema 4. Queda pendent la solució per a un futur post.

UPDATE: Solució Brute Force:

Ahir no estava d’humor per a posar-me a investigar un algorisme pera solucionar el problema 4… i avui tampoc! L’opció és fer força bruta, que,de fet, als ordinadors se’ls dona molt bé.

Amb força bruta i generadors de Python (itertools) la cosa queda tan simple com això:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# biggetst integer

import itertools as itt

print "\nBiggest number\n"

nums = ['500', '5', '51', '52', '504', '506', '54', '56', '514', '515', '516', '575']

max_str = ''
num_iters = 0

for perm in itt.permutations(nums, len(nums)):
    num_iters = num_iters + 1
    num = ''.join(perm)
    if  num > max_str:
        max_str = num

print "max: %s; iters: %d\n" % (max_str, num_iters)        

'''
>>> import biggest

Biggest number

max: 575565545251651551514506504500; iters: 479001600
''' 

Aquesta solució és qualsevol cosa menys elegant, però és molt ràpida de programar i soluciona el problema en un temps finit. Cal dir que he tirat, de nou, de la màgia de Pyhton que m’ha permès resoldre amb el simple import de les itertools la generació de les permutacions dels números. Després la concatenació amb el join i actualitzar el màxim a mida que es va trobant.

Queda pendent, per a quan tingui temps i ganes d’investigar-ho, el trobar un algorisme més intel·ligent que la solució per força bruta. Això sí, en tot cas, la força bruta sempre és una opció a considerar (i els bons programadors ho saben).

Finalment, la solució al problema 5

Primer la solució amb Python. I ara veureu perquè Python és el Llenguatge dels Déus:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
'''
Problem 5
Write a program that outputs all possibilities to put + or - or nothing 
between the numbers 1, 2, ..., 9 (in this order) 
such that the result is always 100. 
For example: 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100.
'''
def get_base3_indexes(num):
    ix = [0,0,0,0,0,0,0,0]
    done = False
    i = 0
    while not done:
        quot, mod = num / 3, num % 3

        if quot >= 3:
            num = quot
            ix[i] = mod
        else:
            done = True
            ix[i] = mod
            ix[i + 1] = quot

        i = i + 1

    ix.reverse()
    return ix

if __name__ == "__main__":
    symbols = ["+","-"," "]
    formula = "1%c2%c3%c4%c5%c6%c7%c8%c9"
    ix = [0,0,0,0,0,0,0,0]
     
    # és a dir: Variacions amb Repetició de 3 elements agafats de 8 en 8
    # RV n m = n ** m
 
    top =  3**8
    
    for i in range(0, top - 1):
        ix = get_base3_indexes(i)
        
        calc = formula % (symbols[ix[0]],
                          symbols[ix[1]],
                          symbols[ix[2]],
                          symbols[ix[3]],
                          symbols[ix[4]],
                          symbols[ix[5]],
                          symbols[ix[6]],
                          symbols[ix[7]])

        calc2 = [c for c in calc if c != " "]
        calc2_compact = "".join(calc2)
        result = eval(calc2_compact)
        if result == 100:
            print "%s = %d" % (calc2_compact, result)
            
    print "%d lines analyzed" % top
    print "done!"

O sigui, calcula les “variacions amb repetició de tres elements agafats de 8 en 8″ Els tres elements són les tres “operacions” possibles entre dígits: sumar (“1” + “2” = 3), restar (“1” – “2” = -1) i concatenar (“1” concat “2” = “12”) i els agafo de 8 en 8 perquè són 8 posicions per a operadors entre els 9 operands numèrics. la iteració per tots els casos possibles i la conversió a base 3 de l’index actual permet posar els operadors adequats on els toca en cada iteració.

Però la màgia de Python ve en aquestes tres línies:

        calc2 = [c for c in calc if c != " "]
        calc2_compact = "".join(calc2)
        result = eval(calc2_compact)

La primera línia fa una llista d’elements (calc2) a partir de la llista original (calc) on els operadors “concat” apareixen com blancs entre els números. Agafa cada element c de calc excepte els elements iguals a ” “. És dir, “compacta” la llista calc eliminant-li els blancs. Es tracta d’un bonic exemple de Python Comprehensions.

La següent línea genera un string a partir de la llista compactada.

la tercera línia avalua la suma.

La dada és que fa tot això en tres línies. Eficiència i productivitat en un llenguatge és exactament això.

I ara l’equivalent amb elisp:

;; Problem 5
;; Write a program that outputs all possibilities to put + or - or nothing 
;; between the numbers 1, 2, ..., 9 (in this order) 
;; such that the result is always 100. 
;; For example: 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100.
;; 
;; variations with repetition of 3 elements (the +,- and "concat" operators) 
;; taken 8 (8 operands within the 1,2,3,4,5,6,7,8 and 9 operands) at a time
;;
;; VR n r = n ** r
;;  
(defun main ()
  ;; return vector with coeficients of the conversion of num to base 3.
  (defun get_base3 (num)
    (let
      ( 
        (base3 (make-vector 8 0))
        (n 8)
        (done nil)
        (i 0)
        (quot 0)
        (mod 0)
      )
      
      (while (not done)
        (setq quot (/ num 3))
        (setq mod (% num 3))

        (if (>= quot 3)
          (progn
            (setq num quot)
            (aset base3 i mod)
        
          )
          (progn
            (setq done t)
            (aset base3 i mod)
            (aset base3 (1+ i) quot)
          ) 
        )
        (setq i (1+ i))
      )

      ;; return
      base3
    )
  )

  ;; clean white spaces
  (defun clean_white_spc (str)
    (let
      ( 
        (c "")
        (j 0)
        (str_out "")
        (len (length str))
      )
      (dotimes (j len)
        (setq c (substring str j (+ j 1)))
        (if (not (string= c " "))
          (setq str_out (concat str_out c))
        )
      )

      ;; return
      str_out
    )
  )

  ;; formula parser
  (defun perform_calculation (formula)
    (let 
      (
        (n (length formula))
        (stackoperands (make-vector 9 0))
        (stackoperators (make-vector 8 "+"))
        (i 0)
        (j 0)
        (k 0)
        (accum 0)
      )
 
      ;; lexical parser
      (dotimes (i n)
        (setq c (substring formula i (1+ i)))
        (if (and (not (string= c "+")) (not (string= c "-")))
          (progn ;; true. c is a number
            (setq accum (+ (* accum 10) (string-to-number c)))
          ) 
          (progn ;; false. c is an operator  
            (aset stackoperands j accum)
            (aset stackoperators k c)
            (setq k (1+ k))
            (setq j (1+ j))
            (setq accum 0)
          )
        )
        (if (> accum  0)
          (aset stackoperands j accum)
        )
      )

      ;; performs the sum
      (setq i 0)
      (setq j 0)
      (setq operator "")
      (setq operand 0)
      (setq accum 0)

      (dotimes (i (length stackoperands))
        (setq operand (aref stackoperands i))
        (if (= i 0)
          (progn ;; i = 0
            (setq accum operand) 
          )
          (progn ;; i > 0
            (setq j (1- i))
            (setq operator (aref stackoperators j))
            (if (string= operator "+")
              (setq accum (+ accum operand))
              (setq accum (- accum operand))
            )
          )
        )
      )

      ;; return
      accum
    )
  )

  ;; main
  (let
    (
      (symbols ["+" "-" " "])
      (formula "1%s2%s3%s4%s5%s6%s7%s8%s9")
      (ix (make-vector 8 0)) 
      (top (- (expt 3 8) 1))
      (i 0)
      (count 0)
    )
  
    (insert "\nSum 100\n")
 
    (dotimes(i top) 
      (setq ix (get_base3 i))
      (setq calc (format formula (aref symbols (aref ix 0))
                                 (aref symbols (aref ix 1))
                                 (aref symbols (aref ix 2))
                                 (aref symbols (aref ix 3))
                                 (aref symbols (aref ix 4))
                                 (aref symbols (aref ix 5))
                                 (aref symbols (aref ix 6))
                                 (aref symbols (aref ix 7))  
                 )
      )
     
      (setq calc2 (clean_white_spc calc))
      (setq sum (perform_calculation calc2))

      (if (= sum 100)
        (progn 
          (setq count (1+ count))
          (insert (format "%d: %s = %d\n" count calc2 sum))
        )
      )
    )
    (insert (format "\n%d lines analyzed\ndone!"  top))
  )
)

És equivalent a la solució amb Pyhton, només que ha calgut fer funcions per a fer la compactació i eliminació dels espais en blanc, i també per avaluar la fórmula amb un senzill parser.

……

Una hora diu. En fi.