Home > Project Euler, python > Problem Euler #28

Problem Euler #28

'''
Starting with the number 1 and moving to the right in a clockwise direction
a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.
What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral
formed in the same way?
'''

Ho creato un oggetto, con all’interno una matrice.
Posiziono il numero 1 al centro della matrice, poi comincio con gli
spostamenti che sono:

1 passo a destra e posiziono il 2
1 passo in basso e posiziono il 3

Dopo una coppia di movimenti, lo step aumenta di 1:

2 passi verso sx posizionando il 4 ed il 5
2 passi verso l’alto posizionando il 6 ed il 7

aumento lo step

3 passi verso destra
3 passi verso il basso e così via.

Il calcolo della diagonale viene da sè…

python:

import time

ts = time.clock()

class Matrix():
    def __init__(self, dim):
        '''Create dim*dim grid '''
        self.c = 1 # count
        self.step = 1
        self.row = self.col = dim/2
        self.m = [[0 for i in range(dim)] for j in range(dim)]

    def start(self):
        '''Start to cycle'''
        self.m[self.row][self.col] = self.c # start point '1'
        while True:
            try:
                self.go_right()
                self.go_down()
                self.step += 1
                self.go_left()
                self.go_up()
                self.step += 1
            except IndexError:
                break

    def go_right(self):
        for i in range(self.step):
            self.c += 1
            self.col += 1
            self.m[self.row][self.col] = self.c
        
    def go_down(self):
        for i in range(self.step):
            self.c += 1
            self.row += 1
            self.m[self.row][self.col] = self.c

    def go_left(self):                
        for i in range(self.step):
            self.col -= 1
            self.c += 1
            self.m[self.row][self.col] = self.c
        
    def go_up(self):                
        for i in range(self.step):
            self.row -= 1
            self.c += 1
            self.m[self.row][self.col] = self.c

    def show(self):
        for row in self.m:
            print row

    def get_diagonal_sum(self):
        nums = []
        i = 0
        j = 1
        while i < len(self.m):
            nums.append(self.m[i][i])
            nums.append(self.m[i][len(self.m) - j])
            i += 1
            j += 1
        return sum(nums)-1

if __name__ == '__main__':
    matrix = Matrix(101)
    matrix.start()
    print matrix.get_diagonal_sum()
    print "elapsed: %ssec" %(time.clock() - ts)

risultato:

669171001
elapsed: 0.668709618693sec

Poi esistono le soluzioni disarmanti, quelle dei matematici:

per un quadrato 5*5:
il valore del primo angolo in alto a dx è = n^2 (25)
il valore dell’angolo successivo in senso antiorario è = n^2 – n + 1 (21)
il valore dell’angolo successivo è = n^2 – 2n + 2 (17)
l’ultimo angolo è = n^2 – 3n + 3 (13)

quindi abbiamo:
n^2 + n^2 – n + 1 + n^2 – 2n + 2 + n^2 – 3n + 3 =
4n^2 – 6n + 6

Per ottenere la diagonale di un quadrato 5×5, dobbiamo sommare anche i 4 angoli del
quadrato 3×3 interno e infine sommare 1 (il quadrato 1×1 non lo consideriamo).
Per un quadrato maggiore, basterà applicare tale formula a tutti i numeri dispari, da
3 a 1002 (escluso):

sum([(4*i**2 - 6*i + 6) for i in range(3,1002,2)]) + 1

roba da matti…

Categorie:Project Euler, python
  1. Non c'è ancora nessun commento.
  1. giugno 13, 2014 alle 6:21 pm

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: