Another good problem for Rust. Because my stated goal is learning the Rust library better I'm doing it all in a text editor without an IDE, which forces you to read the docs rather than rely on autocomplete. I feel I'm writing more code between doc searches now, which is great!
I'm a Staff Software Engineer at Cisco. I specialize in Python and Go, building functional, practical, and maintainable web systems leveraging Kubernetes and the cloud. Blog opinions are my own.
It's neat and it passed the tests and got the right answer for me, but I'm not convinced it's totally correct for all input data. I'm sure there are cases it could miss by inching the end forward too far before moving the start.
Because of the contiguous set limitation, it always works. You can't ever go down in value by moving the right end, and you can't ever go up in value by moving the left end.
Ah, this one lead to a nice relaxing day :-) Nothing fancy in my Haskell implementation, but fine all the same. Relies heavely on lazyness to avoid over production, but if the feature exists why not use it...
-- helper function to generate tuple perms of a list and pass to a functionperms::Eqt=>(t->t->a)->[t]->[a]permsfxs=[fxy|(x:ys)<-tails(nubxs),y<-ys]-- asserts if a number is XMAS encrypted correctlyvalid::[Int]->Int->Int->(Bool,Int)validisli=letps=map(\(_,_,z)->z)$perms(\xy->(x,y,x+y))(takelis)n=is!!iin(n`elem`ps,n)-- checks, for a given header length, that each input is valid check::Int->[Int]->[(Bool,Int)]checklis|lengthis<=l+1=[]|otherwise=validisll:checkl(tailis)-- find the first input that is not valid with respec to XMAS encryption task1::Int->[Int]->Inttask1l=snd.head.filter(not.fst).checkl-- find the a contiguous sequence whose sum is equal to the input (calulated by task1) and-- sum the smallest and largest number in that sequencetask2::Int->[Int]->Inttask2n=(\xs->headxs+lastxs).snd.head.filter((n==).fst).map(\xs->(sumxs,sortxs)).filter((>1).length).(:)[].filter(not.null).concatMaptails.initsmain=doxs<-readFile"day9_input"<&>lines<&>fmap(read::String->Int)letx=task125xsprintxprint(task2xxs)
I'm a Staff Software Engineer at Cisco. I specialize in Python and Go, building functional, practical, and maintainable web systems leveraging Kubernetes and the cloud. Blog opinions are my own.
Had some extra time tonight so I got ahead of the curve. The time complexity isn't great, with the loops being a nasty hairy mess, but it works fine :)
#include "Day9.h"
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include "parsing.h"
/// Day 9: Encoding Error/// /// Find the number that can't be made by a combination of the numbers/// preceding it.#define MAX_NUMBER_STRING_SIZE 16
/// Parse the input file into a list of integers, one per line.int*parse(constchar*filename,int*count){FILE*fp;fp=fopen(filename,"r");if(fp==NULL){printf("Couldn't open file.\n");exit(EXIT_FAILURE);}*count=count_lines(fp);int*numbers=(int*)malloc(sizeof(int)**count);for(inti=0;i<*count;i++){charbuf[MAX_NUMBER_STRING_SIZE]={0};fgets(buf,MAX_NUMBER_STRING_SIZE,fp);numbers[i]=atoi(buf);}fclose(fp);returnnumbers;}/// Decides if a number is a 'valid number,' i.e. there is some/// combination of two numbers in the preceding 'preamble_length' /// numbers that add up to it.boolvalid_number(int*numbers,inti,intpreamble_length){// Add each pair of numbers in the preceding 'preamble_length' #'s// If there's any pair that add up to the i'th number, it's valid.for(intj=0;j<preamble_length;j++){for(intk=j+1;k<preamble_length;k++){if(numbers[i-preamble_length+j]+numbers[i-preamble_length+k]==numbers[i]){returntrue;}}}returnfalse;}/// Find the one number that isn't 'valid' per the above definition.intpart1(constchar*filename,intpreamble_length){intcount=0;int*numbers=parse(filename,&count);for(inti=preamble_length;i<count;i++){if(!valid_number(numbers,i,preamble_length)){returnnumbers[i];}}return-1;}/// There is a set of contiguous numbers, two or greater in length,/// that, when added up, equal the invalid number from part 1./// Return the minimum number in that set + the max in that set.intpart2(constchar*filename,intpreamble_length){intcount=0;int*numbers=parse(filename,&count);intinvalid_target=part1(filename,preamble_length);// Check each size from 2 all the way up to all of the numbersfor(intsize=2;size<=count;size++){// At each size, shift the window from front to back, one by one.for(inti=0;i+size-1<count;i++){// Add up that window of numbers and see if it matchesinttotal=0;for(intj=0;j<size;j++){total+=numbers[i+j];}// If it matches, find the min and max values in that window// and return their sum.if(total==invalid_target){intmin=INT_MAX;intmax=0;// Simultaneously find the min and max in the range.for(intj=0;j<size;j++){if(numbers[i+j]>max)max=numbers[i+j];if(numbers[i+j]<min)min=numbers[i+j];}returnmin+max;}}}return-1;}/// Run both partsintday9(){printf("====== Day 9 ======\n");printf("Part 1: %d\n",part1("data/day9.txt",25));printf("Part 2: %d\n",part2("data/day9.txt",25));returnEXIT_SUCCESS;}
Today was the first day we got different params for the sample solution, so I had to think about how to make that work with my puzzle runner. I don't love the solution, but it works. Thinking I might do a quick post on the runner, not sure if that would interest anyone...
Overall this was a fun little exercise, not super challenging, though I did have a harder time trying to condense the code for this solution. Not something I typically do day-to-day, but it's a code challenge, not production code 🥳
Anyway, here's my solution for the day
Part1
publicclassPart1:Puzzle<long[],long>{publicoverridelongSampleAnswer=>127;protectedintpreamble=25;publicoverridelong[]ParseInput(stringrawInput)=>rawInput.Split(Environment.NewLine).Where(line=>line.Length>0).Select(line=>long.Parse(line)).ToArray();publicoverridelongSolve(long[]input)=>FindInvalidNumber(input)??thrownewSystem.Exception("Result not found!");publicoverrideboolValidateSample(long[]input){// First time we hit a sample with different params as the solution.preamble=5;returnbase.ValidateSample(input);}protectedlong?FindInvalidNumber(long[]input){for(inti=preamble;i<input.Length;i++){varwindow=input[(i-preamble)..(i)];if(TargetSumExistsInWindow(input[i],window)==false){returninput[i];}}returnnull;// not found}privateboolTargetSumExistsInWindow(longtarget,long[]window){boolfound=false;for(varj=0;j<window.Length;j++){// Bail early. One half of the sum is already greater than the result.if(window[j]>target){continue;}// If already true, don't set back to false.found=window.Any(x=>x!=window[j]&&x+window[j]==target)||found;}returnfound;}}
Part 2
publicclassPart2:Part1{publicoverridelongSampleAnswer=>62;publicoverridelongSolve(long[]input){varinvalidNumber=FindInvalidNumber(input)??thrownewSystem.Exception("Result not found!");varrange=FindRangeSummingTo(invalidNumber,input)??thrownewSystem.Exception("Result not found!");returnrange!.Start+range!.End;}(longStart,longEnd)?FindRangeSummingTo(longtarget,long[]input){for(vari=0;i<input.Length;i++){longsum=0;for(varj=i;j<input.Length;j++){if((sum+=input[j])==target){return(input[i..j].Min(),input[i..j].Max());}if(sum>target){break;};}}returnnull;}}
Python, should be a reasonably efficient way of doing it although in part 2 it may be better to test the longer sequences first as there are fewer of them.
fromcollectionsimportdequedefpair_is_summable_to(n,iterable):seen=set()forxiniterable:target=n-xiftargetinseen:returnTrueseen.add(x)returnFalsedefpart1(lines,preamble_len=25):queue=deque(lines[:preamble_len],preamble_len)fori,ninenumerate(lines[preamble_len:]):ifpair_is_summable_to(n,queue):queue.append(n)else:returnn,idefpart2(target_weakness,lines):# test all contiguous sets of length 2 then all of length 3 etc
fortest_leninrange(2,len(lines)):queue=deque(lines[:test_len],test_len)forposinrange(test_len,len(lines)):ifsum(queue)==target_weakness:w_0=min(queue)w_1=max(queue)returnw_0+w_1,test_len,poselse:queue.append(lines[pos])lines=[int(l.strip())forlinopen('input.txt','r')]target_weakness,at_row=part1(lines)print(f"Part 1: result is {target_weakness} which is at line {at_row}")weakness,seq_len,at_row=part2(target_weakness,lines)print(f"Part 2: result is {weakness} from a sequence of length {seq_len} ending at row {at_row}")
usingSystem;usingSystem.Collections.Generic;usingSystem.Diagnostics;usingSystem.IO;usingSystem.Linq;usingSystem.Text;namespaceAdventOfCode2020{staticclassDay9{//Declaring numberToConsider so it can easily be changed when testingstaticintnumberToConsider=25;staticList<long>input;staticintfirstposition=numberToConsider;staticlongfaultingNumber;publicstaticvoidExecute(){input=File.ReadAllLines("//input").Select(r=>long.Parse(r)).ToList();//Added a imer just for funvartimer=newStopwatch();timer.Start();while(true){faultingNumber=input[firstposition];if(!SumFound(faultingNumber,firstposition))break;firstposition++;}//Part 2:varanswerPart2=FindSumUpToAnswer();timer.Stop();Console.WriteLine($"Part1 answer: {faultingNumber}");Console.WriteLine($"Part2 answer: {answerPart2}");Console.WriteLine($"Executed in: {timer.ElapsedMilliseconds} milliseconds");}privatestaticlongFindSumUpToAnswer(){firstposition=0;varsecondPosition=1;while(true){varlistToCheck=input.GetRange(firstposition,secondPosition-firstposition);varrangeResult=listToCheck.Sum();if(rangeResult==faultingNumber){returnlistToCheck.Min()+listToCheck.Max();}//By adding to either the first or second position a window is created and results are re-used instead of creating a new list every timeif(rangeResult<faultingNumber)secondPosition++;elsefirstposition++;}}privatestaticboolSumFound(longnextNumberToCheck,intposition){varworkingList=input.Skip(position-numberToConsider).Take(numberToConsider).ToList();workingList.Sort();for(inti=0;i<numberToConsider-1;i++){varvalueNeeded=nextNumberToCheck-workingList[i];varresult=workingList.BinarySearch(valueNeeded);if(result>=0)returntrue;}returnfalse;}}}
I started out with isize because I just knew that the second half would add negative numbers somehow. Then it didn't. :/
I got part 1 done rather quickly comparatively. I then spent far to long arguing with the rust compiler over lifetimes of slices and the ability to sum on borrowed vs. non-borrowed values.
Ultimately I moved into using a more C-style for-loop driven solution, where we walk down the entry vector until we're too big, and then step down to the next item.
Didn't get the elegant interator-driven solution, but meh - a win's a win. :)
Another good problem for Rust. Because my stated goal is learning the Rust library better I'm doing it all in a text editor without an IDE, which forces you to read the docs rather than rely on autocomplete. I feel I'm writing more code between doc searches now, which is great!
I like your sort of “inchworm” approach to part 2!
It's neat and it passed the tests and got the right answer for me, but I'm not convinced it's totally correct for all input data. I'm sure there are cases it could miss by inching the end forward too far before moving the start.
Because of the contiguous set limitation, it always works. You can't ever go down in value by moving the right end, and you can't ever go up in value by moving the left end.
It's the right approach.
This is the first day I did not OOP it up, because I felt lazy. Part 2 is still nicely linear, but didn't bother to optimise Part 1. Here's Ruby:
Ah, this one lead to a nice relaxing day :-) Nothing fancy in my Haskell implementation, but fine all the same. Relies heavely on lazyness to avoid over production, but if the feature exists why not use it...
This one seemed simple to me. Basic dynamic programming.
More javascript. Still can't see a regex solution. Part 2 contains part 1, so I'll just post that:
Had some extra time tonight so I got ahead of the curve. The time complexity isn't great, with the loops being a nasty hairy mess, but it works fine :)
Today was the first day we got different params for the sample solution, so I had to think about how to make that work with my puzzle runner. I don't love the solution, but it works. Thinking I might do a quick post on the runner, not sure if that would interest anyone...
Overall this was a fun little exercise, not super challenging, though I did have a harder time trying to condense the code for this solution. Not something I typically do day-to-day, but it's a code challenge, not production code 🥳
Anyway, here's my solution for the day
Part1
Part 2
Python, should be a reasonably efficient way of doing it although in part 2 it may be better to test the longer sequences first as there are fewer of them.
C# solution.
Top 3 love rank:
`
+1 Rust solution.
I started out with isize because I just knew that the second half would add negative numbers somehow. Then it didn't. :/
I got part 1 done rather quickly comparatively. I then spent far to long arguing with the rust compiler over lifetimes of slices and the ability to sum on borrowed vs. non-borrowed values.
Ultimately I moved into using a more C-style for-loop driven solution, where we walk down the entry vector until we're too big, and then step down to the next item.
Didn't get the elegant interator-driven solution, but meh - a win's a win. :)
As always, on Github.
My Javascript walkthrough: