אתגר aoc2017 יום רביעי

#1

הי,

@YOEL, @11115, @splintor, @Amirkr, @miryeh

אנחנו ממשיכים לחידה הרביעית שלנו באתגר. שמתם לב וודאי שהחידה הקודמת (מספר 3) היתה יותר קשה מהשתיים הראשונות. בכל מקרה הרביעית נותנת לנו הזדמנות לקחת אוויר שוב אז תרגישו חופשי להשקיע בפיתרונות קצרים ואלגנטיים.

סיסמאות חזקות

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

לדוגמא הביטוי aa bb cc dd ee הוא מאובטח כי כל מילה מופיעה בו פעם אחת
הביטוי aa bb cc dd aa לא מתאים כסיסמא מאחר ו aa מופיעה בו פעמיים
והביטוי aa bb cc dd aaa גם בסדר

המשימה שלכם לקבל קובץ עם סיסמאות כאלה ולספר כמה מהן תקינות.

לדוגמא אם הקובץ היה מכיל את שלושת ביטויי הדוגמא היה צריך להדפיס 2.

(אגב- הפיתרון הנכון הראשון לחידה הזו הוגש בזמן אמת 37 שניות לאחר שפורסמה… אז אם אתם רציניים לגבי לגשת איתי ל AoC של השנה נסו לחשוב איך אנחנו מתמודדים עם המשוגעים ששם)

#2

זה באמת די קל:

function unique(s) {
    function hasDuplicate(c) {
        const dic = {};
        return c.reduce((acc, w) => acc || w in dic || (dic[w] = false), false);
    };
    return s.split(/[\r\n]+/)
        .map(l => l.split(/\W+/))
        .reduce((acc, c) => acc + (hasDuplicate(c) ? 0 : 1), 0);
}
לייק 1
#3

והחלק השני מצריך שינוי קל - במקום לבדוק אם מילה קיימת כבר ולשמור אם לא, אנחנו בודקים ושומרים את הגרסה הממויינת של אותיות המילה:

function anagram(s) {
    const sorted = s => s.split('').sort().join('');
    function hasDuplicate(c) {
        const dic = {};
        return c.reduce((acc, w) => acc || sorted(w) in dic || (dic[sorted(w)] = false), false);
    };
    return s.split(/[\r\n]+/)
        .map(l => l.split(/\W+/))
        .reduce((acc, c) => acc + (hasDuplicate(c) ? 0 : 1), 0);
}
לייק 1
#4

יש ב JavaScript מבנה נתונים בשם Set שאני חושב שיותר יתאים פה מאשר Object

הבעיה עם Object שיש כל מיני מילים שכבר קיימות שם שאולי לא קיימות בקלט שלך, למשל נסה להפעיל:

unique('toString will convert anything to string')
#5

ועוד אגב - אני חושב הפיתרון הפעם באליקסיר יצא לי לא פחות קריא מקוד ה JavaScript (בינתיים חלק ראשון):

IO.stream(:stdio, :line)
|> Stream.map(&String.trim/1)
|> Stream.map(&String.split/1)
|> Stream.map(fn line -> MapSet.size(MapSet.new(line)) == Enum.count(line) end)
|> Stream.map(&Boolean.to_integer/1)
|> Enum.sum
|> IO.inspect
#6

מה המשמעות של ה 1/ שיש בסופם של כל מיני ביטויים? מבלבל אותי כל פעם…

#7

כן, אני יודע. הנחתי (בצדק) שזה לא יהיה בקלט שאני אקבל…
כדי לפתור את זה אפשר להשתמש ב-set ואפשר לאתחל עם אובייקט ריק באמת:

const dic = Object.create(null);
#8

ה-Boolean.to_integer שלך גרם לי לבדוק ולהזכר שב-JavaScript, אפשר להתייחס לבוליאניים כמספרים בפעולות חישוב, ואז אפשר לפשט עוד את הפתרון שלי:

function unique(s) {
    function hasDuplicate(c) {
        const dic = Object.create(null);
        return c.reduce((acc, w) => acc || w in dic || (dic[w] = false), false);
    };
    return s.split(/[\r\n]+/)
        .map(l => l.split(/\W+/))
        .reduce((acc, c) => acc + hasDuplicate(c) , 0);
}
#9

זה נקרא ה Arity של הפונקציה - כלומר כמה פרמטרים הפונקציה מצפה לקבל. בצורה כזו אליקסיר תומכת בהעמסת פונקציות (Functon Overloading), פיצ׳ר שלא קיים ב JavaScript.

לייק 1
#10

פתרון לחלק א

import collections


path = r'C:\Python\Advent_of_code\4th_day\valid_password.txt'
counted = 0
with open(path,'r') as readline:
    for line in readline:
        res = line.split()
        res = [item for item, count in collections.Counter(res).items() if count > 1]
        if res == []:
            counted += 1


print counted

אגב ינון,
לא תרגמת את חלק ב

לייק 1
#11

אוי ואבוי שכחתי לגמרי מהחלק השני ודווקא זה חלק שאני אוהב במיוחד, תודה על התזכורת

חלק 2 - עדכון למדיניות האבטחה

מחלקת אבטחת המידע החליטה לעדכן את המדיניות כדי להקשיח עוד יותר את המערכת. עכשיו כדי שסיסמא תהיה תיקנית עלינו לוודא שאף שתי מילים אינן אנאגרמה אחת של השניה (שתי מילים הן אנאגרמה אם הן מורכבות מאותן אותיות אבל בסדר שונה).

לכן לדוגמא הטקסט abcde fghij הוא סיסמא תקני אבל הטקסט abcde xyz ecdab אינו תקני כי המילה הראשונה והאחרונה מורכבות מאותן אותיות בסדר שונה.

עדכנו את התוכנית כך שתספור כמה סיסמאות תקינות לפי המדיניות החדשה

#12

גדול
אני הייתי בודק אם אורך המערך הוא 0 כי לדעתי זה יותר קריא כך

#13

חלק ב
למה הוא מבצע רק את השורה הראשונה בקובץ?



from collections import defaultdict




def load_words(path = r'C:\Python\Advent_of_code\4th_day\valid_password.txt'):

    with open(path) as readline:
        for line in readline:
            res = line.split()
            return res

def get_anagrams(source):
    d = defaultdict(list)
    for word in source:
        key = "".join(sorted(word))
        d[key].append(word)
    return d

def print_anagrams(word_source):
    count = 0
    d = get_anagrams(word_source)
    acc = 0
    for key, anagrams in d.iteritems():
        if len(anagrams) > 1:
            print(key, anagrams)
            count += 1


word_source = load_words()
print_anagrams(word_source)
#14

מה הכוונה שורה ראשונה? איפה הוספת הדפסת בדיקות? מה אתה מקבל? מה אתה מצפה לקבל?

#15

בפונקציה print_anagrams

#16

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

#17

בבקשה

''' The code find if there are anagrams in each line in the file and returns the valid lines (w\o anagram)'''


from collections import defaultdict


def load_words(path = r'C:\Python\Advent_of_code\4th_day\valid_password.txt'):
    count = 0
    count_lines = 0
    with open(path) as readline:
        for line in readline:
            count_lines += 1
            res = line.split()
            count += print_anagrams(res)

        print "There are {} lines in total".format(count_lines)
        print "{} lines are invalid".format(count)
        result = count_lines - count
        print "{} lines are valid".format(result)


def get_anagrams(source):
    d = defaultdict(list)
    for word in source:
        key = "".join(sorted(word))
        d[key].append(word)
    return d


def print_anagrams(word_source):
    count = 0
    d = get_anagrams(word_source)
    for key, anagrams in d.iteritems():
        if len(anagrams) > 1:
            count += 1
            break
    return count


load_words()
לייק 1
#18

אשמח לחוות דעתך על הקוד

#19

נראה מעולה בסוף הצלחת לגרום לו לעבוד?

#20

פתרון ליום 4, פייתון3:

def f(s):
    words = s.split()
    return len(words) == len(set(words))


assert f("aa bb cc dd ee")
assert not f("aa bb cc dd aa")
assert f("aa bb cc dd aaa")
print(sum(map(f, open("day4.txt").read().splitlines())))


def f2(s):
    words = s.split()
    return len(words) == len(set(tuple(sorted(w)) for w in words))


assert f2("abcde fghij")
assert not f2("abcde xyz ecdab")
assert f2("a ab abc abd abf abj")
assert f2("iiii oiii ooii oooi oooo")
assert not f2("oiii ioii iioi iiio")

print(sum(map(f2, open("day4.txt").read().splitlines())))