Advent of Code 2017 Day 22 Optimized Solution

[CoG]

This was a crazy workflow to build. It is not the prettiest workflow, but it works much better than the more typical style of workflow one may build to try and solve this problem.

Solution Description

Spoiler

The Most Valuable Tool (MVT): Multi-Row Formula Tool, which, through absolutely horrible string manipulation, allows us to perform multiple cycles in a single iteration.

That alone would still leave you with a very, very slow workflow, due to the massive amount of text you end up working with by the end of the workflow (I accidentally output all the data from each iteration into a browse tool: 88 GB had to be processed, with the final rows having tens of thousands of characters to perform multiple Contains() + other string functions on.

I was first able to enhance performance with what I will call: Domain Restriction. Why keep track of all data points, when you can look at a smaller radius of points that you've fenced the iteration into since the memory requirements increase by the square of the radius? I chose 15 units (radius; there may be a more efficient balance). This way I could complete 15 cycles in a single iteration only tracking/analyzing 450 points (aka (30^2)/2), then merge all the other data points back in at the end for the next iteration. This solved the problem in about 24 hours.

The final insight and tremendous optimization came from including the fact that the agent turns often. This means that the agent will take longer than 15 cycles to leave it's fenced in barrier. I added a multiplicative factor to generate a buffer of potential moves that could be made and learned that I can run over 1000 cycles/iteration within my 15 unit border radius, continuing the calculations until I use up the buffer or I leave the Domain Restriction. This ultimately brought a workflow that takes over a week for Alteryx to run to one that can run 10M cycles in 1.5 hours! How's that for a performance boost!!!

Link to Problem: Day 22 - Advent of Code 2017 

Hope this helps and Happy Solving!

[PangHC]

you code in the multi-row formula tool. 🤣

[gawa]

@CoG 

Not a main topic but I learned new way of using Multi-row Formula that functions like a "Generate Row" tools stopping at specific records.

As for expression inside Multi-row formula in your WF, it's too complicated to digest it in my brain. It's awesome.

[PangHC]

my version, ~16hrs maybe. not confirm because i run and stop few times. 

using similar concept but i using formula tool instead. 

idea is same, reduce passing data between tools. 

hence, i edit the xml to duplicate the formula x99 time into a formula tool to reduce the time. 

about 30 second for first 10k iteration and

about 1 mins 10 seconds for last 10k iteration

improvement:
i believe if add all clean spot will help because it need not to go through all spots only then identify as clean. 
but i lazy to do that. 

another idea:
i try to do is processing via input format directly. 
i.e. 
...
.#.
...
in 1 cell.
where search by y*(x+1) + x to get the position (+1 to include the new line)
and update it via left(-1) + change + right()
and rows/column if x/y reach border via '.......\n'+[map] and replace([map],'\n','.\n')
 
because by this way, the total length is less current method.

[Hub119]

Like I mentioned in AoC WhatsApp chat, unfortunately my computer decided to reboot itself after finally finishing the straight forward "brute force" version of this problem, so I can't post a screenshot of the exact runtime, but it went from starting in the evening of February 23rd, and finished sometime early this morning March 12th (thankfully I output solution to a file instead of a browse)... So 2 weeks, and almost 2 days!

[PangHC]

here the version that i mention before.

instead of concate by position.

i concate the map instead.

020

010

000

change to 0-3 for ease of update state by mod(x+1,4)

i only test run till 100k. it valid. but i believe it take less time maybe?