Hofstadter’s FIGURE-FIGURE Sequences
December 1, 2015
We discussed this task in a previous exercise. The solution given there can be found at http://programmingpraxis.codepad.org/XzHqlaHb.
A collection of etudes, updated weekly, for the education and enjoyment of the savvy programmer
We discussed this task in a previous exercise. The solution given there can be found at http://programmingpraxis.codepad.org/XzHqlaHb.
Pages: 1 2
Haskell:
[…] Problem: Hofstadter’s FIGURE-FIGURE sequences […]
Pyhon:
def r_series(n):
‘Hofstadter’s FIGURE-FIGURE Sequences’
def r(n):
if n<=1:return 1
else:return r(n-1)+s(n-1, r_list)
def s(n, r_list):
if n<=1: return 2
else:
check = False
i=1
while not check:
if s(n-1,r_list)+i not in r_list: break
i+=1
return s(n-1,r_list)+i
r_list=[]
for i in xrange(1,n):r_list.append(r(i))
return r(n)
def s_series(n):
return r_series(n+1) -r_series(n)
print [r_series(x) for x in xrange(1,10)]
print [s_series(x) for x in xrange(1,10)]
Solution in python http://pastebin.com/zCF7b3m6
Ruby solution
figure_seq=[1]
space_seq=[2]
(0..15).each do |x|
figure_item = figure_seq[x]+space_seq[x]
puts figure_item
space_item = space_seq[x].next
figure_seq<<figure_item
until !figure_seq.include? space_item
space_item += 1
end
space_seq<<space_item
end
puts figure_seq.join(" ")
puts space_seq.join(" ")
Here are three solutions, a nice C loop (this is the Bach solution):
#include <stdio.h> void h(int *a, int N) { int *p = a, *q = a+1, n; for (*p = n = 1; q < a+N; q++, n++) { if (n == *p) { p++; n++; } *q = *(q-1) + n; } } int main() { int N = 20, a[N]; h(a,N); for (int i = 0; i < N; i++) { printf("%d ", a[i]); } printf("\n"); }A Gödelian solution in Haskell:
And finally, for Escher, BCM2835 GPU assembler, for a Raspberry Pi:
@praxis: Hope you are feeling better. GEB is fun, haven’t read it for a long time – have added to my Christmas list.
Here’s a single python generator that generates sequence 1 if called with an argument of 1 and the second sequence if called with an argument of 2.
def seq(which): ns = {1:False} n = 1 for d in it.count(1): if ns.pop(d, True): yield n if which == 1 else d n += d ns[n] = False list(it.islice(seq(1), 20)) => [1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260] list(it.islice(seq(2), 20)) => [2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25]@Mike: nice solution and got me thinking about bit representations and run length encoding. Finally came up with this (I think rather fine) Haskell solution, note that “elr” is “rle” backwards and “scanl (+) n s” generates the sequence from n whose (first) differences are s. hof2 is the 1,3,7.. sequence, hof1 is the complement (my previous solutions only generated hof2):
Here’s a better solution, including series h0, the second differences series. The elr function is the same, but rewritten to use basic functions.
def figure1(maxSize): l = [1, 3, 7] adder = 5 index = 2 if maxSize < 3: return l[:maxSize] while len(l) < maxSize: if l[index] != adder: l.append(adder + l[-1]) else: index += 1 adder += 1 return l def figure2(maxSize): l = [2, 4, 5] dontAdd = 7 index = 2 if maxSize < 3: return l[:maxSize] while len(l) < maxSize: if l[-1] + 1 != dontAdd: l.append(l[-1] + 1) else: dontAdd += l[index] index += 1 l.append(l[-1] + 2) return lfigure1(s) generates the first s elements of first sequence and similarly figure2(s)
[…] A quick and dirty, powershell solution to the hofstadters-figure-figure-sequences problem. […]