Wikipedia:Reference desk/Archives/Computing/2012 December 18

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 18

DOS find command in Windows 7

I issue the following two commands in an empty directory, so neither should find any files to search:

find "call"  *

find "call"  *\*

The first command correctly says "File not found - *". The 2nd command hangs forever (but doesn't seem to use any CPU time). What's it doing, and how do I prevent it ? Also, is there a better way to repeat a search recursively in all sub-directories (all the way down) ? StuRat (talk) 01:09, 18 December 2012 (UTC)

You should be able to use PowerShell for a decent "native" grep alternative. You could also just grab a win32 build of grep from http://gnuwin32.sf.net/. ¦ Reisio (talk) 03:03, 18 December 2012 (UTC)

Grep won't work in Windows in this case because Windows doesn't see *\* as a valid path. Here's how I would search recursively for a string:

for /r . %i IN (*) DO find "call" %i

Other commands simply display an error that the path cannot be found or that is incorrectly spelled. But even if *\* was accepted by Windows, it would only search one level deep.—Best Dog Ever (talk) 03:08, 18 December 2012 (UTC)

grep works fine (and recursively) in Windows… if you have it. ¦ Reisio (talk) 03:24, 18 December 2012 (UTC)

What I was saying is that you can't search for a string in the Windows command prompt using the *\* wildcard no matter what command you use.—Best Dog Ever (talk) 03:30, 18 December 2012 (UTC)

Luckily you don’t have to, you can use . or the name of the top-level directory instead (and in fact wouldn’t want to use */* to "search recursively in all sub-directories (all the way down)", even if you could. ¦ Reisio (talk) 03:36, 18 December 2012 (UTC)

Thanks so far. So what exactly does my 2nd command attempt to do ? It behaves as if it's waiting for more input. StuRat (talk) 19:35, 18 December 2012 (UTC)

The help for Find (find /?) says: 'If a path is not specified, FIND searches the text typed at the prompt or piped from another command', and you're getting the first of those - try typing lines that do and don't contain "call". It seems to be a bit of a bug that it ignores the invalid filespec. AndrewWTaylor (talk) 13:17, 19 December 2012 (UTC)

Yes, it then repeats any line I type containing "call". I agree, seems like a bug. StuRat (talk) 08:35, 22 December 2012 (UTC)

SHA1 and MD5 collision attacks

I'm aware that both SHA-1 and MD5 have been broken with collision attacks. Some of which I guess can be run very quickly. But have there been any published attacks that can break both at the same time? In other words, find an arbitrary input that can collide with a predetermined sha1 and md5 checksum? Shadowjams (talk) 02:48, 18 December 2012 (UTC)

• The article Preimage attack covers what you are talking about. IETF RFC 4270: Attacks on Cryptographic Hashes in Internet Protocols contains references to published attacks. DreadRed (talk) 09:03, 18 December 2012 (UTC)

I know both discrete attacks exist, but does that attack apply to both on the same input block? The article doesn't seem to say as much. Shadowjams (talk) 10:05, 18 December 2012 (UTC)

Hashes are calculated independently for each 512-bit block so that is where collisions are sought. DreadRed (talk) 12:21, 18 December 2012 (UTC)

Alright, that's not an answer to my question. Shadowjams (talk) 13:26, 18 December 2012 (UTC)

You can't seriously hope to find a simultaneous attack on both SHA-1 and MD5, can you? DreadRed (talk) 07:49, 19 December 2012 (UTC)

Well that's the question. Never say never when it comes to cryptography. How long was it predicted MD5 would last in 1992? Shadowjams (talk) 20:20, 19 December 2012 (UTC)

FileMaker

Anyone use FileMaker?

I was asked if I could set up a members database and have it searchable, etc etc. The users are all around the world, so having it on a web site is best. In fact, optimally, they'd like the web site to pull data from the database for use on the site (showing lists of members, locations, how many members do we have that answered XX to YY question, etc). I've never had to set up a database myself, though I've installed and run a couple forums that relied on them. Shortly after being asked about this, the person who asked found FileMaker for another project that they're working on. They found it easy to use and now think that they might not need me to do anything. I took a look at the FileMaker web site and I don't see right off where it'll do what they want. Am I misreading things? Would they be better served by having an SQL database? Or is there some third solution that I remain unaware of? Thanks, Dismas|^(talk) 06:09, 18 December 2012 (UTC)

FileMaker is, as of version 12, a SQL database in its own right (from version 9 it could interact with other databases via their SQL interfaces). It does sound like, to make it accessible from around the world, you need a web app. FileMaker PRO does support this ([1]). To do that someone would have to code a webapp (in say PHP) which interacted with FileMaker (using their own API). Then you'd need to make that accessible on the web - it's likely that you'd get a FileMaker hosting solution (one that supports their Instant Web App capability - a web search finds lots of filemaker hosting companies) and host it there. They could certainly change to a different database, and / or write the webapp in another language (allowing different hosting); they could abandon their local database altogether and store the data in the cloud, and have everyone (including their own admin staff) access it by a webapp. But I think all of this requires engineering to write that webapp. -- Finlay McWalterჷTalk 15:25, 18 December 2012 (UTC)

Note (so you understand what you're looking at when you read some of the "FileMaker hosting" pages) - some organisations use FileMaker PRO as a kind of distributed groupware thing. Their employees around the world have their own copies of FileMaker PRO and they connect those up to a shared server to make changes (just as if they were back at HQ). It sounds like your members are just regular people who don't all own a copy of FileMaker, and so who can't avail themselves of this. That's why you need a webapp. -- Finlay McWalterჷTalk 15:30, 18 December 2012 (UTC)

Update: it looks like Instant Web Publishing means you don't need to write a webapp - they essentially have the FileMaker interface presented via HTML, which is done automatically. Writing a webapp is needed only if you want to have more control over how it appears and what people can do. Like other databases, FileMaker has security segregation between users - but if I were exposing a real database over the internet (particularly when you have to comply with various countries' data protection laws, which may be the case if you're storing details about people) then I'd want that set up by someone with lots of experience with FileMaker, so the security doesn't get cocked up. -- Finlay McWalterჷTalk 16:21, 18 December 2012 (UTC)

Thanks for the breakdown. It's a non-profit organization and they already have a web site. I don't know who they host it with. And you're correct in that not everyone would own a copy of FileMaker. After reading the link that you provided and reading over your explanation, it does seem like they might be able to do what they want with FM. Thanks again, Dismas|^(talk) 09:08, 19 December 2012 (UTC)

Playing Blu-ray discs on my computer

Is it just a matter of 'get Blu-ray drive, install drive, insert disc'? Or does my system need to be of a certain spec in order to play Blu-rays correctly? Don't really know much about them at all, TBH - just been musing over getting a BR drive for my computer now that my DVD burner is playing up on me... --Kurt Shaped Box (talk) 19:35, 18 December 2012 (UTC)

It should play immediately, once the drive and driver are installed. However, since Blu-Ray is capable of displaying a higher resolution image, the question comes up as to whether your PC can display it at full resolution, color depth, and frame rate without lagging. This involves the monitor, graphics card, GHz, etc. StuRat (talk) 19:38, 18 December 2012 (UTC)

That's a thought. My machine does lag sometimes when playing downloaded 720p/1080p HD videos (the latter moreso)... --Kurt Shaped Box (talk) 19:51, 18 December 2012 (UTC)

And the Blu-Ray player should have a minimum requirements list for your PC. That really is a minimum, though, meaning if you have anything else running while watching a Blu-Ray movie, you will need more oomph (technical term) to avoid lag. StuRat (talk) 20:20, 18 December 2012 (UTC)

No, you can't just rock up with a BluRay disc and get it to play. You need the right software to decode it. Often this will come bundled with the drive, unless it's an OEM device. See here and here for more. - Cucumber Mike (talk) 21:56, 18 December 2012 (UTC)

That's what I'm calling the driver, codecs included. StuRat (talk) 22:06, 18 December 2012 (UTC)

I'm pretty sure that I already have the required software installed anyway, but that's no biggie if not. I was more concerned about hardware requirements. Perhaps I should spend some of my probable Xmas gift money on a dedicated graphics card - what's considered good these days anyhow? It's literally been a decade since I paid attention to developments in computer hardware. My current machine has some on-motherboard graphic chipset thing that so far (mostly) works well enough for what I use it for... --Kurt Shaped Box (talk) 22:20, 18 December 2012 (UTC)

Really most any dedicated graphics card that's say not more then 3 years old would do (I mean in generation and real generation not the pseudo-generation due to renaming), even many older if all you care about is bitstreaming H264 and perhaps high quality basic post processing like deinterlacing. With the rise in GPGPU there may be advantages to a slightly more powerful card but it depends on your requirements. But really I have to say, basically most any dual core CPUs except perhaps for some of the Atoms and Pentium Ds (i.e. Pentium 4 dual cores) should be able to handle 1080p software decoding without issue particularly with the sort of bitrates for most downloads. Perhaps they will have fairly high usage but they can handle it without significant drop frames or other issues. I know from experience even one of the old socket 939 A64 x2/dual cores has no problem. So how old is your computer? Even if it has a 16x PCI-express slot so can handle a video card upgrade easily, it may still be worth upgrading the whole. It'll be a bit more but not that much more. The new Intel Ivy Bridge and AMD Trinity chips would often have at least as good GPU performance as the low end GPU you're likely looking at and presuming your computer is really as crap as suggested, you'll likely get more RAM and get a much faster CPU, and that's even with Trinity.

Note that Bluray software is not simple. Because of the DRM restrictions, just having the right codecs doesn't help and a lot of free software doesn't work well without a decrypter like AnyDVD HD which isn't free and I'm not aware any free decrypter works well (it's difficult because of the continous updates required). Most cheap and OEM versions of software which does support Bluray like WinDVD, PowerDVD, Total Media Theatre will not support Bluray. (Obviously OEM versions with Bluray drivers usually will support.) And remember you also need to get updates for your software otherwise it's likely to stop working with new discs.

Nil Einne (talk) 03:41, 20 December 2012 (UTC)

I currently have (cutting and pasting) "AMD Athlon 64 X2 4400+" with "2.00 GB Single-Channel DDR2 (6-6-6-18)". My motherboard does have a 16x PCI-express slot. Well, the manual that I have for what I think is my motherboard (though it may be from another one that died a couple of years ago...) says that I do, but I haven't had chance to open my PC to look yet... --Kurt Shaped Box (talk) 15:47, 20 December 2012 (UTC)

Is this a virus?

I had a program blocked today by my firewall, i think it was trying to send info to the internet. From the information it gives, it looks like a virus that is trying to pass as some legitimate windows program. Look at its location on the hard drive too! The folder name is so arbitrary.

http://i45.tinypic.com/1fd3yc.jpg

Is this a virus? Please share thoughts! :)

PS: I can't think for the life of me why i would have some crap from microsoft, with the publisher being russian...

137.81.118.126 (talk) 19:56, 18 December 2012 (UTC)

Looks iffy to me. I'd get rid of it. StuRat (talk) 20:16, 18 December 2012 (UTC)

I'd compress it with heavy algorithm, not into the file type .ZIP (since Windows natively supports it) and leave the compressed file there. You never know if it's actually legit; you may need it again. -- 143.85.199.242 (talk) 23:04, 18 December 2012 (UTC)

Appears to be a trojan common in Russian-speaking countries. If you don't already have it then please download MalwareBytes Anti Malware and scan the file as that is the recommended fix. MalwareBytes is pretty good at this thing anyway if you've never used it. Good luck! ツ Jenova20 ^(email) 23:42, 18 December 2012 (UTC)

Solve chess

How long would it that the Titan supercomputer to solve chess? — Preceding unsigned comment added by 67.60.98.242 (talk) 20:01, 18 December 2012 (UTC)

Depends on what you mean by "solve". If you mean to use a brute force approach to look ahead from the start of the game to all possible games, and use that to decide each move, that's not possible (would take longer than computer would last). StuRat (talk) 20:15, 18 December 2012 (UTC)

I am not interested in a practical application, an academic result will be sufficient. Are we talking decades, centuries, millenia or the age of the earth here? — Preceding unsigned comment added by 67.60.98.242 (talk) 20:21, 18 December 2012 (UTC)

Let's see. If you brute force it, this site says there are some 10¹²⁰ possible moves: [2]. That would take longer than the universe will last to solve. However, if you just look at board configurations, the number is far lower. This is because you can arrive at the same board position by many different sequences of moves. This site lists only some 140 million board positions: [3]. So, if you had each of those in the database, and the appropriate move for each, then looking them up should still allow for a perfect game, in a small amount of time. StuRat (talk) 20:35, 18 December 2012 (UTC)

Good idea. Is the reason that it has not been solved then because of the time to create 140M databases? — Preceding unsigned comment added by 67.60.98.242 (talk) 20:50, 18 December 2012 (UTC)

Yes. StuRat (talk) 20:55, 18 December 2012 (UTC)

Well, depending on what 67 means. If a (fast) oracle would hand you the correct move from any position, and if that's really all there are (I haven't checked that), then such a database would be perfectly feasible. The problem is computing the correct move. (What's a correct first move for White, for example?) --Trovatore (talk) 21:38, 18 December 2012 (UTC)

Oh, I guess you already went into that. Never mind. --Trovatore (talk) 21:39, 18 December 2012 (UTC)

To go a bit further, each pawn or piece can have it's board position modeled by 6 bits (3 bits gives us one of 8 horizontal positions, since 2³ = 8, and 3 more give us the vertical). Some pieces would need an additional bit, so a king stores whether it has yet castled, and a pawn whether it has been promoted to a queen. So, let's just round this 6 or 7 bits up to 8 bits, or 1 byte per piece or pawn. That's a complete board position modeled by 32 pieces × 1 byte, or 32 bytes (less as pieces are taken). Along with those, you'd want to store the next move, so maybe 4 more bytes for that (2 for white's move if it's white's turn, and 2 for black's). So, a total of at most, 36 bytes. Multiply that by 140 million possible board positions, and we get 5GB. That should fit easily on a hard drive, but for maximum speed, we'd want it in memory. A high-end PC could handle that. Add a proper index/hash to search through the board positions, and it could move basically instantaneously, from a human POV. However, actually generating all this data in the first place would take vastly more computation time. StuRat (talk) 20:55, 18 December 2012 (UTC)

Endgame tablebase could be relevant here. bamse (talk) 21:32, 18 December 2012 (UTC)

The source used above [4] gives no real argument for the alleged 140 million positions. It's a gross underestimate. Chess#Mathematics and computers says: "The number of legal positions in chess is estimated to be between 10⁴³ and 10⁴⁷". See also Shannon number and Solving chess. PrimeHunter (talk) 22:50, 18 December 2012 (UTC)

Expanding on the above, lets assume we can now build a computer storage array that contains the equivalent of one million 1 TB drives. That's 10¹⁸ bytes. Assuming that each position could be mapped to a unique address and we use roughly a byte of storage to store some piece of information (such as moves to win, loose or draw), we can represent roughly 10¹⁸ positions. Well short of our goal for now. Populating data for a game of that magnitude would not be a huge problem. Assuming 1 million processors calculating 1 million positions per second, they could process a universe or 10¹⁸ positions in as little as a few weeks. Note that all of these assumptions could be off by many orders of magnitude, but these are minor going into the next step of the estimation.

If we pick the middle ground for the total number of legal positions, say 10⁴⁵, we will find that our current technology falls short by a factor of 10²⁷ or 2⁹⁰. A liberal application of Moore's law, where both storage capacity and processing power double every two years, would place the expectation for a final solution 180 years in the future (give or take a couple of hundred years). Of course Moore's law is not guaranteed. A molecular crystalline storage device capable of storing 10⁴⁵ bytes might be the size and mass of a small moon.

Perhaps sometime in the year 2200, there will be a chess showdown between Ganymede and Titan, which uninterestingly always ends in an agreed draw before the first move. -- Tom N (tcncv) talk/contrib 04:17, 19 December 2012 (UTC)

Or with Black resigning - if you believe as I do that Chess is won for White. Rich Farmbrough, 16:29, 20 December 2012 (UTC).

That 140 million positions given above is an estimate of the number of "logical positions", which means ones likely to occur in a game. That sounds very low to me. Also, to solve chess, you have to consider all all positions, not just that tiny subset. Of course, there are ways to reduce that 10¹²⁰ by many orders of magnitude. Bubba73 ^{You talkin' to me?} 06:41, 20 December 2012 (UTC)

I could see a solution for perfect play having a table with 140 million positions or so (although I do agree it does sound low). The solution doesn't need to involve every possible position, or even those that are likely to come up in a normal game. It only has to include positions that the board can get into given perfect play on its part. To actually build a table for perfect play, many many more positions would have to be evaluated, and that's where you get into the values like 10^45 above. So even if the solution is reasonably small, actually finding the solution could take ages and tons of resources. 209.131.76.183 (talk) 13:59, 20 December 2012 (UTC)

Of course "perfect play" might mean winning in the shortest number of moves, whereas a more useful definition would be simply winning. To simplify the problem, provided one can calculate to a win, one can prune vast amounts of the game tree. Conversely an unqualified the claim that one can use unique compressed positions as the key to the problem fails, since apart form the above mentioned extra bits for promotion, castling (and, presumably, en-passant), one also needs to take into account the "draw by repetition" rule and the "50 move rule". Rich Farmbrough, 16:29, 20 December 2012 (UTC).

No, perfect play is the same as optimal play, which wins in the shortest number of moves, if it can win by force. Bubba73 ^{You talkin' to me?} 00:39, 21 December 2012 (UTC)

The standard way to record a game position is Forsyth–Edwards Notation. This does take into account promotion, castling and en passant, and also the 50-move rule. Draw by repetition isn't allowed for, but this draw can be claimed by one of the players; it doesn't have to be.-gadfium 02:03, 21 December 2012 (UTC)

python

how do you find the index of the largest int in a list? and how do i find what item occurs most often in a list? thanks, 70.117.119.138 (talk) 23:55, 18 December 2012 (UTC)

Both of these involve a simple iteration through the list, keeping tabs as you go. Have you tried to get this working youself - if so, please show us where you failed. For tasks that look like homework, you'll find Wikipedia editors will help you but they won't (for your benefit) do the work for you. 87.114.106.165 (talk) 01:48, 19 December 2012 (UTC)

For the first one, try "print myList.index(max(myList))". However, this will only return the first index with the max value. If there are more than 1, you might not want this behavior. "myList.count(max(myList))" will tell you if there are more than 1.

For the second, I think iteration is needed. Again, you need to think about what to do if you get a tie (2-way, 3-way or more). StuRat (talk) 19:39, 19 December 2012 (UTC)

For the second task, if you are using a fairly recent version of python, collections.Counter is perfect for the job, provided everything in the list is hashable. For the first one, as well as StuRat's answer, another option is to use the max function's key argument, for example:

   >>> max(enumerate([1,4,0,7,2]), key=lambda x:x[1])
   (3, 7)

This returns a tuple containing the index and value of the maximal element (if two or more are maximal, returns the first one). That lambda function is equivalent to operator.itemgetter(1) by the way, if you prefer using that. 130.88.99.231 (talk) 16:21, 21 December 2012 (UTC)