题解、Writeup、游记和碎碎念
Given a c file, which calls lua, and we need to finish two tasks.
In the first one, we need to construct an injective map between 8 distinct numbers from 0 to 39999, and 7 distinct numbers with their permutation. Note that C(40000,8)/C(40000,7) is about 5000, which is less than 7!, thus it’s possible. We may delete the number which is k-th smallest, where k is the total sum of 8 numbers modulo 8. For any 7-number tuples, there exists about 5000(more precisely, less than 5008) other numbers, such that it will be deleted. We can find the rank of the actual one in them, and encode it into a permutation.
In the second task, Alice is given an array of length 96, consists of 32 2s and 64 1s, she needs to mark 32 of the 1s to 0. Bob is given the remaining array, but he only knows whether a number is 0. He needs to find all “2”s. In fact, the task needs a bijective map from C(96,32) to C(96,32), but each pair don’t have common elements. We may split the sequence into blocks of length 2, if some block is 01 or 10, just flip it. Otherwise, we obtain a new sequence with 11 and 00, thus it’s the same as the original problem, and we can recursively solve it.
function nthperm(n)
s={}
t=1
for i=1,7,1 do
a=n//t
t=t*i
b=a//i
c=a-i*b
s[i]=c+1
end
for i=1,7,1 do
for j=1,i-1,1 do
if s[j]>=s[i] then
s[j]=s[j]+1
end
end
end
return s
end
function permrank(s)
s=table.shallow_copy(s)
n=0
t=1
for i=7,1,-1 do
for j=1,i-1,1 do
if s[j]>s[i] then
s[j]=s[j]-1
end
end
end
for i=1,7,1 do
n=n+(s[i]-1)*t
t=t*i
end
return n
end
function getdel(s)
sum=0
for i=1,8,1 do
sum=sum+s[i]
end
return s[sum-(sum//8)*8+1]
end
function table.shallow_copy(t)
local res={}
for k=1,#t,1 do
res[k]=t[k]
end
return res
end
function count(l,r,r2,v)
if(r>r2)then
r=r2
end
if(l>r)then
return 0
end
lt=l//8
rt=r//8
if(lt==rt)then
if(l<=lt*8+v and lt*8+v<=r)then
return 1
end
return 0
end
res=rt-lt-1
if(l<=lt*8+v)then
res=res+1
end
if(rt*8+v<=r)then
res=res+1
end
return res
end
function modt(x)
if(x<0)then
return x+8
end
return x
end
function countus(s,x)
sum=0
for i=1,7,1 do
sum=sum+s[i]
end
sum=sum-(sum//8)*8
res=count(0,s[1]-1,x,modt(-sum))
for i=1,6,1 do
res=res+count(s[i]+1,s[i+1]-1,x,modt(i-sum))
end
res=res+count(s[7]+1,39999,x,modt(7-sum))
return res
end
function kthus(s,k)
l=-1
r=39999
while l+1<r do
mid=(l+r)//2
if(countus(s,mid)>=k)then
r=mid
else
l=mid
end
end
return r
end
function Alice1(s)
table.sort(s)
x=getdel(s)
local res={}
for i=1,8,1 do
if(s[i]~=x)then
table.insert(res,s[i])
end
end
c=countus(res,x)
rv=nthperm(c)
resn={}
for i=1,7,1 do
resn[i]=res[rv[i]]
end
return resn
end
function Bob1(s)
res=table.shallow_copy(s)
table.sort(s)
rv={}
for i=1,7,1 do
for j=1,7,1 do
if res[i]==s[j] then
rv[i]=j
end
end
end
c=permrank(rv)
t=kthus(s,c)
return t
end
function getothseq(s)
if(#s==1)then
return s
end
if(#s-(#s//2)*2==1)then
tmp=table.shallow_copy(s)
table.remove(tmp)
tmp=getothseq(tmp)
table.insert(tmp,0)
return tmp
end
tmp={}
for i=1,#s-1,2 do
if(s[i]==s[i+1])then
table.insert(tmp,s[i])
end
end
tmp=getothseq(tmp)
c=0
res={}
for i=1,#s-1,2 do
if(s[i]==s[i+1])then
c=c+1
table.insert(res,tmp[c])
table.insert(res,tmp[c])
else
table.insert(res,s[i+1])
table.insert(res,s[i])
end
end
return res
end
function Alice2(s)
tmp={}
for i=1,96,1 do
table.insert(tmp,s[i]-1)
end
v=getothseq(tmp)
res={}
for i=1,96,1 do
if(s[i]==1 and v[i]==1) then
table.insert(res,i)
end
end
return res
end
function Bob2(s)
tmp={}
for i=1,96,1 do
table.insert(tmp,1-s[i])
end
v=getothseq(tmp)
res={}
for i=1,96,1 do
if(s[i]==1 and v[i]==1) then
table.insert(res,i)
end
end
return res
end
Run the game with HyperZebra, we find that it checks the solution with some external function, if all three levels are passed, it will output flag using the solution and some built-in keys.
The checking part is like a cellular automaton, and we can find the solution by bfs. Finally, just play the game with these paths, and we can see the flag.
s='rrbrb rg g bgrbgggr ggrgr gr rg brr b bggrbgbb'
t={' ':0,'r':1,'g':2,'b':3}
v=' rgb'
s=[list(s[i:i+7])for i in range(0,49,7)]
for i in range(7):
for j in range(7):
s[i][j]=t[s[i][j]]
def get(x,y):
if x<0 or x>6 or y<0 or y>6:
return 0
return s[x][y]
def get_neighbors(x,y):
c=[0]*4
for i in range(-1,2):
for j in range(-1,2):
if i or j:
c[get(x+i,y+j)]+=1
return c[1],c[2],c[3]
def nxt(s):
r=[[0]*7 for i in range(7)]
for i in range(7):
for j in range(7):
c1,c2,c3=get_neighbors(i,j)
arg4,arg2,arg0=c1,c2,c3
if s[i][j]==0:
if arg2==0 and arg0==0:
arg6=0
elif arg0<arg2:
arg6=2
else:
arg6=3
elif s[i][j]==1:
if arg4!=2 and arg4!=3:
arg6=0
elif arg0==0 or arg2==0:
arg6=0
else:
arg6=1
elif s[i][j]==2:
if arg4>4:
arg6=0
elif arg0>4:
arg6=3
elif arg4==2 or arg4==3:
arg6=1
else:
arg6=2
else:
assert s[i][j]==3
if arg4>4:
arg6=0
elif arg2>4:
arg6=2
elif arg4==2 or arg4==3:
arg6=1
else:
arg6=3
r[i][j]=arg6
return r
def ok_red(x1,y1,x2,y2):
if x1<0 or x1>7 or y1<0 or y1>7:
return 0
if x2<0 or x2>7 or y2<0 or y2>7:
return 0
if x1==x2:
if y1>y2:y1=y2
return get(x1,y1)==1 or get(x1-1,y1)==1
assert y1==y2
if x1>x2:x1=x2
return get(x1,y1)==1 or get(x1,y1-1)==1
pos=[(0,0,'','(0,0)')]
for i in range(50):
npos=set()
for x,y,path,his in pos:
for nx,ny,d in [(x-1,y,'u'),(x+1,y,'d'),(x,y-1,'l'),(x,y+1,'r')]:
if ok_red(x,y,nx,ny):
np=path+d
if '(%d,%d)'%(nx,ny) in his:
continue
npos.add((nx,ny,np,his+'(%d,%d)'%(nx,ny)))
pos=npos
for x,y,path,his in pos:
if x==7 and y==7:
print(len(path),path)
s=nxt(s)
It contains a big matrix, elements fall down, change according to the characters of the flag, and interact with each other. In fact, each line of the puzzle is independent. The last element will “eat” every element in front of it, and finally check if it’s equal to some constant. There are 64 different statuses in this process, and in fact it’s just xor (but shuffled). So we can find some relations about the xor, and find the flag by gauss elimination.
raw=open('code.txt','r',encoding='utf-8').readlines()
cmap={}
for i in range(1139,1267):
a,b=raw[i].strip().split(' = ')
cmap[a]=b
cmap['C']='fljldviokmmfmqzd'
cmap['F']='iawjsmjfczakueqy'
cmap['.']='.'
cmap['X']='X'
rule1s=[]
rule1={}
rule1x={}
for i in range(64):
rule1['char'+str(i)]={}
for i in range(1427,5523):
t=raw[i].strip()
a,b=t[:-6].split(' -> ')
ax,ay=a[2:-2].split(' | ')
bx,by=b[2:-2].split(' | ')
rule1s.append((ay,ax,bx))
rule1[ay][ax]=bx
if ax not in rule1x:
rule1x[ax]={}
rule1x[ax][bx]=ay
rule2s=[]
rule2={}
rule2x={}
for i in range(5523,9619):
t=raw[i].strip()
a,c=t[8:-10].split(' ] -> [ ')
a,b=a.split(' | ')
rule2s.append((a,b,c))
if a not in rule2:
rule2[a]={}
rule2[a][b]=c
if c not in rule2x:
rule2x[c]={}
rule2x[c][a]=b
rule3s=[]
rule3={}
for i in range(9619,9747):
t=raw[i].strip()
a,c=t[2:-10].split(' ] -> [ ')
a,b=a.split(' | ')
rule3s.append((a,b,c))
if a not in rule3:
rule3[a]={}
rule3[a][b]=c
board=[]
for i in range(9760,9806):
t=list(raw[i].strip())
for j in range(len(t)):
t[j]=cmap[t[j]]
board.append(t)
board.append(['']*47)
board.append(['X']+['char63']*45+['X'])
charmap=list(map(chr,range(65,65+26)))+list(map(chr,range(97,97+26)))+list(map(chr,range(48,48+10)))+['{','}']
req='kkavwvmbabfuqctz'
slist=[]
for x in rule2x[req]:
slist.append(rule2x[req][x])
sid={}
for i in range(64):
sid[slist[i]]=i
tbl=[[0]*64 for i in range(64)]
for tr in slist:
for op1 in range(64):
t=board[1][2]
v=rule1['char'+str(op1)][t]
nxt=rule2x[tr][v]
tbl[sid[tr]][op1]=sid[nxt]
t=[]
u=0
cur=set([u])
while True:
x=0
while x<64 and tbl[u][x] in cur:
x+=1
if x==64:
break
t.append(x)
for i in cur.copy():
cur.add(tbl[i][x])
curu=[]
for i in range(64):
if tbl[u][i] in cur:
curu.append(i)
sr=[]
for i in range(64):
v=u
for j in range(6):
if i>>j&1:
v=tbl[v][t[j]]
for j in range(64):
if tbl[u][j]==v:
sr.append(j)
sl=[]
for i in range(64):
sl.append(tbl[u][sr[i]])
slrev=[0]*64
for i in range(64):
slrev[sl[i]]=i
eq=[]
for X in range(45,0,-1):
cur=[]
xor_const=slrev[sid[req]]^slrev[sid[board[X][46]]]
for Y in range(1,46):
t=board[X][Y]
tmp=[0]*6
for i in range(6):
k=sr[1<<i]
v=rule1['char'+str(k)][t]
tmp[i]=slrev[sid[rule2x[slist[sl[0]]][v]]]
cur+=tmp
for i in range(6):
t=[]
for j in cur:
t.append(j>>i&1)
t.append(xor_const>>i&1)
eq.append(t)
s=eq
n=len(s)
m=len(s[0])
c=0
for i in range(m-1):
if not s[c][i]:
t=c+1
while t<n and not s[t][i]:
t+=1
s[c],s[t]=s[t],s[c]
for j in range(n):
if j!=c and s[j][i]:
for k in range(m):
s[j][k]^=s[c][k]
c+=1
for i in range(0,45*6,6):
t=sum(s[i+j][m-1]<<j for j in range(6))
print(charmap[sr[t]],end='')
print()
日期： 2020-04-29
这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/283/ 查看。