[Challenge] Find the numbers - programming

MrGrj · May 27, 2015

Se da urmatoarea poza:

Se cer:

- rezolvarea sirului prin orice metoda ( backtracking / recursivitate / bruteforce / etc ), in orice limbaj de programare
- o solutie cu o complexitate cat mai mica si un run-time cat mai mic
- doar siruri de numere naturale de la 1 la 9
- combinatii cerute: 10.

CONDITII:

- postati aici codul + print cu timpul de rulare al programului si cele 10 combinatii cerute mai sus.

Castiga cel care reuseste sa genereze 10 combinatii corecte care sa se potriveasca pattern-ului din poza + complexitate cat mai mica + run-time cat mai mic.

Bafta !

SOLVERS:

- @shaggi - (solutie bruteforce / PHP - timp de executie ~ 0.0072510242462)

Edited May 28, 2015 by MrGrj

Byte-ul · May 27, 2015

Rulat de 50 de ori.... de fiecare data fiind aflate combinatiile de 1000 de ori (timpul era prea mic si era aratat ca 0 )

Deci timpul e valoarea afisata impartita la 1000. (sper sa nu vorbesc prostii)

Codul: [C++] cucu - Pastebin.com

Ganav · May 27, 2015

@Byte-ul

Ai putea folosi:


std::cin.get();

pentru a "opri" aplicatia.

MasterLight · May 27, 2015

.

Edited July 5, 2016 by MasterLight

mah_one · May 27, 2015

mie mi-a dat:

--- 0.00197815895081 seconds ---

shaggi · May 27, 2015

E super usor de facut, cea mai usoara metoda e bruteforce. Cea mai rapida e tot bruteforce:))

shaggi@leet:~$ while(true) do time php a.php ; done;7 + 13 * 4 / 2 + 9 + 12 * 4 - 6 - 11 + 7 * 3 / 7 - 10 == 66


real	0m0.108s
user	0m0.084s
sys	0m0.020s
0 + 13 * 6 / 6 + 4 + 12 * 6 - 2 - 11 + 0 * 4 / 6 - 10 == 66


real	0m0.066s
user	0m0.056s
sys	0m0.012s
8 + 13 * 9 / 4 + 4 + 12 * 4 - 3 - 11 + 1 * 3 / 4 - 10 == 66


real	0m0.052s
user	0m0.040s
sys	0m0.008s
2 + 13 * 0 / 1 + 5 + 12 * 7 - 4 - 11 + 2 * 0 / 0 - 10 == 66


real	0m0.085s
user	0m0.060s
sys	0m0.020s
4 + 13 * 6 / 6 + 9 + 12 * 5 - 7 - 11 + 6 * 8 / 6 - 10 == 66


real	0m0.099s
user	0m0.072s
sys	0m0.024s
7 + 13 * 9 / 9 + 6 + 12 * 5 - 4 - 11 + 1 * 5 / 1 - 10 == 66


real	0m0.089s
user	0m0.052s
sys	0m0.040s
5 + 13 * 5 / 1 + 2 + 12 * 1 - 9 - 11 + 8 * 6 / 4 - 10 == 66


real	0m0.090s
user	0m0.060s
sys	0m0.028s
3 + 13 * 7 / 7 + 3 + 12 * 5 - 1 - 11 + 7 * 9 / 7 - 10 == 66


real	0m0.071s
user	0m0.056s
sys	0m0.012s
^C
real	0m0.097s
user	0m0.080s
sys	0m0.012s


shaggi@leet:~$ cat a.php
<?php
while(true){
$a = array();
for($i=0;$i <= 9;$i++)
	$a[] = rand(0,9);
if(@($a[0] + 13 * $a[1] / $a[2] + $a[3] + 12 * $a[4] - $a[5] - 11 + $a[6] * $a[7] / $a[8] - 10 ) == 66){
echo $a[0]." + 13 * ".$a[1]." / ". $a[2]." + ".$a[3]." + 12 * ".$a[4]." - ".$a[5]." - 11 + ".$a[6]." * ".$a[7]." / ".$a[8]." - 10 ";
	echo "== 66\n";
	die();
}else{
	//echo "!== 66\n";
	}
}
shaggi@leet:~$

Erase · May 28, 2015


2 + 13 * 7 / 2 + 4 + 12 * 3 - 2 - 11 + 1 * 8 / 4 - 10   0.0003
2 + 13 * 1 / 6 + 7 + 12 * 6 - 4 - 11 + 8 * 1 / 1 - 10   0.0003
8 + 13 * 7 / 6 + 4 + 12 * 5 - 2 - 11 + 4 * 5 / 7 - 10   0.0003
7 + 13 * 1 / 2 + 6 + 12 * 6 - 7 - 11 + 5 * 3 / 4 - 10   0.0003
4 + 13 * 7 / 8 + 1 + 12 * 6 - 4 - 11 + 2 * 3 / 2 - 10   0.0003
1 + 13 * 1 / 2 + 6 + 12 * 4 - 6 - 11 + 4 * 8 / 1 - 10   0.0003
6 + 13 * 7 / 7 + 1 + 12 * 5 - 3 - 11 + 5 * 2 / 1 - 10   0
3 + 13 * 4 / 3 + 8 + 12 * 3 - 7 - 11 + 6 * 5 / 1 - 10   0.0003
2 + 13 * 6 / 5 + 5 + 12 * 4 - 7 - 11 + 7 * 7 / 2 - 10   0.0003
3 + 13 * 6 / 7 + 1 + 12 * 6 - 2 - 11 + 4 * 4 / 7 - 10   0.0003
6 + 13 * 4 / 6 + 3 + 12 * 6 - 6 - 11 + 4 * 8 / 8 - 10   0.0003

do
{
    sw = Stopwatch.StartNew();
    for (int i = 0; i <= 8; i++)
     v[i] = rnd.Next(1, 9);
    try
    {
     total = v[0] + 13 * v[1] / v[2] + v[3] + 12 * v[4] - v[5] - 11 + v[6] * v[7] / v[8] - 10;
    }
    catch (DivideByZeroException) { }

    if (total == 66)
    {
     times++;
     sw.Stop();

     Console.WriteLine(string.Format(
      "{0} + 13 * {1} / {2} + {3} + 12 * {4} - {5} - 11 + {6} * {7} / {8} - 10 {9}",
      v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], sw.Elapsed.TotalMilliseconds));
    }
} while (times <= 10);

mah_one · May 28, 2015

Voi nu ati tinut cont de niste lucruri....

Cand se face impartirea, trebuie sa luati float, ca daca luati int nu e buna solutia data de voi!

Cum ati scris voi asa, ar fi 27.645 de solutii, le-am facut un count.

Spre exemplu, am sa va arat ce s-a dat mai sus si rezultatul:

2 + 13 * 7 / 2 + 4 + 12 * 3 - 2 - 11 + 1 * 8 / 4 - 10 = 66.5

2 + 13 * 1 / 6 + 7 + 12 * 6 - 4 - 11 + 8 * 1 / 1 - 10 = 66.1(6)

6 + 13 * 4 / 6 + 3 + 12 * 6 - 6 - 11 + 4 * 8 / 8 - 10 = 66.(6)

...........

Daca lucrati cu float o sa aveti 258 de solutii in care gasiti rezultatul 66.0

z0 + (13*z1/z2) + z3 + 12*z4 – z5 -11 + (z6*z7/z8) - 10= 67

Daca puneti conditia (cum am pus si eu) ca cele doua impartitiri 13*z1%z2 == 0 si a doua impartire (z6*z7)%z8 == 0

O sa fie in jur de 50 de rezultate...

Voi ce faceti le gasiti pe primele 10 din cele 27.645 de solutii.... Eu le gasesc pe primele 10 din cele 50 de solutii..

Edited May 28, 2015 by mah_one

MrGrj · May 28, 2015

Voi nu ati tinut cont de niste lucruri....
Cand se face impartirea, trebuie sa luati float, ca daca luati int nu e buna solutia data de voi!
Cum ati scris voi asa, ar fi 27.645 de solutii, le-am facut un count.
Spre exemplu, am sa va arat ce s-a dat mai sus si rezultatul:
2 + 13 * 7 / 2 + 4 + 12 * 3 - 2 - 11 + 1 * 8 / 4 - 10 = 66.5
2 + 13 * 1 / 6 + 7 + 12 * 6 - 4 - 11 + 8 * 1 / 1 - 10 = 66.1(6)
6 + 13 * 4 / 6 + 3 + 12 * 6 - 6 - 11 + 4 * 8 / 8 - 10 = 66.(6)
...........
Daca lucrati cu float o sa aveti 258 de solutii in care gasiti rezultatul 66.0
z0 + (13*z1/z2) + z3 + 12*z4 – z5 -11 + (z6*z7/z8) - 10= 67
Daca puneti conditia (cum am pus si eu) ca cele doua impartitiri 13*z1%z2 == 0 si a doua impartire (z6*z7)%z8 == 0
O sa fie in jur de 50 de rezultate...
Voi ce faceti le gasiti pe primele 10 din cele 27.645 de solutii.... Eu le gasesc pe primele 10 din cele 50 de solutii..

Corect

Byte-ul · May 28, 2015

Voi nu ati tinut cont de niste lucruri....
Cand se face impartirea, trebuie sa luati float, ca daca luati int nu e buna solutia data de voi!
Cum ati scris voi asa, ar fi 27.645 de solutii, le-am facut un count.
Spre exemplu, am sa va arat ce s-a dat mai sus si rezultatul:
2 + 13 * 7 / 2 + 4 + 12 * 3 - 2 - 11 + 1 * 8 / 4 - 10 = 66.5
2 + 13 * 1 / 6 + 7 + 12 * 6 - 4 - 11 + 8 * 1 / 1 - 10 = 66.1(6)
6 + 13 * 4 / 6 + 3 + 12 * 6 - 6 - 11 + 4 * 8 / 8 - 10 = 66.(6)
...........
Daca lucrati cu float o sa aveti 258 de solutii in care gasiti rezultatul 66.0
z0 + (13*z1/z2) + z3 + 12*z4 – z5 -11 + (z6*z7/z8) - 10= 67
Daca puneti conditia (cum am pus si eu) ca cele doua impartitiri 13*z1%z2 == 0 si a doua impartire (z6*z7)%z8 == 0
O sa fie in jur de 50 de rezultate...
Voi ce faceti le gasiti pe primele 10 din cele 27.645 de solutii.... Eu le gasesc pe primele 10 din cele 50 de solutii..

Unde zice ca impartirea trebuie facuta exact? Ideea e sa ajungi la rezultatul ala. (adica 66.0) @MrGrj solutia mea e cea mai rapida Timpii care apar in consola sunt pentru 1000 de rulari.

MrGrj · May 28, 2015

Afla timpul a 10 rulari @Byte-ul si posteaza aici. Nu am timp acum sa verific C++. Python mi-a fost la-ndemana ca-l folosesc la munca.

Byte-ul · May 28, 2015

Afla timpul a 10 rulari @Byte-ul si posteaza aici. Nu am timp acum sa verific C++. Python mi-a fost la-ndemana ca-l folosesc la munca.

E prea rapid si apare 0. Nu stiu sa-l fac sa arate mai exact de atat.

shaggi · May 28, 2015

Deci cele mai multe combinatii se afla intre numerele 5-7, deci daca facem bruteforce doar pe astea, o sa gasim solutii in sub 100 de combinatii, ceea ce e foarte rapid pe langa a face bruteforce pe 1-9. Niste testem gasiti mai jos.

10 combinatii de numere de la 1-9 per fiecare rulare, si timpi rulari.

shaggi@programare:~$ while(true) do php a.php; done;
1432804277.0644 - 1432804277.0113 = 0.053034067153931
1432804277.1582 - 1432804277.1135 = 0.04463005065918
1432804277.2761 - 1432804277.1895 = 0.086684942245483
1432804277.3591 - 1432804277.3136 = 0.045469045639038
1432804277.429 - 1432804277.3904 = 0.038651943206787
1432804277.4997 - 1432804277.4628 = 0.036898136138916
1432804277.5574 - 1432804277.5301 = 0.027316093444824
1432804277.6132 - 1432804277.5879 = 0.025299072265625
1432804277.701 - 1432804277.6482 = 0.052848815917969
1432804277.7724 - 1432804277.7317 = 0.040709018707275
1432804277.8377 - 1432804277.8026 = 0.03516411781311
1432804277.9086 - 1432804277.8717 = 0.036844968795776
1432804277.9782 - 1432804277.9405 = 0.037657022476196
1432804278.0524 - 1432804278.0172 = 0.035200119018555
1432804278.1596 - 1432804278.0828 = 0.076802968978882
1432804278.2133 - 1432804278.1946 = 0.018671989440918
1432804278.2881 - 1432804278.2473 = 0.040793895721436
1432804278.3645 - 1432804278.3248 = 0.039740085601807
1432804278.4189 - 1432804278.3983 = 0.020576953887939
1432804278.4868 - 1432804278.4535 = 0.033290147781372
1432804278.5854 - 1432804278.5195 = 0.065865039825439
1432804278.6812 - 1432804278.6218 = 0.05939793586731
1432804278.7793 - 1432804278.7165 = 0.062873840332031
1432804278.8685 - 1432804278.815 = 0.05351996421814
1432804278.9532 - 1432804278.9055 = 0.047666072845459
1432804279.0292 - 1432804278.9875 = 0.041703939437866
1432804279.1394 - 1432804279.0602 = 0.079138040542603
1432804279.2078 - 1432804279.1795 = 0.028285026550293
1432804279.2679 - 1432804279.2387 = 0.029206991195679

10 combinatii de la 5-7 per fiecare rulare, si timpi rulari

shaggi@programare:~$ while(true) do php a.php; done;
1432804348.8132 - 1432804348.8059 = 0.0072789192199707
1432804348.8579 - 1432804348.8494 = 0.0085098743438721
1432804348.8963 - 1432804348.8891 = 0.0072510242462158
1432804348.9438 - 1432804348.9329 = 0.010945081710815
1432804348.9802 - 1432804348.9762 = 0.0039839744567871
1432804349.0276 - 1432804349.0167 = 0.010900020599365
1432804349.0657 - 1432804349.0595 = 0.0062358379364014
1432804349.11 - 1432804349.1009 = 0.0090839862823486
1432804349.1576 - 1432804349.1508 = 0.0068058967590332
1432804349.2046 - 1432804349.1963 = 0.0082898139953613
1432804349.2473 - 1432804349.2413 = 0.0060479640960693
1432804349.2941 - 1432804349.2865 = 0.0076580047607422
1432804349.3334 - 1432804349.3281 = 0.0052459239959717
1432804349.3703 - 1432804349.3653 = 0.0050420761108398
1432804349.413 - 1432804349.4046 = 0.0083949565887451
1432804349.4581 - 1432804349.4504 = 0.0077629089355469
1432804349.5009 - 1432804349.4918 = 0.009105920791626
1432804349.5383 - 1432804349.5334 = 0.0048370361328125
1432804349.5728 - 1432804349.5692 = 0.0035660266876221
1432804349.6163 - 1432804349.6079 = 0.0084130764007568
1432804349.6542 - 1432804349.6479 = 0.0063669681549072
1432804349.7018 - 1432804349.6927 = 0.0091378688812256
1432804349.7499 - 1432804349.742 = 0.0079410076141357

 <?php $tt = microtime(true); for($j=0;$j<10;$j++){ $mom = true; while($mom - Pastebin.com

Erase · May 28, 2015

Op, poti sa-mi explici de ce in calculele tale 00:00:00.0000003 > 0:00:00.000323 ?

LE: @MrGrj, daca nu ai specificat ca vrei ca rezultat valoare exacta, toate solutiile de mai sus sunt corecte.

Edited May 28, 2015 by Erase

soimuletzu1 · May 28, 2015

Am incercat si eu ceva in js ...

Edit fiddle - JSFiddle

In chrome:


66=9+13*8/8+4+12*5-8-11+9*2/2-10
66=2+13*4/2+2+12*5-7-11+7*4/7-10
66=4+13*9/9+5+12*4-7-11+8*9/3-10
66=7+13*5/5+4+12*5-2-11+6*5/6-10
66=6+13*4/1+7+12*2-5-11+3*8/8-10
66=6+13*6/7+4+12*6-7-11+6*1/7-10
66=5+13*3/1+9+12*2-4-11+8*7/4-10
66=6+13*8/4+6+12*4-3-11+4*5/5-10
66=9+13*9/2+1+12*2-8-11+5*3/6-10
66=4+13*3/1+9+12*3-8-11+7*2/2-10
Execution time:  0.038752000022213906  seconds

In ie:

Execution time: 0.004737778176329044 seconds

Edited May 28, 2015 by soimuletzu1

MrGrj · May 28, 2015

Op, poti sa-mi explici de ce in calculele tale 00:00:00.0000003 > 0:00:00.000323 ?

Nu, dar pot sa iti explic altceva :

Uite rezultatul primei solutii gasite de tine:

2 + 13 * 7 / 2 + 4 + 12 * 3 - 2 - 11 + 1 * 8 / 4 - 10 = 66.5

Uite si la a doua:

2 + 13 * 1 / 6 + 7 + 12 * 6 - 4 - 11 + 8 * 1 / 1 - 10 = 66.1666666666666667

Daca nu ai ascultat nimeni sfatul lui @Erase - valoarea tre' sa fie exact 66. Credeam ca se intelege destul de clar din cerinta. Primele sunt false deci nu ai cum sa imi spui ca solutiile tale sunt adevarate. Ia in considerare asta si adauga niste conditii.

Edited May 28, 2015 by MrGrj

Erase · May 28, 2015

"Castiga cel care reuseste sa genereze 10 combinatii corecte care sa se potriveasca pattern-ului din poza + complexitate cat mai mica + run-time cat mai mic."

Hai sa fim seriosi, din descrierea acestui post se intelege ca vrei sa determinam numerele care dau ca rezultat acel numar, corect este, exact nu.

exact != corect

In fine.

float total;

if(total == 66.0)

//whatever

Sign In

[Challenge] Find the numbers - programming

Recommended Posts

MrGrj

Byte-ul

Ganav

MasterLight

mah_one

shaggi

Erase

mah_one

MrGrj

Byte-ul

MrGrj

Byte-ul

shaggi

Erase

soimuletzu1

MrGrj

Erase

Join the conversation

Browse

Activity

Pages