Rules: no spoilers.

The other rules are made up as we go along.

Share code by link to a forge, home page, pastebin (Eric Wastl has one here) or code section in a comment.

  • swlabr@awful.systemsEnglish
    4·
    1 year ago
    a,b

    a: Just copied what I did for 10 b. and applied it to work here. Had to fiddle with it to make it work, but it worked. I implemented a line-crossing counting algorithm. If you slice up the area into rows, you can tell if you are inside the area if you cross an odd number of lines that vertically cross that row.

    b. Pretty much just changed the input parsing and ran the same algorithm. Thought that it might be too slow, but I put in some stopwatch ticks and found out that it should take about 5 minutes to run my a) algorithm to get the answer.

    The actual time elapsed was 5m50s.

    I miiiiight try make a faster version but my head is too fucked up to care right now, hence me letting the slow algorithm run.

    • swlabr@awful.systemsEnglish
      4·
      1 year ago

      Update on 18.

      It's not cheating if it's something you learned and forgot from a university course

      So, I have made my code a million times faster. My original algorithm counted every square of area individually, plus a bunch of other inefficient things.

      My new algorithm now uses some swanky computational geometry to calculate the enclosed area. It took a bit of scribbling on a paper pad to get this right. Some notes:

      1. If you naively use the coordinates you land on as the points of a polygon and then calculate the area of that polygon, you will slightly underestimate the enclosed area.
      2. The error comes from the contribution of the area of the perimeter. Drawing out the sample case and observing how it contributes, it basically contributes 1/2 m^3 for every straight portion of the perimeter, and 1/4 or 3/4 for a corner, depending on if that corner is a right or left turn. It should instead contribute 1 for each perimeter tile, so you need to calculate this difference.
      3. You can use the cross product to determine if a set of 3 points forms a straight line, a left turn, or a right turn.

      So, here’s what I did. I looked at some old lecture notes I had on programming competition computation geometry implementation details. I copied and pasted some code that implemented a counter-clockwise check and one that calculated the area of a simple polygon. That’s pretty much all I needed.

      Now my code runs in a few milliseconds.

      There is almost definitely a more elegant way to do what I did for this iteration but I’m happy to leave that to someone else to figure out (or copy paste from reddit or something).

      • zogwarg@awful.systemsEnglish
        3·
        1 year ago
        18

        The beauty is you don’t need to keep track of the corners at all: ultimately the area contributed by the perimeter is ( 1/2 * perimeter ) + 1. The short justification is that is if was just ( 1/2 * perimeter ), for every inside corners you overcount by 1/4 and for every outside corner you undercount. And there is exactly 4 more outside corners that inside ones, always. You can justify that by having an arrow follow the eddges, utlmately the arrow must make 1 full turn, each outside corner adds 1/4 turn. each inside corner removes 1/4 turn.

        • swlabr@awful.systemsEnglish
          2·
          1 year ago

          I knew there was a better way! Thanks!

          perhaps

          A more elegant proof might show that starting with a rectangle, you have 4 corners contributing 1/4. You can push out parts of the edges of the rectangle to generate more corners, but they will always be in pairs of opposite types.