Advent of Code

[Ben T]

Less than a second including calc of leg lengths?? If so mine must be inefficient then as that takes about 5 seconds per leg. Only reason could be that it is plodding along one square at a time rather than going as far as possible with each movement. But optimizing probably unnecessary...

[David Martin]

(click to show/hide)

Nope, reads it in to a graph structure straight off then does a BFS starting from each node (that gives you all 7 distances, though you are measuring them all twice. The only condescension to optimisation is not to start at all points as the distances are symmetric so I skip one BFS and read the results from the other.

Code: [Select]

import itertools,functools
from queue import Queue
class Graphnode ():
    def __init__(self, name, x,y):
        self.name = name
        self.links=[]
        self.x=x
        self.y=y
        self.steps=None

    def addlink(self,node):
        self.links.append(node)

    def resetsteps(self):
        self.steps=None
        self.parent=None
       
    def __repr__(self):
        return 'Node {} at {} steps'.format(self.name, self.steps)
graph={}
points={}

data=[x.strip() for x in open('day24input.txt').readlines()]

stack =[]
# now build the graph
for y in range(len(data)):
    for x in range(len(data[y])):
        if data[y][x] != '#':
            name = 'N{}-{}'.format(x,y)
            node=graph.get(name)
            #print(name, node)
            if node==None:
                node=Graphnode(name, x,y)
                graph[name]=node
            if data[y][x] !='.':
                points[data[y][x]]=node
            if data[y][x+1] != '#':
                newname='N{}-{}'.format(x+1,y)
                linknode=graph.get(newname)
                if linknode is None:
                    linknode=Graphnode(newname, x+1,y)
                    graph[newname]=linknode
                linknode.addlink(node)
                node.addlink(linknode)
            if data[y+1][x] != '#':
                newname='N{}-{}'.format(x,y+1)
                linknode=graph.get(newname)
                if linknode is None:
                    linknode=Graphnode(newname, x,y+1)
                    graph[newname]=linknode
                linknode.addlink(node)
                node.addlink(linknode)

# now do exhaustive search for each pairwise distance.
distances ={}
for k in list(points.keys())[:-1]:
    distances[k]={}
    for n in graph.values():
        n.resetsteps()
       
    root = points[k]
    root.steps=0
    stack=Queue()
    stack.put(root)
    while not stack.empty():       
        current = stack.get()
        for  n in current.links:
            if n.steps is None:
                n.steps = current.steps + 1
                n.parent = current
                stack.put(n)
    for d in points.keys():
        distances[k][d] = points[d].steps
       
distances['2']={'2':0}     
for k in distances.keys():
     distances['2'][k]=distances[k]['2']

def distx(x):
    return sum( [distances[x[i]][x[i+1]] for i in range(len(x)-1)])

nodes = [str(x)for x in range(1,8)]

part1=functools.reduce(min,map(distx, [ ['0']+list(x) for x in itertools.permutations(nodes)]))
part2=functools.reduce(min,map(distx, [ ['0']+list(x)+['0'] for x in itertools.permutations(nodes)]))
print(part1,part2)
Python has really good optimisations for iterations and map/reduce so I am learning to use those.

[David Martin]

Today's is quite fun.

(click to show/hide)

It is quite enlightening seeing just how many operations it takes to do something simple. For those of a coding bent a hint is

(click to show/hide)

The multiply has been met before but the divide/modulo operation is new

(click to show/hide)

>> is what it is all about

(click to show/hide)

but the number you put in is not the signal, it completes the signal.

I quite enjoyed working out what the code was doing and then determining the input needed by hand rather than brute forcing it to calculate the answer. I will admit that implementing a compiler to simplify the task is beyond my current resources (time and ability).

[Ben T]

(click to show/hide)

var answer = Enumerable.Range(2550, Int16.MaxValue).First(s => Regex.IsMatch(Convert.ToString(s, 2), @"^(10)+$")) - 2550;

or slightly more terse but less calculation:

(click to show/hide)

var answer = Convert.ToInt32(Enumerable.Range(1, 10).Select(i => string.Join("", Enumerable.Repeat("10", i))).First(s => Convert.ToInt32(s, 2) > 2550), 2) - 2550;

[Pickled Onion]

day 19 part 1:

(click to show/hide)

int get_answer(int numElves)
{
   int hpt_pow = (int)log2(numElves);
   int hpt = pow(2, hpt_pow);
   int ans = (numElves - hpt) * 2 + 1;
   return ans;
}

I know I'm a bit behind the times (computer downtime). I liked this one too, it's clear there's an analytic solution - every second elf loses his presents. But the problem as presented looks like a queue, so I coded it in that spirit:

(click to show/hide)

while (scalar @elves > 1){
   push @elves, shift @elves;
   shift @elves;
}

[David Martin]

Very neat.

[Pickled Onion]

Thank you. 

Perl's lists/arrays are optimised for use as queues, so repeated push/pop/shift/unshift does not create a massive realloc fest. Unfortunately, removing an element from the middle is something else entirely, so part 2 in the same vein

(click to show/hide)

while (scalar @elves > 1){
   push @elves, shift @elves;
   splice @elves, int((scalar @elves)/2)-1, 1;
}

takes rather a long time...

[Ben T]

Withdrawal symptoms?
I've found this website https://projecteuler.net which offers a multitude of problems some of which appear to solvable by programming.
Some are quite interesting, e.g. this one https://projecteuler.net/problem=575 which I've managed to solve.
A lot seem very maths-heavy e.g. about sets of prime  numbers and the like, but they do appear to be simple from a brute force point of view but then you are asked from a number very high in the sequence, so either mathematical knowledge and/or heavy optimization or realizing some vast simplification is required.

[Oaky]

2017 AoC in about 16 hours time!

[Greenbank]

ooh, signed up

(And going back and doing 2016 as practice...)

[Diver300]

2017 AoC in about 16 hours time!

Arrgghhh!

December productivity will be at it's usual post 2015 levels.

[David Martin]

That's the marking taking a back seat then.

Is there a YACF league?

[Croft]

From previous years, the YACF leaderboard code is 48462-ea506236

[davelodwig]

Enjoyed that, once I'd remembered to read the question properly.

Am using PHP just because that's what I happen to use daily.

D.

[Oaky]

I'm using Python again,  trying to use Pandas/numpy wherever possible.

(click to show/hide)

Today's turned into an easy application of np.roll()

[freeflow]

Done today's using VBA. Tomorrow I'll try python.

[David Martin]

I'm using Python again,  trying to use Pandas/numpy wherever possible.

(click to show/hide)

Today's turned into an easy application of np.roll()

Interesting - I'd not seen that.
The second part is a special case

(click to show/hide)

You can do the first half (range(len(x)//2)) then double it because you are then matching the symmetrical pair.

[Pickled Onion]

Ah yes, well spotted. A language that supports negative array indices is hinted by part one, and helps for part 2.

58 keystrokes. Anyone manage fewer?

[Greenbank]

ooh, signed up

(And going back and doing 2016 as practice...)

2016 done, will move on to 2015 too.

Doing all of mine in Perl as that's what I use for quick hacks and prototypes.

[David Martin]

Ah yes, well spotted. A language that supports negative array indices is hinted by part one, and helps for part 2.

58 keystrokes. Anyone manage fewer?

I presume that is CTRL-C/CTRL-V to copy and paste the original data? And is that one part or both parts.
81 characters, but some are spaces.

[Pickled Onion]

ok, I didn't include the data or printing out the answer. Fully working solution is 64 characters for part 1 and 67 characters for part 2

(click to show/hide)

Code: [Select]

@a=split//,<>;map$s+=$a[$_],grep$a[$_-1]==$a[$_],0..@a-1;print$s
@a=split//,<>;map$s+=$a[$_],grep$a[$_-@a/2]==$a[$_],0..@a-1;print$s



[Greenbank]

2016 done, will move on to 2015 too.

Doing all of mine in Perl as that's what I use for quick hacks and prototypes.

Ugh, enough for now, done up to (and including day 16 of 2015).

[Pickled Onion]

It's started to get more interesting today. Only day 3, is this year going to be a tough one?

Out of interest, who are Phong and mTrak? I'm iakobski.

[David Martin]

That was painful. The first part was elementary maths - no code needed.
The second part I used a dynamic programming approach and promptly filled it so full of bugs it took a long time to wrangle out. Was there a more elegant way that I somehow missed?

(click to show/hide)

I cached previous results, only calculating the ones I needed.
Work out which square you are on and which piece in which side. Write all the edge cases for turning the corners and then iterate backwards and forwards till you hit the two numbers surrounding the input data.

Seems very hard for day 3.

[Pickled Onion]

That's the thing with a lot of these - if you short-circuit part 1, you find part 2 needs the data from part 1.

I built the whole grid in part 1, even though it was obvious there would be a clever way round that, so adding on a value to each point was trivial.

However my first attempt using recursion succeeded only in turning my laptop into a lap-heater, who knew that recursing several of hundreds deep on each point was not the best use of cpu cycles