6,626 reputation
1836
bio website
location United Kingdom
age 43
visits member for 4 years, 4 months
seen 3 hours ago

Mar
17
revised What algorithm can be used to determine order given incomplete information?
added 281 characters in body
Mar
17
revised What algorithm can be used to determine order given incomplete information?
Updated with complexity note due to Dovals comment
Mar
17
comment What algorithm can be used to determine order given incomplete information?
@Doval - it could be the "+ Edges" part of that big-O that resolves my confusion. What I said about true/false/don't-know obviously applies to full-order sorting (it's just that the don't-know case never happens) and that obviously has O(n log n) complexity, but n in that case is only the number of vertices. The number of possible edges in a digraph with n vertices (and at most one edge in each direction between any pair of vertices) is n^2, so the number of edges is significant. A full order sort based on an O(n) topological sort would presumably be O(n^2) because all possible edges exist.
Mar
17
answered What algorithm can be used to determine order given incomplete information?
Mar
17
comment What algorithm can be used to determine order given incomplete information?
Another possibility is a "transitive closure". A closure takes some seed set and grows it until all reachable members are included in that set. If you have a < b and b < c in your seed set, by transitivity, you also have a < c, so a transitive closure would add that to the set, and then use that as if it were a seed element as well to try to find more, until no further ordering statements can be proven from those already found.
Mar
17
comment What algorithm can be used to determine order given incomplete information?
You might be looking for "topological sort". Note that depending on which statements you're working from, you may only have a partial order (so there are multiple possible orderings and topological sort just chooses an arbitrary one) or there might be a contradiction (so there's no possible ordering).
Feb
4
awarded  Nice Answer
Dec
2
comment How would one implement communication between an input device and a PC?
Of course I could be making some obsolete assumptions. For example, when you think about it, a USB game controller driver doesn't own a particular USB port. The port its currently dealing with may host multiple devices via a hub. IOW a game controller driver isn't really communicating directly with the hardware - there's other drivers in-between. And I'm sure I've heard about user-mode drivers or something like that.
Dec
2
comment How would one implement communication between an input device and a PC?
That's why Microsoft decided that all drivers should be checked by them (at a price) and should be signed - you still get unsigned drivers on occasion, but the user gets an alert and has to give specific permission to install them. So Microsoft has been systematically testing drivers and charging for that for quite a while. I'm not sure how far they are following the Apple model and checking and controlling Apps in the app store, but drivers were controlled for a long time before, there's good reasons for that, and Microsoft are unlikely to get complacent about them.
Dec
2
comment How would one implement communication between an input device and a PC?
For the windows store issue - I don't know for sure, I've never considered writing software to sell there, but drivers have special privileges and have an ability to crash the whole operating system that other software shouldn't have. If you remember Windows 98, almost all of the crashing issues with that were due to bad drivers - partly because Microsoft didn't control their development (e.g. the DDK back then was IIRC a free or cheap download) and partly because even the DDK examples had errors and there were few tools to catch them.
Dec
2
comment How would one implement communication between an input device and a PC?
I'm not sure why doing "some manner of magic" is a problem. Drivers, background services and applications are all software - they can all do calculations and make decisions. For joysticks, Windows has its own model of game controllers. You can fake that at the driver level certainly, but I can't see why you can't fake it at the Win32 API level by sending fake messages as well. That's not strong evidence that it can be, of course.
Dec
1
awarded  Nice Answer
Dec
1
comment How would one implement communication between an input device and a PC?
The most reliable method is IIRC to install drivers for virtual keyboard and mouse devices, as you seem to suggest. Send messages to those drivers which they translate to keyboard/mouse events. As far as Windows is concerned, these events are coming from a genuine keyboard/mouse. But that could easily be overkill, might get you in trouble with the windows app store if that's relevant, and means getting the Driver Development Kit. It may be easier to send fake messages via the Win32 API or .NET. See e.g. here
Nov
28
awarded  Yearling
Nov
21
answered Determining the winning condition for Tic-Tac-Toe
Nov
5
awarded  Nice Question
Sep
4
awarded  Good Answer
Aug
15
comment Has whitespace in identifiers ever been idiomatic?
Some dialects of BASIC have multi-keyword command names. Not the same thing, of course, but considering these are built-in commands in dialects with huge numbers of commands that should really be in libraries, they're related in a cheating kind of way. Anyway, examples include game-oriented BASIC dialects old and new (Dark BASIC, IIRC STOS on the Atari ST) and I think even the original Dartmouth BASIC (for matrix operations). Of course two or more keywords making a command name is trivial provided the parser recognizes the commands.
Jul
30
revised Why the scorn for COBOL?
Got the older standard year wrong twice (1973 instead of 1974) - fixed
Jul
30
revised Why the scorn for COBOL?
Confessions now that I can check facts - bought a copy of the book I originally learned from