karanlyons/bringing-a-gun-to-a-trainer-fight.py

## bringing-a-gun-to-a-trainer-fight.py
#!/usr/bin/env python3

from collections import namedtuple
from fractions import gcd
from math import ceil, sqrt


# Calculating distances with bounces and stuff is...a pain, but given our bounce rules we
# can instead construct infinite congruent rooms, mirrored about each other, which in
# effect "unwraps" the bouncing line into just a straight one. In ascii form:
#
#     ┌────┬────┬────┬────┬────┐
#     │    │    │    │    │    │
#     │  t │ t  │  t │ t  │  t │
#     │    │    │    │    │    │
#     │ s  │  s │ s  │  s │ s  │
#     ├────┼────┼────┼────┼────┤
#     │ s  │  s │ s  │  s │ s  │
#     │    │    │    │    │    │
#     │  t │ t  │  t │ t  │  t │
#     │    │    │    │    │    │
#     ├────┼────┼────┼────┼────┤
#     │    │    │    │    │    │
#     │  t │ t  │  T │ t  │  t │
#     │    │    │    │    │    │
#     │ s  │  s │ S  │  s │ s  │
#     ├────┼────┼────┼────┼────┤
#     │ s  │  s │ s  │  s │ s  │
#     │    │    │    │    │    │
#     │  t │ t  │  t │ t  │  t │
#     │    │    │    │    │    │
#     ├────┼────┼────┼────┼────┤
#     │    │    │    │    │    │
#     │  t │ t  │  t │ t  │  t │
#     │    │    │    │    │    │
#     │ s  │  s │ S  │  s │ s  │
#     └────┴────┴────┴────┴────┘
#
# This is a lattice. I would muse on how many ostensibly engineering interview problems
# are actually just math problems but as long as we're comfortable with the fact that I
# am *not* a mathematician then I think we can all be friends.


Point = namedtuple('Point', ('x', 'y'))
Shot = namedtuple('Shot', ('bearing', 'distance', 'hit'))


def distance(a, b):
	return sqrt(((a.x - b.x) ** 2) + ((a.y - b.y) ** 2))


def bearing(a, b):
	d = Point((b.x - a.x), (b.y - a.y))
	r = abs(gcd(*d))

	return Point(d.x // r, d.y // r) if r else Point(None, None)


def get_reflected_point(room, point, offset):
	return Point(
		(room.x * offset.x) + ((room.x - point.x) if (offset.x % 2) else point.x),
		(room.y * offset.y) + ((room.y - point.y) if (offset.y % 2) else point.y),
	)


def get_reflections(room, max_distance, point):
	tiles = Point(
		int(ceil(max_distance / room.x)),
		int(ceil(max_distance / room.y)),
	)

	return {
		get_reflected_point(room, point, offset)
		for offset in
		(
			Point(x, y)
			for x in range(-tiles.x, tiles.x + 1)
			for y in range(-tiles.y, tiles.y + 1)
		)
	}


def solution(room, shooter, target, max_distance):
	room, shooter, target = Point(*room), Point(*shooter), Point(*target)

	shots = [
		Shot(
			bearing(shooter, reflected_shooter),
			distance(shooter, reflected_shooter),
			hit=False,
		)
		for reflected_shooter in get_reflections(room, max_distance, shooter)
	] + [
		Shot(
			bearing(shooter, target),
			distance(shooter, target),
			hit=True,
		)
		for target in get_reflections(room, max_distance, target)
	]

	slopes = {
		shot.bearing: shot.hit
		for shot in sorted(
			(shot for shot in shots if shot.distance <= max_distance),
			key=lambda shot: (shot.distance, shot.hit),
			reverse=True,
		)
	}

	return sum(slopes.values())

## dodge-the-lasers.py
#!/usr/bin/env python3

from decimal import Decimal, localcontext


# This is a Beatty sequence with r = sqrt(2). OEIS has this neat way to generate it that
# doesn't use much beyond basic arithmetic, but it's also linear. The hint here would
# seem to imply applying the complimentary sequence with s = r / (r - 1). So you want to
# start with the Gauss summation of 1..B_r(n) which gets you the sum of all integers in
# *both* sequences up to that point, and then remove the sum of the complementary
# sequence. It can be defined in terms of the original sequence, thus allowing for a
# recursive solution:
#
# sum(1..i) := i * (i + 1) / 2
#
# r := sqrt(2)
#
# s := r / (r - 1)
#   := sqrt(2) / (sqrt(2) - 1)
#   := sqrt(2) + 2
#
# B_r(n) := floor(n * r)
#
# B_s(n) := floor(n * s)
#        := floor(n * (sqrt(2) + 2))
#        := floor((n * 2) + (o * sqrt(2)))
#        := (n * 2) + floor(n * sqrt(2)) # As n is in Z
#        := (n * 2) + floor(n * r)
#        := (n * 2) + B_r(n)
#
# floor(B_r(n) / r) = n - 1 due to flooring. Similarly, then,
# floor(B_r(n) / s) = o, where o is the index of the last integer in B_s before B_r(n).
# This allows us to discover the index necessary to produce the complementary summation:
#
# o := floor(B_r(n) / s)
#
# sum(B_s(1)..B_s(o)) = sum((1 * 2) + B_r(1)..(o * 2) + B_r(o))
#                     = sum(B_r(1)..B_r(o)) + sum(1 * 2..o * 2)
#                     = sum(B_r(1)..B_r(o)) + (2 * sum(1..o))
#                     = sum(B_r(1)..B_r(o)) + (2 * o * (o + 1) / 2)
#                     = sum(B_r(1)..B_r(o)) + (o * (o + 1))
#
# Now with the complementary summation defined in terms of the original sequence:
#
#      sum(1..B_r(n)) = sum(B_r(1)..B_r(n)) + sum(B_s(1)..B_s(o))
# sum(B_r(1)..B_r(n)) = sum(1..B_r(n)) - sum(B_s(1)..B_s(o))
#                     = sum(1..B_r(n)) - sum(B_r(1)..B_r(o)) - (o * (o + 1))
#
# Reordered to make the recursion clearer:
#
# sum(B_r(1)..B_r(n)) = sum(1..B_r(n)) - (o * (o + 1)) - sum(B_r(1)..B_r(o))
#
# As o := floor(floor(n * sqrt(2)) / (sqrt(2) + 2)) this recurses logarithmically.


def solve(n):
	if n == 0: return 0

	# // truncates towards zero rather than rounding down, but the alternative here is the
	# kinda gross .quantize(Decimal('1'), rounding=ROUND_DOWN), and all our numbers are
	# positive anyway.
	B_rn = (n * Decimal(2).sqrt()) // 1
	o = (B_rn / (Decimal(2).sqrt() + 2)) // 1

	return (B_rn * (B_rn + 1) / 2) - (o * (o + 1)) - solve(o)


def solution(s):
	with localcontext() as ctx:
		ctx.prec = 201 # ought to be enough for anybody

		return str(solve(Decimal(s)))

## doomsday-fuel.py
#!/usr/bin/env python3

from fractions import Fraction

import numpy as np


# So this is an absorbing markov chain. I was trying to come up with a short but not
# "import the rest of the owl" solution for this, but I'm not sure that's really possible
# given the cycles between transient states: I'm going to basically have to deal with
# matrix math in some way or another. This is frankly also not what I'm good at and the
# prospect of implementing all of it in pure Python is both daunting and impractical.


def solution(m):
	# If the s0 is absorbing, 100% of the time we'll end in s0. Later we assume that s0
	# isn't an absorbing state, so we have to handle this special case first.
	if sum(m[0]) == 0: return [1] + [0] * (len(m) - 1) + [1]

	transient, absorbing = [], []
	for y, row in enumerate(m):
		if any(row): transient.append(y)
		else: absorbing.append(y)

	# For definitions, see: https://en.wikipedia.org/wiki/Absorbing_Markov_chain
	#     Q | R
	# P = --+--
	#     0 | I
	# Q and R are [t][t] and [t][r] respectively, so in either case we just need the
	# transient rows.
	# There's probably a way to get numpy to work with fractions, but I'm betting using
	# doubles will work out fine.
	m = np.matrix(m, dtype=np.double)[transient, :]
	denominator = int(np.prod(m.sum(1))) # This could've been a reduced mul of sums, but.
	m /= m.sum(1)

	Q, R = m[:, transient], m[:, absorbing]

	N = (np.identity(len(transient)) - Q).getI() # Fundamental matrix.
	B = N * R # Absorbing probabilities.

	# We just care about the probabilities of the various absorbing states from s0.
	probs = [
		Fraction.from_float(i).limit_denominator(denominator)
		for i in B[0].tolist()[0]
	]

	lcm = np.lcm.reduce([f.denominator for f in probs])

	return [f.numerator * (lcm // f.denominator) for f in probs] + [lcm]

## elevator-maintenance.py
#!/usr/bin/env python3

def solution(l): return sorted(l, key=lambda v: [int(i) for i in v.split('.')])

## fuel-injection-perfection.py
#!/usr/bin/env python3

from math import log


def solution(n):
	# This problem was fun! And by fun I mean more complicated than it initially appeared.
	#
	# So intuitively you want to maximize the string of even numbers you get, since
	# dividing by 2 is the fastest way to reduce the number to 1. This means you want to
	# turn the number you have into a power of 2 as efficiently as possible.
	#
	# "As efficiently as possible" is where it gets annoying, though: powers of 2 of
	# course grow exponentially further apart, so it's not as simple as "add or subtract
	# to the closest power of 2". But from this we can gain another intuition: given any
	# number and the choice to halve it or add/subtract, halving is *always* better
	# *unless* adding/subtracting would get you to a power of 2. Both are a single
	# operation, but halving logarithmically reduces your distance to a power of 2, and
	# thus *also* reduces the number of add/subtract ops to get onto the happy path. Of
	# course, any number 1 away from a power of 2 is also definitionally even,
	# excluding 1. So: always halve even numbers.
	#
	# But do we add or subtract odd numbers? Annoyingly, it matters! Remember we want to
	# halve as much as possible, and adding/subtracting affects that. Take 23:
	#
	#     23 +> 24 /> 12 />  6 />  3 ->  2 />  1 (vs.)
	#     23 -> 22 /> 11 -> 10 />  5 ->  4 />  2 />  1 (or)
	#     23 -> 22 /> 11 +> 12 />  6 />  3 ->  2 />  1
	#
	# or 25:
	#
	#     25 -> 24 /> 12 />  6 />  3 ->  2 />  1 (vs.)
	#     25 +> 26 /> 13 -> 12 />  6 />  3 ->  2 />  1
	#
	# Let's look at it a different way:
	#
	#     23 == 0b010111 (+)
	#     25 == 0b011001 (-)
	#     27 == 0b011011 (+ / -)
	#     29 == 0b011101 (-)
	#     31 == 0b011111 (+)
	#     33 == 0b100001 (-)
	#     35 == 0b100011 (+ / -)
	#
	# If we look at what we're doing here, the operation we prefer is *always* the one
	# that reduces the number of set bits. This makes sense as dividing by 2 is a right
	# shift of 1, and the fewer set bits the fewer times we have to interrupt those shifts
	# with an addition/subtraction to clear a bit so we can right shift "safely":
	#
	#      1 == 0b0001 (-)
	#      3 == 0b0011 (+ / -)
	#      5 == 0b0101 (-)
	#      7 == 0b0111 (+)
	#      9 == 0b1001 (-)
	#     11 == 0b1011 (+ / -)
	#     13 == 0b1101 (-)
	#     15 == 0b1111 (+)
	#
	# In some cases both operations result in the same reduction of bits, so if we ignore
	# those then a simple check emerges: if all three least significant bits are set, add
	# to clear two bits, otherwise subtract to clear 1 bit.
	#
	# We can confirm this all by writing a dumb recursive solution that gives us back the
	# number of steps and sequence of numbers from our input to 1. This also gets us an
	# integer sequence that we can plug into an on-line encyclopedia...and get A061339,
	# which defines the sequence's formula as the dumb recursive solution. So there's
	# probably not a closed form solution for this. But at least we know we got it right!

	n = int(n)
	ops = 0

	while True:
		print(n)
		if n & (n - 1) == 0: # Power of 2; fast out (assume a clever interpeter).
			return ops + int(log(n, 2))

		if n & 1: # Odd:
			if (n & 7) == 7: n += 1 # 0b111, add to clear two bits.
			else: n -= 1 # 0b101 or 0b011, subtract to clear one bit.
		else: n //= 2 # Even.

		ops += 1

## hey-i-already-did-that.py
#!/usr/bin/env python3

# I'm not going to add defensive checks/asserts because I trust you.
def positive_decimal_to_base(n, base):
	res = []
	while n:
		n, remainder = divmod(n, base)
		res.append(remainder)

	return ''.join(str(i) for i in reversed(res))


# There's probably some clever closed form way to do this, which I'm unlikely to figure
# out without googling or messing with some pen and paper for a long while.
def solution(n, b):
	# 1) Start with a random minion ID n, which is a nonnegative integer of length k in
	#    base b
	k = len(n)

	stream = {n: 0}
	while True:
		# 2) Define x and y as integers of length k. x has the digits of n in descending
		#    order, and y has the digits of n in ascending order
		x = ''.join(sorted(n, reverse=True))
		y = ''.join(reversed(x))

		# 3) Define z = x - y. Add leading zeros to z to maintain length k if necessary
		# 4) Assign n = z to get the next minion ID, and go back to step 2
		n = positive_decimal_to_base(int(x, base=b) - int(y, base=b), b).zfill(k)

		# If this n has been seen before then we're definitionally at the start of a
		# cycle: return the length of that cycle. Otherwise track what index this n is.
		if n in stream: return len(stream) - stream[n]
		else: stream[n] = len(stream)

## prepare-the-bunnies-escape.py
#!/usr/bin/env python3

from collections import deque


def get_shortest_path(m, start, end):
	queue = deque([[start]])
	seen = set([start])

	while queue:
		path = queue.popleft()

		if path[-1] == end: return len(path)

		y, x = path[-1]
		for y2, x2 in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
			if (
				0 <= y2 < len(m)
				and 0 <= x2 < len(m[y2])
				and not m[y2][x2]
				and (y2, x2) not in seen
			):
				queue.append(path + [(y2, x2)])
				seen.add((y2, x2))

	return float('inf')


def solution(m):
	end = (len(m) - 1, len(m[-1]) - 1)

	return min(
		get_shortest_path(m, (0, 0), end), # No walls removed
		min(get_shortest_path(
				(
					m[:y]
					+ [m[y][:x] + [0] + m[y][x + 1:]]
					+ m[y + 1:]
				),
				(0, 0),
				end,
			)
			for y in range(len(m))
			for x in range(len(m[y]))
			if m[y][x]
		),
	)

## re-id.py
#!/usr/bin/env python3

# Look, I could get fancy and write some sieve of eratosthenes or whatever but we only
# need 10k+5 chars here, so let's just call it precomputation for cold-start performance
# and move on with our lives.
PRIME_STRING = (
	''
	+ '2357111317192329313741434753596167717379838997101103107109113127131137139149151157'
	+ '1631671731791811911931971992112232272292332392412512572632692712772812832933073113'
	+ '1331733133734734935335936737337938338939740140941942143143343944344945746146346747'
	+ '9487491499503509521523541547557563569571577587593599601607613617619631641643647653'
	+ '6596616736776836917017097197277337397437517577617697737877978098118218238278298398'
	+ '5385785986387788188388790791191992993794194795396797197798399199710091013101910211'
	+ '0311033103910491051106110631069108710911093109711031109111711231129115111531163117'
	+ '1118111871193120112131217122312291231123712491259127712791283128912911297130113031'
	+ '3071319132113271361136713731381139914091423142714291433143914471451145314591471148'
	+ '1148314871489149314991511152315311543154915531559156715711579158315971601160716091'
	+ '6131619162116271637165716631667166916931697169917091721172317331741174717531759177'
	+ '7178317871789180118111823183118471861186718711873187718791889190119071913193119331'
	+ '9491951197319791987199319971999200320112017202720292039205320632069208120832087208'
	+ '9209921112113212921312137214121432153216121792203220722132221223722392243225122672'
	+ '2692273228122872293229723092311233323392341234723512357237123772381238323892393239'
	+ '9241124172423243724412447245924672473247725032521253125392543254925512557257925912'
	+ '5932609261726212633264726572659266326712677268326872689269326992707271127132719272'
	+ '9273127412749275327672777278927912797280128032819283328372843285128572861287928872'
	+ '8972903290929172927293929532957296329692971299930013011301930233037304130493061306'
	+ '7307930833089310931193121313731633167316931813187319132033209321732213229325132533'
	+ '2573259327132993301330733133319332333293331334333473359336133713373338933913407341'
	+ '3343334493457346134633467346934913499351135173527352935333539354135473557355935713'
	+ '5813583359336073613361736233631363736433659367136733677369136973701370937193727373'
	+ '3373937613767376937793793379738033821382338333847385138533863387738813889390739113'
	+ '9173919392339293931394339473967398940014003400740134019402140274049405140574073407'
	+ '9409140934099411141274129413341394153415741594177420142114217421942294231424142434'
	+ '2534259426142714273428342894297432743374339434943574363437343914397440944214423444'
	+ '1444744514457446344814483449345074513451745194523454745494561456745834591459746034'
	+ '6214637463946434649465146574663467346794691470347214723472947334751475947834787478'
	+ '9479347994801481348174831486148714877488949034909491949314933493749434951495749674'
	+ '9694973498749934999500350095011502150235039505150595077508150875099510151075113511'
	+ '9514751535167517151795189519752095227523152335237526152735279528152975303530953235'
	+ '3335347535153815387539353995407541354175419543154375441544354495471547754795483550'
	+ '1550355075519552155275531555755635569557355815591562356395641564756515653565756595'
	+ '6695683568956935701571157175737574157435749577957835791580158075813582158275839584'
	+ '3584958515857586158675869587958815897590359235927593959535981598760076011602960376'
	+ '0436047605360676073607960896091610161136121613161336143615161636173619761996203621'
	+ '1621762216229624762576263626962716277628762996301631163176323632963376343635363596'
	+ '3616367637363796389639764216427644964516469647364816491652165296547655165536563656'
	+ '9657165776581659966076619663766536659666166736679668966916701670367096719673367376'
	+ '7616763677967816791679368036823682768296833684168576863686968716883689969076911691'
	+ '7694769496959696169676971697769836991699770017013701970277039704370577069707971037'
	+ '1097121712771297151715971777187719372077211721372197229723772437247725372837297730'
	+ '7730973217331733373497351736973937411741774337451745774597477748174877489749975077'
	+ '5177523752975377541754775497559756175737577758375897591760376077621763976437649766'
	+ '9767376817687769176997703771777237727774177537757775977897793781778237829784178537'
	+ '8677873787778797883790179077919792779337937794979517963799380098011801780398053805'
	+ '9806980818087808980938101811181178123814781618167817181798191820982198221823182338'
	+ '2378243826382698273828782918293829783118317832983538363836983778387838984198423842'
	+ '9843184438447846184678501851385218527853785398543856385738581859785998609862386278'
	+ '6298641864786638669867786818689869386998707871387198731873787418747875387618779878'
	+ '3880388078819882188318837883988498861886388678887889389238929893389418951896389698'
	+ '9718999900190079011901390299041904390499059906790919103910991279133913791519157916'
	+ '1917391819187919992039209922192279239924192579277928192839293931193199323933793419'
	+ '3439349937193779391939794039413941994219431943394379439946194639467947394799491949'
	+ '7951195219533953995479551958796019613961996239629963196439649966196779679968996979'
	+ '7199721973397399743974997679769978197879791980398119817982998339839985198579859987'
	+ '1988398879901990799239929993199419949996799731000710009100371003910061100671006910'
	+ '0791009110093100991010310111101331013910141101511015910163101691017710181101931021'
	+ '1102231024310247102531025910267102711027310289103011030310313103211033110333103371'
	+ '0343103571036910391103991042710429104331045310457104591046310477104871049910501105'
	+ '1310529105311055910567105891059710601106071061310627106311063910651106571066310667'
	+ '1068710691107091071110723107291073310739107531077110781107891079910831108371084710'
	+ '8531085910861108671088310889108911090310909109371093910949109571097310979109871099'
	+ '3110031102711047110571105911069110711108311087110931111311117111191113111149111591'
	+ '1161111711117311177111971121311239112431125111257112611127311279112871129911311113'
	+ '1711321113291135111353113691138311393113991141111423114371144311447114671147111483'
	+ '1148911491114971150311519115271154911551115791158711593115971161711621116331165711'
	+ '6771168111689116991170111717117191173111743117771177911783117891180111807118131182'
	+ '1118271183111833118391186311867118871189711903119091192311927119331193911941119531'
	+ '1959119691197111981119871200712011120371204112043120491207112073120971210112107121'
	+ '0912113121191214312149121571216112163121971220312211122271223912241122511225312263'
	+ '1226912277122811228912301123231232912343123471237312377123791239112401124091241312'
	+ '4211243312437124511245712473124791248712491124971250312511125171252712539125411254'
	+ '7125531256912577125831258912601126111261312619126371264112647126531265912671126891'
	+ '2697127031271312721127391274312757127631278112791127991280912821128231282912841128'
	+ '5312889128931289912907129111291712919129231294112953129591296712973129791298313001'
	+ '1300313007130091303313037130431304913063130931309913103131091312113127131471315113'
	+ '1591316313171131771318313187132171321913229132411324913259132671329113297133091331'
	+ '3133271333113337133391336713381133971339913411134171342113441134511345713463134691'
	+ '3477134871349913513135231353713553135671357713591135971361313619136271363313649136'
	+ '6913679136811368713691136931369713709137111372113723137291375113757137591376313781'
	+ '1378913799138071382913831138411385913873138771387913883139011390313907139131392113'
	+ '9311393313963139671399713999140091401114029140331405114057140711408114083140871410'
	+ '7141431414914153141591417314177141971420714221142431424914251142811429314303143211'
	+ '4323143271434114347143691438714389144011440714411144191442314431144371444714449144'
	+ '6114479144891450314519145331453714543145491455114557145611456314591145931462114627'
	+ '1462914633146391465314657146691468314699147131471714723147311473714741147471475314'
	+ '7591476714771147791478314797148131482114827148311484314851148671486914879148871489'
	+ '1148971492314929149391494714951149571496914983150131501715031150531506115073150771'
	+ '5083150911510115107151211513115137151391514915161151731518715193151991521715227152'
	+ '3315241152591526315269152711527715287152891529915307153131531915329153311534915359'
	+ '1536115373153771538315391154011541315427154391544315451154611546715473154931549715'
	+ '5111552715541155511555915569155811558315601156071561915629156411564315647156491566'
	+ '1156671567115679156831572715731157331573715739157491576115767157731578715791157971'
	+ '5803158091581715823158591587715881158871588915901159071591315919159231593715959159'
	+ '7115973159911600116007160331605716061160631606716069160731608716091160971610316111'
	+ '1612716139161411618316187161891619316217162231622916231162491625316267162731630116'
	+ '3191633316339163491636116363163691638116411164171642116427164331644716451164531647'
	+ '7164811648716493165191652916547165531656116567165731660316607166191663116633166491'
	+ '6651166571666116673166911669316699167031672916741167471675916763167871681116823168'
	+ '2916831168431687116879168831688916901169031692116927169311693716943169631697916981'
	+ '1698716993170111702117027170291703317041170471705317077170931709917107171171712317'
	+ '1371715917167171831718917191172031720717209172311723917257172911729317299173171732'
	+ '1173271733317341173511735917377173831738717389173931740117417174191743117443174491'
	+ '7467174711747717483174891749117497175091751917539175511756917573175791758117597175'
	+ '9917609176231762717657176591766917681176831770717713177291773717747177491776117783'
	+ '1778917791178071782717837178391785117863178811789117903179091791117921179231792917'
	+ '9391795717959179711797717981179871798918013180411804318047180491805918061180771808'
	+ '9180971811918121181271813118133181431814918169181811819118199182111821718223182291'
	+ '8233182511825318257182691828718289183011830718311183131832918341183531836718371183'
	+ '7918397184011841318427184331843918443184511845718461184811849318503185171852118523'
	+ '1853918541185531858318587185931861718637186611867118679186911870118713187191873118'
	+ '7431874918757187731878718793187971880318839188591886918899189111891318917189191894'
	+ '7189591897318979190011900919013190311903719051190691907319079190811908719121191391'
	+ '9141191571916319181191831920719211192131921919231192371924919259192671927319289193'
	+ '0119309193191933319373193791938119387193911940319417194211942319427194291943319441'
	+ '1944719457194631946919471194771948319489195011950719531195411954319553195591957119'
	+ '5771958319597196031960919661196811968719697196991970919717197271973919751197531975'
	+ '9197631977719793198011981319819198411984319853198611986719889198911991319919199271'
	+ '9937199491996119963199731997919991199931999720011200212002320029200472005120063200'
	+ '7120089201012010720113201172012320129201432014720149201612017320177201832020120219'
	+ '2'
)

def solution(i): return PRIME_STRING[i:i + 5]

## running-with-bunnies.py
#!/usr/bin/env python3

from copy import deepcopy
from itertools import chain, combinations, islice, permutations, product
from collections import deque


# So this is an adjacency matrix of a complete graph, and our goal is to visit as many
# unique nodes as possible starting at node 0 (Start) and ending at node -1 (Bulkhead)
# with a total cost under our limit. This is basically the traveling salesman problem? But
# you want the global optimum and I can visit each node more than once, both of which
# complicate an already NP hard problem further.
#
# If we reduce the problem a bit I think we can make it work. First for every node we want
# to find the *best* path to every other node, because there's never a reason not to use
# the best path for traversal. Then we just brute all those because I'm out of intuitive
# optimizations beyond some fast outs. Luckily the graph order is small!


def powerset(iterable):
	it = list(iterable)
	return chain.from_iterable(combinations(it, r) for r in range(len(it), 0, -1))


def sliding_window(iterable, n):
	it = iter(iterable)
	window = deque(islice(it, n), maxlen=n)

	if len(window) == n:
		yield tuple(window)

	for x in it:
		window.append(x)
		yield tuple(window)


def best_costs(times):
	# https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Algorithm
	# Also see "Behavior with negative cycles"

	costs = deepcopy(times)

	for k, i, j in product(range(len(costs)), repeat=3):
		costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j])

	return costs


def has_negative_cycles(costs):
	return any(costs[i][i] < 0 for i in range(len(costs)))


def solution(times, time_limit):
	costs = best_costs(times)

	# We can abuse any negative cycle to get infinite time on the clock, which means we
	# can definitely get every bunny.
	if has_negative_cycles(costs): return list(range(len(times) - 2))

	# If not then we basically need to look at every possible combination of bunnies and
	# see which are possible to path through from the start to the bulkhead. We start
	# with the longest lists and work backwards so we can fast out. Since we're also
	# feeding an ordered list of bunnies into the powerset, the first of any n length
	# path under our time limit will also have the smallest starting bunny.
	for bunnies in powerset(range(1, len(times) - 1)): # Bunnies as their index, not ID
		if any(
			0 <= sum(
				costs[i][j]
				for i, j in sliding_window((0,) + bunnies_perm + (-1,), n=2)
			) <= time_limit
			for bunnies_perm in permutations(bunnies)
		):
			return [i - 1 for i in bunnies]
	#!/usr/bin/env python3

	from collections import namedtuple
	from fractions import gcd
	from math import ceil, sqrt


	# Calculating distances with bounces and stuff is...a pain, but given our bounce rules we
	# can instead construct infinite congruent rooms, mirrored about each other, which in
	# effect "unwraps" the bouncing line into just a straight one. In ascii form:
	#
	# ┌────┬────┬────┬────┬────┐
	# │ │ │ │ │ │
	# │ t │ t │ t │ t │ t │
	# │ │ │ │ │ │
	# │ s │ s │ s │ s │ s │
	# ├────┼────┼────┼────┼────┤
	# │ s │ s │ s │ s │ s │
	# │ │ │ │ │ │
	# │ t │ t │ t │ t │ t │
	# │ │ │ │ │ │
	# ├────┼────┼────┼────┼────┤
	# │ │ │ │ │ │
	# │ t │ t │ T │ t │ t │
	# │ │ │ │ │ │
	# │ s │ s │ S │ s │ s │
	# ├────┼────┼────┼────┼────┤
	# │ s │ s │ s │ s │ s │
	# │ │ │ │ │ │
	# │ t │ t │ t │ t │ t │
	# │ │ │ │ │ │
	# ├────┼────┼────┼────┼────┤
	# │ │ │ │ │ │
	# │ t │ t │ t │ t │ t │
	# │ │ │ │ │ │
	# │ s │ s │ S │ s │ s │
	# └────┴────┴────┴────┴────┘
	#
	# This is a lattice. I would muse on how many ostensibly engineering interview problems
	# are actually just math problems but as long as we're comfortable with the fact that I
	# am not a mathematician then I think we can all be friends.


	Point = namedtuple('Point', ('x', 'y'))
	Shot = namedtuple('Shot', ('bearing', 'distance', 'hit'))


	def distance(a, b):
	return sqrt(((a.x - b.x) 2) + ((a.y - b.y) 2))


	def bearing(a, b):
	d = Point((b.x - a.x), (b.y - a.y))
	r = abs(gcd(*d))

	return Point(d.x // r, d.y // r) if r else Point(None, None)


	def get_reflected_point(room, point, offset):
	return Point(
	(room.x * offset.x) + ((room.x - point.x) if (offset.x % 2) else point.x),
	(room.y * offset.y) + ((room.y - point.y) if (offset.y % 2) else point.y),
	)


	def get_reflections(room, max_distance, point):
	tiles = Point(
	int(ceil(max_distance / room.x)),
	int(ceil(max_distance / room.y)),
	)

	return {
	get_reflected_point(room, point, offset)
	for offset in
	(
	Point(x, y)
	for x in range(-tiles.x, tiles.x + 1)
	for y in range(-tiles.y, tiles.y + 1)
	)
	}


	def solution(room, shooter, target, max_distance):
	room, shooter, target = Point(room), Point(shooter), Point(*target)

	shots = [
	Shot(
	bearing(shooter, reflected_shooter),
	distance(shooter, reflected_shooter),
	hit=False,
	)
	for reflected_shooter in get_reflections(room, max_distance, shooter)
	] + [
	Shot(
	bearing(shooter, target),
	distance(shooter, target),
	hit=True,
	)
	for target in get_reflections(room, max_distance, target)
	]

	slopes = {
	shot.bearing: shot.hit
	for shot in sorted(
	(shot for shot in shots if shot.distance <= max_distance),
	key=lambda shot: (shot.distance, shot.hit),
	reverse=True,
	)
	}

	return sum(slopes.values())
	#!/usr/bin/env python3

	from decimal import Decimal, localcontext


	# This is a Beatty sequence with r = sqrt(2). OEIS has this neat way to generate it that
	# doesn't use much beyond basic arithmetic, but it's also linear. The hint here would
	# seem to imply applying the complimentary sequence with s = r / (r - 1). So you want to
	# start with the Gauss summation of 1..B_r(n) which gets you the sum of all integers in
	# both sequences up to that point, and then remove the sum of the complementary
	# sequence. It can be defined in terms of the original sequence, thus allowing for a
	# recursive solution:
	#
	# sum(1..i) := i * (i + 1) / 2
	#
	# r := sqrt(2)
	#
	# s := r / (r - 1)
	# := sqrt(2) / (sqrt(2) - 1)
	# := sqrt(2) + 2
	#
	# B_r(n) := floor(n * r)
	#
	# B_s(n) := floor(n * s)
	# := floor(n * (sqrt(2) + 2))
	# := floor((n * 2) + (o * sqrt(2)))
	# := (n * 2) + floor(n * sqrt(2)) # As n is in Z
	# := (n * 2) + floor(n * r)
	# := (n * 2) + B_r(n)
	#
	# floor(B_r(n) / r) = n - 1 due to flooring. Similarly, then,
	# floor(B_r(n) / s) = o, where o is the index of the last integer in B_s before B_r(n).
	# This allows us to discover the index necessary to produce the complementary summation:
	#
	# o := floor(B_r(n) / s)
	#
	# sum(B_s(1)..B_s(o)) = sum((1 * 2) + B_r(1)..(o * 2) + B_r(o))
	# = sum(B_r(1)..B_r(o)) + sum(1 * 2..o * 2)
	# = sum(B_r(1)..B_r(o)) + (2 * sum(1..o))
	# = sum(B_r(1)..B_r(o)) + (2 * o * (o + 1) / 2)
	# = sum(B_r(1)..B_r(o)) + (o * (o + 1))
	#
	# Now with the complementary summation defined in terms of the original sequence:
	#
	# sum(1..B_r(n)) = sum(B_r(1)..B_r(n)) + sum(B_s(1)..B_s(o))
	# sum(B_r(1)..B_r(n)) = sum(1..B_r(n)) - sum(B_s(1)..B_s(o))
	# = sum(1..B_r(n)) - sum(B_r(1)..B_r(o)) - (o * (o + 1))
	#
	# Reordered to make the recursion clearer:
	#
	# sum(B_r(1)..B_r(n)) = sum(1..B_r(n)) - (o * (o + 1)) - sum(B_r(1)..B_r(o))
	#
	# As o := floor(floor(n * sqrt(2)) / (sqrt(2) + 2)) this recurses logarithmically.


	def solve(n):
	if n == 0: return 0

	# // truncates towards zero rather than rounding down, but the alternative here is the
	# kinda gross .quantize(Decimal('1'), rounding=ROUND_DOWN), and all our numbers are
	# positive anyway.
	B_rn = (n * Decimal(2).sqrt()) // 1
	o = (B_rn / (Decimal(2).sqrt() + 2)) // 1

	return (B_rn * (B_rn + 1) / 2) - (o * (o + 1)) - solve(o)


	def solution(s):
	with localcontext() as ctx:
	ctx.prec = 201 # ought to be enough for anybody

	return str(solve(Decimal(s)))
	#!/usr/bin/env python3

	from fractions import Fraction

	import numpy as np


	# So this is an absorbing markov chain. I was trying to come up with a short but not
	# "import the rest of the owl" solution for this, but I'm not sure that's really possible
	# given the cycles between transient states: I'm going to basically have to deal with
	# matrix math in some way or another. This is frankly also not what I'm good at and the
	# prospect of implementing all of it in pure Python is both daunting and impractical.


	def solution(m):
	# If the s0 is absorbing, 100% of the time we'll end in s0. Later we assume that s0
	# isn't an absorbing state, so we have to handle this special case first.
	if sum(m[0]) == 0: return [1] + [0] * (len(m) - 1) + [1]

	transient, absorbing = [], []
	for y, row in enumerate(m):
	if any(row): transient.append(y)
	else: absorbing.append(y)

	# For definitions, see: https://en.wikipedia.org/wiki/Absorbing_Markov_chain
	# Q \| R
	# P = --+--
	# 0 \| I
	# Q and R are [t][t] and [t][r] respectively, so in either case we just need the
	# transient rows.
	# There's probably a way to get numpy to work with fractions, but I'm betting using
	# doubles will work out fine.
	m = np.matrix(m, dtype=np.double)[transient, :]
	denominator = int(np.prod(m.sum(1))) # This could've been a reduced mul of sums, but.
	m /= m.sum(1)

	Q, R = m[:, transient], m[:, absorbing]

	N = (np.identity(len(transient)) - Q).getI() # Fundamental matrix.
	B = N * R # Absorbing probabilities.

	# We just care about the probabilities of the various absorbing states from s0.
	probs = [
	Fraction.from_float(i).limit_denominator(denominator)
	for i in B[0].tolist()[0]
	]

	lcm = np.lcm.reduce([f.denominator for f in probs])

	return [f.numerator * (lcm // f.denominator) for f in probs] + [lcm]
	#!/usr/bin/env python3

	def solution(l): return sorted(l, key=lambda v: [int(i) for i in v.split('.')])
	#!/usr/bin/env python3

	from math import log


	def solution(n):
	# This problem was fun! And by fun I mean more complicated than it initially appeared.
	#
	# So intuitively you want to maximize the string of even numbers you get, since
	# dividing by 2 is the fastest way to reduce the number to 1. This means you want to
	# turn the number you have into a power of 2 as efficiently as possible.
	#
	# "As efficiently as possible" is where it gets annoying, though: powers of 2 of
	# course grow exponentially further apart, so it's not as simple as "add or subtract
	# to the closest power of 2". But from this we can gain another intuition: given any
	# number and the choice to halve it or add/subtract, halving is always better
	# unless adding/subtracting would get you to a power of 2. Both are a single
	# operation, but halving logarithmically reduces your distance to a power of 2, and
	# thus also reduces the number of add/subtract ops to get onto the happy path. Of
	# course, any number 1 away from a power of 2 is also definitionally even,
	# excluding 1. So: always halve even numbers.
	#
	# But do we add or subtract odd numbers? Annoyingly, it matters! Remember we want to
	# halve as much as possible, and adding/subtracting affects that. Take 23:
	#
	# 23 +> 24 /> 12 /> 6 /> 3 -> 2 /> 1 (vs.)
	# 23 -> 22 /> 11 -> 10 /> 5 -> 4 /> 2 /> 1 (or)
	# 23 -> 22 /> 11 +> 12 /> 6 /> 3 -> 2 /> 1
	#
	# or 25:
	#
	# 25 -> 24 /> 12 /> 6 /> 3 -> 2 /> 1 (vs.)
	# 25 +> 26 /> 13 -> 12 /> 6 /> 3 -> 2 /> 1
	#
	# Let's look at it a different way:
	#
	# 23 == 0b010111 (+)
	# 25 == 0b011001 (-)
	# 27 == 0b011011 (+ / -)
	# 29 == 0b011101 (-)
	# 31 == 0b011111 (+)
	# 33 == 0b100001 (-)
	# 35 == 0b100011 (+ / -)
	#
	# If we look at what we're doing here, the operation we prefer is always the one
	# that reduces the number of set bits. This makes sense as dividing by 2 is a right
	# shift of 1, and the fewer set bits the fewer times we have to interrupt those shifts
	# with an addition/subtraction to clear a bit so we can right shift "safely":
	#
	# 1 == 0b0001 (-)
	# 3 == 0b0011 (+ / -)
	# 5 == 0b0101 (-)
	# 7 == 0b0111 (+)
	# 9 == 0b1001 (-)
	# 11 == 0b1011 (+ / -)
	# 13 == 0b1101 (-)
	# 15 == 0b1111 (+)
	#
	# In some cases both operations result in the same reduction of bits, so if we ignore
	# those then a simple check emerges: if all three least significant bits are set, add
	# to clear two bits, otherwise subtract to clear 1 bit.
	#
	# We can confirm this all by writing a dumb recursive solution that gives us back the
	# number of steps and sequence of numbers from our input to 1. This also gets us an
	# integer sequence that we can plug into an on-line encyclopedia...and get A061339,
	# which defines the sequence's formula as the dumb recursive solution. So there's
	# probably not a closed form solution for this. But at least we know we got it right!

	n = int(n)
	ops = 0

	while True:
	print(n)
	if n & (n - 1) == 0: # Power of 2; fast out (assume a clever interpeter).
	return ops + int(log(n, 2))

	if n & 1: # Odd:
	if (n & 7) == 7: n += 1 # 0b111, add to clear two bits.
	else: n -= 1 # 0b101 or 0b011, subtract to clear one bit.
	else: n //= 2 # Even.

	ops += 1
	#!/usr/bin/env python3

	# I'm not going to add defensive checks/asserts because I trust you.
	def positive_decimal_to_base(n, base):
	res = []
	while n:
	n, remainder = divmod(n, base)
	res.append(remainder)

	return ''.join(str(i) for i in reversed(res))


	# There's probably some clever closed form way to do this, which I'm unlikely to figure
	# out without googling or messing with some pen and paper for a long while.
	def solution(n, b):
	# 1) Start with a random minion ID n, which is a nonnegative integer of length k in
	# base b
	k = len(n)

	stream = {n: 0}
	while True:
	# 2) Define x and y as integers of length k. x has the digits of n in descending
	# order, and y has the digits of n in ascending order
	x = ''.join(sorted(n, reverse=True))
	y = ''.join(reversed(x))

	# 3) Define z = x - y. Add leading zeros to z to maintain length k if necessary
	# 4) Assign n = z to get the next minion ID, and go back to step 2
	n = positive_decimal_to_base(int(x, base=b) - int(y, base=b), b).zfill(k)

	# If this n has been seen before then we're definitionally at the start of a
	# cycle: return the length of that cycle. Otherwise track what index this n is.
	if n in stream: return len(stream) - stream[n]
	else: stream[n] = len(stream)
	#!/usr/bin/env python3

	from collections import deque


	def get_shortest_path(m, start, end):
	queue = deque([[start]])
	seen = set([start])

	while queue:
	path = queue.popleft()

	if path[-1] == end: return len(path)

	y, x = path[-1]
	for y2, x2 in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
	if (
	0 <= y2 < len(m)
	and 0 <= x2 < len(m[y2])
	and not m[y2][x2]
	and (y2, x2) not in seen
	):
	queue.append(path + [(y2, x2)])
	seen.add((y2, x2))

	return float('inf')


	def solution(m):
	end = (len(m) - 1, len(m[-1]) - 1)

	return min(
	get_shortest_path(m, (0, 0), end), # No walls removed
	min(get_shortest_path(
	(
	m[:y]
	+ [m[y][:x] + [0] + m[y][x + 1:]]
	+ m[y + 1:]
	),
	(0, 0),
	end,
	)
	for y in range(len(m))
	for x in range(len(m[y]))
	if m[y][x]
	),
	)
	#!/usr/bin/env python3

	# Look, I could get fancy and write some sieve of eratosthenes or whatever but we only
	# need 10k+5 chars here, so let's just call it precomputation for cold-start performance
	# and move on with our lives.
	PRIME_STRING = (
	''
	+ '2357111317192329313741434753596167717379838997101103107109113127131137139149151157'
	+ '1631671731791811911931971992112232272292332392412512572632692712772812832933073113'
	+ '1331733133734734935335936737337938338939740140941942143143343944344945746146346747'
	+ '9487491499503509521523541547557563569571577587593599601607613617619631641643647653'
	+ '6596616736776836917017097197277337397437517577617697737877978098118218238278298398'
	+ '5385785986387788188388790791191992993794194795396797197798399199710091013101910211'
	+ '0311033103910491051106110631069108710911093109711031109111711231129115111531163117'
	+ '1118111871193120112131217122312291231123712491259127712791283128912911297130113031'
	+ '3071319132113271361136713731381139914091423142714291433143914471451145314591471148'
	+ '1148314871489149314991511152315311543154915531559156715711579158315971601160716091'
	+ '6131619162116271637165716631667166916931697169917091721172317331741174717531759177'
	+ '7178317871789180118111823183118471861186718711873187718791889190119071913193119331'
	+ '9491951197319791987199319971999200320112017202720292039205320632069208120832087208'
	+ '9209921112113212921312137214121432153216121792203220722132221223722392243225122672'
	+ '2692273228122872293229723092311233323392341234723512357237123772381238323892393239'
	+ '9241124172423243724412447245924672473247725032521253125392543254925512557257925912'
	+ '5932609261726212633264726572659266326712677268326872689269326992707271127132719272'
	+ '9273127412749275327672777278927912797280128032819283328372843285128572861287928872'
	+ '8972903290929172927293929532957296329692971299930013011301930233037304130493061306'
	+ '7307930833089310931193121313731633167316931813187319132033209321732213229325132533'
	+ '2573259327132993301330733133319332333293331334333473359336133713373338933913407341'
	+ '3343334493457346134633467346934913499351135173527352935333539354135473557355935713'
	+ '5813583359336073613361736233631363736433659367136733677369136973701370937193727373'
	+ '3373937613767376937793793379738033821382338333847385138533863387738813889390739113'
	+ '9173919392339293931394339473967398940014003400740134019402140274049405140574073407'
	+ '9409140934099411141274129413341394153415741594177420142114217421942294231424142434'
	+ '2534259426142714273428342894297432743374339434943574363437343914397440944214423444'
	+ '1444744514457446344814483449345074513451745194523454745494561456745834591459746034'
	+ '6214637463946434649465146574663467346794691470347214723472947334751475947834787478'
	+ '9479347994801481348174831486148714877488949034909491949314933493749434951495749674'
	+ '9694973498749934999500350095011502150235039505150595077508150875099510151075113511'
	+ '9514751535167517151795189519752095227523152335237526152735279528152975303530953235'
	+ '3335347535153815387539353995407541354175419543154375441544354495471547754795483550'
	+ '1550355075519552155275531555755635569557355815591562356395641564756515653565756595'
	+ '6695683568956935701571157175737574157435749577957835791580158075813582158275839584'
	+ '3584958515857586158675869587958815897590359235927593959535981598760076011602960376'
	+ '0436047605360676073607960896091610161136121613161336143615161636173619761996203621'
	+ '1621762216229624762576263626962716277628762996301631163176323632963376343635363596'
	+ '3616367637363796389639764216427644964516469647364816491652165296547655165536563656'
	+ '9657165776581659966076619663766536659666166736679668966916701670367096719673367376'
	+ '7616763677967816791679368036823682768296833684168576863686968716883689969076911691'
	+ '7694769496959696169676971697769836991699770017013701970277039704370577069707971037'
	+ '1097121712771297151715971777187719372077211721372197229723772437247725372837297730'
	+ '7730973217331733373497351736973937411741774337451745774597477748174877489749975077'
	+ '5177523752975377541754775497559756175737577758375897591760376077621763976437649766'
	+ '9767376817687769176997703771777237727774177537757775977897793781778237829784178537'
	+ '8677873787778797883790179077919792779337937794979517963799380098011801780398053805'
	+ '9806980818087808980938101811181178123814781618167817181798191820982198221823182338'
	+ '2378243826382698273828782918293829783118317832983538363836983778387838984198423842'
	+ '9843184438447846184678501851385218527853785398543856385738581859785998609862386278'
	+ '6298641864786638669867786818689869386998707871387198731873787418747875387618779878'
	+ '3880388078819882188318837883988498861886388678887889389238929893389418951896389698'
	+ '9718999900190079011901390299041904390499059906790919103910991279133913791519157916'
	+ '1917391819187919992039209922192279239924192579277928192839293931193199323933793419'
	+ '3439349937193779391939794039413941994219431943394379439946194639467947394799491949'
	+ '7951195219533953995479551958796019613961996239629963196439649966196779679968996979'
	+ '7199721973397399743974997679769978197879791980398119817982998339839985198579859987'
	+ '1988398879901990799239929993199419949996799731000710009100371003910061100671006910'
	+ '0791009110093100991010310111101331013910141101511015910163101691017710181101931021'
	+ '1102231024310247102531025910267102711027310289103011030310313103211033110333103371'
	+ '0343103571036910391103991042710429104331045310457104591046310477104871049910501105'
	+ '1310529105311055910567105891059710601106071061310627106311063910651106571066310667'
	+ '1068710691107091071110723107291073310739107531077110781107891079910831108371084710'
	+ '8531085910861108671088310889108911090310909109371093910949109571097310979109871099'
	+ '3110031102711047110571105911069110711108311087110931111311117111191113111149111591'
	+ '1161111711117311177111971121311239112431125111257112611127311279112871129911311113'
	+ '1711321113291135111353113691138311393113991141111423114371144311447114671147111483'
	+ '1148911491114971150311519115271154911551115791158711593115971161711621116331165711'
	+ '6771168111689116991170111717117191173111743117771177911783117891180111807118131182'
	+ '1118271183111833118391186311867118871189711903119091192311927119331193911941119531'
	+ '1959119691197111981119871200712011120371204112043120491207112073120971210112107121'
	+ '0912113121191214312149121571216112163121971220312211122271223912241122511225312263'
	+ '1226912277122811228912301123231232912343123471237312377123791239112401124091241312'
	+ '4211243312437124511245712473124791248712491124971250312511125171252712539125411254'
	+ '7125531256912577125831258912601126111261312619126371264112647126531265912671126891'
	+ '2697127031271312721127391274312757127631278112791127991280912821128231282912841128'
	+ '5312889128931289912907129111291712919129231294112953129591296712973129791298313001'
	+ '1300313007130091303313037130431304913063130931309913103131091312113127131471315113'
	+ '1591316313171131771318313187132171321913229132411324913259132671329113297133091331'
	+ '3133271333113337133391336713381133971339913411134171342113441134511345713463134691'
	+ '3477134871349913513135231353713553135671357713591135971361313619136271363313649136'
	+ '6913679136811368713691136931369713709137111372113723137291375113757137591376313781'
	+ '1378913799138071382913831138411385913873138771387913883139011390313907139131392113'
	+ '9311393313963139671399713999140091401114029140331405114057140711408114083140871410'
	+ '7141431414914153141591417314177141971420714221142431424914251142811429314303143211'
	+ '4323143271434114347143691438714389144011440714411144191442314431144371444714449144'
	+ '6114479144891450314519145331453714543145491455114557145611456314591145931462114627'
	+ '1462914633146391465314657146691468314699147131471714723147311473714741147471475314'
	+ '7591476714771147791478314797148131482114827148311484314851148671486914879148871489'
	+ '1148971492314929149391494714951149571496914983150131501715031150531506115073150771'
	+ '5083150911510115107151211513115137151391514915161151731518715193151991521715227152'
	+ '3315241152591526315269152711527715287152891529915307153131531915329153311534915359'
	+ '1536115373153771538315391154011541315427154391544315451154611546715473154931549715'
	+ '5111552715541155511555915569155811558315601156071561915629156411564315647156491566'
	+ '1156671567115679156831572715731157331573715739157491576115767157731578715791157971'
	+ '5803158091581715823158591587715881158871588915901159071591315919159231593715959159'
	+ '7115973159911600116007160331605716061160631606716069160731608716091160971610316111'
	+ '1612716139161411618316187161891619316217162231622916231162491625316267162731630116'
	+ '3191633316339163491636116363163691638116411164171642116427164331644716451164531647'
	+ '7164811648716493165191652916547165531656116567165731660316607166191663116633166491'
	+ '6651166571666116673166911669316699167031672916741167471675916763167871681116823168'
	+ '2916831168431687116879168831688916901169031692116927169311693716943169631697916981'
	+ '1698716993170111702117027170291703317041170471705317077170931709917107171171712317'
	+ '1371715917167171831718917191172031720717209172311723917257172911729317299173171732'
	+ '1173271733317341173511735917377173831738717389173931740117417174191743117443174491'
	+ '7467174711747717483174891749117497175091751917539175511756917573175791758117597175'
	+ '9917609176231762717657176591766917681176831770717713177291773717747177491776117783'
	+ '1778917791178071782717837178391785117863178811789117903179091791117921179231792917'
	+ '9391795717959179711797717981179871798918013180411804318047180491805918061180771808'
	+ '9180971811918121181271813118133181431814918169181811819118199182111821718223182291'
	+ '8233182511825318257182691828718289183011830718311183131832918341183531836718371183'
	+ '7918397184011841318427184331843918443184511845718461184811849318503185171852118523'
	+ '1853918541185531858318587185931861718637186611867118679186911870118713187191873118'
	+ '7431874918757187731878718793187971880318839188591886918899189111891318917189191894'
	+ '7189591897318979190011900919013190311903719051190691907319079190811908719121191391'
	+ '9141191571916319181191831920719211192131921919231192371924919259192671927319289193'
	+ '0119309193191933319373193791938119387193911940319417194211942319427194291943319441'
	+ '1944719457194631946919471194771948319489195011950719531195411954319553195591957119'
	+ '5771958319597196031960919661196811968719697196991970919717197271973919751197531975'
	+ '9197631977719793198011981319819198411984319853198611986719889198911991319919199271'
	+ '9937199491996119963199731997919991199931999720011200212002320029200472005120063200'
	+ '7120089201012010720113201172012320129201432014720149201612017320177201832020120219'
	+ '2'
	)

	def solution(i): return PRIME_STRING[i:i + 5]
	#!/usr/bin/env python3

	from copy import deepcopy
	from itertools import chain, combinations, islice, permutations, product
	from collections import deque


	# So this is an adjacency matrix of a complete graph, and our goal is to visit as many
	# unique nodes as possible starting at node 0 (Start) and ending at node -1 (Bulkhead)
	# with a total cost under our limit. This is basically the traveling salesman problem? But
	# you want the global optimum and I can visit each node more than once, both of which
	# complicate an already NP hard problem further.
	#
	# If we reduce the problem a bit I think we can make it work. First for every node we want
	# to find the best path to every other node, because there's never a reason not to use
	# the best path for traversal. Then we just brute all those because I'm out of intuitive
	# optimizations beyond some fast outs. Luckily the graph order is small!


	def powerset(iterable):
	it = list(iterable)
	return chain.from_iterable(combinations(it, r) for r in range(len(it), 0, -1))


	def sliding_window(iterable, n):
	it = iter(iterable)
	window = deque(islice(it, n), maxlen=n)

	if len(window) == n:
	yield tuple(window)

	for x in it:
	window.append(x)
	yield tuple(window)


	def best_costs(times):
	# https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Algorithm
	# Also see "Behavior with negative cycles"

	costs = deepcopy(times)

	for k, i, j in product(range(len(costs)), repeat=3):
	costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j])

	return costs


	def has_negative_cycles(costs):
	return any(costs[i][i] < 0 for i in range(len(costs)))


	def solution(times, time_limit):
	costs = best_costs(times)

	# We can abuse any negative cycle to get infinite time on the clock, which means we
	# can definitely get every bunny.
	if has_negative_cycles(costs): return list(range(len(times) - 2))

	# If not then we basically need to look at every possible combination of bunnies and
	# see which are possible to path through from the start to the bulkhead. We start
	# with the longest lists and work backwards so we can fast out. Since we're also
	# feeding an ordered list of bunnies into the powerset, the first of any n length
	# path under our time limit will also have the smallest starting bunny.
	for bunnies in powerset(range(1, len(times) - 1)): # Bunnies as their index, not ID
	if any(
	0 <= sum(
	costs[i][j]
	for i, j in sliding_window((0,) + bunnies_perm + (-1,), n=2)
	) <= time_limit
	for bunnies_perm in permutations(bunnies)
	):
	return [i - 1 for i in bunnies]