symbols kirjoitti:
$100 when you beat #15.
Anagrammit löytyvät sorttaamalla sanojen kirjaimet ja keräilemällä ryhmiinsä. Tehtävässä sallitut muunnokset taas ovat niitä joiden Levensteinin etäisyys on enintään yksi.
Löytyykö helpompi ratkaisu?
Google translate is failing me, I cannot understand your message.
#15 has two parts, the second one is non-trivial but beatable. The first part is very simple, I think that's what your post is about.
Opettelen suomea puolen vuoden ajan.
Great! I hope we will see improvements on the bounds.
jalski: Tehtävässä #15 (Kielitiedettä) sanojen yhdistely on helppo vaihe. Varsinainen ongelma on siitä jatkaminen: Yhdistelyn seurauksena saadaan suuri verkko. (Tiedostoistani löytyy verkko, jossa on 11266 solmua ja 44308 kaarta. Muistelen, että tämä olisi suurin yhtenäinen verkko sanalistassa.) Verkosta pitäisi etsiä pisin polku. Tämä tehtävä on NP-kova eli toistaiseksi vailla tehokasta ratkaisua. Vai onko PL/I:ssä tähänkin hyvä kikka?
Metabolix kirjoitti:
Vai onko PL/I:ssä tähänkin hyvä kikka?
Ehkä PL/I ei tähän olisi paras työkalu, kun taas 8th voisi toimia hyvin.
Alustava ajatus olisi ollut käydä sanalista läpi, sortata sanan kirjaimet ja tallentaa sana taulukon sisään mappiin käyttäen sorttausta avaimena. Sitten kävisin läpi avaimet ja ryhmittelisin yhteen kaikki, joiden Levensteinin etäisyys olisi enintään yksi.
Näistä ryhmistä lähtisin sitten muodostamaan mahdollisia sanaketjuja.
jalski, kuten jo sanoin, tuo tarkemmin kuvailemasi osa ratkaisusta on triviaali (joskin näyttää silti menevän kuvauksessasi jotenkin väärin), ja todelliset ongelmat alkavat vasta vaiheessa ”lähtisin sitten muodostamaan mahdollisia sanaketjuja”, koska vaihtoehtoja on ns. tähtitieteellinen määrä.
symbols kirjoitti:
(07.03.2018 17:22:13): $100 when you beat #15. $1000 if...
Should one spend time on beating your solutions, what guarantee is there of payment?
Metabolix kirjoitti:
...(joskin näyttää silti menevän kuvauksessasi jotenkin väärin), ja todelliset ongelmat alkavat vasta vaiheessa ”lähtisin sitten muodostamaan mahdollisia sanaketjuja”, koska vaihtoehtoja on ns. tähtitieteellinen määrä.
Millä tavalla väärin? Olemme varmaan kuitenkin samaa mieltä siitä, että anagrammit löytyvät sorttaamalla sanan kirjaimet. Nämä, kun tallentaa mappiin siten, että sortattu sana toimii avaimena ja arvona tomii taulukko, johon tallennetaan sanat joilla on sama avain (ovat sama sortattuna).
Nyt jos kerätään avaimet yhteen, joiden Levensteinin etäisyys on enintään yksi niin saadaan ryhmiä. Näissä ryhmissä on sanoja, joihin käytetyissä kirjaimissa voi olla enintään yhden kirjaimen ero.
Villi veikkaus on, että tähtitieteellistä määrää voi pienentää hiukan arvaamalla, että pisin sanaketju löytyy suurimmasta ryhmästä, jossa on eniten sanoja.
jalski kirjoitti:
Metabolix kirjoitti:
...(joskin näyttää silti menevän kuvauksessasi jotenkin väärin), ja todelliset ongelmat alkavat vasta vaiheessa ”lähtisin sitten muodostamaan mahdollisia sanaketjuja”, koska vaihtoehtoja on ns. tähtitieteellinen määrä.
Millä tavalla väärin? Olemme varmaan kuitenkin samaa mieltä siitä, että anagrammit löytyvät sorttaamalla sanan kirjaimet. Nämä, kun tallentaa mappiin siten, että sortattu sana toimii avaimena ja arvona tomii taulukko, johon tallennetaan sanat joilla on sama avain (ovat sama sortattuna).
Nyt jos kerätään avaimet yhteen, joiden Levensteinin etäisyys on enintään yksi niin saadaan ryhmiä. Näissä ryhmissä on sanoja, joihin käytetyissä kirjaimissa voi olla enintään yhden kirjaimen ero.
Esimerkiksi sanojen ALAS ja ALUS välinen etäisyys on 1, vaikka aakkostettujen anagrammiryhmien AALS ja ALSU välinen etäisyys on 2. Toisaalta sanojen NETTI ja TENTTI etäisyys on 2, vaikka ryhmien EINTT ja EINTTT etäisyys on 1. Eli anagrammiryhmät johtavat harhaan tässä työvaiheessa.
Mutta toistan vielä kerran: verkon muodostaminen on helppoa ja nopeaa suhteessa tehtävän loppuosaan, joten sitä on ihan turha pohtia.
jalski kirjoitti:
Villi veikkaus on, että tähtitieteellistä määrää voi pienentää hiukan arvaamalla, että pisin sanaketju löytyy suurimmasta ryhmästä, jossa on eniten sanoja.
Kuten sanoin, se suurin ryhmä sisältää ilmeisesti ainakin 11266 sanaa, joista jokaisesta pääsee keskimäärin 4 muuhun sanaan. Jos oletetaan, että tämä verkko olisi säännöllisen ruudukon muotoinen (jolloin ruuduilla on yleensä tuo 4 naapuria), ruudukko olisi kooltaan 106×106 ja sen vastakkaisesta kulmasta toiseen olisi lähes 10^62 erilaista lyhintä mahdollista 211 sanan reittiä – pidemmistä puhumattakaan. Toki tämä ei ole verkon todellinen muoto, mutta tästä voi silti muodostaa jonkinlaisen käsityksen ongelman mittasuhteista.
jalski kirjoitti:
Villi veikkaus on, että tähtitieteellistä määrää voi pienentää hiukan arvaamalla, että pisin sanaketju löytyy suurimmasta ryhmästä, jossa on eniten sanoja.
Kun se kerran on niin helppo, niin miksei listalta löydy Jalskin tulosta?
Grez kirjoitti:
jalski kirjoitti:
Villi veikkaus on, että tähtitieteellistä määrää voi pienentää hiukan arvaamalla, että pisin sanaketju löytyy suurimmasta ryhmästä, jossa on eniten sanoja.
Kun se kerran on niin helppo, niin miksei listalta löydy Jalskin tulosta?
Katsotaan, josko sanaketjuja voisi selvittää tehokkaasti vaikka tallentamalla sanat BK-puuhun ja hakemalla käyttäen ykköstä toleranssi rajana?
Thanks for all the replies! I could understand most of them, but in my own posts I will stick to English for now.
By the way, I have verified that 18 is optimal for #35. Without further spoilers I'll add that this can be done in a few seconds on a modern computer.
Grez kirjoitti:
Should one spend time on beating your solutions, what guarantee is there of payment?
My word is the only guarantee you have, but on the other hand I think that any improvement on #45 or #48 would be worth a serious publication, so if this is your kind of thing I encourage giving them a try.
I have not submitted my best results for #15, so an improvement there is guaranteed to be possible, which is why I promise only $100. I'll add that only the first person to improve on my result gets the bounty. I have an upper-bound on the optimal result, but the gap between that and my best lower-bound is big. Although I doubt I will ever manage to make them meet, the problem is fun, and some competition would be nice. I am actually working on a variation of this problem (using an English dictionary) for my Master's thesis on graph algorithms.
Improving #45 requires a fundamentally different approach. I'm preaching to the choir here, but the result of 329 can be achieved by splitting the problem into two sub-problems, solving each one optimally, and combining the results. This happens to work very well in this particular case because the larger sub-problem has a very specific structure which admits an optimal solution, while the smaller one can be solved by heuristic methods (*). I find it hard to believe that this splitting is the best way to approach the whole problem, but it surprisingly difficult to improve on it.
(*) There is a slight chance that the smaller sub-problem has not been solved optimally yet. But I believe it has.
For #48 I spent some serious CPU hours to verify that, with a few reasonable assumptions, my solution is optimal, and I have generated a list of all optimal solutions within these assumptions. It would be great to have someone replicate this, and I'd be absolutely excited to see someone beat it. (A variation of this problem, again using an English dictionary, will be a part of my thesis.)
(All of the bounties I've promised are based on valid solutions, so a hack or an attack on this website would not count.)
I was introduced to "Putkaposti" by a friend who provided English translations of the most interesting problems a while ago. Google translate has helped on some others. I think this collection is fabulous and publishing an English version would be a great idea.
symbols kirjoitti:
My word is the only guarantee you have
Word of an anonymous forum person...
If you are serious, maybe it would be worth a while to offer the bounty on some less obscure channel. (Like if you have a site or blog or something) Maybe also people who are not members of Ohjelmointiputka would get interested. I'm not saying there aren't any talented people here, but there would be many more if people from all around the world would participate.
I think it would be worth of testing how good results we could achieve by collaborating. In mathematics, there are Polymath projects where everyone can submit his or her idea and then others can use that to find other ideas. I think Polymath has solved some open mathematical problems and improved some other results. Maybe something similar might work in programming.
I think the https://codegolf.stackexchange.com/ would be suitable for many kind of optimization problems in programming. Many problem there wants the shortest code but I don't see any reason why the winning criterion can't be different.
Grez kirjoitti:
If you are serious, maybe it would be worth a while to offer the bounty on some less obscure channel.
Point taken. I'm a bit worried about copyrights. Is it okay to publish an English version of Putkaposti? I would naturally provide a link to this website as the original source. If not, is this website interested in providing English descriptions that I could link to? I would be happy to translate the problems I have solved so far.
Jaska: There are important problems in CS where a Polymath-like project might be a great idea. But, for me, Putkaposti is attractive because it's so obscure and it's a very personal challenge. I wonder if anyone will ever see #48 like I do.
First: nice to see people showing some interest in the old Putkaposti, they were fun to try to solve when they appeared.
Metabolix kirjoitti:
(07.03.2018 18:52:47): jalski: Tehtävässä #15...
Jep. Tuo reilun 10000 solmun verkko on ainoa mielekäs tutkittava. Kaikki muut sanat voi pudottaa pois, koska mikään muu verkko ei voi sisältää optimiratkaisua...
Tuota isoa verkkoa voi hieman ”järkeistää” kahdella erillisellä tunnetulla matemaattisella kikalla, joilla sen saa pilkottua ulkomuistista noin sataan pienempään osaongelmaan (kahta eri tyyppiä). Uskon tämänkaltaisen kikkailun olevan kätevää tuota pitkien ketjujen tehokasta etsintää toteuttaessa. (Oli muuten hauskaa lukea vanhan hyvän ajan tieteellistä algoritmikirjallisuutta, että kikan kaksi sai toteutettua sellaisessa laskenta-ajassa, että sen pystyi tuohon ongelmaan ajamaan.)
Suurin osa noista osaongelmista on kiitettävän pieniä, ja niihin liittyvän osan ketjua voi ratkaista tarkasti. Tähän asti jaksoin tuota joskus ratkoa... ennen kun muut kiireet silloin saivat unohtamaan tämän koko ongelman kunnes nyt joku nosti tämän taas pinnalle.
Valitettavasti muistaakseni tasan yksi noista osaverkoista on aivan liian suuri tuolla tavalla käsitellä. Siinä taisi olla joku noin puolet noista solmuista ja yksi toinen ikävä ominaisuus joka paljastaisi ehkä liikaa siitä miten ongelmaa kannattaa mielestäni lähestyä. Oleellisesti varmaan 2/3 pisteistä tulee tästä osaongelmasta. Itse en koskaan jaksanut keksiä tehokasta tapaa etsiä sieltä mitään siedettävää yksittäistä ketjua siitä osasta, ja koska noiden pienempien osaongelmien hyvä ratkaisu ei yksinään auta hyviin pisteisiin, niin oma vastaus jäi sellaiseksi että en sitä koskaan tainnut syötää vastauksena. Missäköhän levyllä tuokin koodi makaa.
Lisäksi pari muuta noista pienemmistä ongelmista oli aavistuksen liian isoja täyteen raa'an voiman ratkaisuun. Niissä jäi kanssa hieman auki, että onko löytämäni niiden läpi kulkeva osaketju varmasti paras mahdollinen. Tosin, triviaali yläraja ja paras löytämäni ratkaisu niissä taisi olla melko lähellä.
symbols kirjoitti:
I'm a bit worried about copyrights. Is it okay to publish an English version of Putkaposti? I would naturally provide a link to this website as the original source.
It is OK and I encourage you to do that! (I've written all the Finnish problem statements.) In fact, I have never realized that Putkaposti problems could be interesting for international audience.
Antti Laaksonen kirjoitti:
In fact, I have never realized that Putkaposti problems could be interesting for international audience.
Actually you wrote me an email on 19th September 2011 that it is not fair that I have some records that were solved on https://artofproblemsolving.com . So at least that forum has some of the problems translated into English by me.
Jaska kirjoitti:
Antti Laaksonen kirjoitti:
In fact, I have never realized that Putkaposti problems could be interesting for international audience.
Actually you wrote me an email on 19th September 2011 that it is not fair that I have some records that were solved on [another site]. So at least that forum has some of the problems translated into English by me.
Getting help on a forum does not mean that anyone would be too interested in the problems. People try to help because it's nice to help. That should be evident considering that even trivial questions like ”why doesn't this code compile?” get attention.
Now that you mention asking for solutions on other forums, I seem to remember that you even offered money so that someone would give you better solutions. That's so wrong and embarrassing.
symbols kirjoitti:
There are important problems in CS where a Polymath-like project might be a great idea. But, for me, Putkaposti is attractive because it's so obscure and it's a very personal challenge.
+1. Sharing ideas may be nice, but sharing complete solutions would make the high score meaningless.
Metabolix kirjoitti:
I seem to remember that you even offered money so that someone would give you better solutions. That's so wrong and embarrassing.
That is not true. I have never wanted to spent money on those problems. That is the first time I hear it is wrong to hire a programmer and pay him or her a salary. I think there are still people who gets their salary by programming although there are many open source developers too.
Jaska kirjoitti:
Metabolix kirjoitti:
I seem to remember that you even offered money so that someone would give you better solutions. That's so wrong and embarrassing.
That is not true.
Ok, this must be someone else then: https://hackforums.net/showthread.php?tid=3848380 ”Winner gets 5$” and a task copied from Putkaposti.
Jaska kirjoitti:
That is the first time I hear it is wrong to hire a programmer and pay him or her a salary.
Laws and ethics are two different things. Salary to help someone get up on a scoreboard? Lol.
Anyway, enough of that, let's stay on topic.
Offers are still standing.
I have local improvements for #15 and #45, so they are achievable. I believe #48 is optimal.
Edit:
I will pay $100 for the first person to match my result on #48, if it happens within the next 3 months.
Have you actually found efficient algorithms for these, or is it still about brute force and heuristics?
#15 is just good heuristics. It's a problem that might appear in a TopCoder Marathon Match, and top contestants would easily beat the current top result in a few days.
#45 is a very difficult problem, especially with the specific parameters that appear here. My best result was achieved using generalized versions of state-of-the-art methods for covering designs.
#48 is an efficient algorithm. Given a fresh dictionary with similar properties, I could solve the problem exhaustively in less than a day (which may count as brute force), and likely find an optimal solution in an hour. The algorithm could also be improved significantly, likely by 1-2 orders of magnitude, but it was unnecessary here.
Great to hear that you have improved the bound in #45. I will try to find time to work on this problem.
Aihe on jo aika vanha, joten et voi enää vastata siihen.