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
Kommentit 35
Kommentointi on päättynyt.
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
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
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
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
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
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
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.
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.
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
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/