Rosetta Code

Hofstadter Q sequence: Difference between revisions

Page Discussion

Hofstadter Q sequence (view source)

Revision as of 22:11, 28 July 2014

156 bytes removed ,  9 years ago
→‎{{header|jq}}: faster implementation of flips(n)
(→‎{{header|jq}}: omit parenthetical remark)
(→‎{{header|jq}}: faster implementation of flips(n))
Line 970:
 
=={{header|jq}}==
For the tasks related to evaluating Q(n) directy, a recursive implementation is used, firstly because the task requirements refer to "recursion limits", and secondly to demonstrate one way to handle a cache in a functional language. To count the number of inversions, a non-recursive approach is used as it is faster and scales linearly.
The implementation here is recursive, firstly to satisfy the task
requirement regarding "recursion limits", and secondly to
demonstrate one way to handle a cache in a functional language.
 
For simplicity, we also define Q(0) = 1, so that the defining
formula also holds for n == 2, and so that we can cache Q(n) at the
n-th position of an array with index origin 0.
<lang jq>
<lang jq># Q/1 is a helper function for computing Q(n) and also for the
# function that solves the "extra credit" task.
# Q(n) as defined here returns an updated cache array such that .[n]
# is the Hofstadter value Q(n), assuming that the input is null or a
# valid cache.
 
def Q(n):▼
n as $n▼
| (if . == null then [1,1,1] else . end) as $q▼
| if $q[$n] != null then $q▼
else ▼
$q | Q($n-1) as $q1▼
| $q1 | Q($n-2) as $q2▼
| $q2 | Q($n - $q2[$n - 1]) as $q3 # Q(n - Q(n-1))▼
| $q3 | Q($n - $q3[$n - 2]) as $q4 # Q(n - Q(n-2))▼
| ($q4[$n - $q4[$n-1]] + $q4[$n - $q4[$n -2]]) as $ans▼
| $q4 | setpath( [$n]; $ans)▼
end ;▼
 
 
# For n>=2, Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2))
def Q:
def Q: . as $n | null | Q($n) | .[$n];▼
▲ def Q(n):
 
▲ n as $n
▲ | (if . == null then [1,1,1] else . end) as $q
▲ | if $q[$n] != null then $q
▲ else
▲ $q | Q($n-1) as $q1
▲ | $q1 | Q($n-2) as $q2
▲ | $q2 | Q($n - $q2[$n - 1]) as $q3 # Q(n - Q(n-1))
▲ | $q3 | Q($n - $q3[$n - 2]) as $q4 # Q(n - Q(n-2))
▲ | ($q4[$n - $q4[$n-1]] + $q4[$n - $q4[$n -2]]) as $ans
▲ | $q4 | setpath( [$n]; $ans)
▲ end ;
▼
▲def Q: . as $n | null | Q($n) | .[$n];
# count the number of times Q(i) > Q(i+1) for 0 < i < n
def flips(n):
(reduce range(13; n) as $in
( [01,null1,1]; . #+ [ count;.[$n cache- .[$n-1]] + .[$n - .[$n - 2 ]] ] )) as $q
| reduce range(0; .[0]n) as $counti
|(0; .[1] |+ Q(if $q[$i)] as> $rq[$i + 1] then 1 else 0 end)) ;
 
| $r | Q($i + 1) as $s
# The three tasks: at hand:▼
| (if $s[$i] > $s[$i + 1] then 1 else 0 end) as $one
| [ $count + $one, $s ] )
| .[0] ;
▲
▲# The three tasks at hand:
((range(0;11), 1000) | "Q(\(.)) = \( . | Q)"),
 
(100100000 | "flips(\(.)) = \(flips(.))")</lang>
===Transcript===
<lang bash>
Line 1,035 ⟶ 1,023:
flips(100000) = 49798
 
real 0m580m0.566s562s
user 0m450m0.799s541s
sys 0m90m0.187s011s</lang>
 
=={{header|Julia}}==
Peak
2,502

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/203549"