Jump to content

Advent Of Code - 25 challenges for December

madknight3

The day 7 problem took me quite a while to solve but I finally managed it (mostly). For some reason my solution executed every command except my final "lx -> a" instruction. I'm not sure why, so I just printed out the value of "lx" instead and am going to move on with my life...

 

Maybe one day I'll revisit it and clean up the code and figure out what my error was.

Link to comment
Share on other sites

Link to post
Share on other sites

I really don't see where I'm going wrong but keep getting the wrong answer > :(

 

Did you get this figured out yet? If not, what are you getting for your real input (ie: the pastebin). I'll check it against my result.

 

I ran my code against the following test input and also got 10404.

turn on 0,0 through 999,999turn off 499,499 through 600,600toggle 0,0 through 999,999 
Link to comment
Share on other sites

Link to post
Share on other sites

 

Did you get this figured out yet? If not, what are you getting for your real input (ie: the pastebin). I'll check it against my result.

 

I ran my code against the following test input and also got 10404.

turn on 0,0 through 999,999turn off 499,499 through 600,600toggle 0,0 through 999,999 

Ya, it seems nano is dumb and adds empty lines to the end of the input file which screwed up my solution. Thanks :)

 

Ended up getting 569999 or something like that, i forget :[

Link to comment
Share on other sites

Link to post
Share on other sites

Ya, it seems nano is dumb and adds empty lines to the end of the input file which screwed up my solution. Thanks :)

 

Ended up getting 569999 or something like that, i forget :[

 

Right on, that's what I got with your input as well.

Link to comment
Share on other sites

Link to post
Share on other sites

You just need to understand that MD5 is a hashing function that takes some input string and transforms it into a seemingly random 32 character hex string. Since you use C++ you'll need some library that performs the function, or you could try something like Python that has it built in.

I just can't understand the meaning of MD5 and how the heck it works. Maybe i'm too young for this complexity. so if you could just pass me through day 4 (give answers) i'd be grateful. (part 1 - yzbqklnj )

i5-4690k, R9 380 4gb, 8gb-1600MHz ram, corsair vs 550w, astrock h97m anniversary.

 

Link to comment
Share on other sites

Link to post
Share on other sites

I just can't understand the meaning of MD5 and how the heck it works. Maybe i'm too young for this complexity. so if you could just pass me through day 4 (give answers) i'd be grateful. (part 1 - yzbqklnj )

MD5 is a hash function.

A hash function can be used to map data of arbitrary size to data of fixed size.

For example

240px-Hash_table_4_1_1_0_0_1_0_LL.svg.pn

 

This is exactly what the MD5 algorithm does, just in a more complex manner.

If you have the input , it's easy to verify if it corresponds to a certain hash. But if you have the hash and not the value, it's way harder. You either have to make an inverse function, but certain cryptographic functions are designed to not be reversible , or pretty close to impossible to reverse , or to just brute force your way.

 

MD5 is often used to verify file integrity.

For example, you download a file and you are given its md5 checksum. After you download it , you compare the checksum of the file you have on your computer to the one it should have.

 

Header :

.cpp file :

class MD5{public:  typedef unsigned int size_type; // must be 32bit   MD5();  MD5(const std::string& text);  void update(const unsigned char *buf, size_type length);  void update(const char *buf, size_type length);  MD5& finalize();  std::string hexdigest() const;  friend std::ostream& operator<<(std::ostream&, MD5 md5); private:  void init();  typedef unsigned char uint1; //  8bit  typedef unsigned int uint4;  // 32bit  enum {blocksize = 64}; // VC6 won't eat a const static int here   void transform(const uint1 block[blocksize]);  static void decode(uint4 output[], const uint1 input[], size_type len);  static void encode(uint1 output[], const uint4 input[], size_type len);   bool finalized;  uint1 buffer[blocksize]; // bytes that didn't fit in last 64 byte chunk  uint4 count[2];   // 64bit counter for number of bits (lo, hi)  uint4 state[4];   // digest so far  uint1 digest[16]; // the result   // low level logic operations  static inline uint4 F(uint4 x, uint4 y, uint4 z);  static inline uint4 G(uint4 x, uint4 y, uint4 z);  static inline uint4 H(uint4 x, uint4 y, uint4 z);  static inline uint4 I(uint4 x, uint4 y, uint4 z);  static inline uint4 rotate_left(uint4 x, int n);  static inline void FF(uint4 &a, uint4 b, uint4 c, uint4 d, uint4 x, uint4 s, uint4 ac);  static inline void GG(uint4 &a, uint4 b, uint4 c, uint4 d, uint4 x, uint4 s, uint4 ac);  static inline void HH(uint4 &a, uint4 b, uint4 c, uint4 d, uint4 x, uint4 s, uint4 ac);  static inline void II(uint4 &a, uint4 b, uint4 c, uint4 d, uint4 x, uint4 s, uint4 ac);}; std::string md5(const std::string str); #endif
/* interface header */#include "md5.h" /* system implementation headers */#include <cstdio>  // Constants for MD5Transform routine.#define S11 7#define S12 12#define S13 17#define S14 22#define S21 5#define S22 9#define S23 14#define S24 20#define S31 4#define S32 11#define S33 16#define S34 23#define S41 6#define S42 10#define S43 15#define S44 21 /////////////////////////////////////////////// // F, G, H and I are basic MD5 functions.inline MD5::uint4 MD5::F(uint4 x, uint4 y, uint4 z) {  return x&y | ~x&z;} inline MD5::uint4 MD5::G(uint4 x, uint4 y, uint4 z) {  return x&z | y&~z;} inline MD5::uint4 MD5::H(uint4 x, uint4 y, uint4 z) {  return x^y^z;} inline MD5::uint4 MD5::I(uint4 x, uint4 y, uint4 z) {  return y ^ (x | ~z);} // rotate_left rotates x left n bits.inline MD5::uint4 MD5::rotate_left(uint4 x, int n) {  return (x << n) | (x >> (32-n));} // FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.// Rotation is separate from addition to prevent recomputation.inline void MD5::FF(uint4 &a, uint4 b, uint4 c, uint4 d, uint4 x, uint4 s, uint4 ac) {  a = rotate_left(a+ F(b,c,d) + x + ac, s) + b;} inline void MD5::GG(uint4 &a, uint4 b, uint4 c, uint4 d, uint4 x, uint4 s, uint4 ac) {  a = rotate_left(a + G(b,c,d) + x + ac, s) + b;} inline void MD5::HH(uint4 &a, uint4 b, uint4 c, uint4 d, uint4 x, uint4 s, uint4 ac) {  a = rotate_left(a + H(b,c,d) + x + ac, s) + b;} inline void MD5::II(uint4 &a, uint4 b, uint4 c, uint4 d, uint4 x, uint4 s, uint4 ac) {  a = rotate_left(a + I(b,c,d) + x + ac, s) + b;} ////////////////////////////////////////////// // default ctor, just initailizeMD5::MD5(){  init();} ////////////////////////////////////////////// // nifty shortcut ctor, compute MD5 for string and finalize it right awayMD5::MD5(const std::string &text){  init();  update(text.c_str(), text.length());  finalize();} ////////////////////////////// void MD5::init(){  finalized=false;   count[0] = 0;  count[1] = 0;   // load magic initialization constants.  state[0] = 0x67452301;  state[1] = 0xefcdab89;  state[2] = 0x98badcfe;  state[3] = 0x10325476;} ////////////////////////////// // decodes input (unsigned char) into output (uint4). Assumes len is a multiple of 4.void MD5::decode(uint4 output[], const uint1 input[], size_type len){  for (unsigned int i = 0, j = 0; j < len; i++, j += 4)    output[i] = ((uint4)input[j]) | (((uint4)input[j+1]) << 8) |      (((uint4)input[j+2]) << 16) | (((uint4)input[j+3]) << 24);} ////////////////////////////// // encodes input (uint4) into output (unsigned char). Assumes len is// a multiple of 4.void MD5::encode(uint1 output[], const uint4 input[], size_type len){  for (size_type i = 0, j = 0; j < len; i++, j += 4) {    output[j] = input[i] & 0xff;    output[j+1] = (input[i] >> 8) & 0xff;    output[j+2] = (input[i] >> 16) & 0xff;    output[j+3] = (input[i] >> 24) & 0xff;  }} ////////////////////////////// // apply MD5 algo on a blockvoid MD5::transform(const uint1 block[blocksize]){  uint4 a = state[0], b = state[1], c = state[2], d = state[3], x[16];  decode (x, block, blocksize);   /* Round 1 */  FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */  FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */  FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */  FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */  FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */  FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */  FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */  FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */  FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */  FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */  FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */  FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */  FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */  FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */  FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */  FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */   /* Round 2 */  GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */  GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */  GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */  GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */  GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */  GG (d, a, b, c, x[10], S22,  0x2441453); /* 22 */  GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */  GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */  GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */  GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */  GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */  GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */  GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */  GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */  GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */  GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */   /* Round 3 */  HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */  HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */  HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */  HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */  HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */  HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */  HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */  HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */  HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */  HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */  HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */  HH (b, c, d, a, x[ 6], S34,  0x4881d05); /* 44 */  HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */  HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */  HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */  HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */   /* Round 4 */  II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */  II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */  II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */  II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */  II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */  II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */  II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */  II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */  II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */  II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */  II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */  II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */  II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */  II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */  II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */  II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */   state[0] += a;  state[1] += b;  state[2] += c;  state[3] += d;   // Zeroize sensitive information.  memset(x, 0, sizeof x);} ////////////////////////////// // MD5 block update operation. Continues an MD5 message-digest// operation, processing another message blockvoid MD5::update(const unsigned char input[], size_type length){  // compute number of bytes mod 64  size_type index = count[0] / 8 % blocksize;   // Update number of bits  if ((count[0] += (length << 3)) < (length << 3))    count[1]++;  count[1] += (length >> 29);   // number of bytes we need to fill in buffer  size_type firstpart = 64 - index;   size_type i;   // transform as many times as possible.  if (length >= firstpart)  {    // fill buffer first, transform    memcpy(&buffer[index], input, firstpart);    transform(buffer);     // transform chunks of blocksize (64 bytes)    for (i = firstpart; i + blocksize <= length; i += blocksize)      transform(&input[i]);     index = 0;  }  else    i = 0;   // buffer remaining input  memcpy(&buffer[index], &input[i], length-i);} ////////////////////////////// // for convenience provide a verson with signed charvoid MD5::update(const char input[], size_type length){  update((const unsigned char*)input, length);} ////////////////////////////// // MD5 finalization. Ends an MD5 message-digest operation, writing the// the message digest and zeroizing the context.MD5& MD5::finalize(){  static unsigned char padding[64] = {    0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0  };   if (!finalized) {    // Save number of bits    unsigned char bits[8];    encode(bits, count, 8);     // pad out to 56 mod 64.    size_type index = count[0] / 8 % 64;    size_type padLen = (index < 56) ? (56 - index) : (120 - index);    update(padding, padLen);     // Append length (before padding)    update(bits, 8);     // Store state in digest    encode(digest, state, 16);     // Zeroize sensitive information.    memset(buffer, 0, sizeof buffer);    memset(count, 0, sizeof count);     finalized=true;  }   return *this;} ////////////////////////////// // return hex representation of digest as stringstd::string MD5::hexdigest() const{  if (!finalized)    return "";   char buf[33];  for (int i=0; i<16; i++)    sprintf(buf+i*2, "%02x", digest[i]);  buf[32]=0;   return std::string(buf);} ////////////////////////////// std::ostream& operator<<(std::ostream& out, MD5 md5){  return out << md5.hexdigest();} ////////////////////////////// std::string md5(const std::string str){    MD5 md5 = MD5(str);     return md5.hexdigest();}

i5 4670k @ 4.2GHz (Coolermaster Hyper 212 Evo); ASrock Z87 EXTREME4; 8GB Kingston HyperX Beast DDR3 RAM @ 2133MHz; Asus DirectCU GTX 560; Super Flower Golden King 550 Platinum PSU;1TB Seagate Barracuda;Corsair 200r case. 

Link to comment
Share on other sites

Link to post
Share on other sites

I just can't understand the meaning of MD5 and how the heck it works.

 

Fortunately you don't need to understand how the MD5 algorithm works to solve this problem. All you really need to know is that the MD5 algorithm will take your input and return a bunch of letters and numbers. The output may look random, but it's not. Every time you run the md5 function on the same input it will produce the same output.

 

Here are some examples using this online tool. You can rerun all of the examples with this other online tool to see that you get the same output.

md5("hello")        // returns 5d41402abc4b2a76b9719d911017c592md5("password")     // returns 5f4dcc3b5aa765d61d8327deb882cf99md5("123")          // returns 202cb962ac59075b964b07152d234b70md5("abcdef609043") // returns 000001dbbfa3a5c83a2d506429c7b00e

The problem is just looking for you to check if the results from the md5 function start with 5 zeros. There are plenty of libraries out there with an MD5 function that do all the work for you. You simply have to call the function (they usually just take a string) and check the result (which is usually just a string).

Link to comment
Share on other sites

Link to post
Share on other sites

Fortunately you don't need to understand how the MD5 algorithm works to solve this problem. All you really need to know is that the MD5 algorithm will take your input and return a bunch of letters and numbers. The output may look random, but it's not. Every time you run the md5 function on the same input it will produce the same output.

 

Here are some examples using this online tool. You can rerun all of the examples with this other online tool to see that you get the same output.

md5("hello")        // returns 5d41402abc4b2a76b9719d911017c592md5("password")     // returns 5f4dcc3b5aa765d61d8327deb882cf99md5("123")          // returns 202cb962ac59075b964b07152d234b70md5("abcdef609043") // returns 000001dbbfa3a5c83a2d506429c7b00e

The problem is just looking for you to check if the results from the md5 function start with 5 zeros. There are plenty of libraries out there with an MD5 function that do all the work for you. You simply have to call the function (they usually just take a string) and check the result (which is usually just a string).

Wait, so if i have built the generator (do i have to make it?) i just have to add numbers to the given string and see if the result starts with 5 zeros?

i5-4690k, R9 380 4gb, 8gb-1600MHz ram, corsair vs 550w, astrock h97m anniversary.

 

Link to comment
Share on other sites

Link to post
Share on other sites

Wait, so if i have built the generator (do i have to make it?) i just have to add numbers to the given string and see if the result starts with 5 zeros?

 

Your code basically just needs to do this

// Check the result of md5("yzbqklnj1"). If it starts with 5 zeros, you're done. If not, check the next number.// Check the result of md5("yzbqklnj2"). If it starts with 5 zeros, you're done. If not, check the next number.// Check the result of md5("yzbqklnj3"). If it starts with 5 zeros, you're done. If not, check the next number.// Check the result of md5("yzbqklnj4"). If it starts with 5 zeros, you're done. If not, check the next number.// etc

How you get the MD5 function is up to you. You can find a library to include, or you can just get the source code online for it and add it to your code. If I recall correctly you use C++ so here's an implementation of the MD5 algorithm in C++ (I believe this is what NineShadow posted above).

Link to comment
Share on other sites

Link to post
Share on other sites

Day 5

 

So i get right answers with the given examples, i tried some from my puzzle and i get them right, but when i compile the whole puzzle i get it too high, any mistakes in my code?

 

EDIT: got it. searching for sub strings was a bit off (answer changed by 1 :D and it was correct)

i5-4690k, R9 380 4gb, 8gb-1600MHz ram, corsair vs 550w, astrock h97m anniversary.

 

Link to comment
Share on other sites

Link to post
Share on other sites

Completed day 9 with a brute force approach. Anyone decide to go with a more efficient graph algorithm?

Link to comment
Share on other sites

Link to post
Share on other sites

Completed day 9 with a brute force approach. Anyone decide to go with a more efficient graph algorithm?

Heh heh, we are the brute force squad

Link to comment
Share on other sites

Link to post
Share on other sites

So i get right answers with the examples and with some chosen from my puzzle, but i believe that my "pair" searching mechanism is a bit off though.

       string temp = isNice[i]       int pear=0; for(int j=0; j<temp.length()-1;j++)        {   int sk=0;            for(int k=0; k<temp.length()-1; k++)            {                if(temp[j]==temp[k] && temp[j+1]==temp[k+1] )                    sk++;            }            if(sk>1)                {                    pear=sk;                   if(pear>1) break;                }        }

EDIT: solved

i5-4690k, R9 380 4gb, 8gb-1600MHz ram, corsair vs 550w, astrock h97m anniversary.

 

Link to comment
Share on other sites

Link to post
Share on other sites

Starting to get behind due to travelling. Get some free time, go to log in, and GitHub isn't accepting my 2 factor authentication. Now my account is locked (temporarily I think). Gotta love it.

 

Hopefully I'll get it sorted out and be back on track soon.

Link to comment
Share on other sites

Link to post
Share on other sites

Ya I'm going to get back into this when the ides of december is over :)

Link to comment
Share on other sites

Link to post
Share on other sites

Been falling behind for a while now, I'm hopefully going to power through a few days worth of challenges every day during Christmas break.

My Current Build: 

Intel i5 3570K @ 4.4GHz 1.11V, Cooler Master Hyper 212 EVO, Asrock Z77 Extreme4, Corsair Vengeance 8GB 1600MHz, Samsung 840 EVO 250GB, Asus GTX 760 DCII Overclocked, Corsair CX600M

Link to comment
Share on other sites

Link to post
Share on other sites

How long will the page be active after the 25th day?

i5-4690k, R9 380 4gb, 8gb-1600MHz ram, corsair vs 550w, astrock h97m anniversary.

 

Link to comment
Share on other sites

Link to post
Share on other sites

How long will the page be active after the 25th day?

 

The creator said a couple weeks after the 25th.

Link to comment
Share on other sites

Link to post
Share on other sites

Day 6 part 1:

is my method right?:

/**/

EDIT: nevermind :)

i5-4690k, R9 380 4gb, 8gb-1600MHz ram, corsair vs 550w, astrock h97m anniversary.

 

Link to comment
Share on other sites

Link to post
Share on other sites

Day 7. Do i need to create decimal to binary and binary to decimal converter?

i5-4690k, R9 380 4gb, 8gb-1600MHz ram, corsair vs 550w, astrock h97m anniversary.

 

Link to comment
Share on other sites

Link to post
Share on other sites

No.

Grab the code from the web?

i5-4690k, R9 380 4gb, 8gb-1600MHz ram, corsair vs 550w, astrock h97m anniversary.

 

Link to comment
Share on other sites

Link to post
Share on other sites

Grab the code from the web?

Was trying to see what day7 was and it I did it but the site appears to be down atm

Link to comment
Share on other sites

Link to post
Share on other sites

@prolemur

TBH i decided to skip day 7 because there is too much bs i cant seem to understand.

i5-4690k, R9 380 4gb, 8gb-1600MHz ram, corsair vs 550w, astrock h97m anniversary.

 

Link to comment
Share on other sites

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


×