המממ… מאתגר אותך: אני מצרף שלושה קבצים - האם תוכל לשפר את הקוד (באופן אלגוריתמי) כך שזמן העבודה על הקובץ יהיה סביר?
(אני יכול לחשוב על כמה פתרונות, חלקם טריויאליים)
באמת מעניין - כיוון ראשון יהיה למחוק את כל האותיות האפשריות מכל מילה ואז לחפש מילים שכבר ראינו או ברובי:
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, אבל הקובץ הגדול עדיין נראה לי מחוץ לתחום. איזה עוד רעיונות היו לך?
בררר… כבר מאוחר לי בלילה עכשיו להבין רובי עד הסוף, אבל נראה לי שיש לך באג כי הקוד שלי (בפייתון) בכיוון הזה סגר לי את הפינה בקלות עם הקבצים האלה.
זה אמור לעבוד בגדול ביעילות של n.
את הראשון הקוד שלי מסיים ב-3 מאיות השני ב-38 מאיות ואת הגדול ב-4.3 שניות - אז זה באמת דומה ל-n.
אני אתן רמז לפתרון אחר: יש פתרון פשוט (מבחינת כתיבת הקוד) עם יעילות מומצעת של נגיד n*log n ומאוד יעילה מבחינת דרישות זכרון.
גם ב 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
}
}
'''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)
השתמשתי ב 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)