Amazon TechO(n) Challenge

QuoVadis · December 5, 2015

Dac? e?ti pasionat de rezolvarea unor probleme informatice complexe, te invit?m s? participi la a doua edi?ie a concursului "Amazon TechO(n) Challenge". Competi?ia are loc online, deci nu trebuie s? te deplasezi c?tre o anumit? loca?ie; totul e s? ai acces la internet pe durata derul?rii lui. Premii:

Locul I: 10000 RON
Locul II: 5000 RON
Locul III: 2500 RON

Autentific?-te folosind contul t?u Facebook sau Google pentru a participa, iar noi î?i vom reaminti pe email cu o zi înainte de începerea concursului. Mult succes!

TechO(n) Challenge

Zatarra · December 5, 2015

Scuze de intrebare, in ce consta challenge-urile?

tjt · December 5, 2015

Scuze de intrebare, in ce consta challenge-urile?

Sunt probleme de algoritmica, cel putin asa a fost anul trecut, dar sunt foarte grele...

Zatarra · December 5, 2015

Sunt probleme de algoritmica, cel putin asa a fost anul trecut, dar sunt foarte grele...

Mersi. In ce limbaj se pot rezolva? Sau e irelevant?

tjt · December 5, 2015

Mersi. In ce limbaj se pot rezolva? Sau e irelevant?

Din ce tin minte nu era specificat un limbaj anume.

QuoVadis · December 5, 2015

Scuze de intrebare, in ce consta challenge-urile?

7. MEDIU Concurentii pot folosi orice limbaj de programare pentru a rezolva problemele de programare, cu ajutorul oricarui mediu de dezvoltare sau editor de text.

8. CONCURSUL Pentru a castiga premiile, Concurentii vor trebui sa rezolve problemele de programare care le vor fi prezentate pe Site-ul Concursului. In principiu, problemele constau in gasirea unor strategii optime intr-o simulare, in functie de o serie de reguli bine definite care se regasesc pe Site-ul Concursului. Pentru rezolvarea problemelor concurentii vor trebui sa genereze programe intr-un limbaj descris in textul problemei, programe ce vor trebui incarcate/trimise prin intermediul Site-ul de Concurs. Aceste programe vor reprezenta Solutiile. Concurentii vor trebui sa respecte cu strictete cerintele descrise in probleme pentru a obtine Solutii valabile. Nerespectarea cerintelor specificate in probleme va conduce la obtinerea de Solutii invalide, care nu vor fi punctate.

Regulament - http://challenge.amazontechon.com/RegulamentAmazonChallenge2015.pdf

Zatarra · December 5, 2015

Mersi @tjt

tjt · December 10, 2015

A inceput competitia.

Problema e cu Drone #StarWars

QuoVadis · December 10, 2015

Problema de pe TechO(n) Challenge (Au mai ramas 7 zile, 5 ore)

Începând cu anul acesta Amazon experimenteaz? livrarea comenzilor online prin drone. Dronele sunt înc?rcate cu coletele ce trebuie livrate, iar sarcina lor este s? duc? coletul la o anumit? destina?ie indiferent de obstacolele care pot ap?rea pe traseu. Problema de anul acesta v? propune s? scrie?i codul pentru a ghida o astfel de dron? pe h?r?i arbitrare.

Harta: caroiaj R x C unde R este num?rul de linii, iar C num?rul de coloane, col?ul stânga sus fiind (0,0)

Pe hart? exist? o singur? destina?ie X unde trebuie s? ajung? drona (care pleac? ini?ial din pozi?ia marcat? cu ‘@’). Pe hart? mai pot fi:

obstacole (marcate prin simbolul '#')
alte drone operate de alte companii (marcate cu 'D')
?i cet??eni nemul?umi?i c? spa?iul lor aerian e foarte înc?rcat (marca?i cu 'C' pe hart?)

Limitele h?r?ii: nu sunt marcate cu obstacole, dar orice obiect (dron?, cet??ean) care iese de pe hart? se consider? "disp?rut" ?i nu mai poate influen?a în nici un fel obiectele r?mase pe hart?.

Obstacolele: situate doar în interiorul h?r?ii, în momentul când orice dron? se izbe?te de ele, este distrus?.

Cet??enii: pot fi op?ionali pe hart? ?i sunt nemul?umi?i de faptul c? dronele traverseaz? spa?iul lor aerian. Odat? pozi?iona?i pe hart?, au o direc?ie fix? (una dintre valorile UP, DOWN, LEFT sau RIGHT) prestabilit? pe care o urmeaz? pân? ies în afara h?r?ii. Pot trece prin obstacole - adic? s? ocupe aceea?i pozi?ie cu un obstacol - ?i trag cu pra?tia ?i doboar? orice dron? care se afla în raza lor vizual? (de 3 p?tr??ele).

Raza vizual? e definit? folosind o func?ie de distan?? d = max (|x1 - x2|, |y1 - y2|), astfel încât "raza vizuala" a unui cet??ean este un p?trat în jurul acestuia.

Dronele: sunt programate de ingineri necunoscu?i ?i au propriile lor destina?ii, predefinite ?i ajung la destina?ie urmând un algoritm propriu. De obicei evit? obstacolele ?i cet??enii dar nu reu?esc tot timpul. Nu urm?resc aceea?i destina?ie 'X', doar se întâmpl? s? treac? prin acela?i spa?iu aerian.

Propria dron?:

Scopul concursului este s? cre?m un program care s? duc? propria dron? la destina?ie, în ciuda obstacolelor ?i a cet??enilor nemul?umi?i de pe hart?. Pentru a reduce costurile ?i a m?ri cât mai mult eficien?a dronelor, ele sunt dotate cu un controller foarte simplu (specificat în sec?iunea "CPU") care poate încarc? ?i rula un program specificat ca text surs?.

Pentru c? procesorul dronei consum? destul de mult curent, exist? un num?r maxim de instruc?iuni care pot fi executate, cu cât execu?ia unui program cere mai pu?ine instruc?iuni executate cu atât punctajul ob?inut este mai bun. De asemenea bateria dronei este limitata ?i aceasta nu poate zbura pentru un timp nedefinit, deci cu cât drona face mai pu?ini pa?i pân? la ?int? (maxim 2500), cu atât scorul este mai mare.

Solu?ia

Solu?ia unei h?r?i este un fi?ier text con?inând programul care s? controleze o dron?. Programul trebuie scris într-un limbaj pentru CPU-ul dronei (specificat mai jos în sec?iunea CPU).

CPU

Programul realizat pentru drone se execut? pe un CPU foarte simplu care are la dispozi?ie doar 2 regi?tri ?i memorie. Atât regi?trii cât ?i celulele de memorie pot stoca un num?r întreg de 32 bi?i cu semn.

Exista 2 regi?tri, iar fiecare poate stoca un num?r întreg:

A - acumulator, folosit pentru opera?ii aritmetice.
N - registru de indirectare, folosit pentru a accesa memoria.

Memoria dronei: 10^6 celule, fiecare capabil? s? stocheze un num?r întreg pe 32 bi?i. Numerotarea celulelor începe cu 0 care e prima loca?ie de memorie.

Setul de instruc?iuni disponibile:

LDN constant?/referin?? - încarc? registrul N cu o constant? (ex. LDN 3 încarc? 3 în N) sau cu o valoare din memoria dronei de la adresa specificat? (ex LDN [3] încarc? în N valoarea din memorie de la adresa 3).
STA referin??/reg - stocheaz? valoarea din registrul A în memoria dronei la adresa ref (ex. STA [3] stocheaz? valoarea registrului A în memorie la adresa 3) sau la adresa specificat? de registrul N (ex. LDN 3 urmata de STA [N] va stoca valoarea registrului A în memorie la adresa 3)
LDA constant?/referin??/reg - încarc? în registrul A valoarea unei constante (ex. LDA 5 încarc? 5 în A) sau valoarea din memoria dronei de la adresa referin??/reg (ex. LDA [6] încarc? în A valoarea memoriei de la adresa 6 iar LDA [N] încarc? în A valoarea memoriei pointata de N)
ADDA constant?/referin?? - sumeaz? valoarea registrului A cu o constant? (ex. ADDA 3 aduna 3 la valoare din registrul A) sau cu valoarea din memoria dronei de la adresa referin?? (ex. ADDA [4] adaug? la A valoarea memoriei de la adresa 4).
SUBA constant?/referin?? - scade valoarea registrului A cu o constant? (ex. SUBA 3 scade 3 din valoarea registrului A) sau cu valoarea din memoria dronei de la adresa referin?? (ex. SUBA [7] scade din valoarea registrului A valoarea memoriei de la adresa 7).
JGE constant?/referin?? – continua execu?ia programului cu linia din program specificat? de const/ref dac? valoarea registrului A este mai mare sau egal? cu 0 (ex. JGE 8 sare la linia 8; JGE [2] sare la linia specificat? de valoarea din memorie de la adresa 2).
HLT - termin? ciclul curent de execu?ie

Exemplu pentru calculare Fibonacci:

 

// calculate Fibonacci(7)
LDA 7
SUBA 1
STA [0]

LDA 0
STA [1] // [1] is var "a"
LDA 1
STA [2] // [2] is var "b"

// loop start
LDA [1] // add a and b
ADDA [2]
STA [3] // store result in "tmp" @[3]
LDA [2] // a = b
STA [1]
LDA [3] // b = tmp
STA [2]

LDA [0] // DEC [0]
SUBA 1
STA [0]
JGE 7

LDA [1] // result in reg A
HLT

Input/Output

Configura?ia h?r?ii în fiecare moment este scris? în memoria procesorului dronei la o loca?ie fix?. Ca rezultat al execu?iei programului rezult? un num?r întreg pe care programul trebuie s?-l scrie la o alt? adres? fix? care s? semnifice direc?ia în care s? se mi?te drona sau eventual s? stea pe loc.

Comenzi dron?:

Comanda pe care drona trebuie s? o execute la urm?torul pas se scrie la adresa 0 de memorie.

Valorile care trebuie folosite sunt:

0 = HOLD
1 = UP
2 = RIGHT
3 = DOWN
4 = LEFT

Configura?ie hart?:

Harta este disponibil? începând cu adresa 1 din memoria dronei. La fiecare pas harta este actualizat? cu noile obiecte de pe hart?, deci harta poate s? ocupe mai mult sau mai pu?in? memorie de la pas la pas dac? apar sau dispar obiecte de pe ea (drone sau cet??eni). Maximul pe care poate s? îl ocupe harta în memorie este determinat de câte obstacole sunt pe hart? ?i câ?i cet??eni ?i drone pot exista pe hart? la un moment dat (Vezi limitele problemei).

Structura:

Rows, Cols: dimensiunile h?r?ii, nu se schimb?
X, Y: coordonatele curente ale dronei
Tx, Ty: coordonatele target-ului (nu se schimb? de-a lungul simul?rii)
NR_OBSTACOLE, urmeaz? 2 x NR_OBSTACOLE cu coordonatele lor (nu se schimb? de-a lungul simul?rii)
NR_CETATENI, urmeaz? 2 x NR_CETATENI cu coordonatele lor
NR_DRONE, urmeaz? 2 x NR_DRONE celule cu coordonatele lor

Limite:

Rows, Cols <= 50
NR_OBSTACOLE < (R x C) / 2
NR_CETATENI <= 50
NR_DRONE <= 50
Se poate face upload la o solu?ie per hart? o dat? la 10 secunde.
Nu pot exista mai mult de 10 000 de solu?ii per hart?.

Scor

Scorul ob?inut la o hart? este 0 dac? drona love?te un obstacol, este doborâta de un cet??ean sau dac? nu ajunge la destina?ie în maxim 2500 pa?i. Dac? drona ajunge la destina?ie, se acorda un punctaj calculat dup? urm?toarea formul?:

Pondere_Hart? * 10000 / ln(Nr_pa?i^2 * SUM(CPU_consumat_la_fiecare_pas))

Fiecare hart? are o pondere diferit? (egal? cu num?rul de ordine în cazul celor vizibile ?i dublu num?rului de ordine în cazul celor private), astfel încat cu cât rezolvi mai multe h?r?i dificile cu atât ob?ii un scor total mai mare.

Execu?ia programului

Execu?ia codului dronei începe cu linia 0 din program ?i se opre?te dup? 10^6 instruc?iuni sau dac? în program a ap?rut instruc?iunea HLT. La momentul respectiv se ia valoarea de la adresa 0 ?i se interpreteaz? ca fiind o comand? de deplasare.

Înainte de a se executa deplasarea, se verifica dac? drona nu se afla peste un obstacol sau în afara h?r?ii caz în care se termin? simularea cu punctaj 0.

În caz c? drona se afl? deja pe destina?ie, se termin? simularea ?i se calculeaz? scorul.

Exemple

Harta 1

Primele h?r?i au o configura?ie prestabilit? (dimensiune, obstacole, obiecte pe hart?), deci programul dronei nu trebuie s? se adapteze la diferite configura?ii. Ultimele h?r?i au configura?ii dinamice (disponibile la runtime prin memoria controllerului), cu nivel cresc?tor de dificultate (num?r de cet??eni ?i drone).

O hart? este descris? în format JSON.

Exemplu

{
  "simulatedDrone": {"type": "Drone", "identifier": "@", "position": {"x": 3, "y": 0}},
  "map": {
    "cols": 20,
    "rows": 20,
    "target": {"x": 17, "y": 12},
    "objects": [
      {"type": "Obstacle", "position": {"x": 16, "y": 12}},
      {"type": "Obstacle", "position": {"x": 17, "y": 14}},
      {"type": "Obstacle", "position": {"x": 18, "y": 14}},
      {"type": "Obstacle", "position": {"x": 13, "y": 11}},
      {"type": "Obstacle", "position": {"x": 14, "y": 11}},
      {"type": "Obstacle", "position": {"x": 15, "y": 11}},
      //cetateni
      {"type": "Cetatean", "identifier": "C01", "position": {"x": 0, "y": 6}, "direction": "RIGHT"},
      // drones
      {"type": "Drone", "identifier": "D01", "position": {"x": 6, "y": 19}, "controller": {"type": "Direction", "direction": "UP"}},
      {"type": "Drone", "identifier": "D02", "position": {"x": 16, "y": 0}, "controller": {"type": "Target", "target": {"x": 10, "y": 5}}}
    ]
  },
  "steps": [
    {
      "stepNumber": 4,
      "objects": [
        // drone
        {"type": "Drone", "identifier": "D03", "position": {"x": 0, "y": 14}, "controller": {"type": "Direction", "direction": "RIGHT"}}
      ]
    },
    {
      "stepNumber": 9,
      "objects": [
        // cetateni
        {"type": "Cetatean", "identifier": "C03", "position": {"x": 16, "y": 19}, "direction": "UP"},
        // drone
        {"type": "Drone", "identifier": "D10", "position": {"x": 19, "y": 7}, "controller": {"type": "Target", "target": {"x": 15, "y": 19}}}
      ]
    }
  ]
}

Pentru fi?ierul JSON dat ca exemplu mai sus:

Drona proprie este în câmpul simulatedDrone ?i începe de la pozi?ia specificat? în câmpul position.
Harta este descris? de obiectul map cu num?rul de rânduri în câmpul rows ?i num?rul de coloane în câmpul cols. La primul pas pe hart? exist? ni?te obiecte: obstacole, cet??eni ?i/sau drone.
La anumi?i pa?i în viitor în simulare pot ap?rea alte obiecte, îns? nu pot ap?rea noi obstacole. Aceste obiecte dinamice sunt descrise de vectorul din câmpul steps.

Luând în considerare descrierea h?r?ii, putem afla o solu?ie optima pentru acea hart? specific? ?i apoi scrie instruc?iunile pentru aceasta.

H?r?ile devin mai dificile pentru h?r?ile private în care doar drona ?tie cum arat? harta la un anumit pas deoarece are configura?ia acesteia în memorie. Pentru aceste h?r?i drona trebuie s? fie inteligent? ?i s? evite obstacolele, celelalte drone ?i cet??enii în mod programatic.

Harta 2

Pentru o hart? de 10x10 cu ?inta la (7, 5):

Drona ta este marcat? cu @. Avem un program cu solu?ia:

 
// mergi la dreapta pentru primii 7 pa?i
LDA [1000]
SUBA 7
JGE 6 // sari la instruc?iunile de mers în jos
LDA 2
STA [0]
JGE 8 // sari la instruc?iunile de incrementare

// mergi în jos de la pasul 8 la pasul 12
LDA 3
STA [0]

// pa?i de incrementare
LDA [1000]
ADDA 1
STA [1000]

HLT

Edited December 10, 2015 by aa7670

catalyn_sss · December 14, 2015

A rezolvat cineva prima problema si ne poate trimite solutia ?

tjt · December 14, 2015

A rezolvat cineva prima problema si ne poate trimite solutia ?

E la fel ca in exemplu. Eu am rezolvat asa:


LDA [1]
SUBA 7
JGE 6
LDA 3
STA [0]
JGE 8
LDA 2
STA [0]
LDA [1]
ADDA 1
STA [1]
HLT

tjt · December 17, 2015

Destul de urat modul in care s-a desfasurat competitia anul acesta. Au fost publicate ultimele harti cu o zi inainte de terminarea concursului si nici macar nu s-a anuntat pe email.

A fost mult mai usor ca anul trecut, dar mi se pare ca organizarea a lasat de dorit.

Oricum a fost interesant.

nardini · December 29, 2015

concursurile lor , viitorul armatei americane :)) ))

Sign In

Amazon TechO(n) Challenge

Recommended Posts

QuoVadis

Zatarra

tjt

Zatarra

tjt

QuoVadis

Zatarra

tjt

QuoVadis

catalyn_sss

tjt

tjt

nardini

Join the conversation

Browse

Activity

Pages