[–]▶ No.835306>>840886 [Watch Thread][Show All Posts]
Advent of Code is a series of small programming puzzles for a variety of skill levels. They are self-contained and are just as appropriate for an expert who wants to stay sharp as they are for a beginner who is just learning to code. Each puzzle calls upon different skills and has two parts that build on a theme.
http://adventofcode.com/
Previous thread: >>830716
▶ No.835328>>836651
Reminder:
more hard challenges on
12th
18th
25th
▶ No.835364>>835391 >>835526 >>836260
The hardest part of all the challenges so far have been deciphering the instructions of a few of them. Some of them are quite cryptic.
▶ No.835391>>836260
>>835364
this, whoever wrote them has a terrible way with words
▶ No.835403
>>835061
>Not writing a real parser
#[macro_use]
extern crate nom;
const INPUT: &'static [u8] = include_bytes!("../input");
enum E {
Group(Vec<E>),
Garbage(Vec<char>),
}
impl E {
fn score(&self, depth: u32) -> u32 {
match *self {
E::Group(ref x) => x.iter().map(|y| y.score(depth+1)).sum::<u32>()+depth,
E::Garbage(_) => 0,
}
}
fn count_garbage(&self) -> usize {
match *self {
E::Group(ref x) => x.iter().map(|y| y.count_garbage()).sum(),
E::Garbage(ref x) => x.iter().filter(|&y| *y != '!').count(),
}
}
}
named!(group<E>,
delimited!(
tag!("{"),
map!(
separated_list!(tag!(","), alt!(group | garbage)),
|a: Vec<E>| {E::Group(a)}
),
tag!("}")
)
);
named!(garbage<E>,
do_parse!(
a: delimited!(
tag!("<"),
many0!(alt!(
do_parse!(tag!("!") >> take!(1) >> ('!')) |
none_of!(">")
)),
tag!(">")
) >>
(E::Garbage(a.clone()))
)
);
fn main() {
let parsed = group(INPUT).unwrap().1;
println!("Part 1: {}", parsed.score(1));
println!("Part 2: {}", parsed.count_garbage());
}
yes, I cheated a bit for garbage counting
▶ No.835467>>835470 >>835471
I can't even do this one. Fucking Firefox piece of shit can't handle more than 4096 characters and I can't save it from my browser because they're fucking retards who don't know the difference between saving something and redownloading it, which shouldn't even be a problem anyway because I'm still logged in and can open it just fine.
>Puzzle inputs differ by user. Please log in to get your puzzle input.
Nice work, assholes!
▶ No.835470>>835475
>>835467
Works fine on machine my machines.
Why not just open up the network tab, visit the page, copy the request it makes as a curl command, and paste it into your terminal to get the input file.
▶ No.835471>>835475
▶ No.835475
>>835470
>>835471
Nvm, I solved it.
▶ No.835505>>835512 >>835516 >>836260
Today's instructions (part 2) are 100% cancer. Some examples are plain incorrect and some things are contradicting each other. Still I somehow managed to guess the answers. The code is nothing special, but I think I'll golf the 2nd part in a few minutes.
▶ No.835512
>>835505
Hmm I figured it, I actually forgot one thing. Now it can do correct answer in all cases. Great luck that I got a star with incorrect solution lol.
▶ No.835516>>835518
>>835505
287 characters
R=range
z=256
*l,=R(z)
s=0
p=0
f=0
for r in R(64):
for n in[*open('i','rb')][0]+b'\x11\x1fI/\x17':o=(n+s)%z;l=[*reversed(l[:n]),*l[n:]];l=l[o:]+l[:o];p+=o;s+=1
c=(z-p)%z
l=l[c:]+l[:c]
print(''.join(map(lambda x:format(x,'02x'),(eval('^'.join(map(str,l[i*16:i*16+16])))for i in R(16)))))
▶ No.835518
>>835516
fug, of course I forgot to golf 2 more bytes
285 bytes
R=range
z=256
*l,=R(z)
s=0
p=0
f=0
for r in R(64):
for n in[*open('i','rb')][0]+b'\x11\x1fI/\x17':o=(n+s)%z;l=[*reversed(l[:n]),*l[n:]];l=l[o:]+l[:o];p+=o;s+=1
c=(z-p)%z
print(''.join(map(lambda x:format(x,'02x'),(eval('^'.join(map(str,(l[c:]+l[:c])[i*16:i*16+16])))for i in R(16)))))
▶ No.835519>>835520 >>841248
>>834979
day 10. fuck.
void one_round(uint8_t(& mylist)[256], const vector<uint8_t>& lengths, size_t& skip, uint8_t& cur)
{
for (uint8_t length : lengths){
for (uint8_t i = cur, last = cur + length - 1, l = length, l2 = length / 2; l --> l2; ++i, --last)
swap(mylist[i], mylist[last]);
cur += length + skip++;
}
}
void knot_hash1(string_view input)
{
uint8_t mylist[256]; iota(begin(mylist), end(mylist), 0);
vector<uint8_t> lengths;
for (uint8_t length : input | split(by_num) | map_to(to_int))
lengths.push_back(length);
size_t skip = 0; uint8_t cur = 0;
one_round(mylist, lengths, skip, cur);
cout << "part 1: " << int(mylist[0]) * int(mylist[1]) << '\n';
}
void knot_hash2(string_view input)
{
uint8_t mylist[256]; iota(begin(mylist), end(mylist), 0);
vector<uint8_t> lengths;
for (uint8_t ch : input)
lengths.push_back(ch);
for (uint8_t ch : {17, 31, 73, 47, 23})
lengths.push_back(ch);
size_t skip = 0; uint8_t cur = 0;
for (uint8_t i = 0; i < 64; ++i)
one_round(mylist, lengths, skip, cur);
uint8_t dense[16] = {0};
for (uint16_t i = 0, j = 0; i < 16; ++i, j += 16)
for (uint8_t k = 0; k < 16; ++k)
dense[i] ^= mylist[j + k];
string res; res.reserve(32);
for (uint8_t x : dense)
for (uint8_t nibble : {(x & 0b11110000) >> 4, x & 0b00001111})
res.push_back((nibble < 10 ? '0' : 'a' - 10) + nibble);
cout << "part 2: " << res << '\n';
}
▶ No.835520>>835521
>>835519
c++ solution is serious indeed
but can you also golf it?
▶ No.835521
>>835520
Today's puzzle annoyed me enough that I don't feel like touching it again.
▶ No.835523>>835524
>To play, please identify yourself via one of these services:
>[GitHub] [Google] [Twitter] [Reddit]
cancer. why not a patreon donation link for Literally Who 5 guys while you're at it?
▶ No.835524
>>835523
A github account is a necessity nowadays anyway.
Idk what the fuck are other 3 options doing here though.
▶ No.835526>>836260
>>835364
they were mostly fine in previous days, but day 10 is really fucked up indeed.
▶ No.835542>>835608 >>835905
▶ No.835563>>836260
Day 10 was a chore to read through. Crazy that someone solved it in 5 mins, 51 seconds.
▶ No.835566>>835571 >>835577
nasty fucking trick, day 10. You clearly intended that. 30 fucking minutes burnt because I 'treated my puzzle input as a string of ASCII characters' in the the wrong fucking way.
module Knot =
struct
let knot_size = 256
let secret = [|17; 31; 73; 47; 23|]
let rounds = 64
type t = { data : int array; mutable at : int; mutable skip : int }
let make () =
let data = Array.make knot_size 0 in
for i = 1 to (knot_size - 1) do data.(i) <- i done;
{ data; at = 0; skip = 0 }
let swap k n m =
let n, m = n mod knot_size, m mod knot_size in
let a = k.data.(n) in
k.data.(n) <- k.data.(m);
k.data.(m) <- a
let code_of_string s =
let a = Array.make (String.length s + Array.length secret) 0 in
for i = 0 to (String.length s) - 1 do
a.(i) <- int_of_char s.[i]
done;
Array.blit secret 0 a (String.length s) (Array.length secret);
a
let twist k n =
assert (knot_size >= n && n >= 0);
let rec loop i j times =
if times = 0 then () else
(swap k i j;
loop (i + 1) (j - 1) (times - 1)) in
loop k.at (k.at + n - 1) (n / 2 + (n mod 2));
k.at <- (k.at + n + k.skip) mod knot_size;
k.skip <- k.skip + 1
let twist_by_string k s =
let code = code_of_string s in
for i = 1 to rounds do Array.iter (twist k) code done
let twist_by_array k a =
let code = Array.append a secret in
for i = 1 to rounds do Array.iter (twist k) code done
let to_dense_hash k =
let hash = Array.make 16 0 in
for i = 0 to 16 - 1 do
for j = i * 16 to i * 16 + 16 - 1 do
hash.(i) <- hash.(i) lxor k.data.(j)
done
done;
hash
let hexdigit c =
if c >= 0 && c < 10 then char_of_int (c + int_of_char '0') else
char_of_int (c - 10 + int_of_char 'a')
let hash k =
let h = to_dense_hash k in
let b = Bytes.make 32 ' ' in
for i = 0 to 16 - 1 do
let c = h.(i) in
Bytes.set b (i * 2) (hexdigit ((c land 0xF0) lsr 4));
Bytes.set b (i * 2 + 1) (hexdigit (c land 0x0F))
done;
Bytes.to_string b
let hash_of s =
let k = make () in
twist_by_string k s;
hash k
end
get solutions with Knot.hash_of "test string"
▶ No.835571>>835577
>>835566
>in the the wrong fucking way.
That part got me too, at first I didn't realize they wanted the commas in that input.
▶ No.835577>>835581 >>835584
>>835566
>>835571
>For example, if you are given 1,2,3, you should convert it to the ASCII codes for each character: 49,44,50,44,51.
Wow reading is sooo hard. Didn't you learn reading in elementary school? Or are you niggers that didn't attend such a facility?
▶ No.835579>>835587 >>835589 >>835594 >>835881
What are you even supposed to do in 7b?
The example is totally different from the actual data and their description is absolute ass.
▶ No.835581
>>835577
I read that just fine. My code produced the correct answers for each of the examples which are presented as strings. And then I used my input, interpreting each number as an ASCII code, because it's set up that expectation already.
▶ No.835584>>835587
>>835577
I said at first, fool.
▶ No.835587>>835592 >>835594
>>835579
You are supposed to find the one node that unbalances the whole tree and give its corrected weight as answer.
>>835584
You are still unable to read simple instructions.
▶ No.835589
>>835579
Find the single weight that has to change.
▶ No.835592>>835593
>>835587
>unable to read simple instructions.
Well clearly not since I solved the problem. Also if you're going for speed, you may opt to skip their example outputs. Obviously a mental midget like yourself needs everything spelled out for you in explicit detail.
▶ No.835593>>835596 >>835599
>>835592
>fails reading the instructions
>fucks up
>no u
ok kid
▶ No.835594
>>835579
>>835587
note that you don't have to care about the whole tree. That's just the setting. Since the entire tree is composed of "waiter holding cups that all have the same weight", you just need to find waiters with differently-weighted cups. Since waiters are standing on top of each other you'll find more than one waiter like this with a simple scan. Then it's just selecting the right waiter, which should be obvious.
▶ No.835596>>835601
>>835593
You're a waste of time.
▶ No.835599>>835601
>>835593
>say this: boobs boobs boobs boobs boobs boobs boobs boobs boobs boobs boobs
<uh ok: boobs boobs boobs boobs boobs boobs boobs boobs bo--
>what are women good for?
<boobs!
<uh I mean
it's a trick. It's deliberate. Go ahead and pretend to above tricks all you want.
▶ No.835602
▶ No.835603>>835608
>>835601
Have you even posted a solution yet?
▶ No.835607>>835608
Radio silence I thought that'd make you shut up.
▶ No.835608>>835635
>>835603
>>835607
I just don't want to shit up the thread further. So let us stop arguing about irrelevant shit?
For my solution see here: >>835542
▶ No.835635
>>835608
wew lad
>people correctly notice that the puzzle's instructions are kinda bad
>angry little rust hipster starts grumpily berating others for pointing the truth
>people respond
<wow just wow lets be nice and stop arguing guys???
The rust community in a nutshell.
▶ No.835799>>835820
>find perl6 solution
>oh I wonder how fast this is
>is 730 times slower than ocaml solution
>32 times slower than ocaml bytecode-interpreted solution
c'mon /tech/ why aren't you using perl6?
do you hate women or something?
▶ No.835820>>835827
>>835799
>pacman -Ss perl6
>community/haskell-interpolatedstring-perl6 1.0.0-28
▶ No.835827>>835829
>>835820
never used arch. do you mean that that's the only 'perl6' that you have, and that's why you're not using it?
▶ No.835829
>>835827
There is no perl6 in the arch repos.
>community/haskell-interpolatedstring-perl6 1.0.0-28
>QuasiQuoter for Perl6-style multi-line interpolated strings
▶ No.835881
>>835579
Every node's children has to have the same weight. If they don't match look at the bad one's children to see if they all match.
Once you find the child with all matching children, you need to adjust the child's weight to fix the whole tree.
▶ No.835905>>835919 >>835921 >>835923 >>835924
/**
* Copyright m712 2017.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define GROW_CHUNK 8
#define CHECK_GROW(type, arr, len) \
if ((len) % GROW_CHUNK == 0) \
(arr) = realloc((arr), ((len) + GROW_CHUNK) * sizeof(type))
#define PUSH(type, arr, len, item) \
do { \
CHECK_GROW(type, arr, len); \
(arr)[(len)] = (item); \
(len)++; \
} while (0)
// Thanks rust
#define loop for(;;)
char *
get_input(void) {
char *output = NULL;
int outlen = 0;
int c;
while ((c = getchar()) != -1 && c != '\n')
PUSH(char *,output, outlen, (char)c);
PUSH(char *,output, outlen, 0);
return output;
}
int *
get_lengths(const char *input, int *lenlen) {
int *output = NULL;
int outlen = 0;
char *cursor = (char *) input;
// Explodes on '\0', so no need for bounds check
loop {
int num = strtol(cursor, &cursor, 10);
PUSH(int *,output, outlen, num);
if (!*cursor) break;
cursor++;
(*lenlen)++;
}
return output;
}
int *
generate_range(int end) {
int *output = malloc(end * sizeof(int));
for (int i = 0; i < end; i++) output[i] = i;
return output;
}
#define RANGE_SIZE 256
#define PRINT_RANGE(range) \
do { \
printf("["); \
for (int i = 0; i < RANGE_SIZE; i++) \
printf("%d, ", range[i]); \
puts("\b\b] "); \
} while (0)
int *
knot(int *input, int inlen, int iters) {
int *range = generate_range(RANGE_SIZE);
int cursor = 0,
skip = 0;
for (int t = 0; t < iters; t++)
for (int i = 0; i < inlen; i++) {
int len = input[i];
int *reversed = malloc(len * sizeof(int));
int j;
for (j = 0; j < len; j++)
reversed[j] = range[(cursor+j)%RANGE_SIZE];
// Copy it in reverse
for (j = 0; j < len; j++)
range[(cursor+len-1 -j)%RANGE_SIZE] = reversed[j];
free(reversed);
cursor += len + skip;
skip++;
}
return range;
}
int
part1(int *lengths, int lenlen) {
int *range = knot(lengths, lenlen, 1);
int product = range[0] * range[1];
PRINT_RANGE(range);
free(range);
return product;
}
char *
part2(const char *input) {
int salt[] = {17, 31, 73, 47, 23};
char hexdigits[] = "0123456789abcdef";
int lenlen = strlen(input) + 5;
int *lengths = malloc(lenlen * sizeof(int));
// char to int
for (int i = 0; i < lenlen; i++)
lengths[i] = (int) input[i];
memmove(lengths + lenlen - 5, salt, 5 * sizeof(int));
int *sparse = knot(lengths, lenlen, 64);
char *hex = malloc(33);
for (int i = 0; i < 16; i++) {
int dense = 0;
int *chunk = sparse + (i * 16);
for (int j = 0; j < 16; j++)
dense ^= chunk[j];
// Fucking ugly but can't bother
hex[(2*i)] = hexdigits[(dense>>4)%16];
hex[(2*i)+1] = hexdigits[(dense)%16];
}
hex[32] = 0;
free(sparse);
free(lengths);
return hex;
}
int
main(int argc, char **argv) {
(void) argc;
(void) argv;
char *input = get_input();
int lenlen = 0;
int *lengths = get_lengths(input, &lenlen);
printf("Product of first two items: %d\n", part1(lengths, lenlen));
char *hex = part2(input);
printf("Hex output: %s\n", hex);
free(hex);
free(input);
free(lengths);
return 0;
}
m712@nextchan:~/advent$ time ./day10 < day10input >/dev/null
real 0m0.002s
user 0m0.002s
sys 0m0.000s
>2ms
>on a shitbox vps cpu
STEVEKLABNIK ON SUICIDE WATCH
>>835542
>0.12ms
>it's actually 12ms
LOL
▶ No.835919
>>835905
>0.002s vs. OCaml's 0.001s, using same time-everything standard
C is a meme.
<oh wait fug this is C you have to *tell* it to fast
>0.001s vs OCaml's 0.001s, using same time-everything standard
well at least C has an easier time dropping down to asm :^)
>install dirty-iron crab-language to compare
>rustc 1.18.0 is too old for for_each methods on std::iter::Enumerate<std::slice::IterMut<'_, u8>>
that was a waste of time.
▶ No.835921>>836150
>>835905
>wtf why is my solution so slow? isnt c supposed be fast
>i know what i'll do. i will run the rust version without optimizations so i can feel better about my pajeet code
pathetic turkroach
▶ No.835923>>836150
>>835905
Are you retarded nigger seriously allocating a new array instead of reversing in place???
▶ No.835924>>836150
>>835905
printf("["); \
for (int i = 0; i < RANGE_SIZE; i++) \
printf("%d, ", range[i]); \
puts("\b\b] ");
gross. at least isatty(fileno(stdout)) before you do stuff like this.
▶ No.836150
>>835921
Whoops. It's indeed 0.12ms my bad.
>>835923
Unfucked it:
66a67,73
>
> #define SWAP(x, y) \
> do { \
> int temp = (x); \
> (x) = (y); \
> (y) = (temp); \
> } while (0)
79,80d85
< int *reversed = malloc(len * sizeof(int));
<
82,88c87,88
< for (j = 0; j < len; j++)
< reversed[j] = range[(cursor+j)%RANGE_SIZE];
< // Copy it in reverse
< for (j = 0; j < len; j++)
< range[(cursor+len-1 -j)%RANGE_SIZE] = reversed[j];
<
< free(reversed);
---
> for (j = 0; j < len/2; j++)
> SWAP(range[(cursor+len-1 -j)%RANGE_SIZE], range[(cursor+j)%RANGE_SIZE]);
It only does 15 allocs/frees now.
>>835924
It was for testing. Here:
60,66d59
< #define PRINT_RANGE(range) \
< do { \
< printf("["); \
< for (int i = 0; i < RANGE_SIZE; i++) \
< printf("%d, ", range[i]); \
< puts("\b\b] "); \
< } while (0)
101d93
< PRINT_RANGE(range);
Also,
>first REEEEE about me taking it too seriously and say that it's just a challenge in the previous thread
>now nitpick about correctness
This is your brain on Rust. (aka corroding)
▶ No.836171>>836172
Day 11 was pretty easy once you understood how the hexagonal grid worked.
I solved it by just writing a simplifier. I recognized that each step is commutative (the order doesn't matter) so I count up how many of each type of step is made. I then wrote my simplifier in 2 phases. The first phrase combines all the n/s, nw/se, etc pairs and cancels them out. My second phase of my simplifier handled what happens when you get stuff like n/se, ne,s, etc where you can take two directions and simplify them into 1. For each of these phrases they keep running in a loop until it detects it has finished by when nothing was updated that iteration. Once the whole thing was simplified, I could simply count up each of number of steps and present that as my answer. For the second part I just wrote a loop around it so that it would do the same thing except I had it done for first step, the first 2 steps, the first 3 steps, etc. At the end of each iteration I checked if the sum it found was the greatest and saved it for later if so. </blogpost>
▶ No.836172>>836173
>>836171
Somewhat similar shit, but I was again lucky to grab both stars with incorrect solution.
After that I think I figured how to do it 100% correct, now gonna golf it to hell, stay tuned
▶ No.836173>>836185
>>836172
Yeah, mine was pretty copy paste heavy. I could have defiantly abused symmetry for this one.
You'll probably be able to get a pretty nice code golf for today's.
▶ No.836179>>836184 >>836185 >>836204 >>836209 >>836250
#!/usr/bin/env python3
# Copyright m712 2017.
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
import sys
import math
moves = {
"n": (+0, -1),
"ne": (+1, -0.5),
"se": (+1, +0.5),
"s": (+0, +1),
"sw": (-1, +0.5),
"nw": (-1, -0.5),
}
def parse(input):
return input.strip().split(',')
def get_steps(x, y):
x,y = abs(x),abs(y)
return x + (y - x/2)
def solve(inm):
x, y = 0, 0
max_steps = 0
max_index = 0
for m in inm:
move = moves[m]
x += move[0]
y += move[1]
max_steps = max(max_steps, get_steps(x, y))
return (get_steps(x, y), max_steps)
if __name__ == "__main__":
print("Enter input:")
input = parse(sys.stdin.read())
part1, part2 = solve(input)
print("Number of moves:", part1)
print("Furthest move:", part2)
This one was pretty simple but I misunderstood the question (how many steps it took from start instead of max steps) because the AoC creator is a fucking rabbi or something because he can't into English. I checked out the subreddit and everyone used a Z thing. I just solved it by literally emulating a hexagon.
▶ No.836184>>836185 >>836186
>>836179
Clever, I was originally going to do something like that but didn't get the idea to use a fractional increment.
Could you explain what that Z thing was?
▶ No.836185>>836187 >>836188
>>836179
>>836184
>>836173
257 bytes
n,ne,se,d=[0]*4
a=abs
def D():x,y=ne+se,n-se;return a(a(x)-a(y))+min(a(x),a(y))if x*y<0else a(x+y)
s='n neses swnw'
for r in next(open('i')).split(','):i=s.index(r+' '*(len(r)<2));exec(f'{s[i%6:i%6+2]}{"+-"[i//6]}=1',None,locals());d=max(d,D())
print(D(),d)
▶ No.836186
>>836184
I didn't care enough to check it. I just used basic coordinates. Apparently it's explained here:
https://www.redblobgames.com/grids/hexagons/
▶ No.836187
>>836185
this is all without anything fractional btw.
I simply view hex grid as 2d board which allows walking in 1 of the diagonal directions.
▶ No.836188>>836193 >>836196
>>836185
254 bytes
forgot to get rid of f''
n,ne,se,d=[0]*4
a=abs
def D():x,y=ne+se,n-se;return a(a(x)-a(y))+min(a(x),a(y))if x*y<0else a(x+y)
s='n neses swnw'
for r in next(open('i')).split(','):i=s.index(r+' '*(len(r)<2));exec(s[i%6:i%6+2]+"+-"[i//6]+'=1',None,locals());d=max(d,D())
print(D(),d)
▶ No.836193>>836196
>>836188
Substring search can be golfed more, I should fix it when I go back to computer.
▶ No.836195>>836204
/**
* Copyright m712 2017.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#include <stdio.h>
#include <stdlib.h>
enum move_type {
N, NE, SE, S, SW, NW, EOM
};
#define abs(x) (x<0?-x:x)
#define max(a,b) (a>b?a:b)
#define GROW_CHUNK 8
#define CHECK_GROW(type, arr, len) \
if ((len) % GROW_CHUNK == 0) \
(arr) = realloc((arr), ((len) + GROW_CHUNK) * sizeof(type))
#define PUSH(type, arr, len, item) \
do { \
CHECK_GROW(type, arr, len); \
(arr)[(len)] = (item); \
(len)++; \
} while (0)
#define NOPE \
do { \
printf("Unexpected char %c\n", c); abort(); \
} while (0)
enum move_type *
parse(int *movlen) {
enum move_type *moves = NULL;
int c;
*movlen = 0;
while ((c = getchar()) != EOF && c != '\n') {
if (c == 'n') {
switch(c = getchar()) {
case 'w': PUSH(enum move_type *,moves,*movlen,NW); getchar(); break;
case 'e': PUSH(enum move_type *,moves,*movlen,NE); getchar(); break;
case '\n': case ',': PUSH(enum move_type *,moves,*movlen,N); break;
default: NOPE;
}
continue;
} else if (c == 's') {
switch(c = getchar()) {
case 'w': PUSH(enum move_type *,moves,*movlen,SW); getchar(); break;
case 'e': PUSH(enum move_type *,moves,*movlen,SE); getchar(); break;
case '\n': case ',': PUSH(enum move_type *,moves,*movlen,S); break;
default: NOPE;
}
continue;
} else NOPE;
}
return moves;
}
int
get_steps(double x, double y) {
x = abs(x);
y = abs(y);
return (x + (y - x/2));
}
void
do_step(enum move_type move, double *x, double *y) {
switch (move) {
case N:
*y -= 1;
break;
case S:
*y += 1;
break;
case NW:
*x -= 1;
*y -= 0.5;
break;
case SW:
*x -= 1;
*y += 0.5;
break;
case NE:
*x += 1;
*y -= 0.5;
break;
case SE:
*x += 1;
*y += 0.5;
break;
default:
printf("Unexpected move_type %d\n", move);
abort();
}
}
void
solve(enum move_type *moves, int movlen, int *part1, int *part2) {
double x = 0, y = 0;
for (int i = 0; i < movlen; i++) {
do_step(moves[i], &x, &y);
*part2 = max(*part2, get_steps(x, y));
}
*part1 = get_steps(x, y);
}
int
main(int argc, char **argv) {
(void) argc;
(void) argv;
int movlen;
enum move_type *moves = parse(&movlen);
int part1 = 0, part2 = 0;
solve(moves, movlen, &part1, &part2);
printf("Number of moves: %d\n", part1);
printf("Furthest move: %d\n", part2);
free(moves);
return 0;
}
m712@nextchan:~/advent$ time ./day11 < day11input >/dev/null
real 0m0.001s
user 0m0.000s
sys 0m0.001s
Works for me. The parsing and incrementings parts look like horseshit but I don't care enough to make it look better.
▶ No.836196>>836208
>>836188
>>836193
249 bytes
n,ne,se,d=[0]*4
a=abs
def D():x,y=ne+se,n-se;return a(a(x)-a(y))+min(a(x),a(y))if x*y<0else a(x+y)
s='n ne se s sw nw '
for r in next(open('i')).split(','):i=s.index(r+' ');exec(s[i%9:i%9+2]+"+-"[i//9]+'=1',None,locals());d=max(d,D())
print(D(),d)
▶ No.836204>>836208 >>836214
>>836179
>>836195
These solutions do not end with the same values that I came up with which the website accepted. They are quite far off actually.
Did these actually work for you?
▶ No.836206
This is the path the retarded child took.
▶ No.836208>>836212
>>836204
can you also check >>836196
?
▶ No.836209>>836214
>>836179
> "n": (+0, -1),
> "s": (+0, +1),
North is negative, south positive? Explain yourself.
▶ No.836212>>836215
>>836208
Works great! Just had to delete the trailing newline from the file for it to work.
▶ No.836214>>836215 >>836547
>>836209
Fucked that one up. I thought of a grid where y expands downwards.
>>836204
Both worked for my results. I wonder what's causing the problem?
▶ No.836215>>836216
>>836212
fug
it will cost 1 byte
open('i').read()
instead of
next(open('i'))
I probably deleted the newline myself before starting
>>836214
if I got it right, there are 2 distinct cases in the math model, maybe your input is the other case
▶ No.836216>>836217
>>836215
Which distinct cases? i dond ged id DDDDD:
▶ No.836217>>836240
>>836216
in my interpretation (used in the golfed solution) where I view hex board as regular 2d board with integer coordinates, diagonal moves are allowed in one "axis" (when x and y are changed by (-1,1) or (1,-1)).
one case is when these moves are not used at all (x and y are same sign, or one of them is zero)
other case is when min(|x|,|y|) moves are made by that diagonal and the only other direction to move is either x or y
▶ No.836220
Too easy (again): https://play.rust-lang.org/?gist=606d837723102abe16086eadd33f8d6e
Time: 0.13 ms
fn main() {
let instant = std::time::Instant::now();
let mut pos: (i32, i32, i32) = (0, 0, 0);
let mut max_distance = 0;
for s in INPUT.trim().split(',') {
pos = match s {
"n" => { (pos.0 + 1, pos.1 - 1, pos.2) }
"ne" => { (pos.0, pos.1 - 1, pos.2 + 1) }
"se" => { (pos.0 - 1, pos.1, pos.2 + 1) }
"s" => { (pos.0 - 1, pos.1 + 1, pos.2) }
"sw" => { (pos.0, pos.1 + 1, pos.2 - 1) }
"nw" => { (pos.0 + 1, pos.1, pos.2 - 1) }
_ => { unreachable!(); }
};
max_distance = std::cmp::max(max_distance, distance(pos));
}
let d = instant.elapsed();
println!(
"Part 1: {}\nPart 2: {}\nTime: {} ms",
distance(pos),
max_distance,
(d.as_secs() as f64 + d.subsec_nanos() as f64 / 1000000000.0) * 1000.0
);
}
fn distance(pos: (i32, i32, i32)) -> u32 {
(pos.0.abs() + pos.1.abs() + pos.2.abs()) as u32 / 2
}
▶ No.836240
>>836217
Try this one. I tried to implement it as you said. Also I changed the matrix a little bit. Let me know if it works on your input.
/**
* Copyright m712 2017.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#include <stdio.h>
#include <stdlib.h>
enum move_type {
N, NE, SE, S, SW, NW, EOM
};
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define GROW_CHUNK 8
#define CHECK_GROW(type, arr, len) \
if ((len) % GROW_CHUNK == 0) \
(arr) = realloc((arr), ((len) + GROW_CHUNK) * sizeof(type))
#define PUSH(type, arr, len, item) \
do { \
CHECK_GROW(type, arr, len); \
(arr)[(len)] = (item); \
(len)++; \
} while (0)
#define NOPE \
do { \
printf("Unexpected char %c\n", c); abort(); \
} while (0)
enum move_type *
parse(int *movlen) {
enum move_type *moves = NULL;
int c;
*movlen = 0;
while ((c = getchar()) != EOF && c != '\n') {
if (c == 'n') {
switch(c = getchar()) {
case 'w': PUSH(enum move_type *,moves,*movlen,NW); getchar(); break;
case 'e': PUSH(enum move_type *,moves,*movlen,NE); getchar(); break;
case '\n': case ',': PUSH(enum move_type *,moves,*movlen,N); break;
default: NOPE;
}
continue;
} else if (c == 's') {
switch(c = getchar()) {
case 'w': PUSH(enum move_type *,moves,*movlen,SW); getchar(); break;
case 'e': PUSH(enum move_type *,moves,*movlen,SE); getchar(); break;
case '\n': case ',': PUSH(enum move_type *,moves,*movlen,S); break;
default: NOPE;
}
continue;
} else NOPE;
}
return moves;
}
int
get_steps(int x, int y) {
// move minimum as diagonal, then rest as the diff
if (x*y < 0)
return abs(abs(x) - abs(y)) + min(abs(x), abs(y));
// Just move with axis, because no diagonals
return abs(x + y);
}
void
do_step(enum move_type move, int *x, int *y) {
/**
* N |NE|
* NW|xx|SE
* |SW|S
*/
switch (move) {
case N:
*x -= 1;
*y += 1;
break;
case S:
*x += 1;
*y -= 1;
break;
case NW:
*x -= 1;
break;
case SW:
*y -= 1;
break;
case NE:
*y += 1;
break;
case SE:
*x += 1;
break;
default:
printf("Unexpected move_type %d\n", move);
abort();
}
}
void
solve(enum move_type *moves, int movlen, int *part1, int *part2) {
int x = 0, y = 0;
for (int i = 0; i < movlen; i++) {
do_step(moves[i], &x, &y);
*part2 = max(*part2, get_steps(x, y));
}
*part1 = get_steps(x, y);
}
int
main(int argc, char **argv) {
(void) argc;
(void) argv;
int movlen;
enum move_type *moves = parse(&movlen);
int part1 = 0, part2 = 0;
solve(moves, movlen, &part1, &part2);
printf("Number of moves: %d\n", part1);
printf("Furthest move: %d\n", part2);
free(moves);
return 0;
}
▶ No.836250>>836260
>>836179
>fails to understand clearly worded instructions
>fucking TWICE
>it's the authors fault XDDD
take some english classes, retarded turkroach
▶ No.836260>>836264
>>836250
But it's not just me, other people said he sucks at typing out the puzzles, see >>835364, >>835391, >>835505, >>835526, >>835563
▶ No.836264>>836268 >>836269
>>836260
>other people are retarded too
epic defense bro
day 10 is a lot of text, but it is clearly worded and has fucking step-by-step instructions.
i don't know about you, but i learned reading comprehension in elementary school.
▶ No.836268>>836272
>>836264
jesus fucking christ, you're just saying the same thing over and over again. You have added nothing to the original insult.
you are why this board needs filter-by id.
▶ No.836269>>836272
>>836264
>i'm such a divine person
Keep fellating yourself you cocksucker. People are not perfect and can misread instructions and when you have a lot of people complaining about it you know you're doing something wrong.
sage for replying to obvious rustfag bait
▶ No.836270>>836343
also,
>day 11
>hex grids
if I can proceed to day 12 without getting today done, I will.
▶ No.836272>>836273
>>836268
>i need a safe space because i can't read
>>836269
>>i'm such a divine person
no. i'm able to read.
>People are not perfect and can misread instructions
>a lot of people complaining about it you know you're doing something wrong
how is the author at fault when people don't read the instructions? can you actually provide me with an example of a not clearly worded puzzle?
>rustfag bait
??? what does that even mean and how is rust relevant? are you really that butthurt that you have to bring irrelevant shit into the discussion?
▶ No.836273>>836274
>>836272
>deletes spam
>leans back
>this 'safe space' is so comfy
>I don't have to read
>THE
>SAME
>FUCKING
>THING
>OVER
>AND
>OVER
>AGAIN
▶ No.836274
>>836273
>complains about spam
>writes
>like
>this
lol
▶ No.836277
here's some OCaml that keeps track of total n, nw, sw (the upper-left of the hex) while parsing the input. Turning that into an answer though seems to require the same work I'd hoped to avoid. I don't have time to absorb the universally-referenced hexagonal grid article to get out a solution today.
Would preferred this shit for Saturday morning.
let parse s =
let len = String.length s in
let rec step i n nw sw =
if i >= len then (abs n + abs nw + abs sw, n, nw, sw) else
if i = len - 1 then match s.[i] with
| 'n' -> (abs (n + 1) + abs nw + abs sw, n + 1, nw, sw)
| 's' -> (abs (n - 1) + abs nw + abs sw, n - 1, nw, sw)
| a -> failwith (sprintf "invalid step %d : %c" i a)
else match s.[i], s.[i + 1] with
| 'n', ',' -> step (i + 2) (n + 1) nw sw
| 'n', 'w' -> step (i + 3) n (nw + 1) sw
| 'n', 'e' -> step (i + 3) n nw (sw - 1)
| 's', 'e' -> step (i + 3) n (nw - 1) sw
| 's', 'w' -> step (i + 3) n nw (sw + 1)
| 's', ',' -> step (i + 2) (n - 1) nw sw
| a, b -> failwith (sprintf "invalid step %d : %c %c" i a b)
in step 0 0 0 0
▶ No.836343>>836581
>>836270
Why? It's easier than you're imagining.
▶ No.836541
>>835167
Have you only been completing half of the puzzles? You must log in to get each day’s part 2.
▶ No.836542>>841248
day 11. More pleasant than day 10.
void hex_ed(string_view input)
{
int x = 0, y = 0;
const auto walk = [](string_view dir, int& a, int& b){
if (dir.size() == 1){ ++a; --b; } else if (dir[1] == 'w') --b; else ++a;
};
const auto dist = [&]{ return (x < 0) == (y < 0) ? abs(x) + abs(y) : max(abs(x), abs(y)); };
int maxdist = 0;
for (string_view dir : input | split(by_alpha)){
if (dir[0] == 'n') walk(dir, x, y); else walk(dir, y, x);
if (int d = dist(); d > maxdist) maxdist = d;
}
cout << "part 1: " << dist() << '\n';
cout << "part 2: " << maxdist << '\n';
}
▶ No.836547>>836611
>>836214
>Both worked for my results. I wonder what's causing the problem?
If you want to poke at it yourself here was my input: https://hastebin.com/huvipukori
▶ No.836581>>836593
>>836343
it's depressing. I still don't get hextiles at all, but the cube distance function is enough for this puzzle.
let distance (x2, y2, z2) (x1, y1, z1) =
max (abs (x2 - x1)) (max (abs (y2 - y1)) (abs (z2 - z1)))
let extent = ref 0
let parse s =
extent := 0;
let len = String.length s in
let rec step i x y z =
let d = distance (0, 0, 0) (x, y, z) in
if d > !extent then extent := d;
if i >= len then (x, y, z) else
if i = len - 1 then match s.[i] with
| 'n' -> (x, y + 1, z - 1)
| 's' -> (x, y - 1, z + 1)
| a -> failwith (sprintf "invalid step %d : %c" i a)
else match s.[i], s.[i + 1] with
| 'n', ',' -> step (i + 2) x (y + 1) (z - 1)
| 'n', 'w' -> step (i + 3) (x - 1) (y + 1) z
| 'n', 'e' -> step (i + 3) (x + 1) y (z - 1)
| 's', 'e' -> step (i + 3) (x + 1) (y - 1) z
| 's', 'w' -> step (i + 3) (x - 1) y (z + 1)
| 's', ',' -> step (i + 2) x (y - 1) (z + 1)
| a, b -> failwith (sprintf "invalid step %d : %c %c" i a b)
in step 0 0 0 0
▶ No.836593
>>836581
It's overkill for this problem, but here's more than you could ever want to know about hex tiles.
https://www.redblobgames.com/grids/hexagons/
▶ No.836611>>836630
>>836547
>here's my input
>doesn't give the answer
▶ No.836630
>>836611
Maybe try reading the reply chain next time. The output doesn't matter, but rather the fact that other people's approach's answer did not match my own, while for other people's inputs it did.
My answers are irrelevant, if you think I was just begging I am not as I was in the top 500 fastest solvers for both parts on that challenge.
▶ No.836650>>836662
Today's was pretty boring. The only trouble I had was running into a stack overflow when traversing the list. To fix it I just kept track of all the nodes I had already visited.
▶ No.836651>>836662
>>835328
so this is officially BS
Day 12 (today) was a piece of cake
▶ No.836662>>836706
>>836650
>>836651
314 bytes
could be less but it is boring
from collections import defaultdict as D
n=D(set)
for l in open('i'):
p,r=l.split(' <->');*r,=map(str.strip,r.split(', '));n[p]|={*r}
for a in r:n[a]|={p}
g=0
while n:
p,*_=n.keys();o={p};q={p}
while len(q):
s={*o}
for x in q:c=n[x];o|=c
q=o-s
if'0'in o:print(len(o))
for x in o:del n[x]
g+=1
print(g)
▶ No.836668>>836669 >>836672 >>836674 >>836728
> Muh built-in libraries.
▶ No.836669
>>836668
Ugh I left in something superfluous. PartA can be
Length@ConnectedComponents[g, {0}][[1]]
▶ No.836672>>836673
>>836668
>proprietary software
Stallman doesn't approve
▶ No.836673
>>836672
Made on Mac too. Stallman would love me.
▶ No.836674>>836675
>>836668
At least it's easy to replace macOS with GNU/Linux when you're ready --- a lot of software works on both.
But Mathematica addiction is serious shit, because it doesn't have drop-in replacements AFAIK. Get well soon!
▶ No.836675
>>836674
Well let's be clear, I'm using Mac by choice. Mathematica does run nicely on GNOOO/Linux by the way (Not that it pleases Stallman). My Mathematica addiction is probably inoperable though.
▶ No.836680
#!/usr/bin/env python3
# Copyright m712 2017.
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
import sys
import re
class Program(object):
def __init__(self, id, piped):
self.id = id
self.piped = piped
def __repr__(self):
return "<{}: {}>".format(type(self).__name__, str(self))
def __str__(self):
return "program {} [{}]".format(self.id, ", ".join(map(
lambda x: str(x.id), self.piped)))
def parse(input):
programs = {}
for l in filter(None, input.strip().splitlines()):
id, _, piped = l.split(' ', 2)
id = int(id)
programs[id] = Program(id, map(int, piped.split(', ')))
for p in programs.values():
p.piped = set(programs[x] for x in p.piped)
# Bidirectional pipes so finding groups is O(log(n))
for p in programs.values():
for c in p.piped:
c.piped.add(p)
return programs
# Need to maintain state between recursions so we need this helper function
def get_group(program):
group = set([program])
def add_piped(program):
for p in program.piped:
if p in group: continue
group.add(p)
add_piped(p)
add_piped(program)
return group
def get_all_groups(_programs):
groups = []
# Get a copy
programs = dict(_programs)
# Loop until no more programs
while programs:
# Pop a random one and get groups
_, current = programs.popitem()
group = get_group(current)
# Remove all items in group from programs
for p in group:
programs.pop(p.id, None)
groups.append(group)
return groups
if __name__ == "__main__":
print("Enter input:")
programs = parse(sys.stdin.read())
zero_group = get_group(programs[0])
all_groups = get_all_groups(programs)
print("Length of group which includes 0:", len(zero_group))
print("Count of all groups:", len(all_groups))
This is kinda bulky but whatever. Wasn't too hard.
▶ No.836684>>836756
Fucking graphs man. Gonna optimize it later. Don't want to deal with graphs so early in the morning.
https://play.rust-lang.org/?gist=3caf96ac2b05eda8464c97ffc2426fac
Time: 2.7 ms
Christmas is ruined again
▶ No.836706>>836707 >>836713 >>836715 >>836717
>>836662
why are you measuring the size of the script as if it means anything. the python executable and the memory footprint that's going to create is going to be like 10MB minimum. I like python but you can't claim this.
▶ No.836707
>>836706
sage leftover from old thread
▶ No.836710>>836712
sorry, my code for day 12 is just ridiculous. No effort towards treating this as a graph and being sensible with it. At least, it shows that you can also brute force solutions in OCaml? The language is not too proud to go down into a gutter with you.
let count_rooted input =
let known = Array.make (Array.length input) Unknown in
let mark list status seen =
Hashtbl.iter (fun k _ -> known.(k) <- status) seen;
let rec loop list status =
match list with
| [] -> ()
| n :: rest ->
match Hashtbl.mem seen n with
| true -> loop rest status
| false ->
Hashtbl.replace seen n ();
known.(n) <- status;
loop input.(n) status;
loop rest status in
loop list status in
let rec trace list seen =
match list with
| [] -> ()
| 0 :: _ -> raise Found_root
| n :: rest ->
match known.(n) with
| Rooted -> raise Found_root
| Rootless _ -> raise Found_rootless
| Unknown ->
match Hashtbl.mem seen n with
| true -> trace rest seen
| false ->
Hashtbl.replace seen n ();
trace input.(n) seen;
trace rest seen in
for i = 0 to (Array.length input) - 1 do
let seen = Hashtbl.create 100 in
let list = i :: input.(i) in
try
trace list seen;
(* found neither root nor rootless *)
mark list (Rootless i) seen
with
| Found_root -> mark list Rooted seen
| Found_rootless -> mark list (Rootless i) seen
done;
let seen = Hashtbl.create 10 in
(Array.fold_left (fun acc v -> if v = Rooted then acc + 1 else acc) 0 known,
Array.fold_left (fun acc v -> match v with
| Unknown -> failwith "still unknown at end"
| Rooted -> acc
| Rootless n ->
match Hashtbl.mem seen n with
| true -> acc
| false ->
Hashtbl.add seen n ();
n :: acc) [] known)
Result: (count of members of 0's group; count of non-0 groups)
▶ No.836712>>836716
>>836710
code's missing:
type isrooted = Unknown | Rooted | Rootless of int
exception Found_root
exception Found_rootless
▶ No.836713>>836717 >>836777
>>836706
>the size of the script as if it means anything
You've never heard of code golfing? He's trying to solve the problem in the fewest number of characters.
Code size / Time / Memory size are all valid things to try and optimize, and typically, to go to the extreme for one, you might have to sacrifice the other two.
▶ No.836715>>836777
▶ No.836716>>836719 >>836720
>>836712
10ms
Santa's computer must be *at least* ten times as fast as my laptop, surely?
▶ No.836717
>>836713
that golfed solution is pretty fast though.
>>836706
the fact that it's golfed was also mentioned in the "subject" field of the post.
btw it's funny to see how vastly bigger are the other solutions posted, so much unnecessary code, when the run time will be under 1/10s of second anyway.
▶ No.836719>>836721
>>836716
the golfed solution also takes 10ms on average (if I ignore python's own startup time).
not really good for ocaml.
▶ No.836720>>836736
>>836716
type isrooted = Unknown | Rooted | Rootless of int
let count_rooted input =
let known = Array.make (Array.length input) Unknown in
known.(0) <- Rooted;
let rec trace list seen ans =
match list with
| [] -> ()
| 0 :: rest -> ans := Rooted; trace rest seen ans
| n :: rest ->
match Hashtbl.mem seen n with
| true ->
(match known.(n) with
| Rooted -> ans := Rooted
| Rootless g -> ans := Rootless g
| Unknown -> ());
trace rest seen ans
| false -> Hashtbl.add seen n ();
trace input.(n) seen ans;
trace rest seen ans in
for i = 0 to (Array.length input) - 1 do
if known.(i) = Unknown then
begin
let seen = Hashtbl.create 100 in
let list = i :: input.(i) in
let ans = ref Unknown in
trace list seen ans;
if !ans = Unknown then ans := Rootless i;
Hashtbl.iter (fun k _ -> known.(k) <- !ans) seen
end
done;
let seen = Hashtbl.create 10 in
(Array.fold_left (fun acc v -> if v = Rooted then acc + 1 else acc) 0 known,
Array.fold_left (fun acc v -> match v with
| Unknown -> failwith "still unknown at end"
| Rooted -> acc
| Rootless n ->
match Hashtbl.mem seen n with
| true -> acc
| false ->
Hashtbl.add seen n ();
n :: acc) [] known)
let () =
let start = Unix.gettimeofday () in
for i = 0 to 500 - 1 do ignore (count_rooted input) done;
let (a, list) = count_rooted input in
let stop = Unix.gettimeofday () in
printf "part 1: %d\npart 2: %d\n" a (1 + (List.length list));
printf "That took %.2f (%.6f) s\n" (stop -. start) ((stop -. start) /. 500.)
holy shit.
$ ocamlopt -O3 unix.cmxa day12b.ml -o day12
$ ./day12
part 1: 175
part 2: 213
That took 0.16 (0.000323) s
the refactoring to have trace continue to build seen had no effect. the speed savings only came with the 'if known.(i) = Unknown' in the for loop.
▶ No.836721>>836793
>>836719
grats. OCaml now takes 0.3ms. Got any plans to improve the Python that don't involve writing C?
>so much unnecessary code
You aren't writing Forth, friend. You're writing obfuscated Python. If that scratches any kind of minimalism itch then you're living a lie, like someone taking Heroin and calling it happiness.
▶ No.836728
>>836668
Cleaning up my code for autism's sake.
▶ No.836736>>836756
>>836720
type isrooted = Unknown | Rooted | Rootless of int
let count_rooted input =
let known = Array.make (Array.length input) Unknown in
let rec mark k = function
| [] -> ()
| n :: rest ->
if known.(n) = Unknown then
(known.(n) <- k;
mark k input.(n));
mark k rest in
known.(0) <- Rooted;
mark Rooted input.(0);
for i = 1 to (Array.length input) - 1 do
if known.(i) = Unknown then
(known.(i) <- Rootless i;
mark (Rootless i) input.(i))
done;
let seen = Hashtbl.create 50 in
(Array.fold_left (fun acc v -> if v = Rooted then acc + 1 else acc) 0 known,
Array.fold_left (fun acc v -> match v with
| Unknown -> failwith "still unknown at end"
| Rooted -> acc
| Rootless n ->
match Hashtbl.mem seen n with
| true -> acc
| false ->
Hashtbl.add seen n ();
n :: acc) [] known)
0.1ms over 500 iterations:
part 1: 175
part 2: 213
That took 0.07 (0.000137) s
throw mud at a wall -> notice properties of dripping mud -> take properties into account -> 70x improvement in efficiency. of course it'd be more impressive to not throw mud at the wall in the first place.
sage b/c spam
▶ No.836756>>836768 >>836773 >>836778 >>836813
>>836684
Rewrote it using the excellent petgraph crate: https://play.rust-lang.org/?gist=027c6478395acf08c06558308ca99a9a
Time: 0.68 ms
>>836736
How the FUCK are you managing to do the whole thing in 0.137 ms when it takes me already 0.27 ms to just parse my input???
Is your input really short? Do you have a monster CPU?
https://play.rust-lang.org/?gist=96e2d055b41f6aa1a59983651b62450e&version=nightly&mode=release
▶ No.836768
>>836756
I haven't parsed any input since problem #1, except for where the problem called for it. But OK, parsing raises it to 0.9ms:
let get_input () =
let a = Array.make 2000 [] in
let ch = open_in "day12input.txt" in
let re = Str.regexp "^\\([0-9]+\\) <-> \\(.*\\)$" in
let split = Str.regexp ", " in
for i = 0 to 2000 - 1 do
let line = input_line ch in
assert (Str.string_match re line 0); (* used for side effect *)
assert (Str.matched_group 1 line |> int_of_string = i); (* unnecessary check *)
a.(i) <- (Str.matched_group 2 line
|> Str.split split
|> List.map int_of_string)
done;
close_in ch;
a
I've heard that the Str module isn't great, so this could probably be improved by using another regex module or by doing my own parsing. I just like regex for the readable validation (relatively speaking) that you get along with the parse. Speaking of which, it costs a whole 'nother 0.1ms (so 1ms for the whole thing) to match against this instead:
"^\\([0-9]+\\) <-> \\([0-9]*\\(, [0-9]*\\)*\\)"
▶ No.836773>>836781
>>836756
as for the rest, maybe the problem is too simple for an excellent graphing crate to pay off
▶ No.836777
>>836713
>>836715
thanks, no i haven't heard of code golfing before
▶ No.836778
>>836756
also, you're timing a single run and I'm getting the average of 500 runs in succession.
▶ No.836781
▶ No.836793
>>836721
Sorry, not enough free time to go that far.
▶ No.836813
▶ No.837252>>837256 >>837305
wew, for the first time I made it into the global leaderboard
apparently a lot of people had trouble with this problem, while it's brute forced even in python (pypy) just fine
▶ No.837256
>>837252
I almost got onto the global leaderboard fort he second part. I mistakenly assumed that for the second part that it allowed us to delay at any point, not just the beginning.
▶ No.837258>>837259 >>837260
>>837257
fug, as always forgot some shit
185 bytes
L=[*map(lambda l:[*map(int,l.split(':'))],open('i'))]
o=0
f=1
while f:
s=0;f=0
for d,r in L:
p=r*2-2
if d%p==-o%p:
s+=d*r;f=1
if o:o+=1;break
if o==0:print(s);o+=1
print(o)
▶ No.837259
>>837258
and the runtime on my half dead gaybook with battery removed:
$ time pypy3 aoc.py
1612
3907994
real 0m1.857s
user 0m1.781s
sys 0m0.065s
it's crap but it's faster than implementing a more clever algorithm :D
▶ No.837260>>837262 >>837278
>>837258
Whoops, forgot one more thing.
181 bytes
o=0
f=1
while f:
s=0;f=0
for d,r in [*map(lambda l:[*map(int,l.split(':'))],open('i'))]:
p=r*2-2
if d%p==-o%p:
s+=d*r;f=1
if o:o+=1;break
if o==0:print(s);o+=1
print(o)
▶ No.837262>>837263
>>837260
yeah, on the other hand reading the file many times is quite bad (if it was a named pipe for example, it wouldn't work that way)
▶ No.837263>>837265 >>837267
>>837262
Even though it will be a lot slower from the IO overheard, I did save three bytes from doing that. I also saved another byte from chopping off the final newline. In the end the performance of the golfed program doesn't really matter.
▶ No.837265>>837269
>>837263
I didn't count the final newline anyway, it's just there to have something before "[/code]".
The thing about inlining L is a good catch, I'd also do that, but I tried it once when I fucked up the code with some other error, quickly rolled back and forgot to finally do it again later.
▶ No.837267
>>837263
And it's more about correctness than performance. But of course nobody said that it must support reading from pipes, so count that as just a lame attempt to give an excuse lol.
▶ No.837269
>>837265
>I didn't count the final newline anyway
Oh, I see. I also got rid of the byte for the L in the for loop.
▶ No.837278>>837279 >>837282
>>837260
Can you explain how this works please?
▶ No.837279
>>837278
it simply uses remainder operations to check whether the packet and a scanner will interfere, it is pretty obvious if you think about it
and to find minimum delay, it just uses brute force --- tests each delay starting from 0 until the next delay doesn't hit any scanner.
▶ No.837282
>>837278
The main meat of it is the modulus stuff. Since the scanner moves back and forth we can detect if the scanner is on the first (zeroeth) lines by just doing time % ((length * 2) - 2) == 0.
That's essentially what I used for my solution.
▶ No.837305>>837320 >>837407
>>837252
yeah I read the description and just went to bed
▶ No.837320
>>837305
ocaml:
let part1 layers =
let caught d r = d mod (2 * r - 2) = 0 in
List.fold_left (fun acc (d, r) ->
if caught d r then acc + d * r else acc)
0 layers
let part2 layers =
let rec loop delay =
let caught (d, r) = (d + delay) mod (2 * r - 2) = 0 in
match List.find_opt caught layers with
| None -> delay
| Some _ -> loop (delay + 1)
in loop 0
▶ No.837335
▶ No.837407>>837414 >>837424 >>838133
>>837305
Likewise. Part A is easy modulo arithmetic once you see the pattern. Part B is of course the same, with delays, yet my solution is an ugly brute forced one. Going to try and find a slicker way of completing it.
▶ No.837414>>837419
▶ No.837419
>>837414
It's multiplying the contents of lists two levels deep.
Mathematica is similar to Lisp in that expressions are tuples with a function or tag in the head (car) position. {1,2} is equivalent to List[1,2], which would be (list 1 2) in lisp. The Apply function changes the head, so Apply[F,{1,2}] -> F[1,2]. @@ is a shorthand for Apply, and @@@ for Apply at nesting level 2.
Times@@@{{0,1},{4,6}} -> Times[0,1],Times[4,6]->{0*1,4*6}
▶ No.837424>>837428
>>837407
Nice proprietary software faggot 🐻
▶ No.837428>>837429
>>837424
the furry containment thread is this way >>>832419
▶ No.837429
▶ No.837675>>837679
So today is regurgitation of previous problems. How nice.
▶ No.837679
>>837675
It takes unpractical time if I golf the variable which is costly to recompute. Also, tired of this shit.
531 bytes
R=range
b=set()
for w in R(128):
z=256;*l,=R(z);s=0;p=0;f=0
for r in R(64):
for n in open('i','rb').read()+f'-{w}'.encode()+b'\x11\x1fI/\x17':o=(n+s)%z;l=[*reversed(l[:n]),*l[n:]];l=l[o:]+l[:o];p+=o;s+=1
c=(z-p)%z;l=l[c:]+l[:c];i=int.from_bytes(bytes(eval('^'.join(map(str,l[i*16:i*16+16])))for i in R(16)),'big')
for d in range(128):
if 2**d&i:b|={(d,w)}
print(len(b))
g=0
while b:
g+=1;v=[[*b][0]]
while v:
j=[]
for x,y in v:
try:b.remove((x,y));j+=[(x+1,y),(x-1,y),(x,y+1),(x,y-1)]
except:pass
v=j
print(g)
▶ No.837685
Today's was pretty annoying for a combination of reasons. One, I started late. Two, it reused stuff from a previous challenge. I had already deleted that solution since I succeeded. Three, I had to redo my whole implementation for the second day by actually creating a bitmap. Originally I just used an instruction which counted the amount of 1s in an integer.
▶ No.837688>>837689
>>837687
but can you write that without using built-in algorithms, like a real programmer?
▶ No.837689
>>837688
>It's only real programming if you do it in ASSEMBLY!
I can, but these days I do very little 'real' programming, so while the algorithms would be easy, I'd take me a couple days to get back into writing code, probably a few more if I did C. I'm planning on redoing these in Ada in the near future.
I sometimes wonder if I've forgotten more languages than most will ever learn.
14 done again, with even less coding, using a built in image processing function.
▶ No.837695>>837701
I wouldn't normally recommend reddit, but this thread is funny if you want to watch someone sperging out.
https://www.reddit.com/r/adventofcode/comments/7jpgma/2017_day_14dont_understand_the_puzzle/
▶ No.837698
Solve :: Reddit -> Solution
pfft I'll leave the trivial implementation up to you "real" programmers.
▶ No.837701>>837703
>>837695
lol today's wasn't even worded confusingly. It was one of the few where I didn't need to look at the example to see what the designer even meant.
▶ No.837702
I didn't post C versions of today's one and yesterday's one because it's not really worth it and more than half the code would be memory allocations (implementing vectors and such), also both were pretty easy so I didn't bother.
t. m712
▶ No.837703>>837708
>>837701
This conversation thread is a disaster:
https://www.reddit.com/r/adventofcode/comments/7jpgma/2017_day_14dont_understand_the_puzzle/dr86e3j/
> What is a hash?
> How does a string turn into 32 hex?
> I solved day 10
https://www.reddit.com/r/adventofcode/comments/7jpgma/2017_day_14dont_understand_the_puzzle/dr86tz9/
> What bits?
> I've been programming for 30 years and this is possibly the worst description of a problem I've ever seen.
Imagine being this dumb.
▶ No.837705
https://play.rust-lang.org/?gist=2301423b76215085c1f37d7406e7453c
Time: 6.4 ms
Slightly gay puzzle. Part 1 was cool because i could just use u8::count_ones without actually building the grid but then part 2 fucked it all up.
▶ No.837708>>837713
>>837703
I didn't read everything carefully but it looks like there's almost entire thread of dumb people.
Or that's just fine for reddit?
▶ No.837713
>>837708
It's odd for the AoC sub because there are at least some talented people there. I guess the idiots just pooled into that one thread.
**Reddit on the whole is so retarded I feel bad even linking it. Their news pages are just recitations of:
>MUH MEDICAL 420 BLAZE IT
>Nazi Orange idiot meanie DRUMPF is done for now!!!!!**
▶ No.837728
part 1
module K = Knot (struct
let knot_size = 256
let secret = [|17; 31; 73; 47; 23|]
let rounds = 64
end)
let count_bits_in_string s =
let rec loop i n =
if i < 0 then n else
loop (i - 1) (n + match s.[i] with
| '0' -> 0 | '1' -> 1 | '2' -> 1 | '3' -> 2 | '4' -> 1
| '5' -> 2 | '6' -> 2 | '7' -> 3 | '8' -> 1 | '9' -> 2
| 'a' -> 2 | 'b' -> 3 | 'c' -> 2 | 'd' -> 3 | 'e' -> 3
| 'f' -> 4 | c -> failwith (sprintf "invalid hex digit: %c" c))
in loop (String.length s - 1) 0
let part1 input =
let rec loop n acc =
if n = 128 then acc else
let key = input ^ "-" ^ (string_of_int n) in
loop (n + 1) (acc + count_bits_in_string (K.hash_of key))
in loop 0 0
there's fast bit math to count set bits but I'd rather add that to Knot than turn the string back to numbers.
part2 is going to be ridiculous.
▶ No.837733
part 2
module BitTable =
struct
type t = int array array
let int_of_hexchar = function
| '0' -> 0 | '1' -> 1 | '2' -> 2 | '3' -> 3 | '4' -> 4
| '5' -> 5 | '6' -> 6 | '7' -> 7 | '8' -> 8 | '9' -> 9
| 'a' -> 10 | 'b' -> 11 | 'c' -> 12 | 'd' -> 13 | 'e' -> 14
| 'f' -> 15 | c -> failwith (sprintf "invalid hex digit: %c" c)
let of_knotkey key =
let bt = Array.make_matrix 128 128 0 in
for i = 0 to 127 do
let row = Array.get bt i in
let hash = K.hash_of (key ^ "-" ^ (string_of_int i)) in
for j = 0 to 31 do
let x = int_of_hexchar hash.[j] in
row.(j * 4 + 0) <- (x land 8) lsr 3;
row.(j * 4 + 1) <- (x land 4) lsr 2;
row.(j * 4 + 2) <- (x land 2) lsr 1;
row.(j * 4 + 3) <- x land 1;
done
done;
bt
let count_used bt =
Array.fold_left (fun acc row ->
Array.fold_left (fun acc square -> if square <> 0 then acc + 1 else acc)
acc row) 0 bt
let rec mark_group bt x y n =
if y < 0 || x < 0 || y > 127 || x > 127 || bt.(y).(x) <> 1 then () else
(bt.(y).(x) <- n;
mark_group bt (x + 1) y n;
mark_group bt (x - 1) y n;
mark_group bt x (y - 1) n;
mark_group bt x (y + 1) n)
let mark_groups bt =
let n = ref 2 in
for x = 0 to 127 do
for y = 0 to 127 do
if bt.(y).(x) = 1 then
(mark_group bt x y !n; incr n)
done
done;
!n - 2
end
let part2 input =
let bt = BitTable.of_knotkey input in
BitTable.mark_groups bt
▶ No.838133>>838137
I revisited my day13 solution for part B >>837407.
After plotting their example data, it becomes clear that after the first zero value, each scanner follows consistent periodic cycle (see the bottom left plot plot). Once that offset is known, you can just sieve out multiples of the period. Do that for each scanner, and the first non-zero in your array will be the required offset time.
▶ No.838137
>>838133
Also: Mathematica arrays are 1-based, adjust for your favorite language. Secondly, this solution doesn't check for solutions which occur before the latest period start.
▶ No.838231>>838233
fug less than 10 away from making top 100.
Why are challenges still this easy on day 15?
▶ No.838233>>838234
>>838231
I dunno but I agree, today's challenge is stupid
If it asked for 40*10^12 pairs for example, then it would involve some maths to solve, but today's problem is trivially bruteforced even on shit hardware.
I won't even bother posting code today, this problem is too stupid.
▶ No.838234
>>838233
>even on shit hardware
and even in fucking Python lol
▶ No.838251
Went back and redid the first part in day 15 in haskell because it looked like I could abuse list comprehension. Note that you'll need to import Data.Bits from the standard library for it to work.
length [() | (x, y) <- zip [(65 * 16807^x) `mod` 2147483647 | x <- [1..40000000]] [(8921 * 48271^x) `mod` 2147483647 | x <- [1..40000000]], (x .&. 0xFFFF) == (y .&. 0xFFFF)]
▶ No.838268>>838270
Extremely easy, but my brain doesn't work on mornings. Also fuck integer limits, made me lose 3 minutes.
380 chars
Inspired by python golffag
#include <stdlib.h>
#define H 65536
#define I if(u%H==r%H)
#define Q(n,v) n=(n*v)%2147483647
#define U Q(u,16807)
#define R Q(r,48271)
#define F(n) for(i=0;i<n;i++)
main(int c,char**v){if(c!=3)return 1;int a=atoi(v[1]),b=atoi(v[2]),o=0,m=0,i;long long int u=a,r=b;F(40000000){U;R;I o++;}u=a,r=b;F(5000000){do{U;}while(u%4);do{R;}while(r%8);I m++;}return printf("%d %d\n",o,m),0;}
m712@nextchan:~/advent$ time ./day15 516 190 >/dev/null
real 0m1.046s
user 0m1.036s
sys 0m0.000s
Ideone (https://ideone.com/SdwS1f) reports 0.52s, so the Nextchan box is being shitty. I'll test in on my render rig at home and post benchmarks.
I could probably cut off a few more bytes and optimize it but I don't care. The loops have to be separate (I think) because the generators behave differently.
▶ No.838270>>838296
>>838268
If you are golfing why do you check argc? Also can't you leave out the return in general at the end (might just be a gcc thing though)?
▶ No.838296>>838301
>>838270
Taken into consideration.
330 bytes
#include <stdlib.h>
#define I if(u%65536==r%65536)
#define Q(n,v) n=(n*v)%2147483647
#define U Q(u,16807)
#define R Q(r,48271)
#define F(n) for(i=0;i<n;i++)
#define D u=516,r=190
main(int c,char**v){long long int o=0,m=0,i,D;F(40000000){U;R;I o++;}D;F(5000000){do{U;}while(u%4);do{R;}while(r%8);I m++;}printf("%lld %lld\n",o,m);}
replace numbers in D with your input.
▶ No.838297>>838298
▶ No.838298>>838301
>>838297
To be fair, unless you have a supercomputer this will be hard to compute in 1ms. C solution is faster than yours at 520ms :^)
▶ No.838301>>838325
>>838296
>#define I if(u%65536==r%65536)
#define I if(u<<48==r<<48)
This would work in Rust at least. Don't know if this is UB in C.
>>838298
To be fair, the timings were not taken on the same hardware. Also I'm not doing it in a single loop. I could optimize it a little but it would still be way off from <1ms so why bother.
▶ No.838308
Did this one in Ada (I'm a rank amateur at this language). The cool part is in line 4, where a modular subtype is declared, meaning all operations performed between those types are automatically in modulo 2147483647.
with Ada.Text_IO, Ada.Integer_Text_IO;
use Ada.Text_IO, Ada.Integer_Text_IO;
procedure day15 is
type AOC is mod 2_147_483_647;
Gen_A : constant AOC := 16807;
Gen_B : constant AOC := 48271;
Start_A : constant AOC := 289;
Start_B : constant AOC := 629;
A, B: AOC;
Matches: Integer;
begin -- day15
A := Start_A; B := Start_B;
Matches := 0;
for I in 1 .. 40_000_000 loop
A := A * Gen_A;
B := B * Gen_B;
if (A and 16#FFFF#) = (B and 16#FFFF#) then
Matches := Matches + 1;
end if;
end loop;
Put("PartA: "); Put(Matches); New_line;
A := Start_A; B := Start_B;
Matches := 0;
for I in 1 .. 5_000_000 loop
loop
A := A * Gen_A;
exit when A mod 4 = 0;
end loop;
loop
B := B * Gen_B;
exit when B mod 8 = 0;
end loop;
if (A and 16#FFFF#) = (B and 16#FFFF#) then
Matches := Matches + 1;
end if;
end loop;
Put("PartB: "); Put(Matches); New_line;
end day15;
▶ No.838325>>838330
>>838301
><<48
You're saying it loops around?
▶ No.838330
>>838325
I'm saying shift the lower 16 bits into the uppermost position, pushing out all bits we don't care about.
▶ No.838352
Christmas is ruined, so I played a little bit with the module system.
module type GeneratorDesign =
sig
val factor : int
val init : int
val test : int -> bool
end
module Generator ( GD : GeneratorDesign ) =
struct
type t = { factor : int; mutable last : int }
let make () = { factor = GD.factor; last = GD.init }
let next g =
let rec loop () =
let n = (g.last * g.factor) mod 0x7FFF_FFFF in
g.last <- n;
if GD.test n then n else loop ()
in loop ()
end
module Alice = Generator (struct
let factor = 16807
let init = 277
let test n = n mod 4 = 0
end)
module Bob = Generator (struct
let factor = 48271
let init = 349
let test n = n mod 8 = 0
end)
let alice = Alice.make ()
let bob = Bob.make ()
let judge n =
let matches = ref 0 in
for i = 1 to n do
let a, b = Alice.next alice, Bob.next bob in
if a land 0xFFFF = b land 0xFFFF then
incr matches
done; !matches
let () =
print_int (judge 5_000_000);
print_newline ()
▶ No.838673
Part2 was pretty low effort by the creator.
<uh uh just do part 1 a billion times
<this will surely be a challenge
▶ No.838680>>838684
>one billion
ok I guess I'll at least not parse the string that many times.
type moves = Spin of int | Exchange of int * int | Swap of char * char
let assemble moves =
let moves = String.split_on_char ',' moves in
let whatmove move =
let rest = String.sub move 1 (String.length move - 1) in
match move.[0] with
| 's' -> Spin (int_of_string rest)
| 'x' ->
(match (String.split_on_char '/' rest) with
| [a; b] -> Exchange (int_of_string a, int_of_string b)
| _ -> failwith (sprintf "invalid dance move: %s" move))
| 'p' ->
(match (String.split_on_char '/' rest) with
| [a; b] -> Swap (a.[0], b.[0])
| _ -> failwith (sprintf "invalid dance move: %s" move))
| _ -> failwith (sprintf "invalid dance move: %s" move)
in List.map whatmove moves
... waiting ...
▶ No.838684>>838685 >>838689
>>838680
looks like it's going to take.. 50 hours? well plenty of time to go to sleep then.
▶ No.838685>>838691
>>838684
or enough time for me to attach a hashtbl to this and see that the dance is repeating 42 moves
▶ No.838687>>838688
528 bytes
T=open('i').read().split(',')
A=lambda x:chr(97+x)
B=lambda x:ord(x)-97
F=lambda n:''.join(map(A,n))
E=range
G=tuple
def D(C):
*C,=C
for t in T:
k=t[0]
if k=='s':l=-int(t[1:]);C=C[l:]+C[:l]
else:
t=t[1:].split('/')
if k=='x':a,b=map(int,t);c,d=C[a],C[b]
if k=='p':c,d=map(B,t);e={C[i]:i for i in E(16)};a,b=e[c],e[d]
C[a]=d;C[b]=c
return G(C)
print(F(D(E(16))))
H=G(E(16))
I={H:0}
J=10**9
for i in E(J):
H=D(H)
if H in I:K=H;L=i+1;M=i+1-I[H];break
else:I[H]=i+1
H=K
for i in E((J-L)%M):H=D(H)
print(F(H))
▶ No.838688>>838689
>>838687
-1 byte for stupid read() function
527 bytes
T=[*open('i')][0].split(',')
A=lambda x:chr(97+x)
B=lambda x:ord(x)-97
F=lambda n:''.join(map(A,n))
E=range
G=tuple
def D(C):
*C,=C
for t in T:
k=t[0]
if k=='s':l=-int(t[1:]);C=C[l:]+C[:l]
else:
t=t[1:].split('/')
if k=='x':a,b=map(int,t);c,d=C[a],C[b]
if k=='p':c,d=map(B,t);e={C[i]:i for i in E(16)};a,b=e[c],e[d]
C[a]=d;C[b]=c
return G(C)
print(F(D(E(16))))
H=G(E(16))
I={H:0}
J=10**9
for i in E(J):
H=D(H)
if H in I:K=H;L=i+1;M=i+1-I[H];break
else:I[H]=i+1
H=K
for i in E((J-L)%M):H=D(H)
print(F(H))
▶ No.838689>>838692
>>838684
you are not supposed to do bruteforcing for that much time.
>>838688 this is an example how to do it in ~1 second.
▶ No.838690
may God have mercy on my soul
let dance moves =
let start = ref 0 in
let dancers = Bytes.of_string "abcdefghijklmnop" in
let len = Bytes.length dancers in
let spin n = start := !start + (len - n) in
let exchange a b =
let i = (a + !start) mod len in
let j = (b + !start) mod len in
let c = Bytes.get dancers i in
Bytes.set dancers i (Bytes.get dancers j);
Bytes.set dancers j c in
let swap a b =
let i = Bytes.index dancers a in
let j = Bytes.index dancers b in
Bytes.set dancers i b;
Bytes.set dancers j a in
let dance move =
match move with
| Exchange (a, b) -> exchange a b
| Swap (a, b) -> swap a b
| Spin x -> spin x
in
let moves = assemble moves in
let previous = Hashtbl.create 1000 in
for i = 1 to 1_000_000_000 do
List.iter dance moves;
let return = Bytes.make len ' ' in
let j = ref 0 in
for i = !start to !start + len - 1 do
Bytes.set return !j (Bytes.get dancers (i mod len));
incr j
done;
Bytes.blit return 0 dancers 0 (Bytes.length dancers);
start := 0;
(match Hashtbl.mem previous (Bytes.to_string dancers) with
| true -> print_int i; print_string " : "; print_int (Hashtbl.find previous (Bytes.to_string dancers)); print_string " : "; print_endline (Bytes.to_string dancers);
| false -> Hashtbl.replace previous (Bytes.to_string dancers) i)
done;
Bytes.to_string dancers
fake rotation at the cost of expensive return step. Doing that return step every time because I worried I'd run out of bits to store the offset. The long print_int line was me avoiding Printf.printf because it wasn't flushing enough during the billion-iteration loop. Super messy code but... somehow still preferable code to my messy code in other languages. I feel like I could take this as it is and polish it very easily, without having to give up and rewrite it.
▶ No.838691>>838693 >>838695
>>838685
hmmmm, does it always have loop size = 42? because I also got 42
▶ No.838692>>838696
>>838689
yeah that's totally obfuscated. Are you doing something other than detecting the period of the dances and then calculating what the billionth dance will be from that?
▶ No.838693
>>838691
maybe. I just remembered that the circuit diagram I got while loading today's puzzle included some incorrect math: "9 * 6 = 42". So the meme number is clearly in the guy's head.
▶ No.838695
>>838691
My dance had a period of 24.
▶ No.838696
>>838692
nope, I am only doing exactly that
▶ No.838724
>>838711
Stayed up to write a better version. I saw a comment on reddit mentioning that you can treat the partner swaps separately from the other two kinds. That makes it quite simple (and fast) with built in Mathematica functions for composing permutations.
The only trick is you have to do them separately, and remember that two kinds manipulate index values, and the other manipulates values.
▶ No.838759
$ time ./omg
hklecbpnjigoafmd
real 12m16.506s
user 12m16.526s
sys 0m0.004s
literally one billion dances in 12 minutes, by optimizing the 10k-move dance into a 27-move dance:
utop # input |> assemble |> counterspin |> reexchange |> reswap;;
- : moves list =
[Swap ('a', 'b'); Swap ('b', 'c'); Swap ('a', 'd'); Swap ('a', 'e');
Swap ('d', 'f'); Swap ('d', 'g'); Swap ('b', 'h'); Swap ('h', 'i');
Swap ('b', 'j'); Swap ('e', 'l'); Swap ('a', 'm'); Swap ('l', 'n');
Swap ('n', 'p'); Exchange (0, 1); Exchange (1, 2); Exchange (2, 3);
Exchange (0, 4); Exchange (2, 6); Exchange (1, 7); Exchange (7, 8);
Exchange (5, 9); Exchange (6, 10); Exchange (6, 11); Exchange (2, 12);
Exchange (8, 13); Exchange (12, 15); Spin 8]
The simplest is:
let counterspin moves =
let rec loop moves spin acc =
match moves with
| Spin n :: rest -> loop rest ((spin + (16 - n)) mod 16) acc
| Swap (a, b) :: rest -> loop rest spin (Swap (a, b) :: acc)
| Exchange (a, b) :: rest ->
loop rest spin (Exchange ((a + spin) mod 16,
(b + spin) mod 16) :: acc)
| [] -> List.rev (Spin spin :: acc)
in loop moves 0 []
▶ No.839021>>839025
another day. another circular buffer. another "bruteforce it if you can :^)"
well here's my bruteforce-it-if-I-can code:
class spinlock steps =
object (self)
val mutable buffer = Array.make 60_000_000 0
val mutable at = 0
val mutable length = 1
val mutable n = 1
val steps = steps
method buffer = buffer
method at = at
method length = length
method show =
for i = max 0 (at - 3) to (at - 1) do
Printf.printf "%d " buffer.(i);
done;
Printf.printf "(%d)" buffer.(at);
for i = at + 1 to min (min (at + 4) (Array.length buffer - 1)) (length - 1) do
Printf.printf " %d" buffer.(i);
done; print_newline ()
method step = at <- (at + steps) mod length
method expand =
let newbuffer = Array.make (2 * length) 0 in
Array.blit buffer 0 newbuffer 0 length;
buffer <- newbuffer;
method insert =
if (n land 0xFFFF) = 0 then (Printf.printf "inserting %d\n" n; flush stdout);
self#step;
if length = (Array.length buffer) then self#expand;
Array.blit buffer at buffer (at + 1) (length - at);
buffer.(at + 1) <- n;
at <- at + 1;
length <- length + 1;
n <- n + 1
end
let p =
let p = new spinlock 3 in
p#show;
p#insert;
p#show;
p#insert;
p#show;
p#insert;
p#show;
p
let part1 =
let p = new spinlock 301 in
for i = 1 to 2017 do
p#insert
done;
p#show;
p
let part2 =
let p = new spinlock 301 in
for i = 1 to 50_000_000 do
p#insert
done;
p#show;
Printf.printf "after zero: %d\n" p#buffer.(1);
p
while I wait five hours for that to run...
you know, insertion is really expensive with an Array and this thing inserts constantly. hmm.
▶ No.839024
Day 17 was very straight forward, won't bother posting the code.
▶ No.839025>>839026 >>839029
>>839021
Spoiler: You don't need to insert for part b
▶ No.839026>>839027
>>839025
ha. you think you can spoil me? you think I understand anything after reading the spoiler? I understand nothing!
nothing!
▶ No.839027>>839028
>>839026
I'm not sure if you're serious, but you'll kick yourself when you see how easy part b is.
▶ No.839028>>839030
>>839027
completely serious. halfway through brute-forcing it with a circular list, m8.
▶ No.839029
>>839025
It was pretty obvious
Unless someone is a brainlet
▶ No.839030>>839032
>>839028
What position would you have to be in, to insert something after the zero?
▶ No.839032>>839033
>>839030
the puzzle says
>What is the value after 0 the moment 50000000 is inserted?
there's no connection made there between zeor and position you insert 50mil to.
>After a tree falls, what's in my pocket?
OOOH obviously the tree is in your pocket!
what?
▶ No.839033>>839034 >>839035
>>839032
What position is always after the 0?
▶ No.839034
>>839033
*after as in, adjacent to.
▶ No.839035>>839037 >>839039
>>839033
position 1. what does that tell me about what's inserted in position 1? if 'step' takes the spinlock back to zero, then what it inserts becomes the new position 1. It can do that a number of times on its way to 50mil. That number of times can probably be mathed out. I do nazi the obvious thing here.
▶ No.839037>>839038
>>839035
Yes, position 1. So perhaps you only need to remember the last value to be inserted at position 1
▶ No.839038>>839042
>>839037
and that saves me from inserting 50mil times, how?
▶ No.839040>>839042 >>839043
>>839039
I hope there are multiple people jeering at me and not just one guy who thinks that remembering what I insert means I don't have to insert things after I explained that position 1 can be replaced multiple times throughout the spin.
▶ No.839042>>839043 >>839044 >>839062
>>839038
It's the insert that is slowing you down. You still need to iterate 50 million times, but you only need to track one number.
>>839040
Multiple people. Me Mathematica poster and some other guy who I assume is the Rustfag from use of the term brainlet.
▶ No.839043
>>839040
Multiple people, not counting the ones said in
>>839042
Literally the only difference between the two solutions is a simple if statement
▶ No.839044>>839046
>>839042
... oh.
ok. I get it now.
▶ No.839047>>839120
$ time ./day17b
(50000000) 4970712 8649148 1386265
after zero: 33601318
real 5m2.388s
user 5m2.214s
sys 0m0.232s
using this buggy code:
class spinlock steps =
object (self)
val mutable buffer = (let rec xs = 0 :: xs in xs)
val mutable zero = []
val mutable n = 1
val steps = steps
method buffer = buffer
method zero = zero
method show =
Printf.printf "(%d)" (List.hd buffer);
for i = 1 to 3 do
Printf.printf " %d" (List.nth buffer i);
done; print_newline ()
method step = for i = 1 to steps do buffer <- List.tl buffer done
method insert =
self#step;
Obj.set_field (Obj.repr buffer) 1 (Obj.repr (n :: (List.tl buffer)));
buffer <- List.tl buffer;
n <- n + 1
initializer zero <- buffer
end
That Obj. line is magic and apparently the magic causes weird things to happen if multiple spinlocks are created. So I only got the correct answer after commenting out the earlier test runs. Still, inserting into a circular list by mutation in a functional language is nearly as cheaty as the no-data solution... right?
▶ No.839062
>>839042
>some other guy who I assume is the Rustfag from use of the term brainlet
Nope, I am not him
▶ No.839097
>>839095
You can do that way more elegantly in Rust:
if &buf[..4] == b"GET " {
doing_get = true;
index = 4;
} else if &buf[..5] == b"HEAD " {
doing_get = false;
index = 5;
}
▶ No.839103>>839107
>>839079
ugly and unreadable wiith none of the benefits of a language that actually requires something that looks like functional syntax
▶ No.839107
>>839103
Sure thing anti Rust shill. I'm a #cmissile now
▶ No.839113>>839114
>>839095
>PRINGLES
>white men breathtakingly admiring literal pajeet Java
▶ No.839115>>839117
>>839114
it's casting chars to byte
you do that in Java because chars are 16-bit whereas bytes are 8-bit
you don't do that in C because bytes aren't a thing and the explicit cast does nothing to benefit the numeric comparison
▶ No.839117>>839120
>>839115
oh shit you're right
▶ No.839120
>>839117
oh also the +'ing of strings together. I know that the code is shockingly low-level-looking but actually it's just shit. C can look much better than that.
>>839047
oh, I thought of this while coding but found out how to do the magic thing and went with it instead, but you can avoid magic and bugs by defining your own list type (which doesn't need an empty-list variant in this case). With record types the code actually looks slightly cleaner than it does working with a literal list. and it's not any slower.
▶ No.839140>>839210
reddit:
>I've been doing these in Haskell the first 15 days but I'm honestly quite fed up having to find ways to optimize this and that so that things run in reasonable amounts of time so here it is in Javascript lol
▶ No.839141>>839156
(import (srfi srfi-1) (ice-9 receive))
(define (list-insert lst pos val)
(receive (head tail)
(split-at lst pos)
(append head (cons val tail))))
(define* (part1 stride count #:optional (lst '(0)) (state 1) (pos 0))
(if (positive? count)
(let* ((new-pos (modulo (+ 1 pos stride) state))
(new-lst (list-insert lst (1+ new-pos) state)))
(part1 stride (1- count) new-lst (1+ state) new-pos))
(values lst (1+ pos))))
(define* (part2 stride count #:optional (ans -1) (state 1) (pos 0))
(if (positive? count)
(let ((new-pos (modulo (+ 1 pos stride) state))
(new-ans (if (zero? pos) (1- state) ans)))
(part2 stride (1- count) new-ans (1+ state) new-pos))
ans))
(let ((stride (read)))
(receive (lst pos)
(part1 stride 2017)
(format #t "~A\n~A\n" (list-ref lst (1+ pos)) (part2 stride 50000000))))
▶ No.839156>>839160
▶ No.839160>>839538
>>839156
even worse.
with that 'ice-9'
I believe it is Guile
▶ No.839210>>839251
>>839140
Haskell programmers are just desperate to be acknowledged (used to be one and writing slick haskell code is often a false sense of accomplishment), there was a guy the other day showing off his haskell solution saying: It features clever use of a monoid!, p-p-please like me.
▶ No.839251>>839259 >>839282
>>839210
haskell is gay, everyone can write it after 5 day crash course.
real badass fuckers write distrubided fault tolerant 99.999% uptime systems in Erlang. :D
▶ No.839259
>>839251
erlang is gay, everyone can write it after 5 day crash course.
real badass LARPers write distrubided fault tolerant 99.999% uptime posts on /tech/. :D
▶ No.839282
>>839251
> everyone can write it after 5 day crash course
And then another 5 years in academia where you right papers on type systems, and proving that you can use Haskell's type system to solve Rubiks cube puzzles, replete with category theory you learned and now need to find an excuse to use.
I like Erlang, and in that case, a sufficiently talented programmer could teach themselves it in 5 days. It's a small language.
▶ No.839538
>>839160
>even better
ftfy
Guile is the official extension language of GNU.
▶ No.839567>>839569
In 2nd part of day 18, is simply executing these codes viable?
Mine doesn't terminate, I mean the lower bound of the answer gets over 1 million and I am not sure how long I should wait
▶ No.839569>>839576
>>839567
now it's larger than 6 millions
▶ No.839571>>839578 >>839581 >>839587
real cool day.
unfortunately my part 2 answer isn't accepted.
nothing to do but stare at code until error is apparent.
open Printf
type arg = Lit of int | Reg of int
type instruction =
| Send of arg
| Set of arg * arg
| Add of arg * arg
| Mul of arg * arg
| Mod of arg * arg
| Receive of arg
| Jump of arg * arg
let assemble code =
let lines = String.split_on_char '\n' code in
let reg s =
assert(String.length s = 1);
let c = s.[0] in Reg (int_of_char c - int_of_char 'a') in
let lit s = Lit (int_of_string s) in
let arg s =
if String.length s > 1 then lit s else
if s.[0] < 'a' || s.[0] > 'z' then lit s else
reg s in
let decode line =
match String.split_on_char ' ' line with
| ["snd"; x] -> Send (reg x)
| ["set"; x; y] -> Set (reg x, arg y)
| ["add"; x; y] -> Add (reg x, arg y)
| ["mul"; x; y] -> Mul (reg x, arg y)
| ["mod"; x; y] -> Mod (reg x, arg y)
| ["rcv"; x] -> Receive (reg x)
| ["jgz"; x; y] -> Jump (arg x, arg y)
| _ -> failwith (sprintf "invalid instruction: %s" line) in
List.map decode lines |> Array.of_list
type state = Ready | Sending of int | Receiving of int | Halted
type program = {
pid : int;
mutable code : instruction array;
mutable at : int;
mutable registers : int array;
mutable state : state;
mutable mailbox : int list
}
let p0, p1 =
let instr = assemble Day18input.input in
let r0, r1 = Array.make 256 0, Array.make 256 0 in
let reg_pid = int_of_char 'p' - int_of_char 'a' in
r0.(reg_pid) <- 0;
r1.(reg_pid) <- 1;
({ pid=0; code=instr; at=0; registers=r0; state=Ready; mailbox=[] },
{ pid=1; code=instr; at=0; registers=r1; state=Ready; mailbox=[] })
let part2 = ref 0
let run p =
let delit = function
| Lit x -> x
| Reg x -> p.registers.(x) in
let rec next () =
p.at <- p.at + 1;
loop ()
and loop () =
if p.at < 0 || p.at >= Array.length p.code then p.state <- Halted else
match p.code.(p.at) with
| Send a -> p.state <- Sending (delit a); p.at <- p.at + 1;
| Set (Reg a, b) -> p.registers.(a) <- delit b; next ()
| Add (Reg a, b) -> p.registers.(a) <- p.registers.(a) + delit b; next ()
| Mul (Reg a, b) -> p.registers.(a) <- p.registers.(a) * delit b; next ()
| Mod (Reg a, b) -> p.registers.(a) <- p.registers.(a) mod (delit b); next ()
| Receive (Reg a) -> p.state <- Receiving a; p.at <- p.at + 1;
| Jump (a, b) -> if delit a > 0 then (p.at <- p.at + delit b; loop ()) else next ()
| Set (Lit _, _) | Add (Lit _, _) | Mul (Lit _, _) | Mod (Lit _, _) | Receive (Lit _)
-> failwith "invalid instruction - literal provided when register expected"
in loop ()
let runboth () =
let rec loop () =
match (p0.state, p1.state, p0.mailbox, p1.mailbox) with
| (Halted, Halted, _, _) -> ()
| (Halted, Ready, _, _) -> run p1; loop ()
| (Ready, Halted, _, _) -> run p0; loop ()
| (Ready, Ready, _, _) -> run p0; run p1; loop ()
| (Receiving a, _, x :: mb, _) ->
p0.registers.(a) <- x;
p0.mailbox <- mb;
p0.state <- Ready;
loop ()
| (_, Receiving a, _, x :: mb) ->
p1.registers.(a) <- x;
p1.mailbox <- mb;
p1.state <- Ready;
loop ()
| (Sending a, _, _, _) ->
p1.mailbox <- a :: p1.mailbox;
p0.state <- Ready;
loop ()
| (_, Sending a, _, _) ->
incr part2;
p0.mailbox <- a :: p0.mailbox;
p1.state <- Ready;
loop ()
| (Receiving _, Receiving _, [], []) ->
printf "part 2: %d\n" (!part2);
failwith "deadlock by mutual receive"
| (Receiving _, Ready, [], _) -> run p1; loop ()
| (Ready, Receiving _, _, []) -> run p0; loop ()
| (Receiving _, Halted, [], _) ->
printf "part 2: %d\n" (!part2);
failwith "deadlock with p0 receiving from halted p1"
| (Halted, Receiving _, _, []) ->
printf "part 2: %d\n" (!part2);
failwith "deadlock with p1 receiving from halted p0"
in loop ()
let () = runboth ()
▶ No.839576>>839580
>>839569
Now I rearranged the code and it started to work. Seems like I seriously fucked up it the first time when I decremented pointers instead of using continue to skip the rest of the loop when needed.
▶ No.839578>>839580
>>839571
> | ["snd"; x] -> Send (reg x)
trying it against the example shows that this should be 'arg x'. there wasn't a literal in my input... so no change to behavior on my input. I get the correct answer for the test code though.
▶ No.839580>>839585
>>839576
Too lazy to golf today, I already got fucked in the ass by 1.5 hours of debugging. But I got the accepted answer.
from collections import defaultdict, deque
def parse_line(l):
return tuple(map(str.strip, l.split(' ')))
instructions = [parse_line(l) for l in open('i')]
registers = [defaultdict(lambda: 0) for _ in range(2)]
pipes = [deque() for _ in range(2)]
instruction_ptr = [0, 0]
locked = [0, 0]
current_pid = 0
def get_value(x):
try:
return int(x)
except:
return registers[current_pid][x]
answer = 0
registers[0]['p'] = 0
registers[1]['p'] = 1
code_length = len(instructions)
while 0 <= instruction_ptr[0] < code_length or 0 <= instruction_ptr[1] < code_length:
ip = instruction_ptr[current_pid]
if ip >= code_length or ip < 0:
locked[current_pid] = 1
current_pid ^= 1
continue
assert 0 <= ip < code_length
c, *a = instructions[ip]
if c == 'set':
registers[current_pid][a[0]] = get_value(a[1])
elif c == 'snd':
pipes[current_pid].append(get_value(a[0]))
if current_pid: answer += 1
elif c == 'add':
registers[current_pid][a[0]] += get_value(a[1])
elif c == 'mul':
registers[current_pid][a[0]] *= get_value(a[1])
elif c == 'mod':
registers[current_pid][a[0]] %= get_value(a[1])
elif c == 'rcv':
try:
v = pipes[1 - current_pid].popleft()
registers[current_pid][a[0]] = v
except IndexError:
locked[current_pid] = 1
current_pid ^= 1
if locked[current_pid] and not pipes[1 - current_pid]:
break
continue
else:
if get_value(a[0]) > 0:
instruction_ptr[current_pid] += get_value(a[1]) - 1
locked[current_pid] = 0
instruction_ptr[current_pid] += 1
print(answer)
>>839578
You may compare the result with my code, if they differ then maybe you can guess what went wrong.
▶ No.839581
>>839571
> p1.mailbox <- a :: p1.mailbox;
woops that's a fifo mailbox, not a lifo mailbox. fixed... and no change to my answer.
▶ No.839585
>>839580
ok. yours also doesn't allow the IP to run outside the instruction array. your modulo answers are the same as mine. that's what I've tried varying on so far, so it helps to know there's no shenanigans there (probably).
▶ No.839587>>839588
>>839571
*sigh* checked the subreddit for people bitching about problems they had
oh hey as of part2 rcv is no longer a no-op if the arg is 0
▶ No.839588>>839589
>>839587
uh, no that wasn't my problem.
I just edited the test out of the Jump instruction. true, it is adjacent to Receive...
▶ No.839589>>839590 >>839616
>>839588
536870912 * 2 = -1073741824
motherfucker.
▶ No.839590>>839591
>>839589
are you not using unlimited size integers by default?
sucks to be you
▶ No.839591>>839592 >>839599
>>839590
unlimited size integers is a bad default and it is irresponsible and biased and probably hateful for this contest to support them.
fix:
<add "open Num" to top of program
<add "-package num -linkpkg" to compilation step
no other code changes at all :^)
▶ No.839592>>839594
>>839591
>unlimited size integers is a bad default
really?
since when?
it's a lot worse when your shit overflows silently
▶ No.839594>>839598
>>839592
a bug is unexpected behavior. If your head is in the clouds you'll be surprised by floating point and fixed-width numerics. If you're working with a particular architecture you'll expect exactly that. It's not like I enjoyed losing 40 minutes to a silent overflow, but I also didn't enjoy having a serious project never get released at all because the performance was never good enough.
▶ No.839597
I was stuck on today's until I realized stuff like jgz 2 1 is a valid instruction. All the examples always had jgz read from a register so I thought I could leave out that case.
▶ No.839599>>839626
>>839591
>no other code changes at all
fug I only needed 63 bits for this.
somehow I was using /usr/local/bin/ocaml with only 31 bits.
>>839598
>performance has never mattered for me
grats.
▶ No.839615
Abused dynamic scoping so I could reuse most of my part A code.
▶ No.839616>>839618
Oh boy what a mess.
https://play.rust-lang.org/?gist=139a9543fb81e22dff5a419b51f6de03
>>839589
Thanks to Rust checking arithmetic in debug mode I didn't have this problem.
▶ No.839618>>839620 >>839623
>>839616
Thanks to Mathematica, "what is overflow?
▶ No.839620>>839621 >>839624
>>839618
It is something only blazingly fast languages have.
▶ No.839621>>839627
>>839620
Python is also fast (if you use appropriate implementation for the task) and it doesn't overflow.
▶ No.839623>>839628
>>839618
>what is overflow
It is a feature of the cpu.
▶ No.839624
>>839620
Heh. Mathematica does of course have a notion of 'Machine Integers', but they're for rare occasions.
▶ No.839626>>839650
>>839599
do you know that premature optimization is ass?
optimization should be done when it is justified somehow, and you are simply wasting time here.
▶ No.839627>>839629
>>839621
>Python is also fast
ok
▶ No.839628
>>839623
Yes yes, the joke was that mathematica automatically converts to big integers whenever needed.
▶ No.839629>>839630
>>839627
if you can't use it efficiently, it's your problem
▶ No.839630>>839633
>>839629
The only way to make a Python project fast is by rewriting it in a fast language.
▶ No.839633>>839645
>>839630
only for a few kinds of projects
why do you continue asserting things in a topic where you clearly lack knowledge and experience?
▶ No.839644
>>839636
at least he didn't use AppleScript
▶ No.839645>>839646 >>839647
>>839633
>why do you continue asserting things in a topic where you clearly lack knowledge and experience?
you started with "python is fast". how about you back your claim up?
protip: you can't
▶ No.839646>>839649
>>839645
I can't be bothered to spoonfeed you,
at first please try searching the web for the following keywords for example:
pypy
numpy
numba
cython
opencl+python
▶ No.839647>>839649
>>839645
also you should understand that the "speed" is a property of an implementation and not a language
▶ No.839649
>>839646
>I can't be bothered to spoonfeed you,
Then stop making baseless claims.
>pypy
>numba
>cython
>opencl+python
Still slower than using a real language.
>numpy
>C 53.7%
So, is this the power of Python?
>>839647
Wrong. Demonstrated by the lack of fast python implementations.
▶ No.839650>>839651 >>839652
>>839626
why are you telling me common wisdom like I've never heard of it? Is this some roundabout way of asking me to explain how it can possibly be that Santa isn't real?
programming is a field that has incredibly poor tools. If you choose them, out of some phobia for optimization, then it can be so hard to make a product that is good that the effort will be aborted. programming is not so refined that the deficiencies of those tools will actually have sufficient compensating advantages sufficient. For a woodcutter to choose steel over rotten cursed plague-bearing wood is not 'premature optimization'; it is 'having basic faculties of perception'.
▶ No.839651
>>839650
hahaha just kidding kids Santa is totally real.
But programmer common wisdom is mostly bullshit.
▶ No.839652
>>839650
define "good product" then
apparently what I do gets me good money, so it must be good right?
▶ No.840213>>840215
Today's was pretty simple since the line had no loops you had to worry about. Part 2 was trivial since you just add a counter to it.
▶ No.840214
cool. we're implementing befunge today (or something much less interesting than that, but befunge-inspired features might show up for part 2)
ocaml will be much delayed.
▶ No.840215
>>840213
aw, I guess not about befunge then.
▶ No.840221>>840227 >>840229 >>840231
Started on time for once, rank 282.
▶ No.840227>>840229 >>840230
>>840221
btw I got rank 259 on part 2 :D
▶ No.840229>>840232
>>840221
For autism's sake, I should have replaced that If after the switch with another switch clause,
:_?LetterQ, Sow[at]
>>840227
Do solve it normally and golf afterwards?
▶ No.840230>>840235
I don't know if it would save space, and correct me if this is what you are doing. I kept track of a dx / dy and for getting the new direction I would either swap dx and dy, or swap them and then negate both of them.
>>840227
I got 141
▶ No.840231>>840233 >>840240
>>840221
349 bytes
a=(*open('i'),)
x=a[0].index('|')
y=0
b=0
z=0
c=1
e=[]
k=lambda f,g:0<=g<len(a)and 0<=f<len(a[g])
while k(x,y):
d=a[y][x]
if d=='+':
for f,g in(0,1),(1,0),(0,-1),(-1,0):
if(f,g)!=(b,c)and(-f,-g)!=(b,c):
h=x+f;i=y+g
if k(h,i)and a[i][h]!=' ':b=f;c=g;break
if d==' ':break
if d not in'|-+ ':e+=[*d]
x+=b;y+=c;z+=1
print(''.join(e),z)
▶ No.840232
>>840229
>Do solve it normally and golf afterwards?
of course. it's only moderately golfed at first.
▶ No.840233>>840235
>>840231
It's been a while since I've used Python, but can't you do a multiple assignment to zero for y,b,z ?
▶ No.840235>>840299
>>840230
I could get higher but I had to take a dump right in the middle of the coding.
>>840230
> I kept track of a dx / dy and for getting the new direction I would either swap dx and dy, or swap them and then negate both of them.
Not sure about golf score and too lazy to check now, but it could be more efficient
>>840233
afaik only like this
a,b,c=[0]*3
it'll start being profitable only with more variables
▶ No.840240>>840245
>>840231
more golfing
323 bytes
a=(*open('i'),)
x=a[0].index('|')
y=0
b=0
z=0
c=1
e=[]
k=lambda f,g:0<=g<len(a)and 0<=f<len(a[g])
while k(x,y):
d=a[y][x]
if d=='+':
for f,g in{(0,1),(1,0),(0,-1),(-1,0)}-{(b,c),(-b,-c)}:
h=x+f;i=y+g
if k(h,i)and a[i][h]!=' ':b=f;c=g
if d==' ':break
if d not in'|-+ ':e+=[*d]
x+=b;y+=c;z+=1
print(''.join(e),z)
▶ No.840245>>840256 >>840257
>>840240
don't use list for letters, put them directly into str
311 bytes
a=(*open('i'),)
x=a[0].index('|')
y=0
b=0
z=0
c=1
e=''
k=lambda f,g:0<=g<len(a)and 0<=f<len(a[g])
while k(x,y):
d=a[y][x]
if d=='+':
for f,g in{(0,1),(1,0),(0,-1),(-1,0)}-{(b,c),(-b,-c)}:
h=x+f;i=y+g
if k(h,i)and a[i][h]!=' ':b=f;c=g
if d==' ':break
if d not in'|-+ ':e+=d
x+=b;y+=c;z+=1
print(e,z)
▶ No.840256
>>840245
apparently compression only makes things worse with small programs, but it can be used to put anything at all in one line.
import base64,gzip;exec(gzip.decompress(base64.b85decode(b'ABzY8Zm>970{=aa!EVDK42I9)DcA`ZWFpt5ev*g-1V~UaQbm<U()QhFR%r)Y`hLs*Z(HD>+bv|y5)(?00(Q{mD`g)FXHO=`0h&0h6KjNy1YnFTu-b3uEsbir=qpUu6+Nu5*;B;$#$hso{LE<$bm2uE;zAma0f!liAx(<Z12D-@ZsN9AGn(>)Yt;$GJEgH})mCULz1jzNYOLr~JBn9bY-T7j_6ZI-RYcc?&no@hVuxgg*?a(_?BXEyBTWCnRoa7H-U7|r9n;yfl{g3zJZXvq*B=tb{*?IoZBO~mgF3}8Vc5^|Hvs?u')))
▶ No.840257>>840258 >>840260
>>840245
Can you save a byte by removing the + from the third to last line?
▶ No.840258>>840260
>>840257
also what about replacing index on the second line with find?
I don't know python but there just happened to be a find function that works in this case lol****
▶ No.840260>>840263
>>840257
nope, only if I add more characters in other places, to exit early in other branches
>>840258
yeah this is a good catch
▶ No.840263>>840264
>>840260
>nope, only if I add more characters in other places, to exit early in other branches
Could you at least get rid of the space then, since it would have already breaked in the if statement above?
▶ No.840264
>>840263
sure, yes
I should have read it more carefully, but I'm still sleeping
▶ No.840268>>840271 >>840273 >>840277
why you nerds do this shit for free ahah while you fags were doing autism puzzles you could have been trading cryptos for 1000% gains instead
▶ No.840271>>840274
>>840268
because we can; and you can only produce noise.
▶ No.840273>>840275
>>840268
>implying I'm not doing this on company time
>implying I'm not competing with other coworkers on our companies leaderboard
>implying I'm not winning
▶ No.840274>>840276 >>840278
▶ No.840275
>>840273
>implying i didn't just make more in one trade than you did wagecucking all day
▶ No.840276>>840278 >>840280
>>840274
unless you don't control cryptos markets, you can't win anything on average, it is more like casino b.c. your decisions to trade are arbitrarily crippled by transaction delays which are only really controlled by (((them)))
at this point the only winning move is not to play
▶ No.840277
▶ No.840278
>>840274
>>840276
…so, you're either a LARPer or a lucky bastard which will eat a dick next time when luck is not on your side
▶ No.840283>>840284
>>840280
you're in a wrong thread dude
it's not really intended for brainlets and low effort trolls
▶ No.840289
▶ No.840297
Could you just not reply to the nigger???
▶ No.840299>>840350
>>840235
a=b=c=0 also works
▶ No.840350
>>840299
thanks, idk why I missed it
▶ No.840508>>840509
>>840326
>that readability
What the fuck were they thinking?
▶ No.840509>>840511
>>840508
white background is racist
▶ No.840511>>840513
>>840509
I meant Rust's syntax my dude
▶ No.840513>>840523
>>840511
but it's just fine
▶ No.840523>>840530
>>840513
if b'|' => ((you) say!) so[#~|b].unwrap();
▶ No.840530>>840538
>>840523
Sorry, but that does not compile. You are a pretty awful anti Rust shill.
▶ No.840538>>840548 >>840564
>>840530
I like the idea of Rust and I've tried to get into it, but the syntax is just... The need of constant unwrapping and hop jumping is off-putting to me.
I would like this philosophy in a language to be implemented better, that's all.
Even writing Haskell or Lisp is a smoother experience than this, sorry.
▶ No.840548
>>840538
>The need of constant unwrapping
No. You don't unwrap in serious code.
>hop jumping
???
>I would like this philosophy in a language to be implemented better, that's all.
Ada
▶ No.840564>>840579 >>840586
▶ No.840579>>840599 >>840615
>>840564
No. Thank you.
I have made up my mind about Rust. I'm not shilling anything. I just don't like it despite having wanted and tried to. If it becomes more comfortable to write without convoluted syntax then I'll look at it again.
>To “unwrap” something in Rust is to say, “Give me the result of the computation, and if there was an error, panic and stop the program.” It would be better if we showed the code for unwrapping because it is so simple, but to do that, we will first need to explore the Option and Result types. Both of these types have a method called unwrap defined on them.
I mean, if I want the "result of a computation", why do I have to .unwrap() instead of the compiler doing it automatically, erroring, panicking and everything on its own?
I think this language is not well thought-out. It feels like half its syntax is the result of after-thoughts and corner cases.
Again, it's my fucking opinion and you can use the language if you want. I'll stick to using the software made with it.
▶ No.840586>>840594 >>840599
>>840564
>when some blue haired moron decided it is a good idea for the compiler to try and force you to do error handling but instead you end up shitting up your code with unwrap and runtime panics everywhere
Rust really is full to the brim with retarded design decisions.
▶ No.840594
>>840586
Fitting, as the life of a SJW is probably a sequence of random panics.
▶ No.840599>>840934
>>840579
>>840586
Wow are you serious or just pretending to be retarded? I already said that you dont use unwrap in real code.
Typical anti Rust shilling tactics. Going full >muh syntax without realizing that C/C++ are even uglier.
▶ No.840615>>840618 >>840938 >>841059
>>840579
Man I'd sure love that Result could blow up in my face when I'm not careful if it implicitely unwrapped. In actual code nobody uses unwrap, but instead you'll have a lot of ? flying around.
fn gay_shit() -> Result<i32, Error> {
// ? returns early from a function if the Result is Err as Err
let mut thing = BufReader::new(File::open("nigger")?);
// same thing as let a = dothing(&mut thing)?;
let a = match dothing(&mut thing) {
Ok(a) => a,
Err(e) => return Err(e),
};
// x::dicks returns a Result<String, Error>
// if any of the calls to dicks errors, it will return the Error
// otherwise thing will be a Vec<String>
let thing = a.map(|x| x.dicks()).collect::<Result<Vec<_>, Error>>()?;
// ? also works in functions returning Option
fn thething(v: &Vec<String>) -> Option<i32> {
// ok converts Result to Option and throws away the Err
v.iter().last()?.parse().ok()?
}
// Options can also be promoted to Results
thething(&thing).ok_or(Eror::Error)
}
Why did I even write that? You'll just complain about how the compiler doesn't automatically derive all error handling by reading your mind.
▶ No.840618
>>840615
>v.iter().last()?.parse().ok()?
truly patrician syntax
▶ No.840808>>840813
OCaml and M-x htmlfontify-buffer
▶ No.840813>>840825
>>840808
OCaml syntax does look nice. Is OCaml free from a lot of the intellectual masturbation you find in Haskell? Muh Monad transforms, applicative functors etc..
▶ No.840825
>>840813
remarkably masturbation-free. It doesn't even have the compose operator in the standard lib, so pointfree Haskell programmers find it disconcerting. There's a video about you can sort of get "monad-generic programming" through abuse of functors, that's the worst I've seen. And there are some 'monadic' libraries that aren't that bad. I don't know what "applicative functor" means in general, but 'functors' in OCaml aren't bullshit, they're just an advancement of the module system; this is an example from the last thread:
module type KnotDesign =
sig
val knot_size : int
val secret : int array
val rounds : int
end
module Knot ( KD : KnotDesign ) =
struct
type t = { data : int array; mutable at : int; mutable skip : int }
let make () =
let data = Array.make KD.knot_size 0 in
for i = 1 to (KD.knot_size - 1) do data.(i) <- i done;
{ data; at = 0; skip = 0 }
...
let swap ...
let code_of_string ...
...
end
module K = Knot (struct
let knot_size = 256
let secret = [|17; 31; 73; 47; 23|]
let rounds = 64
end)
You can then go on to use 'K.make', 'K.swap', where these functions use the provided knot_size, etc.
as for OCaml's syntax... people don't like it. I remember not liking it, when I last looked at OCaml almost ten years ago. Probably, ;; confuses people, and the toplevel/subexpression dichotomy in the syntax is no explained well. These days I just think OCaml is very clean and readable.
▶ No.840858
80 people did part1 of day19,
and then saw part2,
and then didn't do it.
▶ No.840886>>840889
>>835306 (OP)
If I wasn't such a baka I could have done part 1 really quickly. I literally solved it by just eyeballing the data to pick out the smallest acceleration.
For part 2 I only had to simulate 38 steps.
▶ No.840887
I didn't bother to write complete deterministic solutions for today. I simply filtered the list to 3 possible candidates and then guessed.
For part 2, I ran endless simulation and tried numbers when they seemingly stopped changing, turned out it converges quickly so I didn't have to guess more than 1 time for part 2.
Could have answered part 1 from first try if I didn't accidentally use max instead of min.
If anyone went for full code solution, it'd be quite interesting to see the algorithm.
import re
from operator import add
from collections import defaultdict
sp = re.compile('[pva=<,>\s]+')
def parse_line(l: str):
p1, p2, p3, v1, v2, v3, a1, a2, a3 = map(int, filter(None, sp.split(l)))
return (p1, p2, p3), (v1, v2, v3), (a1, a2, a3)
def abs_sum(t):
return sum(map(abs, t))
def cmp_abs(d):
return lambda t: abs_sum(t[d])
min_acc = None
min_vel = None
answer = None
for i, x in enumerate(map(parse_line, open('i'))):
acc = cmp_abs(2)(x)
if min_acc is None or acc <= min_acc:
answer = i
min_acc = acc
print(answer, min_acc, x[2], x[1])
def vsum(a, b):
return tuple(map(add, a, b))
def step_one(x):
p, v, a = x
v = vsum(v, a)
p = vsum(p, v)
return p, v, a
def step_cld(ps):
d = defaultdict(lambda: 0)
for p, v, a in ps:
d[p] += 1
clz = set()
for p, cnt in d.items():
if cnt > 1:
clz.add(p)
return tuple(step_one(x) for x in ps if x[0] not in clz)
pass
ps = tuple(map(parse_line, open('i')))
l = len(ps)
while True:
ps = step_cld(ps)
nl = len(ps)
if nl != l:
l = nl
print(l)
▶ No.840889>>840891 >>840892 >>841779
>>840886
there's more than 1 particle with the minimal acceleration (by manhattan measure)
the answer needs to also have smaller velocity than other candidates
and the WTF part is that it's not trivial to measure velocity because depending on signs, each component is either always increased, or it first cancels out (goes through zero).
▶ No.840891>>840894
>>840889
If I sort the strings by length and then find the smallest acceleration for it that happened to be my solution.
▶ No.840892>>840905
>>840889
I think the brute force solution is to simulate canditates until in all of them for each axis acceleration has the same sign as velocity, and then pick the one with the smallest velocity.
Hopefully then there is only one particle.
If not, need to also resolve by position by similar algorithm
▶ No.840894>>840906
>>840891
and this proves that this challenge is very poorly composed
▶ No.840897>>840899
These are getting easier.
▶ No.840903
I'd call this brute force except it was just brutish, with not much force required.
▶ No.840905
>>840892
as noted it converges very quickly. I just ran a loop interactively to run N ticks, then looked at things, then ran N ticks again. No change in answer? That's the answer. where N=10000, probably massive overkill
▶ No.840906
>>840894
maybe this was a challenge made with only the serious leaderboard nuts in mind. "who will be first? look at all these potential shortcuts that you could have taken!"
▶ No.840919>>840929
>>840911
Sorry can't appreciate it, I have blocked any and all .gif urls in uBO because most of the time they have particularly low usefulness/network traffic ratio.
▶ No.840929
>>840919
nice blogpost fag
anti-sage btw
▶ No.840934
>>840599
>projecting this hard
Nobody mentioned C/C++ in this debate before you did, he said writing Haskell/Lisp was easier. Who hurt you? Alternatively, who's paying you?
▶ No.840938>>840970
>>840615
Why not just include the ? in the function name? The current syntax for that looks very terse. Is it because it's a postfix operator? Also, maybe something like ?{...} for exploding if any failing calls (even inside chains) inside the block will cause it to explode?
▶ No.840956>>841074
>>840911
> NETSCAPE2.0
wat?
Anyway, the gif crashes sxiv for some reason. But xanim plays it ok.
▶ No.840985>>840986 >>841273
Didn't post for the past few days because was busy. Won't do day16 in C because it's too much of a chore (string procesing days are boring).
Day 17
227 bytes
#define J
#define F(i,t) for(i=0;i<t;i++)
#define I n=(n+J)%e
main(){int*l=calloc(2017,4),e=1,i,n=0,a,b;F(i,2017){I;memmove(l+n+1,l+n,(e-n)*4);l[++n]=i+1;e++;}a=l[n+1];e=1;n=0;F(i,50000000){I;if(!n)b=i+1;n++;e++;}printf("%d %d\n",a,b);}
Compile with -DJ=<input>.
Will do the other days later.
▶ No.840986
>>840985
>#define J
Oops.
#define F(i,t) for(i=0;i<t;i++)
#define I n=(n+J)%e
main(){int*l=calloc(2017,4),e=1,i,n=0,a,b;F(i,2017){I;memmove(l+n+1,l+n,(e-n)*4);l[++n]=i+1;e++;}a=l[n+1];e=1;n=0;F(i,50000000){I;if(!n)b=i+1;n++;e++;}printf("%d %d\n",a,b);}
▶ No.841059
>>840615
pic related: how that rust stuff translates to OCaml. A more reasonable '?'-like operator in OCaml would be a prefix operator that throws an exception:
let ( !? ) = function
| Ok thing -> thing
| Error e -> raise e
... which is more like .unwrap(). Either strip the 'wrapper' of an OK response or else throw an exception.
▶ No.841064>>841101
>>840970
>Rust
>macOS
>.unwrap()
>.unwrap()
>.unwrap()
Checks out.
Polite sage for off-topic. Go ahead and "negate sage" xDXXDXDXDXD
▶ No.841074
>>840956
Netscape were the ones who amended the spec 89a to allow "looping gifs". Nothing odd about that.
▶ No.841101>>841118
>>841064
>>macOS
what?
sage negated btw xDXXDXDXDXD
▶ No.841118>>841129
>>841101
You look like a faggot, write like a faggot and use an operating system for cock gobblers .
▶ No.841129
>>841118
I don't use macOS though. How have you gotten that idea?
Try harder, anti Rust shill.
▶ No.841248>>841259
>>835519
>>836542
Alright, time to slowly catch up.
day 12
struct group_t { vector<uint16_t> next; bool visited = false; };
void digital_plumber_rec(uint16_t cur, vector<group_t>& group)
{
if (group[cur].visited)
return;
group[cur].visited = true;
for (uint16_t next : group[cur].next)
digital_plumber_rec(next, group);
}
void digital_plumber(string_view input)
{
vector<group_t> group; group.reserve(2000);
for (string_view line : input | split(by_line)){
auto [num_s, rest] = parse_n<1>(line, by_num);
uint16_t num = to<uint16_t>(num_s);
while (group.size() < num + 1u) group.emplace_back();
for (uint16_t next : rest | split(by_num) | map_to(to<uint16_t>))
group[num].next.push_back(next);
}
digital_plumber_rec(0, group);
cout << "part 1: " << count_if(group.begin(), group.end(), [](auto&& x){ return x.visited; }) << '\n';
uint16_t n_groups = 1;
for (uint16_t i = 1, sz = group.size(); i < sz; ++i)
if (!group[i].visited){
digital_plumber_rec(i, group);
++n_groups;
}
cout << "part 2: " << n_groups << '\n';
}
▶ No.841259>>841278
>>841248
day 13
void packet_scanners1(string_view input)
{
size_t severity = 0;
for (string_view line : input | split(by_line)){
auto [depth_s, range_s, rest] = parse_n<2>(line, by_num);
size_t depth = to<size_t>(depth_s), range = to<size_t>(range_s);
if (depth % (2 * (range - 1)) == 0)
severity += depth * range;
}
cout << "part 1: " << severity << '\n';
}
void packet_scanners2(string_view input)
{
vector<array<uint8_t, 2>> scanners;
for (string_view line : input | split(by_line)){
auto [depth_s, range_s, rest] = parse_n<2>(line, by_num);
scanners.push_back({to<uint8_t>(depth_s), to<uint8_t>(range_s)});
}
size_t delay = 0;
while (![&]{
for (auto [depth, range] : scanners)
if ((depth + delay) % (2 * (range - 1)) == 0)
return false;
return true;
}()) ++delay;
cout << "part 2: " << delay << '\n';
}
▶ No.841262>>841263 >>841268 >>841476 >>841531
637 bytes
from itertools import chain as G
F=filter
M=map
T=tuple
R=range
K=reversed
def I(i):s=len(i);return T(T(i[s-a-1][b]for a in R(s))for b in R(s))
H=lambda i:(i,I(i))
A={}
for C, D in M(lambda l:M(lambda l:T(M(lambda r:T(M('.#'.find,r)),F(None,M(str.strip,l.split('/'))))),F(None,l.split('=>'))),open('i')):
for E in G(H(C),H(T(K(C))),H(T(M(lambda r:T(K(r)),C)))):A[E]=D
J=(0,1,0),(0,0,1),(1,1,1)
def Z(b):
S=len(b);L=2+S%2;N=[]
for y in R(S//L):
O=[]
for x in R(S//L):O+=[(A[T(T(b[y*L+Y][x*L+X]for X in R(L))for Y in R(L))])]
for Y in R(L+1):N+=[(T(G(*M(lambda c:c[Y],O))))]
return T(N)
for _ in R(18):J=Z(J)
print(sum(M(sum,J)))
▶ No.841263
>>841262
btw got ~140 place before starting to golf
▶ No.841268
>>841262
and with pressing:
583 bytes
import base64,gzip;exec(gzip.decompress(base64.b85decode(b'ABzY8+*vzX0{>M}+lt#T5Pe>Kg`gDAY_!RGpNfMDVJ}H@g^eFJD@?HyxfS?^<dj`X|Ggu-F<XN?GdgE(N4c#_Zdz^Ix-J|yWmDUhAAhE%;;G|v_9Syt5Y9HTOdA%<_S_VjJxiNbKQvoOtAA<h^ogBx&cA`d$jL%i<V>w@&$i+*#9)-WNpHeLWl3IJo^q=H3=Yvp*$}aXEYdPN5gvgNz8tcd{QZY{-o4-tp1Og5q$2v@#xMl73xe^dV4R!kBrKwMf^A)Cu>sfGF&)#0V(gm2v=B@J^xuUu+{>>X5OqWQ1cv;GUHL&C{S<Rpz&(luZMPx^d-uN?R^U5(45OKPOymPwO1KrFxJ5yhJhCChA$Iz`LgstyI|VbGuI1fm|M_mZl`835zxP`0CzG{jUhO)hgWf(uyOC5dQ(pT_y<e|KheW-RdFk|j>8a~p|HBX^cqw+d8-*BceXSVga6N2yjE?G%h@D@JQihk_V)s(t`|R)wMoak$OJt2TRSWK1l0x(sOG^9;_iHaDeF6Xg')))
▶ No.841273
>>840985
>string procesing days are boring
perhaps this is because C doesn't even have any support for strings whatsoever and you have to either link some 3rd party shit or reinvent strings.
null-terminated, 1 byte per "character" arrays are not strings
▶ No.841278>>841307
>>841259
day 14
void disk_defragmentation1(string input)
{
const auto popcnt = [](char nibble){
static constexpr uint8_t popcnt_lo[10] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2 },
popcnt_hi[6] = { 2, 3, 2, 3, 3, 4 };
return nibble < 'a' ? popcnt_lo[nibble - '0'] : popcnt_hi[nibble - 'a'];
};
input += '-';
uint16_t sum = 0;
for (uint16_t i = 0; i < 128; ++i)
for (char nibble : knot_hash(input + to_string(i)))
sum += popcnt(nibble);
cout << "part 1: " << sum << '\n';
}
void disk_defrag2_rec(uint8_t x, uint8_t y, bool(& disk)[128][128])
{
disk[x][y] = false;
if (y != 0 && disk[x][y - 1]) disk_defrag2_rec(x, y - 1, disk);
if (y != 127 && disk[x][y + 1]) disk_defrag2_rec(x, y + 1, disk);
if (x != 0 && disk[x - 1][y]) disk_defrag2_rec(x - 1, y, disk);
if (x != 127 && disk[x + 1][y]) disk_defrag2_rec(x + 1, y, disk);
}
void disk_defragmentation2(string input)
{
const auto bin = [](char nibble){
return nibble < 'a' ? nibble - '0' : nibble - ('a' - 10);
};
bool disk[128][128];
input += '-';
for (uint16_t i = 0, j = 0; i < 128; ++i, j = 0)
for (uint8_t nibble : knot_hash(input + to_string(i)) | map_to(bin))
for (uint8_t k = 0; k < 4; ++j, ++k)
disk[i][j] = nibble & 0b1000, nibble <<= 1;
uint16_t sum = 0;
for (uint8_t i = 0; i < 128; ++i)
for (uint8_t j = 0; j < 128; ++j)
if (disk[i][j]){
disk_defrag2_rec(i, j, disk);
++sum;
}
cout << "part 2: " << sum << '\n';
}
▶ No.841279>>841284 >>841288
>>841276
seems legit now try to golf it, and post as text because I'm not gonna count symbols from picture :D
▶ No.841284>>841294
>>841279
I don't play golf. Especially not with Mathematica!
▶ No.841288>>841290
>>841279
I'll give you this though.
▶ No.841290
>>841288
Same again, at 600dpi, so you can actually see the 18th iteration.
▶ No.841294>>841296
>>841284
>Especially not with Mathematica
why?
▶ No.841296>>841410
>>841294
Characteristically long function names.
▶ No.841307>>841361 >>841555
>>841278
day 15
void dueling_generators1(uint64_t a, uint64_t b)
{
const auto next = [&]{ (a *= 16807) %= 2147483647; (b *= 48271) %= 2147483647; };
size_t count = 0;
for (size_t i = 0; next(), i < 40'000'000; ++i)
count += (a & 0xffff) == (b & 0xffff);
cout << "part 1: " << count << '\n';
}
void dueling_generators2(uint64_t a, uint64_t b)
{
const auto next = [&]{ (a *= 16807) %= 2147483647; (b *= 48271) %= 2147483647; };
size_t i = 0, count = 0;
deque<uint64_t> qa, qb;
const auto judge = [&](deque<uint64_t>& qadded, deque<uint64_t>& qother){
if (!qother.empty()){
count += (qadded[0] & 0xffff) == (qother[0] & 0xffff);
qadded.pop_front(); qother.pop_front();
return ++i < 5'000'000;
}
return true;
};
while (next(), 1){
if ((a & 3) == 0) { qa.push_back(a); if (!judge(qa, qb)) break; }
if ((b & 7) == 0) { qb.push_back(b); if (!judge(qb, qa)) break; }
}
cout << "part 2: " << count << '\n';
}
▶ No.841361>>841371
>>841307
How long does your part 2 take?
▶ No.841371>>841489 >>841570
>>841361
On my computer,
part 1: ~ 0.46 s
part 2: ~ 0.65 s
meh
▶ No.841410>>841489
>>841296
so shorten them
or it won't let you?
I thought it has first class functions
▶ No.841466>>841467 >>841470 >>841476 >>841516
>>841463
Jesus. Who the fuck thought this was a good idea?
▶ No.841467>>841477
>>841466
The kind of people who does things like these:
https://gist.github.com/rbirkby/1004837
Either hobbyists or professionals as a joke.
But Rust took too much time to be a joke, so it must have been made by hobbyists.
▶ No.841470
>>841466
What is your problem though?
▶ No.841476
>>841466
isn't it better than >>841262 though?
▶ No.841477
>>841467
that c# thing is pretty lame, you'll only impress some young schoolgirls with that.
▶ No.841489>>841493 >>841570
>>841371
Ah. Yours is the first solution I've seen that used a queue for part 2, so I wondered what the time penalty might be.
Ada did both parts in 580ms
>>841410
It does, and I could, but I have no motivation to code golf.
▶ No.841493>>841498
>>841489
>It does, and I could, but I have no motivation to code golf
then stop giving bland excuses (mathematica this, mathematica that), you should have just admitted that you're not brave enough to golf.
▶ No.841498>>841508
>>841493
> you should have just
You were told directly that I didn't care to golf.
▶ No.841508>>841515
>>841498
Alright forget this, I'll do it this one and only time.
You triggered my competitive autism, you bastard.
▶ No.841515>>841518 >>841777
>>841508
You stick out like a sore thumb you insufferable faggot.
▶ No.841516
>>841466
even outside of rust, this is why classes are a mistake
▶ No.841518
>>841515
At least try and make sense when crafting an insult. You just sound like a gibbering idiot.
▶ No.841531
>>841262
385 bytes
r=Reverse
s=StringSplit
l=NestList
n=Nest
c=Count
v@i_:=r@i
h@i_:=r[i,2]
o@i_:=Transpose@v@i
t=Join@@Map[Table[p->#[[2]],{p,Join[l[o,#[[1]],3],l[o,h[#[[1]]],3]]}]&,Characters[s[#,"/"]&/@s[Import["g","List"]," => "]]];
z={{".","#","."},{".",".","#"},{"#","#","#"}};
p@i_:=ArrayFlatten[Partition[i,If[Divisible[Dimensions[i][[1]],2],{2,2},{3,3}]]/.t]
c[n[p,z,5],"#",2]
c[n[p,z,18],"#",2]
Runs slower than the nicer version, since the optional Dispatch function has been removed which provided an optimization for rule replacements. Enjoy!
▶ No.841535>>841627
355 bytes
r=Reverse
s=StringSplit
l=NestList
v@i_:=r@i
h@i_:=r[i,2]
o@i_:=Transpose@v@i
t=Join@@Map[Table[p->#[[2]],{p,Join[l[o,#[[1]],3],l[o,h[#[[1]]],3]]}]&,Characters[s[#,"/"]&/@s[Import["g","List"]," => "]]];
Count[Nest[ArrayFlatten[Partition[#,If[Divisible[Dimensions[#][[1]],2],{2,2},{3,3}]]/.t]&,{{".","#","."},{".",".","#"},{"#","#","#"}},#],"#",2]&/@{5,18}
I'm done with this now. Mathematica wins.
▶ No.841555>>841674
>>841307
continuing. day 16
auto sep_by(char nc) { return [nc](char c){ return c != nc; }; }
void permutation_promenade(string_view input)
{
char id_perm[16]; iota(begin(id_perm), end(id_perm), 'a');
uint8_t pos_perm[16]; iota(begin(pos_perm), end(pos_perm), 0);
const auto by_not_slash = sep_by('/');
for (string_view arg : input | split(sep_by(','))){
switch (arg[0]){
break; case 's':
rotate(rbegin(pos_perm), rbegin(pos_perm) + to<uint8_t>(arg.substr(1)), rend(pos_perm));
break; case 'x': {
auto [a, b, _] = parse_n<2>(arg.substr(1), by_not_slash);
swap(pos_perm[to<uint8_t>(a)], pos_perm[to<uint8_t>(b)]);
} break; case 'p':
swap(*find(begin(id_perm), end(id_perm), arg[1]), *find(begin(id_perm), end(id_perm), arg[3]));
}
}
char prog1[16], * buf1 = prog1, prog2[16], * buf2 = prog2; iota(begin(prog1), end(prog1), 'a');
const auto dance = [&]{
for (uint8_t j = 0; j < 16; ++j)
buf2[j] = id_perm[buf1[pos_perm[j]] - 'a'];
swap(buf1, buf2);
};
dance();
cout << "part 1: " << string_view(buf1, 16) << '\n';
for (int i = 1; i < 1'000'000'000; ++i)
dance();
cout << "part 2: " << string_view(buf1, 16) << '\n';
}
▶ No.841570>>841578
>>841371
>>841489
Tried with vectors instead and it worsened the time initially (not too unexpected), but enabled some easy parallelization for a time of ~ 0.49 s:
void dueling_generators2_para(uint64_t a, uint64_t b)
{
const auto gen = [](uint64_t a, uint64_t mask, uint64_t mul){
return [=]() mutable {
vector<uint64_t> q; q.reserve(5'000'000);
while ((a *= mul) %= 2147483647, q.size() < 5'000'000)
if ((a & mask) == 0)
q.push_back(a);
return move(q);
};
};
future<vector<uint64_t>> gena = async(launch::async, gen(a, 3, 16807)),
genb = async(launch::async, gen(b, 7, 48271));
while (!gena.valid() || !genb.valid())
this_thread::yield();
vector<uint64_t> qa = gena.get(), qb = genb.get();
size_t count = 0;
for (int i = 0; i < 5'000'000; ++i)
count += (qa[i] & 0xffff) == (qb[i] & 0xffff);
cout << "part 2: " << count << '\n';
}
▶ No.841578
>>841570
oops, I guess .valid() doesn't do what I thought it did. Maybe I should use .wait_for() or something.
▶ No.841627>>841634
>>841535
322
Guess I wasn't tired of winning yet.
r=Reverse
s=StringSplit
l=NestList
a=Partition
j=Join
h@i_:=r[i,2]
o=Transpose@*r
k={2,2}
c=Characters
t=j@@Map[Table[p->#[[2]],{p,j[l[o,#[[1]],3],l[o,h@#[[1]],3]]}]&,c[s[#,"/"]&/@s[Import["g","List"]," => "]]]
Count[Nest[ArrayFlatten[a[#,If[Mod[Dimensions[#][[1]],2]==0,k,k+1]]/.t]&,a[c@".#...####", 3],#],"#",2]&/@{5,18}
▶ No.841634>>841757
>>841627
312
r=Reverse
s=StringSplit
l=NestList
a=Partition
j=Join
h@i_:=r[i,2]
o=Transpose@*r
k={2,2}
c=Characters
t=j@@Map[Table[p->#[[2]],{p,j[l[o,#[[1]],3],l[o,h@#[[1]],3]]}]&,c[s[#,"/"]&/@s[Import["g","List"]," => "]]]
Count[Nest[ArrayFlatten[a[#,If[Mod[Length[#],2]==0,k,k+1]]/.t]&,a[c@".#...####",3],#],"#",2]&/@{5,18}
▶ No.841674>>841744 >>841757
>>841555
day 17. I'm sure there must be a clever more efficient way to do it, but whatever, I got the right answer.
struct circular_list
{
auto take(circular_list* cdr_, int car_) { cdr = cdr_; car = car_; return this; }
circular_list* cdr;
int car;
};
template<uint16_t step> void spinlock()
{
circular_list* node = new circular_list[50'000'001];
circular_list* cur = node[0].take(&node[0], 0);
const auto step_insert = [&](int x){
for (uint16_t i = 0; i < step; ++i)
cur = cur->cdr;
cur = cur->cdr = node[x].take(cur->cdr, x);
};
for (int i = 1; i <= 2017; ++i)
step_insert(i);
cout << "part 1: " << cur->cdr->car << '\n';
for (int i = 2018; i <= 50'000'000; ++i)
step_insert(i);
while (cur->car != 0) cur = cur->cdr;
cout << "part 2: " << cur->cdr->car << '\n';
delete[] node;
}
▶ No.841744
>>841674
day 18. Simply magical.
template<typename F> struct ins_t { F op; int64_t* to, * from; };
template<typename F> auto make_duet(string_view input, const F& snd, const F& rcv)
{
static const F set = +[](int64_t* to, int64_t* from, int pc){
*to = *from;
return pc + 1;
}, add = +[](int64_t* to, int64_t* from, int pc){
*to += *from;
return pc + 1;
}, mul = +[](int64_t* to, int64_t* from, int pc){
*to *= *from;
return pc + 1;
}, mod = +[](int64_t* to, int64_t* from, int pc){
*to %= *from;
return pc + 1;
}, jgz = +[](int64_t* to, int64_t* from, int pc){
return *to > 0 ? pc + (int)*from : pc + 1;
};
unordered_map<int, int64_t> data; int cur_data = 0;
vector<ins_t<F>> prog;
for (string_view line : input | split(by_line)){
switch (line[1]){
break; case 'n': {
auto [x, _] = parse_n<1>(line.substr(4), by_word);
prog.push_back({snd, &data[0], isalpha(x[0]) ? &data[x[0]] : &(data[cur_data++] = to<int64_t>(x))});
} break; case 'e': {
auto [x, y, _] = parse_n<2>(line.substr(4), by_word);
prog.push_back({set, &data[x[0]], isalpha(y[0]) ? &data[y[0]] : &(data[cur_data++] = to<int64_t>(y))});
} break; case 'd': {
auto [x, y, _] = parse_n<2>(line.substr(4), by_word);
prog.push_back({add, &data[x[0]], isalpha(y[0]) ? &data[y[0]] : &(data[cur_data++] = to<int64_t>(y))});
} break; case 'u': {
auto [x, y, _] = parse_n<2>(line.substr(4), by_word);
prog.push_back({mul, &data[x[0]], isalpha(y[0]) ? &data[y[0]] : &(data[cur_data++] = to<int64_t>(y))});
} break; case 'o': {
auto [x, y, _] = parse_n<2>(line.substr(4), by_word);
prog.push_back({mod, &data[x[0]], isalpha(y[0]) ? &data[y[0]] : &(data[cur_data++] = to<int64_t>(y))});
} break; case 'c': {
auto [x, _] = parse_n<1>(line.substr(4), by_word);
prog.push_back({rcv, &data[0], isalpha(x[0]) ? &data[x[0]] : &(data[cur_data++] = to<int64_t>(x))});
} break; case 'g': {
auto [x, y, _] = parse_n<2>(line.substr(4), by_word);
prog.push_back({jgz, isalpha(x[0]) ? &data[x[0]] : &(data[cur_data++] = to<int64_t>(x)),
isalpha(y[0]) ? &data[y[0]] : &(data[cur_data++] = to<int64_t>(y))});
}
}
}
return pair(move(data), move(prog));
}
void duet1(string_view input)
{
auto [data, prog] = make_duet(input, +[](int64_t* to, int64_t* from, int pc){
*to = *from;
return pc + 1;
},+[](int64_t* to, int64_t* from, int pc){
static bool b = false;
if (*from && !b)
return cout << "part 1: " << *to << '\n', -1;
return pc + 1;
});
for (int pc = 0; (size_t)pc < prog.size();)
pc = prog[pc].op(prog[pc].to, prog[pc].from, pc);
}
void duet2(string_view input)
{
deque<int64_t> pipe[2];
enum {good, blocked, dead} status[2] = {good, good};
int pc[2] = {};
int cur = 0, counter = 0;
const auto snd = [&](int self) -> function<int(int64_t*, int64_t*, int)> {
return [&, self](int64_t* to, int64_t* from, int pc_cur){
if (self == 1) ++counter;
pipe[self].push_back(*from);
return pc_cur + 1;
};
};
const auto rcv = [&](int self, int other) -> function<int(int64_t*, int64_t*, int)> {
return [&, self, other](int64_t* to, int64_t* from, int pc_cur){
if (pipe[other].empty()){
if ((status[other] == blocked && pipe[self].empty()) || status[other] == dead)
status[self] = dead;
else
status[self] = blocked;
status[other] = good;
cur = other;
return pc_cur;
}
*from = pipe[other][0];
pipe[other].pop_front();
return pc_cur + 1;
};
};
auto [data0, prog0] = make_duet(input, snd(0), rcv(0, 1));
data0['p'] = 0;
auto [data1, prog1] = make_duet(input, snd(1), rcv(1, 0));
data1['p'] = 1;
decltype(prog0) prog[2] = {move(prog0), move(prog1)};
while (status[0] != dead && status[1] != dead){
int oldcur = cur;
int updatedpc = prog[cur][pc[cur]].op(prog[cur][pc[cur]].to, prog[cur][pc[cur]].from, pc[cur]);
if ((size_t)updatedpc >= prog[0].size()){
status[oldcur] = dead;
cur = !oldcur;
} else
pc[oldcur] = updatedpc;
}
cout << "part 2: " << counter << '\n';
}
▶ No.841756
1. "I don't need to rotate or flip stuff, lol. I'm not using APL. I just need to step through the structure while translating its coordinate system. It's just math."
2. ... ok but how do you do that?
3. pic related
I should've just implemented APL. I don't have the will to continue living long enough to even test this shitty code.
▶ No.841757>>841760
>>841674
>clever more efficient way to do it
Yeah, you don't need to actually do the inserts, since what you're looking for is always in a known position.
>>841634
With a fresh look, got it down to 303
r=Reverse
s=StringSplit
l=NestList
a=Partition
j=Join
h@i_:=r[i,2]
o=Transpose@*r
c=Characters
j@@Map[#/.{y_,w_}:>Table[p->w,{p,j[l[o,y,3],l[o,h@y,3]]}]&,c@s[#,"/"]&/@s[Import["g","List"]," => "]]
Count[Nest[ArrayFlatten[a[#,If[Mod[Length@#,2]==0,{2,2},{3,3}]]/.%]&,a[c@".#...####",3],#],"#",2]&/@{5,18}
Probably time for a new thread before the Day22 round.
▶ No.841760>>841761 >>841763
>>841757
300
r=Reverse
s=StringSplit
l=NestList
a=Partition
j=Join
h=r[#,2]&
o=Transpose@*r
c=Characters
j@@Map[#/.{y_,w_}:>Table[p->w,{p,j[l[o,y,3],l[o,h@y,3]]}]&,c@s[#,"/"]&/@s[Import["g","List"]," => "]]
Count[Nest[ArrayFlatten[a[#,If[Mod[Length@#,2]==0,{2,2},{3,3}]]/.%]&,a[c@".#...####",3],#],"#",2]&/@{5,18}
▶ No.841761>>841763
>>841760
what language is this?
besides Greek.
▶ No.841763
>>841760
293
r=Reverse
s=StringSplit
l=NestList
a=Partition
j=Join
o=Transpose@*r
c=Characters
j@@Map[#/.{y_,w_}:>Table[p->w,{p,j[l[o,y,3],l[o,r[y,2],3]]}]&,c@s[#,"/"]&/@s[Import["g","List"]," => "]]
Count[Nest[ArrayFlatten[a[#,If[Mod[Length@#,2]==0,{2,2},{3,3}]]/.%]&,a[c@".#...####",3],#],"#",2]&/@{5,18}
>>841761
Mathematica. It's a golfed version of this code >>841276. Code golfing is surprisingly addictive, but not something I'd want to do often.
▶ No.841769
Have any of you guys donated money to AoC?http://adventofcode.com/support
I'm a rich fag, so I'll probably toss him some shekels, it has provided pretty good entertainment.
▶ No.841772
day 19.
void series_of_tubes(string_view input)
{
vector<string_view> tubes;
for (string_view line : input | split(by_line))
tubes.push_back(line);
static constexpr array<int8_t, 3> dirs[4] = {{-1, 0, 1}, {1, 0, -1}, {0, -1, 1}, {0, 1, -1}};
const array<int8_t, 3>* dir = &dirs[3];
string res;
size_t steps = 2;
for (uint16_t x = tubes[0].find_first_not_of(" "), y = 1;; x += (*dir)[0], y += (*dir)[1], ++steps)
if (tubes[y][x] != '-' && tubes[y][x] != '|'){
if (tubes[y][x] != '+')
res.push_back(tubes[y][x]);
for (int8_t i = 0; i < 4; ++i)
if (&dirs[i] != dir + (*dir)[2] && tubes[y + dirs[i][1]][x + dirs[i][0]] != ' '){
dir = &dirs[i];
goto keep_going;
}
break;
keep_going:;
}
cout << "part 1: " << res << '\n';
cout << "part 2: " << steps << '\n';
}
▶ No.841774>>841865
nothing fancy.
I amended part 1 in place to get part 2, so no part 1 here, I'm too lazy to recover it.
284 bytes
e=enumerate
b={}
for y,l in e(open('i')):
l=l.strip()
p=(len(l)//2,)*2
for x,c in e(l):
if c=='#':b[x,y]=1
c,d=0,-1
a=0
for _ in range(10**7):
k=b.get(p,3)
if k==3:c,d=d,-c;b[p]=0
if k==0:a+=1;b[p]=1
if k==1:c,d=-d,c;b[p]=2
if k==2:c,d=-c,-d;b[p]=3
p=p[0]+c,p[1]+d
print(a)
▶ No.841777
▶ No.841779
>>840889
Today's was pretty interesting relative to the other challenges.
▶ No.841782
>>841780
I accidentally quoted you. I think I had your reply already in the message box from last time.
▶ No.841857>>841863
skipped day21, first actual skip.
day22 looks completely easy but my answers are wrong. Again, NFI how. Nothing but "heh easy day" and 22s Python crap on reddit.
>flips desk
>goes home
▶ No.841863>>841865
>>841857
and as soon as I say that:
I was adjusting the virus's coordinates even when the grid was extended to the right and to the bottom, which are coordinate-preserving extensions.
▶ No.841865>>841869 >>841874
>>841863
you could've just used hashmap and not have to fuck with 2d arrays relocation etc
like here >>841774
▶ No.841868
ocaml. commented out: the part that doesn't count already-infected blocks.
▶ No.841869>>841875
>>841865
yeah, I did that before, and it would've saved a lot of time here, but the actual 2d array work wasn't that involved except for my errors and it's easier to draw.
▶ No.841874>>841875
>>841865
>fuck with 2d arrays relocation
Whenever it says infinite grid it does not mean infinite. You just have to make the grid sufficiently big. Doing a 1000x1000 was enough for the challenge.
▶ No.841875>>842019
>>841869
dictionary is also trivial to draw, you only need to find the bounds
>>841874
having to guess is so-so. even more if you fuck this up and it will exceed the limits silently.
▶ No.842019
>>841875
>if you fuck this up and it will exceed the limits silently
I abused this fact considering the language I used java errors when accessing an out of bounds element. If it crashes I know I messed up somewhere.
▶ No.842074
Bump limit has been reached. New thread?
▶ No.842141>>842152
Woo, part b seems tricky.
▶ No.842152>>842153
>>842141
because it is!
and it doesn't involve writing code
▶ No.842153
>>842152
Haven't solved it yet I thought I might be able to solve it via just my text editor and some nice labels.
▶ No.842155