Community Spring Cleaning week is here! Join your fellow Maveryx in digging through your old posts and marking comments on them as solved. Learn more here!

General Discussions

Discuss any topics that are not product-specific here.

Advent of Code 2021 Day 23 (BaseA Style)

jdunkerley79
ACE Emeritus
ACE Emeritus

Discussion thread for day 23 of the Advent of Code - https://adventofcode.com/2021/day/23

 

330px-Gammarus_roeselii.jpg

6 REPLIES 6
dsmdavid
11 - Bolide
Spoiler
Does "pen & paper" count as BaseA?
If so, easy solve. If not... 😅
Spoiler
#############
#...........#
###D#C#D#B###
  #D#C#B#A#
  #D#B#A#C#
  #C#A#A#B#
  ######### 
  
#############
#B..........#
###D#C#D#.###
  #D#C#B#A#
  #D#B#A#C#
  #C#A#A#B#
  ######### 
  
#############
#BA.......BC#
###D#C#D#.###
  #D#C#B#.#
  #D#B#A#.#
  #C#A#A#.#
  ######### 
  ---
#############
#BA.......BC#
###.#C#.#D###
  #.#C#B#D#
  #.#B#A#D#
  #C#A#A#D#
  ######### 
---
 
#############
#B......C.BC#
###.#C#.#D###
  #.#C#B#D#
  #.#B#A#D#
  #A#A#A#D#
  ######### 

#############
#BB.....C.BC#
###.#C#.#D###
  #A#C#.#D#
  #A#B#.#D#
  #A#A#.#D#
  ######### 
---

#############
#BB...B...BC#
###A#.#.#D###
  #A#.#C#D#
  #A#.#C#D#
  #A#.#C#D#
  ######### ​
I started doing this to get some inspiration for the workflow, but ended up finishing it before getting any idea of how to implement this in a reasonable amount of time...
patrick_digan
17 - Castor
17 - Castor

Finally got my stars, I built workflows but had to hardcode some things so that it would finish. Given infinite resources, the logic would work for all paths, but it clearly needed some guiding to finish in a reasonable time.

Spoiler
I mapped the diagram and went through an iterative workflow to process it. The first part is mostly dynamic, but I did have to hardcode one part to get rid of less efficient routes. It's possible a fix for part 2 would make it completely dynamic, but I didn't investigate. For part 2, I had to give it the first 8 steps (I think I got an easy one and it was obvious how you should start). I tried pen and paper but I missed a key step that saved me several hundred energy. It did the rest on it own. In theory it would have solved all the steps without any help, but the size was getting too big too quick. It's possible I could have had logic to reduce it, but nothing was coming to me.

Part 2 macro:
 patrick_digan_0-1640310833265.png

 

mmontgomery
10 - Fireball

Brute force by hand p1 and p2. P2 below by hand. I used alteryx for the sum/calculations

 

Spoiler

#############
#...........#
###D#A#A#D###
###D#C#B#A###
###D#B#A#C###
###C#C#B#B###
#########

A up 1;
A left 4;

A up 1;
A right 4;

D up 1;
D right 2;

A up 2;
A left 7;

B up 2;
B right 1;

C up 2;
C right 2;
C down 4;

B up 3;
B left 1;

C up 4;
C right 2;
C down 3;

B right 1;
B down 4;

B left 3;
B down 3;

B left 5;
B down 2;

D up 1;
D left 5;

A up 2;
A right 1;

C up 3;
C left 2;
C down 1;

B up 4;
B left 4;
B down 1;

D right 5;
D down 4;

D up 1;
D right 6;
D down 3

D up 2;
D right 6;
D down 2;

D up 3;
D right 6;
D down 1;

C up 4;
C right 4;
C down 1;

A right 1;
A down 4;

A right 2;
A down 3;

A left 7;
A down 2;

A left 8
A down 1;


Pang_Hee_Choy
12 - Quasar

i built an excel macro to do it (attached), similar to hand and paper, but faster.

 

Spoiler
Pang_Hee_Choy_3-1642731947313.png

 

Pang_Hee_Choy_5-1642735769671.png

 


 way to use the macro. 
1. Click the start button.
2. in the game area, use mouse to click the token want to move.
3. then press direction key to move (i.e. up, down, left, right key)

*to restart, click the start button again.
**it change the function of direction key. hence, click STOP to stop the game. (No resume)
***the shortest answer and answer need to manual copy.

 

 

Pang_Hee_Choy
12 - Quasar

I made it!!

Both within 5mins.

part 2 is take less time then part1, without do anything change.

 

Spoiler
duplicate the rules
1. only first letter in the room can move.
2. the second move only can move to room.
3. if move to room, check whether is A/B/C/D

key to reduce size
1. if the room is open, all other move for that letter is removed.(i.e. only keep the move to room.)
2. if above move is room to room. it consider as second move. (exclude them to generate new move in next iteration)
3. verify all the possible, remove duplicate tree that create same result.

key to reduce time
1. sort necessary only.
2. sort without dictionary if possible.

Workflow
Pang_Hee_Choy_0-1643251525439.pngPang_Hee_Choy_1-1643251601598.png

Macro:

Pang_Hee_Choy_2-1643251695232.pngPang_Hee_Choy_3-1643251738865.png


output:
part1: 4-6mins

Pang_Hee_Choy_4-1643251765602.png

part2:

Pang_Hee_Choy_5-1643251780895.pngPang_Hee_Choy_6-1643251812004.png

 

 

 

 

 

 

SeanAdams
17 - Castor
17 - Castor

This one took me a month part-time to get this finalised.

 

Went through a ton of different things - details below:

 

Spoiler
- First tried a brute-force method - that failed - largely 'cause of the lack of regression
- Then did something like a path-find, where you keep the shortest path to any given board configuration
- Now - to keep a given configuration - you need a fingerprint - first this was stored in a string that went SUPER slow (days)
- Then I converted this to a single fingerprint ID
     - Given that each position can have one of 5 values (empty; A; B; C; D) - you can use a base 5 number system
     - And since there are 15 unique positions in the board for part 1; and 23 for part 2 - you can store the fingerprint in a single 64 bit integer
- But then we realised that Alteryx doesn't respect 64 bit integer algebra - instead it converts this to a double - so I had to change this to 2 fingerprints to describe the board.

At the end of all this - it completes all of the path finding in 5m 25s for part 2

Main flow:

SeanAdams_0-1644110010425.png


The main recipe:
- Create the matrix of all the possible moves (do this once) - and the positions that it goes through to get there.
- Start with the starting position:
         - Match with the move matrix to find the possible moves in step 1
         - Exclude any where the path is blocked; or where it breaks the rules
         - Whateever remains then becomes part of the next iteration
... continue doing this until you hit the target end-state





 


Labels