Changes

Jump to: navigation, search

Gits2012teaser

2,632 bytes added, 12:46, 8 January 2012
/* #2 AL's Revenge */
if (name & a)
name ^= b;
}H
return (result == 1);
}
</pre>
 
* it looks like a multiplication over a galois field, with the irreducible polynomial 0x1a348fccd93aea5a7 (note leading bit not in C), but it actually isn't, because the high bit gets checked after the shift, not before.
* lacking math knowledge and math package fu, decided to treat the problem as a linear equation system:
* The shifting and xoring produces a set of integers, call them name_i. If the serial bit s_i is set, name_i gets added to the result. So you can roughly say r = N * s, with r being the result vector, s the serial vector and N the names matrix.
* lacking math package fu, implement a gaussian elimination manually:
 
<pre>
class Numeric
def bits64
sprintf("%064b", self).each_char.map{|c| c == "0" ? 0 : 1}
end
end
 
def names(name)
p = 0xa348fccd93aea5a7
 
if (name >> 63) & 1 == 1
name ^= p
end
 
([name] + 63.times.map do |i|
name <<= 1
if (name >> 63) & 1 == 1
name ^= p
end
name
end).map(&:bits64)
end
 
class Array
def pivot
res = []
self[0].size.times.map do |i|
self.size.times.map do |j|
self[j][i]
end
end
end
 
def bitary_to_int
self.join.to_i(2)
end
end
 
class Eq < Array
attr_accessor :res
 
def initialize(ary, res)
self.replace(ary)
@res = res
end
 
def lead_zero
self.take_while{|e| e == 0}
end
 
def first_pos
self.index(1)
end
 
def subtract(o)
Eq.new(self.zip(o).map{|aa, bb| aa ^ bb}, @res ^ o.res)
end
end
 
class EqSys < Array
def initialize(ary, res=nil)
if !(Eq === ary[0]) && !ary.empty?
ary = ary.zip(res).map{|a, r| Eq.new(a, r)}
end
self.replace(ary)
end
 
def sort_by_zeros
self.sort do |a, b|
a.lead_zero <=> b.lead_zero
end
end
 
def subtract_eq(eq)
pos = eq.first_pos
return self if not pos
EqSys.new(self.map{|e| e[pos] == 1 ? e.subtract(eq) : e})
end
 
def elim
front = EqSys.new([])
cur = nil
rest = self.sort_by_zeros
while not rest.empty?
front << cur if cur
cur = rest.shift
 
front = front.subtract_eq(cur)
rest = rest.subtract_eq(cur)
rest = rest.sort_by_zeros
end
front << cur
 
front
end
 
def to_s
self.map{|e| e.map(&:to_s).join + " = #{e.res}"}.join("\n")
end
end
 
require 'pp'
if __FILE__ == $0
ns = names(0x6638623261336134)
 
pv = ns.pivot
es = EqSys.new(pv, 1.bits64)
 
puts es.to_s
puts
 
r = es.elim
puts r.to_s
 
res = r.map{|e| e.res}.reverse
puts res.bitary_to_int.to_s(16)
 
s0 = r.pivot.last.reverse
puts s0.bitary_to_int.to_s(16)
puts (res.bitary_to_int^s0.bitary_to_int).to_s(16)
end
</pre>
== #3 Hackquest ==