Project Euler / programming problems

General Chat
530

Merry Christmas everyone! I finally found some time this evening to finish 10p2 so I can go back and look at your hidden comments, and if you think you have an ugly solution, you should see mine!

I stubbornly stuck with my beloved single-pass algorithm, which works kind of like this:
  1. You identify groups as they appear
  2. If you later find that two groups are connected, fix up the data and keep going

Step 2 was pretty easy in part 1 - basically just add the lengths of the pipes.

But for part 2, I was using that same integral area formula that @antonTobi mentioned. You notice how he said this so casually?

Building up these groups piece by piece, I never got to know if I was walking them in the wrong direction, or which side was inside and outside. And it’s not just a sign flip because of the width of the pipe. So I had to keep track of two types of areas for each group in some giant arrays. And also some guess about whether I was “inside” or “outside” at each point.

So then part 2 becomes a mess of logic about how the “inner” and “outer” areas add together depending on whether I think I’m inside or outside each group. What a mess. I wasn’t even sure it was possible, but I forced my way through few example cases and eventually the thing worked.

The core mess:

# get rid of left_group and add its area to up_group
# (easier said than done)

if not up_inside[left_group] and up_inside[up_group]:
    new_ia = outer_area[left_group] + inner_area[up_group]
    new_oa = inner_area[left_group] + outer_area[up_group]
    down_inside[up_group] = not down_inside[left_group]
elif up_inside[left_group] and not up_inside[up_group]:
    new_ia = inner_area[left_group] + outer_area[up_group]
    new_oa = outer_area[left_group] + inner_area[up_group]
    up_inside[up_group] = True
    down_inside[up_group] = down_inside[left_group]
elif not up_inside[left_group] and not up_inside[up_group]:
    new_ia = inner_area[left_group] + inner_area[up_group]
    new_oa = outer_area[left_group] + outer_area[up_group]
    down_inside[up_group] = down_inside[left_group]
else:
    # inside both can't happen for a closed group, I think
    pass

inner_area[up_group] = new_ia
outer_area[up_group] = new_oa

It’s so asymmetric and amazing that it works.

…
Anyway, I may be behind, but I’ve got this cool menu system for running my programs:

4 Likes