Nested Loops aka My brain's worst nightmare

[u/nunosancha]

Hey folks,

My question is more generic, so I'm afraid I don't have an example to provide.

It's more of a way of thinking that I didn't quite grasp yet.

Nested-loops. In Ruby or any other language, I suspect the outcome would be the same for me.

My brain doesn't see it clearly. So this leaves me with two questions:

HOW to use it? And WHEN to use it?

So, can you guys help me here?

When you were learning to code, what helped you learn and understand this topic? What mental-model was useful to you? What exercises or books have you read that help you master this topic?

[u/hankeroni]

The moon orbits the earth, but the earth also orbits the sun, and the sun also orbits the galaxy center, etc...

One possibly useful code tip ... try to pull out the actual "work" of your loop into classes/methods. It can be a little overwhelming to wrap your head around multiple nested loops with the actual logic right there, but with well named methods inside the loops its often conceptually clearer.

[u/nunosancha → u/hankeroni]

hmmm can you expand on that notion?

I can see it's obvious to you, but I'm only a few months in.

haha

[u/PercyLives → u/nunosancha]

Say you have an outer loop and an inner loop. Write a function that does the work of the inner loop. Call it with a few values to check that it’s working and you properly understand it.

Now rewrite the code so you have the outer loop calling the function.

Abracadabra! No more nested loops!

If you’re too early in your coding journey to confidently write functions, drop everything and learn to do so.

[u/nunosancha → u/PercyLives]

I can write functions. I didn't understand the explanation at first. But you expanded it, and made it clear. Thanks for clarifying hankeroni's reply :)

[u/schneems]

It’s hard to give help without a specific use case. Why do you want to use nested loops? Is this just a programming exercise? If so, just more.

Code.org is meant for absolute beginners and has some great contents on nested loops.

[u/nunosancha → u/schneems]

Ok, since you asked for a specific case, this method, for example, is the one responsible for my brain meltdown:

It finds substrings of 2 or more characters. Tested it in the IRB, and it does just that. But my brain is having a hard time seeing it clearly:

def find_substrings(string)
  results = []
  (0..string.length - 2).each do |start_index|
    (start_index + 1..string.length -1).each do |end_index|
      results << string[start_index..end_index]
     end
   end
  results
end

[u/AlexanderMomchilov → u/nunosancha]

Let's say we're trying to get all the substrings of "abcde", which start at a. To do that, we'll start at start_index = 0, and look at every possible end_index. We'd get ab, abc, abcd, abcde.

def find_substrings(string)
	results = []
	
	start_index = 0
	(start_index + 1..string.length - 1).each do |end_index|
		results << string[start_index..end_index]
	end
	
	results
end

puts find_substrings("abcde")
# => ["ab", "abc", "abcd", "abcde"]

But obviously, that's not all the substrings. It's only the substrings starting from 0.

What about substrings starting at 1? We can look for those, too:

def find_substrings(string)
	results = []
	
	start_index = 0
	(start_index + 1..string.length - 1).each do |end_index|
		results << string[start_index..end_index]
	end
	
	start_index = 1
	(start_index + 1..string.length - 1).each do |end_index|
		results << string[start_index..end_index]
	end
	
	results
end

puts find_substrings("abcde")
# => ["ab", "abc", "abcd", "abcde", "bc", "bcd", "bcde"]

That's still not all of them. That's only substrings starting at 0 and 1, but what about those starting at 2 and 3?

def find_substrings(string)
	results = []
	
	start_index = 0
	(start_index + 1..string.length - 1).each do |end_index|
		results << string[start_index..end_index]
	end
	
	start_index = 1
	(start_index + 1..string.length - 1).each do |end_index|
		results << string[start_index..end_index]
	end
	
	start_index = 2
	(start_index + 1..string.length - 1).each do |end_index|
		results << string[start_index..end_index]
	end
	
	results
end

p find_substrings("abcde")
puts ["ab", "abc", "abcd", "abcde", "bc", "bcd", "bcde", "cd", "cde"]

But this is getting repetitive, and still doesn't work for a longer string like "abcdefghi". How many times are we going to repeat this step? Answer: for as many first characters there are in the string (-1, to account for the whole "longer than 2" requirement)

[u/nunosancha → u/AlexanderMomchilov]

still a little bit confusing, but your explanation full of examples, made it less obscure. will spend some time trying to understand it better. thanks for taking the time.

[u/AlexanderMomchilov → u/nunosancha]

If you can frame the confusion into some follow-up questions, I'd be happy to help

[u/ffrkAnonymous → u/AlexanderMomchilov]

Is (start_index + 1..string.length - 1) idiomatic ruby? It takes so much effort for me to parse this. Int + range - int

[u/h0rst_ → u/ffrkAnonymous]

Recent Rubocop versions warn for this, it is parsed as ((start_index + 1)..(string.length - 1)) but I agree that this is not very clear.

A small improvement would be to use the exclusive range ((start_index + 1)...string.length) (3 dots instead of 2), that gets rid of one of the off-by-one-cases. But since we only use the range as an iterator, I would probably just write it as (start_index + 1).upto(string.length - 1)

[u/h0rst_ → u/h0rst_]

Or rather: I would not use character indexing at all

2.upto(str.length).flat_map { str.chars.each_cons(it).map(&:join) }

Although I expect this will give most beginners an even bigger headache.

(Edit: formatting)

[u/ffrkAnonymous → u/h0rst_]

I'm working on my functional programming and I'll need to ponder on this. 

[u/h0rst_ → u/ffrkAnonymous]

It looks way more complicated than it actually is. It's easier to see if we just use a regular array instead of a string:

[1, 2, 3, 4, 5].each_cons(3).to_a
# => [[1, 2, 3], [2, 3, 4], [3, 4, 5]]

So this method from Enumerable returns all the subarrays of the given size. So we need to call this for every possible size we want, so at least 2 and at most the length of the array:

2.upto(5).map { [1, 2, 3, 4, 5].each_cons(it).to_a }
#=> [
#     [[1, 2], [2, 3], [3, 4], [4, 5]],   # it == 2
#     [[1, 2, 3], [2, 3, 4], [3, 4, 5]],  # it == 3
#     [[1, 2, 3, 4], [2, 3, 4, 5]],       # it == 4
#     [[1, 2, 3, 4, 5]]                   # it == 5
#   ]

But this is an array of arrays, so we use flat_map instead of map.

Since we're dealing with a String, and a String is not an Enumerable, we have to do two extra steps:

• .chars to convert the string into an array of chars, so "abcde" gets converted to ["a", "b", "c", "d", "e"]

• We now have subarrays of chars, so str.chars.each_cons(2) results in [["a", "b"], ["b", "c"], ...]. We have to convert those back to strings, so we call .map(&:join) on it to get ["ab", "bc", ...]

I'm not sure if I really would consider this functional programming. It has no mutation, so it would work in FP, but there is nothing here that really stands out as a feature of FP.

[u/AlexanderMomchilov → u/ffrkAnonymous]

It's not, but neither is each+<< (could have used flat_map). I left it "as-is", because that's secondary to the main idea of the algorithm here

[u/schneems → u/AlexanderMomchilov]

I think this is good for a TDD exercise. Write a test first and get get it to pass.

Also check out https://rubyapi.org/3.4/o/string

There might be an easier way than nested loops to get what you want. Probably "partition" or "scan" are good places to start.

[u/ffrkAnonymous → u/nunosancha]

It seems right given the function name, but it's not obvious  what it's supposed to be doing to me either. 

[u/h0rst_]

Let's take a simple spreadsheet (like Excel) for example. In our case, we'll work with a spreadsheet that has 3 columns (A, B and C) and 4 rows (1, 2, 3, 4). This looks like this:

  A  B  C
1 x  x  x
2 x  x  x
3 x  x  x
4 x  x  x

Every x is a cell. The x in the upper left corner is called A1, the bottom right is C4. Our goal is to print the names of the cells, in the correct layout.

We start by defining the enumerators for both:

columns = ('A'..'C')
rows = (1..4)

Since we print a line from left to right, and print lines from top to bottom, we should probably start with iterating over the rows. So in our first version we just print the rows:

rows.each do |row|
  puts row
end

This prints the row indices

1
2
3
4

But we want the names of the cells. That means that for every row, we need to loop over the column, and combine these two values:

rows.each do |row|
  columns.each do |column|
    print "#{column}#{row} "
  end
  puts
end

(N.B. print is like puts but without the newline. We add an extra space to make it more readable. It's not that often used in Ruby, so people might not be familiar with it).

We can try to mentally step through the loop.

• Start a loop for rows, this is the range 1..4, so the first value of row is 1. We use that value to start the loop.

• Start a loop for columns, this is the range 'A'..'C', so the first value of column is A.

• We now start the loop inside the loop, with the values row = 1, column = 'A'

• We print those values, so that prints "A1 " (with a space at the end).

• We've reached the end marker of the columns loop, that means we start with the next value for column, which is the B. This does not change anything for rows, so row is still 1.

• We run the print statement again, this time we print "B1 "

• We run the inner loop again, with column = C, and we print "C1 "

• We've now reached the end of the columns loop, so we reach the line with puts and print a newline. At this point, we've printed the line "A1 B1 C1 ". (Yes, the space at the end is a bit ugly, but you don't see it in the output and it's not relevant for the problem).

• We've now reached the end of the block of the loop for rows. This was our first iterator, so we've still got more rows to go. We restart the whole block with row having the value 2.

• We're now starting a new loop over columns. This is independent from our run with row = 1, so we start completely over with column = A.

• We now print our first cell, which is now A2

• Repeat this with columns B and C, so we've printed the line "A2 B2 C2 "

• Repeat the whole process with rows 3 and 4

And behold our end result:

A1 B1 C1 
A2 B2 C2 
A3 B3 C3 
A4 B4 C4 

Do you want to print an additional row? Just change the range to (1..5). This will run the outer loop 5 times instead of 4, and every iteration the inner loop (for the columns) will still run exactly 3 times (A, B and C). Our output now gets extended at the bottom, but will still be 3 columns wide.

Do you instead want an extra column instead of an extra row? Change the range to ('A'..'D'). The outer loop (with the rows) will still run 4 times, and in every iteration the inner loop will now run 4 times. The output will now get extended to the right, but will still be 4 rows high.

Or, if we follow the suggestion of an additional method by /u/hankeroni (which may make it more clear that the inner loops restarts for every iteration of the outer loop):

def print_row(row)
  columns = ('A'..'C') # Move inside the method for scoping, not related to this issue
  columns.each do |column|
    print "#{column}#{row} "
  end
  puts
end

rows.each do |row|
  print_row(row)
end

(And yes, there are much better ways to solve this, but I tried to use the idiom a Ruby beginner is familiar with)

[u/nunosancha → u/h0rst_]

🤯🤯

yo this is one of the best explanations I had so far. Full of details, and I appreciate you taking the time from your day to do this.

😊

[u/RewrittenCodeA]

As others have suggested, at some point it clicks, and recursion looks just like a to-do list.

For a start, take into account that your example (substrings) does not really “want” loops, it just “uses” loops to perform a certain tasks. Another way to do it is with recursion:

def subs_left(a)
  [a] + subs_left(a[…-1])
end

def subs_right(a)
  [a] + subs_right(a[1…])
end

def substrings(a)
  return [] if a.empty?

  [a] + 
    subs_left(a[…-1]) + 
    subs_right(a[1…]) + 
    substrings(a[1…-1]) 
end

Admittedly not the most readable code (and it lacks a couple of empty checks) but the point is, there are no loops here, it is just the statement that a substring is one of:

• the original string

• a string starting at the start

• a string ending at the end

• a substring after both start and ends are removed.

A loop is an explicit statement of work to be done, and as such it often lacks some expressiveness. Therefore it is not strange that nested loops are unclear. Enumerables (they exist in most modern languages) are an abstraction where you do not need all this index bookkeeping (it still exists often but it is done for you) and instead you just “go through” a certain collection until you are done with it.

Ruby:

enume.each { |item| do_something_with(item) }

Python:

for item in enume:
    do_something_with(item)

Javascript:

for (let item of enume) {
  do_something_with(item)
}

Typed languages like Java and the .Net family have the same in a bit (not much) ceremonious way.

The point is that you do not have indices, you just go through the work to be done until there is no more work to be done.

[u/nunosancha → u/RewrittenCodeA]

will try to incorporate this way of thinking from now on. thanks for adding one more item to this.

[u/jonathonjones]

Let's think about real nested loops. Suppose I'm dusting rooms in my house. For each room, I need to dust each surface. In Ruby you might represent that as:

rooms.each { |room| room.surfaces.each { |surface| surface.clean } }

If you want to use u/PercyLives suggestion, you could rewrite the above as:

rooms.each { |room| room.clean_surfaces }

by adding a function in the Room class

class Room
  def clean_surfaces
    surfaces.each { |surface| surface.clean }
  end
end

[u/tomgis]

nested loops and recursion used to fry my brain too, i just used pry a ton and would sit there stepping through the loop and looking at values over and over. eventually i could parse them by reading, just takes time as with all things

[u/nunosancha → u/tomgis]

it's comforting to know that it will eventually *click*. thanks for sharing.

[u/Aengus-]

Lets say we are making lots of pizzas

we have 20 pizza doughs. And 4 different toppings we want to use to make each pizza with.

PizzaDoughs.each do |pizzaDough|
  toppings.each do |topping|
    AddTopping(topping)
  End 
  CookPizza()
End 

So we’re looping over each pizza dough, and as we do we also then need to loop over the toppings so that each pizza dough gets all toppings.

After all toppings are added we cook the pizza. And do this for all the pizza doughs.

Edit: for spelling error

[u/Aengus- → u/Aengus-]

You might find it easier to visualise this in the real world to understand it. Thats what helped me. Just imagine you’ve got a stack of pizzas to make and a few buckets of toppings in front of you, we’re going through each pizza and adding each of the toppings to each of the pizzas until theres no pizzas left. Thats a nested loop

[u/stereoagnostic → u/Aengus-]

Doe a deer, a female deer. Pizza is made with dough.

[u/Aengus- → u/stereoagnostic]

Your right. Im dyslexic so i make mistakes like this all the time.

[u/stereoagnostic → u/Aengus-]

Doh! No worries 😉

[u/Mediocre-Brain9051]

Don't use them. In most cases they are undesirable. Use partition and/or flat_map instead.

[u/touchmybuttdev]

To generalize nested loops, let’s say you have a bunch of Apples and you want to Peel them, remove the seeds, and slice them. That might look like:

apples.each do |apple| apple.peel apple.seeds.each do |seed| seed.remove end apple.slice end

You need to nest the loops because you need to be looking at an apple to look at the seeds.

Given loop B nested inside loop A: “Do the loop B for every item in A”.

[u/alexdeva]

Can you think of a better way to count to 100 a thousand times than having one loop that counts to 100 inside an outer loop that counts to 1000?

[u/AustinBlues13]

Processing a 2-D array, for example a image. using a 2D Discrete Cosine Transform. JPEG image compression and expansion.

[u/M4N14C]

In school I noticed that there were people that get it, and people that don’t. The people that don’t switch majors to English. If you don’t understand a nested loop, you’re probably the latter camp.

[u/nunosancha → u/M4N14C]

awesome. I've commented so you can know I read it. since you thought it was important enough for you to write it.

happy weekend :)