19
\$\begingroup\$

Your task is to write a non-empty program / function of byte count L, which, when repeated M times, checks whether a given positive integer N is equal to L × M.

You should, in theory, support an arbitrary number of repetitions (an arbitrary positive integer value of M), but it's fine if, due to language limitations, it cannot work over a certain threshold. Reading the source code of your program or accessing information about it is strictly forbidden.

For providing output, you should choose a consistent value for one of the states (either truthy or falsy) and use any other (not necessarily consistent) possible output for the other state (Discussion).

Your answers will be scored by your initial program's length L (in bytes), with less bytes being better.

Example

Let's say your (initial) program is ABCDE. Then:

  • ABCDE (1 repetition) should check if the input equals 5.
  • ABCDEABCDE (2 repetitions) should check if the input equals 10.
  • ABCDEABCDEABCDE (3 repetitions) should check if the input equals 15. Etc...

The score of this sample code would be 5, as the initial source is 5 bytes long.

\$\endgroup\$
  • \$\begingroup\$ Just to clarify: source code of length L concatenated after itself M times should return whether its input N is equal to L*M? \$\endgroup\$ – user77406 Mar 24 '18 at 9:05

21 Answers 21

12
\$\begingroup\$

Jelly, 1 byte

Output is 0 for a match, non-zero for a non-match.

Try it online!

How it works

This makes advantage of the overly liberal output format. Repeating M times simply decrements the input M times, so the result will be zero if and only if the input is LM, where L = 1.

\$\endgroup\$
  • \$\begingroup\$ Oh god I didn't see this coming... (inb4 everyone ports it to other esolangs...) \$\endgroup\$ – Mr. Xcoder Mar 23 '18 at 19:42
  • \$\begingroup\$ I did have a 0-byte answer in mind, but, eh, quine. :P \$\endgroup\$ – Erik the Outgolfer Mar 23 '18 at 19:44
  • \$\begingroup\$ My first thought. Beaten by 23 minutes :( \$\endgroup\$ – Khuldraeseth na'Barya Mar 23 '18 at 20:04
11
\$\begingroup\$

Haskell, 8 bytes

(-8+).id

Try it online!

Like many other answers it returns 0 for truthy and non-0 for falsy by repeatedly subtracting the length of the code from the input number.

\$\endgroup\$
  • \$\begingroup\$ I was so close to tinkering to getting to this... \$\endgroup\$ – totallyhuman Mar 23 '18 at 20:24
8
\$\begingroup\$

Retina, 21 20 bytes

\d+
*
^$
_
^_{20}

_

Try it online! Just repeat the part in the Code window to see how it handles the multiples.

Gives 0 for the correct multiple and positive integers for everything else.

Explanation

Let's look at the single program first:

\d+
*

This converts a decimal number to unary (using _ as the unary digit).

^$
_

If the string is empty (which can't happen at this point, because the input is guaranteed to be positive), we replace it with a single _.

^_{20}

Now we get rid of the first 20 underscores. Iff the input was 20, this results in an empty string.

_

And finally we count the number of underscores in the result, which is zero iff the input was 20.


Now what happens when we repeat the source code. Since we don't insert a linefeed when joining the programs, the first line will go right at the end of the last line, we get this when the double the program:

\d+
*
^$
_
^_{20}

_\d+
*
^$
_
^_{20}

_

Now instead of counting the underscores, we end up with the following stage:

_\d+
*

This stage does nothing, because there are no more digits in the working string at this point, so the regex can't match.

^$
_

Now this stage becomes relevant. If the input was a smaller multiple of 20, the string has been emptied by the previous copy of the source code. In that case, we turn it into a single underscore, which we know can never be turned into an empty string again by our program. This way we ensure that only the Mth multiple is accepted (and not all multiples up to the Mth).

^_{20}

We remove the first 20 underscores once more. So M repetitions of the source code will remove 20M underscores from the string, if possible.

_

And when we get to the end of the program, we still count underscores so that valid inputs give zero.

\$\endgroup\$
5
\$\begingroup\$

x86 32-bit machine code fragment, 1 byte

48                      dec    eax

Input in EAX, output in EAX: 0 for true, non-zero for false. (Also leaves the ZF flag set for true, unset for false, so you could je was_equal). As a "bonus", you don't have to worry about wrapping; 32-bit x86 can only address 4GiB of memory, so you can't make M large enough to wrap all the way around and find 1 == 2**32 + 1 or something.

To make a callable function, append a 0xC3 ret instruction after repeating 0x48 M times. (Not counted in the total count, because many languages need to repeat just the function body, or an expression, to be able to compete).

Calleable from GNU C with the prototype __attribute__((regparm(1))) int checkeqM(int eax); GNU C's regparm x86 function attribute, like -mregparm, uses EAX to pass the first integer arg.

For example, this complete program takes 2 args, and JITs M copies of the instruction + a ret into a buffer, and then calls it as a function. (Requires executable heap; compile with gcc -O3 -m32 -z execstack)

/******* Test harness: JIT into a buffer and call it ******/
// compile with gcc -O3 -no-pie -fno-pie -m32 -z execstack
// or use mprotect or VirtualProtect instead of -z execstack
// or mmap(PROT_EXEC|PROT_READ|PROT_WRITE) instead of malloc

// declare a function pointer to a regparm=1 function
// The special calling convention applies to this function-pointer only
// So main() can still get its args properly, and call libc functions.
// unlike if you compile with -mregparm=1
typedef int __attribute__((regparm(1))) (*eax_arg_funcptr_t)(unsigned arg);

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

int main(int argc, char *argv[])
{
    if (argc<3) return -1;
    unsigned N=strtoul(argv[1], NULL, 0), M = strtoul(argv[2], NULL, 0);

    char *execbuf = malloc(M+1);   // no error checking
    memset(execbuf, 0x48, M);     // times M  dec eax
    execbuf[M] = 0xC3;            // ret
    // Tell GCC we're about to run this data as code.  x86 has coherent I-cache,
    // but this also stops optimization from removing these as dead stores.
    __builtin___clear_cache (execbuf, execbuf+M+1);
     //   asm("" ::: "memory");  // compiler memory barrier works too.

    eax_arg_funcptr_t execfunc = (eax_arg_funcptr_t) execbuf;
    int res = execfunc(N);
    printf("%u == %u  =>  %d\n", N,M, res );
    return !!res;   // exit status only takes the low 8 bits of return value
}

non-PIE executables are loaded lower in virtual memory; can do a bigger contiguous malloc.

$ gcc -g -O3 -m32 -no-pie -fno-pie -fno-plt -z execstack coderepeat-i386.c
$ time ./a.out 2747483748 2747483748   # 2^31 + 600000100 is close to as big as we can allocate successfully
2747483748 == 2747483748  =>  0

real    0m1.590s     # on a 3.9GHz Skylake with DDR4-2666
user    0m0.831s
sys     0m0.755s

$ echo $?
0

 # perf stat output:
       670,816      page-faults               #    0.418 M/sec                  
 6,235,285,157      cycles                    #    3.885 GHz                    
 5,370,142,756      instructions              #    0.86  insn per cycle         

Note that GNU C doesn't support object sizes larger than ptrdiff_t (signed 32-bit), but malloc and memset do still work, so this program succeeds.

ARM Thumb machine code fragment, 2 bytes

 3802            subs    r0, #2

First arg in r0 and return value in r0 is the standard ARM calling convention. This also sets flags (the s suffix). Fun fact; the non-flag-setting version of sub is a 32-bit wide instruction.

The return instruction you need to append is bx lr.

AArch64 machine code fragment, 4 bytes

d1001000        sub     x0, x0, #0x4

Works for 64-bit integers. Input / output in x0, as per the standard calling convention. int64_t foo(uint64_t);

AArch64 doesn't have a Thumb mode (yet), so 1 instruction is the best we can do.

\$\endgroup\$
  • \$\begingroup\$ Note for anyone else who comes across this: the call to __builtin___clear_cache is only necessary because you're executing memory that you got from malloc. If you got the memory from mmap instead, the optimization doesn't happen. \$\endgroup\$ – Joseph Sible Sep 2 at 16:26
4
\$\begingroup\$

V, 16 (or 1) bytes

Boring answer:

<C-x>

one byte.

Less boring answer:

uÓ^$/0
16Ø^a$

Try it online!

Hexdump:

00000000: 75d3 5e24 2f30 0a31 3601 d85e 1261 240a  u.^$/0.16..^.a$.

I actually wrote this about 5 minutes after the challenge came out. It took me 30 minutes to patch this horrible pile of spaghetti code that I call a language.

\$\endgroup\$
3
\$\begingroup\$

Perl 5 -p, 6 bytes

$_-=6;

Try it online!

uses 0 for equal

\$\endgroup\$
  • 1
    \$\begingroup\$ Also a valid Perl 6 -p solution. \$\endgroup\$ – nwellnhof Mar 24 '18 at 14:27
3
\$\begingroup\$

Brachylog, 2 bytes

-₂

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Python 3, 27 bytes

int=lambda x,i=int:i(x)-27;

Try it online!

Code repeated twice:

int=lambda x,i=int:i(x)-27;int=lambda x,i=int:i(x)-27;

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Brain-Flak, 24 bytes

({}[(((()()()){}){}){}])

Try it online!

Returns 0 for equal and something else for not equal.

How it works:

({} #pop the top of the stack
  [(((()()()){}){}){}] #subtract 24
) #push the result.

This code run n times will subtract n * 24 from the input, giving 0 only when the input = n*24.

\$\endgroup\$
2
\$\begingroup\$

Stax, 1 byte

v

Try it online!

\$\endgroup\$
2
\$\begingroup\$

TI-Basic (83 series), 4 bytes

:Ans-4

Takes input in Ans: for example, you might type 17:prgmCODEGOLF to run this with an input of 17. Prints (and returns in Ans) the value 0 if the input is equal to L × M, and a nonzero value otherwise.

Note that the : is part of the code, so if you are entering this into the program editor, you should see

PROGRAM:CODEGOLF
::Ans-4

if you enter it once and

PROGRAM:CODEGOLF
::Ans-4:Ans-4:An
s-4

if you enter it three times.

\$\endgroup\$
1
\$\begingroup\$

Haskell, 12 bytes

(-)$0
 +12--

Try it online!

Outputs 0 for truthy and some non-zero integer for falsy.

Alternate solution, 12 bytes

id
 .(-)12--

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Befunge-98, 15 bytes

]#<@.-&+
>fv
v+

Try it online!

Try it doubled!

Uses 0 for equal and anything else for unequal.

Explanation:

This code repeated many times will look something like this:

]#<@.-&+
>fv
v+]#<@.-&+
>fv
v+]#<@.-&+
>fv
 .
 .
 .
v+]#<@.-&+
>fv
v+
  1. ] right turn. Sends the IP down.

  2. > move east. Sends the IP right.

  3. f push a 16.

  4. v move south. Sends the IP down. If this is the last time, Goto step 8.

  5. ] right turn. Sends the IP left.

  6. + add. Adds the 16 to the top of the stack.

  7. v move south. Sends the IP down. Goto step 2.

  8. < move west. Send the IP left.

  9. # skip. jump over the ] and wrap around to the end.

  10. + add. Adds the 16 to the top of the stack.

  11. & input. Push a number from the user.

  12. - subtract. get the difference of sum we were working on and the input.

  13. . print. Print the result.

  14. @ end.

\$\endgroup\$
1
\$\begingroup\$

Pure Bash, 15

Input given as a command-line parameter. Output as a shell exit code - 1 for TRUE and 0 for FALSE.

(((a+=15)-$1))

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 13 bytes

PI⁼Iθ×¹³L⊞Oυω

Try it online! Based on my answer to I double the source, you double the output! Explanation:

         ⊞Oυω   Push empty string to predefined empty list
        L       Take the length
     ×¹³        Multiply by 13
  ⁼Iθ           Compare to the input
 I              Cast to string
P               Print without moving the cursor

Manages to output 1 for truthy and 0 for falsy. Subsequent repetitions compare the input against 13, 26, 39, 52 etc. but each time the answer is overprinted so only the final answer is seen.

\$\endgroup\$
1
\$\begingroup\$

JavaScript ES6, 32 Bytes

((f=k=>n=>n>0?n==k:f(k+32))(32))

if true be 0 and false as others, 31 bytes

(f=k=>n=>n>0?n-k:_=>f(k+_))(31)

console.log([
    ((f=k=>n=>n>0?n==k:f(k+32))(32)) (31),
    ((f=k=>n=>n>0?n==k:f(k+32))(32)) (32),
    ((f=k=>n=>n>0?n==k:f(k+32))(32)) (33),
    ((f=k=>n=>n>0?n==k:f(k+32))(32)) (64),
    ((f=k=>n=>n>0?n==k:f(k+32))(32))((f=k=>n=>n>0?n==k:f(k+32))(32)) (32),
    ((f=k=>n=>n>0?n==k:f(k+32))(32))((f=k=>n=>n>0?n==k:f(k+32))(32)) (63),
    ((f=k=>n=>n>0?n==k:f(k+32))(32))((f=k=>n=>n>0?n==k:f(k+32))(32)) (64),
    ((f=k=>n=>n>0?n==k:f(k+32))(32))((f=k=>n=>n>0?n==k:f(k+32))(32))((f=k=>n=>n>0?n==k:f(k+32))(32)) (96)
]);

\$\endgroup\$
1
\$\begingroup\$

MIPS, 4 bytes

Uses $a0 as argument and return value.

0x2084fffc    addi $a0, $a0, -4

MIPS, 8 bytes (using MIPS calling convention)

0x2084fff8    addi $a0, $a0, -8
0x00041021    move $v0, $a0

x86, 5 bytes

This is my first x86 answer so feedback welcome. Uses _fastcall convention with ecx as first argument.

83 e9 05                sub    $0x5,%ecx
89 c8                   mov    %ecx,%eax

Peter Cordes has a 1 byte solution in the comments.


Brainfuck commentary: The hard part is getting brainfuck to return a single value. Otherwise something like this would be easy.

- >,[-<->] < .
\$\endgroup\$
  • 1
    \$\begingroup\$ Your x86 code fragment would be the same size for 32-bit integers, no need to limit to 8. But if you used a custom calling convention (arg in AL, retval somewhere else,), you could use the 2-byte AL special encoding sub $4, %al / mov %al, %dl. Or still return in AL/EAX and then you get Dennis's solution, with dec %eax (1 byte in 32-bit mode). And yes, custom calling conventions are fine for asm. It's asm, not just "asm that's easy to call from C"; real code written in asm does use custom calling conventions where it helps, so this is totally justifiable. \$\endgroup\$ – Peter Cordes Mar 25 '18 at 15:42
  • 1
    \$\begingroup\$ ARM's normal calling convention is first arg in r0 which is also the retval, so Thumb sub r0, #2 is 2 bytes. \$\endgroup\$ – Peter Cordes Mar 25 '18 at 15:44
  • 1
    \$\begingroup\$ Note that neither of these are functions: they require a ret at the end of the repeat block before you could call them. Normally I include the ret in byte counts for my x86 asm answers. But I think bending the rules here to just the function body makes sense, otherwise many languages can't compete at all. \$\endgroup\$ – Peter Cordes Mar 25 '18 at 15:47
  • 1
    \$\begingroup\$ (nvm, this doesn't leave the retval in %al). xchg %eax, %ecx / sub $4, %al / xchg %eax, %ecx is 4 bytes, and follows the _fastcall convention. Using the AL, imm8 and xchg-with-eax short encodings are often helpful for code golf. \$\endgroup\$ – Peter Cordes Mar 25 '18 at 15:49
  • 1
    \$\begingroup\$ I usually use objdump -drwC -Mintel to get a hexdump of the machine-code bytes. add r32, imm8 is also 3 bytes: opcode + ModR/M + imm8. All instructions that can take an imm32 have an alternative opcode that takes a sign-extended imm8. See felixcloutier.com/x86/ADD.html for example; all the "classic" ALU instructions (but not MOV) that date back to 8086 have all those encodings, including the special AL/AX/EAX ones with no modr/m, just op + imm8/16/32. This answer has examples \$\endgroup\$ – Peter Cordes Mar 25 '18 at 16:09
1
\$\begingroup\$

Octave: 23 bytes

+23;[ans,i]((N==ans)+1)

If N = L*M, the expression returns 0+i (i.e. a purely imaginary number), otherwise the expression results in a complex number with a real component.

For a slightly nicer result at the cost of an extra byte:

+24;[ans,-1]((N==ans)+1)

If N = L*M the expression returns -1, otherwise a positive number.

Demo:

N=48;
+24;[ans,-1]((N==ans)+1)                                                 #>> 24 
+24;[ans,-1]((N==ans)+1)+24;[ans,-1]((N==ans)+1)                         #>> -1
+24;[ans,-1]((N==ans)+1)+24;[ans,-1]((N==ans)+1)+24;[ans,-1]((N==ans)+1) #>> 23

PS, you can get the same result with +24;if N==ans;-1;end;ans but the bytecount is the same

\$\endgroup\$
1
\$\begingroup\$

Lua, 56 46 bytes

a=(a or io.read())-46io.write(a<=0 and a or"")

Outputs a 0 (without a trailing newline) if equal and either nothing or a series of negative numbers (with preceding zero in some cases) if not equal.

Alone: Try it online!

Repeated a bunch of times: Try it online!

Explanation

a=(a or io.read())-46

On the first iteration (when a hasn't been defined yet and is therefore nil), sets a to a number taken from input, otherwise to itself. In both cases, 46 is then subtracted from a.

io.write(a<=0 and a or"")

This just prints a if it is less than (to take care of cases where the input was larger than the total length) or equal to zero, and the empty string otherwise.

-10 bytes for remembering that Lua does conversions between numbers and strings automatically. Whoops.

\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 47 bytes

This is using the same technique as Benoit Esnard in this answer (from I double the source, you double the output!).

Prints 0 if n = 47 * M, or a non-zero value otherwise.

n=prompt(setTimeout`alert(n)`)-47/*
n-=47//*///

Demo for M = 1

n=prompt(setTimeout`alert(n)`)-47/*
n-=47//*///

Demo for M = 2

n=prompt(setTimeout`alert(n)`)-47/*
n-=47//*///n=prompt(setTimeout`alert(n)`)-47/*
n-=47//*///

\$\endgroup\$
0
\$\begingroup\$

Brain-Flak, 24 bytes

({}[(((()()()){}){}){}])

Try it online!

Just subtracts 24 from the input. Outputs 0 for true and anything else for false.

Brain-Flak, 68 bytes

{<>}<>(({}[((((()()()()){}){}()){}){}])<>{})((){[()](<{}<>>)}{}<>{})

Try it online!

This one is more sophisticated it outputs 1 for true and 0 for false.

\$\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.