Advent of Code

[red marley]

Finally found an answer to Day 12b (JSON parsing)

(click to show/hide)

Kludged the Processing JSON parser to work with the sample json file. Most parsers seem to be designed to work with a schema where you know what elements / objects / arrays to expect. Since this challenge involves navigating nested arrays and objects with a random structure and set of keys, I had to try for each type and do lots of exception catching when, for example, I tried to read an object when an array was found or integer when a String was found. Not very elegant, but it did find the solution in under a second.

[David Martin]

processing.org seems to fit the bill

Thanks jo.

Will play after my trip to Germany.


(Thanks also Pancho for the perl suggestion.)

An alternative is the python Anaconda distribution and the Spyder IDE (which is what I have done most of mine in.)

[David Martin]

Finally found an answer to Day 12b (JSON parsing)

(click to show/hide)

Kludged the Processing JSON parser to work with the sample json file. Most parsers seem to be designed to work with a schema where you know what elements / objects / arrays to expect. Since this challenge involves navigating nested arrays and objects with a random structure and set of keys, I had to try for each type and do lots of exception catching when, for example, I tried to read an object when an array was found or integer when a String was found. Not very elegant, but it did find the solution in under a second.

(click to show/hide)

That is more or less what I did. The python stock json parser provides a list of objects. I wrote a recursive function that would test the type of the object it had been given. If it was an int it would return that value, if a list it would call itself on each element of the list, adding the values up and returning those, and likewise for an object - first check to see if it has a value of 'red' and return 0 if so, else iterate through the values and call the function on each one, adding the result.

[David Martin]

Day 7

(click to show/hide)

Oaky - That's exactly what I experienced - on the fly calculation never completed, but caching the results as they propagate through the network gave the answer in a fraction of a second. I'm not sure why it appears to get stuck without caching as the instructions claim that any one wire only ever feeds into one other and there cannot be any loops otherwise it would never be solved even with caching.

I do love the elegance of recursion, but hate having to debug things when recursion behaves unexpectedly.

(click to show/hide)

On the fly calculation becomes exponential.
A cache for the instructions for each node works (hash/dictionary with the target as the key) and a hash to contain the value of each node.
Then a recursive function (I seem to like those) that when called with a node name, retrieves the instructions for that node name and calculates them from the cached values. If there were no cached value for a node  then it calls itself on the missing value node name to retrieve the value. And so it propagates and runs in a very short time.

[Oaky]

yay! finally up to date (well, at least until the next puzzle is released at 5 a.m  ).

[Oaky]

Finally found an answer to Day 12b (JSON parsing)

(click to show/hide)

Kludged the Processing JSON parser to work with the sample json file. Most parsers seem to be designed to work with a schema where you know what elements / objects / arrays to expect. Since this challenge involves navigating nested arrays and objects with a random structure and set of keys, I had to try for each type and do lots of exception catching when, for example, I tried to read an object when an array was found or integer when a String was found. Not very elegant, but it did find the solution in under a second.

(click to show/hide)

That is more or less what I did. The python stock json parser provides a list of objects. I wrote a recursive function that would test the type of the object it had been given. If it was an int it would return that value, if a list it would call itself on each element of the list, adding the values up and returning those, and likewise for an object - first check to see if it has a value of 'red' and return 0 if so, else iterate through the values and call the function on each one, adding the result.

(click to show/hide)

I also used the stock Python JSON parser with a recursive function for part (2).  (I sneaked part (1) using a regexp, but I wrote my json processor to handle part (1) as well).

Instead of testing for type, I tried type-specific operations in carefully chosen order and handled the exceptions (following the "better to ask for forgiveness than permission" principle):-

Code: [Select]

def summing_walk(jsondata, part, depth):
    #print '>'*depth
    total = 0
    # is it a dict (object)?
    try:
        keys = jsondata.keys()
        # process values here to look for red
        process_this_one = True
        if part == 2:
            for i in keys:
                if jsondata[i] == 'red':
                    process_this_one = False
        if process_this_one:
            for i in keys:
                total += summing_walk(jsondata[i], part, depth + 1)
    except AttributeError:
        # OK this wasn't a dict
        # is it a list?
        try:
            jsondata.append('MNO')
            jsondata.pop() # remove it again if we succeeded
            # process list
            for i in jsondata:
                total += summing_walk(i, part, depth + 1)
        except AttributeError:
            # not a list either - must be string (ignore)
            # or int (add to total)
            try:
                total += jsondata
            except TypeError:
                # it was a string
                pass
    return total



[red marley]

Have just completed days 13 and 14, which seemed a bit easier than some of the earlier ones.

Day 13 (Table planning)

(click to show/hide)

Is pretty much the same as Day 9 (route planning), except it is a digraph (A->B not necessarily equal to B->A). Part B was a trivially simple addition of an extra row and column of zeros to the edge matrix.

[David Martin]

Have just completed days 13 and 14, which seemed a bit easier than some of the earlier ones.

Day 13 (Table planning)

(click to show/hide)

Is pretty much the same as Day 9 (route planning), except it is a digraph (A->B not necessarily equal to B->A). Part B was a trivially simple addition of an extra row and column of zeros to the edge matrix.

I had a search for a more elegant way than my brute force approach but couldn't find a suitable one. My matrix math is not up to it and your graph theory is probably far better than mine.

[David Martin]

Really not happy with my solution to day 15.

(click to show/hide)

It looked initially like a linear algebra puzzle which should be solvable with matrices, except that the score is a product of the terms with a floor function. So I was stuck on an elegant solution as my matrix fu only goes so far.
generated 10 million random matrices for the ingredient proportions, did matrix multiplication of the ingredients to get a score matrix which I could then apply the pmax function to row wise and then calculate the final cumulative product for each row. Then select the max of those. Repeat several times till I got a candidate best.
Sample the space around the best candidate to check it was a maximum. That gave a heuristic answer for part a which was correct.
Simple matrix multiplication to get the calories for each recipe, then select the max score where calories==500 (my target). That heuristic also worked.

Why don't I like it? Because it doesn't guarantee to give the right answer. I may just be lucky (but the more I try the luckier I get )

[red marley]

Day 15:

(click to show/hide)

I thought this would make a good linear programming problem initially, but opted for a procedural approach in the end. But surely you don't need so many random matrices? For 4 ingredients together summing to 100 units, there are only 156849 possible combinations. This can be found iteratively:

for (a=1 TO 100)
  for (b=1 TO 100-a)
    for (c=1 TO 100-a-b)

or recursively (which makes it easier to generalise to any number of ingredients and any total, permute(4,100) used for this challenge):

array spoons[numberOfIngredients]

permute(spoonsToFind, total)
  if (spoonsToFind==1)
    spoons[0] = total   // Set of proportions found.
    return
 
  for  (i=1 TO total-spoonsToFind)
      spoons[spoonsToFind-1] = i     
      permute(spoonsToFind-1, total-i)

[David Martin]

You are correct - I was doing it in a bit of a rush between invigilation and marking.. Only 300 more scripts to go before then end of term.

[Oaky]

(click to show/hide)

I took the same iterative approach as jo spelled out (except that I initially forgot the last parameter was completely constrained, and still searched the range all the way up to the value it finally had to have.    This actually got the correct aswer for part 1.  I only noticed it when running part 2 - I got the wrong answer then noticed that my ingredients added up to less than 100 spoons. d'oh!

I wondered for a while how best to add the calorie constraint into it, but decided that just having my score function return 0 for cookies which didn't have 500 calories would be quickest.

It was only while reading jo's spoiler above that I realised that my permutation generator was set up specifically for 4 ingredients which sent me scurrying back to the code to try to work out how it still managed to get the correct answer for the example case with two ingredients.

[Pingu]

Day 9a done eventually followed by 9b two minutes later.

[David Martin]

(click to show/hide)

I wondered for a while how best to add the calorie constraint into it, but decided that just having my score function return 0 for cookies which didn't have 500 calories would be quickest.

(click to show/hide)

I recognised a nice matrix based problem so set my ingredients up as a 5x4 matrix, then calculating the scores for each combination was a matrix multiplication of all permutations (as an n*4 matrix) with the ingredient parameters (except calories) to give an n*4 matrix of total parameter scores for each permutation. Applying a row wise function (set every value below 0 to 0, then multiply the row) gave me a n*1 matrix in which it is trivial to find the max value. Having this as a base I could then do the same multiplication as previously but calculate the calories by multiplying the permutation with the fifth column. Then filter the scores by calories==500 and take the max. That was actually a few seconds work to do the extension.

[Pingu]

Day 10 done. What a contrast with day 9.

[red marley]

Day 16

(click to show/hide)

A fairly straightforward challenge this one - filtering a list based on a subset of attributes.

According to Eric Wastl (the Advent of Code author), today was the last of the "easy" ones.

[Oaky]

Day 16

(click to show/hide)

A fairly straightforward challenge this one - filtering a list based on a subset of attributes.

According to Eric Wastl (the Advent of Code author), today was the last of the "easy" ones.

(click to show/hide)

I anticipated the change in the comparison while coding for part1, so had already written my Sue class's match method to accept a comparison function as a parameter.  I hadn't anticipated a type-dependent one though, so had to add an argument to pass in the type to the comparison function.

Of course,  I'd written it in such a way that I couldn't immediately decide whether my func shoudl use less or greater than in each of the two given cases!  Carefully tracing an example through the function (and through a few "not"s) decided it in the end.

[David Martin]

(click to show/hide)

I parsed it as I read it in with a set of rejection criteria. If it passed those it got added to my list of possible sues.
This should end up with just one entry (which it did).

Today was very easy. I dread tomorrow.

[red marley]

David, that's a more elegant approach than mine. My instinct tends towards 'grab all the data and structure it, then start processing'. I think this comes from my usual need to visualise data. But it makes much more sense in this context to follow your approach.

As with almost all of the puzzles so far, in practice the data volumes involved mean that inefficient storage or processing hungry algorithms can be tolerated. I suspect this will change from the 17th onwards.

I am trying to resist the temptation to come up with a speedy answer early in the morning to get posted on the leader board (mostly because I am not speedy enough). But I do wonder whether anyone is going to be spending an antisocial Christmas morning coding in order to make it to the head of the final leader board (I certainly won't be).

[David Martin]

Only if you can get up early enough

Your line of work is based around visualising all the data - a lot of mine is stream parsing and quality filtering. I took the view that filtering out what I didn't want and seeing what was left would be the easier option.

Anyhow, tomorrow will be a toss up between marking stats reports, planning next semester's course (don't ask why it is so late) and doing the Advent of Code.

Being less than elegant I hard-coded the parse rules.

(click to show/hide)

Code: [Select]

ifh=open('input.txt')
mysue={
'children': 3,
'cats': 7,
'samoyeds': 2,
'pomeranians': 3,
'akitas': 0,
'vizslas': 0,
'goldfish': 5,
'trees': 3,
'cars': 2,
'perfumes': 1
}

sues=[]
for line in ifh.readlines():
    try:
        f=line.strip().split()
        thissue={f[2][:-1]:int(f[3][:-1]),f[4][:-1]:int(f[5][:-1]),f[6][:-1]:int(f[7])}
        wrongsue=True
        for k in thissue.keys():
            if k=='cats' or k=='trees':
                if mysue[k]>=thissue[k]:
                    wrongsue=False
            elif k in ('pomeranians', 'goldfish'):
                if mysue[k]<=thissue[k]:
                    wrongsue=False
            else:   
                if mysue[k]!=thissue[k]:
                    wrongsue=False
        thissue[f[0]]=int(f[1][:-1])
        if wrongsue:
            sues.append(thissue)
    except:
        print(line)       

The check the value of sues at the end.

[David Martin]

Day 17 required some thought but very few lines of code.

(click to show/hide)

It is a simple branch and bound algorithm so you don't enumerate every possibility, only those that have the potential to have a correct solution.

[Oaky]

Day 17 required some thought but very few lines of code.

(click to show/hide)

It is a simple branch and bound algorithm so you don't enumerate every possibility, only those that have the potential to have a correct solution.

(click to show/hide)

A quick back of the envelope calc told me that brute force and ignorance would probably be fine, so I simply counted up from 1, turning that into a bitmask of the same length as the list.  I applied the mask to the list of inputs, throwing away any combinations that didn't sum to the total.

[David Martin]

That was one option. I just happen to like recursion. It took a few seconds to ru, if that. (longer to write than to run).

[Feanor]

Elegant as it is, you need to be careful with recursion because every time you re-enter a subroutine, the previous context is pushed onto the stack.

The stack will build and build as you recurse down, and only when (if!) you reach the bottom of the rabbit-hole and start returning do you begin to pop stuff off the stack.

So unless you know there's a limit on how deeply you will be recursing, you run a risk of stack overflow.
It's a fairly small risk with modern OSes, as the stack allocation is usually quite generous, but it is a limit to be aware of.

[David Martin]

In this case the recursion limit is the tree depth which is the length of the list. So not a problem. If it was an optimisation I'd have some convergence criteria.