Advent of Code 2018 - 25x2 coding puzzles for December

Culture
, ,
21

I was the other way around.

Part 1 took me forever, mostly because i forgot to reset my letter counters after each row. (There can’t really only be six of one and five of the other, surely.)


$input="snip";
$inputArray = $input -split '\r\n';
$numRows = $inputArray.Count;
$countTwos = 0;
$countThrees = 0;
$checksum=0;
$countArray=(('a',0),('b',0),('c',0),('d',0),('e',0),('f',0),('g',0),('h',0),('i',0),('j',0),('k',0),('l',0),('m',0),('n',0),('o',0),('p',0),('q',0),('r',0),('s',0),('t',0),('u',0),('v',0),('w',0),('x',0),('y',0),('z',0))
$strLen=0;

for ($i=0;$i -lt $numRows;$i++) {
  for ($k=0;$k -lt 26;$k++) {
    $countArray[$k][1]=0;
  
  }
  $hasTwos=0;
  $hasThrees=0;
  $ID=$inputArray[$i]
  $strLen=$ID.length;
  for ($j=0;$j -lt $strLen;$j++) {
    $char = $ID[$j];
    for ($k=0;$k -lt 26;$k++) {
      if ($char -eq $countArray[$k][0]) {
        $countArray[$k][1]++;
      }  
    }
  }
  for ($k=0;$k -lt 26;$k++) {
    if (2 -eq $countArray[$k][1]) {
      $hasTwos=1;
    }  
    elseif (3 -eq $countArray[$k][1]) {
      $hasThrees=1;
    }
  }
  $countTwos+=$hasTwos;
  $countThrees+=$hasThrees;
}
$checksum=$countTwos*$countThrees;
Write-Output $checksum;

Whereas Part 2 was remarkably easy (although, again, I had problems with resetting counters: this time putting the reset inside the wrong loop rather than forgetting it entirely).


$input="snip";
$inputArray = $input -split '\r\n';
$numRows = $inputArray.Count;
$strLen=0;

for ($i=0;$i -lt $numRows;$i++) {
  $ID1=$inputArray[$i];
  $strLen=$ID1.length;
  for ($j=$i+1;$j -lt $numRows;$j++) {
    $countDiff = 0;
    $ID2 = $inputArray[$j];
    for ($k=0;$k -lt $strLen;$k++) {
      if ($ID1[$k] -ne $ID2[$k]) {
        $countDiff++;
      }
    }
    if ($countDiff -eq 1){break;}
  }
  if ($countDiff -eq 1){break;}
}
Write-Output $ID1;
Write-Output $ID2;
2 Likes
22

I think the main thing that was messing me up with part 2 was not realizing at first I didn’t have to walk the entire list every time - I could start from the next row and ignore everything that came before. It’s possible this was called out and I just missed it.

Even though I’m a developer by trade, I’m not classically trained (I’m mostly self-taught and don’t have a CS degree). Algorithms have never been a strong suit of mine. Against all odds I’ve managed to work around this limitation and be successful, but I admit it’s a weakness.

That’s part of why I’m doing these exercises - to bone up on some of these fundamentals since these are muscles I don’t work very often.

3 Likes
23

Day 2:
I did part 1 relatively quickly…


@input = split("\n", "INPUT HERE");

my ($two, $three) = (0,0);

foreach my $i (@input) {
        my %counts;
        my @letters = split(//, $i);

        foreach my $letter (@letters) { $counts{$letter}++; }

        if(grep {$counts{$_} == 2} keys %counts) { $two++; }
        if(grep {$counts{$_} == 3} keys %counts) { $three++; }
}

print $two * $three;

Then I hit part 2, said “crap”, wiped out my code for part 1, thought of a few clever ways to do part 2 that ultimately I couldn’t figure out how to make them work, and finally just brute forced the thing with a tried-and-true pattern.


@input = split("\n", "INPUT HERE");

for(my $current = 0; $current <= $#input; $current++) {
        for(my $compare = 0; $compare <= $#input; $compare++) {

                my @left = split(//, $input[$current]);
                my @right = split(//, $input[$compare]);
                my $diff = 0;
                my $result = "";

                for(my $test = 0; $test <= $#left; $test++) {
                        if($left[$test] ne $right[$test]) { $diff++; }
                        else                              { $result .= $left[$test]; };
                }

                if($diff == 1) {
                        print $result;
                        exit;
                }
        }
}

I did go back and re-do my solution of part 2 for day 1 down to 8 lines (not counting the input). I’m not proud of the main trick I used to shrink it (using a side-effect of uninitialized hash values and ++), though I’m sure there’s other dirty tricks that could make it smaller…


my @input = split("\n", "INPUT HERE");

my ($result, $current) = (0,0);
my %freqs;

while (! ($freqs{$result}++)) {
        if($input[$current] =~ /^[+-]\d+$/) { $result+= eval($input[$current]) };
        ($current == $#input)? $current = 0 : $current++;
}

print $result;
1 Like
24

Some of the solutions on Reddit were pretty mind-blowing. Especially the requisite, “here’s a regex that solves it in one line” style responses.

3 Likes
25

Yeah, mine are generally just brute force, solving them in the most straightforward way possible.

3 Likes
26

I set up two accounts, one for my work, and one for here, since you can only be connected to a single private leaderboard. I just went in to enter my answers for the work account and discovered that each player has a unique input file. Fascinating.

4 Likes
27

Yep. Makes sense: it verifies that you at least have access to a program that can compute the answer, not just to a list of answers.

You can still copy someone else’s work, but not as trivially.

2 Likes
28

It’s a good idea to rig up a way to load your input in separately, anyways. The problems tend to include a short amount of example data, and if you can easily swap inputs out then you can use the example to get a quick sanity check if you’re trying to troubleshoot a problem.

I actually ended up losing a fair bit of time this morning on day 3’s problem because vi decided to be “helpful” and double-up on “#” marks when I pasted in data, and I didn’t even notice until I realized my code wasn’t giving me anything useful.

1 Like
29

I’ve been writing unit tests to verify my logic as I go. I create assertions for each of the sample data they show, and then just print out the result for the official input, which I’ve been loading from a file at runtime.

1 Like
30

I didn’t have much problem with either riddle today.
Part 1:


$input="???";

$array = New-Object 'object[,]' 1000,1000;
$inputArray = $input -split '\r\n';
$numRows = $inputArray.Count;
$strLen=0;
$countOLap=0;
for ($i=0;$i -lt 1000;$i++) {
  for ($j=0;$j -lt 1000;$j++) {
    $array.SetValue(0,$i,$j);
  }
}

for ($i=0;$i -lt $numRows;$i++) {
  $instance = $inputArray[$i] -split '[#| @ |,|: |x]';
  $x1=([int]::Parse($instance[4]));
  $x2=$x1+([int]::Parse($instance[7]));
  $y1=([int]::Parse($instance[5]));
  $y2=$y1+([int]::Parse($instance[8]));

  for ($j=$x1;$j -lt $x2;$j++){
    for ($k=$y1;$k -lt $y2;$k++){
      $array.SetValue($array.getValue($j,$k)+1,$j,$k);
    }
  }
}
for ($i=0;$i -lt 1000;$i++) {
  for ($j=0;$j -lt 1000;$j++) {
    if ($array.getValue($i,$j) -gt 1){
      $countOLap++;
    }
  }
}
Write-Output $countOLap;

I mean, I’d have to look into RegExes a little further to figure out why 1, 4, 5, 7, and 8, but I figured on not being able to figure that out, and, hey, so long as it’s consistent from line to line.

Part 2 was just a matter of changing what I was looking for after Part 1, and hey, I already have a loop set up to iterate through those! So that wasn’t hard either.

Part 2:


$input="???";

$array = New-Object 'object[,]' 1000,1000;
$inputArray = $input -split '\r\n';
$numRows = $inputArray.Count;
$strLen=0;
$currClaim=0;
for ($i=0;$i -lt 1000;$i++) {
  for ($j=0;$j -lt 1000;$j++) {
    $array.SetValue(0,$i,$j);
  }
}

for ($i=0;$i -lt $numRows;$i++) {
  $instance = $inputArray[$i] -split '[#| @ |,|: |x]';
  $x1=([int]::Parse($instance[4]));
  $x2=$x1+([int]::Parse($instance[7]));
  $y1=([int]::Parse($instance[5]));
  $y2=$y1+([int]::Parse($instance[8]));
  for ($j=$x1;$j -lt $x2;$j++){
    for ($k=$y1;$k -lt $y2;$k++){
      $array.SetValue($array.getValue($j,$k)+1,$j,$k);
    }
  }
}
for ($i=0;$i -lt $numRows;$i++) {
  $instance = $inputArray[$i] -split '[#| @ |,|: |x]';
  $x1=([int]::Parse($instance[4]));
  $x2=$x1+([int]::Parse($instance[7]));
  $y1=([int]::Parse($instance[5]));
  $y2=$y1+([int]::Parse($instance[8]));
  $currClaim=$instance[1];
  $overlap=0;
  for ($j=$x1;$j -lt $x2;$j++){
    for ($k=$y1;$k -lt $y2;$k++){
      if($array.getValue($j,$k) -gt 1){
        $overlap++;
        break;
      }
    if($overlap -gt 0) {break;}
    }
  }
  if($overlap -eq 0) {break;}
}
Write-Output $currClaim;
31

I’ve put my solutions up on Gitlab:

3 Likes
32

Either I was incredibly tired this morning or day 4 was worded very confusingly (or both…). I had to read and re-read it a number of times just to figure out what was needed, and ended up doing part of part 1 manually because I just wasn’t wrapping my mind around the task.

And the randomly-ordered input seemed more like filler to throw in an extra simple-yet-annoying step.

2 Likes
33

Yeah, agreed. Most of my problems from Day 4 were from reading comprehension fails.

In Step 1, I completely missed that every sleeping period would be between 00:00 and 01:00 on the same day, so I put in extra logic to handle all 24 hours, even if the sleeping period started on one day and ended on another. I could have vastly simplified it if I knew I could treat it as parse-and-subtract-integers.

I mean, I got it to work, in the end, but it would have saved me no end of hassle if I had just dropped all of the date-handling logic as unnecessary.

And then, in Step 2; I thought I was supposed to find the minute where guards were most often asleep, and then find the guard most likely to be asleep at that minute, rather than finding the guard/minute combination for sleep that was most frequent.

(This, I assume, is why I finished Part 1 before you did, but you beat me in finishing Part 2).

For Step 2, I basically ended up looping through each of the sixty minutes and outputting the worst guard and number of times asleep for each minute, and located the highest of those manually, because I was just all out of shits to give at that point.

1 Like
34

Yeah, I added extra logic myself, though mainly just a naive check to convert any hour difference to minutes.

I sorta did the reverse of you, it sounds like. For step 1, since I had so much trouble working out the end goal, I collated the log info for each guard and their totals, and then manually found the answer from that. And lost a ton of time when I accidentally missed the highest total and tried answering from the guard with the second-highest multiple times before I finally caught the mistake.

Once I hit step 2 I’d finally worked out what was wanted. Since I was already saving way more information from the logs than needed I was able to just add in a running check/log for the desired maximum in the same loop that was parsing out each record. Ended up with a fair bit of completely unnecessary code and memory usage, but I just didn’t care by that point.

1 Like
35

I had a similar problem as @nimelennar on 1-2. My solution takes upwards of 3 minutes to run, but I can’t see why. If anyone has a few minutes to take a look, I’d appreciate some feedback.

It’s worth mentioning that the solution for 1-2 is contained in the method named find_frequency_match.

1 Like
36

That sounds about how long my final coded version ended up running for. If you’re being rigorous, and you have a thousand records, and find the result on the hundredth loop (ballparking it), you’re going to end up checking each new result against about a hundred thousand other results, about a hundred thousand times, halved (n*(n+1)/2).

That works out to about five billion checks, so three minutes doesn’t seem too ridiculous.

If you want to cheat to bring your run-time down, it isn’t too hard to figure out in which iteration of the loop you’re going to find the result, and just jump straight to that iteration.

1 Like
37

If you’re not too concerned about memory usage (which I definitely wasn’t), you can also use a hash/associative array/(I think that’s a “dictionary” in python) to avoid iteratively testing every entry, and just check whether the relevant entry exists or not. My perl answer using a hash runs in about two seconds. :sunglasses:

Or you could sort the array and do a binary search to limit the tests, but that seems like a lot more work than it’s worth.

3 Likes
38

No, no, no. You’re doing random inserts. If you want it sorted, you want a linked list or a binary tree (I’d lead towards a doubly-linked list, as you tend to be bouncing back-and-forth within a range of about 500 values before moving on).

2 Likes
39

See, though, if you have a language that doesn’t make it too difficult/expensive to insert into the middle of an array, doing the search for whether the value is in the array automatically gives you the insertion position to keep the array sorted and minimize the time of a binary search. Granted, you could do the same with a linked list, but the essence of what you’re doing is still similar.

Still easier to use a hash or similar construct, though. It’s sorta abusing their purpose, and if it weren’t a (relatively) limited number of small key values involved it might lead to a lot of memory usage, but…

1 Like
40

I’m running behind. Just finished Day 3. I found it incredibly frustrating, mostly because I kept screwing up my math and also I was having a hard time getting the kind of data structure I wanted in PowerShell. The really annoying thing is I knew exactly how I wanted to solve it pretty much from the beginning (since it’s a pretty typical “overlapping windows” type puzzle) but I just kept messing myself up and making dumb mistakes. But, I eventually figured it out. Once I got part 1 squared away, I was able to do part 2 in about 5 minutes.

Here’s my solution which incorporates both puzzles. I’m actually pretty pleased with how it turned out although the solution for #1 could be done in a more optimal manner. It was a pretty clever bit of shorthand I had never used before (thanks, SO).

Set-StrictMode -Version Latest
$input = '...' # Parse our input and extract the values we care about
$sr = [System.IO.StringReader]::new($input)
$map = [int[][]]::new(1001, 1001) # fabric map
$claimMap = [int[][]]::new(1001, 1001) # claim map (solution 2)
$overlaps = @{} # overlapping claims (solution 2)

while($null -ne ($v = $sr.ReadLine())) {
    # #1 @ 662,777: 18x27 == #<number> @ <left>,<top>: <height>x<width>
    $m = [regex]::Match($v, '^\#(\d+)\s+@\s+(\d+),(\d+):\s+(\d+)x(\d+)')
    $claim = [int]$m.Groups[1].Value
    $top = [int]$m.Groups[3].Value
    $left = [int]$m.Groups[2].Value
    $height = [int]$m.Groups[5].Value
    $width = [int]$m.Groups[4].Value

    Write-Verbose "$claim"
    $overlaps[$claim] = $false # initialize our claim for overlap checking (solution 2)
    for($x = $left; $x -lt $left + $width; $x++) {
        for($y = $top; $y -lt $top + $height; $y++) {
            $map[$x][$y] += 1 # increment our overlaps (solution 1)

            # Determine if the claim is already used or not (solution 2)
            if($claimMap[$x][$y] -gt 0) {
                $overlaps[$claimMap[$x][$y]] = $true
                $overlaps[$claim] = $true
            } else {
                $claimMap[$x][$y] = $claim
            }
        }
    }
}

Write-Host "Solution #1:" 
# This is some motherfucking sorcery here -- flatten the array and look for matches >= 2
((@($map | %{$_}) | where { $_ -ge 2 }) | measure).Count # solution 1

Write-Host "Solution #2:"
($overlaps.GetEnumerator() | where { $_.Value -eq $false }).Key # solution 2

Now on to day 4. Based on what others are saying it sounds like it’s going to be a doozie.

1 Like