Another week, another challenge!

This time, assume you're given a grid where each . represents an empty space and each # represents a "wall". We'll call any contiguous space of .s a "region". You can also think of a grid with no walls the "base" region. The walls may subdivide the base region into any number of isolated sub-regions of any shape or size.

Write a program that will, given a grid description, compute the total number of isolated regions.

For example, the following grid has 5 isolated regions:

....#....#
....#.###.
....#.#.#.
#...#..#..
.#..#...#.

Anybody here have a good setup for batch-downloading articles/news from several sites you specify, similar to youtube-dl but for general websites? I'm sure it could be scripted with not too much effort but I'm interested what polished solutions there are.

The idea would be so people with rare internet access could go to a hotspot weekly or something and sync that week's worth of content.

It looks like it's been over a week and a half since our last coding challenge, so let's get one going. This challenge is a relatively simple one, but it's complex enough that you can take a variety of different approaches to it.

As the title suggests, write a program that accepts an arbitrary number of arrays, in whatever form or manner you see fit (if you want to e.g. parse a potentially massive CSV file, then go nuts!), and returns a single array containing all of the elements of the other arrays in sorted order. That's it!

Bonus points for creative, efficient, or generalized solutions!

Let's do something a little more challenging this time.

Given an MxN grid of arbitrary size, and given a random starting place on that grid and a list of points to visit, find the shortest path such that you visit all of them. Path lengths will be computed using taxicab distances rather than strict coordinate distance calculations.

There are no restrictions on expected input this time. Output should be the total distance traveled between points.

Example

Assume that we use the character # to denote a spot on the grid, the character @ to denote your starting point, and the character * to denote a place on the grid that you're required to visit. One such grid may look something like this:

######
######
**####
#*####
#*#*##
#@####
######

In this case, let's say that the bottom-left point on the grid is point (0, 0) and we're starting on point (1, 1). One valid solution would be to move to point (3, 2), then (1, 2), then (1, 3), then (1, 4), and finally (0, 4). The shortest path available is thus 8. Note that it's not enough just to visit the next nearest point on the grid!

Preface

One of the most common questions I see from prospective programmers and computer scientists is "where should I start?". My answer to that is a pretty consistent one: learn how to solve problems effectively. But that's vague and not really all that helpful, so I figured that I should actually tackle this in a little more depth by touching on something more specific.

Specifically, I want to touch on the subject of how to think about complex problems.

The Rationale Behind Learning

Before we can better understand how to effectively solve problems, it's important to consider how it is that we learn. With any subject, the standard approach is to begin with the bare basics. For programming, that's writing a Hello, World! program in the new language you're working with. For foreign languages, you learn basic common words and sentence structure. For math, you learn your basic arithmetic operations like addition and multiplication.

From there, we add on more additional complexity and string together everything we've learned. For a foreign language, this looks like learning about new words, stringing them together in your own sentences, then learning about verb tenses and throwing them into the mix as well. With math, you take your normal number crunching and suddenly throw the concept of order of operations into the mix, then variables and how to solve for them.

As a general rule, we first get comfortable with solving a simple problem and gradually build up toward solving increasingly more difficult ones.

The Missing Piece

Odds are that we've all sat in a math class at one point, and when the teacher asked a student how to solve a problem, they received an immediate "I don't know". You may or may not have been that kid yourself. I have no intention of shaming the kids who struggled (or those who still struggle) with math. Rather, I want to point to what I believe is the fundamental cause of that mental barrier that has frustrated students for generations.

Learning is not simply a matter of adding more complexity to problems. A key part of learning, and one that I don't recall ever having emphasized during my grade school studies, is your ability to break problems down into the steps that you know how to complete and combine the different, simpler skills you've already learned to arrive at a solution. Instead, you were expected to solve many of those complex problems and learn through practice, or through pure rote memorization.

What determined whether or not you could solve those problems was then a question of whether or not you could intuit or memorize how to solve those specific problems, and brand new problems that still made use of the same skill sets but had completely different forms would throw a wrench in that. Those who could solve any of those problems--those who, I would argue, were often mistakenly referred to as "geniuses" or "talented"--were really just those who knew how to break a problem down into simpler pieces.

This isn't a failing on the students, but on the way they've been taught to think about problems.

Reducing Problems

What does it mean to "break down" a problem, though? The few times I recall a teacher ever touching on the subject, "break down the problem" and "use the skills you've already learned" were the kinds of pieces of advice passed around, completely vague and devoid of meaning for anyone who didn't already understand. How can we better grasp this important step?

There's a term in complexity theory known as "reduction". The general idea is that if you have problems A and B, where you already know how to solve B, then if you can transform problem A so that it looks like problem B, then you can use your solution for B to solve at least part of A.

In other words, finding the solution to a more complex problem is just a matter of finding a way to make it look like a problem you already know how to solve.

The advice to "break down" a problem really means to perform this process of "reduction", of transforming your more complicated problem A into your simpler, known problem B.

In Practice

We're still discussing a vague concept, but now that we have more specific language to work with, we can more easily see how it works in practice (a reduction of its own!).

Let's consider a conceptually simple problem: grabbing the k^th largest (or smallest) item from a list. How do we solve this problem? Probably the most obvious and straightforward answer is to sort the list then grab the k^th item, right?

Notice that we gave two high-level descriptions of the steps we need to solve this problem: sorting, then grabbing the appropriate item. We can therefore then state that the problem of "grab the k^th largest/smallest item from a list" can be reduced to the two problems "sort a list" and "grab the k^th item from a list".

Now, let's say we're given the problem "take this list of competitor times from the race and tell me what the top 10 race times were". What do we know about this problem? We know that we're being given a list, and we know that we need the 10 smallest items from that list. We also know that "10 smallest items" is just shorthand for "the 1st smallest item, the 2nd smallest item, ..., and the 10th smallest item". We can therefore reduce this problem to the previous one we solved by transforming it into "grab the k^th smallest item from a list" and "repeat for values 1-10 for k".

Practical Advice

In the end, my explanation may not have helped much at all in actually grasping the concept of reduction. My intent isn't necessarily to help you understand it immediately, but to provide you a framework for a way of thinking. Even if you do grasp the general concept, you may even wonder how you're supposed to recognize these kinds of reductions out in the wild in non-academic environments. The answer, perhaps annoying, is practice. Much like an appraiser can only become good at discerning details through experience, a programmer or computer scientist can only recognize these patterns through repeated exposure.

In general, if I had to narrow it down to a small list of tips for improving your problem solving skills, this would be it:

• Work on grasping the concept of reduction itself.
• Expose yourself to lots of new problems.
• Don't shy away from difficult problems. Reduce them as much as you can and solve the pieces you're able to. Try to research the pieces you're struggling with. Return to the problem later when you have more experience if you have to, but take a crack at it first.
• Don't accept "I don't know" as an answer in itself. Ask yourself why you don't how to solve a problem. Narrow down which pieces you're able to solve and which pieces you're not.
• Just solve problems. Any problems. Easy ones, hard ones, and anything in between. Solving problems is a skill, and practicing it will make you better at solving problems in general, and better at recognizing the simpler problems inside of more complicated ones.
• Don't just come up with a solution to a problem. Ensure that you understand how each piece of it works and why it works. Copy-pasting from StackOverflow can be a valid tool at your disposal, but doing so mindlessly isn't nearly as valuable as reviewing the solution, being able to determine whether or not it works before ever executing the code, and being able to discard anything unnecessary from it.

Final Thoughts

I'm not an authoritative voice on this subject. I'm not an educator. More than anything, I'm a life-long student and an enthusiast. There's seldom a day when I don't have to research something new in order to solve a problem I'm not familiar with, or remind myself the syntax for a function I've used several times in the past. I don't know anything about teaching others, but I do know plenty about learning, and if there's anything that has stood out to me over the years, it's the fact that I find it easier to learn about something or to solve a problem if I can transform the concept into something that's easier for me to grasp.

Moreover, I'm human and thus prone to mistakes. Call me out on them if you notice them. I'll take any of my mistakes as learning opportunities :)

Another programming mini-challenge for you. It's been a month since the first one and that seemed to be rather successful. (I appreciate that there are other challenges on here but trying to sync with them seems tricky!)

A reminder:
I'm certain that many of you might find these pretty straight forward, but I still think there's merit in sharing different approaches to simple problems, including weird-and-wonderful ones.

KnightBot

Info

You will be writing a small part of a Chess program, specifically focusing on the Knight, on an 8 x 8 board.

Input

The top-left square of the board will have index 0, and the bottom-right square will have index 63.

• The first input is the starting square of the knight.
• The second input is the requested finishing square of the knight.
• The third input is the number of maximum moves allowed.

Output

The expected outcome is either True or False, determined by whether or not the Knight can reach the requested finishing square within the number of allowed moves when stating on the starting square.

e.g. The expected output for the input 16, 21, 4 is True since the Knight can move 16->33->27->21, which is 3 moves.

Extensions

Some additional ideas for extending this challenge...

1. Instead of an 8x8, what if the board was nxn?
2. Instead of "within x moves", what if it was "with exactly x moves?"
3. Instead of a traditional Knight's move (2 long, 1 short), what if it was n long and m short?
4. What if the board was infinite?
5. What if the board looped back around when crossing the edges? (e.g. the square to the right of 7 is 0)

Those that have pursued a career that deals with any type of computer science, what advice would you give to students before they get a job in it? What do you do on a daily basis? What would you have wanted to know before you started?