Computing desk
< April 2	<< Mar \| April \| May >>	Current desk >

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

April 3

Jigsaw Algorithm

I have a calendar jigsaw using some pentominos and some quadrominos (if that 4-word is right).

The board which is not a regular shape and where each "item" is a square, looks like

Ja Fe Mr Ap My Jn
Jl Au Se Oc No De
1  2  3  4  5  6  7
8  9  10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 Su Mo Tu We
            Th Fr Sa

I have 10 pieces vaguely named after letters of the alphabet. The can be rotated and turned over.

vvv  iiii  zz   rr  l   pp  u u  ss   ttt  SSS
v           z   r   l   pp  uuu   ss   t     SS
v           zz  r   l   p              t
                    ll

The jigsaw requires fitting the pieces to the board to leave only the month, date and day exposed. I indicate these with "*", so the solution that i used for April 1st was:

2022-04-01 Fr
ppp*zz
ppssvz
*ssSvzz
ilSSvvv
ilStrrr
ilStttr
illtuuu
    u*u

You will observe I have removed excess spaces from the above, so it doesn't "look" a square grid. As far as I know all dates are doable and many in several ways.

My question is: "What sort of algorithm would solve this in reasonable time - I don't want to try anything 80 factorial (10 pieces, 2 sides, 4 orientations) times." In general I can solve them manually in about 10 minutes.

Thanks. -- SGBailey (talk) 12:03, 3 April 2022 (UTC)[reply]

I suspect that with the current typical processor speeds a depth-first search with backtracking will find a solution in a reasonable time, since most of the time the search will hit the end of a dead-end alley pretty soon. Since there are complications near the top of the board (month name, day number, irregularity) and the bottom of the board (irregularity, day name), I'd number the 47 cells to be covered taking turns from the top-left cell and from the bottom-right cell, as shown here for the case of Ap 1 Fr:

  00 02 04 ** 06 08
  10 12 14 16 18 20
  ** 22 24 26 28 30 32
  34 36 38 40 42 44 46
  45 43 41 39 37 35 33
  31 29 27 25 23 21 19
  17 15 13 11 09 07 05
              03 ** 01

(As is usual in algorithms, the numbering starts with 0, so we get 00 through 46.) When the next free cell in this ordering cannot be covered by an omino, the algorithm should backtrack to the previous node. If you can use recursion, this can be coded up relatively simple. --Lambiam 16:21, 3 April 2022 (UTC)[reply]

Because of various symmetries, these ominoes give a maximal branching factor (at the top node) of 58, not 80. Also, you cannot reuse the same omino, so 58! is far too pessimistic. If I'm not mistaken, without any backtracking there are 2·4⁴·8⁵·10! = 60881161420800 combinations to be considered. While humungous if you are not the NSA, this is a far cry from 80! = 71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000. --Lambiam 16:41, 3 April 2022 (UTC)[reply]

So if I am understanding the suggestions right, it is:

[ List the 58 piecevariations then recurse and backtrack seeing if the topmost piece orientation can be placed at the "current square", noting which subsquare of the picevariation was used. If ok, try the next square. etc. If not ok, try the next piecevariation. If not ok and reached end of piecevariation list then rewind one and try again. ]

Coding this will take me a while but we'll see. Thanks (ps there are only 7*366 = 2562 jigsaws to do.) -- SGBailey (talk) 18:44, 3 April 2022 (UTC)[reply]

To get you started, here is the algorithm in pseudo code:

   solve(board, untried):
     if is_full(board):  # yeah, a solution!
        return board
     set empty_cell ← lowest_numbered_empty_cell(board)
     for piece in untried:
       for z in orientations(piece):
         if oriented(z, piece) fits board while covering empty_cell:
           set s ← solve(board union (oriented(z, piece)), untried except piece)
           if s ≠ null:
             return s
     return null

This function should be called with the first parameter representing a board with 47 empty cells, and the second parameter a set of 10 pieces {v,i,z,r,l,p,u,s,t,S}. It uses some auxiliary functions whose meaning is hopefully obvious. To implement this, you have to decide on data structures for representing the board and the pieces, which can be done as lists of sorted coordinate pairs (i,j). (If they are sorted, when trying to fit a piece, if empty_cell is an even-numbered cell the first cell of the piece should cover empty_cell, but when empty_cell is an odd-numbered cell the last cell of the piece should cover it.) To save time, rather than computing the oriented pieces on the fly, they should be pre-computed. --Lambiam 20:16, 3 April 2022 (UTC)[reply]

Thanks. -- SGBailey (talk) 06:06, 4 April 2022 (UTC)[reply]

Sensitivity of Dragging and Dropping

I am using a 2017 Windows 10 desktop computer that isn't ready for Windows 11. I am finding that the sensitivity of the mouse to dragging and dropping is too sensitive, so that a lot of mouse moves that I do turn into drags and drops, where something that I wasn't trying to move, such as a tab in Firefox or a phrase on a PDF, are being dragged and think that they are ready to be dropped. Dropping a tab in Firefox creates a new window, which may not be what I intended. Dropping a phrase from a PDF does nothing, because the PDF is read-only, but it distracts from moving the mouse. What I want to do is to decrease the sensitivity of the mouse to starting a drag and drop. I looked up how to turn off Dragging and Dropping, which can be done by editing parameters in the Registry Editor; but it turns out that turning off dragging and dropping turns off a lot of useful capabilities, so I turned it back on. How do I control the sensitivity with which it starts dragging something? Robert McClenon (talk) 16:29, 3 April 2022 (UTC)[reply]

First here's an answer to your question: Change Drag and Drop Sensitivity in Windows. But are you sure this is what you want? The sensitivity is the distance which it's possible to move the mouse, with the button held down, before the item underneath is picked up and dragging begins. Usually this is four pixels. You might test this by attempting delicate mouse movements and seeing how far you can get before the icon (or whatever) that you clicked on moves. One consideration is that some software may re-implement dragging, perhaps with a distance threshold of zero, so you may want to be sure that the problem is system-wide (perhaps specific software is your real problem, not the system setting). But is it possible that you're getting unintended mouse clicks, rather than having a specific problem with dragging? I don't mean to question your personal experience, but something like an over-sensitive mouse button is an easy explanation, whereas explaining how the system drag threshold could have been somehow set to zero is harder. When you say "mouse moves that I do turn into drags", that suggests clicks are being triggered accidentally. The obvious question: have you tried a new mouse? Oh, and another thought: is there possibly an unused secondary input device, such as a trackpad, which might be interfering? If you'd said "laptop" rather than "desktop", this would have been my guess. I suppose there might be a keyboard key for left-click (manufacturers come up with all kinds of original things) and it might be stuck. Card Zero (talk) 16:57, 3 April 2022 (UTC)[reply]

User:Card Zero - I think that for less than $30 a new mouse is worse trying. Thank you. Robert McClenon (talk) 23:17, 3 April 2022 (UTC)[reply]

Or (assuming it's wireless) perhaps try changing the batteries? Card Zero (talk) 23:50, 3 April 2022 (UTC)[reply]

Yubikeys in banking

Why are banks (of all companies) rarely implementing an MFA based on Yubikeys and instead often use SMS authentication? Is it expensive to implement? They don't want to halfway force clients into spending money on third-party companies and convey the idea that SMS is not 100% safe? They don't think bank accounts are a main target for phishing attempts? --Bumptump (talk) 23:43, 3 April 2022 (UTC)[reply]

While SMS is the most common, I don't know of it's correct to say it's rare for banks to use other means. In the past, it wasn't uncommon for banks to use security token backed 2FA either for all customers or for customers who chose the option, albeit generally with proprietary systems specific to the particularly bank (the devices may be somewhat universal but you generally can't use one for two banks or even for two bank accounts) from companies like VASCO [1], RSA Security etc. These devices generally had LCD screens sometimes with number pads which could be used for PIN protection or to generate a code linked to the transaction. Earlier versions of these devices often predated 2008. Nowadays banks are often moving away from such devices and instead using smart phone apps for their 2FA generally protected with a PIN or biometrics. Nil Einne (talk) 01:41, 4 April 2022 (UTC)[reply]

Presume MFA is Multi-factor authentication, also 2FA for Two-factor authentication. A YubiKey appears to be some form of hardware dongle. SMS is normal phone text. -- SGBailey (talk) 06:13, 4 April 2022 (UTC)[reply]

My wife was part of a study on two-factor authorization for her company, which was a hospital, not a bank. Yubikey was one of the products they checked and they found that customers were absolutely opposed to purchasing a Yubikey device to access their medical records. The lawyers questioned if it would be legal because there are access to health records laws and regulations that prohibit hospitals from making it difficult to access health records. With Yubikey, it was a cost that had to paid to a company that the customers did not know and did not trust for a device that the customers would not know how to use and would certainly lose very quickly. The comittee opted for two choices: Zenkey and SMS. Both only require a cell phone. Zenkey was developed as a joint effort by the cell phone companies in the United States and is very good at identifying a specific cell phone, not just a phone claiming to have ownership of a certain phone number. After multiple rounds of legal questions and customer surveys, they went with SMS messaging. The reality is that anything other than SMS messaging is perceived as an insurmountable hurdle and the customers do not believe that every SMS message is hacked all of the time. So, the risk is minimal. Similarly, I worked with Piggly Wiggly on a system to replace physical loyalty cards with a fingerprint scanner. It is very rare for people to lose their fingers, so it is very secure and easy. Just scan your thumb at checkout and you get all your rewards. Customers found it very scary that Piggly Wiggly was scanning fingerprints. Were they sending all that data to law enforcement so they could track criminals? Was the FBI using it to track people? Legal also questioned the legality of using biometrics, even with customer consent. So, that entire project failed and, in the end, Piggly Wiggly went bankrupt. I believe that both of these examples show that the general public does not see a security threat in the current system and there are many legal issues to consider. In reality, the only problem is that SMS databases are not required to be encrypted and SMS transmissions are not required to be encrypted. They can be. Many years ago, I worked on a contract for Verizon. They were encrypting the SMS database and if the phone accepted it (basically, if it was not an Apple phone), they encrypted the SMS communication to the phone. They could have turned off encryption between then and now, but the point is that they have the technology and they can turn it on. If SMS is encrypted in transmission and at rest, the entire SMS security argument falls apart. 97.82.165.112 (talk) 12:21, 4 April 2022 (UTC)[reply]

It's not clear to me how your SMS encryption system works. If it requires the end user to remove a password or keep a key then I guess this might mostly prevent compromise without user error but seems to significantly affect user acceptance. However if it's on the side of the providers, it wouldn't seem to prevent SMS compromise. AFAIK, the most common method to do so is by tricking the provider into authorising a SIM swap for the number, whether with the same provider or even with another provider via number portability (but I think this is less common since it generally means you are effectively even if indirectly dealing with two providers). See e.g. [2] [3] [4] [5] [6] The SMSes may encrypted but they're still heading to a device controlled by an attacker. Nil Einne (talk) 12:55, 4 April 2022 (UTC

I was not discussing SIM cloning or swapping. I was discussing the two arguments that I far more often hear. First, there is the claim that the SMS database on the provider's end is not encrypted. So, all you have to is get into their computer network and you can open the database and see every SMS message. Second, there is the claim that SMS is sent plain-text over the air. So, all you need is an antenna and you can read every SMS message in your area. Encryption solves both of those problems, even if they are not real problems founded on actual practice. 97.82.165.112 (talk) 13:34, 4 April 2022 (UTC)[reply]

While I can't speak for the OP, when I hear informed people concerned about SMS security or say we should abandon SMS because of the security risks, it's more commonly about real world problems, rather than mostly theoretical ones. E.g. this blog post from Microsoft [7] which got a lot of attention [8] does mention in the clear issues indeed sorta before other issues, which IMO is overprioritising them, however it doesn't seem to suggest they're the main concern. Nil Einne (talk) 13:49, 4 April 2022 (UTC)[reply]

I can only speak for my provider, Verizon. If anyone, including myself, were to attempt to transfer my number to another SIM, it would require that person to login to my account using a PIN sent via SMS to my phone. Then, once logged in, the person has to get another PIN from the website. Then, the person has to give that new PIN to the agent doing the transfer. It is not automated. It is done manually. Finally, once that is all completed, the original phone receives one last SMS message stating that the number has been transferred and then the transfer takes place. I will receive an email telling me about it and I will receive a letter in the mail explaining what happened. The only way to shortcut any of it is to purchase a phone directly from Verizon through my account. Then, they know the SIM of the new phone and are expecting a request to transfer the number. In theory, someone could steal my phone, hack my email, and get all my credentials to login to my account so they can do the transfer to another phone. But, it would be much easier to try and get me to hand over my bank account details so they can simply submit a draft to my account. 97.82.165.112 (talk) 14:12, 5 April 2022 (UTC)[reply]

(EC) I'd note though that although there is a lot of concern over SMS compromise, I'm not actually sure it's as big a deal as the OP thinks for bank security. The first article I linked which while only talking about SIM swaps, mentions rapid growth but we're only talking about $68 million and 1600 customers. These are cases reported to the FBI and the real numbers are likely a lot higher. Still I wonder how large that is compared to other methods like especially social engineering victims. This may entail tricking a victim into installing malware on their devices, using a reverse proxy or even approving transfers themselves. And malware may also be installed without social engineering with software bugs.

Note that as some of the sources say, SMS is particularly vulnerable to malware because viewing and mirroring SMS is something most devices allow with appropriate permissions. By comparison, app security is generally higher, since modern smart phone OSes often allow the app to prevent any sort of screen mirroring or screenshotting with no possible override. "Rooted" phones can generally override such restrictions, one reason smart phone apps often try to disallow people using them on rooted phones. But they're not perfect and some phones may be rooted even without user input. And even if you need user input, if you can trick someone into installing malware, you may be able to trick them into rooting the phone although it's probably a fair amount less likely. If you app isn't compromised (directly or via the OS being compromised), you may also require the user to approve the specific transfer, so reverse proxying probably won't work without heavy social engineering. And likewise I'm assuming it increases the chance social engineering attempts will fail e.g. with a refund scam and similar. (Proper SMS systems help too since they also should tell the customer what the code is for, however as mentioned malware generally negates this. And I expect it's easy to distract a victim into not noticing what the SMS said than it is to get them to approve a transfer on the app.)

I'm not that familiar with how Yubikeys works but I assume it provides limited protection against well implemented reverse proxying. It may offer greater protection against malware, at the very least perhaps only being workable when the user is using the Yubikey device. The bank security tokens are similar although key pad ones can provide greater protection. Notably even with reverse proxying or malware, the customer may need to be making a transfer for you to have any chance of compromising it, or successfully socially engineering the customer into doing something which isn't normal. On the first point, if the bank only asks for you to generate a code based on a number they provide than you can potentially use any transfer to fool the customer. However I'm fairly sure I remember one system which required you to enter the last X digits of the bank account. With such a system you either need to be lucky enough to have an account with matching digits to one a customer is making or use social engineering.

It's perhaps worth noting that while a lot of fraud happens, banks do spent a fair amount trying to prevent it and have their own internal systems to try and detect it that go beyond 2FA. I don't know about legal issues, but do think user acceptance is a big factor why they're not likely to abandon SMS. However I doubt they're hiding the risks, indeed they may talk about them when you ask you to consider security tokens or apps. And getting back to my first point, it seems easily possible that for banks, while SMS security is a concern, it's only a small one compared to all the other risks.

Nil Einne (talk) 13:43, 4 April 2022 (UTC)[reply]

OTOH based on [9], at least on bank in NZ still accepts card based 2FA..... Nil Einne (talk) 10:15, 5 April 2022 (UTC)[reply]