Tweakers dev challenge writeup - 5

Door Boudewijn op donderdag 1 oktober 2015 00:05 - Reacties (0)
Categorie: Tweakers dev challenge, Views: 796

In het oude Rome stond een sterk staaltje architectuur genaamd het 'Ominesium'. Op de gevel van het gebouw was met moza´ek aangegeven hoe oud het gebouw was in jaren. Uiteraard gaven de oude Romeinen dit aan met Romeinse cijfers. Deze Romeinen waren erg bij de tijd en gebruikten de moderne notatie voor Romeinse cijfers: 49 = XLIX, 4 = IV.

Het gebouw is net na een stevige aardbeving voltooid, en het eerste moza´ek werd na een jaar aangebracht. Onze jaartelling begint bij 0, dus het eerste moza´ek werd geplaatst in het jaar 1.

Het aantal moza´ksteentjes benodigd voor een symbool is 250. Het jaartal IV kostte dus 500 steentjes om op de muur aan te brengen.
Om kleurverschil tegen te gaan werd bij elke plaatsing van een nieuw jaartal de complete moza´ek opnieuw geplaatst.
Het was een regio met veel seismische activiteit; om de 43 jaar werd de regio getroffen door een zware aardbeving waarbij 15% van de voorraad steentjes verloren ging, per aardbeving afgerond naar boven op gehele steentjes. De eerste beving sinds de voltooiing van het gebouw vond plaats na 43 jaar.
Aardbevingen vonden door een enorm toeval telkens plaats voordat het nieuwe moza´ek werd aangebracht.
Na de voltooiing van het 'Ominesium' (en dus ook nß de aardbeving in het jaar 0) was er nog een voorraad van 12.500.000 moza´eksteentjes beschikbaar voor de jaarlijkse renovatie van het moza´ek.
In welk jaar was de voorraad steentjes niet meer voldoende om het nieuwe jaartal op het gebouw te plaatsen?

Antwoord in Romeinse notatie, dus bijvoorbeeld: DCCLXII
Leuke opgave, niet zo makkelijk te bruteforcen en toch gaaf. Eigenlijk had ik gehoopt dat de resterende tekens meegenomen konden worden naar het nieuwe jaartal zodat je met de hamming distance aan de slag moest. Wellicht leuk voor een volgende keer.

Dit format "we hebben een beginsituatie, daarin verandert per tijdseenheid dit dit en dat en dat moet je doen tot" zien we bij andere delen van de puzzel-serie ook terugkomen. Je ziet vaak (zo ook bij de maanstanden en de zombies straks) dat ik een staat definieer (bijvoorbeeld met een variabele) en deze per tijdseenheid muteer en update... zo ook hier.

De intToRoman en romanToInt code heb ik gecopieerd van het internet (http://code.activestate.com/recipes/81611-roman-numerals/)

https://github.com/boudew...r/tweakers-challenge/5.py

Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import math

# bron: http://code.activestate.com/recipes/81611-roman-numerals/
numeral_map = zip(
    (1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1),
    ('M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I')
)

def int_to_roman(i):
    result = []
    for integer, numeral in numeral_map:
        count = int(i / integer)
        result.append(numeral * count)
        i -= integer * count
    return ''.join(result)

def roman_to_int(n):
    n = unicode(n).upper()

    i = result = 0
    for integer, numeral in numeral_map:
        while n[i:i + len(numeral)] == numeral:
            result += integer
            i += len(numeral)
    return result




BEGINSTEENTJES=12500500         # aantal steentjes bij start
AARDBEVINGSJAAR=43              # aantal jaren tussen bevingen
AARDBEVINGSRESTANT=0.85         # percentage dat overblijft na een beving
SYMBOOLPRIJS=250                # prijs per letter


def berekenSteentjes(jaartal, steentjesvoorraad):
    if (jaartal %AARDBEVINGSJAAR == 0):
        steentjesvoorraad=math.ceil(steentjesvoorraad*AARDBEVINGSRESTANT)
     
    dit_jaar = int_to_roman(jaartal)
   
    steentjesprijs = len(dit_jaar)*SYMBOOLPRIJS
    print ("Jaar: " +str(jaartal) +"\tvooraad: " +str(steentjesvoorraad)+"\t" + str(int_to_roman(jaartal))+"\tprijs " + str(steentjesprijs))   
    return(steentjesvoorraad-steentjesprijs)
    


steentjes_voorraad=[BEGINSTEENTJES]
for i in range(1,1000):
    steentjes_voorraad+=[berekenSteentjes(i,steentjes_voorraad[i-1])]
    if (steentjes_voorraad[i] < 0 ):
        print ("Eerste jaar met te weinig steentjes: "+str(i) + "(" + int_to_roman(i)+")")
        break



Gezien ik een hekel heb aan magic numbers gebruik ik voor mijn constanten altijd capitals bovenaan mijn scripts. Ook ben ik lui geweest en bereken ik dit alleen voor de eerste 1000 jaar, netter zou zijn om een while ( steentjes_voorraad > 0) lus te schrijven.

De steentjesvooraad heb ik in een array gezet zodat het verloop mooi te volgen is. Dit kan prima in een losse integer als je dat niet interessant vindt.

Ook hier kan ik niet al teveel over zeggen behalve dat ik denk dat deze implementatie redelijk effectief is.


Deze serie gaat verder op:
Boudewijns blog

Volgende: Tweakers dev challenge writeup - 6 10-'15 Tweakers dev challenge writeup - 6
Volgende: Tweakers dev challenge writeup - 4 10-'15 Tweakers dev challenge writeup - 4

Reacties

Er zijn nog geen reacties op deze post


Reactie formulier
(verplicht)
(verplicht, maar wordt niet getoond)
(optioneel)