phc-discussions - RE: [PHC] OT: Pw0nd the tech riddle

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Sat, 17 May 2014 22:45:21 -0400
From: "Gary W. Hvizdak" <gary.hvizdak@....rr.com>
To: <discussions@...sword-hashing.net>
Subject: RE: [PHC] OT: Pw0nd the tech riddle

Back to the puzzle, I can do it (in my head) in eight compares for a 12 x 12 matrix, when said matrix is a multiplication table.

From: Bill Cox [mailto:waywardgeek@...il.com] 
Sent: Saturday 17 May 2014 2153
To: discussions@...sword-hashing.net
Subject: [PHC] OT: Pw0nd the tech riddle

You guys are the biggest online geeks I've run across, on average, so if you enjoy dumb tech riddles (which I suspect many of you do), read on, but it's way off topic.

I was challenged with a puzzle yesterday, but I don't believe the guy offering the puzzle understands the solution very well.  Once I understood his puzzle (which took me a while - I can be slow), I gave him the optimal solution, running in O(N), in about 10 seconds.  He didn't seem to like it, so we moved into highly unoptimal territory, and before giving up on the discussion, he pressed me on how long I though his preferred solution would take, "in my gut".  I stuck to O(N*log2(N)).  He was clearly unimpressed.  I'm giving myself kudos for sticking with my gut, which turned out to be exactly right, but only if I give the guy the benefit of the doubt and improve his algorithm slightly - doing a binary search on the diagonal, rather than picking the middle element.  I simply couldn't accept that he was advocating picking the middle element and then recursing on 3 N/2xN/2 sub-matricies... that's just nuts.  Here's a link to an online discussion of the puzzle I found today:

http://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/

It seems that most of the geeks on this forum have trouble with this problem.  I'm not looking for confirmation of my solution - I know it's right.  I'd just prefer talking with a level of geek where I don't have to keep explaining things.  Even better, I prefer talking to geeks I can learn from, and I've had the best luck in years on this forum.  I hope you enjoy it.  I did!

Bill

Content of type "text/html" skipped