| --- Log opened Mon May 09 00:00:11 2022 |
| 01:08 | | Degi_ [Degi@Nightstar-ia3a72.pool.telefonica.de] has joined #code |
| 01:09 | | Degi [Degi@Nightstar-kljtui.pool.telefonica.de] has quit [Ping timeout: 121 seconds] |
| 01:09 | | Degi_ is now known as Degi |
| 01:29 | | himi [sjjf@Nightstar-v37cpe.internode.on.net] has joined #code |
| 01:29 | | mode/#code [+o himi] by ChanServ |
| 01:56 | | gizmore|2 [kvirc@Nightstar-8bltfh.dip0.t-ipconnect.de] has joined #code |
| 01:59 | | gizmore [kvirc@Nightstar-7avbuh.dip0.t-ipconnect.de] has quit [Ping timeout: 121 seconds] |
| 02:01 | | catalyst_ [catalyst@Nightstar-oer94b.dab.02.net] has joined #code |
| 02:02 | | catalyst [catalyst@Nightstar-ejd4sd.cable.virginm.net] has quit [Ping timeout: 121 seconds] |
| 02:07 | | catalyst [catalyst@Nightstar-ejd4sd.cable.virginm.net] has joined #code |
| 02:10 | | catalyst_ [catalyst@Nightstar-oer94b.dab.02.net] has quit [Connection reset by peer] |
| 03:45 | | abudhabi__ [abudhabi@Nightstar-vmjuke.adsl.tpnet.pl] has joined #code |
| 03:48 | | abudhabi_ [abudhabi@Nightstar-p95inj.adsl.tpnet.pl] has quit [Ping timeout: 121 seconds] |
| 04:44 | < simon_> | I have a coding challenge I'm trying to find a good solution for. |
| 04:45 | < simon_> | it starts out with: what's the biggest palindrome integer that is the product of two 3-digit positive integers? |
| 04:46 | < simon_> | my first thought is to look at 999 x 999 = 998001, find the biggest palindrome below that, and assess whether that's a product of two 3-digit numbers. |
| 04:46 | < simon_> | converting 998001 => 899998, and factorizing that to 2 x 11^2 x 3719 tells me the biggest palindrome below 999 x 999 isn't a product of two 3-digit numbers. |
| 04:47 | < simon_> | the conversion to the largest palindrome below n seems cheap |
| 04:47 | < simon_> | the factorization doesn't (asymptotically, I mean) |
| 04:48 | <@macdjord> | simon_: Pretty sure just trying pairs and seeing if they are palindromic is faster. |
| 04:48 | <@macdjord> | s/they/the result. |
| 04:48 | <&McMartin> | Yeah, this is a loop from 1 to 1,000,000, more or less |
| 04:48 | <&McMartin> | That's nothing on a GHz machine |
| 04:49 | < simon_> | macdjord, do you also think it is asymptotically faster if the problem is either "find the largest palindrome that is the product of two n-digit numbers"? |
| 04:50 | < simon_> | at this point I'm not really trying to code up a quick solution, I was more interested in the asymptotics of the algorithm :) but I sense that unless I can come up with a trick for the factorization, going forward rather than backward would probably be cheaper. |
| 04:50 | <&McMartin> | Factorizing arbitrary large integers is, in fact, very hard |
| 04:51 | < simon_> | right |
| 04:51 | <&McMartin> | And "all numbers that are the sum of two N-digit factors" is O(n^2) and can probably do some merge-sort-y shenanigans to make sure you get a clean, strictly-decreasing set. |
| 04:52 | < simon_> | hmmm, ok |
| 04:52 | < simon_> | yeah |
| 04:52 | <@macdjord> | Let's see. Two n-digit numbers will produce a product that is at most 2n digits long. There are O(10^n) palindromes of length 2n. |
| 04:53 | <@macdjord> | So unless I've missed a trick, the number of palindromes will grow faster than the number of integer pairs. |
| 04:54 | < simon_> | hmmm, very good point! |
| 04:55 | < simon_> | I can find large palindromes below n fast, but I can't factorize them fast. I can find products that are palindrome naively in O(n^2), and I might be able to do that faster. so going forward definitely seems like the faster choice. |
| 04:56 | <&McMartin> | Generating the set of products is O(n^2), and palindrome checking should be linear in the number of digits, which will be O(log n). |
| 04:56 | < simon_> | I should check the products looping backwards, then. |
| 05:00 | <&McMartin> | Yeah. "check all the palindomes" -- coming up with *any given* palindrome may be fast, but you have an exponential number of palindromes to check, so even with a magic factorizer it's *still* an exptime algorithm compared to a quadratic one. |
| 05:25 | | Vorntastic [uid293981@Nightstar-phvupn.irccloud.com] has joined #code |
| 05:25 | | mode/#code [+qo Vorntastic Vorntastic] by ChanServ |
| 06:32 | <~Vorntastic> | Even digit palindromes are divisible by 11 |
| 06:39 | < simon_> | :-D |
| 06:48 | <~Vorntastic> | And not by 10. So you start with [(-979*999, 979, 999)], heappop, check for palindromity, then if not, heappush with b-11,c and b,c-1, keep going |
| 07:22 | <~Vorntastic> | https://ideone.com/Qlre6u |
| 08:10 | <@macdjord> | "Does anyone else think it's weird that the universal search icon is a magnifying glass? When was the last time you searched for *anything* with a magnifiying glass in real life? My ideal search icon would be a little picture of me, screaming "HAS ANYONE SEEN MY CAR KEYS?!" " |
| 08:14 | <&McMartin> | Harder to represent with a 16x16-pixel sprite. |
| 10:16 | < catalyst> | just a bunch of question marks |
| 10:16 | < catalyst> | and then it's mandated to play the metal gear solid "you're in danger" music and sound |
| 13:32 | | gizmore|2 [kvirc@Nightstar-8bltfh.dip0.t-ipconnect.de] has quit [Connection reset by peer] |
| 13:39 | | gizmore [kvirc@Nightstar-8bltfh.dip0.t-ipconnect.de] has joined #code |
| 14:32 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has joined #code |
| 14:32 | | mode/#code [+qo Vornicus Vornicus] by ChanServ |
| 16:14 | | Vorntastic [uid293981@Nightstar-phvupn.irccloud.com] has quit [[NS] Quit: Connection closed for inactivity] |
| 17:33 | | Emmy [Emmy@Nightstar-l49opt.fixed.kpn.net] has joined #code |
| 17:49 | | Kimo|autojoin [Kindamoody@Nightstar-eubaqc.tbcn.telia.com] has joined #code |
| 17:49 | | mode/#code [+o Kimo|autojoin] by ChanServ |
| 17:49 | | Kimo|autojoin is now known as Kindamoody |
| 18:22 | | catalyst_ [catalyst@Nightstar-ui3pmb.dab.02.net] has joined #code |
| 18:26 | | catalyst [catalyst@Nightstar-ejd4sd.cable.virginm.net] has quit [Ping timeout: 121 seconds] |
| 18:32 | | catalyst [catalyst@Nightstar-058ijn.cable.virginm.net] has joined #code |
| 18:34 | | catalyst_ [catalyst@Nightstar-ui3pmb.dab.02.net] has quit [Ping timeout: 121 seconds] |
| 19:44 | | Kizor [a@Nightstar-nfsqa7.yok.fi] has quit [NickServ (RECOVER command used by Kizor_)] |
| 19:44 | | Kizor [a@Nightstar-nfsqa7.yok.fi] has joined #code |
| 19:45 | | Kizor [a@Nightstar-nfsqa7.yok.fi] has left #code [] |
| 19:45 | | Kizor [a@Nightstar-nfsqa7.yok.fi] has joined #code |
| 20:22 | | Emmy [Emmy@Nightstar-l49opt.fixed.kpn.net] has quit [Ping timeout: 121 seconds] |
| 20:52 | | macdjord [macdjord@Nightstar-re5.7if.45.45.IP] has quit [[NS] Quit: Deep inside, every housecat believes themself to be just a temporarily embarrassed tiger.] |
| 20:53 | | macdjord [macdjord@Nightstar-re5.7if.45.45.IP] has joined #code |
| 20:54 | | mode/#code [+o macdjord] by ChanServ |
| 21:11 | | catalyst_ [catalyst@Nightstar-ootcp9.dab.02.net] has joined #code |
| 21:13 | | catalyst [catalyst@Nightstar-058ijn.cable.virginm.net] has quit [Ping timeout: 121 seconds] |
| 21:21 | | catalyst [catalyst@Nightstar-ejd4sd.cable.virginm.net] has joined #code |
| 21:24 | | catalyst_ [catalyst@Nightstar-ootcp9.dab.02.net] has quit [Ping timeout: 121 seconds] |
| 22:35 | | Kindamoody is now known as Kindamoody[zZz] |
| --- Log closed Tue May 10 00:00:12 2022 |