/aocg/ - Advent of Code 2018 General #6

Previous thread: adventofcode.com/
>Advent of Code is a series of small programming puzzles for a variety of skill levels. They are self-contained and are just as appropriate for an expert who wants to stay sharp as they are for a beginner who is just learning to code. Each puzzle calls upon different skills and has two parts that build on a theme.
You need to register with an account but you can appear as anonymous.

Private leaderboard join code: 368748-e33dcae3


People who are inactive for 5 days will be kicked, but other leaderboards can be made if desired.

Attached: file.png (392x260, 2K)

Other urls found in this thread:

levenshtein.net/
twitch.tv/videos/343498733##
twitter.com/NSFWRedditImage

Is it an LCS alg?

>tfw brainlet

Where my Emacs Lisp boys at?
part 1
(let* ((ids (with-temp-buffer
(insert-file-contents (expand-file-name "./day02-input"))
(split-string (buffer-string) "\n" t)))
(alphabet (cl-loop for x from 97 to 122
collect x))
(checksum-2 0)
(checksum-3 0))
(mapc (lambda (id)
(let ((has-letter-2 nil)
(has-letter-3 nil))
(mapc (lambda (letter)
(let ((count (cl-count letter id)))
(when (= count 2)
(setq has-letter-2 t))
(when (= count 3)
(setq has-letter-3 t))))
alphabet)
(when has-letter-2
(setq checksum-2 (+ checksum-2 1)))
(when has-letter-3
(setq checksum-3 (+ checksum-3 1)))))
ids)
(* checksum-2 checksum-3))

>inactive for 5 days
you should prune zerostarlets tomorrow and then go with the 5 days rule for everyone else

It was supposed to be the table from levenshtein.net/ but I copied a gif into a clipboard and fucked up the thread.

2 stars for each day should be mandatory (with a delay of 5 days, or less).

file = [s[0:len(s) - 1] for s in open('files/puzzle2.txt').readlines()]
two_count = 0
three_count = 0

for i, s in enumerate(file):
letter_table = [0 for idx in range(26)]
two_count_inc = 0
three_count_inc = 0

for c in s:
letter_table[ord(c) - ord('a')] += 1

for l in letter_table:
if l == 2:
two_count_inc = 1
if l == 3:
three_count_inc = 1

two_count += two_count_inc
three_count += three_count_inc

for ss in file[0: i]:
if sum([ord(a) ^ ord(b) >= 1 for a, b in zip(s, ss)]) == 1:
print ''.join(['' if ord(a) ^ ord(b) else a for a, b in zip(s, ss)])

print two_count * three_count

I couldn't figure out a a better way for part 2 other than brute force, I was trying to solve it with a radix tree for a while but gave up.

Whats the non brainlet strat?

Alright so I'm trying to optimize my Python solution for D2P2 and I've ran into some weird anomaly.
Currently what I do is I just generate combinations for the input and check that but this obviously generates duplicates, so I tried by simply looping twice over the input however this actually makes the runtime worse from 75ms avg to 95ms avg.
Another thing I tried was converting the combinations result to a set to get unique combinations and here's where the puzzling part starts: Python runs the solution in anywhere between 10ms and 120ms (varies highly between runs) whereas PyPy runs it in consistent 45ms (vs 16ms using naive combinations approach). What the fuck is going on.

>he didn't convert his strings to matrices as first step
never gonna make it

You don't actually need to optimize anything. I did the most obvious strategy which was just comparing every string with every string and I still measured it to run at 7ms (counting PowerShell command parsing time)

Python

part 1

def main():
two_letters = 0
three_letters = 0
data = [ID.strip() for ID in open('input', 'rt').readlines()]

for ID in data:
has_three_letters = False
has_two_letters = False
for letter in ID:
if ID.count(letter) == 3 and not has_three_letters:
three_letters += 1
has_three_letters = True
if ID.count(letter) == 2 and not has_two_letters:
two_letters += 1
has_two_letters = True

print(two_letters * three_letters)
return 0


exit(main())

MATLAB stronk.

My solution to part 2 for today, where data is a column vector with all the input strings.

box1 = 0;
box2 = 0;

for i = 1:length(data)
tmp = data ~= data(i,:);
ones = find(sum(tmp, 2) == 1);

if length(ones) == 1
box1 = data(i,:);
box2 = data(ones,:);
break
end
end

uncommon_char_index = find((box1 ~= box2) == 1);
box1(uncommon_char_index) = []

part 2

def main():
data = [ID.strip() for ID in open('input', 'rt').readlines()]

for ID1 in data:
for ID2 in data:
if ID1 != ID2:
common_letters = ""
uncommon_letters_count = len(ID1)
for i in range(len(ID1)):
if ID1[i] == ID2[i]:
uncommon_letters_count -= 1
common_letters = common_letters + ID1[i]
if uncommon_letters_count == 1:
print(common_letters)
return 0


exit(main())

I did some more testing and here's the results visualization.

Attached: file.png (1014x119, 4K)

repostan my code for feedback
#include
#include
#include
#include

int main() {
std::vector lines;

int threes = 0, twos = 0;
for (std::string line; std::getline(std::cin, line);) {
lines.push_back(line);

std::unordered_map count;
for (auto c: line)
count[c]++;

if (std::any_of(count.begin(), count.end(), [](auto const& p){return p.second == 3;}))
threes++;
if (std::any_of(count.begin(), count.end(), [](auto const& p){return p.second == 2;}))
twos++;
}

std::cout

(use-modules (ice-9 rdelim))
(use-modules (srfi srfi-1))

(define (read-list f)
(let ((s (read-line f 'trim)))
(if (eof-object? s) '()
(cons s (read-list f)))))

(define (slist->intllist sl)
(map (lambda (s) (map (lambda (c) (- (char->integer c) 97)) (string->list s))) sl ))

(define (do-line l) (count-map (fold do-line-help (make-array 0 26) l)))
(define (do-line-help i tbl)
(array-set! tbl (+ 1 (array-ref tbl i)) i) tbl)

(define (count-map tbl)
(let ((n2 0) (n3 0))
(array-for-each (lambda (n)
(cond ((= n 2) (set! n2 1))
((= n 3) (set! n3 1)))) tbl)
`(,n2 ,n3)))

(define (padd a b) `(,(+ (car a) (car b)) ,(+ (cadr a) (cadr b))))

(define (part1 l) (apply * (fold padd '(0 0) (map do-line l))))

(define (all-eq-but-one x y)
(cond ((null? x) #f)
((= (car x) (car y)) (all-eq-but-one (cdr x) (cdr y)))
(else (equal? (cdr x) (cdr y)))))

(define (allpairs y0 x y )
(cond ((null? x) '())
((null? y) (allpairs (cdr y0) (cdr x) (cdr y0)))
(else (cons `(,(car x) . ,(car y)) (allpairs y0 x (cdr y))))))

(define (revert p)
(list->string (map (compose integer->char (lambda (i) (+ i 97)) car)
(filter (lambda (l) (apply = l)) (zip (car p) (cdr p))))))

(define (part2 l)
(revert (find (lambda (p) (all-eq-but-one (car p) (cdr p))) (allpairs l l l))))

(let* ((f (open-input-file "input.txt"))
(l (slist->intllist (read-list f))))
(format #t "p1: ~a\n" (part1 l))
(format #t "p2: ~a\n" (part2 l)))

weep at my autsim , but in all fairness I dont think its too bad , I know some duplicate values may get added to my list in the first part but its fine really.
a= open('input.txt','r').read().replace("\n"," ").split(" ")[0:-1]
#partone
cdic = {}
m3 = 0
m2 = 0
crli = []
cur = ""
for i in a:
cdic = {}
cur = i

for r in i:
if r in cdic:
cdic[r] +=1
else:
cdic[r] = 1

if 3 in cdic.values():
m3+=1
crli.append(cur)
if 2 in cdic.values():
m2+=1
crli.append(cur)

print(m3*m2)

#part two
a = crli

cdic = {}
samec = 0
ans = ""
for i in a:

for r in a:
samec = 0

if i == r:
break

else:
for k in range(0,len(i)):
if i[k] == r[k]:
samec +=1
if samec + 1 == len(i):
for z in range(0,len(i)):
if i[z] == r[z]:
ans+= i[z]

print(ans)

I failed on 2nd part drastically, had to do O(n^2) solution because I couldn't make a robust O(n) on-spot

import sys
from collections import Counter

def part_one(lines):
two = 0
three = 0
for line in lines:
counts = set(Counter(line.strip()).values())
if 2 in counts:
two += 1
if 3 in counts:
three += 1
print(two * three)

def ex_one_dif(a, b):
if len(a) != len(b):
return False
c = 0
for i in range(len(a)):
if (a[:i] + a[i+1:]) == (b[:i] + b[i+1:]):
c += 1
return c == 1

def part_two(lines):
for i in range(len(lines)):
for j in range(i + 1, len(lines)):
if ex_one_dif(lines[i], lines[j]):
print(lines[i])
print(lines[j])

lines = [i.strip() for i in sys.stdin ]
part_one(lines)
part_two(lines)

with open(‘input.txt’, ‘’) as f:data = f.read()

Haskell:

module Day02 where

import Data.List

file :: IO String
file = readFile "input"

occursTimes :: Ord a => Int -> [a] -> Bool
occursTimes n = elem n . map length . group . sort

ifOccursTimesAdd n l | occursTimes n l = (+1)
| otherwise = id

countBoth :: (Traversable t, Ord a) => t [a] -> (Int, Int)
countBoth = foldl f (0,0)
where f (a, b) str = ( ifOccursTimesAdd 2 str a
, ifOccursTimesAdd 3 str b)

star1 :: IO Int
star1 = uncurry (*) . countBoth . lines file

differ :: (Eq a, Num t) => [a] -> [a] -> (t, [a])
differ = go 0 []
where go n rs xs ys = case (xs, ys) of
(a:as, b:bs) | a == b -> go n (a:rs) as bs
| otherwise -> go (n + 1) rs as bs
([],[]) -> (n, reverse rs)
_ -> error "something happened"

findOneDiff :: (Applicative t, Foldable t) => t String -> String
findOneDiff l = maybe "something happened" snd . find ((== 1) . fst)
$ differ l l

star2 :: IO String
star2 = findOneDiff . lines file

main :: IO ()
main = star1 >>= print >> star2 >>= print


What are runtimes like today? This runs in 17ms.

in part 2 your second loop doesn't need to traverse the whole file, either traverse all the elements in a up to i, or all the elements in a after i.

there's obviously places where you could cut down some code with in built functions/ small shortcuts but your alg is otherwise solid.

for me, it's part 2
std::string solve_part_two(std::ifstream& ifs)
{
std::string line;
std::vector lines;
while (std::getline(ifs, line))
lines.push_back(std::move(line));

std::sort(lines.begin(), lines.end());

const std::size_t ROWS = lines.size();
const std::size_t COLS = lines.front().size();
for (std::size_t i = 0; i < ROWS - 1; ++i) {
std::size_t diffs = 0;
for (std::size_t j = 0; j < COLS; ++j) {
if (lines[i][j] != lines[i + 1][j] && diffs++ != 0)
break;
}

if (diffs == 1) {
std::string common_chars;
for (std::size_t j = 0; j < COLS; ++j) {
if (lines[i][j] == lines[i + 1][j]) {
common_chars.push_back(lines[i][j]);
}
}

return common_chars;
}
}

return {};
}

anything better than O(N^2) possible?

matlab is neat

just find a library to solve the problem for you lmaoooo

from jellyfish import levenshtein_distance

def main():
with open("input.txt") as f:
content = f.read().split()

best_distance = 99999

for s1 in content:
for s2 in content:
if s1 == s2:
break
else:
if levenshtein_distance(s1, s2) < best_distance:
best_distance = levenshtein_distance(s1, s2)
best_s1 = s1
best_s2 = s2

print(best_distance)
print(best_s1)
print(best_s2)

Attached: 1506099199074.png (645x729, 50K)

no wait, this is O(N).

O(NlogN)*

(defn has-multiple-char [multiple string]
(some #(= (second %) multiple) (frequencies string)))

(defn hamming-distance [s1 s2]
(if (not (= (count s1) (count s2)))
nil
(reduce (fn [acc cur]
(if (= (first cur) (second cur))
acc (inc acc)))
0
(map vector s1 s2))))

(let [input (str/split (slurp "input2.txt") #"\n")]
(let [twos (filter (partial has-multiple-char 2) input)
threes (filter (partial has-multiple-char 3) input)]
(* (count twos) (count threes))))

(let [input (str/split (slurp "input2.txt") #"\n")]
(let [twos (filter (partial has-multiple-char 2) input)
threes (filter (partial has-multiple-char 3) input)
all (distinct (concat twos threes))]
(filter
(fn [[s1 s2]] (= 1 (hamming-distance s1 s2)))
(combo/combinations all 2))))

Clojure

Any way I could make this code more "rusty"?
use std::fs;

fn main() {
let contents = fs::read_to_string("input.txt").unwrap();

for id in contents.lines() {
contents.lines().for_each(|other| {
if diff_chars(id, other) == 1 {
println!("{}", id);
}
})
}
}

fn diff_chars(id: &str, other: &str) -> i32 {
if id.len() != other.len() {
return -1;
}

let mut diff_chars = 0;
id.chars().zip(other.chars()).for_each(|(a, b)| {
if a != b {
diff_chars += 1
}
});
diff_chars
}

Attached: Capture.png (774x1236, 46K)

my haskell solution runs in 9ms, my scheme solution takes about 25

#include
#include
#include
#include
#include

int main()
{
std::fstream f("f.txt");

std::stringstream ss;

ss length(); ++u)
{
if (i->at(u) != st[u])
{
++comp;
}
if (comp > 1)
{
break;
}
}
if (comp == 1)
{
std::cout

sort your input for an easy speed boost! see

arg = get_input(1)
S = set()
for line in arg:
m = len(line)
S2 = set()
for k in range(m):
ss = line[0:k] + line[k+1:m]
if ss in S:
print(ss)
else:
S2.add(ss)
for ss in S2:
S.add(ss)

What do you think about this?
With N the number of words and M the length of a word, I think it would be O(NM)

I don't know the complexity of ss = line[0:k] + line[k+1:m], so it could be O(NM2). Still, it's linear in N

>mfw
impressive

Oh damn I didn't realize the timer starts when the puzzle unlocks.
I thought it depends on when you generate your input or open the page or something like that.
Do you guys set an alarm to solve the puzzles on time?

Attached: Screenshot from 2018-12-02 14-15-28.png (646x144, 12K)

no, I like sleeping

No image for the day yet?

must of us are here at midnight/when the puzzle unlocks.

Yeah, I wake up at 5AM to shitpost here, then do the puzzle an hour later

No I get up at around 11 AM and the puzzle unlocks at 6 so it's not worth it. Last year I worked night shifts so I was doing them on release but I won't reschedule my sleep for a puzzle.

Yeah MATLAB was especially good for day 2 as it's nice to solve with matrix manipulations.

ye I don't feel like waking up at 6 am just to do a puzzle and feel like shit the rest of the day at work.
guess that means I'm not getting anyplace high in the leaderboards
anyone here on the global leaderboards?

You could use a const string reference instead of deep copy for st.
Also you need to strip the duplicate letters from your output.

#44

I'm #43 :^)

It starts at 3:00 in the evening for me. :^)

Apologies to people who actually know Common Lisp.
(defun count-char-occurances (line)
(let ((counter (make-hash-table)))
(loop for c across line do
(let ((m (gethash c counter)))
(if (not (null m))
(setf (gethash c counter) (1+ m))
(setf (gethash c counter) 1))))
counter))

(defun count-groups (hash)
(let ((two-count 0)
(three-count 0))
(maphash #'(lambda (k v)
(cond ((= v 2) (setf two-count 1))
((= v 3) (setf three-count 1))))
hash)
(list two-count three-count)))

(defun first-part (input)
(let ((two-total 0)
(three-total 0))
(dolist (l input)
(let ((result (count-groups (count-char-occurances l))))
(incf two-total (first result))
(incf three-total (second result))))
(* two-total three-total)))

(defun char-onediffp (x y)
(let ((diff-count 0))
(loop
for i in (coerce x 'list)
for j in (coerce y 'list)
if (char/= i j)
do (incf diff-count)
when (> diff-count 1)
do (return-from char-onediffp t))
nil))

(defun find-similar-lines (input)
(let ((lines (copy-list input))
(results ()))
(dolist (line lines)
(let ((comparisons (remove-if #'(lambda (l) (or (string= line l)
(char-onediffp line l)))
lines)))
(if comparisons (push line results))))
results))

(defun str-to-char-list (l)
(mapcar #'(lambda (x) (coerce x 'list)) l))

(defun second-part (lines)
(let ((similar (str-to-char-list (find-similar-lines lines))))
(coerce (loop
for i in (first similar)
for j in (second similar)
if (char= i j)
collect i)
'string)))

Nice
We'll see if we get to stay or not, I've been lucky yesterday and today but I don't think it's going to last

Oh yeah I was a bit lazy and did the stripping myself. That's why I print out both strings. But you're right; I'm bad when it comes to using references, I'll keep it in mind.

Attached: rusty.png (971x444, 303K)

I tried to do it O(n) in n
static void FindPairLinear(string file)
{
string[] words = File.ReadAllLines(file);
int wordsize = words[0].Length;
HashSet[] hs = new HashSet[words.Length];

for (int i = 0; i < words.Length; i++)
for (int j = 0; j < wordsize; j++)
{
if (hs[j] == null) hs[j] = new HashSet();

string word = words[i].Substring(0, j) +
words[i].Substring(j + 1, words[i].Length - j - 1);

if (!hs[j].Add(word))
{
Console.WriteLine(word);
return;
}
}
}

I wouldn't lie on the internet, would I.

Also part 1 for my MATLAB solution

alphabet = 'a':'z';
alphabet = alphabet';

twice_thrice_map = zeros(length(data), 2);

for i = 1:length(alphabet)
s = sum(data(:,:) == alphabet(i), 2);
twos = find(s == 2);
threes = find(s == 3);
twice_thrice_map(twos,1) = 1;
twice_thrice_map(threes, 2) = 1;
end

checksum = sum(twice_thrice_map(:,1)) * sum(twice_thrice_map(:,2))

Attached: diogenes.jpg (1280x1032, 450K)

I DONT FUCKING UNDERSTAND IT

Attached: 1443553636207.jpg (250x250, 10K)

?

install gentoo

Answer me you fucks

How does one go about finding a proper candidate for twice if the char that occurs thrice is the same that you found twice?
How to find another proper candidate.

This won't work for this test case:

abcd
acde

They have a hamming distance of 3, but your algorithm would find these two in your set
a_cd
acd_

thus giving a false positive.

That happened to me too and I fixed it by using a lot of sets here:

that's at least O(nm), m being the length of the words. might be more depending on the complexity of Substring and concat

looks like you're quadratic in line size

the post I quoted disregarded M so I did too, but yeah you're completely right.

kinda disappointed in part two, there should've been more data
there's so little that the naive solution in python runs under a second

heres mine

Attached: day2.png (548x810, 63K)

There's only two ids that differ by one.

read the instructions of the problem...

Attached: file.png (840x182, 33K)

*exactly* two of any letter
*exactly* three of any letter


Definition of exactly

1a : in a manner or measure or to a degree or number that strictly conforms to a fact or condition

so if you have a 3x then it doesn't count towards 2x

Oh right I forgot about that

Then the slightly better attempt that my own shame compelled me to do.
(defun count-repeated (s)
(let ((counter ()))
(loop for c across s
for m = (assoc c counter)
do (if m
(rplacd m (incf (cdr m)))
(setf counter (acons c 1 counter))))
(delete-if-not #'(lambda (x)
(or (= 2 (cdr x)) (= 3 (cdr x))))
counter)))

(defun first-part (input)
(let ((total-two 0)
(total-three 0))
(dolist (line input)
(let ((counted (count-repeated line)))
(if (rassoc 2 counted) (incf total-two))
(if (rassoc 3 counted) (incf total-three))))
(* total-two total-three)))

(defun similar-stringp (x y)
(let ((diff-count 0))
(when (not (eq x y))
(loop for i across x
for j across y
if (char/= i j)
do (incf diff-count)
when (> diff-count 1)
do (return-from similar-stringp nil)
collect i))))

(defun strip-unique (x y)
(coerce (loop for i across x
for j across y
if (char= i j)
collect i)
'string))

(defun second-part (input)
(let ((result ()))
(dolist (l input)
(dolist (s input)
(if (similar-stringp l s)
(push l result))))
(reduce #'strip-unique result)))

>read the instructions of the problem...
lmao every fucking time

Step away from iterating and think about recording.

>for
>for
>iterating over the hashmap 2 times
>'outer: for
>for
use more iterator adaptors/10

What's the required IQ to complete all the challenges last year?

at most 108

about 80

Yes Im fucking aware. Notice where it says counts for both?

halp

Depends on the language you're using
>List
140+
>C
130+
>Haskell
120+
>Go
100+
>Java-tier shit
80+
>Python
no requirement

forgot image god help me.

Attached: brainlet.png (392x219, 5K)

Attached: file.png (645x773, 164K)

guess that makes python the best language

Solving this shit in C is easier than in Haskell though.

arg = get_input(1)
S = set()
for line in arg:
m = len(line)
for k in range(m):
ss = line[0:k] + line[k+1:m]
if (ss,k) in S:
print(ss)
else:
S.add((ss,k))

This should be correct (executes in 15ms)
I think it's the same logic as yours

please bully me, but I've no fucking idea about which part of the problem I don't understand.

Attached: Capture.png (352x734, 23K)

C# Linq is my guilty pleasure.

Attached: Day02.png (964x917, 50K)

I'm guessing it's the 'exactly' part

This guy fucks.

You're overengineering it.
def count(data, a):
t = 0
for l in data:
for c in l:
if l.count(c) == a:
t=t+1
break
return t
data = [x.strip() for x in open('input.txt').readlines()]
print('Checksum: ' + str(count(data,2)*count(data,3)))
You're already doing most of this in the occurance function.

Can't you put split.trim.isnullorempty in the Solution thing?

got 0.3ms on this one

Mirin'
I see you're using attributes, are you pulling the dataset automagically and checking if it works?

;_; thanks

I just wanted this to work before making it pretty and fast.

You're not going to get this faster than O(n).
The length of the strings is constant, so it doesn't count.

inefficient solution, you are looping through the data twice here when you can get all the info you need by looping it just once.

>inefficient solution
it's more readable, so idgaf

Linq is a miracle.

twitch.tv/videos/343498733##
Why aren't you watching xir stream? The creator of AoC loves this

It's really not, it's just C# syntax for what you do in Haskell often.
Still nice if you /have/ to work with C#, that you can write monadic interfaces to your shit and handle errors in a single function for instance.

is that a man?

why are trannies so common in the IT but not as much everywhere else? does computer autism enable mental illness?

>skip ahead
>Social media is half of my life

Attached: 1513480589362.jpg (640x480, 67K)

Attached: Capture.png (295x460, 175K)