יום 2 - Inventory Management System

#1

הי,

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

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

class String
  def count
    Hash.new(0).tap { |h| self.each_char { |word| h[word] += 1 } }
  end

  def icount
    counts = self.count
    each_char.group_by {|c| counts[c]}
  end

  def common(other)
    return 0 if other == self
    return length if other.length != self.length
    self.each_char.each_with_index.map {|char, index| char == other[index] ? char : '' }.join
  end
end

## Part 1
twos = 0
threes = 0
ARGF.each_line.map(&:strip).map(&:icount).each do |counts|
  twos += 1 if counts.key?(2)
  threes += 1 if counts.key?(3)
end

puts twos, threes, twos * threes


## Part 2
puts ARGF
  .each_line
  .map(&:strip)
  .to_a
  .combination(2)
  .map {|pair| pair[0].common(pair[1])}
  .select {|word| word.length == 25}
  .first
#2

המממ… מאתגר אותך: אני מצרף שלושה קבצים - האם תוכל לשפר את הקוד (באופן אלגוריתמי) כך שזמן העבודה על הקובץ יהיה סביר?
(אני יכול לחשוב על כמה פתרונות, חלקם טריויאליים)

קובץ ראשון:
day2_2000.txt

קובץ שני:
day2_20000.txt

וקובץ שלישי (גדול מדי לאתר):
https://gist.github.com/nonZero/e9cc630bac267d9055f75838c7456a7b/raw/f165fefc546b38be64d4423ecd149360367fed44/day2_200000.txt

#3

באמת מעניין - כיוון ראשון יהיה למחוק את כל האותיות האפשריות מכל מילה ואז לחפש מילים שכבר ראינו או ברובי:

require 'set'

class String
  def withoutletter
    res = Set.new
    self.length.times do |idx|
      value = self.dup
      value[idx] = ''
      res << value
    end
    res
  end
end

## Part 2
puts ARGF
  .each_line
  .lazy
  .map(&:strip)
  .map(&:withoutletter)
  .inject(Set.new) { |seen, val|
    code = seen & val
    break code.first if code.length > 0
    seen | val
  }

וזה באמת משפר את הזמן על הקובץ הקטן מ 20 שניות ל-5, אבל הקובץ הגדול עדיין נראה לי מחוץ לתחום. איזה עוד רעיונות היו לך?

#4

בררר… כבר מאוחר לי בלילה עכשיו להבין רובי עד הסוף, אבל נראה לי שיש לך באג כי הקוד שלי (בפייתון) בכיוון הזה סגר לי את הפינה בקלות עם הקבצים האלה.
זה אמור לעבוד בגדול ביעילות של n.
את הראשון הקוד שלי מסיים ב-3 מאיות השני ב-38 מאיות ואת הגדול ב-4.3 שניות - אז זה באמת דומה ל-n.

אני אתן רמז לפתרון אחר: יש פתרון פשוט (מבחינת כתיבת הקוד) עם יעילות מומצעת של נגיד n*log n ומאוד יעילה מבחינת דרישות זכרון.

#5

נמצאה האבדה- פעולת Union בין שתי קבוצות יוצרת קבוצה חדשה וזו פעולה כבדה כשיש המון איברים. עדיף למזג הכל לאוביקט אחד עם merge. זה הקוד המתוקן:

## Part 2
puts ARGF
  .each_line
  .lazy
  .map(&:strip)
  .map(&:withoutletter)
  .inject(Set.new) { |seen, val|
    code = seen & val
    break code.first if code.length > 0
    seen.merge(val)
  }

עדיין לגדול לקח 12 שניות אז בטח יש עוד כמה שטויות שפספסתי

#6

גם ב Go אפשר לממש בפשטות על ידי שימוש ב map ששומר את כל הפרמוטציות של מחרוזת כאשר מורידים אות אחת. בהינתן שאורך מחרוזת הוא M אזי היעילות תהיה M*N (רצים על כל המחרוזות ביעילות N ומכניסים כל מחרוזת ל map ביעילות של M). גם על הקובץ הגדול זמן הריצה מהיר יחסית.

m := make(map[string]string)
for _, boxID := range boxIDs {
    for i := 0; i < len(boxID); i++ {
        p := boxID[:i] + boxID[i+1:]
	if otherBox, ok := m[p]; ok && boxID != otherBox {
	    return p
        }
	m[p] = boxID
     }
}
לייק 1
#7

פתרון לחלק א בפייתון

'''This program find if a letter exist 2 or 3 time in the text'''
import collections

path = r'C:\Users\Champion\PycharmProjects\AdventOfCode_2018\Day_2\checksum.txt'

count_2 = 0
count_3 = 0
res_2 = 0
res_3 = 0

def count(word):
    c = collections.Counter(word)
    #print c
    return c

def checksum(fisrt,second):
    return fisrt * second

with open(path, "r") as f_r:
    s = [count(i) for i in f_r]

for i in s:
    for j in i.keys():
        if i[j] == 3:
            count_3 += 1
        if i[j] == 2:
            count_2 += 1
    if count_3 >= 1:
        count_3 = 1
        res_3 += 1

    if count_2 >= 1:
        count_2 = 1
        res_2 += 1
    count_2 = 0
    count_3 = 0

print checksum(res_2,res_3)
#8

הי,

כן אני רואה למה לא היית מרוצה מהפיתרון

שני דברים שלדעתי יעשו כאן מהפך:

  1. שמות משתנים… i, j, s, c, ואפילו count ו res הם לא שמות טובים כשרוצים לכתוב קוד שאפשר יהיה גם לקרוא אותו.

  2. לפייתון יש פונקציה בשם any שממש טובה בלבדוק אם ״מישהו מהמילון מופיע פעמיים״. הקוד הבא למשל יגיד לך שבמילה hello יש אות שמופיעה פעמיים:

>>> letter_counts = collections.Counter('hello')
>>> any(v == 2 for k, v in letter_counts.items())
True

נסה להשתמש בשני הטריקים האלה ותראה אם אתה יותר מרוצה מהתוצאה

לייק 1
#9

השתמשתי ב any
נראה יותר טוב
אשמח אם יש לך עוד הערות

''' This program find if a letter exist 2 or 3 time in the text and calculate the checksum'''
import collections

path = r'C:\Python\Advent_of_code\2018\day_2\checksum.txt'

count_2 = 0
count_3 = 0


def count(word):
    c = collections.Counter(word)
    return c

def checksum(fisrt,second):
    return fisrt * second

with open(path, "r") as f_r:
    all_word_list = [count(word) for word in f_r]

for line in all_word_list:
    if any(v == 2 for k,v in line.items()):
        count_2 += 1

    if any(v == 3 for k, v in line.items()):
        count_3 += 1


print checksum(count_2,count_3)