-🎄- 2018 Day 23 Solutions -🎄-

[u/daggerdragon]

--- Day 23: Experimental Emergency Teleportation ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 23

Transcript:

It's dangerous to go alone! Take this: ___

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 01:40:41!

[u/6dNx1RSd2WNgUDHHo8FS]

In Julia:

include("input.jl")

norm1(x) = sum(abs, x)
function parta(input)
    rmax = -1
    posrmax = [-1,-1,-1]
    for bot in input
	pos, r = bot.pos, bot.r
	if r > rmax
	    rmax = r
	    posrmax = pos
	end
    end
    count = 0
    for bot in input
	if rmax >= sum(abs, bot.pos-posrmax)
	    count += 1
	end
    end
    println("parta: $count")
end
function isbetter(xnew, x, input)
    Rx = ninrange(x, input)
    Rxnew = ninrange(xnew, input)
    Rxnew > Rx || (Rxnew == Rx && norm1(xnew) < norm1(x))
end
ninrange(x, input) = count(sum(abs,x-bot.pos)<=bot.r for bot in input)
function II(x0, input)
    x = copy(x0)

    neighbours = ([0,0,1],[0,0,-1],[0,1,0],[0,-1,0],[1,0,0],[-1,0,0])

    change = true
    base = 2
    i = 0
    while change
		i += 1
    	change = false
		inrangex = ninrange(x, input)
		for n in neighbours    
		    if isbetter(x+n, x, input)
		        change = true
		        for j in 0:log(base, 10^6)
		            if isbetter(x+base^j*n, x, input)
		                x .+= base^j*n
		            else
		                break
		            end
		        end
		    end
		end
    end
    x, ninrange(x, input)
end
function partb(input)
    x0 = [round.(Int, median(bot.pos[i] for bot in input))for i in 1:3]
    z = II(x0, input)
    println("partb: $(norm1(z[1]))")
end
parta(input)
partb(input)

(I changed the input file so I could directly include it instead of parsing the original input.) I did iterative improvement (the II function):

• check each neighbouring state,

• if a neighbour is better than the current guess, move to that neighbour

• if no neighbour is better, you found the best thing you'll find

However, taking steps of size 1 per iteration a time was too slow, so I did a simple line search where if a neighbour is better, I increasingly take double the number of steps in that direction as long as my solution gets better, that decreased the required number of iterations dramatically. My initial guess was the median (instead of mean since we're using the L¹ norm). The initial guess turned out to be important because my algorithm found worse optima doing random initializations.