Advent of Code
» >
» Goto page 1, 2  Next
» View previous topic :: View next topic  
flyingfisch posted this link in #omnimaga and I thought y'all might like it: http://adventofcode.com/

I'm going to try to do all of them on the right days, but I dunno if I'll have the time. Post your solutions to the problems in the thread. I'll update this post as I solve the puzzles

Instead of updating this post whenever I finish a new puzzle, I've put them all in a github repo: https://github.com/Ivoah/AdventofCode
https://ivoah.net
My Calcs: TI-86, TI SR-56, TI-Nspire CX CAS, TI-83+ SE
TI-84+ SE, TI-85, TI-73 Explorer VS, TI-84+ CSE, TI-89 Titanium
Since the problem is called "Not quite Lisp"
1:

Code:
#lang racket

(define (fold-str-int f i str)
  (sequence-fold f i (sequence-map char->integer (in-string str))))

(define (elevator str)
  (inexact->exact
   (* (fold-str-int
       (lambda (i c)
         (+ i (- c 40.5))) 0 str) -2)))

(define (disallow-basement str)
  (letrec
      ([make-counter
        (lambda ([count 0] [v 0])
          (lambda (c)
            (let
                ([v (+ v (- c 40.5))]
                 [count (+ 1 count)])
              (if (< 0 v)
                  (raise-user-error (~a count))
                  (make-counter count v)))))])
    (inexact->exact
     (* (fold-str-int (lambda (f c) (f c)) (make-counter 0 0) str) -2))))


[edit]
See Day 1 run here: http://pasterack.org/pastes/92103


And I did day 2 as well:

Code:
#lang racket
(define (foldl-small-sides f str)
  (foldl + 0
         (map
          (lambda (p)
            (let
                ([side-l (sort (map string->number (string-split p "x")) <)]
                 [perimeter (lambda (s) (* 2 (apply + (take s 2))))]
                 [area (lambda (s) (apply * (take s 2)))]
                 [volume (lambda (s) (apply * s))])
              (f side-l perimeter area volume)))
          (string-split str "\n"))))
 
(define (elf-paper str)
  (foldl-small-sides
   (lambda (side-l perimeter area volume)
     (+ (area side-l)
        (sequence-fold + 0 (sequence-map area (in-permutations side-l))))) str))
 
(define (elf-ribbon str)
  (foldl-small-sides
   (lambda (side-l perimeter area volume)
     (+ (perimeter side-l)
        (volume side-l))) str))


and Day 2 here: http://pasterack.org/pastes/11996
<- Please Support on Lego Ideas

Code:
import java.util.Scanner;
public class Day1 {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      System.out.print("Movements: ");
      String str = sc.next();
      int floor = 0;
      boolean first = true;
      for(int i = 0; i < str.length(); i++){
         if(str.substring(i,i+1).equals("("))
            floor++;
         else
            floor--;
         if(floor == -1 || first){
            System.out.println("First basement entry: " + i+1);
            first = false;
         }
      }
      System.out.println("Final floor: " + floor);
   }
}


I did Day 2 as well, but I didn't keep the first part.


Code:
import java.util.Scanner;
import java.util.Arrays;
import java.io.File;
import java.io.FileNotFoundException;
public class Day2 {
   public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      System.out.print("File path: ");
      try {
         String path = sc.next();
         System.out.println(path);
         Scanner fl = new Scanner(new File(path));
         int total = 0;
         while(fl.hasNext()){
            int[] dim = new int[3];
            String box = fl.next();
            int pos1 = box.indexOf("x");
            dim[0] = Integer.parseInt(box.substring(0,pos1));
            int pos2 = box.indexOf("x", pos1+1);
            dim[1] = Integer.parseInt(box.substring(pos1+1,pos2));
            dim[2] = Integer.parseInt(box.substring(pos2+1));
            System.out.println(Arrays.toString(dim));
            int[] perims = {2*(dim[0]+dim[1]), 2*(dim[0]+dim[2]), 2*(dim[1]+dim[2])};
            int min = Integer.MAX_VALUE;
            for(int per : perims){
               if(per < min)
                  min = per;
            }
            total += min + dim[0]*dim[1]*dim[2];
         }
         System.out.print("Total Length = " + total);
      } catch(FileNotFoundException e){
         System.out.print("Invalid file");
      }
   }
}
Scanner seems like overkill here, why not just pass your strings in via args?
<- Please Support on Lego Ideas
elfprince13 wrote:
Scanner seems like overkill here, why not just pass your strings in via args?


I could have done it that way, but is easier to use in my IDE with Scanner. Overall, I could have done things more efficiently, but it gets the right answer.

EDIT: Day 3 done. I'm on the leaderboard now!


Code:
import java.util.ArrayList;

public class Day3 {

    public static final int PART_NUMBER = 2;
    public static final String MOVES = "^^<<v/*. . .*/<<v>";

    public static void main(String[] args){
        ArrayList<Integer[]> visited = new ArrayList<Integer[]>();

        for(int j = 0; j < PART_NUMBER; j++){
            int x = 0;
            int y = 0;
            for(int i = j; i < MOVES.length(); i += PART_NUMBER){
                String temp = MOVES.substring(i,i+1);
                if(temp.equals("^"))
                    y++;
                else if(temp.equals("v"))
                    y--;
                else if(temp.equals("<"))
                    x--;
                else
                    x++;
                Integer[] p = new Integer[2];
                p[0] = x;
                p[1] = y;
                visited.add(p);
            }
        }
        for(int i = 0; i < visited.size(); i++){
            for(int j = 0; j < visited.size(); j++){
                if(i != j && visited.get(i)[0] == visited.get(j)[0] && visited.get(i)[1] == visited.get(j)[1]){
                    visited.remove(j);
                    j--;
                 }
             }
         }
         System.out.println(visited.size());
    }
}


DAY 4:

Code:
import java.security.*;
import java.io.*;
public class Day4{
    public static final String SECRET = "ckczppom"
                             , TARGET = "000000";
    public static void main(String[] args) throws NoSuchAlgorithmException, UnsupportedEncodingException{
        int n = 0;
        String temp;
        MessageDigest digest = MessageDigest.getInstance("MD5");
        do {
            byte[] hash = digest.digest((SECRET+(++n)).getBytes());
            temp = "";
            for (int i = 0; i < TARGET.length()/2+1; i++)
                temp += Integer.toString((hash[i] & 0xff) + 0x100, 16).substring(1);
        } while(!temp.startsWith(TARGET));
        System.out.println(n);
    }
}
I'm giving myself a challenge to do it as much with LINQ as possible, trying to limit it to a single 'line'. A line, in this case, can include anonymous methods, which may have multiple lines of code in them. This code is awful.

Assumed variable input holds the input in string format, assuming Environment.NewLine for new lines.

Day 1:
Part 1:

Code:
input.Select(c => c == '(' ? 1 : -1).Sum()

Part 2:

Code:
input.Select(c => c == '(' ? 1 : -1).TakeWhile((element, index) => input.Take(index).Select(c => c == '(' ? 1 : -1).Sum() >= 0).Count()


Day 2:
Part 1:

Code:
input.Split(new[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries).Select(s => s.Split('x').Select(i => int.Parse(i))).Select(i => i.ToArray()).Select(i => new[] { i[0] * i[1], i[1] * i[2], i[0] * i[2] }).Select(i => i.Min() + 2 * i.Sum()).Sum()

Part 2:

Code:
input.Split(new[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries).Select(s => s.Split('x').Select(i => int.Parse(i))).Select(i => i.OrderBy(j => j).ToArray()).Select(i => 2 * i[0] + 2 * i[1] + i.Aggregate((a, b) => a * b)).Sum()


Day 3:
I had to cheat here and use a second line, which was the declaration for the running total tuple.

Part 1:

Code:
var agg = Tuple.Create(0, 0); input.Select(i => { switch (i) { case '>': return Tuple.Create(0, 1); case '<': return Tuple.Create(0, -1); case '^': return Tuple.Create(1, 0); case 'v': return Tuple.Create(-1, 0); default: return Tuple.Create(0, 0); } }).Select(i => { agg = Tuple.Create(i.Item1 + agg.Item1, i.Item2 + agg.Item2); return agg; }).Distinct().Count() + 1

Part 2:

Code:
var agg = new List<Tuple<int, int>>(new[] { Tuple.Create(0, 0), Tuple.Create(0, 0) }); input.Select(i => { switch (i) { case '>': return Tuple.Create(0, 1); case '<': return Tuple.Create(0, -1); case '^': return Tuple.Create(1, 0); case 'v': return Tuple.Create(-1, 0); default: return Tuple.Create(0, 0); } }).Select((i, index) => { agg[index % 2] = Tuple.Create(i.Item1 + agg[index % 2].Item1, i.Item2 + agg[index % 2].Item2); return agg; }).SelectMany(i => i).Distinct().Count()
Shaun
Day 3 of my imprisonment in this hellscape of manufactured cheer. The Overlords have decreed that I shall write programs in Rust. I am not entirely pleased with the verbosity of my work, but it should still be quite efficient.

Code:
use std::collections::HashSet;
use std::io::Read;

fn main() {
    let mut s = String::new();
    let stdin = std::io::stdin();
    stdin.lock().read_to_string(&mut s).unwrap();

    let mut set = HashSet::new();
    part_one(&mut set, s.chars());
    println!("{}", set.len());

    println!("With robo-santa, {}", part_two(s.chars()));
}

fn part_one<I: IntoIterator<Item=char>>(s: &mut HashSet<(i32, i32)>, input: I) {
    let mut coords = (0i32, 0i32);

    s.insert(coords);
    for dir in input {
        let (x, y) = coords;
        coords = match dir {
            '<' => (x - 1, y),
            '>' => (x + 1, y),
            '^' => (x, y + 1),
            'v' => (x, y - 1),
            _ => (x, y)
        };

        s.insert(coords);
    }
}

fn part_two<I: Iterator<Item=char> + Clone>(input: I) -> usize {
    let mut s = HashSet::<(i32, i32)>::new();

    part_one(&mut s, input.clone().enumerate().filter_map(|(i, x)| {
        if i % 2 == 0 {
            Some(x)
        } else {
            None
        }
    }));

    part_one(&mut s, input.enumerate().filter_map(|(i, x)| {
        if i % 2 == 1 {
            Some(x)
        } else {
            None
        }
    }));

    s.len()
}


Day four, in which OpenSSL has fast hash implementations.

Code:
extern crate openssl;

use std::io::Write;
use openssl::crypto::hash::{Hasher, Type};

fn preimage<F, I>(prefix: &[u8], mut predicate: F, gen: I) -> Vec<u8>
    where F: FnMut(&[u8]) -> bool,
          I: IntoIterator<Item=Vec<u8>> {
    let mut h = Hasher::new(Type::MD5);
    h.write_all(prefix).unwrap();

    for suffix in gen {
        let mut hasher = h.clone();
        hasher.write(&suffix).unwrap();
        let digest = hasher.finish();

        if predicate(&digest) {
            return suffix;
        }
    }
    panic!("Exhausted suffix generator");
}

fn main() {
    const KEY: &'static [u8] = b"ololol";

    let suffix = preimage(KEY, |digest| {
        digest[..2] == [0, 0] && (digest[2] & 0xF0) == 0
    }, (0u32..).map(|x| x.to_string().into_bytes()));
    println!("5 zeroes: {}", String::from_utf8(suffix).unwrap());

    let suffix = preimage(KEY, |digest| {
        digest[..3] == [0, 0, 0]
    }, (0u32..).map(|x| x.to_string().into_bytes()));
    println!("6 zeroes: {}", String::from_utf8(suffix).unwrap());
}
タリ ·· Ask questions the smart way ·· digipres.club
Relevant to nothing in particular, for the MD5 challenge, you need to try an average of 16^6 = 16 million hashes before you find one where the first 6 hex digits are any particular given sequence. I'm very curious to try this on a calculator.
KermMartian wrote:
Relevant to nothing in particular, for the MD5 challenge, you need to try an average of 16^6 = 16 million hashes before you find one where the first 6 hex digits are any particular given sequence. I'm very curious to try this on a calculator.


Could the specialized MD5 hardware stuff be utilized to speed up computation?
https://ivoah.net
My Calcs: TI-86, TI SR-56, TI-Nspire CX CAS, TI-83+ SE
TI-84+ SE, TI-85, TI-73 Explorer VS, TI-84+ CSE, TI-89 Titanium
Ivoah wrote:
KermMartian wrote:
Relevant to nothing in particular, for the MD5 challenge, you need to try an average of 16^6 = 16 million hashes before you find one where the first 6 hex digits are any particular given sequence. I'm very curious to try this on a calculator.


Could the specialized MD5 hardware stuff be utilized to speed up computation?
indeed, that's what I was thinking. Using that hardware, I believe I could complete the challenge in a few hours of computation.
I decided days 3 and 4 should be in Scala. Perhaps unsurprisingly, they bear a lot of resemblance to Tari's Rust versions.

I spent a while on Day 3 trying to figure out if I could collapse the two collect calls into a single method that generates *two* streams lazily, but I didn't come up with anything good.

Code:

package net.cemetech.sfgp.advent
import scala.collection.GenTraversableOnce
import scala.collection.immutable.StringOps

object HouseGrid {
   def deliverSet(directions:GenTraversableOnce[Char]) = {
      val start = (0,0)
      directions.foldLeft((start, Set(start))){
         case((pos, set), char) =>
            val npos = char match {
               case '<' => (pos._1 -1, pos._2)
               case '>' => (pos._1 +1, pos._2)
               case 'v' => (pos._1, pos._2 -1)
               case '^' => (pos._1, pos._2 +1)
            }
            (npos, set + npos)
      }._2
   }
   
   def deliverPresents(directions:StringOps) = {
      deliverSet(directions).size
   }
   
   def splitSantas(dir:Seq[(Char,Int)]) = {
      (dir.collect{case(c,i) if i % 2 == 0 => c},dir.collect{case(c,i) if i % 2 == 1 => c})
   }   
   
   def deliverWithRobo(directions:StringOps) = {
      val santas = splitSantas(directions.view.zipWithIndex)
      (deliverSet(santas._1) ++ deliverSet(santas._2)).size
   }
   
   def main(args:Array[String]) = {
      Console.println(deliverPresents(">"))
      Console.println(deliverPresents("^>v<"))
      Console.println(deliverPresents("^v^v^v^v^v"))
      Console.println(deliverWithRobo("^v"))
      Console.println(deliverWithRobo("^>v<"))
      Console.println(deliverWithRobo("^v^v^v^v^v"))
   }
}


Day 4 was shockingly easy with MessageDigest:

Code:
package net.cemetech.sfgp.advent

object Coins {
   val hasher = java.security.MessageDigest.getInstance("MD5")
   def toHex(b:Array[Byte]) = {
      b.map("%02x".format(_)).mkString
   }
   
   def mine(matchPref:String)(key:String) = {
      val mLen = matchPref.length
      val hLen = (mLen / 2.0).ceil.intValue
      Iterator.from(1).dropWhile(p => !toHex(hasher.digest((key + p).getBytes).take(hLen)).take(mLen).equals(matchPref)).next
   }
   
   def main(args:Array[String]) = {
      val mine5 = mine("00000")_
      val mine6 = mine("000000")_
      Console.println(mine5("abcdef"))
      Console.println(mine5("pqrstuv"))
      Console.println(mine5("SECRET"))
      Console.println(mine6("SECRET"))
   }
}
<- Please Support on Lego Ideas
Day 4:
Part 1:

Code:
Enumerable.Range(0, int.MaxValue).FirstOrDefault(s => BitConverter.ToString(System.Security.Cryptography.MD5.Create().ComputeHash(Encoding.UTF8.GetBytes(input + s))).StartsWith("00-00-0"))


Part 2:

Code:
Enumerable.Range(0, int.MaxValue).FirstOrDefault(s => BitConverter.ToString(System.Security.Cryptography.MD5.Create().ComputeHash(Encoding.UTF8.GetBytes(input + s))).StartsWith("00-00-00"))


There are some things I could do to speed it up, but part 2 took less than a minute, so I'm not terribly worried about it.

EDIT: Decided to try to speed it up.
Initial run:

Code:

> Stopwatch s = new Stopwatch(); s.Start(); Enumerable.Range(0, int.MaxValue).FirstOrDefault(s => BitConverter.ToString(System.Security.Cryptography.MD5.Create().ComputeHash(Encoding.UTF8.GetBytes(input + s))).StartsWith("00-00-00")); s.Stop(); s.Elapsed
[00:00:47.9377014]


First things first, don't create a new md5 object each run through:

Code:
> Stopwatch s = new Stopwatch(); s.Start(); var md5 = System.Security.Cryptography.MD5.Create(); Enumerable.Range(0, int.MaxValue).FirstOrDefault(s => BitConverter.ToString(md5.ComputeHash(Encoding.UTF8.GetBytes(input + s))).StartsWith("00-00-00")); s.Stop(); s.Elapsed
[00:00:25.7084424]

That's a pretty good speed up already.

Next step, why even deal with strings:

Code:
Stopwatch s = new Stopwatch(); s.Start(); var md5 = System.Security.Cryptography.MD5.Create(); Enumerable.Range(0, int.MaxValue).FirstOrDefault(s => md5.ComputeHash(Encoding.UTF8.GetBytes(input + s)).TakeWhile(b => b == 0).Count() == 3); s.Stop(); s.Elapsed
[00:00:21.8899311]


That's a little better. I tried a few more things like making my own CountWhile() method, and computing just the first block of the hash, but nothing really seemed to help after this. My guess is I just need a faster MD5 hash implementation if I want to get much faster.
Shaun
I like PHP's shortness and efficiency for Day4 :

Code:
$i = 0;
while (strpos(md5('ckczppom' . ++$i), '00000') !== 0);
echo $i;


Runs in approximately less than .5 seconds for part 1 and about 7 seconds for part 2.

TI-Planet.org co-founder / co-admin
elfprince13 wrote:

I spent a while on Day 3 trying to figure out if I could collapse the two collect calls into a single method that generates *two* streams lazily, but I didn't come up with anything good.

Code:

   def splitSantas(dir:Seq[(Char,Int)]) = {
      (dir.collect{case(c,i) if i % 2 == 0 => c},dir.collect{case(c,i) if i % 2 == 1 => c})
   }   
   
   def deliverWithRobo(directions:StringOps) = {
      val santas = splitSantas(directions.view.zipWithIndex)
      (deliverSet(santas._1) ++ deliverSet(santas._2)).size
   }

I discovered groupBy and partition! Unfortunately, partition returns a tuple, which you can't easily iterate over (productIterator loses type safety, for obvious reasons), but groupBy is a generalized version of the same thing. splitSantas is no longer needed, and deliverWithRobo is now just one line. This code also generalizes easily to n robotic santas, all running in parallel, by making the % 2 a parameter.

Code:
   def deliverWithRobo(directions:StringOps) = {
      directions.zipWithIndex.groupBy(_._2 % 2).values.map(s=>deliverSet(s.map(_._1))).reduceLeft(_ union _).size
   }

We could probably add some views to make it more memory efficient, but as is, I'm pretty happy.

Also discovered that the view before zipWithIndex in my previous version wasn't helping anything, because zipWithIndex is apparently strict.
<- Please Support on Lego Ideas
Day five of my imprisonment. I fear the depths of "holiday cheer" were not meant to be plumbed by sane minds. Should I fail to return in condition to report what I have witnessed herein, I pray these notes will be sufficient to persuade future explorers of their folly in digging deeper than man was meant to go.

Code:
use std::io::BufRead;
use std::collections::HashMap;
use std::collections::hash_map::Entry::*;

static BAD_STRINGS: [&'static [u8]; 4] = [
    b"ab", b"cd", b"pq", b"xy"
];

fn main() {
    let (mut p1_count, mut p2_count) = (0, 0);

    let stdin = std::io::stdin();
    for line in stdin.lock().lines() {
        let line = line.unwrap();
        if part1(line.as_bytes()) {
            p1_count += 1;
        }
        if part2(line.as_bytes()) {
            p2_count += 1;
        }
    }

    println!("{}", p1_count);
    println!("{}", p2_count);
}

fn part1(input: &[u8]) -> bool {
    let n_vowels = input.iter().filter(|c| b"aeiou".contains(c)).count();
    let has_pair = input.windows(2).any(|s| s[0] == s[1]);
    let has_bad = input.windows(2).any(|s| BAD_STRINGS.contains(&s));

    n_vowels >= 3 && has_pair && !has_bad
}

fn part2(input: &[u8]) -> bool {
    let has_singles = input.windows(3).any(|s| s[0] == s[2]);

    let mut pairs: HashMap<&[u8], usize> = HashMap::new();
    let has_pairs = input.windows(2).enumerate().any(|(idx, pair)| {
        match pairs.entry(pair) {
            Occupied(ref e) => e.get() + 1 < idx,
            Vacant(e) => {
                e.insert(idx);
                false
            }
        }
    });

    has_singles && has_pairs
}
タリ ·· Ask questions the smart way ·· digipres.club
Day 5:
Part 1:

Code:
input.Split('\n').Where(s => s.Count(c => "aeiou".Contains(c)) >= 3 && s.TakeWhile((c, i) => i < s.Length - 2 && c != s[i + 1]).Count() < s.Length - 2 && s.IndexOf("ab") == -1 && s.IndexOf("cd")==-1 && s.IndexOf("pq") == -1 && s.IndexOf("xy") == -1).Count()


Part 2:

Code:
input.Split(new[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries).Where(s => s.Where((c, i) => i < s.Length - 2 && c == s[i + 2]).Count() > 0 && s.Where((c, i) => i < s.Length - 3 && s.IndexOf(c.ToString() + s[i + 1], i + 2) != -1).Count() > 0).Count()


Part 1 could be simplified a bit by what I learned from part 2 (specifically that Where can take an index), but oh well, it's done.
Shaun
Day 6: experimenting with parser combinators. Perhaps if I can automate performance of the horrific side tasks assigned to me by the Overlords they will allow me to leave, sanity intact, once these programming tasks have been completed.


Code:
#[macro_use]
extern crate nom;

use nom::{digit, newline, space};
use std::cmp::max;
use std::io::Read;
use std::str;

#[derive(Clone, Copy, Debug)]
enum Action {
    TurnOn,
    TurnOff,
    Toggle
}
type Coord = (u32, u32);
#[derive(Debug)]
struct Command(Action, Coord, Coord);

named!(number<u32>,
    map_res!(
        map_res!(digit, str::from_utf8),
        str::parse::<u32>
    )
);

named!(coordinate<Coord>,
    chain!(
        first: number ~
        tag!(",") ~
        second: number,

        || (first, second)
    )
);

named!(command<Command>,
    chain!(
        action: alt!(
            tag!("turn on") => { |_| Action::TurnOn } |
            tag!("turn off") => { |_| Action::TurnOff } |
            tag!("toggle") => { |_| Action::Toggle  }
        ) ~
        space ~
        top_left: coordinate ~
        space ~ tag!("through") ~ space ~
        bottom_right: coordinate ,

        || Command(action, top_left, bottom_right)
    )
);

named!(commands(&[u8]) -> Vec<Command>, separated_list!(newline, command));

fn main() {
    let stdin = std::io::stdin();
    let mut input = Vec::new();
    stdin.lock().read_to_end(&mut input).unwrap();

    match commands(&input) {
        nom::IResult::Done(tail, commands) => {
            if tail.len() != 0 {
                panic!("Unparseable tail (probable syntax error)");
            }

            let mut p1 = [false; 1000000];
            let mut p2 = [0i32; 1000000];
            for command in commands {
                exec_command(&mut p1, &command, |a: Action, x: bool| {
                    match a {
                        Action::TurnOn => true,
                        Action::TurnOff => false,
                        Action::Toggle => !x
                    }
                });

                exec_command(&mut p2, &command, |a: Action, x: i32| {
                    match a {
                        Action::TurnOn => x + 1,
                        Action::TurnOff => max(x - 1, 0),
                        Action::Toggle => x + 2
                    }
                });
            }
            println!("{}", p1.iter().filter(|&&b| b).count());
            println!("{}", p2.iter().fold(0i32, |a, x| a + x));
        },
        err => println!("{:?}", err),
    }
}

fn exec_command<T, F>(state: &mut [T], &Command(action, (tx, ty), (bx, by)): &Command,
                      mut handler: F)
        where T: Copy,
              F: FnMut(Action, T) -> T {
    assert!(by >= ty && bx >= tx);
    for i in &[tx, ty, bx, by] {
        assert!(*i < 1000);
    }

    for y in ty..(by + 1) {
        for x in tx..(bx + 1) {
            let element = &mut state[y as usize * 1000 + x as usize];
            *element = handler(action, *element);
        }
    }
}


Turns out the optimizer is extremely good at handling this code:
Code:
$ time cargo run < input
...
cargo run < input  2.59s user 0.08s system 97% cpu 2.729 total
$ time cargo run --release < input
...
cargo run --release < input  0.14s user 0.09s system 78% cpu 0.302 total
タリ ·· Ask questions the smart way ·· digipres.club
Alright, I got the answers for Day 6, but my code basically just took the normal route because I didn't feel like dealing with anything. Anyway, here are the pictures of my lights:

Day 6:
Part 1:


Part 2:
Shaun
Day 7: why compute dependency chains when we can make the OS do it indirectly for us?

Parser declarations first since they're not very interesting.
Code:
#[macro_use]
extern crate nom;

use std::collections::BTreeMap;
use std::io::Read;
use std::{str, mem};
use std::sync::mpsc::{sync_channel, Receiver, SyncSender};
use std::thread::spawn;
use nom::space;

type Wire<'a> = &'a str;
type Wires<'a> = BTreeMap<&'a str, (Option<SyncSender<u16>>, Receiver<u16>)>;

#[derive(Debug)]
enum Operation<'a> {
    Pass(Wire<'a>),
    Literal(u16),
    And(Wire<'a>, Wire<'a>),
    Or(Wire<'a>, Wire<'a>),
    // Apparently sometimes the first parameter to AND is a literal (only ever
    // '1'?). This is dumb.
    AndLiteral(Wire<'a>, u16),
    Shl(Wire<'a>, u16),
    Shr(Wire<'a>, u16),
    Invert(Wire<'a>)
}

named!(number<u16>,
    map_res!(
        map_res!(nom::digit, str::from_utf8),
        str::parse::<u16>
    )
);

named!(name<Wire>, map_res!(nom::alpha, str::from_utf8));

named!(operation<Operation>,
    alt!(
        chain!(lhs: number ~ space ~ tag!("AND") ~ space ~ rhs: name,
               || Operation::AndLiteral(rhs, lhs)) |
        map!(number, Operation::Literal) |
        chain!(tag!("NOT") ~ space ~ input: name,
               || Operation::Invert(input)) |
        chain!(lhs: name ~ space ~ tag!("AND") ~ space ~ rhs: name,
               || Operation::And(lhs, rhs)) |
        chain!(lhs: name ~ space ~ tag!("OR") ~ space ~ rhs: name,
               || Operation::Or(lhs, rhs)) |
        chain!(input: name ~ space ~ tag!("LSHIFT") ~ space ~ shift: number,
               || Operation::Shl(input, shift)) |
        chain!(input: name ~ space ~ tag!("RSHIFT") ~ space ~ shift: number,
               || Operation::Shr(input, shift)) |
        map!(name, |n| Operation::Pass(n))
    )
);

named!(decl<(Wire, Operation)>,
    chain!(op: operation ~ space ~ tag!("->") ~ space ~ dest: name,
           || (dest, op))
);

named!(decls(&[u8]) -> Vec<(Wire, Operation)>,
    separated_list!(nom::multispace, decl)
);

Simulation:
Code:
/// Return a receiving half for the channel set driven by `w`.
fn inwire<'a>(wires: &mut Wires<'a>, w: Wire<'a>) -> Receiver<u16> {
    // Get driver, create if it doesn't exist
    if !wires.contains_key(w) {
        let (sender, receiver) = sync_channel(1);
        wires.insert(w, (Some(sender), receiver));
    }

    // Create a tee, replace old sender with one output from the tee
    let (s1, r1) = sync_channel(1);
    let (s2, r2) = sync_channel(1);
    let input = match wires.get_mut(w) {
        Some(&mut (_, ref mut r)) => {
            mem::replace(r, r2)
        }
        _ => unreachable!()
    };

    // Duplicate value to two outputs s1 and s2. Necessary since
    // one wire may drive multiple gates, and this lets us inspect
    // all wires, rather than just terminals (ones that drive nothing).
    spawn(move || {
        let x = input.recv().unwrap();
        s1.send(x).unwrap();
        s2.send(x).unwrap();
    });
    r1
}

fn main() {
    let input = std::io::stdin().bytes().map(Result::unwrap).collect::<Vec<_>>();

    let decls = match decls(&input) {
        nom::IResult::Done(i, ref o) if i.len() > 0 => {
            panic!("Unparseable tail (error): `{}`\nGot {:?}",
                   str::from_utf8(i).unwrap_or("<bad utf8>"),
                   o);
        },
        nom::IResult::Done(_, o) => o,
        x => panic!("Failed to parse: {:?}", x)
    };

    let mut wires: Wires = BTreeMap::new();
    for (output, expr) in decls {
        // Create channel for wire if does not yet exist
        if !wires.contains_key(output) {
            let (sender, receiver) = sync_channel(1);
            wires.insert(output, (Some(sender), receiver));
        }
        // Get sending half of the channel for evaluation
        let sender = wires.get_mut(output).unwrap()
            .0.take().expect(&format!("Wire `{}` appears to have multiple drivers", output));

        /// One-argument worker
        fn w1<'a, F>(wires: &mut Wires<'a>, output: SyncSender<u16>, input: Wire<'a>, f: F)
                where F: Send + 'static + FnOnce(u16) -> u16 {
            let input = inwire(wires, input);
            spawn(move || output.send(f(input.recv().unwrap())));
        }

        /// Two-argument worker
        fn w2<'a, F>(wires: &mut Wires<'a>, output: SyncSender<u16>,
                     l: Wire<'a>, r: Wire<'a>, f: F)
                where F: Send + 'static + FnOnce(u16, u16) -> u16 {
            let l = inwire(wires, l);
            let r = inwire(wires, r);
            spawn(move || output.send(f(l.recv().unwrap(), r.recv().unwrap())));
        }

        match expr {
            Operation::Pass(input) => w1(&mut wires, sender, input, |x| x),
            Operation::Literal(x) => {
                spawn(move || sender.send(x));
            },
            Operation::And(lhs, rhs) => w2(&mut wires, sender, lhs, rhs, |l, r| l & r),
            Operation::Or(lhs, rhs) => w2(&mut wires, sender, lhs, rhs, |l, r| l | r),
            Operation::AndLiteral(input, lit) => w1(&mut wires, sender, input, move |x| x & lit),
            Operation::Invert(input) => w1(&mut wires, sender, input, |x| !x),
            Operation::Shr(input, n) => w1(&mut wires, sender, input, move |x| x >> n),
            Operation::Shl(input, n) => w1(&mut wires, sender, input, move |x| x << n),
        }
    }

    println!("Have {} wire(s), with the following values:", wires.len());
    for (name, (_, receiver)) in wires {
        println!("\t{}: {}", name, receiver.recv().unwrap());
    }
}

We spawn a thread for every statement in the input, where each thread waits for a value to appear from its inputs then performs its computation and sends it to the output.

A fair amount of complexity appears because wires may be referred to before their drivers are defined, and the channel primitive is not ideal for single-producer-multiple-consumer systems like this. A monitor would be somewhat better, since each consumer thread could mwait and avoid making copies as implemented by inwire.
タリ ·· Ask questions the smart way ·· digipres.club
Code for the last couple days:
Day 5:

Code:
package net.cemetech.sfgp.advent

object NaughtyOrNice {
   val vowels = "aeiou".toSet
   val bads = "ab,cd,pq,xy".split(",").toSet
   def isNice1(s:String):Boolean = {
      val state = s.sliding(2).foldLeft((false, false, 0)){
         case ((rep, bad, vowel), pair) =>
            (rep | (pair(0) == pair(1)),
             bad | bads.contains(pair),
             vowel + vowels.count(_.equals(pair(1))))
      }
      s.length > 1 && state._1 && !state._2 && (3 <= vowels.count(_.equals(s(0))) + state._3)
   }
   
   def isNice2(s:String):Boolean = {
      val state = s.sliding(2).zipAll(s.sliding(3),"","").foldLeft((false,false,false,Set[String]())){
         case((rep1,rep2,bad,tup),(pair,trip)) if trip.length == 3 =>
            (rep1 | trip(0) == trip(2) && trip(0) != trip(1),
            rep2 | tup.contains(pair),   
            bad | trip(0) == trip(2) && trip(0) == trip(1),
            tup + pair)
         case((rep1,rep2,bad,tup),(pair,_)) =>
            (rep1,rep2 | tup.contains(pair),bad,tup + pair)
      }
      state._1 && state._2 && !state._3
   }
   
   def countNice(pred: (String => Boolean), s :String) ={
      s.lines.foldLeft(0){
         case (ct, l) if pred(l) => ct+1
         case (ct, _) => ct
      }
   }
   
   def main(args:Array[String]) = {
      Console.println(isNice1("ugknbfddgicrmopn"))
      Console.println(isNice1("aaa"))
      Console.println(isNice1("jchzalrnumimnmhp"))
      Console.println(isNice1("haegwjzuvuyypxyu"))
      Console.println(isNice1("dvszwmarrgswjxmb"))
      Console.println(isNice2("qjhvhtzxzqqjkmpb"))
      Console.println(isNice2("xxyxx"))
      Console.println(isNice2("uurcxstgmygtbstg"))
      Console.println(isNice2("ieodomkazucvgmuy"))
      Console.println(List(isNice1 _,isNice2 _).map(f=>countNice(f,"""MY SECRET INPUT""")))
   }

}


More recently, I discovered how much fun Regex can be with Scala. Day 6:

Code:
package net.cemetech.sfgp.advent
import scala.reflect.ClassTag

object StartAFire {
   val iKeys = Array("turn on", "turn off", "toggle")
   val iMaps = (Map(iKeys(0) -> {s:Boolean => true},iKeys(1) -> {s:Boolean => false},iKeys(2) -> {s:Boolean => !s}),
             Map(iKeys(0) -> {i:Int => i+1},iKeys(1) -> {i:Int => List(0,i-1).max},iKeys(2) -> {i:Int => i+2}))
   val iExp = s"(${iKeys.mkString("|")}) (\\d+),(\\d+) through (\\d+),(\\d+)".r
   def fiddleLights[T](im:Map[String,(T => T)])(a:Array[Array[T]], s:String) =
      s match {
         case iExp(instr,xi,yi,xf,yf) => a.view(xi.toInt,1 + xf.toInt).foreach(_.view(yi.toInt,1 + yf.toInt).transform(im(instr)(_)));a
      }
   
   def execInstr[T:ClassTag](init:T, counter:(Array[T] => Int), impl:Map[String,(T => T)])(instr:String) =
      instr.lines.foldLeft(Array.fill(1000,1000)(init))((l,i) => fiddleLights(impl)(l,i)).foldLeft(0)((c,row) => c + counter(row))
   
   def main(args:Array[String]) = {
      Console.println(List(   execInstr(false,{row:Array[Boolean]   => row.count(b=>b)}, iMaps._1) _,
                     execInstr(0,   {row:Array[Int]      => row.reduce(_+_)}, iMaps._2) _).map(_("""MY SECRET INPUT HERE""")))
   }

}


My first instinct for day 7 was to do a topological sort, and do a single pass over all expressions, but instead I decided to just write a simple memoizing interpreter, which I think was more fun:

Code:
package net.cemetech.sfgp.advent


abstract class Vertex
case class Wire(id:String) extends Vertex
case class Signal(v:Char) extends Vertex
case class Gate1(v:Vertex,f:Char=>Char) extends Vertex
case class Gate2(l:Vertex,r:Vertex,f:(Char,Char)=>Char) extends Vertex

object BobbyTables {
   val unMap = Map("NOT" -> {c:Char => (~c).toChar})
   val binMap = Map[String,(Char,Char)=>Char]("AND" -> {(l,r) => (l&r).toChar},"OR" -> {(l,r) => (l|r).toChar},
         "LSHIFT" -> {(l,r) => (l<<r).toChar},
         "RSHIFT" -> {(l,r) => (l>>r).toChar})
   val term = """([a-z]+|\d+)"""
   val gateExp = s"(?:(?:(${unMap.keys.mkString("|")}) $term)|(?:$term (${binMap.keys.mkString("|")}) $term)|$term) -> ([a-z]+)".r
   def depends(id:String, vm:Map[String,Either[Vertex,Char]]) = vm.getOrElse(id, Left(Wire(id))).left.get
   def idOrV(s:String, vm:Map[String,Either[Vertex,Char]]) = try { Signal(s.toInt.toChar) } catch { case nfe:NumberFormatException => depends(s,vm) }
   def constructGate(instr:String, vm:Map[String,Either[Vertex,Char]]) = {
      instr match {
         case gateExp(null,null,null,null,null,src,dst) => vm + (dst -> Left(idOrV(src,vm)))
         case gateExp(op,r,null,null,null,null,dst) => vm + (dst -> Left(Gate1(idOrV(r, vm),unMap(op))))
         case gateExp(null,null,l,op,r,null,dst) => vm + (dst -> Left(Gate2(idOrV(l, vm),idOrV(r,vm),binMap(op))))
      }
   }
   
   def handleVertex(v:Vertex, vm:Map[String,Either[Vertex,Char]]):(Char, Map[String,Either[Vertex,Char]]) = {
      v match {
               case Signal(v) => (v, vm)
               case Wire(id) => deduceValue(id, vm)
               case Gate1(v,f) => val s = handleVertex(v,vm);(f(s._1),s._2)
               case Gate2(l,r,f) => val sl = handleVertex(l,vm);val sr = handleVertex(r,sl._2);(f(sl._1,sr._1),sr._2)
            }
   }
   
   def deduceValue(id:String, vm:Map[String,Either[Vertex,Char]]):(Char, Map[String,Either[Vertex,Char]]) = {
      vm(id) match {
         case Left(v:Vertex) => val s = handleVertex(v, vm);(s._1,s._2 + (id -> Right(s._1)))
         case Right(c:Char) => (c,vm)
      }
   }
   
   def compileVM(instr:String) = instr.lines.foldLeft(Map[String,Either[Vertex,Char]]())((vm,i) => constructGate(i,vm))
   def main(args:Array[String]):Unit = {
      Console.println(deduceValue("a",compileVM("""blah blah"""))._1.toInt)
   }
}
<- Please Support on Lego Ideas
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Advent of Code
» Goto page 1, 2  Next
» View previous topic :: View next topic  
Page 1 of 2
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement