Problem Solving Techniques

People often talk about the importance of problem solving skills, but there's shockingly few resources that analyze the problem solving process from a general point of view (outside of some problem solving domain). Does anyone have any non-orthodox suggestions for books/essays on problem solving?

Polya's "How to Solve It" and Paul Zeitz's "Art and Craft of Problem Solving" are both great. Are there other resources on this topic that are worth reading?

This is the shortest common supersequence problem (https://en.wikipedia.org/wiki/Shortest_common_supersequence_...). It's NP-hard if you include repeating numbers; there's no simple changes to make your solution work in that case.

I liked the write up, it's very clean and understandable. Though I feel the point about practice should be more emphasized. Solving complex cs/math programming problems makes you better as cs/math problems. No matter what techniques you know, without intuition (which comes from practice) you cannot really use those techniques effectively.

> Try not to jump straight into the code, sometimes it's OK, but it can also be distracting. I strive to first form a reasonable conceptual model of my approach before implementing it in code.

This was probably the key takeaway for me. Too often, specially when I'm solving hackerrank/leetcode challenges, I jump straight into the code without bothering to think about the problem first, at least for a moment.

Now I keep a physical notepad to write and/or draw at least basic models of whatever non-obvious problem or issue I'm given. I've noted that it's helped me quite a bit, at least to give me a general idea of what I should do.

From my first few minutes of thinking about the problem (essentially scrolled right to the problem statement):

- Something about it reminded me of Project Euler. Shortly afterwards read the surrounding text confirming that.

- The problem should be pretty easy to solve if we could assume that each digit is unique (i.e. appears only once in the pass phrase). Clearly the challenge here comes largely from digits being possibly present multiple times. A greedy algorithm could start with this assumption and then, upon encountering a contradiction, duplicate a digit. To decide whether such an algorithm is optimal you'd want to try and construct an example where it produces a suboptimal result. Might lead to a few iterations of refining and seeing whether you can keep it greedy.

- Could this problem be NP-hard? Could you encode NP problems in the ambiguities of "are these two identical digits also the same ones in the passcode"? At this point some meta-solving comes in: Project Euler problems allow brute-forcing in principle, but usually it won't get you far without at the very least a clever reduction. 50 login attempts might be on the order of 10-20 digits in the passphrase (if you assume digit positions being chosen at random, you could actually get a decent estimate), which is not amenable to pure brute force.

- Is it possible that there is no unique solution? It seems very likely to me, and I should probably try to construct an example. (I won't, because I'm trying to only scope out my own solution process).

- I tried to frame the problem as a partial ordering, but the difficulty is (again) in the label ambiguities. Could we give a different label to every single given digit and then try to merge them? Can this be done greedily? What to do with ambiguities? The above considerations return, from a different angle.

- The unknown length makes the number of unknowns, well, unknown. But you could postulate a length, giving you a fixed number of unknowns that need to be assigned.

- It's impossible to observe my own problem solving process without impacting it. And writing it down tends to affect it very strongly (mentally drilling down into individual facets instead of staying at "surveying level").

Mine was: step 1: which number is never shown after others? it must be first. now which number is never shown except after that one? etc. so it took about 30 seconds in my head. The trouble is I spent fifteen minutes before this in an absolute rage at how OP, and then with commenters here backing him up, seemed to be answering something different to what the question asked because I can't read "determine the shortest possible secret passcode of unknown length" anything other than a weird way of asking "what is the minimum length". My mind just locked in to my wrong understanding. I think my problem solving was better than the people spinning up elaborate code, but it seems at the cost of lateral thinking needed for "problem understanding".

please note that several of the commenters today are accounts created just to praise OP

Good article, and fun problem!

My way of solving this was to write down the rules of which the digits appear paper with a pen. Liked that you pressed for that in the article, it really helps me to understand.

However my own weakness is when it comes to put this down to code. I often tend to only use pen + paper when things can be automated. It was great to see your approach of first writing a simplified algorithm - and then take it all the way insightful.

Going to try out this in the future, thanks for good read!

It seems amenable to constraint propagation + search. Assuming no repeating digits to start with, each digit is assigned a position variable on which sequence constraints can be applied, propagated and searched. You might end up with no solution if the tightest length of the sequence is assumed, so the search process must also relax that to the extent necessary to find one .. in which case you'll have holes in the result I suppose.

nice readup, Had to lookup how I did solve this problem because I could not remember it. I solved it when I was about to join a university.

/ * Created by Sneeuwpopsneeuw on 28-Aug-16. */ The code Is one big commend that basically says use ctrl+f. I found 2 items in the list that I thought where the beginning and end. Based on that I filled in the missing digits.

Step 0: discard unnecessary information and recode the problem to make plain what is actually being asked for.

A string that contains each three-tuple in order but not necessarily contiguous, and is the shortest possible string that meets this criteria.

The second clause of the problem rules out simply concatinating the fifty succesful login attempts. But that does give us an upper limit on the length of the string.

N[max] = 3 * 50 = 150

Next consider the simple brute-force solution: Iterate through the integers from n (to be determined later, for now set it to zero or one) to 10^150 - 1 and check each one. Halt when the solution is found.

Depending on the urgency of the situation this is as much thinking as you might need to do. There are several fairly obvious ways to trim the amount of integers you would need to check.

But of course, the generate-and-test strategy is overkill for this problem, and relatively uninteresting compared to the possibility of devising a clever mathematical or logical solution.

One angle would be to explore generation functions that might produce minimal strings directly from the set of three-tuples.

Another angle would be to set up the problem for a contraint-solver. I'm a little rusty these days but I think you could convert the problem to a SAT instance and use an off-the shelf SAT solver.

(As an aside, watch out for unfounded assumptions, e.g. maybe all ten digits don't appear in the logins. Do digits appear more than once in a given keylog entry?)

It took me about ten minutes to write the brute force python code, and about half an hour to get it to work. (The biggest problem I had was debuggin a stupid Python 2/3 error: map() returns an iterator now not a list. FML. Also, getting conda to work in windows with vscode was a lil hassle (use cmd.exe not PowerShell.) FML.)

For the curious:

    keylog = list(map(list, '''\
    319
    680
    180
    690
    129
    620
    762
    689
    762
    318
    368
    710
    720
    710
    629
    168
    160
    689
    716
    731
    736
    729
    316
    729
    729
    710
    769
    290
    719
    680
    318
    389
    162
    289
    162
    718
    729
    319
    790
    680
    890
    362
    319
    760
    316
    729
    380
    319
    728
    716'''.splitlines()))


    def predicate(N):
        f = N.find
        # This works because there are no repeated digits (like 112).
        for a, b, c in keylog:
            i = f(a)
            if -1 == i:
                return False
            j = f(b, i)
            if -1 == j:
                return False
            if -1 == f(c, j):
                return False
        return True


    def do():
        n = 9999
        while True:
            N = str(n)
            if predicate(N):
                print(N)
                break
            n += 1

    do()

Is it only me or nobody else also having problem accessing website?