Helmikuun koodauspähkinä

Matemaattiset ohjelmointipähkinät ovat siitä mielenkiintoisia, että ne on yleensä helppo määritellä, mutta ratkaisu saattaa osoittautua yllättävän hankalaksi. Haastamme blogin lukijat nyt ratkomaan seuraavaa pintapuolisesti yksinkertaista ongelmaa:

Jaa luvut sqrt(1), sqrt(2), … , sqrt(100) kahteen osaan siten, että osien summat ovat mahdollisimman lähellä toisiaan.

Esimerkiksi laittamalla parillisten lukujen neliöjuuret yhteen joukkoon ja parittomien toiseen joukkoon, saadaan osien summiksi noin 338,05 ja 333,42, ja eroa jää noin 4,63.

Pystytkö parempaan? Koodaa ohjelma, joka etsii mahdollisimman hyvän ratkaisun, ja postaa tuloksesi kommentteihin!

Jarno Niklas Alanko
Toimittaja, Skrolli

Sol_HSA

sqrt(57)+sqrt(58)+sqrt(59)+sqrt(60)+sqrt(61)+sqrt(62)+sqrt(63)+sqrt(64)+sqrt(65)+sqrt(66)+sqrt(67)+sqrt(68)+sqrt(72)+sqrt(73)+sqrt(74)+sqrt(76)+sqrt(77)+sqrt(78)+sqrt(79)+sqrt(80)+sqrt(81)+sqrt(83)+sqrt(84)+sqrt(85)+sqrt(86)+sqrt(87)+sqrt(88)+sqrt(89)+sqrt(90)+sqrt(91)+sqrt(92)+sqrt(93)+sqrt(94)+sqrt(95)+sqrt(96)+sqrt(97)+sqrt(98)+sqrt(99)

delta noin 0


Jarno Niklas Alanko

Delta = 7.302485232685285e-05. Löytyykö parempaa?


Sol_HSA

Vastasi Jarno Niklas Alanko'n kommenttiin 8.2.2018 14:23

sqrt(15) + sqrt(54) + sqrt(55) + sqrt(56) + sqrt(57) + sqrt(58) + sqrt(59) + sqrt(60) + sqrt(61) + sqrt(62) + sqrt(63) + sqrt(64) + sqrt(65) + sqrt(66) + sqrt(67) + sqrt(68) + sqrt(70) + sqrt(71) + sqrt(74) + sqrt(75) + sqrt(79) + sqrt(80) + sqrt(82) + sqrt(85) + sqrt(86) + sqrt(87) + sqrt(88) + sqrt(89) + sqrt(90) + sqrt(91) + sqrt(92) + sqrt(93) + sqrt(94) + sqrt(95) + sqrt(96) + sqrt(97) + sqrt(98) + sqrt(99) + sqrt(100)=335.731 (delta 2.38419e-007)


Sol_HSA

Vastasi Jarno Niklas Alanko'n kommenttiin 8.2.2018 14:55

Hah, löysin koodistani bugin joka esti täysin oikeiden vastauksien löytymisen (eli etsittiin aina lähellä olevaa, mutta ei tarkkaa). ”Oikeita” vastauksia on iso läjä – ainakin doublen tarkkuudella..

Tässä vähän lähestymistä ja sitten muutama nollatulos:

[1, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]=335.332 (delta 0.399182)

[11, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.586 (delta 0.145303)

[3, 63, 64, 65, 66, 67, 68, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]=335.695 (delta 0.0365003)

[15, 62, 63, 64, 65, 66, 67, 68, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.710 (delta 0.02156)

[16, 62, 63, 64, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.717 (delta 0.0140693)

[13, 60, 61, 62, 63, 64, 65, 66, 67, 68, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]=335.721 (delta 0.0108058)

[4, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]=335.726 (delta 0.00593114)

[38, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 71, 72, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.726 (delta 0.00569606)

[41, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.726 (delta 0.00519252)

[38, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 71, 73, 74, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.727 (delta 0.0049026)

[12, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 74, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]=335.728 (delta 0.00310755)

[12, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 72, 73, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]=335.729 (delta 0.00229788)

[41, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70, 71, 73, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.730 (delta 0.0019176)

[12, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 72, 74, 75, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]=335.730 (delta 0.00151968)

[41, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70, 71, 74, 75, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.730 (delta 0.0011394)

[12, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, 72, 73, 75, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]=335.731 (delta 0.000292301)

[34, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70, 71, 72, 73, 74, 75, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.731 (delta 0.000137568)

[44, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 76, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]=335.731 (delta 0.000123739)

[52, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 72, 73, 75, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]=335.731 (delta 6.8903e-005)

[2, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 71, 72, 73, 75, 78, 79, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.731 (delta 5.126e-006)

[13, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 73, 76, 81, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]=335.731 (delta 3.09944e-006)

[14, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, 73, 74, 75, 76, 81, 82, 83, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.731 (delta 2.86102e-006)

[15, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70, 71, 74, 75, 79, 80, 82, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]=335.731 (delta 2.38419e-007)

[30, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70, 71, 73, 76, 78, 79, 80, 81, 82, 84, 86, 87, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.731 (delta 2.38419e-007)

[42, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, 73, 74, 77, 80, 82, 83, 84, 87, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]=335.731 (delta 2.38419e-007)

[42, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 72, 73, 74, 80, 82, 86, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]=335.731 (delta 2.38419e-007)

[50, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70, 74, 75, 76, 77, 78, 80, 82, 84, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.731 (delta 2.38419e-007)

[47, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 77, 78, 79, 80, 81, 83, 84, 85, 87, 88, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.731 (delta 2.38419e-007)

[50, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 71, 73, 74, 76, 77, 78, 81, 83, 84, 85, 87, 88, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.731 (delta 2.38419e-007)

[27, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70, 73, 76, 77, 82, 84, 85, 87, 88, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.731 (delta 2.38419e-007)

[14, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 75, 83, 86, 88, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]=335.731 (delta 0)

[12, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 73, 74, 75, 76, 77, 81, 82, 86, 87, 88, 89, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.731 (delta 0)

[8, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 76, 79, 80, 82, 85, 87, 88, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.731 (delta 0)

[8, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70, 71, 72, 74, 77, 79, 81, 82, 83, 84, 87, 88, 89, 92, 93, 94, 95, 96, 97, 98, 99]=335.731 (delta 0)

[8, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 72, 73, 77, 78, 80, 82, 83, 84, 85, 88, 89, 92, 93, 94, 95, 96, 97, 98, 99, 100]=335.731 (delta 0)

[12, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 73, 74, 79, 80, 81, 82, 83, 84, 89, 92, 93, 94, 95, 96, 97, 98, 99]=335.731 (delta 0)

[5, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 75, 78, 80, 81, 83, 85, 92, 93, 94, 95, 96, 97, 98, 99]=335.731 (delta 0)

[8, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 74, 75, 78, 79, 81, 82, 84, 85, 86, 88, 89, 90, 91, 93, 94, 95, 96, 97, 98, 99]=335.731 (delta 0)

[8, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 74, 76, 78, 80, 81, 82, 83, 86, 89, 91, 93, 94, 95, 96, 97, 98, 99, 100]=335.731 (delta 0)

[5, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 73, 75, 77, 78, 79, 81, 89, 91, 93, 94, 95, 96, 97, 98, 99, 100]=335.731 (delta 0)

[5, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 78, 80, 81, 83, 85, 86, 87, 91, 93, 94, 95, 96, 97, 98, 99]=335.731 (delta 0)


Jarno Niklas Alanko

Onkohan koodissasi joku tarkkuusongelma? Minä saan vielä esimerkiksi viimeisestä ratkaisustasi ei-nollan erotuksen.

>>> total = sum([math.sqrt(x) for x in range(1,101)])
>>> A = [5, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 78, 80, 81, 83, 85, 86, 87, 91, 93, 94, 95, 96, 97, 98, 99]
>>> sum([math.sqrt(x) for x in A]) – total/2
2.449795601933147e-07


Sol_HSA

Vastasi Jarno Niklas Alanko'n kommenttiin 8.2.2018 15:33

Luultavasti kyllä. Konvertoin nyt double-laskennan GMP:lle ja annan sen ruksuttaa jonkin aikaa josko tulisi tarkempaa tulosta.. viimeisin sieltä ulostullut on

[19, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 76, 77, 80, 81, 82, 83, 84, 86, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]=335.731 (delta 4.97368e-08)


Lumi

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


Sol_HSA

Miten lähestyit ongelmaa?


Lumi

Sekoitin luvut, jaoin kahteen osaan ja siirtelin alkioita yhdestä joukosta toiseen satunnaisesti, jos summien erotus pieneni. Tuloksena jokin lokaali minimi. Toistin tätä eri sekoituksilla, kunnes kyllästyin tuulettimen huutoon.
Menetelmää voisi parantaa jollakin simulated annealing – strategialla, joka tekee siirron pienellä todennäköisyydellä, vaikka erotus kasvaisikin.


Sol_HSA

Lähdin vanhasta kunnon levykkeentäyttöongelmasta: sulla on kovalevyllä hakemisto jossa on joku tuhat erkokoista filettä, ja se pitää saada kopsittua mahdollisimman vähään 1.44 megan korppuun. Joten mikä on fiksuin strategia?

Helppo aloitus on kopsia ensin niin isoja fileitä kuin mahdollista, ja sitten koittaa ahtaa pienempiä perään. Tällä päästiin deltaan 0.3992 (sqrt 1 ja 64..100).

Mutta optimaalisempiakin ratkaisuja voi olla, jos pari pienempää sattuu sopimaan paremmin kuin yksi iso; joten rakensin brute-force tarkistuksen joka jättää isoimmasta alkaen aina jonkun pois ja sitten ajaa tuon saman täyttösysteemin. Odotin että tuo ajaisi tunteja, mutta löysikin hetkessä ainakin yhden ratkaisun jossa floatin tarkkuudella ollaan nollassa.

Eiköhän tähän ole fiksumpiakin ratkaisuja mutta ainakin tuolla meni..


Pastori

Pikaratkaisuna kokeilin niin, että lasketaan 100 alaspäin neliöjuuria ja lisätään tulos kahdesta summasta pienempään. Yllättävän lähelle meni:
335.850189929029
335.612757174119


Jami

Pienin delta mihin pääsin on 9.52620666794246e-8, seuraavilla jaoilla:

[33, 8, 11, 46, 58, 61, 78, 39, 74, 68, 6, 38, 35, 1, 37, 76, 80, 43, 88, 49, 79, 91, 2, 5, 47, 95, 92, 28, 90, 36, 25, 69, 51, 42, 67, 62, 27, 89, 32, 81, 40, 82, 14, 19, 60, 54, 13, 12, 98, 17]

[31, 41, 7, 86, 57, 3, 63, 83, 26, 22, 65, 29, 4, 77, 34, 71, 24, 100, 73, 53, 97, 93, 18, 52, 30, 87, 15, 75, 20, 44, 84, 10, 94, 72, 85, 66, 56, 23, 16, 59, 45, 96, 50, 21, 48, 99, 9, 64, 55, 70]


Jarno Niklas Alanko

Koodissasi on bugi. Erotus on paljon isompi:

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


Jami

Vastasi Jarno Niklas Alanko'n kommenttiin 8.2.2018 16:29

Hupsista! Tulos oli oikea, mutta listat väärät. Tässä oikeat vähän pienemmällä erotuksella (3.7220956983219367e-8):

[85,31,71,89,82,43,95,33,72,57,41,37,93,84,3,50,86,15,83,42,6,60,61,20,76,64,75,87,47,91,32,9,49,8,81,22,25,7,1,63,44,26,40,21,5,58,12,24,54,79,59]

[45,18,52,99,13,88,2,27,34,35,65,30,100,69,80,98,92,90,48,51,23,73,55,29,46,14,36,28,74,78,19,96,56,70,17,77,16,62,10,67,39,68,94,4,97,53,11,66,38]


Heikki

>> skrollibruteforce
0.97737
0.0061169
0.0017223
0.0016555
6.6562e-004
2.4706e-004
7.1945e-005
4.9077e-005
2.9620e-005
1.5995e-005
1.2611e-006


Heikki

Vastasi Heikki'n kommenttiin 8.2.2018 15:48

Voiko bruteforcella saada tähän ongelmaan ratkaisun? Ei voi.

Ongelmassa on 9.332621544E+157 permutaatiota
Yhdellä koneella tekee n. 2.2456e+004 yritystä sekunnissa

Toisin sanottuna koko permutaatioavaruuden läpikäynti kestäisi: 1.317846e+146 vuotta.

Vertailun vuoksi universumimme ikä on vain: 1.38E+10 vuotta


Sol_HSA

Vastasi Heikki'n kommenttiin 8.2.2018 16:50

Pienin määrä lukuja joilla pääsee yli puolivälin on 38. Eli jos lähtee laskemaan yhteen kaikkia arvoja suurimmasta pienimpään, lisätessä 38 kerran (eli sqrt(63)) mennään yli puolen välin.

Näinollen permutaatioiden määrä lähtee siitä että mitkä noista 37 arvoista EI ole mukana ”suuremmassa puolikkaassa”. Permutaatioiden määrä on siis jotain luokkaa 2^36, joka on vielä ihan jauhettavissa..


PJS Inc.

Vastasi Heikki'n kommenttiin 8.2.2018 17:03

Yhdellä stepillä tuota voi kovasti yksinkertaistaa. Jos joukot ovat samansuuruiset niin yhden joukon summa on silloin tasan (sqrt(1)+…sqrt(100)) / 2. Lasketaan tuo arvo ensiksi, ja sitten muodostetaan vain 50 alkion joukkoja ja verrataan eroa tuohon samansuuruisten arvoon. Ei tarvi siirrellä alkioita joukoista toiseen, koska toisen joukon summa on vastaavan kaukana, mutta erimerkkinen, sen ensimmäisen joukon summaan verrattuna. On niitä permutaatiota silti paljon (3.068518756E+93)…


PJS Inc.

Vastasi PJS Inc.'n kommenttiin 8.2.2018 17:07

Ja näinhän se Sol_HSA onkin sen jo laskenutkin. Ja hyvä huomio noista ylisuurista summista jotka voidaan karsia pois jo lähtövaiheessa.


Heikki

Vastasi PJS Inc.'n kommenttiin 8.2.2018 17:28

Aivan totta, tajusin itsekin hieman postaukseni jälkeen.
Ekana lähdin vain kokeilemaan simppeleintä mahdollista bruteforcea:
while delta > 0
x = randperm(100);
x1 = x(1,1:50);
x2 = x(1,51:100);
delta = abs(sum(sqrt(x1)) – sum(sqrt(x2)));

(joo, random-permutaatio on tietenkin täysin tehoton, mutta riittävän monta apinaa jne.)

Sitten rupesin laskemaan kuinka suuri tuo ”bruteforce”-kenttä oikein onkaan (riittävän suuri).

Tuolla tyhmällä ”random-permutaatio-bruteforcella” pääsi jo muutamassa minuutissa tarkkuuteen jonka postasinkin yläpuolella (1.2611e-006).


Sol_HSA

[27, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, 72, 73, 75, 76, 79, 80, 83, 84, 89, 91, 92, 94, 95, 96, 97, 98, 99, 100]=335.731 (delta 8.63793e-09)


Jarno Niklas Alanko

Ding ding, tähän mennessä paras ratkaisu. Ratkaisujen vertailukelpoisuuden vuoksi täytyy huomioida, että ilmeisesti raportoimasi delta on erotus optimaaliseen puolikkaaseen, mutta tehtävänannossa kysytään osien välistä etäisyyttä, joka on kaksi kertaa isompi:

>>> A = [27, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, 72, 73, 75, 76, 79, 80, 83, 84, 89, 91, 92, 94, 95, 96, 97, 98, 99, 100]
>>> B = [x for x in range(1,101) if x not in A]
>>> abs(sum([math.sqrt(x) for x in A]) – sum([math.sqrt(x) for x in B]))
1.7275908703595633e-08


Sol_HSA

Ah, totta puhut. Piirun verran parempi tulos tullut ulos sittemmin..

[17, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, 74, 75, 76, 79, 84, 85, 90, 93, 95, 96, 97, 98, 99]=335.731 (delta 4.96302e-09)

(ja tuossa edelleen puolikas delta)


Jami

2.466663318045903e-9, löytyykö vielä pienempää?

[7,23,97,79,60,15,36,94,34,88,10,67,58,87,42,31,69,89,25,91,39,28,62,14,52,78,5,61,98,92,21,73,47,46,53,30,55,48,33,76,72,27,84,99,4,49,64,57]

[2,13,86,66,35,3,74,75,65,77,96,22,38,6,81,100,41,11,68,50,19,12,54,37,83,43,16,71,24,82,20,29,45,32,26,51,1,18,40,93,80,9,8,59,95,90,63,70,85,17,44,56]


pekka

Ratkaisu Karmarkar-Karpin algoritmillä.

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

Delta: 5.16369760816815e-06


Sol_HSA

[21, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70, 71, 73, 74, 76, 79, 86, 87, 89, 90, 92, 94, 95, 97, 98, 99, 100]=335.731 (delta 4.72196e-10)

..taas puolikas delta, eli delta olisi 9.44392e-10

(en viitsi käynnistää tuota ajoa alusta =)


sisu

>>> A = [2, 3, 6, 7, 8, 14, 15, 16, 18, 19, 20, 23, 24, 25, 26, 27, 28, 35, 36, 40, 41, 42, 44, 45, 47, 48, 55, 60, 61, 62, 64, 65, 66, 70, 72, 73, 75, 77, 80, 82, 84, 86, 88, 90, 91, 93, 94, 95, 96, 97]
>>> B = [x for x in range(1,101) if x not in A]
>>> abs(sum([math.sqrt(x) for x in A]) – sum([math.sqrt(x) for x in B]))
5.684341886080802e-14


Sol_HSA

Miten lähestyit ongelmaa?


sisu

Aloin ratkomaan siitä lähtökohdasta, että vaikuttaa mahdottomalta tehdä mitään kovin älykästä, joten paras ratkaisu on hyvin optimoitu bruteforce.

Esilaskin summat kaikille osajoukoille välillä 1..25 ja järjestin summat suuruusjärjestykseen taulukkoon. Sitten toistuvasti arvoin satunnaisesti luvut 26..100, ja etsin binäärihaulla optimaalisen vastauksen luvuille 1..25 esilasketusta taulukosta.

Näyttää että Pythonin oletustarkkuus loppuu kesken, joten pitää ottaa käyttöön enemmän desimaaleja tulosten vertaamiseksi.

>>> from decimal import Decimal, getcontext
>>> getcontext().prec = 30
>>> A = [3, 5, 6, 10, 11, 12, 15, 17, 20, 24, 26, 27, 29, 30, 31, 32, 35, 36, 38, 40, 41, 46, 49, 51, 53, 55, 60, 61, 63, 65, 66, 67, 68, 70, 72, 74, 75, 77, 82, 83, 84, 85, 88, 89, 90, 93, 95, 99, 100]
>>> B = [x for x in range(1,101) if x not in A]
>>> abs(sum([Decimal(x).sqrt() for x in A]) – sum([Decimal(x).sqrt() for x in B]))
Decimal(’4.792426516658E-15’)


Jarno Niklas Alanko

Kova tulos! 5 kertaluokkaa muita edellä tällä hetkellä.


Veikko Sariola

Matlab onelineri, joka ratkoo tehtävän geneettisillä algoritmeillä:

[b,f]=ga(@(x)abs(sum((x*2-1).*sqrt(1:100))),100,[],[],[],[],[],[],[],[],optimoptions(’ga’,’FunctionTolerance’,1e-10,’PopulationSize’,10000,’PopulationType’,’bitstring’))

Antaa ulos esimerkiksi:

b =

Columns 1 through 18

1 0 1 1 0 1 1 1 0 1 1 1 0 1 1 0 0 0

Columns 19 through 36

1 1 0 1 1 0 0 1 0 1 0 0 1 0 0 1 1 0

Columns 37 through 54

1 0 0 0 0 1 1 0 1 1 1 1 1 0 1 0 1 0

Columns 55 through 72

0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 1 1 1

Columns 73 through 90

0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 1 1

Columns 91 through 100

0 0 1 0 1 1 0 1 0 0

f =

3.0997e-05

b:n bitit tarkoittavat siis, kumpaan ryhmään luku kuuluu ja f on ryhmien välinen virhe. Pienentämällä toleranssia ja kasvattamalla populaatiokokoa ja odottelemalla pirusti pääsee vielä tarkempiin tuloksiin; pienin mitä jaksoin etsiä oli 1.1777e-06, mutta täällä on kommenteissa jo yksi 1e-8 ratkaisu, niin mitäpä suotta.


Sol_HSA

Vaikka sisun 4.79e-15 lienee paras tähänastinen niin annan tuon oman bruteforceni etsiskellä vielä.. tähän mennessä paras 3.12e-11..


sisu

Paransin vielä vähän koodinani niin että se valitsee vain 50 ylintä numeroa satunnaisesti ja optimoi alimmat numerot meet-in-the-middle-tekniikalla 2^25 askeleessa. Tällä tavalla löytyi 3.54e-17 ratkaisu,
[1, 2, 3, 5, 6, 10, 11, 14, 15, 18, 22, 26, 28, 32, 33, 36, 37, 39, 41, 42, 44, 45, 46, 49, 50, 51, 54, 55, 62, 63, 64, 65, 67, 68, 69, 70, 73, 75, 78, 79, 80, 82, 85, 88, 89, 92, 93, 96, 97, 99]


Sol_HSA

Aploodit =)

Jotenkin tuntuu että tuo ei vielä ole täysin paras mahdollinen tulos. Saattaa olla, mutta jos katsoo mitkä luvut menevät eri pinoon:

…’..”’..”..”.”’.”’.’.”’..”..’.’..’…”…”..”””….’….”.’.”…’.”.”..”..”..’.’

tuolla mennään 1-3 joukoissa (varsinkin alapäässä) ja 50:n yläpuolella on sitten kuuden ryhmä ja pari neljän ryhmää.. Jos tuon valtaosan ryhmittymät antaa vinkkiä siitä mikä olisi optimaalinen, luultavasti voisi hakea kaikki vaihtoehdot joissa vaihdetaan pinoa 1-3 välein ja löytää se paras sillä tavoin…

..tai sitten voi olla että tuo on jo se paras mahdollinen ja teorisoin tyhjää. =)


Janne Sirén

Julkaisimme koosteen ja kommentaarin parhaista ratkaisuista Skrollin 2018.1 pähkinänurkassa. Nyt tämä artikkeli on luettavissa vapaasti myös blogissa: https://skrolli.fi/2018/04/neliojuuritehtavan-jalkipyykki/


Kommentointi on päättynyt.