Weibliche und männliche Sequenzen

20

Diese Frage ist wahrscheinlich schwieriger als alle Aufgaben, bei denen "eine Folge von Zahlen generiert" wird, da hierfür ZWEI Sequenzen erforderlich sind, die gleichzeitig arbeiten.

Freue mich schon sehr auf die Antworten!

Douglas Hofstadter hat in seinem Buch " Gödel, Escher, Bach: Ein ewiger goldener Zopf " eine ganze Reihe von Zahlen in sich, die alle in irgendeiner Weise auf den vorherigen Begriff zurückgreifen. Informationen zu allen Sequenzen finden Sie auf dieser Wikipedia-Seite .

Ein Paar von Sequenzen, die wirklich interessant sind, sind die weiblichen und männlichen Sequenzen, die folgendermaßen definiert sind:

für n > 0.

Hier ist die weibliche Sequenz und die männliche Sequenz .

Ihre Aufgabe ist es, bei einer Ganzzahl nals Eingabe eine Liste der weiblichen und der männlichen Folge zurückzugeben, wobei die Anzahl der Terme nin zwei Ausgabezeilen der weiblichen Folge in der ersten Zeile und der männlichen Folge in der ersten Zeile entspricht der Zweite.

Beispiel Ein- und Ausgänge: Eingang: 5 Ausgang:[1, 1, 2, 2, 3] [0, 0, 1, 2, 2]

Eingabe: 10 Ausgabe:[1, 1, 2, 2, 3, 3, 4, 5, 5, 6] [0, 0, 1, 2, 2, 3, 4, 4, 5, 6]

HINWEIS: Die Trennung zwischen Listen bedeutet einen Zeilenumbruch.

Das ist Code-Golf, also gewinnt der kürzeste Code in Bytes. Geben Sie auch eine Erklärung für Ihren Code ein.

Bestenliste

Code-Snippet anzeigen

code-golf math sequence Clismique
quelle
5
Können wir ein Paar Listen von einer Funktion zurückgeben, anstatt die Listen zu drucken?
Zgarb
Other challenges involving Hofstadter's sequences: Q sequence, figure-figure sequence
Martin Ender
@Zgarb You can, as long as the two lists are in different lines.
clismique
2
@DerpfacePython There are no lines in a pair of lists; if a function returns a pair of lists, you can print them however you want. That being said, I'm not a huge fan of the lines requirement, even when printing the output. Cumbersome I/O formats are one of the things to avoid when writing challenges.
Dennis
4
It's no big deal for some approaches/languages, but it can make a big difference for others. In C, a lot of bytes could be saved by printing the sequences in columns rather than rows. In Python, the shortest approach I can think of is a recursive lambda similar to my recursive Julia answer that returns a pair of lists, but having to convert that into a string with a linefeed makes it a lot longer, even longer than the full program posted by Sp3000. Other approaches, such as a recursive solution that counts down instead of up, are completely ruled out since it is impossible to add the newline.
Dennis

Antworten:

3

Jelly, 22 20 bytes

ṙṪḢạL}ṭ
çƓḤ¤Ð¡1ṫ-Ṗ€G

Try it online!

How it works

çƓḤ¤Ð¡1ṫ-Ṗ€G  Main link. No user arguments. Left argument defaults to 0.
   ¤          Combine the two links to the left into a niladic chain.
 Ɠ              Read an integer from STDIN.
  Ḥ             Unhalve/double it.
ç   С1       Call the helper link that many times. Return all results.
              In the first call, the left and right argument are 0 and 1 resp.
              After each iteration, the left argument is set to the return value
              and the right argument to the prior value of the left one.
       ṫ-     Tail -1; keep the last two items of the list of results.
         Ṗ€   Discard the last item of each list.
           G  Grid; format the pair of lists.


ṙṪḢạL}ṭ       Helper link. Arguments: x, y (lists)

ṙ             Rotate x k units to the left, for each k in y.
 Ṫ            Tail; extract the last rotation.
  Ḣ           Head; extract the last element.
              This essentially computes x[y[-1]] (Python notation), avoiding
              Jelly's 1-based indexing.
    L}        Yield the length of y.
   ạ          Take the absolute difference of the results to both sides.
      ṭ       Tack; append the difference to y and return the result.
Dennis
quelle
5
And this is the part where I feel proud of myself for making a challenge that makes Jelly use more than 10 bytes.
clismique
13

Julia, 52 48 bytes

x->[n÷φ|(5n^2|4∈(2:3n).^2)for| =(+,-),n=1:x]

Try it online!

Background

In On Hofstadters Ehefeiern zeigt der Autor das

F/M formula

worin φ den goldenen Schnitt bezeichnet ,

delta/epsilon formula

und F n bezeichnet die n- te Fibonacci-Zahl .

Darüber hinaus zeigt der Antragsteller in Advanced Problems and Solutions, H-187: Fibonacci ist ein Quadrat , dass

Fibonacci/Lucas identity

Dabei bezeichnet L n die n- te Lucas-Zahl und umgekehrt, wenn

converse Fibonacci/Lucas identity

dann ist n eine Fibonacci-Zahl und m ist eine Lucas-Zahl.

Daraus leiten wir ab

delta/epsilon theorem

wann immer n> 0 .

Wie es funktioniert

Given input x, we construct a 2 by x matrix, where | is addition in the first column and subtraction in the second, and n iterates over the integers between 1 and x in the rows.

The first term of both F(n - 1) and M(n - 1) is simply n÷φ.

We compute δ(n) and ε(n) by calculating 5n² | 4 and testing if the result belongs to the array of squares of the integers between 2 and 3n. This tests both for squareness and, since 1 is not in the range, for n > 1 if | is subtraction.

Finally we add or subtract the Boolean resulting from 5n^2|4∈(2:3n).^2 to or from the previously computed integer.

Dennis
quelle
can this be expressed in a non-recursive/iterative way ?, what is the closed form for it ?
Abr001am
I've added an explanation.
Dennis
11

Python 2, 79 70 bytes

a=0,;b=1,
exec"a,b=b,a+(len(a)-b[a[-1]],);"*~-input()*2
print b,'\n',a

Iterative rather than recursive, because why not. The first line has a trailing space - if that's not okay it can be fixed for an extra byte. -9 bytes thanks to @Dennis.

Here are some combined lambdas which didn't really help:

f=lambda n,k:n and n-f(f(n-1,k),k^1)or k
f=lambda n,k:[k][n:]or f(n-1,k)+[n-f(f(n-1,k)[-1],k^1)[-1]]

Both take n and a parameter k either 0 or 1, specifying male/female. The first lambda returns the nth element, and the second lambda returns the first n elements (with exponential runtime).

Sp3000
quelle
9

MATL, 23 bytes

1Oiq:"@XJth"yy0)Q)_J+hw

Try it online!

Explanation

This works iteratively. Each sequence is kept in an array. For each index n the new term of each sequence is computed and attached to the corresponding array. A for loop with N−1 terms is used, where N is the input number.

The update for sequence M needs to be done first. This is because sequence F is always greater than or equal to sequence M for the same index, so if we tried to update F first we would need a term of M not computed yet.

The two update equations are the same interchanging F and M. Thus the code for the updating is reused by applying a for loop with two iterations and swapping the sequences in the stack.

1        % Push 1: seed for F sequence
O        % Push 0: seed for M sequence
iq:      % Input N. Generate range [1 2 ... N-1]
"        % For each (i.e. iterate N-1 times)
  @      %   Push current index, n (starting at 1 and ending at N-1)
  XJ     %   Copy to clipboard J
  th     %   Duplicate and concatenate. This generates a length-2 array
  "      %   For each (i.e. iterate twice)
    yy   %   Duplicate top two elements, i.e. F and M sequences
    0)   %     In the *first* iteration: get last entry of M, i.e M(n-1)
    Q)   %     Add 1 and index into F. This is F(M(n-1))
    _J+  %     Negate and add n. This is n-F(M(n-1)), that is, M(n)
    h    %     Concatenate to update M
    w    %     Swap top two elements, to bring F to top.
         %     In the *second* iteration the procedure is repeated to update F,
         %     and then the top two elements are swapped to bring M to top again,
         %     ready for the next iteration of the outer loop
         %   End for implicitly
         % End for implicitly
         % Display implicitly from bottom to top: first line is F, second is M
Luis Mendo
quelle
6

J, 47 bytes

f=:1:`(-m@f@<:)@.*
m=:0:`(-f@m@<:)@.*
(f,:m)@i.

Uses the recursive definition. The first two lines define the verbs f and m which represent the female and male functions, respectively. The last line is a verb that takes a single argument n and outputs the first n terms of the female and male sequences.

Usage

   (f,:m)@i. 5
1 1 2 2 3
0 0 1 2 2
   (f,:m)@i. 10
1 1 2 2 3 3 4 5 5 6
0 0 1 2 2 3 4 4 5 6
miles
quelle
6

JavaScript (ES6), 75 bytes

g=n=>--n?([f,m]=g(n),m=[...m,n-f[m[n-1]]],[[...f,n-m[f[n-1]]],m]):[[1],[[0]]

I could save 2 bytes if I was allowed to return the Male sequence first:

g=n=>--n?([f,m]=g(n),[m=[...m,n-f[m[n-1]]],[...f,n-m[f[n-1]]]]):[[1],[[0]]
Neil
quelle
6

Haskell, 57 bytes

l#s=scanl(\a b->b-l!!a)s[1..]
v=w#1
w=v#0
(<$>[v,w]).take

Usage example: (<$>[v,w]).take $ 5 -> [[1,1,2,2,3],[0,0,1,2,2]]

The helper function # builds an infinite list with starting value s and a list l for looking up all further elements (at index of the previous value). v = w#1 is the female and w = v#0 the male sequence. In the main function we take the first n elements of both v and w.

nimi
quelle
4

Python 2, 107 bytes

F=lambda n:n and n-M(F(n-1))or 1
M=lambda n:n and n-F(M(n-1))
n=range(input())
print map(F,n),'\n',map(M,n)

Try it online

Larger input values cause a RuntimeError (too much recursion). If this is a problem, I can write a version where the error doesn't happen.

Mego
quelle
4

Julia, 54 bytes

f(n,x=1,y=0)=n>1?f(n-.5,[y;-x[y[k=end]+1]+k],x):[x y]'

Try it online!

Dennis
quelle
3

Pyth, 24 bytes

It is probably impossible to use reduce to reduce the byte-count.

Straightforward implementation.

L&b-b'ytbL?b-by'tb1'MQyM

Try it online!

How it works

L&b-b'ytb  defines a function y, which is actually the male sequence.

L          def male(b):
 &b            if not b: return b
   -b          else: return b-
     'ytb            female(male(b-1))


L?b-by'tb1 defines a function ', which is actually the female sequence.

L          def female(b):
 ?b            if b:
   -by'tb          return b-male(female(b-1))
         1     else: return 1


'MQ        print(female(i) for i from 0 to input)
yMQ        print(male(i) for i from 0 to input)
Leaky Nun
quelle
Do I include the anagrammatized name or your original name in the leaderboard? Also, this code is awfully long for a Pyth program.
clismique
How long have you been here... how come you know that I changed my name? Put my new name there.
Leaky Nun
1
I've been here long enough to know that you changed your name.
clismique
@DerpfacePython Seeing that other answers are almost 4 times as long... I'd say my solution is not very long.
Leaky Nun
That's very true, but it's still long compared to other Pyth programs for other questions.
clismique
3

Brachylog, 65 bytes

:{:1-:0re.}fL:2aw,@Nw,L:3aw
0,1.|:1-:2&:3&:?--.
0.|:1-:3&:2&:?--.

My attempt at combining both predicates for male and female into one actually made the code longer.

You could use the following one liner which has the same number of bytes:

:{:1-:0re.}fL:{0,1.|:1-:2&:3&:?--.}aw,@Nw,L:{0.|:1-:3&:2&:?--.}aw

Note: This works with the Prolog transpiler, not the old Java one.

Explanation

Main predicate:

:{:1-:0re.}fL                Build a list L of integers from 0 to Input - 1
             :2aw            Apply predicate 2 to each element of L, write the resulting list
                 ,@Nw        Write a line break
                     ,L:3aw  Apply predicate 3 to each element of L, write the resulting list

Predicate 2 (female):

0,1.                         If Input = 0, unify Output with 1
    |                        Else
     :1-                     Subtract 1 from Input
        :2&                  Call predicate 2 with Input - 1 as argument
           :3&               Call predicate 3 with the Output of the previous predicate 2
              :?-            Subtract Input from the Output of the previous predicate 3
                 -.          Unify the Output with the opposite of the subtraction

Predicate 3 (male):

0.                           If Input = 0, unify Output with 0
  |                          Else
   :1-                       Subtract 1 from Input
      :3&                    Call predicate 3 with Input - 1 as argument
         :2&                 Call predicate 2 with the Output of the previous predicate 3
            :?-              Subtract Input from the Output of the previous predicate 3
               -.            Unify the Output with the opposite of the subtraction
Fatalize
quelle
Wait... which one's predicate 3?
clismique
@DerpfacePython whoops, fixed. Also note that predicate one is {:1-:0re.}, used to create the range list.
Fatalize
3

Clojure, 132 131 bytes

(fn [n](loop[N 1 M[0]F[1]](if(< N n)(let[M(conj M(- N(F(peek M))))F(conj F(- N(M(peek F))))](recur(inc N)M F))(do(prn F)(prn M)))))

Simply builds the sequences iteratively up from zero to n.

Ungolfed version

(fn [n]
  (loop [N 1 M [0] F [1]]
    (if (< N n)
      (let [M (conj M (- N (F (peek M))))
            F (conj F (- N (M (peek F))))]
        (recur (inc N) M F))
      (do
        (prn F)
        (prn M)))))
mark
quelle
Nice answer, welcome to the site! Is a trailing space or newline necessary? I'm counting 131 + a trailing whitespace.
DJMcMayhem
No, there's no need for a trailing whitespace. Sneaky vim added a newline at the end for wc to count.
mark
3

Pyth, 23 bytes

jCuaG-LHtPs@LGeGr1Q],1Z

Try it online: Demonstration

Explanation:

jCuaG-LHtPs@LGeGr1Q],1Z

  u                ],1Z    start with G = [[1, 0]]
                           (this will be the list of F-M pairs)
  u             r1Q        for each H in [1, 2, ..., Q-1]:
              eG              take the last pair of G [F(H-1), M(H-1)]
           @LG                lookup the pairs of these values:
                              [[F(F(H-1)), M(F(H-1))], [F(M(H-1)), M(M(H-1))]]
          s                   join them:
                              [F(F(H-1)), M(F(H-1)), F(M(H-1)), M(M(H-1))]
        tP                    get rid of the first and last element:
                              [M(F(H-1)), F(M(H-1))]
     -LH                      subtract these values from H
                              [H - M(F(H-1)), H - F(M(H-1))]
   aG                         and append this new pair to G
jC                         at the end: zip G and print each list on a line

Alternative solution that uses a function instead of reduce (also 23 bytes):

L?>b1-LbtPsyMytb,1ZjCyM
Jakube
quelle
Nice. Very nice indeed.
Leaky Nun
3

Ruby, 104 92 97 82 bytes

f=->n,i{n>0?n-f[f[n-1,i],-i]:i>0?1:0}
->n{[1,-1].map{|k|p (0...n).map{|i|f[i,k]}}}

Edit: f and m are now one function thanks to HopefullyHelpful. I changed the second function to print f then m. The whitespace after p is significant, as otherwise the function prints (0...n) instead of the result of map.

The third function prints first an array of the first n terms of f, followed by an array of the first n terms of m

These functions are called like this:

> f=->n,i{n>0?n-f[f[n-1,i],-i]:i>0?1:0}
> s=->n{[1,-1].map{|k|p (0...n).map{|i|f[i,k]}}}
> s[10]
[1, 1, 2, 2, 3, 3, 4, 5, 5, 6]
[0, 0, 1, 2, 2, 3, 4, 4, 5, 6]
Sherlock9
quelle
you can drop the p and parens. Output is not required to be printed. Also, you can dorp parens around the range.
Not that Charles
you can replace the 2 function with 1 that has 2 arguments n and i n>0?n-f(f(n-1,i),-i):i>0?1:0
HopefullyHelpful
@HopefullyHelpful Thanks a bunch :D
Sherlock9
@NotthatCharles Is the output not required to be printed? In Ruby, if I want that line break between f and m, I need to print it. Otherwise, I just get an array like [[1, 1, 2, 2, 3, 3, 4, 5, 5, 6], [0, 0, 1, 2, 2, 3, 4, 4, 5, 6]]
Sherlock9
oh, it does say "line break". Too bad.
Not that Charles
3

APL (Dyalog Unicode), 45 25 bytes

Anonymous tacit function. Requires ⎕IO←0, which is standard on many APL systems.

1 0∘.{×⍵:⍵-(~⍺)∇⍺∇⍵-1⋄⍺}⍳

Try it online!

This works by combining F and M into a single dyadic function with a Boolean left argument which selects the function to apply. We use 1 for F and 0 for M so that we can use this selector as return value for F (0) and M (0). We then observe that both functions need to call themselves first (on the argument minus one) and then the other function on the result of that, so first we recurse with the given selector and then with the logically negated selector.

⍳ ɩndices; zero through argument minus one

1 0∘.{…} outer (Cartesian) "product" (but with the below function instead of multiplication) using [1,0] as left arguments (⍺) and the indices as right arguments (⍵):

 ×⍵ if the right argument is strictly positive (lit. the sign of the right argument):

  ⍵-1 subtract one from the right argument

  ⍺∇ call self with that as right argument and the left argument as left argument

  (~⍺)∇ call self with that as right arg and the logical negation of the left arg as left arg

  ⍵- subtract that from the right argument and return the result

 ⋄ else:

  ⍺ return the left argument

Adám
quelle
That works well, but assuming input is stored in a variable is disallowed by default.
Dennis
@Dennis It doesn't really. It is a tfn body. When I was new here, ngn told me I didn't have to count the tfn header (which would be two bytes, a single-char name + a newline, just like the source filename isn't counted, and anonymous fns are allowed. So too here, where the header is a 1-char name + space + a 1-char argument name (n) + plus a newline.
Adám
What exactly is a tfn?
Dennis
@Dennis Tfns are the traditional APL representation of functions. Consist of lines of code with almost none of the dfns's restrictions. E.g you can have proper control structures, and expressions with no result. Line "0" is a header which indicates the fn's syntax.
Adám
2

ES6, 89 85 83 bytes

2 bytes saved thanks to @Bálint

x=>{F=[n=1],M=[0];while(n<x){M.push(n-F[M[n-1]]);F.push(n-M[F[n++-1]])}return[F,M]}

Naïve implementation.

Explanation:

x => {
    F = [n = 1], //female and term number
    M = [0]; //male
    while (n < x) {
        M.push(n - F[M[n - 1]]); //naïve
        F.push(n - M[F[n++ - 1]]); //post-decrement means n++ acts as n in the calculation
    }
    return [F, M];
}
ASCII-only
quelle
I think you can make it an anonymus function, and replace the &&-s with &
Bálint
You can't, && short-circuits, which is wanted, but I removed it anyway because brace syntax is equally short anyway
ASCII-only
Then you could do`F=[n=1]
Bálint
2

Mathematica, 69 62 bytes

Thanks to Sp3000 for suggesting a functional form which saved 14 bytes.

k_~f~0=1-k
k_~f~n_:=n-f[1-k,f[k,n-1]]
Print/@Array[f,{2,#},0]&

This defines a named helper function f and then evaluates to an unnamed function which solves the actual task of printing both sequences.

Martin Ender
quelle
2

Perl 5.10, 85 80 bytes

Meh, dunno if I have more ideas to golf this down...

@a=1;@b=0;for(1..<>-1){push@a,$_-$b[$a[$_-1]];push@b,$_-$a[$b[$_-1]]}say"@a\n@b"

Try it online !

I had to add use 5.10.0 on Ideone in order for it to accept the say function, but it doesn't count towards the byte count.

It's a naive implementation of the algorithm, @a being the "female" list and @b the "male" list.

Crossed-out 85 is still 85 ?

Paul Picard
quelle
Explanation, please?
clismique
Pretty much the same as my JS answer
ASCII-only
@DerpfacePython It's a naive implementation actually. :)
Paul Picard
I haven't tested, but I don't think you should need the parentheses around each pushed term, nor the final semicolon before the close-brace.
msh210
@msh210 Indeed, forgot about this. Saves 5 bytes in total, thanks!
Paul Picard
2

Java, 169 bytes total

int f(int n,int i){return n>0?n-f(f(n-1,i),-i):i>0?1:0;}void p(int n,int i){if(n>0)p(n-1,i);System.out.print(i==0?"\n":f(n,i)+" ");}void p(int n){p(n,1);p(0,0);p(n,-1);}

F(), M() 56 bytes

int f(int n,int i){
    return n>0?n-f(f(n-1,i),-i):i>0?1:0;
}

recursive-for-loop and printing 77 Bytes

void p(int n,int i) {
    if(n>0) {
        p(n-1,i);
    }
    System.out.print(i==0?"\n":f(n,i)+" ");
}

outputting the lists in two different lines 37 Bytes

void p(int n) {
    p(n,1);
    p(0,0);
    p(n,-1);
}

input : p(10)
output :

1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 
0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9
HopefullyHelpful
quelle
1

C, 166 Bytes

#define P printf
#define L for(i=0;i<a;i++)
f(x);m(x);i;c(a){L P("%d ",f(i));P("\n");L P("%d ",m(i));}f(x){return x==0?1:x-m(f(x-1));}m(x){return x==0?0:x-f(m(x-1));}

Usage:

main()
{
    c(10);
}

Output:

1 1 2 2 3 3 4 5 5 6
0 0 1 2 2 3 4 4 5 6

Ungolfed (331 Bytes)

#include <stdio.h>

int female(int x);
int male(int x);
int i;
int count(a){
    for(i=0;i<a;i++){
        printf("%d ",female(i));
    }
    printf("\n");
    for(i=0;i<a;i++){
        printf("%d ",male(i));
    }
}
int female (int x){
    return x==0?1:x-male(female(x-1));
}
int male(x){
    return x==0?0:x-female(male(x-1));
}
int main()
{
    count(10);
}
Giacomo Garabello
quelle
0

8th, 195 bytes

Code

defer: M
: F dup not if 1 nip else dup n:1- recurse M n:- then ;
( dup not if 0 nip else dup n:1- recurse F n:- then ) is M
: FM n:1- dup ( F . space ) 0 rot loop cr ( M . space ) 0 rot loop cr ;

Usage

ok> 5 FM
1 1 2 2 3 
0 0 1 2 2 

ok> 10 FM
1 1 2 2 3 3 4 5 5 6 
0 0 1 2 2 3 4 4 5 6

Explanation

This code uses recursion and deferred word

defer: M - The word M is declared to be defined later. This is a deferred word

: F dup not if 1 nip else dup n:1- recurse M n:- then ; - Define F recursively to generate female numbers according definition. Please note that M has not yet been defined

( dup not if 0 nip else dup n:1- recurse F n:- then ) is M - Define M recursively to generate male numbers according definition

: FM n:1- dup ( F . space ) 0 rot loop cr ( M . space ) 0 rot loop cr ; - Word used to print sequences of female and male numbers

Chaos Manor
quelle