I am struggling with relatively simple algorithms. Am I doomed?

November 23, 2009 2:38 PM

ProgrammingFilter: Just how lame is it that I can't come up with (create from scratch) a string matching algorithm? Can I still become a programmer? I need your honesty.

Coming up with a simple string matching function is one of the problems I've been working on for an intro programming class: i.e., determine whether the second string can be found in the first string and return $found = true or false.

My sense is that, for any semi-intelligent trying-to-learn-programming Person Who Applies Herself, this should not be all that difficult. I think of myself as pretty darn intelligent. And yet, I've put about 10 hours into this so far and am ready to conclude that I CANNOT DO THIS. Yes, I've broken the problem down, I've tried to draw flowcharts. I've made many starts and stops. Ok, given a cave and maybe 3 days, I could probably to do it. But that's not the point. I should have been able to figure this out by now.

I have a background in literature and just don't have what they call a 'natural aptitude' in math and logic. Up until now I've told myself that it's ok not to have a natural aptitude in something: hard work and practice will get me where I want to be. At least, that's what I thought until right about now.

My question is this - and tell me the truth. How ________ (insert derogatory adjective describing my intelligence) am I for not being able to come up with this algorithm? And please be honest. Should I start reconsidering my plan to become a programmer?

Thanks in advance.

posted by kitcat to education (44 comments total)

Hmm ... surprisingly, it may depend a lot on what language you are using. String matching is IMO best in a place done closer to assembly language than most other programming you're doing. Those languages however have a very tight cognitive fit, usually, and what works as a tool for one man won't do for the next one.

What are you using?
posted by krilli at 2:46 PM on November 23, 2009

The first time it will break, you will do the wrong thing, you'll fix it and it will STILL break, you'll still do the wrong thing.

In literature its often said that great writing comes from practice. It's the same in programming. Don't sweat it, take the pressure off, write an algorithm, see where it breaks, and fix it. IT WILL GET EASIER AND MORE NATURAL WITH TIME.
posted by gadha at 2:52 PM on November 23, 2009 [2 favorites]

Have you studied the abstract basis for this kind of pattern matching? I mean, no one is really expected to reinvent DFAs from scratch if that's what you're asking. But I suppose you should be able to code a really bad routine to do it given a few hours. It should be fairly easy to create a bad solution to this problem. A non-backtracking solution is somewhat harder.

I suppose it does depend a little on what language you're using. I'd never be able to do this in LISP or Ruby (ignorance, not because it's not possible) but I could in C.

Also, try again tomorrow. 10 hours in one block is a bad way to devote 10 hours to a problem.
posted by GuyZero at 2:53 PM on November 23, 2009

Also, debugging. Your first algorithm will never work. That's pretty much a given.
posted by GuyZero at 2:53 PM on November 23, 2009

Everyone hits something that they totally don't get for whatever reason. Don't let one stumble convince you you're no good.

When you get stuck really badly on something, step back and start by doing as naively as possible. Fuck flowcharts and graphs and even computers for a moment. Let's say, you, kitcat, were going to try to find a string inside another string without a computer. Start with two specific strings like "kitcat" and "cat". Write down how you did it, in code or pseudo code. Then, try it with another case like "kitcat" and "frustration."

Once you've done this, you'll have an algorithm. Don't worry about whether or not it's a good algorithm or even one that'll handle cases outside of the few you've tested it on. Translate it into code, then try it on the cases you've built it on. When you get it to work there, you might feel pretty good about that.

Then, try it on more cases. When it fails, look at why it failed and change your algorithm and code to cover that. Eventually, you may notice something that'll greatly improve it. Or maybe you won't. Either way, you'll have at least a program that matches some strings. Your professor or classmates will get you the rest of the way there.


Definitely don't be afraid to ask professors and TAs for help, even if all you can say is "I don't know where to start." I wish I did this more often in college.
posted by ignignokt at 2:53 PM on November 23, 2009 [9 favorites]

You don't really need an aptitude in math to succeed as a programmer (depending on the type of things you want to program, I suppose!), but logic is critical. Ultimately you're deciding how the machine will step through your instructions, and it makes decisions literally with logic. There's a difference between "not having an aptitude" and "not being any good at", however: if after having it all clearly explained you still can't write a truth table for AND or OR, you're not going to fare terribly well at programming.

But this exercise isn't going to return a verdict on whether you'll succeed as a programmer; like many other similar exercises it really just shows your familiarity with the field. If you'd read classic tomes like K&R you'd already know how to do this, because it's in there. Likewise, if you'd already learned to think like a computer (an essential skill to fully understand any code you're reading), you'd know how to tackle this program. It's the same problem I had when they tried to teach me football at school -- the assumption was that you already knew the rules of the game and just needed to learn technique. I didn't know the rules, and being able to kick the ball was therefore useless, and I just got frustrated and failed.

What you're trying to do here is similarly pull yourself up by your bootstraps. Writing algorithms can be difficult: there are reasons that programmers keep books of them, and why someone finding a better sort than Quicksort is a Big Deal. It's like discovering mathematics: Pythagoras had to bend his brain to come up with his theorem, but children can manipulate it. That this particular algorithm is at the easier end of the spectrum makes no real difference. We don't ask kids to come up with a way to do long multiplication.

What your inability to solve this problem suggests to me is that you can't think like a computer does. You don't know what a string is to a computer. This doesn't mean you can't program, it just means you can't get there from here: you need to start your learning at a different position.

I'd talk to your teacher; say that you don't think you'd have difficulty working out the solution if you knew how to get to the handles of the problem, that is, if you knew how to think it through like a computer.

If you want to get a handle on it yourself, I'd suggest reading Code: The Hidden Language, as an excellent primer.
posted by bonaldi at 2:54 PM on November 23, 2009 [1 favorite]

You can do it.

It might take the cave and three days, but you can do it.

Then, the next time, it'll take not a cave, but a closed door and two days. And then, a shoji screen and 4 hours, and so on. You will eventually find that it gets easier. Learning how to explain a process to a computer is not something that comes naturally to most people. I am in complete agreement that natural aptitude is nothing compared to hard work and practice. In fact, I'll go farther and say that in the programming world, a "natural aptitude" at programming is far less important in the long haul than is overall clarity of thinking (which some programmers have or obtain) and the ability to communicate ineligibly (which most programmers don't have or don't want).

You didn't ask for help with your specific problem (and good on you for that) but if things get too hairy then I don't see why you can't look at some pointers.
posted by lex mercatoria at 2:55 PM on November 23, 2009

Persistence is often worth more than natural ability. Learning to think in a new way is painful and difficult. Along the way, there will always be some terrible soul crushing challenge. Everyone reaches the breaking point you are at now at one time or another. I know people who couldn't do fractions and ended up doing better in calculus than the people who were previously "good at math." The reason they did better is because they learned how to struggle, study and not give up. People that are good at things often float and then are blindsided by challenges and they don't know how to proceed. Solve this problem even if you have to get outside help to solve it. Then, keep going. In a year, you will look back and chuckle.
posted by milarepa at 2:57 PM on November 23, 2009

Aw, you've all made me feel better. It's really nice, because I'm truly feeling kind of heartbroken over this.

Still, be honest.

Just to clarify a couple things - it hasn't been 10 hours at one go. More like 2 - 3 hour blocks.

Also, the language is PHP.
posted by kitcat at 3:01 PM on November 23, 2009

It's not necessarily that bad. Yes, finding a string within another string is a fairly basic task. But you're just starting out, and things take time to learn, even basic things. Give yourself time. The best programmers I've ever known were patient; while this aspect of my experience may be coincidence, I think their willingness to spend time within the guts of a problem helped make them smarter, rather than their having simply been born geniuses.

Most languages you'd probably be using do string-matching sorts of thing out of the box- they'll have some function or method you could call that would do the finding for you. You might not be ready to start programming in C right now, but even lua and javascript have "give me the matches for this string inside this other string" functions.

Yes, I've broken the problem down,

The success of this method for any given problem depends on the dimensions along which you attempt to break the problem down. If you don't mind me skipping the forest for a moment and instead focusing on a few trees...

Can you determine whether a given character is within a string?

Once you can do that, the next step is to see whether your string contains two specified characters right next to each other in a row. If you can find the first, you need to return true if the other given character is the very next character in the target string.

Once you can do it for two characters, then you might be able to figure out how to do it for any number of characters- an arbitrary input string.

------------

You also might want to try out a bunch of different kinds of programming. Different apps have different flavors. Programming for embedded systems feels different from desktop application programming feels different from web programming feels different from game programming, etc.
posted by Jpfed at 3:01 PM on November 23, 2009 [1 favorite]

Oh- just noted you're doing this in PHP. PHP has a reputation for being a practical (if not especially theoretically beautiful) language; while I've never programmed in it, I would be very surprised if it didn't have a string-matching built-in function.
posted by Jpfed at 3:04 PM on November 23, 2009

"Communicate ineligibly"? Is there a name for a self-referential typo?

Incidentally, the pointer I provided above is to an algorithm which can be proven to be as good or better than any other algorithm. My point wasn't that you should read, understand, and emulate that particular algorithm. My point is that when you are learning something totally new you need to make some allowances for yourself. You goal may have been to write the algorithm w/o using any outside sources. If that's got you beat, then look around for inspiration and see how others have done it.

What you don't want to do it to look at something and say, "Oh, I get it" and leave it at that. You need to practice working with indexes into arrays and keeping track of the various moving parts in an algorithm. So once you've gotten inspiration, continue on your own with the dirty details.
posted by lex mercatoria at 3:07 PM on November 23, 2009

For this assignment, is there any requirement that the program be particularly efficient, or is it enough that it works? Even if the final program needs to be efficient, you should consider trying a completely simplified, naïve algorithm. The string-matching equivalent of bubble sort, if that means anything to you.

Consider breaking it down into the simplest case: Given a string, does it contain a given character? Make that program and verify it works.

Alternatively, think about another simple case: Given a string, is it exactly the same as another string? Make that program and verify it works.

Then, think about how to generalize those to checking a string for a substring.

Above all, don't lose heart and don't be afraid to talk to the TA or professor. I went through much the same experience you're having on a couple of occasions: quick sort and a queuing simulator. In the first case I should've sought help and didn't, to my detriment. In the second case I did seek help and the professor helped me work through what I was having trouble understanding. There's absolutely nothing wrong with being stumped occasionally and it doesn't mean anything about your ability to learn how to program or about computer science.
posted by jedicus at 3:13 PM on November 23, 2009

Don't worry about it. I've been programming professionally for some 8 years now, and I'm not much good with algorithms - haven't needed to be. I've written many programs that do useful things and solve hard business problems, but because I mostly use Python and Java, I've never implemented a string search or a linked list or a hash table from scratch, and I probably never will. You probably never will, either, depending on how you end up using programming and whether you become a full-time programmer or use it just as a tool in a broader job.

I think Jpfed and jedicus have the best specific advice - start by finding a single character within your string and build on that. Don't worry if you end up feeling like you've come up with something horribly inefficient or complicated, because once you make something work - even if it's shaky - you've learned something that will make next time easier. And don't worry if you hate algorithms and the "computer sciencey" side of programming. You can still be a happy and successful programmer.
posted by pocams at 3:17 PM on November 23, 2009

Should I start reconsidering my plan to become a programmer?

You'll definitely write this function at some point. However, if you're thinking about programming as a career, you really need to consider whether or not you want to go in to a field where you'll be competing with a bunch of people who have a) been doing this since they were 12 years old and b) had, comparatively, an extremely easy time writing this function when they tried it the first time. It's really not about whether you're smart or dumb, it's whether or not there are a ton of people who have a knack for this that you'll be competing with for positions and promotions - and there are.

There are plenty of careers out there and life is too short to work in something you're not talented in, especially one where management can be ruthless in "ranking and yanking" lower performers. I don't want to discourage you from programming itself - I enjoy playing guitar despite the fact that I am unbelievably bad at it even after 10 years of playing. I have no aspirations to be a professional musician and am totally cool with this. It's just important to be realistic about what career choices are smart given the talents you've been given.

I was a grader for lower-level and higher-level Computer Science programs at my college. The best indicator for whether or not someone was successful in the more difficult courses wasn't whether they worked hard or not, it was whether they did well in the lower-level courses. A lot of people came in to that college intending to be a CS major, took CS100, and promptly switched to a different major and had a lot of success there. No one took CS100, did poorly in it, then "got it" later on and became really successful academically.
posted by 0xFCAF at 3:34 PM on November 23, 2009 [1 favorite]

I agree with everybody else, I think you might have fallen into the trap here of not trying anything on the problem until you've got the magical super-elegant algorithm that solves it really simply and with no repitition.

However, the truth is that nobody ever comes up with the elegant algorithm first go (okay, maybe some people, but not most of us plebs!). Best approach is just to do it ANY way that you can and then once you've got something that works, then you can try and optomise it. It's so much easier to take a working algorithm and make it more efficient than to get the super-efficient algorithm without trying anything first.

(As an aside, I'm a university professor and I teach programming and I can tell you that you are right and some people just don't get it! No matter what you do, they just don't have the logical mind for programming. Others are naturals at it. Then there's the rest, who will never be super-efficient programmers, but they can write the code, work the algorithms with the best of them and could easily be a coder as a career, so don't give up yet!)
posted by ranglin at 3:41 PM on November 23, 2009

I've taken 28 CS classes and taught Intro CS. Your problem sounds typical for someone just starting out. You're not weird at all.

Persistence is EVERYTHING in CS. Don't let anyone tell you that you can't do it, either because you're a woman or because your background is in literature. Stick to it and never give up.
posted by miyabo at 3:43 PM on November 23, 2009

As a CS/CompEng student who considers himself to be pretty good at programming, the best piece of advice I can give you when you encounter a problem is to step away from it. You'll spend hours working on something and make no progress, and then when you walk away from it and focus on something else for a while, it'll come to you. Most of the time I have a seemingly insurmountable problem, a solution pops into my head while I'm cooking dinner or taking a shower or whatever. It really helps to take breaks. After a while the lines of code start running together.

There is a certain mindset you have to get into in order to write programs; basically, you have to learn to think like the computer thinks, which can be a difficult concept to grasp. It does get easier with time, but like some of the others have said, you should never expect to get something to work on the first try. I've been doing this for a few years and I still can't look at most problems and immediately solve it in the most efficient way possible. What you do instead is get something that works, or kind of works, and then look at it with fresh eyes after some time away from it, and see if you can find a way to improve your algorithm. Rinse and repeat.

Good luck to you. It feels really great when you finally get it to work--really satisfying. Just keep at it and remember to not stress yourself out over it. Working 10 hours at a stretch is a good way to get burned out.
posted by DMan at 4:09 PM on November 23, 2009

In some ways, computer programming is the pursuit of metaphor; ever new layers of abstraction pile up on top of each other in coherent tiers of utility and function. Identifying the operative metaphor for any given layer - and recognizing when the underlying abstraction is leaking out into what you are working on- becomes a lot of the work. In some ways, a literature major may be well suited to identifying these layers- and when they fail to hang together.

This is more important when you get farther along; the initial algorithms are fairly mechanical. Once you grasp the metaphors that people use in architecture and development, you'll be fine- it just takes a while.
posted by jenkinsEar at 4:10 PM on November 23, 2009

I'm an amateur hacky programmer, since childhood, and I spend a lot of time around programmers, but I have no CS or CE degree.

The pros here can correct me, but I think that failing and learning why something fails is how learning programming works.
posted by rokusan at 4:14 PM on November 23, 2009

Upon reading the thread again, I wanted to add a few more things:

Didn't realize your 10 hours was split up into 2-3 hour blocks. Sorry. That is better, but in any case, if you're working on it for a while and you aren't making any progress, just stop and work on something else for a while.

And yes: Ask for help. Professors, TA's, other students. Every time I've asked a professor for help, I've gotten more assistance than I expected. They really are willing to help. And if you can find another student who seems to understand the problem and solution, try asking them for help. I help other kids in my classes all the time and am happy to do so. They help me when they understand a particular assignment better than I do. An integral part of what you learn in school, but what isn't really expressed in words, is knowing how and where to ask for help. Metafilter is certainly a good start and it seems like we have a fairly large amount of programmers here, but asking someone to sit down with you and look at your code would probably be helpful.
posted by DMan at 4:19 PM on November 23, 2009

How are you trying to come up with an algorithm?

Two books that might be helpful in learning to think about coming up with algorithms: Polya's How To Solve It, and Manber's Introduction to Algorithms: A Creative Approach.
posted by phliar at 4:22 PM on November 23, 2009

I've been programming for, oh, about 27 years. I still bang my head against a wall and spend way too long on problems that "shouldn't" take as long as they do.

One thing I've learned is that it really helps to step away from a problem for a while. It's far too easy for your brain to get into a mental rut if you're staring at the same problems for hours on end. Most of my "ah-ha!" moments come around 9:30 in the morning after a good night's sleep.

Programming is a beautiful but harsh mistress. Beautiful because the logic is fixed and pure, harsh because you can be this close to fixing something and still have the same busted result. There is no forgiveness, but at the same time, it is all knowable. But until you know it, you don't. There is no "kind-of" knowing. Which is why sometimes it will take ten hours to get something working, and sometimes it will be instantaneous. In reality, it's all instantaneous. It's just that sometimes you spend 9.9 hours waiting for that instantaneous ah-ha to happen, and sometimes the programming gods smile on you and you get it right away. Rather like writing, actually.

If you're trying to wrap your head around something brand new, start small. Don't just try breaking down a big problem into little bits... that's like disassembling a watch to find out how it ticks. If you've ever tried this, you'll know right away that it doesn't work that way. What you'll end up with is several hundred very tiny parts and no idea of how to put it back together.

Instead, concentrate on starting small and building up. For the clock analogy, maybe you first make a watch face and some hands. Attach the hands to a gear. Attach another gear. Each step, make sure it's working right. Occasionally you'll hit a dead end, and you have to rewind a couple of steps to see what you've done wrong. But it's a hell of a lot easier to do this when you only have a few parts to deal with instead of a hundred.
posted by Civil_Disobedient at 4:22 PM on November 23, 2009 [1 favorite]

Yeah - This is a practice thing, and as people have pointed out, it's not unusual to get stuck on something like this which (a) should be simple and (b) isn't really that simple.

So for example. I specced out in my head how I'd do it, and realised 9/10ths of the way through that my head code wouldn't work in some cases. i.e. It wouldn't be able to find AAB in the string AAAB. (And I've 28 years coding experience)

People have given out good techniques for working this out, but be aware that not every technique works for every person. Try each technique, but don't be disheartened if a specific technique doesn't work for you.

Some other things:

1) Keep at it.

2) When you've worked it out, can you post your code here. I'm curious as to how you eventually solve it.
posted by seanyboy at 4:23 PM on November 23, 2009

I can remember a couple of things in my life which might be relevant. The first thing is the "word problems" I encountered in algebra class in 7th grade (age 12 or so.) I found them at first to be *horribly* difficult, and was reduced to tears by homework assignments more than once. Eventually, after bashing my head against them enough, I kind of got the hang of it.

The 2nd experience, I was trying to come up with an algorithm to convert binary to hex. (This was for a sprite-drawing program I was making on the ti99/4a, which let you define the shape of a sprite via a string of hex digits. But I digress.) Eventually, I had to ask my dad for help on that one (I was probably 13 years old at the time.) He came up with a solution which involved indexing into a string, "0123456789abcdef", using 4 bits at a time as the index. In retrospect, it's easy. I studied what he came up with until I understood how it worked. But at the time, it struck me as being so extremely clever a solution that I never would have come up with it on my own, not in a million years. This turns out to be false, at least the million years part. With practice, studying other people's code, and most importantly, *writing your own code*, you just kind of gain experience and you start to recognize problems, and in short, with time, you get better at these sorts of things. It was similar to the algebra word problems, in that what at first seemed impossibly difficult eventually yielded to persistent effort.

That being said, anyone's first string matching algorithm will likely work, but will likely be non-obviously sub-optimal, and not as good as say, the Boyer-Moore algorithm.
posted by smcameron at 4:28 PM on November 23, 2009

To address your career concerns - rather than beating yourself up about not being able to figure this out, I think the question you should be asking yourself is, am I enjoying trying to solve this puzzle? Did I start out enjoying this? Or does this just suck? Although I'm frustrated am I still compelled to work on this? If I go for a walk, does my mind wander back to this problem on its own, or am I *done* thinking about this?

For most of us (geniuses aside) a career as a programmer is all about solving puzzles, and often the process involves getting frustrated. I think to be happy in the field you have to be ok with being being in a place where you're simultaneously frustrated and compelled to keep working. You also have to enjoy the process of breaking apart a problem, that process can be different from person to person. If you aren't finding that pleasure in it your workdays (to say nothing of classwork) are going to be interminable.
posted by snowymorninblues at 4:30 PM on November 23, 2009 [1 favorite]

Are you running into problems designing the right algorithm, understanding how the language works, writing correct syntax in the language, or something else? It might help to post what you've done so far. I doubt that it's the algorithm itself that is giving you trouble, but rather one of the scores of traps and pitfalls that your programming language has set for you.
posted by jewzilla at 4:39 PM on November 23, 2009

Also, I disagree with some of the comments here. (my opinion, so best taken with salt)
- Apart from thinking about "What character is at position {n} of a string", you don't really need to be looking at pointers.
- You also shouldn't think that coding this would be simpler in assembler or c. It isn't really. And screw K&R.
- You'll never have to write this function professionally.

And I agree with some things too.
- jpfed and jedicus have the best advice.
- You do need to know what a string is. i.e. it's a collection of characters. ('k','i','t','c','a','t')

Finally, (and this isn't for you question asker, so look away now), I thought of two ways of doing this. I dismissed the second way because it seemed like cheating. And then I found out that new low level programming language Go uses that second method for it's version of this function. Not sure why they've done it that way. I suppose the string equality functions are optimised. (Or the index function is not optimised)
posted by seanyboy at 4:48 PM on November 23, 2009

snowymorninblues has it. I've been a programmer for 20+ years and I was definitely where you are now
(and sometimes still feel that way :-). If you enjoy programming, keep at it and you'll get it. There's
lots of value, and no shame, in looking at other peoples code.
posted by luge at 4:52 PM on November 23, 2009

You can probably get something out of it and that's all good. That doesn't necessarily mean you'll become a master or even make a living out of it. But if you don't engage in intellectually challenging pursuits your wasting gray matter.
posted by chairface at 4:59 PM on November 23, 2009

I work with php for a living and off the top of my head the only way I know to do this ("from scratch" without using existing functions/libraries that do precisely this) is grossly inefficient. I also come from a literature background so there's definitely hope for you.

also second this from seanyboy heartily:
You'll never have to write this function professionally.
posted by juv3nal at 5:23 PM on November 23, 2009

The only way this is a disqualifying event is if you find this sensation so unpleasant you simply cannot be bothered to go on. You have met the essence of programming: Need to do X, Cannot get X to work, ready to fling X on the ground and stomp on it and call it names to make it freaking WORK already.

The first time you do a new thing, it will suck and make you mad. Two years from now, you will be laughing your ass off at this, at 4am, trying to make some other damned new thing WORK already.

I think it's good to have the experience even if this isn't what you're going to spend your life doing. I'm a software consultant, and spend more time than you'd think writing T-SQL and little VBscript scriptlets, which most of my coworkers can't do because they have no programming exposure. Programming, no matter how crappy I am at it, has made me a better problem-solver. And I cry less at 4am, because I know I'll eventually bust through the problem or find the resource to help get it busted.

Don't be afraid to go ask for a hint. Say you're clearly thinking about it wrong and need a point in the rigt direction; this is an exercise you have to do because it IS hard, but out here in the real world we use Google and colleagues to punch through the hard stuff. You need to be good at that part of it, too.
posted by Lyn Never at 5:30 PM on November 23, 2009

Maybe I'll post my code once I get it working. Just to show what all the fuss was about :)

I appreciate all of these answers and simply can't mark a 'best'. I especially appreciate "Programming is a beautiful but harsh mistress" and the book recommendations, though. Thank you.
posted by kitcat at 5:44 PM on November 23, 2009

I learned BASIC programming in 8th grade. The two things that gave me fits were 1) arrays and 2) loops. Coincidentally, your problem involves both. (You will be treating the strings as arrays of individual characters.) So it's no surprise that you're having some difficulty.

I would make sure you fully understand these two concepts individually, using exercises designed to teach just one concept at a time, before trying to combine them. Then, when you combine them, try simple exercises like printing the elements of an array backward.

Also, keep in mind that this is just an exercise designed to teach you the concepts of arrays and loops. It is not designed to teach you how to match strings. If you become a programmer, you will rarely have to write a string-matching routine. "Does this string contain this other string" is a commonly-used function and will be in the library of whatever language you use. It might even be an operator and thus a fundamental part of the language (in AppleScript, for example, you simply say "if a is in b"). In fact, as someone has pointed out, PHP can do this for you with a built-in library function. So keep the goal in mind, which is to learn the concepts.
posted by kindall at 5:52 PM on November 23, 2009

There's a difference between the problems of "I can't figure out an algorithm to do X" and "I can't figure out why my PHP code to implement the algorithm to do X doesn't work right". Which problem are you having?

Figuring out algorithms is actually the hard part of programming. Some can be tricky, but most of them seem obvious in retrospect.

Coding it up and debugging can be difficult for different reasons. Experience counts a lot for debugging, and even with experience, you'd be surprised how many hours are spent wasting time due to typing i instead of j in some nested for-loop.
posted by demiurge at 5:54 PM on November 23, 2009

String matching is IMO best in a place done closer to assembly language than most other programming you're doing.

String matching is actually an algorithmic problem. These days, the language is almost a triviality, compared with the runtime and memory characteristics of the algorithm used. This differentiates computer science — research about algorithms and more abstract computing problems — from computer engineering, which applies that science to implementation. Programmers generally fall into the class of engineers, but may not always be scientists. It is not absolutely necessary to be a computer scientist to be a good programmer.
posted by Blazecock Pileon at 6:30 PM on November 23, 2009

I'm assuming here that you're not supposed to use PHP's bulit-in string utility functions. That said:

Try breaking your problem down into smaller sub-problems. Write a routine to figure out if two strings are exactly identical. If you have that and a way to 'clip' out substrings, you should be able to see a way to solve your overall programming problem from there. It may not be the most elegant solution, but as others said, you'll never actually have to implement this in real life. At this early point in your learning, it's more about concepts ("How do I determine if a sequence of objects is contained in another?") than the actual nuts and bolts.

Also, nthing the advice that you might be better off with an iterative approach to the problem than trying to lick it all at once. Start with something half-broken and incrementally improve it, rather than trying to fashion the perfect solution in one go.
posted by axiom at 6:57 PM on November 23, 2009 [1 favorite]

DMan: the best piece of advice I can give you when you encounter a problem is to step away from it. You'll spend hours working on something and make no progress, and then when you walk away from it and focus on something else for a while, it'll come to you. Most of the time I have a seemingly insurmountable problem, a solution pops into my head while I'm cooking dinner or taking a shower or whatever.

Just to give you some more encouragement, this is the key, and is exactly how I code. A lot of times I'll read the requirements, try to work something out, and fail miserably. However, while I'm doing something completely off-topic, the solution, or at least the next waypoint on the journey, will pop into my head. Once I get back to working on the problem, the lines of code flow like rain. You can do this. :)
posted by fireoyster at 7:43 PM on November 23, 2009

The two main tools a programmer has in algorithms is deconstruction and composition. When you can't solve a problem, try solving a simpler one first; perhaps the simpler solution can be applied in multiple times. In your case, try writing a function that can tell if two strings a and b start with the same letter. Then rewrite the function to return true if two strings a and b match at position n. Then write a function that can tell if two strings are equal, using the previous function. This is composition. You build something large out of smaller components.

Truthfully, composition is the only sane approach in any engineering field. Encapsulating whole fields of meaning within a simple function call or schematic symbol is imperative to actually understanding the solution you write. Flowcharts are a weak tool to handle complexity because they can't condense meaning the way functions can.
posted by pwnguin at 1:12 AM on November 24, 2009 [1 favorite]

On review, I guess my above post agrees with axiom's. I'll add that the most of algorithm design is determined in advance by the data structure, and by transforming one data structure into another for processing. The advanced, efficient algorithms people have suggested require you to transform the query string into a graph (specifically, a Finite State Machine) and then process that FSM in conjunction with the string to be searched. An intro to programming class won't cover these in enough detail for you to do this, so just focus on understanding the data structures you're given arrays and strings, and come up with something that works, even if it's inefficient.

If you don't know how to access strings/arrays in PHP, all hope is lost until that point, because this problem decomposes at its base to "return the nth letter of a string". If that's the case, consult the language documentation, and then your instructor. I admit that at this very moment, I'm writing a PHP webapp, and even I don't know how to write a PHP function that returns the nth letter of a string; I consult the language documentation daily to learn discover these things.
posted by pwnguin at 12:19 PM on November 24, 2009

Being as I am currently interviewing for programming jobs and this is definitely a question that could come up, I sat down to write this algorithm as a test to myself after reading your question earlier tonight. I took a fairly heavy course load in CS for my undergrad, and do quite a lot of programming in my day to day work, although I am definitely not a master programmer. I knew going into it that there would be two types of "naive" solutions (non-optimized), one recursive and the other iterative. This problem cries out for recursion, and I managed to polish off straightforward recursive solution relatively quickly (a dozen lines + comments and formatting). However, I am guessing from your question that you might not be familiar with recursion, and there is an alternative iterative solution here that may be what your professor is looking for.

I will admit I struggled with this part quite a bit, and it ended up taking me almost two hours before I really had something solid. I thought about a few approaches beforehand, planning it out on paper and pencil and analyzing my own thought process very carefully. This is a crucial step in a difficult problem analysis, as others have already mentioned. I sat down to write the code, and even after coming up with a working prototype, I had to spend a non-trivial amount of time sorting out edge cases and cutting out and cleaning up parts that were ugly or unnecessary. I managed to eliminate at least half the code I had written in the first prototype on my final version, and then went looking around online. I found a page which confirmed my solution (*spoilers* here). While the solution can end up being relatively short (half a dozen lines or less with some hackery) it is by no means an easy problem and I would definitely not be discouraged that you are encountering difficulty with it.

The important question for you, regarding whether this is a field you want to continue to work in, is do you enjoy this process? It is often frustrating when you are having trouble solving a problem, but does this frustration drive you to try harder and conquer it or just make you want to throw up your hands and give up? Do you find the process of breaking a problem down into logical chunks, attacking it from different angles, researching documentation and reanalyzing every step of your thought process fascinating and all-consuming, or a time-wasting and meaningless exercise in tedium? Perhaps most importantly, do you crave and treasure above all else, after hours, days, or months of hard work, the feeling of joy when you finally submit a build to your compiler/interpreter and instead of spitting back gibberish, warnings, and errors, it returns precisely the solution you have been looking for the entire time? In my mind, it is this indisputable logical validation which drives every great programmer. It is a feeling in some ways akin to receiving a good grade from a particularly difficult literature professor on your final essay, but in others ways completely and utterly different because there is absolutely no subjectivity in the logic of the machine. I hope this helps to provide some perspective, and if you MeMail me I would be more than willing to email you the pseudocode I came up with as a learning tool.
posted by sophist at 1:14 AM on November 25, 2009 [1 favorite]

After reading my post over again, I did not mean to imply that either solution was easy, because they definitely are not. Instead, I wanted to highlight that as you gain experience in solving these types of problems, you will become familiar with various patterns and their application. Because of this, your introduction to programming is often the most difficult part, as you do not yet have the grounding to know in which direction you even need to go. As an example, many people find the basic concepts of math very difficult to learn. After you have these basics down though, and you find yourself at the end of a semester of algebra or calculus, when you encounter some new equation you can quickly take an educated guess that you need to factor it out or take the derivative as an appropriate first step. Indeed, some exposure to math is important for programming in that it trains you to tackle difficult problems in a technical manner, and to detail their solution in a step by step way, with a logical syntax that others can follow. But advanced techniques in math are very rarely applicable to most programmers, except in specific domains. Instead, I think that a literary background can prove highly beneficial to a programmer, and you should consider it a strength. The ability to structure your code in a coherent manner, knowing when you need to elaborate on a given topic and when to cut it short, being able to provide clear and concise documentation and to write the code itself in a manner that others (be they computer or human) can follow, all are crucial in writing good, maintainable code.
posted by sophist at 1:41 AM on November 25, 2009

I DID IT!!!!!!!!!!!!!!!!

Before I posted my question here, I had a flowchart done up that I was fairly proud of. It was an infinitely-looping solution, but I had made some major headway towards solving the problem and I knew it. Nevertheless, I couldn't figure out what conditions to set to get the program to exit the loop. It was a mess. So I took it to my instructor and he suggested another approach. I couldn't understand his approach, which led to some despair. But after reading all of your answers, I decided to go with my gut and tinker with my original flowchart again. And that is how I finally figured it out. In the eleventh hour.

I want to note that: my instructor's not a jerk for suggesting a new approach; he just couldn't see what my code was trying to do, nor could I see what his code was trying to do.

Here is my code. I don't care how elegant/inelegant it is. It works. And now I can go and compare it with other solutions.

Thank you, thank you, thank you for the encouragement.

I realize that this is not set up as a function proper, even though I have it returning a value at the end. My apologies for it being hard to read - I can't get the indents working in here.


$string1 = "";
$string2 = "";
$index1 = 0;
$index2 = 0;
$matches = 0;
$found = false;

echo "Please enter some text: ";
$string1 = trim(fgets(STDIN));

echo "\nWhat text would you like to search for? ";
$string2 = trim(fgets(STDIN));


//While the first string has not been checked through entirely AND $found = false, enter
//the loop

while($found == false && $index1 != strlen($string1))
{
//check if the character at the given index in string1 matches the
//character at the given index letter in string2.

if ($string1[$index1] == $string2[$index2])
{
$matches++;

if ($matches == strlen($string2))
{
$found = true;
}
else
{
$index1++;
$index2++;
}
}
else
{
if (strlen($string1) == $index1)
{
}
else
{
$index2 = 0;
$index1 = $index1 - $matches + 1;
$matches = 0;
}
}
}

return $found;
posted by kitcat at 11:23 AM on November 25, 2009

This is the life of a programmer, or maybe just a programming student. You think long and hard for a while and nothing comes up. Then you start over and suddenly things work.

A few stylistic notes:

* While the compiler likely already optimizes this behind the scenes, it can improve clarity to store strlen($string2) into a variable. The length of $string2 doesn't change so there's no need to recompute it; by giving it a clear name the programmer intent becomes more clear.
* Empty code blocks like the final if statement make code longer than needed. I believe PHP has a inequality operator !=. Invert the boolean and switch the else and if statements, then you won't even need the else.
* Strike that last bit of advice. Once I rewrote it, it becomes clear you can drop the boolean guard entirely. If you've made it to there, you already know by the while boolean that this boolean is also true.

Testing wise, have you tested how the function behaves when the string to be located isn't present? Also, a few suggested test cases:
(string1/string2)
aaaab/c
aababbabbb/abbb
posted by pwnguin at 1:50 PM on November 25, 2009