| --- Log opened Fri Mar 01 00:00:48 2019 |
| 00:21 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has joined #code |
| 00:21 | | mode/#code [+qo Vornicus Vornicus] by ChanServ |
| 00:39 | | Kindamoody is now known as Kindamoody[zZz] |
| 00:52 | | Derakon[AFK] is now known as Derakon |
| 01:16 | | himi [sjjf@Nightstar-6no.81p.56.130.IP] has quit [Ping timeout: 121 seconds] |
| 01:17 | | himi [sjjf@Nightstar-1drtbs.anu.edu.au] has joined #code |
| 01:17 | | mode/#code [+o himi] by ChanServ |
| 02:10 | | M-E [Emmy@Nightstar-9p7hb1.direct-adsl.nl] has joined #code |
| 02:12 | | himi [sjjf@Nightstar-1drtbs.anu.edu.au] has quit [Ping timeout: 121 seconds] |
| 02:16 | | M-E [Emmy@Nightstar-9p7hb1.direct-adsl.nl] has quit [Ping timeout: 121 seconds] |
| 02:28 | | himi [sjjf@Nightstar-6no.81p.56.130.IP] has joined #code |
| 02:28 | | mode/#code [+o himi] by ChanServ |
| 02:52 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has quit [Connection closed] |
| 03:08 | | Romeo [Flesh@Nightstar-06k283.ca.charter.com] has joined #code |
| 03:08 | | Romeo [Flesh@Nightstar-06k283.ca.charter.com] has quit [[NS] Quit: ] |
| 03:08 | | Romeo [Flesh@Nightstar-06k283.ca.charter.com] has joined #code |
| 03:10 | < Romeo> | Hello everyone. It's been a while... lol |
| 03:10 | <&[R]> | No really, it's been less than a minute since you last left |
| 03:11 | < Romeo> | That is true. |
| 03:41 | <@macdjord|slep> | I wish to take an arbitrary boolean expression consisting of some combination of 'and', 'or', 'xor', 'not', and variables, and reduce it to a minimal equivalent. Is this actually tractable or have I accidentally set myself an NP-Hard problem? |
| 03:44 | <@celmin|away> | Pretty sure it's doable without XOR... not sure how the addition of XOR affects it though... |
| 03:44 | | celmin|away is now known as celticminstrel |
| 03:46 | <&McMartin> | XOR can be expressed with "not" and "and" alone. |
| 03:47 | <@macdjord|slep> | TheWatcher, Reiv: Get an actual editor with a GUI, you luddites. There are a lot of things where a command line is more expressive, but editing text is /not one of them/. If I must I'll use vim, but if I'm doing that for anything but my git commit messages, I am working in a deficient development environment. |
| 03:48 | <@macdjord|slep> | McMartin: Yes, but it's exponentially longer to do so. |
| 03:49 | <&[R]> | Editing multiple files with vim is needlessly complicated D: |
| 03:49 | <&McMartin> | ... no? |
| 03:49 | <&McMartin> | It's a linear increase |
| 03:49 | <&McMartin> | It's much easier if you also allow or; it turns one XOR gate into two AND gates, one NOT, and one OR. |
| 03:50 | <&McMartin> | So, the direct answer would be "make a truth table and then express that truth table with minimal logic gates based on adjacent identical values" |
| 03:50 | <&McMartin> | But building a truth table from a boolean expression is exponential in the number of inputs. |
| 03:50 | <&McMartin> | Not, however, the number of gates |
| 03:50 | <&McMartin> | https://www.geeksforgeeks.org/digital-logic-minimization-boolean-functions/ |
| 03:52 | <@macdjord|slep> | McMartin: 'a XOR b' -> '(a && !b) || (!a && b)'. You now have /two copies/ of 'a' and 'b', each of which might be a nontrivial expression. If 'a XOR b' was itself inside argument to another XOR, you then have /4/ copies each. The length of the expression thus potentially doubles for every XOR removed. |
| 03:52 | | catalyst [Jessikat@Nightstar-5dv16h.cable.virginm.net] has quit [[NS] Quit: Leaving] |
| 03:53 | <&McMartin> | Ah, that is a slightly different problem |
| 03:53 | <&McMartin> | In an actual circuit, those subexpressions can have their outputs duplicated for free. |
| 03:53 | <&McMartin> | You just wire both gates to that output. |
| 03:55 | | Romeo_ [Flesh@Nightstar-06k283.ca.charter.com] has joined #code |
| 03:56 | <@macdjord|slep> | McMartin: Yeah, I'm not actually building circuits here, nor writing imperative code to resolve the expression (where I could just save the 'a' and 'b' expressions as code-variables for reuse). I'm operating on a /symbolic/ expression and trying to reduce it to minimal complexity. |
| 03:58 | | Romeo [Flesh@Nightstar-06k283.ca.charter.com] has quit [Ping timeout: 121 seconds] |
| 03:58 | <@macdjord|slep> | I could just represent the common subexpression with a single object which is then an argument to multiple other expression-objects, but I suspect that would make building the simplification engine more complex. |
| 03:58 | | Romeo_ is now known as Romeo |
| 03:59 | <@macdjord|slep> | But yeah, I want a function that will take, say, 'a || b || (a && b && c)' and simplify it to 'a || b'. |
| 04:05 | <&McMartin> | Yeah, that is probably Harder Than NP |
| 04:05 | <&McMartin> | Because "can I reduse this to 'false'" is NP-complete. |
| 04:05 | <@macdjord|slep> | That's what I was worried about. |
| 04:07 | <&McMartin> | "Is this boolean expression ever true" is the canonical NP-complete problem; "Is this boolean expression that also has universal and existential quantifiers in it ever true" is the canonical PSPACE-complete problem. |
| 04:14 | | himi [sjjf@Nightstar-6no.81p.56.130.IP] has quit [Ping timeout: 121 seconds] |
| 04:14 | | himi [sjjf@Nightstar-1drtbs.anu.edu.au] has joined #code |
| 04:14 | | mode/#code [+o himi] by ChanServ |
| 04:41 | <@celticminstrel> | I suppose generating a boolean expression from a truth table isn't easy either? |
| 04:42 | <@celticminstrel> | I mean, unless it has few enough inputs that you can compare the truth table to every possible truth table with that many inputs (which is probably just 2 or maybe 3 inputs). |
| 04:42 | <@macdjord|slep> | celticminstrel: Generating /an/ expression is trivial. I'm not sure if generating a /minimal/ one is. And if my problem space were small enough to make generating an exhaustive truth table practical, I wouldn't need to reduce the original expression in the first place. |
| 04:51 | <@macdjord|slep> | Context: The game works like this: You start with a bunch of game pieces; on your turn, you take the largest and break it into two smaller pieces. Each piece has a different list of possible transformations available, down to the smallest which cannot be broken. If breaking the piece produces a peice you already have, they cancel out. Last player to successfully break a piece wins. |
| 04:51 | <@macdjord|slep> | I need to be able to determine which combinations of starting pieces are winnable, assuming optimal play on both sides. |
| 04:54 | <@macdjord|slep> | My first effect was just to work it out for each possible transition - winnable(state) = not any(winnable(child_state) for child_state is state.children), with a nice big LRU cache on the winnable() function - but it proved intractable. |
| 04:56 | <@macdjord|slep> | I've worked out solutions for the first 5 or so smallest pieces manually, so I was wondering if I could write something that would do so automatically for the rest of it. |
| 04:58 | < Romeo> | Why not start with a valid solution and then work your way back to a starting condition that you can prove, in reverse, to be winnable. |
| 04:58 | <@macdjord|slep> | Romeo: I don't understand your suggestion. |
| 05:02 | < Romeo> | Given a valid solution and a known number of transformations at eat step, you can work the entire problem in reverse from a solution you consider to be accetable to a set of starting pieces that you know to have a valid solution. |
| 05:02 | < Romeo> | *each |
| 05:06 | <@macdjord|slep> | Romeo: Okay, one of us isn't understand the other well. Right now, I can calculate winnable($state) for any $state, but the amount of time taken becomes intractable if $state contains any pieces larger than 200 or so. My eventual goal requires testing several thousand states which each contain 2 pieces in the 5000-8000 range. |
| 05:10 | | Vorntastic [uid293981@Nightstar-6br85t.irccloud.com] has joined #code |
| 05:10 | | mode/#code [+qo Vorntastic Vorntastic] by ChanServ |
| 05:11 | <@macdjord|slep> | AT the moment, I'm thinking the solution might be to hand-solve a bunch more pieces, then see if I can discern a pattern that would let me write a non-general solver to do the rest. |
| 05:12 | | Derakon is now known as Derakon[AFK] |
| 05:18 | | Romeo [Flesh@Nightstar-06k283.ca.charter.com] has quit [[NS] Quit: ] |
| 05:26 | | celticminstrel is now known as celmin|sleep |
| 05:54 | | himi [sjjf@Nightstar-1drtbs.anu.edu.au] has quit [Ping timeout: 121 seconds] |
| 07:06 | <&Reiver> | macdjord|slep: That's actually why I use nano |
| 07:06 | <&Reiver> | On the occasions I need to use a non-GUI text editor, it is to do the absolute minimum editing required to /get/ to my GUI text editors. |
| 07:07 | <&Reiver> | And/or for basic config on equipment where such things aren't available, and simultaneously not worth downloading-editing-uploading the document proper. |
| 07:07 | <&Reiver> | So, small, minor edits. At which point Nano's semi-GUI nature is... enough... to scrape by without having to actually, y'know, learn one of the Holy War Abominations in its place. |
| 07:08 | <@macdjord|slep> | Reiver: Yeah, I use vim in basically only 2 cases: git commits, and when I have to edit files on a server I'm sshed into. |
| 07:22 | <&McMartin> | nano is entirely adequate for both of those use cases |
| 07:23 | <@macdjord|slep> | I'm familiar with the basics of vim, and those use cases aren't frequent enough to make it worth investigating and learning something else. |
| 07:41 | <&Reiver> | yeah, I'm not familiar with /any/ of them |
| 07:41 | <&Reiver> | so I use nano because familarity is not required~ |
| 08:30 | | [R] [rstamer@genoce.org] has quit [[NS] Quit: No Ping reply in 180 seconds.] |
| 08:33 | | [R] [rstamer@Nightstar-d7h8ki.org] has joined #code |
| 08:33 | | mode/#code [+ao [R] [R]] by ChanServ |
| 08:41 | | Kindamoody[zZz] is now known as Kindamoody |
| 09:04 | | himi [sjjf@Nightstar-cb51fu.optusnet.com.au] has joined #code |
| 09:04 | | mode/#code [+o himi] by ChanServ |
| 10:18 | | Kindamoody is now known as Kindamoody|afk |
| 12:52 | | Degi [Degi@Nightstar-snja24.dyn.telefonica.de] has joined #code |
| 14:28 | | Kindamoody|afk is now known as Kindamoody |
| 15:02 | | Degi [Degi@Nightstar-snja24.dyn.telefonica.de] has quit [Connection closed] |
| 15:18 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has joined #code |
| 15:18 | | mode/#code [+qo Vornicus Vornicus] by ChanServ |
| 16:48 | | catalyst [Jessikat@Nightstar-5dv16h.cable.virginm.net] has joined #code |
| 17:02 | | M-E [Emmy@Nightstar-9p7hb1.direct-adsl.nl] has joined #code |
| 17:10 | | Vorntastic [uid293981@Nightstar-6br85t.irccloud.com] has quit [[NS] Quit: Connection closed for inactivity] |
| 19:47 | <@abudhabi> | https://www.youtube.com/watch?v=ywWBy6J5gz8 |
| 20:09 | | M-E is now known as Emmy |
| 20:11 | | JustBob [justbob@Nightstar.Customer.Dissatisfaction.Administrator] has quit [[NS] Quit: This unit is entering a hibernation state.] |
| 20:11 | | JustBob [justbob@ServerAdministrator.Nightstar.Net] has joined #code |
| 20:11 | | mode/#code [+o JustBob] by ChanServ |
| 20:25 | | JustBob [justbob@Nightstar.Customer.Dissatisfaction.Administrator] has quit [[NS] Quit: This unit is entering a hibernation state.] |
| 20:35 | <@TheWatcher> | Someone's managed to break my mediawiki timeline plugin with BC dates |
| 20:38 | <@TheWatcher> | I hate dates. |
| 20:46 | | JustBob [justbob@ServerAdministrator.Nightstar.Net] has joined #code |
| 20:46 | | mode/#code [+o JustBob] by ChanServ |
| 21:54 | | himi [sjjf@Nightstar-cb51fu.optusnet.com.au] has quit [Connection reset by peer] |
| 22:25 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has quit [Connection closed] |
| 23:13 | | * McMartin looks at top during this compile |
| 23:13 | <&McMartin> | ... why is ld taking up 40% CPU |
| 23:53 | <&[R]> | How complicated is the think you're linking? |
| --- Log closed Sat Mar 02 00:00:49 2019 |