96 lines
2.5 KiB
Ruby
96 lines
2.5 KiB
Ruby
# This script finds table for 3x5 decimal fonts.
|
|
|
|
fonts = <<END
|
|
### .#. ### ### #.# ### ### ### ### ###
|
|
#.# ##. ..# ..# #.# #.. #.. #.# #.# #.#
|
|
#.# .#. ### ### ### ### ### ..# ### ###
|
|
#.# .#. #.. ..# ..# ..# #.# .#. #.# ..#
|
|
### ### ### ### ..# ### ### .#. ### ###
|
|
END
|
|
fonts = fonts.lines.map {|l| l.scan(/\S{3}/) }.transpose
|
|
fonts = fonts.join.scan(/.{15}/).map {|l| l.tr(".#", "01").reverse.to_i(2) }
|
|
|
|
|
|
def printable?(x)
|
|
35 <= x && x != 92 && x <= 126
|
|
end
|
|
|
|
# Given integers d, e, and f, finds (x, y) s.t. x*d - y*e = f, where x and y
|
|
# are both printable.
|
|
def solve_identity(d, e, f)
|
|
# First we solve Bezout's identity by using the extended gcd algorithm.
|
|
# See the wikipedia entry in detail.
|
|
g = d.gcd(e)
|
|
return if f % g != 0 # No solution
|
|
d, e, f = d / g, e / g, f / g
|
|
a, b = d, -e
|
|
x0, x1 = 1, 0
|
|
y0, y1 = 0, 1
|
|
while b != 0
|
|
q = a / b
|
|
a, b = b, a % b
|
|
x0, x1 = x1, x0 - x1 * q
|
|
y0, y1 = y1, y0 - y1 * q
|
|
end
|
|
|
|
# Now we have solution candidates.
|
|
# x = -f * x0 - e * t
|
|
# y = -f * y0 - d * t
|
|
# where t is a free parameter.
|
|
# Then, we consider another constraint: x and y is both printable.
|
|
|
|
# We must satisfy: 35 <= x <= 126
|
|
# -> ceil((35+f*x0) / e) <= -t <= floor((126+f*x0) / e)
|
|
# -> ceil((35+f*x0) / e) * d - f*y0 <= y <= floor((126+f*x0) / e) * d - f*y0
|
|
ymin = ( 35+f*x0+e+1) / e * d - f*y0
|
|
ymax = (126+f*x0 ) / e * d - f*y0
|
|
|
|
return if ymax < ymin || ymax < 33 || ymin > 126 # No solution.
|
|
|
|
((ymax + f*y0) / -d).upto((ymin + f*y0) / -d) do |t|
|
|
x = -f * x0 - e * t
|
|
y = -f * y0 - d * t
|
|
return [x, y] if printable?(x) && printable?(y) # Solution found.
|
|
end
|
|
|
|
return # No solution.
|
|
end
|
|
|
|
# Given integers f0, f1, ..., f9, by brute force, finds (u, v, d) s.t. there is
|
|
# some xi and yi:
|
|
# x0 * u - y0 * v = f0 + d
|
|
# x1 * u - y1 * v = f1 + d
|
|
# ...
|
|
# x9 * u - y9 * v = f9 + d
|
|
# where both xi and yi are printable.
|
|
def find_params(fonts)
|
|
1.upto(9) do |d|
|
|
2.times do
|
|
1.upto(999) do |u|
|
|
1.upto(999) do |v|
|
|
if fonts.all? {|f| solve_identity(u, v, f + d) }
|
|
table = fonts.map do |f|
|
|
solve_identity(u, v, f + d).reverse
|
|
end.transpose.flatten.map {|c| c.chr }.join
|
|
return u, v, d, table
|
|
end
|
|
end
|
|
end
|
|
d = -d
|
|
end
|
|
end
|
|
puts "Not found."
|
|
exit
|
|
end
|
|
|
|
|
|
puts "Searching..."
|
|
|
|
u, v, d, s = find_params(fonts)
|
|
|
|
puts "Found."
|
|
puts
|
|
puts "Let s = %p." % s
|
|
puts "You can get the font data of decimal character 'n' (0--9):"
|
|
puts " %d * s[n+10] - %d * s[n] - %d" % [u, v, d]
|