6
\$\begingroup\$

Influenced by Non-discriminating Programming, I made up an idea of a similar challenge.

Here, we say a string is a Lucas string if the number of appearances of each character is a Lucas number (2, 1, 3, 4, 7, ...), and a string is a Fibonacci string if the number of appearances of each character is a Fibonacci number (1, 2, 3, 5, 8, ...).

Here are some concrete examples:

"Programming Puzzles"
Appearance Count:   P a e g i l m n o r s u z
                  1 2 1 1 2 1 1 2 1 1 2 1 1 2

All counts are both Lucas numbers and Fibonacci numbers, so this is both a Lucas string and a Fibonacci String

"Sandbox for Proposed Challenges"
Appearance Count:   C P S a b d e f g h l n o p r s x
                  3 1 1 1 2 1 2 3 1 1 1 2 2 4 1 2 2 1

All counts are Lucas numbers, so this is a Lucas string. However the count of o is not a Fibonacci number, so this is not a Fibonacci string.

"Here are some concrete examples: "
Appearance Count:   : H a c e l m n o p r s t x
                  5 1 1 2 2 8 1 2 1 2 1 3 2 1 1

All counts are Fibonacci, so this is a Fibonacci string. However the counts of and e are not Lucas numbers, so this is not a Lucas string.

"Non-discriminating Programming"
Appearance Count:   - N P a c d g i m n o r s t
                  1 1 1 1 2 1 1 3 5 3 4 2 3 1 1

Since count of i is not Lucas number, and count of n is not Fibonacci number, so this is neither a Lucas string nor a Fibonacci String.

Challenge

Write 2 programs, one Lucas program and one Fibonacci program, both accepting a string as input, that:

  • The Lucas program checks whether the input is Fibonacci; and
  • The Fibonacci program checks whether the input is Lucas,

where the definitions of "Lucas" and "Fibonacci" are as above.

Rules

  • Your programs can choose to receive input either from STDIN or as function/program argument.
  • Your programs must output or return one of the 2(TWO) distinct values at your choice, one for the truthy value and one for the falsy value, and the choice must be consistent across the programs, i.e. you cannot have one program returning 0/1 while the other one returning true/false.
  • Your programs must output or return a truthy value if the source of each other is inputted, i.e. your Lucas program must return a truthy value if the source of your Fibonacci program is inputted, and vice versa.
  • It is allowed to have program being both Lucas and Fibonacci.
  • Characters not used are apparently not counted, in case you doubt because 0 is not in the Lucas sequence.
  • Number of distinct characters in each program are not restricted to either Lucas or Fibonacci numbers.
  • Only full programs or functions allowed. Snippets are not accepted.
  • Standard loopholes are apparently forbidden.

Scoring

The score will be calculated as follows:

  • For each program, multiply the number of distinct characters used by the maximum number of appearances of the characters in the source.
  • Add the two values calculated in the previous step up. This is your score.

Example:

Lucas code :    20 distinct characters, MAX(appearance of each character)=7
Fibonacci code: 30 distinct characters, MAX(appearance of each character)=5
Score: 20*7 + 30*5 = 140 + 150 = 290

Test cases

Input                                   | Output of ...    
                                        | Lucas Program      | Fibonacci Program
----------------------------------------+---------------------------------------
<Your Lucas program>                    | True if all appe-  | True
(Lucas string by rules)                 | arance counts are  |
                                        | exactly 1, 2 or 3; |
                                        | False otherwise    |
----------------------------------------+--------------------+------------------
<Your Fibonacci program>                | True               | True if all appe-
(Fibonacci string by rules)             |                    | arance counts are
                                        |                    | exactly 1, 2 or 3;
                                        |                    | False otherwise
----------------------------------------+--------------------+------------------
"Programming Puzzles"                   | True               | True
(Both Lucas and Fibonacci)              |                    |     
----------------------------------------+--------------------+------------------
"Sandbox for Proposed Challenges"       | False              | True
(Lucas but not Fibonacci)               |                    |     
----------------------------------------+--------------------+------------------
"Here are some concrete examples: "     | True               | False
(Fibonacci but not Lucas)               |                    |
----------------------------------------+--------------------+------------------
"Non-discriminating Programming"        | False              | False
(Neither Lucas nor Fibonacci)           |                    |
----------------------------------------+--------------------+------------------
"Hello world!"                          | True               | True
(Both Lucas and Fibonacci)              |                    |     
----------------------------------------+--------------------+------------------
"18446744073709551616"                  | False              | True
(Lucas but not Fibonacci)               |                    |     
----------------------------------------+--------------------+------------------
"Lucas and Fibonacci are IN pair"       | True               | False
(Fibonacci but not Lucas)               |                    |
----------------------------------------+--------------------+------------------
"Lucas and Fibonacci are in pair"       | False              | False
(Neither Lucas nor Fibonacci)           |                    |

Winning Criteria

The submission with the lowest score in each language wins.

\$\endgroup\$
  • \$\begingroup\$ "Lucas and Fibonacci are IN pair (Fibonacci but not Lucas)" You've swapped the True and False in your table. \$\endgroup\$ – Kevin Cruijssen Aug 24 '18 at 8:00
  • \$\begingroup\$ @Mr.Xcoder I don't see anything stating that. Two programs where each characters is used once should be fine I think. But I'll let OP verify/deny that. \$\endgroup\$ – Kevin Cruijssen Aug 24 '18 at 8:01
  • \$\begingroup\$ @Mr.Xcoder Besides, in the Truthy/Falsey table the Lucas program as input in the Lucas program states: "True if all appearance counts are exactly 1, 2 or 3; False otherwise", and similar in the Fibonacci program and input columns. \$\endgroup\$ – Kevin Cruijssen Aug 24 '18 at 8:19
  • \$\begingroup\$ I see, but I think this should be clarified in the Rules section. I thought they ought to be mutually exclusively either Fib or Lucas. \$\endgroup\$ – Mr. Xcoder Aug 24 '18 at 8:21
  • \$\begingroup\$ @Mr.Xcoder I can definitely understand your confusion. I've re-read the challenge a few times myself to make sure. Still waiting for OP to verify and edit however.. \$\endgroup\$ – Kevin Cruijssen Aug 24 '18 at 8:21
4
\$\begingroup\$

05AB1E, score: 10 + 8 = 18

This could be a comment on Kevin's post, but I've developed it independently and the technique is slightly different. Therefore I am posting it myself.

Fibonacci program that checks Lucas (10 bytes)

€¢Dā0šÅgÃQ

Try it online!

€¢Dā0šÅgÃQ -> Full program
€¢         -> Count the occurrences of each character in the string. Call this list C.
  Dā       -> Duplicate and yield the range [1 ... len string].
    0š     -> Prepend 0. [0 ... len string].
      Åg   -> Nth Lucas number (for each).
        Ã  -> Intersection with C.
         Q -> Check equality with C.

Lucas program that checks Fibonacci (8 bytes)

€¢DāÅfÃQ

Try it online!

€¢DāÅfÃQ -> Full program
€¢       -> Count the occurrences of each character in the string. Call this list C.
  Dā     -> Duplicate and yield the range [1 ... len string].
    Åf   -> Nth Fibonacci number (for each). We don't need the 0th this time!
      Ã  -> Intersection with C.
       Q -> Check equality with C.
\$\endgroup\$
  • \$\begingroup\$ Nice approach, but I'm afraid the Lucas program fail for single-char inputs because the list starts with [2,1,...]. So the Dā<Åg would be [2] with the count [1], returning in a falsey result. The Fibonacci program is perfect, though. :) \$\endgroup\$ – Kevin Cruijssen Aug 24 '18 at 8:40
  • \$\begingroup\$ @KevinCruijssen Fixed. AHHH, Lucas sequence, why do you have to be non-increasing?! \$\endgroup\$ – Mr. Xcoder Aug 24 '18 at 8:56
  • \$\begingroup\$ I know the feeling.. Screwed up my initial program as well. Too bad the is [1,INF] instead of [0,INF], otherwise I would have used that instead of Z>. \$\endgroup\$ – Kevin Cruijssen Aug 24 '18 at 8:58
3
\$\begingroup\$

05AB1E, score: 19 17 (9x1 + 8x1)

-2 score thanks to @Emigna.

Lucas (10 9 bytes):

€¢Z>ÅGKg_

Try it online (with the Fibonacci program as input).
Verify all test cases.

Fibonacci (9 8 bytes):

€¢ZÅFKg_

Try it online (with the Lucas program as input).
Verify all test cases.

Outputs 1 for truthy and 0 for falsey results.

Explanation:

€¢          # Count each of the characters in the input
            #  i.e. "Programming Puzzles" → [2,2,1,2,2,1,2,2,1,1,2,1,2,1,2,2,1,1,1]
  Z         # Get the max, without popping the list
            #  i.e. [2,2,1,2,2,1,2,2,1,1,2,1,2,1,2,2,1,1,1] → 2
   >ÅG      # Calculate the Lucas numbers up to and including this max+1
            # (Note: the +1 is because `1ÅG` returns `[]` instead of `[1]`)
            #  i.e. 2 → [2,1]
   ÅF       # Calculate the Fibonacci numbers up to and including this max
            #  i.e. 2 → [0,1,1,2]
     K      # Remove all these Fibonacci numbers from the count list
            #  i.e. [2,2,1,2,2,1,2,2,1,1,2,1,2,1,2,2,1,1,1] and [2,1] → []
            #  i.e. [2,2,1,2,2,1,2,2,1,1,2,1,2,1,2,2,1,1,1] and [0,1,1,2] → []
      g_    # Check if the list is not empty
            #  i.e. [] → 0
\$\endgroup\$
  • \$\begingroup\$ The test cases in TIO should be swapped, aren't they? Both programs are both Lucas and Fibonacci tho ;) \$\endgroup\$ – Shieru Asakoto Aug 24 '18 at 7:17
  • \$\begingroup\$ @user71546 Should be fixed now. Also added an explanation and test suite. \$\endgroup\$ – Kevin Cruijssen Aug 24 '18 at 8:10
  • \$\begingroup\$ @KevinCruijssen How about the Both programs are both Lucas and Fibonacci tho point? \$\endgroup\$ – Mr. Xcoder Aug 24 '18 at 8:12
  • \$\begingroup\$ @Mr.Xcoder I had the Fibonacci program as input in the Fibonacci TIO, and Lucas program in the Lucas TIO. Hence user71546 stated the test cases should be swapped. The "Both programs are both Lucas and Fibonacci tho ;)" part I read as: "Not that it matters that they are swapped, since both programs are both a Lucas and Fibonacci program anyway. ;)" As mentioned in my other comment, I don't see anything indicating the programs can't be both a Lucas AND Fibonacci program, similar as the test case "Programming Puzzles".. Will delete and/or fix if this is not allowed. \$\endgroup\$ – Kevin Cruijssen Aug 24 '18 at 8:16
  • 1
    \$\begingroup\$ Do you really need the ês? \$\endgroup\$ – Emigna Aug 24 '18 at 13:11
2
\$\begingroup\$

Jelly,  19  8×1+9×1=17

code-page

Lucas Program:

ĠẈfƑJÆḞ$

Try it online! Or see all-tests.

Fibonacci Program:

ĠẈfƑJŻÆĿƊ

Try it online! Or see all-tests.

How?

Both work in very similar fashions -- ÆḞ gets the nth Fibonacci number while ÆĿ gets the nth lucas number. Ż adds a zero to the front of the list of n's to use with ÆĿ to cater for the fact that the 0th Lucas number is 2, which we need to test for while 0 is the 0th Fibonacci number, which we do not need to test for. Ɗ is a quick to chain the last three links together as a monad, while $ chains the last two links together as a monad...

Lucas Program:

ĠẈfƑJÆḞ$ - Link: list of characters, s
Ġ        - group indices by value
 Ẉ       - length of each
       $ - last two links as a monad (f(s))
    J    -   range of length of s
     ÆḞ  -   nth Fibonacci number (vectorises)
   Ƒ     - is left argument is equal to the result of?:
  f      -   filter - remove items from left that are not in right
         -            i.e. groupLengths without those Fibonacci numbers

Fibonacci Program:

ĠẈfƑJŻÆĿƊ - Link: list of characters, s
Ġ         - group indices by value
 Ẉ        - length of each
        Ɗ - last three links as a monad (f(s))
    J     -   range of length of s
     Ż    -   prepend a zero
      ÆĿ  -   nth Lucas number (vectorises)
   Ƒ      - is left argument is equal to the result of?:
  f       -   filter - remove items from left that are not in right
         -            i.e. groupLengths without those Lucas numbers
\$\endgroup\$
2
\$\begingroup\$

Java 8, score 1238 1137 (35x18 + 39x13)

Lucas:

c->c.chars().map(a->c.length()-c.replace(""+(char)a,"").length()).allMatch(a->{int n=2,s=1,m=3;for(;a>m;n=s,s=m)m=n+s;return a>0&a<4|a==m;})//",-..mmnrr

Try it online.

Fibonacci:

s->s.chars().map(e->s.length()-s.replace(""+(char)e,"").length()).allMatch(a->{int l=(int)Math.sqrt(a=5*a*a+4);return(l*l==a|(l=(int)Math.sqrt(a-=8))*l==a);})//--...===aaanl((((()))))

Try it online.

Explanation (base) Lucas:

s->                     // Method with String parameter and boolean return-type
  s.chars()             //  Loop over the characters as integer-stream
   .map(c->             //  Map each of them to:
     s.length()-s.replace(""+(char)c,"").length())
                        //   The occurrence-count of this character in the input
   .allMatch(n->{       //  Check if all these occurrence-counters are true for:
      int a=2,b=1,c=3;  //    Integer `a`,`b`,`c` starting at 2,1,3 (start of Lucas sequence)
      for(;n>c;         //    Loop as long as the current occurrence-counter is larger than `c`
          ;             //      After every iteration:
           a=b,         //       Replace `a` with `b`
           b=c)         //       Replace `b` with `c`
        c=a+b;          //     Replace `c` with `a` + `b`
      return            //    Return whether the occurrence-counter is one of:
             n>0&n<4    //     1,2,3,
             |n==c;})   //     or `c`

Explanation (base) Fibonacci:

s->                     // Method with String parameter and boolean return-type
  s.chars()             //  Loop over the characters as integer-stream
   .map(c->             //  Map each of them to:
      s.length()-s.replace(""+(char)c,"").length())
                        //   The occurrence-count of this character in the input
   .allMatch(n->{       //  Check if all these occurrence-counters are true for:
      int r=(int)Math.sqrt(n=5*n*n+4); 
                        //   Integer `r`, the square of `5*n*n+4` floored
      return r*r==k     //  Return whether `5*n*n+4` is a perfect square,
             |(r=(int)Math.sqrt(n-=8))*r==n;})
                        //  and/or if `5*n*n-4` is a perfect square

A number \$n\$ is a Fibonacci number, if either or both of \$5n^2+4\$ or \$5n^2-4\$ is a perfect square (source)

Explanation modifications:

After these base programs explained above, I've made the following changes:

  • Changed the names of variables to only use letters we've already used to reduce amount of distinct characters; and also so the least amount of characters have to be added at the comment to make the occurrence-counts Lucas/Fibonacci numbers;
  • Added parenthesis around the return-statement (to get rid of the space as well);
  • Put any remaining character we need to increase for it to become a Lucas/Fibonacci number after the trailing comment //.
\$\endgroup\$
2
\$\begingroup\$

Perl 6, 32*2 + 33*2 = 171 130

-41 points thanks to nwellnhof!

Lucas Program:

{min([values .ords⊎e]».&{$_∈(1,1,*+*…0)[0…$_]})}

Fibonacci Program:

{min([values .ords⊎e]».&{$_∈(2,1,*+*…0)[0…$_]})}

Try it online!

Anonymous code blocks that take a string and return a Junction (which can be coerced to truthy/falsey values). Both use the same structure rearranged to get the correct amount of characters.

Explanation:

{min([values .ords⊎e]».&{$_∈(1,1,*+*…0)[0…$_]})}

{  # Anonymous code block
  min(  # Find the minimum of:
      [values .ords⊎e]  # Coerces the string to a list of the number of occurrences
                      ».&{ # Map each value to:
                          $_∈  # Whether the value is an element of:
                             (1,1,*+*…0)   # The sequence
                                        [0…$_]  # Truncated to prevent it evaluating infinitely
                         }
     )
}
\$\endgroup\$
0
\$\begingroup\$

Pyt, 11*1+12*1=23 bytes

Both return 0 as truthy, 1 as falsy

Fibonacci test:

ĐỤ⇹ɔ2ᴇřḞ\Ł±

Try it online!

Lucas test:

ĐỤ⇹ɔ02ᴇŘĿ\Ł±

Try it online!

Explanation:

                    Implicit input
Đ                   Duplicate the input
 Ụ                  Get list of unique characters
  ⇹                 Swap the top two elements on the stack
   ɔ                Count the number of occurrences of each character in the input
    2ᴇř             Push [1,...,100] (should be more than enough)
       Ḟ            Get the first 100 Fibonacci numbers
        \           Get all character counts that aren't Fibonacci numbers
         Ł          Get the number of such counts
          ±         Output the sign of the number of such counts
                    Implicit output

 

                    Implicit input
ĐỤ⇹ɔ                get count of occurrences of each character
    02ᴇŘ            Push [0,1,...,100] (should be more than enough)
        Ŀ           Get the first 101 Lucas numbers
         \          Get all character counts that aren't Lucas numbers
          Ł         Get the number of such counts
           ±        Output the sign of the number of such counts
                    Implicit output
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.