ProgrammeringsBaren! Småprat, om det du elsker!

[Mr.Garibaldi]

Fungerer veldig fint i Opera 9.23...

 

PS. Noen som har noen gode referanser/artikler/avhandlinger om real time radiosity, som ikke er i GPU Gems serien?

[hishadow]

Fungerer veldig fint i Opera 9.23...

 

PS. Noen som har noen gode referanser/artikler/avhandlinger om real time radiosity, som ikke er i GPU Gems serien?

Hehe, ingenting kan jo bli dårligere enn IE.

 

Angående sanntids-radiosity-greiene har jeg ikke vært borti. Har du tenkt å beregne tingene selv eller hente det inn fra et verktøy? Hvis du skal mekke selv og du har erfaring med raytracing er kanskje photon-mapping noe å sjekke ut? Ellers er vel Nvidia og ATI sine sider de eneste stedene å finne noe?

[DeadManWalking]

Nå er det følgende oppgave som tar nattesøvnen min:

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08

49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00

81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65

52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91

22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80

24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50

32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70

67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21

24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72

21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95

78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92

16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57

86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58

19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40

04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66

88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69

04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36

20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16

20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54

01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?

 

Jeg har prøvd meg fram i C++, men svarene jeg får er ikke riktig.

For å gjøre det litt enklere for noen som vil hjelpe, her er en array i C med tallene over:

int grid[] = {8,2,22,97,38,15,0,40,0,75,4,5,7,78,52,12,50,77,91,8,
		49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,4,56,62,0,
		81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,3,49,13,36,65,
		52,70,95,23,4,60,11,42,69,24,68,56,1,32,56,71,37,2,36,91,
		22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80,
		24,47,32,60,99,3,45,2,44,75,33,53,78,36,84,20,35,17,12,50,
		32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70,
		67,26,20,68,2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21,
		24,55,58,5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72,
		21,36,23,9,75,0,76,44,20,45,35,14,0,61,33,97,34,31,33,95,
		78,17,53,28,22,75,31,67,15,94,3,80,4,62,16,14,9,53,56,92,
		16,39,5,42,96,35,31,47,55,58,88,24,0,17,54,24,36,29,85,57,
		86,56,0,48,35,71,89,7,5,44,44,37,44,60,21,58,51,54,17,58,
		19,80,81,68,5,94,47,69,28,73,92,13,86,52,17,77,4,89,55,40,
		4,52,8,83,97,35,99,16,7,97,57,32,16,26,26,79,33,27,98,66,
		88,36,68,87,57,62,20,72,3,46,33,67,46,55,12,32,63,93,53,69,
		4,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36,
		20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,4,36,16,
		20,73,35,29,78,31,90,1,74,31,49,71,48,86,81,16,23,57,5,54,
		1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,1,89,19,67,48};

[Manfred]

Er det ikke enklere å utføre denne hvis du legger det i en to-dimensjonal array? i alle fall nå som du skal gå loddrett, vannrett og diagonalt?

[Mr. K]

Det var det første jeg tenkte på også

[Manfred]

...for da kan du kjøre en

 

for(int i = 0; i < 20; i++)
{
 sjekk(array[1][i]); 
}

osv... da kan du ha en fast og en variabel for å sjekke en rekke... og så array for å sjekke diagonalen.

 

Edit: typo

Endret 16. mars 2008 av Manfred

[DeadManWalking]

Angående den biten der, jeg bare skrev en funksjon slik jeg:

 

//linjer kan være 0-19 og tall 1-20. 
int getNumb(int linje, int tall)
{
	   linje = linje * 20; 
	   return [grid(linje+tall)-1];
}

Endret 16. mars 2008 av data_jepp

[Manfred]

Bare for å gjøre det litt mindre oversiktlig?

[DeadManWalking]

Bare for å gjøre det litt mindre oversiktlig?

 

Haha, nei. Jeg var bare så lei av å redigere inn den lange arrayen

[Vipera]

Er egentlig ikke så vanskelig oppgave, bare ta for deg en ting av gangen. Lag feks fire funksjoner, en som går vannrett, en loddrett, og to på skrå

[steingrim]

Alt dette pratet om projecteuler har frista meg til å starte igjen Morro!

[DeadManWalking]

Det er kjekt å ha et programmeringsproblem jeg kan gruble på mens jeg sitter på bussen eller på skolen, elsker deg. Plutselig bare -"GI MEG ET PAPIR" Idletime løsninger er best

[teflonpanne]

Ikke så veldig vanskelig hvis du har en todimensjonal array, bare husk å start på rad/kolonne 1,1 istedetfor 0,0 og avslutt på 18,18 istedetfor 19,19

 

edit: leif

Endret 16. mars 2008 av teflonpanne

[DeadManWalking]

Fikk den til liksom, men fy faen da. Når jeg fikk tilgang til hvordan andre har løst den fikk jeg hakeslepp. Hvem faen løser slikt i assembly ? wtf

[steingrim]

Er egentlig ikke så vanskelig oppgave, bare ta for deg en ting av gangen. Lag feks fire funksjoner, en som går vannrett, en loddrett, og to på skrå

 

Den var ganske lett ja, men det blei faktisk nesten 30 linjer Python! Overraskende mye for et så enkelt problem, mesteparten gikk for å traversere diagonalt.

 

Jeg kunne trimmet bort mye, men jeg ville jo ha det lesbart også.

[Vipera]

Er egentlig ikke så vanskelig oppgave, bare ta for deg en ting av gangen. Lag feks fire funksjoner, en som går vannrett, en loddrett, og to på skrå

 

Den var ganske lett ja, men det blei faktisk nesten 30 linjer Python! Overraskende mye for et så enkelt problem, mesteparten gikk for å traversere diagonalt.

 

Jeg kunne trimmet bort mye, men jeg ville jo ha det lesbart også.

 

Brukte ca det jeg å.

 

 

grid = [('08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08'), ('49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00'), ('81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65'), ('52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91'), ('22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80'), ('24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50'), ('32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70'), ('67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21'), ('24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72'), ('21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95'), ('78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92'), ('16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57'), ('86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58'), ('19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40'), ('04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66'), ('88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69'), ('04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36'), ('20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16'), ('20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54'), ('01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48')]

greatest = 0
#VANNRETT
for rad in range(0, 20):
for col in range(0, 49, 3):
	number = int(grid[rad][col] + grid[rad][col+1]) * int(grid[rad][col+3] + grid[rad][col+4]) * int(grid[rad][col+6] + grid[rad][col+7]) * int(grid[rad][col+9] + grid[rad][col+10])
	if number > greatest:
		greatest = number

#LODDRETT
for rad in range(0, 17):
for col in range(0, 59, 3):
	number = int(grid[rad][col] + grid[rad][col+1]) * int(grid[rad+1][col] + grid[rad+1][col+1]) * int(grid[rad+2][col] + grid[rad+2][col+1]) * int(grid[rad+3][col] + grid[rad+3][col+1])
	if number > greatest:
		greatest = number

#VERTIKALT MOT HOYRE
for rad in range(0, 17):
for col in range(0, 49, 3):
	number = int(grid[rad][col] + grid[rad][col+1]) * int(grid[rad+1][col+3] + grid[rad+1][col+4]) * int(grid[rad+2][col+6] + grid[rad+2][col+7]) * int(grid[rad+3][col+9] + grid[rad+3][col+10])
	if number > greatest:
		greatest = number

#VERTIKALT MOT VENSTRE
for rad in range(0, 17):
for col in range(9, 59, 3):
	number = int(grid[rad][col] + grid[rad][col+1]) * int(grid[rad+1][col-3] + grid[rad+1][col-2]) * int(grid[rad+2][col-6] + grid[rad+2][col-5]) * int(grid[rad+3][col-9] + grid[rad+3][col-8])
	if number > greatest:
		greatest = number
print number
print greatest

 

[steingrim]

Min løsning ser litt annerledes ut Jeg har en modul kalt euler som inneholder funksjoner som er brukt i flere enn en løsning. I denne løsningen bruker jeg en funksjon derfra som jeg har kalt slide() som ser slik ut:

 

def slide(slicable, size):
i = 0
while i + size < len(slicable):
	yield slicable[i:i+size]
	i += 1

 

Regner forresten med at folk som driver sånt som dette ikke gidder å jukse og kopiere våre løsninger, da går man jo glipp av hele moroa!

 

 

from operator import mul
from euler import slide

F = 'problem11.dat' # data file
C = 4			   # number of consecutive integers


def horisontal():
f = lambda l: [ int(x) for x in l ]
return [ f(l.strip().split()) for l in open(F).readlines() if l.strip() ]

def vertical():
hlines = horisontal()
return [ [ line[i] for line in hlines ] for i in xrange(len(hlines)) ]

def diagonal(direction):
hlines = horisontal()
offset = len(hlines)
dlines = [ [] for i in xrange(offset * 2 + 1) ]
for i in xrange(len(hlines)):
	for j in xrange(len(hlines[i])):
		dlines[direction(i,j,offset)].append(hlines[i][j])
return filter(lambda x: len(x) >= C, dlines)

# functions for traversing diagonally
up = lambda i, j, o: i + j
down = lambda i, j, o: i - j + o

lines = horisontal() + vertical() + diagonal(up) + diagonal(down)
numbers = [ n for x in lines for n in slide(x, C) ]
products = [ reduce(mul, nums) for nums in numbers ]
print max(products)

 

 

edit: fikset innrykk

Endret 17. mars 2008 av steingrim

[Vipera]

En modul med euler relaterte funskjoner var ingen dum ide. Primtall generator har jeg laget alt for mange ganger nå

[steingrim]

Ah, lite motivasjon på jobb i dag, så det blir litt tenking og euler-programmering innimellom

 

Oppgave 12 var fin, der trengte jeg litt mattetenking for å få den til å gå raskere. Jeg lagde først en versjon som snurret og gikk i 30 minutter uten å finne svar (den kom seg nærmere og nærmere da...)

 

Litt matematisk tenking i lunsjpausen og liten tur til mathworld.wolfram.com og vips så tar den litt over 1 sekund.

[teflonpanne]

Hehe, sånt er herlig.