Advent of Code
» >
» Goto page Previous  1, 2
» View previous topic :: View next topic  
I didn't do day 7. I'll add my solution if I do. Anyway, here's day 8:

Day 8:
Part 1:

Code:
input.SplitOnNewLine().Select(s => new { CodeLength = s.Length, MemLength = s.Substring(1, s.Length-2).Aggregate(new { Count = 0, EscapeCount = 0 }, (agg, current) => agg.EscapeCount == -1 ? new { Count = agg.Count, EscapeCount = current == '"' || current == '\\' ? 0 : 2 } : agg.EscapeCount > 0 ? new { Count = agg.Count, EscapeCount = agg.EscapeCount - 1 } : current == '\\' ? new { Count = agg.Count + 1, EscapeCount = -1 } : new { Count = agg.Count + 1, EscapeCount = 0 }, a => a.Count) }).Sum(a => a.CodeLength - a.MemLength)


Part 2:

Code:
input.SplitOnNewLine().Select(s => new { CodeLength = s.Length, EncodedLength = s.Sum(c => c == '"' || c == '\\' ? 2 : 1) + 2 }).Sum(a => a.EncodedLength - a.CodeLength)


Both of these could be slightly reduced by doing the math in the Select--thus selecting an integer--and then having an empty Sum--which knows how to sum integers by default--but this made debugging easier.

Also note that I've made the SplitOnNewLine() extension method because I was tired of typing it out each time. It's just this:

Code:
static string[] SplitOnNewLine(this string s) => s.Split(new[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);


EDIT:
Oh, I realized I don't need the select at all, and can just do it with a sum. So here're the reduced answers:
Part 1:

Code:
input.SplitOnNewLine().Sum(s => s.Length - s.Substring(1, s.Length-2).Aggregate(new { Count = 0, EscapeCount = 0 }, (agg, current) => agg.EscapeCount == -1 ? new { Count = agg.Count, EscapeCount = current == '"' || current == '\\' ? 0 : 2 } : agg.EscapeCount > 0 ? new { Count = agg.Count, EscapeCount = agg.EscapeCount - 1 } : current == '\\' ? new { Count = agg.Count + 1, EscapeCount = -1 } : new { Count = agg.Count + 1, EscapeCount = 0 }, a => a.Count))


Part 2:

Code:
input.SplitOnNewLine().Sum(s => s.Sum(c => c == '"' || c == '\\' ? 2 : 1) + 2  - s.Length)
Shaun
I was thinking about switching off of Scala and trying something different today, but the opportunity to use reflection was just too good. In part one, I don't really do anything fancy, besides having to convert from hex escapes to octal escapes, because this isn't C, but Scala has a built in "un-escaper" it uses for various things, called StringContext, and I used that for a one liner (assuming the input is stored in val inp).

Code:
Console.println(inp.lines.foldLeft(0)((c,l) =>
         c + 2 + l.length - StringContext.treatEscapes("""\\x([0-9a-f][0-9a-f])""".r.replaceAllIn(l, (m =>
            """\\%03o""".format(Integer.parseInt(m.group(1),16))))).length))


For part 2, I used the Scala reflection tools to put my string into Literal Constant AST-node using the reflection tools in scala.reflect.runtime.universe._, and then converted this back into a string:

Code:
Console.println(inp.lines.foldLeft(0){(c,l) =>
         c + Literal(Constant(l)).toString.length - l.length})
<- Please Support on Lego Ideas
State machines and iterators for day 8.

Code:
use std::io::Read;

struct Unescape<I>(I);

const HEX_CHARS: &'static str = "0123456789abcdef";

impl<I: Iterator<Item=char>> Iterator for Unescape<I> {
    type Item = char;

    fn next(&mut self) -> Option<char> {
        enum State {
            Null,
            Begin,
            Hex0,
            Hex1(u8),
        }
        let mut state = State::Null;

        loop {
            state = match (state, self.0.next()) {
                (_, None) => return None,

                (State::Null, Some('"')) => State::Null,
                (State::Null, Some('\\')) => State::Begin,
                (State::Null, c) => return c,

                (State::Begin, c @ Some('"')) |
                (State::Begin, c @ Some('\\')) => return c,
                (State::Begin, Some('x')) => State::Hex0,
                (State::Begin, Some(c)) => panic!("Invalid escape character '{}'", c),

                (State::Hex0, Some(c)) =>
                    State::Hex1(HEX_CHARS.find(c).expect("Invalid character in hex escape") as u8),
                (State::Hex1(x), Some(c)) =>
                    return Some(((x << 4) |
                                 HEX_CHARS.find(c).expect("Invalid character in hex escape") as u8) as char)
            };
        }
    }
}

enum CharOrStr<'a> {
    Char(char),
    Str(&'a str)
}
struct Escape<I>(I);

impl<I: Iterator<Item=char>> Iterator for Escape<I> {
    type Item = CharOrStr<'static>;

    fn next(&mut self) -> Option<Self::Item> {
        match self.0.next() {
            None => None,
            Some('\\') => Some(CharOrStr::Str(r"\\")),
            Some('"') => Some(CharOrStr::Str(r#"\""#)),
            Some(c) => Some(CharOrStr::Char(c))
        }
    }
}

fn main() {
    let stdin = std::io::stdin();
    let mut input: Vec<u8> = vec![];
    stdin.lock().read_to_end(&mut input).unwrap();

    let mut input_size = 0usize;
    let output_size = Unescape (
        input.iter().cloned()
            .map(|b| b as char)
            .filter(|c| !c.is_whitespace())
            .inspect(|_| input_size += 1)
    ).count();
    println!("Part 1: {} byte(s) in, {} char(s) out, delta = {}",
             input_size, output_size, input_size - output_size);

    // Each line of input is implicitly one literal, where each gets leading
    // and trailing quotes.
    let mut nlines = 0usize;
    let output_size = Escape(
        input.iter().cloned()
            .map(|b| b as char)
            .inspect(|c| if *c == '\n' { nlines += 1; })
            .filter(|c| !c.is_whitespace())
    ).map(|o| match o {
        CharOrStr::Char(_) => 1,
        CharOrStr::Str(s) => s.len()
    }).fold(0usize, |a, x| a + x) + 2 * nlines;
    println!("Part 2: {} byte(s) in, {} char(s) out, delta = {}",
             input_size, output_size, output_size - input_size);
}
タリ ·· Ask questions the smart way ·· digipres.club
Day 9: Traveling salesman.
I haven't been up this late in a while, but it paid off, as I just cruised past Adriweb and Juju for the day to position 33 on the leaderboard.



Anyway:

Code:
object TravelingSalesman {
   val inp = """blah blah blah"""
   val distRe = """([a-zA-Z]+) to ([a-zA-Z]+) = ([0-9]+)""".r
   def main(args:Array[String]):Unit = {
      val (dists, cities) = inp.lines.foldLeft((Map[(String,String),Int](),Set[String]())){case ((m,s),distRe(a,b,d)) => (m ++ Map(((a,b) -> d.toInt), ((b,a) -> d.toInt)), s ++ Set(a,b))}
      val routeD = cities.toList.permutations.map(_.sliding(2).foldLeft(0)((d,p)=> d + dists((p(0), p(1))))).toStream
      Console.println(routeD.min)
      Console.println(routeD.max)
   }
}
<- Please Support on Lego Ideas
I had to synthesize my own permutations iterator, sadly. Otherwise we have very similar solutions again.
Code:
#[macro_use]
extern crate itertools;

use std::collections::HashMap;
use std::io::BufRead;
use std::hash::Hash;

fn get_or_create<'a, K, V>(key: &K, default: V, m: &'a mut HashMap<K, V>) -> V
        where K: Eq + Hash + Clone, V: Clone {
    if !m.contains_key(key) {
        m.insert(key.clone(), default);
    }
    m[key].clone()
}

fn main() {
    let mut names: HashMap<String, u8> = HashMap::new();
    let mut distances: HashMap<(u8, u8), u8> = HashMap::new();

    let stdin = std::io::stdin();
    for line in stdin.lock().lines().map(Result::unwrap) {
        let words = line.split(' ').collect::<Vec<&str>>();
        let src = get_or_create(&words[0].into(), names.len() as u8, &mut names);
        assert_eq!(words[1], "to");
        let dst = get_or_create(&words[2].into(), names.len() as u8, &mut names);
        assert_eq!(words[3], "=");
        let distance = str::parse::<u8>(words[4]).unwrap();

        distances.insert((src, dst), distance);
        distances.insert((dst, src), distance);
    }
    println!("Have {} locations, {} distance pairs", names.len(), distances.len());
    // iproduct! below is hard-coded for 8 locations to visit
    assert_eq!(names.len(), 8);

    let n = names.len() as u8;
    let allnames = 0u8..n;
    let prod = iproduct!(allnames.clone(), allnames.clone(), allnames.clone(), allnames.clone(),
                         allnames.clone(), allnames.clone(), allnames.clone(), allnames);
    let mut min_distance = std::usize::MAX;
    let mut max_distance = std::usize::MIN;
    for s in prod {
        let nodes = [s.0, s.1, s.2, s.3, s.4, s.5, s.6, s.7];   // Ick
        if nodes.iter().fold(0u8, |a, &x| a | (1 << x)) != 0xFF {
            continue
        }

        let distance = nodes.windows(2).fold(0usize, |a, p| a + distances[&(p[0], p[1])] as usize);
        min_distance = std::cmp::min(min_distance, distance);
        max_distance = std::cmp::max(max_distance, distance);
    }

    println!("min {}, max {}", min_distance, max_distance);
}

It's another problem where the optimizer puts in some work:
Code:
cargo run < input  6.20s user 0.06s system 98% cpu 6.340 total
cargo run --release < input  0.27s user 0.04s system 81% cpu 0.385 total
タリ ·· Ask questions the smart way ·· digipres.club
Day 10: trivial with grouping iterators. There's an allocation in the tight loops that I'd like to get rid of (format!), but meh.

Code:
#[macro_use]
extern crate itertools;

use itertools::Itertools;
use std::io::Read;

fn expand(s: &mut String) {
    *s = s.chars()
          .filter(|c| c.is_digit(10))
          .group_by_lazy(|x| *x).into_iter()
          .map(|(v, g)| format!("{}{}", g.count(), v))
          .collect();
}

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

    for _ in 0..40 {
        expand(&mut s);
    }
    println!("After 40: {}", s.len());

    for _ in 0..10 {
        expand(&mut s);
    }
    println!("After 50: {}", s.len());
}
タリ ·· Ask questions the smart way ·· digipres.club
You say iteration, I say recursion! I was going to go back to Racket today, but then they didn't have span/splitf in the standard library for streams or sequences, so I got mad and stuck with Scala. This was a good decision, because I also discovered App and no longer have to type def main() = {} boilerplate, so yay.

Code:
object LookAndSay extends App {
   def lookAndSay(s:Stream[Char]):Stream[Char] =
      s.headOption match {
         case Some(c) =>
            val v = s.span(_ == c)
            (v._1.size + '0').toChar #:: c #:: lookAndSay(v._2)
         case None => Stream.Empty
      }
   
   def composeN[T](n:Int, f:T=>T, init:T):T =
      n match {
         case 0 => init
         case _ => composeN(n-1,f, f(init))
      }
   
   val day1 = composeN(40, lookAndSay, this.args(0).toStream)
   val day2 = composeN(10, lookAndSay, day1)
   Console.println(day1.size,day2.size)
}


Sadly (or possibly thankfully) my string sizes weren't long enough for Conway's constant to become helpful.
<- Please Support on Lego Ideas
Didn't bother posting code for day 11 because it wasn't a very interesting problem. You might think Rust would have to fall back to nastiness due to the absence of any kind of schema for the JSON on day 12, but you might also be pleasantly surprised.


Code:
extern crate serde_json;

use serde_json::Value;

fn reduce<F: FnMut(&String) -> bool>(v: &Value, f: &mut F) -> Option<f64> {
    match v {
        &Value::Null |
        &Value::Bool(_) => Some(0f64),

        &Value::String(ref s) => if f(s) { None } else { Some(0f64) },

        &Value::I64(x) => Some(x as f64),
        &Value::U64(x) => Some(x as f64),
        &Value::F64(x) => Some(x),

        &Value::Array(ref a) => {
            Some(a.iter()
                  .map(|x| reduce(x, f))
                  .fold(0f64, |a, x| a + x.unwrap_or(0f64))
            )
        },
        &Value::Object(ref m) => {
            m.iter()
             .map(|(_, v)| reduce(v, f))
             .fold(Some(0f64), |a, x| a.and_then(|a| x.map(|x| a + x)))
             .or(Some(0f64))
        }
    }
}

fn main() {
    let stdin = std::io::stdin();
    let input: Value = serde_json::from_reader(stdin).unwrap();

    println!("{:?}", reduce(&input, &mut |_| false).unwrap_or(0f64));
    println!("{:?}", reduce(&input, &mut |s| s == "red").unwrap_or(0f64));
}

It was rather nicer for just part 1, but in order to prune subtrees I needed to use Option to indicate whether a block should be ignored. This led to the kind of weird monadic and_then(map). Numeric type inference wasn't great either so I ended up needing to annotate all the numeric literals with their types.
タリ ·· Ask questions the smart way ·· digipres.club
Skipped a bunch of days. Oh well...

Day 14:
Part 1:

Code:
input.SplitOnNewLine().Select(s => System.Text.RegularExpressions.Regex.Match(s, "(?<Name>\\w*) can fly (?<Speed>\\d*) km\\/s for (?<Duration>\\d*) seconds, but then must rest for (?<Rest>\\d*) seconds.").Groups).Select(s => new { Name = s["Name"].Value, Speed = int.Parse(s["Speed"].Value), Duration = int.Parse(s["Duration"].Value), Rest = int.Parse(s["Rest"].Value) }).Select(deer => Enumerable.Range(0, 2503).Aggregate(new { State = 'F', TimeInState = 0, Distance = 0}, (state, time) => state.State == 'F' ? state.TimeInState == deer.Duration ? new { State = 'R', TimeInState = 1, Distance = state.Distance } : new { State = 'F', TimeInState = state.TimeInState + 1, Distance = state.Distance + deer.Speed } : state.TimeInState == deer.Rest ? new { State = 'F', TimeInState = 1, Distance = state.Distance + deer.Speed } : new { State = 'R', TimeInState = state.TimeInState + 1, Distance = state.Distance })).Max(deer => deer.Distance)


Part 2... well, maybe I'll do it later.
Shaun
Apparently the recent problems have been boring. 16 is at least something new.

Parsing:
Code:
#[macro_use]
extern crate nom;

use nom::{alpha, digit, newline, space, IResult};
use std::io::Read;
use std::str;

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

type Term<'a> = (&'a str, u32);

named!(term<Term>, chain!(
    space ~ name: map_res!(alpha, str::from_utf8) ~ tag!(":") ~ space ~ value: number,
    || (name, value)
));

type Sue = [Option<u32>; 10];
named!(sue<(u32, Sue)>,
    chain!(
        tag!("Sue") ~ space ~ id: number ~ tag!(":") ~
        terms: separated_nonempty_list!(tag!(","), term),
        || {
            let mut out: (u32, Sue) = (id, Default::default());
            for term in terms {
                let idx = match term.0 {
                    "children" => 0,
                    "cats" => 1,
                    "samoyeds" => 2,
                    "pomeranians" => 3,
                    "akitas" => 4,
                    "vizslas" => 5,
                    "goldfish" => 6,
                    "trees" => 7,
                    "cars" => 8,
                    "perfumes" => 9,
                    s => panic!("Unrecognized term: '{}'", s)
                };
                // Should not be multiply-specified but the parser doesn't enforce that
                assert_eq!(out.1[idx], None);
                out.1[idx] = Some(term.1);
            }
            out
        }
    )
);

named!(sues(&[u8]) -> Vec<(u32, Sue)>, complete!(separated_list!(newline, sue)));


Other stuff:
Code:
fn main() {
    let mut input = vec![];
    std::io::stdin().read_to_end(&mut input).unwrap();

    let sues = match sues(&input) {
        IResult::Done(_, o) => o,
        e => panic!("Parse error: {:?}", e)
    };

    let target: Sue = [Some(3), Some(7), Some(2), Some(3), Some(0),
                       Some(0), Some(5), Some(3), Some(2), Some(1)];
    for (id, ref sue) in sues {
        if target.iter().zip(sue.iter()).all(|(t, s)| {
            s.map_or(true, |s| s == t.unwrap())
        }) {
            println!("Part 1: Sue {} matches", id);
        }

        if target.iter().zip(sue.iter()).enumerate().all(|(idx, (t, s))| {
            s.map_or(true, |s|
                if idx == 1 || idx == 7 {
                    // cats, trees: greater than target's value
                    s > t.unwrap()
                } else if idx == 3 || idx == 6 {
                    // pomeranians, goldfish: less than target's value
                    s < t.unwrap()
                } else {
                    s == t.unwrap()
                }
            )
        }) {
            println!("Part 2: Sue {} matches", id);
        }
    }
}


Nothing real novel. Assume a parameter matches if there's no value for it, otherwise perform an actual comparison.
タリ ·· Ask questions the smart way ·· digipres.club
Yeah, a bunch of the recent days have been essentially repeats and I got bored (day 11 is day 5, day 13 is day 9). Day 12 was kind of fun though, and I went back to Racket.


Code:
(require json)
(define (sum-nodes coll [no-red #f])
  (let ([sum-nodes (curryr sum-nodes no-red)])
    (foldl + 0
           (cond
             [(hash? coll)
              (if (and no-red (< 0 (count (curry equal? "red") (hash-values coll))))
                  null
                  (hash-map coll (lambda (k v) (sum-nodes v))))]
             [(list? coll) (map sum-nodes coll)]
             [(number? coll) `(,coll)]
             [else '(0)]))))

(define (sum-json string [no-red #f])
  (sum-nodes (string->jsexpr string) no-red))
(let
    ([js-str "some json string"])
  (display (map (curry sum-json js-str) '(#f #t))))
<- Please Support on Lego Ideas
Bump!
Advent season has started, and that means new advent of code puzzles! They're still at http://adventofcode.com/. All my solutions are still in the original GitHub repo in my first post. I have two folders in that repo now, a 2015 folder and a 2016 folder.

For today's puzzle (day 3), I managed to snag place 58 on the leaderboard for part 1 Very Happy
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
  
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 Previous  1, 2
» View previous topic :: View next topic  
Page 2 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