Problem Solving Techniques(denvaar.github.io)
denvaar.github.io
Problem Solving Techniques
https://denvaar.github.io/articles/problem_solving_example.html
23 comments
"Problem-Solving Through Problems" by Loren C Larsen (1983) was my favorite at high school.
The sections headings of Chapter 1 on Heuristics give a flavor of its approach: Search for a pattern; Draw a figure; Formulate an equivalent problem; Modify the problem; Choose effective notation; Exploit symmetry; Divide into cases; Work backward; Argue by contradiction; Pursue parity; Consider extreme cases; Generalize.
Links:
* Official Springer book web site: https://www.springer.com/gp/book/9780387961712
* Amazon: https://www.amazon.com/Problem-Solving-Through-Problems-Prob...
* Poor quality scanned PDF: https://math.la.asu.edu/~ifulman/spring13/mat194/problem-sol...
The sections headings of Chapter 1 on Heuristics give a flavor of its approach: Search for a pattern; Draw a figure; Formulate an equivalent problem; Modify the problem; Choose effective notation; Exploit symmetry; Divide into cases; Work backward; Argue by contradiction; Pursue parity; Consider extreme cases; Generalize.
Links:
* Official Springer book web site: https://www.springer.com/gp/book/9780387961712
* Amazon: https://www.amazon.com/Problem-Solving-Through-Problems-Prob...
* Poor quality scanned PDF: https://math.la.asu.edu/~ifulman/spring13/mat194/problem-sol...
I'll add that this book is well above normal high school math. It was our summer reading for Math Olympiad training.
I narrowly missed a place on the Australian IMO team, and at the time was annoyed at myself for being beaten by a 10 year old. He, of course, was Terry Tao, youngest ever winner of a IMO medal, and a Fields Medalist a few years later.
I narrowly missed a place on the Australian IMO team, and at the time was annoyed at myself for being beaten by a 10 year old. He, of course, was Terry Tao, youngest ever winner of a IMO medal, and a Fields Medalist a few years later.
Theory of inventive problem solving, an in-depth methodology developed in the soviet union.
https://en.m.wikipedia.org/wiki/TRIZ
https://en.m.wikipedia.org/wiki/TRIZ
Unfortunately most of the resources that I know of are more geared toward landing a technical interview. Thanks for mentioning those books though -- I'll have to check those out.
Zeitz is a fantastic book, which I absorbed in early university. It's still a helpful bedrock for my problem solving skills today.
Street Fighting Mathematics, and The Art of Insight in Science and Engineering, both by Sanjoy Mahajan. You can find the PDFs online.
- "The Complete Problem Solver", John R. Hayes
- "General Methods for Solving Physics Problems", Belikov.
- "General Methods for Solving Physics Problems", Belikov.
It might be too basic for you but I'm really enjoying working through some of the Art of Problem Solving book series (Introduction to Counting and Probability). I have a PhD in biomechanics but still find many problems to be a fun challenge.
Mathematical problem solving by Alan Shoenfield
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.
Thank you, I felt this was important and just hand waved away in the article.
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.
Thanks for reading. I agree with your feedback. My goal was to try and understand how to form that "intuition". Like you say, I think most of that is done through practice. I may edit to emphasize that point more.
> 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.
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").
- 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
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!
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!
Thanks for reading
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.
/ * 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:
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?
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?