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.
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?
Cameron Sanchez
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.
Oliver Nelson
>he didn't convert his strings to matrices as first step never gonna make it
Hudson Diaz
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)
Jace Green
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())
Nicholas Jenkins
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
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())
Luke James
I did some more testing and here's the results visualization.
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)
Logan Bailey
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)
Jaxson Kelly
with open(‘input.txt’, ‘’) as f:data = f.read()
Michael Jenkins
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)
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
main :: IO () main = star1 >>= print >> star2 >>= print
What are runtimes like today? This runs in 17ms.
Jeremiah Cox
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.
Nathan Martin
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
Nolan Jenkins
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
my haskell solution runs in 9ms, my scheme solution takes about 25
Michael Hughes
#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
Angel Fisher
sort your input for an easy speed boost! see
James Thomas
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
Isaiah Cooper
>mfw impressive
Adam Cruz
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?
must of us are here at midnight/when the puzzle unlocks.
Jason Jenkins
Yeah, I wake up at 5AM to shitpost here, then do the puzzle an hour later
Adam Green
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.
Dominic Ortiz
Yeah MATLAB was especially good for day 2 as it's nice to solve with matrix manipulations.
Hunter Stewart
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?
Isaac Rogers
You could use a const string reference instead of deep copy for st. Also you need to strip the duplicate letters from your output.
Aiden Jackson
#44
Thomas Rivera
I'm #43 :^)
Joshua Green
It starts at 3:00 in the evening for me. :^)
Jaxson Perry
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 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 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)))
Ryan Diaz
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
Cameron Nguyen
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.
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();
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.
Austin Bell
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:
Jonathan Ramirez
that's at least O(nm), m being the length of the words. might be more depending on the complexity of Substring and concat
Ayden Baker
looks like you're quadratic in line size
Anthony Wood
the post I quoted disregarded M so I did too, but yeah you're completely right.
Gabriel Powell
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
*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
Gabriel Rodriguez
Oh right I forgot about that
Joshua Rogers
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 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)))
Grayson Lee
>read the instructions of the problem... lmao every fucking time
Julian Campbell
Step away from iterating and think about recording.
Bentley Wood
>for >for >iterating over the hashmap 2 times >'outer: for >for use more iterator adaptors/10
Jackson Murphy
What's the required IQ to complete all the challenges last year?
Blake Torres
at most 108
Juan Rogers
about 80
Levi Foster
Yes Im fucking aware. Notice where it says counts for both?
halp
Asher Rodriguez
Depends on the language you're using >List 140+ >C 130+ >Haskell 120+ >Go 100+ >Java-tier shit 80+ >Python no requirement
Solving this shit in C is easier than in Haskell though.
Logan Richardson
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
Jayden Bennett
please bully me, but I've no fucking idea about which part of the problem I don't understand.
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.
William Walker
Can't you put split.trim.isnullorempty in the Solution thing?
Hunter Adams
got 0.3ms on this one
Joshua Morris
Mirin' I see you're using attributes, are you pulling the dataset automagically and checking if it works?
Kayden Harris
;_; thanks
I just wanted this to work before making it pretty and fast.
Robert Reyes
You're not going to get this faster than O(n). The length of the strings is constant, so it doesn't count.
Gavin Thomas
inefficient solution, you are looping through the data twice here when you can get all the info you need by looping it just once.
Nathan Gonzalez
>inefficient solution it's more readable, so idgaf
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.
Isaac Wood
is that a man?
Juan Phillips
why are trannies so common in the IT but not as much everywhere else? does computer autism enable mental illness?