Advent Of Code - 25 challenges for December

[Nineshadow]

I thought I had it solved, then I got a stack overflow

How did you even get a stack overflow?

Mine looks fugly but works just fine.

(2nd part of the 3rd problem)

#include <iostream>#include <fstream>using namespace std;ifstream in("santa.in");int size = 10000;int m[10000][10000];int main(){    char c1 , c2;    int x1 = size/2, y1 = size/2, x2 = size/2 , y2 = size/2, k = 0;    m[y1][x1] = 1;    m[y2][x2] = 1;    while(in >> c1 >> c2)    {        if(c1=='>')x1++;        if(c1=='<')x1--;        if(c1=='^')y1--;        if(c1=='v')y1++;        if(c2=='>')x2++;        if(c2=='<')x2--;        if(c2=='^')y2--;        if(c2=='v')y2++;        m[y1][x1] = 1;        m[y2][x2] = 1;    }    for(int i = 0; i < size; i++)        for(int j = 0; j < size; j++)        if(m[i][j]==1) k++;    cout << k;    return 0;}

[madknight3]

How did you even get a stack overflow?

 

Recursion.

 

The first thing that came to mind when I read the question was a solution like yours, however I decided to try solving it in a different way.

 

My original algorithm recursively constructed a list of unique coordinates, [(0,0), (0,1), etc], the length of which is the result of part 1. However the way I implemented it caused a stack overflow.

 

I ended up getting rid of the stack overflow, and solving part 1, by slightly modifying the algorithm. First it recursively constructs the list of all coordinates and then it removes all duplicates. The length of the unique list again being the answer.

 

It's not very fast but it works and it was easy to modify to solve part 2.

[DevBlox]

I find these useful to learn a new language, I'm going python for this one. Has anyone got any good sources on development and design patterns for it? Would be a great read.

      

Completed the third one, was too easy to do in python, I wonder how hard will they get, I want to use good design in all of these, since it's what I'm aiming to learn anyway .

[b4ux1t3]

This is awesome! What a well-designed site. This would be great for a high school programming class to do over the holidays. I'm gonna have to send this to the programming teachers I know.

[madknight3]

I find these useful to learn a new language, I'm going python for this one. Has anyone got any good sources on development and design patterns for it? Would be a great read.

      

Completed the third one, was too easy to do in python, I wonder how hard will they get, I want to use good design in all of these, since it's what I'm aiming to learn anyway .

 

Programming challenges like these tend to be very small and you probably won't get much out of them from a design standpoint. You might get a few functions, maybe even the occasional class, so do the best you can I guess. You can take a TDD approach, or simply unit test, since they often give you example input/output. You might come across problems that require similar algorithms (for example Project Euler has multiple problems on prime numbers) so in those cases you can put them in their own files and import them as needed. Over time this may grow to be something fairly substantial, so try to design it well.

 

Programming challenges are great for improving your problem solving skills, and skills with data structures and algorithms, however if you really want to practice design, you'll want to build a more substantial piece of software.

[prolemur]

Day 4 was super simple to brute force, but are they any other ways than calculating md5 thousands of times?

[Wtalk2]

Day 4 was super simple to brute force, but are they any other ways than calculating md5 thousands of times?

Yeah, I just bruteforced it as well with the default Python hashlib module. If you wanted to do it any other way I think you might have to reverse engineer the actual algorithm that MD5 uses which IMO just isn't worth it.

 

PS: I don't actually have any idea on how you would do it any other way, just a quick guess.

[EpicAdom]

This is cool. I started off and did the first exercise in Python 3 (very easy)

[MisterWhite]

so stuck at the second day.

I can't seem to figure out how to get the numbers from this

string 2x3x4

[prolemur]

 

so stuck at the second day.

I can't seem to figure out how to get the numbers from this

string 2x3x4

Look for a split function and use x and the string as parameters

[MisterWhite]

Look for a split function and use x and the string as parameters

i used stringstream.

string a = boxes[0];    stringstream stream (a);    char s,b;    stream>>l[0]>>s>>h[0]>>b>>w[0];

[MisterWhite]

Day 4 was super simple to brute force, but are they any other ways than calculating md5 thousands of times?

i suppose you did the second days 1st challenge. So i get the numbers in the examples (58, min=6 ; 43, min=1), but i get it wrong with my input puzzle, maybe, if you have your code, you could check if you get :

1600826

Here's the link to the text file (used the first page on google to upload my .txt because i don't know how to upload here): http://www.filedropper.com/file_227

EDIT: figured it out , i did not consider the fact that 2 sides might be equal

[Nineshadow]

Anyone know a good md5 function/library/etc. for c++?

[madknight3]

Day 4 was super simple to brute force, but are they any other ways than calculating md5 thousands of times?

 

I also took the brute force method. if you want to improve efficiency you can run the brute force in parallel.

 

You might be able to use a divide and conquer style algorithm on it. At first I thought a binary search style algorithm would work but then I realized you can't know if the answer is higher/lower so you'd have to check both. This is basically just a brute force algorithm in a different order so I'm not sure it would be any better.

[madknight3]

I was worried the day 6 problem was going to run too poorly with an immutable list but it didn't end up taking too long.

 

Like the problem for day 3, I decided to use an immutable list of tuples over the more conventional mutable 2D array.

[madknight3]

In case anyone missed the reference in the day 7 challenge.

 

 

Source

[fizzlesticks]

I always start these thinking I'm going to spend the time to write good code then after 2 minutes I get lazy and start copy and pasting all over the place just to get it done ; /. 

 

class Wire:    def __init__(self, val=None):        self.val = val        self.outputs = []    def update(self):        for w in self.outputs:            w.val = self.valclass Gate:    def __init__(self, inputs=None, output=None):        self.inputs = inputs or []        self.output = output    def can_run(self):        for w in self.inputs:            if w.val == None:                return False        return True    def run(self):        passclass AndGate(Gate):    def run(self):        if self.can_run():            total = 0xFFFF            for w in self.inputs:                total &= w.val            total &= 0xFFFF            self.output.val = total            self.output.update()class OrGate(Gate):    def run(self):        if self.can_run():            total = 0            for w in self.inputs:                total |= w.val            total &= 0xFFFF            self.output.val = total            self.output.update()class NotGate(Gate):    def run(self):        if self.can_run():            self.output.val = ~self.inputs[0].val            self.output.val &= 0xFFFF            self.output.update()class RShiftGate(Gate):    def __init__(self, inputs=None, output=None, shift=0):        super().__init__(inputs=inputs, output=output)        self.shift = shift    def run(self):        if self.can_run():            self.output.val = self.inputs[0].val >> self.shift            self.output.val &= 0xFFFF            self.output.update()class LShiftGate(Gate):    def __init__(self, inputs=None, output=None, shift=0):        super().__init__(inputs=inputs, output=output)        self.shift = shift    def run(self):        if self.can_run():            self.output.val = self.inputs[0].val << self.shift            self.output.val &= 0xFFFF            self.output.update()if __name__ == '__main__':    with open('input7.txt') as f:        inp = f.read().split('\n')    wires = dict()    gates = []    anon_wires = []    for line in inp:        if not line:            break        #part 2        #if line.endswith('-> b'):        #    line = '956 -> b'        words = line.split(' ')        if 'AND' in line or 'OR' in line:            w1 = wires.get(words[0], None)            w2 = wires.get(words[2], None)            out = wires.get(words[4], None)            if not w1:                w1 = Wire()                try:                    val = int(words[0])                    w1.val = val                    anon_wires.append(w1)                except:                    wires[words[0]] = w1            if not w2:                w2 = Wire()                try:                    val = int(words[2])                    w2.val = val                    anon_wires.append(w2)                except:                    wires[words[2]] = w2            if not out:                out = Wire()                wires[words[4]] = out            if 'AND' in line:                gate = AndGate(inputs=[w1, w2], output=out)            else:                gate = OrGate(inputs=[w1, w2], output=out)            gates.append(gate)        elif 'NOT' in line:            w1 = wires.get(words[1], None)            out = wires.get(words[3], None)            if not w1:                w1 = Wire()                wires[words[1]] = w1            if not out:                out = Wire()                wires[words[3]] = out            gates.append(NotGate(inputs=[w1], output=out))        elif 'SHIFT' in line:            w1 = wires.get(words[0], None)            out = wires.get(words[4], None)            shift = int(words[2])            if not w1:                w1 = Wire()                try:                    val = int(words[0])                    w1.val = val                    anon_wires.append(w1)                except:                    wires[words[0]] = w1            if not out:                out = Wire()                wires[words[4]] = out            if 'R' in line:                gate = RShiftGate(inputs=[w1], output=out, shift=shift)            else:                gate = LShiftGate(inputs=[w1], output=out, shift=shift)            gates.append(gate)        else:            out = wires.get(words[2], None)            w1 = wires.get(words[0], None)            if not w1:                w1 = Wire()            if not out:                out = Wire()                wires[words[2]] = out            try:                val = int(words[0])                w1.val = val                anon_wires.append(w1)                w1.outputs.append(out)                out.val = val            except:                wires[words[0]] = w1                w1.outputs.append(out)                out.val = w1.val    wire_a = wires['a']    while wire_a.val == None:        for gate in gates:            gate.run()    print(wire_a.val) 

[prolemur]

I'm still having issues with my Day 6 code not working, it's probably something I overlooked in Perl, since I'm new to it and mostly just using it to learn it and learn  regular expressions.

[madknight3]

Day 7, part 1, currently has me stumped.

 

I got it working for the sample input, however I failed on the real input. At first I though you just had to assume 0 for anything not already set but that didn't work. Then I realized I missed an important part of the puzzle.

 

A gate provides no signal until all of its inputs have a signal.

 

I'm gonna have to give this one some more thought and then rework my solution a bit.

[prolemur]

I really don't see where I'm going wrong but keep getting the wrong answer >

#!/usr/bin/env perluse strict;use warnings;use File::Slurp qw/read_file/;my @[member='data'] = read_file('input');my $count = 0;my $lights = {};foreach my $line (@[member='data']) {        $line =~ /^(turn on|turn off|toggle) (\d+),(\d+) through (\d+),(\d+)/;        for(my $x = $2; $x <= $4; $x++) {                for(my $y = $3; $y <= $5; $y++) {                        if($1 =~ /on/) {                                $lights->{$x}{$y} = 1;                        } elsif($1 =~ /off/) {                                $lights->{$x}{$y} = 0;                        } elsif($1 =~ /toggle/) {                                $lights->{$x}{$y} = 0 unless defined $lights->{$x}{$y};                                $lights->{$x}{$y} = !$lights->{$x}{$y};                        }                }        }}foreach my $x (keys %$lights) {        foreach my $y (keys %{$lights->{$x}}) {                $count++ if $lights->{$x}{$y};        }}print "Total: $count\n";

input: http://pastebin.com/Ad8gVqaf

 

Testing with input as

turn on 0,0 through 999,999 # 1,000,000
turn off 499,499 through 600,600 # 989,596
toggle 0,0 through 999,999 # 10,404
 

Each line results in these many lights being turned on

Edited December 7, 2015 by alpenwasser
use strict;use warnings; :P

[MisterWhite]

Hey Day 3 part 2 here.

So i split the whole puzzle into 2 pieces, first is for santa, second is for RoboSanta, goes like this:

cnt=0,number=0// cnt for keeping track of how many chars it getsfor(int i = 0; i< count; i++)// count== all chars (8000+){          if( (i+1)%2!=0 )        {            Santa[number]=houses[i];            number++;            cnt++;        }         else          // same but for santaRob

So i get 2 more char arrays and i let them through my house counting algorithm (im in part 2, so it works) but when i get the sum of santa and roboSanta, it's wrong.. suggestions?

[MisterWhite]

Someone please check if you get 2359 with my file: http://pastebin.com/6dTCVCrU

I'm pretty much done, can't find any more mistakes...

EDIT:DONE

[MisterWhite]

BTW on day 4, do i have to understand what MD5 and mining means or i can do it either way, cause from the looks of it need some base knowledge

[fizzlesticks]

BTW on day 4, do i have to understand what MD5 and mining means or i can do it either way, cause from the looks of it need some base knowledge

You just need to understand that MD5 is a hashing function that takes some input string and transforms it into a seemingly random 32 character hex string. Since you use C++ you'll need some library that performs the function, or you could try something like Python that has it built in.

[Nineshadow]

I have a question about the 7th day.

If we have something like

(y RSHIFT 2)-> Zx -> y124 -> x

y will be equal to 124 , and z will be 31, right?

 

The order doesn't matter. We can reference to non-initialized wires, right?