Skip to content

Instantly share code, notes, and snippets.

@vuryleo
Last active November 6, 2015 23:34
Show Gist options
  • Save vuryleo/6fdd62ae8be8cd25e590 to your computer and use it in GitHub Desktop.
Save vuryleo/6fdd62ae8be8cd25e590 to your computer and use it in GitHub Desktop.
import sys
def shiftL(l, s):
return l[s:] + l[:s]
def getDiff(li, totalLen):
if len(li) < 2:
raise Exception('toooo short')
li.append(totalLen + li[0])
nl = [li[i+1] - li[i] for i in range(len(li) - 1)]
return nl
def genShiftIndex(l, s):
sl = shiftL(l, s)
s = set(sl)
index = {i: [j for j in range(len(l)) if sl[j] == i] for i in s}
index = {k: v for k,v in index.iteritems() if len(v) > 1}
return index
def genShiftDiff(l, s):
return {k: getDiff(v, len(l)) for k, v in genShiftIndex(l, s).iteritems()}
def genShiftdIndex(l, s):
index = genShiftIndex(l, s)
dindex = [v[0] for k,v in index.iteritems()]
return sorted(dindex)
def genShiftdDiff(l, s):
return getDiff(genShiftdIndex(l, s), len(l))
def comparedshift(l, a, b):
if genShiftdDiff(l, a) < genShiftdDiff(l, b):
return 'less'
elif genShiftdDiff(l, a) > genShiftdDiff(l, b):
return 'more'
else:
da = genShiftDiff(l, a)
db = genShiftDiff(l, b)
ia = genShiftdIndex(l, a)
ib = genShiftdIndex(l, b)
for i in range(len(ia)):
va = shiftL(l, a)[ia[i]]
vb = shiftL(l, b)[ib[i]]
if da[va] < db[vb]:
return 'less'
elif da[va] > db[vb]:
return 'more'
return 'equal'
def genCode(l, i):
if i == -1:
return 'unique'
di = genShiftdIndex(l, i)
d = genShiftDiff(l, i)
if len(di) == 1:
return 'single' + str(d[shiftL(l, i)[di[0]]])
dd = genShiftdDiff(l, i)
string = 'multi' + str(dd)
for pi in di:
va = shiftL(l, i)[pi]
string = string + str(d[va])
return string
# def compareEqual(ca, cb):
# la, ia = ca
# lb, ib = cb
# if ia == -1 or ib == -1:
# if ia == -1 and ib == -1:
# return 'equal'
# return
# dia = genShiftdIndex(la, ia)
# dib = genShiftdIndex(lb, ib)
# da = genShiftDiff(la, ia)
# db = genShiftDiff(lb, ib)
# if len(dia) != len(dib):
# return
# if len(dia) == 0: # len(dib) == 0
# return 'equal'
# if len(dia) == 1: # len(dib) == 1
# va = shiftL(la, ia)[dia[0]]
# vb = shiftL(lb, ib)[dib[0]]
# if da[va] == db[vb]:
# return 'equal'
# return
# if genShiftdDiff(la, ia) == genShiftdDiff(lb, ib):
# for i in range(len(dia)):
# va = shiftL(la, ia)[dia[i]]
# vb = shiftL(lb, ib)[dib[i]]
# if da[va] != db[vb]:
# return
# return 'equal'
time = int(sys.stdin.readline())
for tt in range(time):
n = int(sys.stdin.readline().split(' ')[0])
code = []
for t in range(n):
l = map(int, sys.stdin.readline().split(' '))
smallest = 0
if len(genShiftdIndex(l, 0)) == 0:
smallest = -1 # all unique
elif len(genShiftdIndex(l, 0)) == 1:
for i in range(1, len(l)):
if genShiftdIndex(l, i)[0] == 0:
if genShiftDiff(l, i)[shiftL(l, i)[0]] < genShiftDiff(l, smallest)[shiftL(l, smallest)[genShiftdIndex(l, smallest)[0]]]:
smallest = i
else:
for i in range(1, len(l)):
if genShiftdIndex(l, i)[0] == 0:
result = comparedshift(l, smallest, i)
if result == 'more':
smallest = i
#print smallest, shiftL(l, smallest)
code.append(genCode(l, smallest))
#print code
#print set(map(genCode, code))
print len(set(code))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment