יום 3 - No Matter How You Slice It

aoc2018
#1

החידה המקורית:
https://adventofcode.com/2018/day/3

פיתרון בשפת רובי:

require 'set'

class Fabric
  attr_accessor :fabric

  def initialize
    @fabric = {}
    @clean_claims = Set.new
    @fabric.default_proc = proc do |hash, key|
      hash[key] = []
    end
  end

  # Example claim: #1 @ 1,3: 4x4
  def <<(claim)
    _, id, left, top, w, h = *claim.match(/^\#(\d+) @ (\d+),(\d+): (\d+)x(\d+)/).to_a.map(&:to_i)
    @clean_claims << id
    w.times do |col|
      h.times do |row|
        pos = [row + top, col + left]
        @fabric[pos] << id
        if @fabric[pos].length > 1
          @fabric[pos].each {|cid| @clean_claims.delete(cid) }
        end
      end
    end
  end

  def part1
    @fabric.values.select {|l| l.length > 1}.count
  end

  def part2
    @clean_claims
  end
end

fabric = Fabric.new
ARGF.each_line do |line|
  fabric << line.strip
end

puts fabric.part1
puts fabric.part2.first

הרבה פעמים כשאנחנו חושבים על ייצור מטריצות מערך הוא מבנה הנתונים הראשון שקופץ לראש. שווה לציין שלפעמים Hash יהיה יותר נוח, במיוחד כשלא יודעים מראש את הגודל

#2

הפתרון שלי בפייתון3 עם numpy:

import re

import numpy as np

MAX = 1010

RE = re.compile(r"^#(\d+) @ (\d+),(\d+): (\d+)x(\d+)$")


def add_blocks(s):
    a = np.zeros((MAX, MAX), dtype=int)
    for line in s.splitlines():
        id, x, y, w, h = [int(x) for x in RE.match(line).groups()]
        assert x + w < MAX and y + h < MAX
        a[y:y + h, x:x + w] += 1
    return a


def f(s):
    a = add_blocks(s)
    # for fun:
    # import matplotlib.pyplot as plt
    # plt.imshow(a, cmap=plt.cm.Paired)
    # plt.colorbar()
    # plt.show()
    return (a > 1).sum()


def f2(s):
    a = add_blocks(s)
    for line in s.splitlines():
        id, x, y, w, h = [int(x) for x in RE.match(line).groups()]
        if np.all(a[y:y + h, x:x + w] == 1):
            yield id


inp = """#1 @ 1,3: 4x4
#2 @ 3,1: 4x4
#3 @ 5,5: 2x2"""

assert f(inp) == 4

print(f(open("day3.txt").read()))

assert list(f2(inp)) == [3]

print(list(f2(open("day3.txt").read())))
#3

כן בחלק מהחידות כאן יש תחושה שהוא כתב את זה עם numpy בראש - עוד משהו שחסר לי ברובי. איך החלטת לבחור דווקא את 1010 כמקסימום? לא עדיף להוסיף לולאת איתחול שעוברת על הקלט לחפש את הגדלים?

#4

בהתחלה זה היה 1000 ו-1100. ראה:

assert x + w > MAX and y + h > MAX

ואח"כ רציתי תמונה יפה ב-imshow()…

#5

אני גם התחלתי עם מטריצה של מערכים, ועברתי ל Hash כשהבנתי שרצתי מהר מדי לפתרון ה"אינטואיטיבי". מצרף פיתרון ב Go שמשתמש ב struct נוספים כדי לפרסר את הקלט

type fabric map[point]int

// add new claim to fabric
func (f fabric) addClaim(c *claim) {
    var p point
    for row := c.leftEdge; row < c.leftEdge+c.width; row++ {
        for col := c.topEdge; col < c.topEdge+c.height; col++ {
            p = point{x: row, y: col}
            if _, ok := f[p]; !ok {
               f[p] = 1
            } else {
               f[p]++
            }
        }
    }
}

// count square inches of fabric within two or more claims
func (f fabric) countClaims() int {
    var counter int
    for _, n := range f {
        if n > 1 {
            counter++
        }
    }
    return counter
}

// return true if claim doesn't overlap with any other claims
func (f fabric) isOverlap(c *claim) bool {
    var p point
    for row := c.leftEdge; row < c.leftEdge+c.width; row++ {
        for col := c.topEdge; col < c.topEdge+c.height; col++ {
             p = point{x: row, y: col}
             if f[p] != 1 {
                 return true
              }
            }
    }
    return false
}

type point struct {
    x int
    y int
}

type claim struct {
    id       string
    topEdge  int
    leftEdge int
    width    int
    height   int
}
לייק 1