title: Tips for golfing in C

text:
# Question
Title: Tips for golfing in C
What general tips do you have for golfing in C? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to C (e.g. "remove comments" is not an answer). Please post one tip per answer. Also, please include if your tip applies to C89 and/or C99 and if it only works on certain compilers.

# Answer
Use bitwise XOR to check for inequality between integers:

`if(a^b)` instead of `if(a!=b)` saves 1 character.
> 129 votes

# Answer
* Abuse `main`'s argument list to declare one or more integer variables:

```
main(a){for(;++a<28;)putchar(95+a);}

```

*(answer to The alphabet in programming languages)*

This solution also abuses the fact that `a` (a.k.a. `argc`) starts out as `1`, provided the program is called with no arguments.
* Use global variables to initialize things to zero:

```
t[52],i;main(c){for(;i<52;)(c=getchar())<11?i+=26:t[i+c-97]++;
for(i=27;--i&&t[i-1]==t[i+25];);puts(i?"false":"true");}

```

*(answer to Anagram Code Golf!)*
> 94 votes

# Answer
# Avoid catastrophic function-argument type declarations

If you're declaring a function where all five arguments are `int`s, then life is good. you can simply write

```
f(a,b,c,d,e){

```

But suppose `d` needs to be a `char`, or even an `int*`. Then you're screwed! If one parameter is preceded by a type, all of them must be:

```
f(int a,int b,int c,int*d,int e){

```

But wait! There is a way around this disastrous explosion of useless characters. It goes like this:

```
f(a,b,c,d,e) int *d; {

```

This even saves on a standard `main` declaration if you need to use the command-line arguments:

```
main(c,v)char**v;{

```

is two bytes shorter than

```
main(int c,char**v){

```

I was surprised to discover this, as I have not so far encountered it on PPCG.
> 78 votes

# Answer
The comma operator can be used to execute multiple expressions in a single block while avoiding braces:

```
main(){

int i = 0;
int j = 1;
if(1)
    i=j,j+=1,printf("%d %d\n",i,j); // multiple statements are all executed
else
    printf("failed\n");

}

```

Outputs: `1 2`
> 76 votes

# Answer
Instead of \>= and \<= you can simply use integer division (/) when the compared values are above zero, which saves one character. For example:

```
putchar(c/32&&126/c?c:46); //Prints the character, but if it is unprintable print "."

```

Which is of course still shrinkable, using for example just \> and ^ (a smart way to avoid writing && or || in some cases).

```
putchar(c>31^c>126?c:46);

```

The integer division trick is for example useful to decide whether a number is less than 100, as this saves a character:

```
a<100 vs 99/a

```

This is also good in cases when higher precedence is needed.
> 47 votes

# Answer
Certain compilers, such as GCC, allow you to omit basic `#include`s, param, and return types for `main`.

The following is a valid C89 and C99 program that compiles (with warnings) with GCC:

```
main(i) { printf("%d", i); }

```

Notice that the `#include` for stdio.h is missing, the return type for `main` is missing, and the type declaration for `i` is missing.
> 46 votes

# Answer
# Use lambdas (unportable)

Instead of

```
f(int*a,int*b){return*a>*b?1:-1;}
...
qsort(a,b,4,f);

```

or (gcc only)

```
qsort(a,b,4,({int L(int*a,int*b){a=*a>*b?1:-1;}L;}));

```

or (clang with blocks support)

```
qsort_b(a,b,4,^(const void*a,const void*b){return*(int*)a>*(int*)b?1:-1;});

```

try something like

```
qsort(a,b,4,"\x8b\7+\6\xc3");

```

...where the string literal contains the machine language instructions of your "lambda" function (conforming to all platform ABI requirements).

This works in environments in which string constants are marked executable. By default this is true in Linux and OSX but not Windows.

One silly way to learn to write your own "lambda" functions is to write the function in C, compile it, inspect it with something like `objdump -D` and copy the corresponding hex code into a string. For example,

```
int f(int*a, int*b){return *a-*b;}

```

...when compiled with `gcc -Os -c` for a Linux x86\_64 target generates something like

```
0:   8b 07                   mov    (%rdi),%eax
2:   2b 06                   sub    (%rsi),%eax
4:   c3                      retq

```

MD XF wrote a bash script that may assist in the writing of simple "lambda" functions.

Edit: This technique was previously published by Shinichiro Hamaji in this document.

# GNU CC `goto`:

You can call these "lambda functions" directly but if the code you're calling doesn't take parameters and isn't going to return, you can use `goto` to save a few bytes. So instead of

```
((int(*)())L"ﻫ")();

```

or (if your environment doesn't have Arabic glyphs)

```
((int(*)())L"\xfeeb")();

```

Try

```
goto*&L"ﻫ";

```

or

```
goto*&L"\xfeeb";

```

In this example, `eb fe` is x86 machine language for something like `for(;;);` and is a simple example of something that doesn't take parameters and isn't going to return :-)

It turns out you can `goto` code that returns to a calling parent.

```
#include<stdio.h>
int f(int a){
 if(!a)return 1;
 goto*&L"\xc3c031"; // return 0;
 return 2; // never gets here
}
int main(){
 printf("f(0)=%d f(1)=%d\n",f(0),f(1));
}

```

The above example (might compile and run on Linux with `gcc -O`) is sensitive to the stack layout.

EDIT: Depending on your toolchain, you may have to use the `-zexecstack` (for gcc) or `-Wl,-z,execstack` (for clang) compile flag.

*If it isn't immediately apparent, this answer was mainly written for the lols. I take no responsibility for better or worse golfing or adverse psychological outcomes from reading this.*
> 45 votes

# Answer
The ternary conditional operator `?:` can often be used as a stand in for simple `if`--`else` statements at considerable savings.

Unlike the c++ equivalent the operator does not formally yield an lvalue, but some compilers (notably gcc) will let you get away with it, which is a nice bonus.
> 40 votes

# Answer
http://graphics.stanford.edu/~seander/bithacks.html

Bits are nice.

```
~-x = x - 1
-~x = x + 1

```

But with different precedences, and don't change x like ++ and --. Also you can use this in really specific cases: ~9 is shorter than -10.

```
if(!(x&y)) x | y == x ^ y == x + y
if(!(~x&y)) x ^ y == x - y

```

That's more esoteric, but I've had occassion to use it. If you don't care about short-circuiting

```
x*y == x && y
if(x!=-y) x+y == x || y

```

Also:

```
if(x>0 && y>0) x/y == x>=y

```
> 35 votes

# Answer
Define parameters instead of variables.

`f(x){int y=x+1;...}`

`f(x,y){y=x+1;...}`

You don't need to actually pass the second parameter.

Also, you can use operator precedence to save parenthesis.
For example, `(x+y)*2` can become `x+y<<1`.
> 31 votes

# Answer
Use *cursors* instead of pointers. Snag the `brk()` at the beginning and use it as a *base-pointer*.

```
char*m=brk();

```

Then make a #define for memory access.

```
#define M [m]

```

`M` becomes a postfix `*` applied to integers. (The old a\[x\] == x\[a\] trick.)

But, there's more! Then you can have pointer args and returns in functions that are shorter than macros (especially if you abbreviate 'return'):

```
f(x){return x M;} //implicit ints, but they work like pointers
#define f(x) (x M)

```

To make a cursor from a pointer, you subtract the base-pointer, yielding a ptrdiff\_t, which truncates into an int, losses is yer biz.

```
int p = sbrk(sizeof(whatever)) - m;
strcpy(m+p, "hello world");

```

This technique is used in my answer to Write an interpreter for the untyped lambda calculus.
> 28 votes

# Answer
The ternary operator `?:` is unusual in that it has two separate pieces. Because of this, it provides a bit of a loophole to standard operator precedence rules. This can be useful for avoiding parentheses.

Take the following example:

```
if (t()) a = b, b = 0;  /* 15 chars */

```

The usual golfing approach is to replace the `if` with `&&`, but because of the low precedence of the comma operator, you need an extra pair of parentheses:

```
t() && (a = b, b = 0);  /* still 15 chars */

```

The middle section of the ternary operator doesn't need parentheses, though:

```
t() ? a = b, b = 0 : 0;  /* 14 chars */

```

Similar comments apply to array subscripts.
> 25 votes

# Answer
Any part of your code that repeats several times is a candidate for replacement with the pre-processor.

```
#define R return

```

is a very common use case if you code involves more than a couple of functions. Other longish keywords like `while`, `double`, `switch`, and `case` are also candidates; as well as anything that is idomatic in your code.

I generally reserve uppercase character for this purpose.
> 24 votes

# Answer
Since usually `EOF == -1`, use the bitwise NOT operator to check for EOF: `while(~(c=getchar()))` or `while(c=getchar()+1)` and modify value of c at every place
> 23 votes

# Answer
If you ever need to output a single newline character (`\n`), don't use `putchar(10)`, use `puts("")`.
> 23 votes

# Answer
# Reverse Loops

If you can, try to replace

```
for(int i=0;i<n;i++){...}

```

with

```
for(int i=n;i--;){...}

```
> 20 votes

# Answer
# Use `for` rather than `while`

Any `while` can be changed into a `for` of the same length:

```
while(*p++)
for(;*p++;)

```

On its own, that's not golf. But we now have an opportunity to move an immediately-preceding statement into the parens, saving its terminating semicolon. We might also be able to hoist an expression statement from the end of the loop; if the loop contained two statements, we could also save the braces:

```
a=5;while(*p++){if(p[a])--a;++b;}

for(a=5;*p++;++b)if(p[a])--a;

```

Even `do...while` loops should be replaced with `for` loops. `for(;foo,bar,baz;);` is shorter than `do foo,bar;while(baz);`.
> 19 votes

# Answer
If your program is reading or writing on one in each step basis always try to use read and write function instead of getchar() and putchar().

**Example** (Reverse stdin and place on stdout)

```
main(_){write(read(0,&_,1)&&main());}

```

Exercise:Use this technique to get a good score here.
> 18 votes

# Answer
Make use of return values to zero stuff. If you call some function, and that function returns zero under normal conditions, then you can place it in a location where zero is expected. Likewise if you know the function will return non-zero, with the addition of a bang. After all, you don't do proper error handling in a code golf in any case, right?

Examples:

```
close(fd);foo=0;   →  foo=close(fd);    /* saves two bytes */
putchar(c);bar=0;  →  bar=!putchar(c);  /* saves one byte  */

```
> 16 votes

# Answer
## Abuse dark corners of array indexing

`i[array]` desugars into `*(i+array)`, and since `+` is commutative for `pointer+integer` too, it is equivalent to `*(array+i)` and therefore `array[i]`.

It's not very common to see an array indexing expression `(whatever)[x]` where `whatever` requires wrapping in parens and `x` doesn't, but when you see one, you can swap the two positions and write `x[whatever]` to save two bytes.

A real golfing example.
> 13 votes

# Answer
1. Use `*a` instead of `a[0]` for accessing the first element of an array.
2. Relational operators (`!=`, `>`, etc.) give `0` or `1`. Use this with arithmetic operators to give different offsets depending on whether the condition is true or false: `a[1+2*(i<3)]` would access `a[1]` if `i >= 3` and `a[3]` otherwise.
> 12 votes

# Answer
You may look into the IOCCC archives (international obfuscated C code contest).

One notable trick is to #define macros whose expansion has unbalanced braces/parentheses, like

```
#define P printf(

```
> 11 votes

# Answer
# `dprintf` for conditional printing

As you may know, printing something by a condition can be done with `?:`, `&&` or `||`:

```
cond&&printf("%d\n",n);
cond||printf("%d\n",n);
cond?:printf("%d\n",n);

```

Another interesting idea is to use `dprintf`, which is the same as `printf` except that it takes an extra argument, specifying the output file descriptor. It will only output to STDOUT if said argument is equal to 1. This can be abused to potentially save a few bytes over the previously mentioned methods:

```
x-1||printf("%d\n",n);
dprintf(x,"%d\n",n);

```
> 11 votes

# Answer
### Assign instead of return.

This is not really standard C, but works with every compiler and CPU that I know of:

```
int sqr(int a){return a*a;}

```

has the same effect as:

```
int sqr(int a){a*=a;}

```

Because the first argument is stored into the same CPU register as the return value.

*Note: As noted in one comment, this is undefined behaviour and not guaranteed to work for every operation. And any compiler optimization will just skip over it.*

### X-Macros

Another useful feature: X-Macros can help you when you have a list of variables and you need to do some operation which involve all of them:

https://en.wikipedia.org/wiki/X\_Macro
> 10 votes

# Answer
Using `asprintf()` saves you the explicit allocating and also measuring the length of a string aka `char*`! This isn't maybe too useful for code golfing, but eases the everyday work with a char arrays. There are some more good advises in 21st Century C.

Usage example:

```
#define _GNU_SOURCE
#include <stdio.h>

int main(int argc, char** argv) {
  char* foo;
  asprintf(&foo, "%s", argv[1]);
  printf("%s",foo);
}

```
> 9 votes

# Answer
`for(int i=0;i<n;i++){a(i);b(i);}` can be made shorter a few ways:

`for(int i=0;i<n;){a(i);b(i++);}` -1 for moving the `++` to the last `i` in the loop

`for(int i=0;i<n;b(i++))a(i);` -3 more for moving all but one statement into the top and out of the main loop, removing the braces
> 9 votes

# Answer
## Go functional!

If you can reduce your problem to simple functions with the same signature and defined as single expressions, then you can do better than `#define r return` and factor-out almost all of the boilerplate for defining a function.

```
#define D(f,...)f(x){return __VA_ARGS__;}
D(f,x+2)
D(g,4*x-4)
D(main,g(4))

```

Program result is its status value returned to the OS or controlling shell or IDE.

Using `__VA_ARGS__` allows you to use the comma operator to introduce sequence points in these *function-expressions*. If this is not needed, the macro can be shorter.

```
#define D(f,b)f(x){return b;}

```
> 9 votes

# Answer
1. use `scanf("%*d ");` to read the dummy input. (in case that input is meaningless in further program) it is shorter than `scanf("%d",&t);` where you also need to declare the variable t.
2. storing characters in int array is much better than character array. example.

`s[],t;main(c){for(scanf("%*d ");~(c=getchar());s[t++]=c)putchar(s[t]);}`
> 8 votes

# Answer
Print a character then carriage return, instead of:

```
printf("%c\n",c);

```

or

```
putchar(c);putchar('\n'); // or its ascii value, whatever!

```

simply, declare c as an int and:

```
puts(&c);

```
> 8 votes

# Answer
## Missing `include`s and return values

As noted in the very first answer, some compilers (notably, GCC anc clang) let you get away with omitting `#include`s for standard library functions.

While that *usually* goes well, it might cause problems in some cases, since the implicit declarations of standard library functions inside the source code will cause the compiler to treat return values as `int`s. For example, the code

```
char*p=getenv("PATH");

```

wont work as expected on a 64-bit platform since `getenv` returns a 64-bit memory address which doesn't fit into an *int*.

In this case, there are at least three ways to use *getenv* without errors.

* Include the header file as follows.

```
#include<stdlib.h>
char*p=getenv("PATH");

```

This is *the right way*™, but not very golfy; it costs **19** bytes.
* Declare *getenv* with the pointer as follows.

```
char*getenv(),*p=getenv("PATH");

```

This costs **10** bytes.
* Finally, unless your code wouldn't work on 32-bit platforms, compile your code on one of those or with the `-m32` flag (gcc). This costs **0** bytes.
> 8 votes

# Answer
# Swap variables

If you ever need to swap variables, don't use the pattern with an extra variable or that addition-subtraction-method, just do some chained XORing:

```
a^=b^=a^=b;

```
> 8 votes

# Answer
# Try `cpow()` instead of `cos()`

Instead of

```
double y=cos(M_PI*2*x);

```

try something like

```
double y=cpow(-1,x*2);

```

This uses Euler's formula, a little complex analysis and the observation that assigning a complex to a double yields the real part (careful with variadic function calls and other subtleties).

\\$\cos 2\pi x+j\sin 2\pi x=e^{j2\pi x}=e^{j\pi 2x}=\left(-1\right)^{2x}\\$

This type of trick can be used to reduce

```
double y=cpow(-1,x/2);

```

into

```
double y=cpow(1i,x);

```

because \\$\left(-1\right)^\frac{x}{2}=j^\frac{2x}{2}=j^x\\$

Edit: Equations now inline \\$\LaTeX\\$ instead of images.
> 8 votes

# Answer
# Exploit ASLR

On systems with ASLR (Address Space Layout Randomization), the address of a stack variable can be used as a one time pseudorandom number. Instead of something like...

```
srand(time(0));

```

...try something like

```
srand(&x)

```

...where the address of `x` (hopefully on the stack) is unique each time the program is run.
> 8 votes

# Answer
## Abuse two's complement

A lot of expressions can be changed by (ab)using two's complement. Take this for example:

```
getchar()+1

```

If you need higher precedence, you can use this:

```
-~getchar()

```

Or, if you're using it as the condition for a loop, this can be used:

```
~getchar()

```

Additionally, instead of subtracting one after another subtraction:

```
a+b-1

```

you can add the bitwise-NOT of the second operand:

```
a+~b

```

This applies similarly to multiplication by 2:

```
2*(a-b)-1

```

can be shortened to:

```
a-b+a+~b

```
> 7 votes

# Answer
## `import` if you have to

As noted in the very first answer, some compilers (notably, GCC and clang) let you get away with omitting `#include`s for standard library functions.

Even if you can't just remove the `#include`, there might be other ways to avoid it, but that's not always practical or particularly golfy.

In the remaining cases, you can use `#import<header file>` instead of `#include<header file>` to save a byte. This is a GNU extension and it is considered deprecated, but it works at least in gcc 4.8, gcc 5.1, and clang 3.7.
> 6 votes

# Answer
instead of the printf loop

```
for(i=1;i<12;i++){if(!i%3)printf("\n");printf("%d",i);}

```

just use

```
for(i=1;i<12;i++) printf("%c%d",!(i%3)*10,i);

```

it helps me so much .

---

@SamHocevar 's answer (shorter by 2bytes)

```
for(i=1;i<12;i++) printf("\n%d"+!!(i%3),i);

```

---

Credits to @AbhayAravinda for ripping off three more bytes

```
for(i=1;i++<12;) printf("\n%d"+!!(i%3),i);

```

The incrementer here works as a part of the inspector.
> 5 votes

# Answer
Here are a few tips I've used to my advantage. I've shamelessly stolen them from others, so credit to anyone but me:

**Combine assignment with function calls**

Instead of this:

```
r = /* Some random expression */
printf("%d", r);

```

Do this:

```
printf("%d", r = /* Some random expression */);

```

**Initialize multiple variables together (when possible)**

Instead of this:

```
for(i=0,j=0;...;...){ /* ... */ }

```

Do this:

```
for(i=j=0;...;...){ /* ... */ }

```

**Collapse zero/nonzero values**

This is a neat trick I picked up from someone here (don't remember who, sorry). When you have an integer value and you need to collapse it to either 1 or 0, you can use `!!` to do so easily. This is sometimes advantageous for other alternatives like `?:`.

Take this situation:

```
n=2*n+isupper(s[j])?1:0; /* 24 */

```

You could instead do this:

```
n=n*2+!!isupper(s[j]); /* 22 */

```

Another example:

```
r=R+(memcmp(b+6,"---",3)?R:0); /* 30 */

```

Could be rewritten as:

```
r=R+R*!!memcmp(b+6,"---",3)); /* 29 */

```
> 5 votes

# Answer
# Overload functions (unportable)

Instead of declaring multiple functions...

```
d(x){return x*2;}
float r(float x){return 1/sqrt(x);}
...
printf( "%d %f\n", d(2), r(2) );

```

...declare one "function" that does different things depending on return and parameter types.

```
(*f)()=L"\xf33f048d\xc3c0520f"; // global
...
printf( "%d %f\n", f(2), ((float(*)(float))f)(2) );

```

Try it online! This works because some ABI's (Linux x86\_64, in this example) use separate registers for floating point and integer arguments and return values.

The disassembly of the `(*f)()` "function"...

```
0:       8d 04 3f                lea    (%rdi,%rdi,1),%eax
3:       f3 0f 52 c0             rsqrtss %xmm0,%xmm0
7:       c3                      retq

```

On a x86\_64 Linux machine, this function takes the first integer parameter, doubles it and places the result in `%eax` (char/short/int/long return value). It takes the first floating point parameter, computes a low precision reciprocal square root and places it in `%xmm0` (float/double return value).
> 5 votes

# Answer
# Inline arrays

If you need a **non-int** constant array and just use it once, you can do

```
float f(a){return (float[]){.3,.2,.7}[a];}

```

instead of

```
float z[]={.3,.2,.7};float f(a){return z[a];}

```

to save 3 bytes.

(In this case it can save one more byte since the blank after `return` can be omitted.)
> 5 votes

# Answer
# Inverse flag update

Sometimes a challenge asks to determine a data set's specific boolean property. To avoid the unacceptably long `return` keyword, I often use a flag variable which gets updated in a loop and assign-returned at the end (I will refer to this tip for more detail on assign-returning).

When working with such boolean flags and boolean values, to update them I often use either `f&=a|b` or `f*=a|b` to align them with the result of `a|b`. This is equivalent to saying `f = f && (a|b)`.

However, sometimes a flag needs to be inversely updated, meaning `f = f && !(a|b)`. Naively, one would use `f&=!(a|b)` (9 bytes), or -- using fundamental logical equivalences -- one would golf it to `f&=!a&!b` (8 bytes).
For the case of an inverse flag update, though, one might be better off using the binary shift right operator `>>`, as the previous assignment is (when working with boolean values) equivalent to `f>>=!(!a&!b)`, which simply golfs to `f>>=a|b` (7 bytes).

If the flag update in question does not involve parentheses due to negation (as in the previous example), inverse flag updating may still be shorter, as for example `f&=!a|!b` (8 bytes) is equivalent to `f&=!(a&b)` (9 bytes), which is equivalent to `f>>=a&b` (7 bytes).

Inverse flag updating may in certain cases also be used even though the values in question are not boolean (either `0` or `1`).
If only one operand is boolean, bitwise and (`&`) can still be used, as the second operand's bits will all be cleared. When using bitwise or (`|`) or both operands are non-boolean, one should consider using logical and (`&&`) and logical or (`||`) to get a boolean result, even though they are one byte longer.

As a side node, these rules also apply when the expression is side-effect-dependent, meaning `!f()&&!g()` is equivalent to `!(f()||g())` regarding the execution of `g()`, such that even in those cases inverse flag updating can be used.

For testing purposes, I wrote a simple truth table tester (TIO-link).

One recent real-world example of this technique in action would be for example my answer to Detect Rectangular Text.
> 5 votes

# Answer
# Boolean constant string selection when the selector's true value is guaranteed to be one larger than the second option's length

At its heart, this tip attempts to golf a ternary if of the form `cnd?str_true:string_false` when two conditions are met, namely that both `str_true` and `string_false` are constant strings and `cnd` is either `0` or `strlen(string_false)+1`.

If the above conditions are met, the expression `cnd?"true":"false"` can be golfed\* by one byte to `"false\0true"+cnd` (here `cnd == 0 || cnd == 6` always holds); another byte can be shaved off by not escaping the null byte (a compiler dependent feature).

### The tip in action

For this example, suppose the string selection's criterion is `k%3`'s truthiness, where `k-1` is never divisible by three. In this case the ternary if

```
k%3?"°@°":"_" // 13 bytes

```

can be golfed to:

```
"_\0°@°"+k%3 // 12 bytes

```

Which can be golfed down to eleven bytes if one does not escape the null byte.

### Application in obfuscation

As the above requirements are rather strict, this tip is most likely not widely applicable. Nonetheless, the shown technique can also be used to potentially obfuscate a program at no further byte cost.

Given `e` as a truly boolean expression -- `(e) == 0 || (e) == 1` holds -- with the proper operator precedence regarding the upcoming factor, the following snippets are interchangeable\* at the same byte count -- when not escaping the null byte.

```
e?"lifeless":"lychee"
"lychee\0lifeless"+e*7

```

Bare in mind that this obfuscation is only non-detrimental to the byte count if the second option's string is not longer than eight characters -- since else the factor spans more than one byte.

\*: If interpreted as constant strings.
> 5 votes

# Answer
## Get the length of a string with `puts()` instead of `strlen()`

According to the standard C specification, `puts()` returns a non-negative integer on success. In practice, most C libraries seem to treat `puts(s)` as equivalent to `printf("%s\n", s)`, which returns an integer equal to the number of bytes written.

As a result, the return value of `puts(s)` is equal to `1 + strlen(s)`. If the additional console output can be ignored, this saves a few bytes.
> 5 votes

# Answer
# Calculating \\$\lceil\log\_{10}(n)\rceil\\$

Especially in challenges where properties of decimal representations are of interest, one needs to find a number's decimal representation's length, or for \\$n\in\mathbb{N}^+\\$ equivalently, \\$\lceil\log\_{10}(n)\rceil\\$.
In this post, several approaches are presented and discussed.

For a C source file containing approaches (a.1) to (b.3) together with a testing setup, see TIO.

I wrote this tip based on this answer of mine, searching for a smaller approach than **(a.1)**.
If you know of any other approach possibly shorter in even a specific scenario, feel free to either add your own tip add to the list below.

## (a.1) An expression in `n`, 20 bytes

```
snprintf(0,0,"%d",n)

```

Versatility is a great property of the above approach, when used to determine a number's decimal representation's length, the most direct approach might be the most byte-effective.

`0` is given its correct decimal representation length of 1.

GCC only throws a warning for ignoring `#include <stdio.h>`, otherwise the inclusion would be very byte-heavy at potentially 19+20=39 bytes. If instead of `sprintf(0`, one uses `sprintf(NULL`, the byte count is increased to 23 bytes. If using both, the byte count could jump to 42 bytes.

## (a.2) A function in `n`, 29 bytes

```
a(n){n=snprintf(0,0,"%d",n);}

```

By being a function, this approach's versatility is high; **(a.1)**'s compiler-specifics also apply, when properly `return`ing, the byte count increases to 5+29=34 bytes.

`0` is given its correct decimal representation length of 1.

## (b.1) A function in `n`, requiring another variable, 32 bytes

```
b(n,k){for(k=0;n;k++)n/=10;n=k;}

```

Of all approaches presented, this one has the worst byte count. However, considering potential compiler restrictions discussed in **(a.1)**, it could prove more byte-efficient, since the approach is nearer to the C core.

`0` is given its incorrect decimal representation length of 0. One can make the case for defining \\$\lceil-\infty\rceil:=0\\$ which would make this approach closer to a logarithm implementation, when further defining \\$\log(0):=-\infty\\$.

Modification to calculate \\$\lceil\log\_b(n)\rceil\\$ for a base \\$b\in\mathbb{N}^+\\$ is possible, changing the byte count by the bytes required to represent \\$b\\$ in C-source.

## (b.2) A statement requiring existence of two variables, setting `n=0`, 20 bytes

```
for(k=0;n;k++)n/=10;

```

If another variable is already declared and `n` can be either discarded or needs to be cleared regardless and the use case is a whole block instead of a one-line expression, the above could be used. Since it is equivalent in byte count to **(a.1)**, the behavioural differences have to be analyzed.

Minimally wrapped inside a function, it becomes **(b.1)**, both being similar in features.

## (b.3) A statement working additively on `k`, setting `n=0`, 17 (pot. 16) bytes

```
for(;n;k++)n/=10;

```

Another variation on **(b.1)**, removing initialization of `k`. Furthermore, `for(;` leaves space for an expression, potentially allowing to save a semicolon's byte, effectively rendering this approach 16 bytes long.

## (c.1) A statement in `n`, producing `stdout`-output, 14 bytes

```
printf("%d",n)

```

Courtesy of H.PWiz.

This approach's utter conciseness and simplicity may be alluring, its major drawback, however, is its `stdout`-output; tolerability being heavily challenge-dependent.

## (c.2) A statement in `n`, producing `stderr`-output, 17 bytes

```
dprintf(2,"%d",n)

```

Courtesy of Jo King.

The above is equivalent to the five bytes longer `fprintf(stderr,"%d",n)` and a variant of **(c.1)**, side-effecting not `stdout` but rather the much more clutterable `stderr`.
Ref. `man dprintf.3`
> 5 votes

# Answer
Use bitwise operators to convert characters to uppercase/lowercase. Bitwise AND with 95 (or `'_'`) to convert to uppercase, bitwise OR with 32 (or `' '`) to convert to lowercase, and to invert case, bitwise XOR with 32 (or `' '`).

This only works for letters, and it also seems to work for just a few other characters: `{` and `}` are lowercase for `[` and `]`, `~` and ``` are lowercase for `^` and `@`, `)` is lowercase for a tab, and `*` is lowercase for a newline.

Example.
> 5 votes

# Answer
Knowing basic logical equalities might be able to save a couple bytes. For instance, instead of `if (!(a&&b)){}` try instead using DeMorgan's law `if (!a||!b){}`. The same applies to bitwise functions: instead of `~(a|b)` do `~a&~b`.
> 4 votes

# Answer
### Use `s[i]` instead of `i<strlen(s)` in string-handling loops

For example:

```
for(i=0;i<strlen(s);i++)s[i]=s[i+1];

```

can be shortened to:

```
for(i=0;s[i];i++)s[i]=s[i+1];

```
> 4 votes

# Answer
# Set an array of `int` to the same value (C99, Linux, BSD, OSX)

Instead of

```
int a[n]=...,x=...;
for(int i=n;i--;)a[i]=x

```

Try something like

```
int a[n]=...,x=...;
wmemset(a,x,n);

```

On MSVC on Windows, `wmemset()` works on arrays of `short` instead of `int`.
> 4 votes

# Answer
**When your algorithm produces output in reverse order, take a pointer to the *end* of a buffer** and write it in decreasing order, returning a pointer to the first element. It's up to the caller to supply a buffer large enough for any this input, or for any possible input.

Base conversion / int-to-string is a classic example where this interface is used in real life, such as glibc's internal `_itoa`, used by the printf family of functions as well as some other internal callers. The max buffer size is 65 bytes for a 64-bit integer -\> base 2 string.

```
// takes a pointer to one-past-the-end, which is also a valid option.
char *itoa_end(unsigned long val, char *p_end) {
  // does *not* zero terminate the buffer.  Use *--p_end = 0;
  const unsigned base = 10;
  char *p = p_end;
  do {
    *--p = (val % base) + '0';
    val /= base;
  } while(val);                  // runs at least once to print '0' for val=0.

  // write(1, p,  p_end-p);
  return p;  // let the caller know where the leading digit is
}

```

---

For golfing, **it can be more compact to take the pointer by reference and modify it, instead of returning it**. (`return` is a long keyword, and code depending on `gcc -O0` evaluating expressions in the return-value register isn't even C.)

For example, I used this in ASCII art uncompression from a base-n number (i.e. int-\>string with a digit lookup table), where I already needed a `char*` arg, so it was *very* cheap to declare another as a `char **`.

**Use `*p` everywhere you have `p` in the simple version**. `*--*p` decrements the caller's pointer, then dereferences that to reference the actual character.

```
/* int n = the number
 * int B = size of I = base
 * char I[] = input table
 * char **O = input/output arg passed by ref:
 *    on entry: pointer to the last byte of output buffer.
 *    on exit:  pointer to the first byte of the 0-terminated string in output buffer
 */
void semi_golfed_g(n,I,B,O)char*I,**O;
{
    for(**O=0 ; n ; n/=B)
        *--*O = I[n%B];
}

```
> 4 votes

# Answer
# Abuse `wchar_t` to print one character from a string

In a little-endian architecture, you can replace

```
putchar("string"[i])

```

with

```
printf(L"string"+i)

```

to save a byte.
> 4 votes

# Answer
Use bitwise and (&) when comparing boolean expressions to save one byte.

Example:

```
if(i^2&k/3) DoSomething;

```

Really, really useful when combined with the other tips
> 3 votes

# Answer
Whenever a certain function is called several times, it's common to `#define` it to something shorter. However, certain compilers (MinGW and clang as far as I know) allows for something even more compact by using function pointers:

```
(*P)()=printf;
P("Test: %d\n", 10);

```

Other compilers might require an `#include` of the proper header file for it to work.
> 3 votes

# Answer
# Favor recursion over loops, especially if going forwards then backwards

## Loops, 67 bytes

```
l;f(char*s){for(l=0;s[l];)putchar(s[l++]);for(;l;)putchar(s[--l]);}

```

Try it online!

## Recursion, 47 bytes

```
f(char*s){*s?putchar(*s),f(s+1),putchar(*s):0;}

```

Try it online!

You can remove two for-loops and a counter variable. Even if you use just one for-loop in order to loop in one direction, you could save ~10 bytes with this transformation.
> 3 votes

# Answer
Sometimes you can use *floating point* where you don't expect to.

Ignoring possible *floating point* imprecision issues you still can use them with many operators you wouldn't normally expect :

* `++` `--` increment / decrement
* `!` `||` `&&` Boolean comparative
* `?` and even ternary!
> 3 votes

# Answer
For scanning a string into an array, you can use

```
gets(str);

```

instead of

```
scanf("%s",str);

```
> 2 votes

# Answer
When you have to walk a string you can walk the pointer instead of incrementing the index.

Code :

```
#include <stdio.h>

// print each char
void f(char* s) {
    for (int i=0;s[i];i++) putchar(s[i]);
}

// same output than f;
void g(char* s)
{
    for (;*s;) putchar(*s++);
}

int main(void) {
    f("hello\n");
    g("hello\n");
    return 0;
}

```

example: Remove duplicated & switched case
> 2 votes

# Answer
### Use `#define` instead of functions when possible

For example:

```
f(int i,char*s){/*do something with i and s*/;}

```

Using `#define` can eliminate the argument list type, curly-braces and closing semicolon:

```
#define f(i,s)/*do something with i and s*/

```
> 2 votes

# Answer
# Use bitwise operators for boolean conditions

For example:

```
if(a||b) /* do something */

```

This saves one byte:

```
if(a|b) /* do something */

```

Respectively, `a!=b` becomes `a^b` and `a&&b` becomes `a&b`

An example of using this trick.

Note that sometimes you have to use `||`. For example:

```
if(!a)b++

```

can be written as

```
a||b++

```

but

```
a|b++

```

doesn't work.
> 2 votes

# Answer
Sometimes, albeit rarely, if your code contains many `for` loops, `#define F for(` may save a byte or two (especially if some of the loops have an empty init section).

If it is applicable to your situation, `#define F;for(` may save even more bytes.

**Examples:**

https://codegolf.stackexchange.com/a/153117/61405

https://codegolf.stackexchange.com/a/149629/61405
> 1 votes

# Answer
Use recursion over loops.

Recursive example

```
f(){printf("infiniteloop");f();}

```

For loop equivalent is 3 bytes longer.

```
f(){for(;;)printf("infiniteloop");}

```
> 1 votes

# Answer
# Conditional `printf` different format

```
x>0?printf("%c",x):printf("%d",-x);
printf(x>0?"%c":"%.f",x,0.-x);     // float goes different registers

```

Used here
> 1 votes

# Answer
# **Use strings as arrays**

Suppose you had an array like the following.

```
c[]={1,2,3,4,5,6,7,8,9,10};
// ...some code here...
printf("%d",c[i]);

```

You can make this at least 9 bytes shorter using this method.

```
char*x,*c="abcdefghij"; // initialize like this if you already have a 'char *' declaration somewhere.
c[]=L"abcdefghij";      // initialize like this you do not (thanks to @ceilingcat for teaching me this one).
// ...some code here...
printf("%d",c[i]-97);

```

---

You can also do something similar with an array of strings.

```
char*c[]={"cat","dog","mouse","fish"};
// ...some code here...
puts(c[i]);

```

you can reduce 2 bytes. However, this is slightly more tricker to get right. This usually only works when the length of the strings in the array only differ by 2 at most.

The '.' characters are padding that allows you to access each "substring" within the string using a multiple of a fixed offset.

```
char*c="cat\0..dog\0..mouse\0fish";
// ...some code here...
puts(c+6*i);

```

If the order of the strings do not matter, it is best to place the longest string at the end as, you may be able to save some bytes worth of padding.

```
char*c="cat\0.dog\0.fish\0mouse";
// ...some code here...
puts(c+5*i);

```

---

This is a useful trick that I have used to reduce quite a lot of bytes in the following answers.

\`lol\` is an ambigram, \`dad\` isn't

Can the chefs go?
> 1 votes

# Answer
# Omit Array Length

If you don't mind possible undefined behavior, define an array `C[]` (compiler assumes to have one element) and then rely upon the adjacent memory as usable space.

```
C[];main(){...}

```

Try it online!
> 1 votes

# Answer
# Omit `return`

Surprised that only this answer provided a similar situation

Instead of `return x;` in the end, use `g=x;` where `g` is a global variable.

In other situations, it may be more shortened. Refer here for more about this.
> 0 votes

---
Tags: code-golf, tips, c
---


# Question
Title: Find a fraction with the smallest denominator
# Input

Two non-negative floating point numbers \\$x \< y\\$. You can assume they are close enough to each other that there is no integer between \\$x\\$ and \\$y\\$.

# Output

A fraction with the smallest possible denomination that lies strictly between \\$x\\$ and \\$y\\$.

# Examples

Input: 1 and 2

Output: 3/2

Input: 0 and 0.33

Output: 1/4

Input: 0.4035 and 0.4036

Output: 23/57

# Answer
# JavaScript (Node.js), 42 bytes

```
x=>g=(y,d)=>(p=-~(x*d))<y*d?[p,d]:g(y,-~d)

```

Try it online!

If \\$ \left \lfloor xd \right \rfloor +1 \< yd \\$, then \\$ \left \lfloor xd \right \rfloor +1 \\$ is an answer
> 3 votes

# Answer
# JavaScript (ES6), 47 bytes

Expects `(x)(y)`, returns `[numerator, denominator]`.

```
(x,p=q=1)=>g=y=>p<y*q++&&p++>x*--q?[--p,q]:g(y)

```

Try it online!

### Commented

```
( x,          // x = first number
  p =         // p = numerator
  q = 1       // q = denominator
) =>          //
g = y =>      // y = second number
p < y * q++   // we test whether p/q < y
              // and increment q afterwards in case it's not
&&            // if truthy,
p++ > x * --q // we restore q, test whether p/q > x
              // and increment p afterwards in case it's not
?             // if truthy again:
  [--p, q]    //   we restore p and return [p, q]
:             // else:
  g(y)        //   we try again with either p or q incremented

```
> 2 votes

# Answer
# Jelly, 18 bytes

```
×ḞĊƭ€r/ḊṖ
1ç1#Ḣṭç¥

```

Try it online!

A pair of links which is called as a monad with a pair of floats and returns a pair of `[numerator, denominator]`.

## Explanation

<pre><code>×ḞĊƭ€r/ḊṖ | Helper link: takes a denominator as the left argument and a pair of floats as the right and returns a valid numerator, if any
×         | Multiply (denominator with floats)
 ḞĊƭ€     | Floor first, ceiling second
     r/   | Reduce using range
       ḊṖ | Remove first and last

1ç1#Ḣṭç¥ | Main link
1ç1#     | Starting with one, find first denominator where there’s a valid numerator (will be wrapped in a list)
    Ḣ    | Head (to unwrap the list)
     ṭç¥ | Tag this onto the result of  running the helper link again to find the numerator
```
</code></pre>
> 2 votes

# Answer
# Charcoal, 33 bytes

```
ＮθＮη≔⌕Ｅ⁺²∕¹⁻ηθ⁻⌈×ηι⌊×θι²ζＩ⟦⊖⌈×ηζζ

```

Try it online! Link is to verbose version of code. Explanation:

```
ＮθＮη

```

Input `x` and `y`.

```
≔⌕Ｅ⁺²∕¹⁻ηθ⁻⌈×ηι⌊×θι²ζ

```

Find `d` such that `⌈yd⌉-⌊xd⌋=2`. `d` is never more than `⌊1+1/(y-x)⌋`, but I have to add `2` due to 0-indexing.

```
Ｉ⟦⊖⌈×ηζζ

```

Output `⌈yd⌉-1` and `d`.
> 2 votes

# Answer
# Python 2, 95 bytes

```
(a,b),(c,d)=[input().as_integer_ratio()for m in 0,0]
while(m*d/c+1)*a>=m*b:m+=1
print m,m*d/c+1

```

Try it online!

Not a math guy, basically uses the formula of this answer.

The input should be in decimal format: `1.0` instead of just `1`.

*-2* bytes: replace `//` with `/`

*-4* bytes: inlining `m`
> 1 votes

# Answer
# , 47 bytes

```
\(x,y){while((p=(x*F)%/%1+1)>=y*F)F=F+1
c(p,F)}

```

Attempt This Online!

Port of @l4m2's JavaScript answer.
> 1 votes

---
Tags: code-golf
---


title: Picture of an old friend in ASCII art

text:
# Question
Title: Picture of an old friend in ASCII art
I hope this picture looks familiar to you.

It's one of Pacman's ghosts in his "vulnerable" state, after Pacman has eaten a power pill.

## The challenge

Picture our ghost in a little frame, using ASCII art. At normal scale (more about this later), each square in the above image should correspond to one character, and the frame should have a one-character separation up and down, and a two-character separation to the left and right of the ghost:

```
####################
#                  #
#       ####       #
#     ########     #
#    ##########    #
#   ############   #
#   ############   #
#   ###  ##  ###   #
#  ####  ##  ####  #
#  ##############  #
#  ##############  #
#  ##  ##  ##  ##  #
#  # ##  ##  ## #  #
#  ##############  #
#  ## ###  ### ##  #
#  #   ##  ##   #  #
#                  #
####################

```

But this doesn't look very pretty. `#` may not be the best choice for the active pixels. Besides, character cells are not square, which makes our friend look more ghostly than he already is.

So, to have more flexibility, the picture will change according to three input parameters:

* Character to be used for active pixels;
* Horizontal scale factor;
* Vertical scale factor.

For example, with `%`, `4`, `2` the ouput would be the better looking picture

```
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%                                                                        %%%%
%%%%                                                                        %%%%
%%%%                            %%%%%%%%%%%%%%%%                            %%%%
%%%%                            %%%%%%%%%%%%%%%%                            %%%%
%%%%                    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%                    %%%%
%%%%                    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%                    %%%%
%%%%                %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%                %%%%
%%%%                %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%                %%%%
%%%%            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%            %%%%
%%%%            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%            %%%%
%%%%            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%            %%%%
%%%%            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%            %%%%
%%%%            %%%%%%%%%%%%        %%%%%%%%        %%%%%%%%%%%%            %%%%
%%%%            %%%%%%%%%%%%        %%%%%%%%        %%%%%%%%%%%%            %%%%
%%%%        %%%%%%%%%%%%%%%%        %%%%%%%%        %%%%%%%%%%%%%%%%        %%%%
%%%%        %%%%%%%%%%%%%%%%        %%%%%%%%        %%%%%%%%%%%%%%%%        %%%%
%%%%        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        %%%%
%%%%        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        %%%%
%%%%        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        %%%%
%%%%        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        %%%%
%%%%        %%%%%%%%        %%%%%%%%        %%%%%%%%        %%%%%%%%        %%%%
%%%%        %%%%%%%%        %%%%%%%%        %%%%%%%%        %%%%%%%%        %%%%
%%%%        %%%%    %%%%%%%%        %%%%%%%%        %%%%%%%%    %%%%        %%%%
%%%%        %%%%    %%%%%%%%        %%%%%%%%        %%%%%%%%    %%%%        %%%%
%%%%        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        %%%%
%%%%        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        %%%%
%%%%        %%%%%%%%    %%%%%%%%%%%%        %%%%%%%%%%%%    %%%%%%%%        %%%%
%%%%        %%%%%%%%    %%%%%%%%%%%%        %%%%%%%%%%%%    %%%%%%%%        %%%%
%%%%        %%%%            %%%%%%%%        %%%%%%%%            %%%%        %%%%
%%%%        %%%%            %%%%%%%%        %%%%%%%%            %%%%        %%%%
%%%%                                                                        %%%%
%%%%                                                                        %%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

```

### Rules

All builtins allowed.

Inputs are taken in any reasonable format and any order. The first input above (character for active pixels) is guaranteed to be a printable ASCII character (codes 32 to 126).

Trailing space after each line or trailing newlines after last line are acceptable.

Code golf, fewest bytes wins.

# Answer
# CJam, ~~53~~ ~~51~~ 49 bytes

```
q~"ǟ #/?Y__Fy_Nf ǟ"f{'Ƞ^2b_W%+S@+f=}fe*e*N*

```

Note that three of the characters are unprintable. Try it online!

### Background

The right half of the unscaled output is identical to the left one, so it suffices to encode one of them. If we replace spaces with zeroes and non-spaces with ones, we get

```
1111111111
1000000000
1000000011
1000001111
1000011111
1000111111
1000111111
1000111001
1001111001
1001111111
1001111111
1001100110
1001011001
1001111111
1001101110
1001000110
1000000000
1111111111

```

where each line can be interpreted as a binary number. This yields

```
1023 512 515 527 543 575 575 569 633 639 639 614 601 639 622 582 512 1023

```

The easiest way to encode this information is to replace each integer with the Unicode character at that code point, but they would all require two bytes to be encoded with UTF-8.

By XORing the integers with 544, we keep all but two integers below 128 and avoid null bytes.

The result is

```
479 32 35 47 63 31 31 25 89 95 95 70 121 95 78 102 32 479

```

as integers or

```
ǟ #/?\x1f\x1f\x19Y__Fy_Nf ǟ

```

as an escaped string.

### How it works

```
q~                e# Read and evaluate all input. This pushes the vscale factor V,
                  e# the hscale factor H, and the character C.
"ǟ #/?Y__Fy_Nf ǟ" e# Push that string.
f{                e# For each character, push C and the character; then:
'Ƞ^               e#   XOR the character with '\u0220' (544), casting to integer.
 2b               e#   Convert from integer to base 2.
 _W%              e#   Push a reversed copy of the binary digits.
 +                e#   Concatenate.
 S@+              e#   Append C to " ".
 f=               e#   Replace each binary digit with ' ' or C.
}                 e#
fe*               e# Repeat each character in each string H times.
e*                e# Repeat each string V times.
N                 e# Join the strings, separating by linefeeds.

```
> 37 votes

# Answer
# Perl, ~~113~~ ~~105~~ ~~104~~ ~~100~~ ~~97~~ 96

Added +2 for `-ap`

Suggestions by dev-null save 9 bytes Fixed wrong count as noticed by Dennis

Run using `echo "2 4 %" | perl -ap pacman.pl`

`pacman.pl`:

```
}for(map+(unpack(aXBXB8Xb8XBXa),$/)x"@F","\xff\x00\x03\x0f\x1f\x3f\x3f\x39\x79\x7f\x7f\x66\x59\x7f\x6e\x46\x00\xff"=~/./g){s%%($&?$F[2]:$")x$F[1]%ge

```

except that the string `"\xff\x00\x03\x0f\x1f\x3f\x3f\x39\x79\x7f\x7f\x66\x59\x7f\x6e\x46\x00\xff"` should be written in binary form with single quotes

Space as replacement character becomes the empty string and leads to short lines. But it will all look blank anyways
> 12 votes

# Answer
# Dyalog APL, 64 bytes

```
{/∘⍉/⍺,⊂' '⍵[1+,∘⌽⍨1⍪⍨1⍪1,0⍪⍨0⍪0,0,⍉(7/2)⊤⎕AV⍳'Äâ\⊥⊥∘)⍞⍞┬#⍞`⍒']}

```

This takes the scale factor as its left argument and the character as its right argument, i.e:

```
      2 1{/∘⍉/⍺,⊂' '⍵[1+,∘⌽⍨1⍪⍨1⍪1,0⍪⍨0⍪0,0,⍉(7/2)⊤⎕AV⍳'Äâ\⊥⊥∘)⍞⍞┬#⍞`⍒']}'%'
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%                                    %%
 %%              %%%%%%%%              %%
 %%          %%%%%%%%%%%%%%%%          %%
 %%        %%%%%%%%%%%%%%%%%%%%        %%
 %%      %%%%%%%%%%%%%%%%%%%%%%%%      %%
 %%      %%%%%%%%%%%%%%%%%%%%%%%%      %%
 %%      %%%%%%    %%%%    %%%%%%      %%
 %%    %%%%%%%%    %%%%    %%%%%%%%    %%
 %%    %%%%%%%%%%%%%%%%%%%%%%%%%%%%    %%
 %%    %%%%%%%%%%%%%%%%%%%%%%%%%%%%    %%
 %%    %%%%    %%%%    %%%%    %%%%    %%
 %%    %%  %%%%    %%%%    %%%%  %%    %%
 %%    %%%%%%%%%%%%%%%%%%%%%%%%%%%%    %%
 %%    %%%%  %%%%%%    %%%%%%  %%%%    %%
 %%    %%      %%%%    %%%%      %%    %%
 %%                                    %%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

```

Explanation:

* `⍉(7/2)⊤⎕AV⍳'Äâ\⊥⊥∘)⍞⍞┬#⍞`⍒'`: The left half of the ghost, without the border. (It is symmetric.) Each character has its high bit set, to prevent selecting non-printing characters from `⎕AV`, but only the first 7 bytes are used.
* `0,⍪⍨0⍪0,0,`: add a border of blanks on the left, top, and bottom
* `1⍪⍨1⍪1,`: add the frame on the left, top, and bottom
* `,∘⌽⍨`: join it with its vertical mirror
* `1+`: add 1, because arrays are 1-indexed by default
* `' '⍵[`...`]`: use that matrix as an index into the string `' '⍵`, so each 0 gets mapped to a blank and each 1 gets mapped to .
* `⍺,⊂`: enclose the matrix and join it to the scale factors
* `/`: right fold with the following function:
* `/∘⍉`: transpose and scale horizontally
> 9 votes

# Answer
# MATL, 71 bytes

```
32hO511-3-12-16-32O6-64-6O25 13-38 17 40 70-511Nq$hYs10H$Bt!P!hi1$lX*Q)

```

**Try it online!**

### Explanation

The image is horizontally symmetric, so only the left half needs to be coded. Each 10-pixel row is binary coded as a number between 0 and 1023. Active pixels are coded as 0 rather than 1, so the first row is number 0 rather than 1023.

Since consecutive rows differ by a few pixels only, the numbers are further encoded differentially. So each row will be decoded as the cumulative sum of all numbers up to that row, followed by conversion to binary.

The needed numbers are then

```
0 511 -3 -12 -16 -32 0 6 -64 -6 0 25 13 -38 17 40 70 -511

```

0 is introduced in MATL using the `O` function, which avoids a separator with neighbouring numbers. Also, negative signs do not imply extra bytes as they serve as separators.

Once the array has been created, it is cumulatively summed, binary-decoded, and horizontally mirrored. The resulting 2D array is used to index a two-char string to produce the result. This string is of the form `'% '`, where `'%'` is an input char.

As noted by @Conor, the code also works with two chars as input. In this case the final string indexed into will be of the form `'%_ '`, where the input is a two-char string `'%_'`. The space will simply be ignored, because the indexing array only addresses the first two chars.

```
32                                             % space (ASCII)
h                                              % concat horizontally with 1st input: char
O511-3-12-16-32O6-64-6O25 13-38 17 40 70-511   % push these numbers
Nq$h                                           % concat all those numbers
Ys                                             % cumulative sum
10H$B                                          % convert to 10-digit binary numbers
                                               % gives 2D array, each number in one row
t                                              % duplicate
!P!                                            % flip horizontally
h                                              % concat horizontally
i                                              % take 2nd input: array [V H]
1$l                                            % matrix oh V×H ones
X*                                             % Kronecker product to increase vertical
                                               % and horizontal scales by V and H resp.
Q                                              % add 1. Converts array of 0,1 into 1,2
)                                              % uses those 1,2 as indices into string

```
> 7 votes

# Answer
# BBC BASIC, ~~239~~ ~~236~~ ~~232~~ 214 bytes

```
0DEFPROCM(A,B,C)C=C-32:FORU=0TO18*A-1:FORV=0TO20*B-1:Y=U DIVA:X=V DIVB:V.32-C*FNC((X<10)*-X-(X>9)*(19-X),Y):N.:P.:N.:E.
1DEFFNC(X,Y)Z=Y*10+X:=((ASCMI."#Cb^2aC*[#1CF<;)C$;I9I$;EYLb&#",Z/6+1)-35)AND(2^(Z MOD6)))=0

```

Calling `PROCM(1,1,35)` produces the ghost made of # symbols. The arguments to PROCM are: horizontal scale, vertical scale, ASCII value of character.

This program will work both for Brandy Basic, and BASIC 2 on an original Model B.
> 3 votes

# Answer
# C (gcc), ~~199~~ 197 bytes

-2 bytes thanks to @JonathanFrech

```
n,j;f(c,h,v){for(char t[20],i=18;i--;){for(n=10;n--;)t[n]=t[19-n]=((("\xff\0""1;\x7fM3\x7f\x7fON~~|x`\0\xff"[i]<<3)|(i&&i^17?1:7))>>n)&1?c:32;for(j=v;j--;puts(""))for(n=20*h;n--;)putchar(t[n/h]);}}

```

Try it online!

# 188 bytes (unprintables)

Courtesy of @JonathanFrech.

```
n,j;f(c,h,v){for(char t[20],i=18;i--;){for(n=10;n--;)t[n]=t[19-n]=((("\xff\0001;M3ON~~|x`\0\xff"[i]<<3)|(i&&i^17?1:7))>>n)&1?c:32;for(j=v;j--;puts(""))for(n=20*h;n--;)putchar(t[n/h]);}}

```

Try it online!

Nothing spectacular going on. Like others noticed, the ghost is highly symmetrical. The image itself is 20 units wide, but except for the top and bottom rows, the three right-most columns are identical. This allows us to store half of the image as characters instead of having to use integers:

```
#######  127     \x7f
           0     \0
##        96     `
####     120     x
#####    124     |
######   126     ~
######   126     ~
#  ###    78     N
#  ####   79     O
#######  127     \x7f
#######  127     \x7f
 ##  ##   51     3
#  ## #   77     M
#######  127     \x7f
 ### ##   59     ;
 ##   #   49     1
           0     \0
#######  127     \x7f

```

The resulting string was reversed to eke out a few bytes on having a descending for loop (also solving an annoying issue with hexadecimal escapes). Other loops could be flipped without issue thanks to symmetry.

Each character is shifted left and given a border (with special care on first and last rows). Then it's just a matter of outputting the string correctly scaled.

All the for loops makes me feel there is a better way.

# C (gcc), 175 bytes (non-ASCII)

Another version, this time courtesy of ceilingcat. Uses some funky non-ASCII characters.

```
n,j;f(c,h,v){for(char t[20],i=18;i--;){for(n=10;n--;)t[n]=t[19-n]=(L"ǿĀ1;ſM3ſſON~~|x`\0ǿ"[i]*8|(i&&i^17?1:7))>>n&1?c:32;for(j=v;j--;puts(""))for(n=20*h;n--;)putchar(t[n/h]);}}

```

Try it online!
> 3 votes

# Answer
## Batch, ~~740~~ ~~722~~ 720 bytes

```
@echo off
setlocal enabledelayedexpansion
set h=%3
set w=
set s=
for /l %%a in (1,1,%2)do set w=%1!w!&set s= !s!
call:l ####################
call:l #                  #
call:l #       ####       #
call:l #     ########     #
call:l #    ##########    #
call:l #   ############   #
call:l #   ############   #
call:l #   ###  ##  ###   #
call:l #  ####  ##  ####  #
call:l #  ##############  #
call:l #  ##############  #
call:l #  ##  ##  ##  ##  #
call:l #  # ##  ##  ## #  #
call:l #  ##############  #
call:l #  ## ###  ### ##  #
call:l #  #   ##  ##   #  #
call:l #                  #
call:l ####################
exit/b
:l
set l=%*
set l=!l: =%s%!
for /l %%a in (1,1,%h%)do echo !l:#=%w%!

```

Edit: Saved ~~18~~ 20 bytes by removing unnecessary spaces.
> 2 votes

# Answer
## Seriously, 116 bytes

```
╩' "3ff 200 203 20f 21f 23f 23f 239 279 27f 27f 266 259 27f 26e 246 200 3ff"s`24╙(¿¡╜'1(Æ' '0(Æ"╛*"£M;R@+εj2└@n`M'
j

```

That newline is important. Hexdump:

```
00000000: ca27 2022 3366 6620 3230 3020 3230 3320  .' "3ff 200 203
00000010: 3230 6620 3231 6620 3233 6620 3233 6620  20f 21f 23f 23f
00000020: 3233 3920 3237 3920 3237 6620 3237 6620  239 279 27f 27f
00000030: 3236 3620 3235 3920 3237 6620 3236 6520  266 259 27f 26e
00000040: 3234 3620 3230 3020 3366 6622 7360 3234  246 200 3ff"s`24
00000050: d328 a8ad bd27 3128 9227 2027 3028 9222  .(...'1(.' '0(."
00000060: be2a 229c 4d3b 5240 2bee 6a32 c040 6e60  .*".M;R@+.j2.@n`
00000070: 4d27 0d0a 6a                             M'..j

```

Same strategy as Dennis's CJam answer, but the values are encoded in hex, rather than XORed with 544, and string manipulation is a lot harder in Seriously.

Try it online!
> 2 votes

# Answer
# Stax, 45 bytes

```
àÄÅ╣>u°↨2ö|dτÅbn╦─▀:ΣFúÇz?⌂É\!n▄§V0Ncó╤½8|δò_

```

Run and debug it

Explanation:

```
"<long string>"!E' x+:BA/s|*mn|*:m Full program, implicit input.
"<long string>"!E                  Push 1531747987795407832964332490922049710271411270772589567
                 ' x+              Push a space plus the given character
                     :B            Interpret the number in binary, replacing 0 with ' ' and 1 with the given char
                       A/          Group into pieces of length 10.
                                   Gives the first half of each line.
                         s|*       Repeat each line <vertical scale factor> times
                            m      For each line:
                             n|*     Repeat each character <horizontal scale factor> times
                                :m   Mirror
                                     Implicit output with newline

```
> 2 votes

# Answer
# Vyxal, 42 bytes

```
»∆nµOḢrċ:f=¢×⁽Ti∴%β‡zwøÞ»ð?+τ18/ƛƛ⁰*;ṅm¹(…

```

Try it Online!

```
»...»                  # Compressed integer representation
        τ              # Decompress using...
     ð?+               # Space and input char
         18/           # Divide into 18 pieces
            ƛ          # Foreach...
             ƛ  ;      # Foreach character
              ⁰*       # Repeat as necesarry
                 ṅ     # Join
                  m    # Palindromise
                   ¹(… # Print (input) times

```
> 2 votes

# Answer
## JavaScript (ES6), 167 bytes

```
(s,w,h)=>[...`Ǌ56:*

\fLJJSlJ[s5Ǌ`].map(c=>`${t=(c.charCodeAt()^565).toString(2)}${[...t].reverse().join``}
`.replace(/./g,b=>` ${s}`[b].repeat(w)).repeat(h)).join``

```

Based on @Dennis's answer. I guess you could shave off another byte by using a literal FF instead of `\f`, but I doubt I can paste one in here. When trying this out you may also want to use `\u01CA` instead of the `Ǌ` character.

Sadly prepending a space to the character argument costs a whole 6 bytes.
> 1 votes

# Answer
## Python 2, ~~838~~ ~~828~~ 618 bytes

Saved 210 bytes by using a string instead of an array, thanks to Dennis for that suggestion, I know I can make even better, but for now its a good improvement.

~~This is the best I can do, I'm not very good with graphics in command line.~~

I took the small ghost as base.

I'm using the ascii 219 by default, because with that char, the ghost looks pretty awesome!!!

### Golfed

```
def g(c,s,w,h,l=""):
 x="c-20,c-1,s-18,c-1,c-1,s-7,c-4,s-7,c-1,c-1,s-5,c-8,s-5,c-1,c-1,s-4,c-10,s-4,c-1,c-1,s-3,c-12,s-3,c-1,c-1,s-3,c-12,s-3,c-1,c-1,s-3,c-3,s-2,c-2,s-2,c-3,s-3,c-1,c-1,s-2,c-4,s-2,c-2,s-2,c-4,s-2,c-1,c-1,s-2,c-14,s-2,c-1,c-1,s-2,c-14,s-2,c-1,c-1,s-2,c-2,s-2,c-2,s-2,c-2,s-2,c-2,s-2,c-1,c-1,s-2,c-1,s-1,c-2,s-2,c-2,s-2,c-2,s-1,c-1,s-2,c-1,c-1,s-2,c-14,s-2,c-1,c-1,s-2,c-2,s-1,c-3,s-2,c-3,s-1,c-2,s-2,c-1,c-1,s-2,c-1,s-3,c-2,s-2,c-2,s-3,c-1,s-2,c-1,c-1,s-18,c-1,c-20"
 for r in x.split(","):
  d=r.split("-");l+=d[0].replace("s",s).replace("c",c)*int(d[1])*w
  if len(l)==20*w:print(l+"\n")*h,;l=""

```

### Try it on repl.it

### Ungolfed

```
def pacmanGhost(char = "█", sep = " ", width = 1, height = 1):
    coords = [[[char, 20]], [[char, 1], [sep, 18], [char, 1]],[[char, 1], [sep, 7], [char, 4], [sep, 7], [char, 1]], [[char, 1], [sep, 5], [char, 8], [sep, 5],
         [char, 1]], [[char, 1], [sep, 4], [char, 10], [sep, 4], [char, 1]], [[char, 1], [sep, 3], [char, 12], [sep, 3], [char, 1]], [[char, 1], [sep, 3],
         [char, 12], [sep, 3], [char, 1]], [[char, 1], [sep, 3], [char, 3], [sep, 2], [char, 2], [sep, 2], [char, 3], [sep, 3], [char, 1]], [[char, 1],
         [sep, 2], [char, 4], [sep, 2], [char, 2], [sep, 2], [char, 4], [sep, 2], [char, 1]], [[char, 1], [sep, 2], [char, 14], [sep, 2], [char, 1]],
         [[char, 1], [sep, 2], [char, 14], [sep, 2], [char, 1]], [[char, 1], [sep, 2], [char, 2], [sep, 2], [char, 2], [sep, 2], [char, 2], [sep, 2],
         [char, 2], [sep, 2], [char, 1]], [[char, 1], [sep, 2], [char, 1], [sep, 1], [char, 2], [sep, 2], [char, 2], [sep, 2], [char, 2], [sep, 1], [char, 1],
         [sep, 2], [char, 1]], [[char, 1], [sep, 2], [char, 14], [sep, 2], [char, 1]], [[char, 1], [sep, 2], [char, 2], [sep, 1], [char, 3], [sep, 2],
         [char, 3], [sep, 1], [char, 2], [sep, 2], [char, 1]], [[char, 1], [sep, 2], [char, 1], [sep, 3], [char, 2], [sep, 2], [char, 2], [sep, 3],
         [char, 1], [sep, 2], [char, 1]], [[char, 1], [sep, 18], [char, 1]], [[char, 20]]]
    for coord in coords:
        line = ""
        for element in coord:
            line = "{}{}".format(line, element[0] * element[1] * width)
        for i in range(height):
            print(line)
    return

```

### Test
> 1 votes

# Answer
# Python 2, 244 bytes

```
p,w,h=raw_input().split()
for i in range(18): mystr=''.join([(p if i=='1'else' ')*int(w)for i in str(10+(i%17==0))+format(ord('\xff\x00\x03\x0f\x1f??9y\x7f\x7ffY\x7fnF\x00\xff'[i]),'08b')]);print'\n'.join([mystr+mystr[::-1]for j in[1]*int(h)])

```
> 1 votes

# Answer
# Python 2, 169 bytes

```
def a(s,x,y):
    z=[]
    for c in u'\u01df #/?\x1f\x1f\x19Y__Fy_Nf \u01df':
        b="".join((s if d=="1"else" ")*x for d in bin(ord(c)^544)[2:]);z+=[b+b[::-1]]*y
    print"\n".join(z)

```

Try it online!

## Explanation:

```
u'\u01df #/?\x1f\x1f\x19Y__Fy_Nf \u01df'

```

As in Dennis's answer, each character in this string represents the binary representation of one line of the left half of the "image", XOR 544.

```
for c in <unicode string>:

```

For each character in the string, do the following:

```
    bin(ord(c)^544)

```

Transform the character into its integer representation, then perform a binary XOR with 544. Then transform this integer into a character string of its binary representation, like '0xb1111111111'.

```
    for d in <string>[2:]

```

For each character in the sting, starting at position 2 (which skips the 0b at the beginning), do the following:

```
    (s if d=="1"else" ")*x

```

If the character == "1", replace it with the supplied character, otherwise replace it with a space. Then copy this character x times. (x=0 will result in an empty string.)

```
    b="".join(<previously generated list of strings>)

```

Concatenate all strings into one long string, separated by an empty string "".

```
    z+=[b+b[::-1]]*y

```

make a string of b + the reverse of b, then create an array containing y instances of this string (y=0 will produce an empty list \[\]), then append this list to the list z.

```
print"\n".join(z)

```

Finally, print to screen each of the produced strings, separated by line breaks.
> 1 votes

# Answer
Added some text color using ASCII Escape Codes to match the original image.

# C (msvc), 468 bytes

```
#include <stdio.h>
main(){char*i[]={"2B14B2B","2B5B4C5B2B","2B3B8C3B2B","2B2B10C2B2B","2B1B12C1B2B","2B1B12C1B2B","2B1B3C2W2C2W3C1B2B","2B4C2W2C2W4C2B","2B14C2B","2B14C2B","2B2C2W2C2W2C2W2C2B","2B1C1W2C2W2C2W2C1W1C2B","2B14C2B","2B2C1B3C2B3C1B2C2B","2B1C3B2C2B2C3B1C2B","2B14B2B"};for(int y=0;y<16;y++,puts("\x1b[0m")){for(char*p=i[y];*p;){int n=strtol(p,&p,10);char c=*p++;char*color=(c=='B')?"\x1b[40m":(c=='C')?"\x1b[44m":(c=='W')?"\x1b[47m":"\x1b[0m";printf("%s%*s",color,n*2,"");}}}

```

Try it online!

# Output

Windows Command Prompt:
> 1 votes

---
Tags: code-golf, ascii-art, kolmogorov-complexity
---


title: Official Tetris Piece Ordering

text:
# Question
Title: Official Tetris Piece Ordering
Classic Tetris was often a difficult game to play. One problem was that you could only work with the Tetris piece you were given, so if you had an awkward board, it would sometimes be difficult to find a suitable location to put your piece. Another problem was that you could only look one piece ahead, so it was difficult to prepare your board for upcoming pieces. These problems together made the classic game quite frustrating to play.

Official Tetris solves these problems with the hold slot and next queue. The next queue allowed a player to look ahead 5 pieces, instead of 1. However, if a player was still unsatisfied with the piece they currently had, they could "hold" the piece in the hold slot and instead use the next piece in the queue.

For example, take the board below.

It would be hard to place the square piece on the board, so the player could "hold" the piece and use the jagged 'Z' piece instead:

Once you "hold" a piece, however, the game doesn't allow you to keep "holding", or switching the pieces again and again until you've used the new piece. For instance, in the example above, you wouldn't be able to switch back to the square piece until you've used the jagged 'Z' piece.

If you want to try this mechanic out yourself, go to JSTris or tetr.io and play around with it.

# Challenge:

The pieces will be labelled J, L, S, Z, O, I, or T. Given the next queue, the current piece, and the hold piece (assume it exists for now), generate all possible orders you can place 6 of the pieces in.

For example, if the next queue was `[Z,S,L,J,I]`, the current piece was O, and the held piece was T, 3 possible orders would be the following:

```
1. O, Z, S, L, J, I (no hold used at all)
2. T, Z, S, L, J, I
   ^ hold O here
3. O, Z, T,        L, J, S
         ^ hold S here   ^ hold I here, S was in hold slot so put S here

```

# Answer
# Python 3, 70 bytes

```
f=lambda x,y=[]:x[1:]and f(x[1:],y+x[:1])+f(x[:1]+x[2:],y+[x[1]])or[y]

```

Try it online!

# Python 3, 66 bytes by tsh

```
f=lambda a,o='':a[1:]and f(a[1:],o+a[0])+f(a[0]+a[2:],o+a[1])or[o]

```

Try it online!

I'm not sure if I understood correctly,
> 2 votes

# Answer
# JavaScript (ES6), 49 bytes

Expects `(queue, held_piece)`, where the first item in the queue is the current piece.

```
f=([c,...a],h,o="")=>c?f(a,h,o+c)+[,f(a,c,o+h)]:o

```

Try it online!
> 2 votes

# Answer
# Curry (PAKCS), 39 bytes

```
f(c:q)h=h:f q c
f(c:q)h=c:f q h
f""h=""

```

Try it online!

Takes the queue (starting from the current piece) as a string and piece in hold as a char. Basically, the code just describes what can happen during a move. Due to non-deterministic behavior, Curry just walks through all the possibilities, which is exactly what we need here.
> 2 votes

# Answer
# Charcoal, ~~32~~ 29 bytes

```
⊞υＳＦＳ≔ΣＥυ⟦⭆κ⁺μ×ι¬ν⁺ικ⟧υＥυ⮌✂ι¹

```

Attempt This Online! Link is to verbose version of code. Takes the hold piece as the first input and the current piece and next queue as a single string as the second input. Explanation:

```
⊞υＳ

```

Start with the hold piece and no played pieces.

```
ＦＳ

```

Loop over the queue.

```
≔ΣＥυ⟦⭆κ⁺μ×ι¬ν⁺ικ⟧υＥυ

```

For each position, create two positions, one playing the current piece and one holding it and playing the hold piece. Note that the piece is played at the start of the string, so the played pieces are currently in reverse order.

```
⮌✂ι¹

```

Print the played pieces of the positions in the correct order.
> 1 votes

# Answer
# Python 3, 69 bytes

```
f=lambda x,y,*a:a and[p+j for p,q in[x+y,y+x]for j in f(q,*a)]or[x,y]

```

Try it online!

Input 7 chars, output str.
> 0 votes

# Answer
# APL(Dyalog Unicode), ~~33,32,31,29,~~26 bytes SBCS

```
(,⍳6⍴2){1↓¯1∘⌽@(⍸1,⍺)⊢⍵}¨⊂

```

Try it on APLgolf!

A tacit function which takes a string on the right in the order of held piece, current piece, queue.

## Old Explanation (essentially the same)

```
(⍳64){1↓¯1∘⌽@(⍸~(7⍴2)⊤⍺)⊢⍵}¨⊂
                            ⊂  # put the input in an array
                               #     so the 'each' doesn't apply to it
     {                    }¨   # apply this dfn for each...
(⍳64)                 ⍺        #     number between 0 and 63
                 7⍴2           # 2 2 2 2 2 2 2 so we can...
                (7⍴2)⊤         #     convert 7 binary digits
               ~               # bitwise not
              ⍸                # indices of 1s
             (⍸~(7⍴2)⊤⍺)       # all combinations of 0-6 that have a 0
            @           ⊢⍵     # at those indices of the input...
        ¯1∘⌽                   #     shift the letters left by 1
      1↓                       # then drop the first letter

```

Created with the help of Luminespire.

This works without recursion because we can take the composition of swaps (holding a piece) and get $$(0~d)(0~c)(0~b)(0~a) = (0~a~b~c~d)$$ in permutation notation. So we take all possible selections of places to hold, add a 0 to each, and permute the input using `¯1∘⌽@`, rotating the selected indices by 1.
> 0 votes

# Answer
# Retina 0.8.2, 30 bytes

```
+%`(.),(.)
$2$1,$'¶$`$1$2,
.,

```

Try it online! Takes the hold piece as the first input and the current piece and next queue as a single string as the second input, separated by a comma. Explanation:

```
(.),(.)
$2$1,$'¶$`$1$2,

```

Match the hold piece and the current piece and create two new positions, one by playing the current piece and one by playing the hold piece.

```
+%`

```

Repeat the above separately on each position until queue is empty.

```
.,

```

Delete the hold piece and separator from each result.
> 0 votes

# Answer
# Jelly, 19 bytes

```
W;Ɱ2ṗ6¤œ-ị@¥\€œ-Ɲ€Y

```

Try it online!

A full program that takes a string as its argument (held, current, five next) and prints the 64 possibilities to STDOUT.

## Explanation

```
W                   | Wrap in a list
 ;Ɱ                 | Concatenate to each of:
   2ṗ6¤             | - 2 Cartesian power 6 (i.e. all lists length 6 of 1s and 2s)
           ¥\€      | For each of these, reduce using the following, collecting up intermediate results:
       œ-ị@         | - Set difference between the current set of pieces and the one found at the index of the right argument (either the first or second)
              œ-Ɲ€  | Set difference of neighbours for each of these outputs
                  Y | Join with new lines

```
> 0 votes

# Answer
# Scala, 127 bytes

A port of @l4m2's Python answer in Scala.

127 bytes, it can be golfed more.

---

Golfed version. Attempt This Online!

```
type L[C]=List[C]
def f[C<:Char](x:L[C],y:L[C]=Nil):L[L[C]]=x match{case h::n::t=>f(n::t,y:+h):::f(h::t,y:+n);case _=>List(y);}

```

Ungolfed version. Attempt This Online!

```
object Main {
  def f(x: List[Char], y: List[Char] = List()): List[List[Char]] = x match {
    case head :: next :: tail => f(next :: tail, y :+ head) ::: f(head :: tail, y :+ next)
    case _ => List(y)
  }

  def main(args: Array[String]): Unit = {
    val result = f(List('O', 'T', 'Z', 'S', 'L', 'J', 'I'))
    println(result)
  }
}

```
> 0 votes

# Answer
# x86-64 machine code, 23 bytes

```
B6 40 56 88 F2 A8 AA AC D0 EA 73 FA A4 75 F9 5E FE C6 71 EE 88 17 C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes:

* in RDI, an address at which to place the result, as multiple null-terminated byte strings run together, terminated with an empty string;
* in RSI, the address of the input, as a null-terminated byte string.

In assembly:

```
f:
    mov dh, 64  # Set DH to 64.
# (This value will run from 64 to 127. The bottom six bits indicate
#  when to switch the hold piece in, covering all possibilities.
#  The top two bits are always 01.)
repeat:
    push rsi    # Save the value of RSI onto the stack.
    mov dl, dh  # Set DL to the value of DH.
    .byte 0xA8  # Absorbs the next instruction into "test al, 0xAA".
switch:
    stosb       # Write AL to the output string, advancing the pointer.
    lodsb       # Read from the input string into AL, advancing the pointer.
nextpiece:      # (AL will store the currently held piece.)
    shr dl, 1   # Shift DL right by 1 bit. The bit shifted out goes into CF.
    jnc switch  # Jump if CF=0.
    movsb       # Add a byte from the input string to the output string,
                #  advancing both pointers.
    jnz nextpiece # Jump if the last calculated value (DL) is nonzero.
    pop rsi       # Restore the value of RSI from the stack.
    inc dh        # Add 1 to DH.
    jno repeat    # Jump back, except when DH overflows from 127 to -128.
    mov [rdi], dl # Add a null byte from DL to the output string.
    ret           # Return.

```
> 0 votes

---
Tags: code-golf, tetris
---


title: "Perfect" an array

text:
# Question
Title: "Perfect" an array
Given an n non-negative integers, how many numbers must be changed so that each number x appears x times? You cannot add or remove elements, only replace them with other numbers.

For example:

```
1 6 23 6 9 23 1 1 6

```

can be turned into:

```
1 6 2 6 6 2 6 6 6

```

with 5 changes, which is optimal.

## Test cases

```
0 => 1
1 2 3 => 1
5 5 5 5 5 => 0
23 7 4 8 => 3
100 100 100 6 => 4
5 5 5 5 5 5 => 1
1 2 2 4 4 4 4 9 9 9 9 => 5

```

Shortest code wins!

# Answer
# Vyxal 3, 16 bytes

```
L:ɾẋΩᵛC₌}ƛ?ÞṅL}g

```

Simple bruteforce, probably can be golfed more.

Try it Online!

```
L:ɾẋΩᵛC₌}ƛ?ÞṅL}g
L:ɾẋ              # Nth cartesian power of range [1, length]
    Ω   }         # Filter by items where
     ᵛC₌          # Count of each item is item
         ƛ    }   # Map through list
          ?ÞṅL    # Length of multiset difference between input and item
               g  # Push minimum

```

Created with the help of Luminespire.
> 8 votes

# Answer
# , 88 bytes

```
\(x,n=sum(x|1))min(combn(rep(1:n,n),n,\(r)`if`(all(names(t<-table(r))==t),sum(r!=x),n)))

```

Attempt This Online!
> 4 votes

# Answer
# Haskell + hgl, 28 bytes

```
mMl<df**<fb(jn rl)<<dpS uq<l

```

I didn't want to brute force this, so I didn't. Although brute forcing would probably be shorter.

## Explanation

First we find all the strictly descending integer partitions of the length of the input. We convert these to "perfect lists". This gives us all the perfect lists with the same size as the input. Then we take use the set difference to remove the elements in the input from each perfect list, these represent the number of replacements that need to be done. Then we get the size of the smallest element and output that.

## Reflection

This answer feels *painfully* long. There are a couple things here:

* `dpS uq` is a bad way to get strictly descending integer partitions. It is 6 bytes long and slower than it needs to be. There should be a 3-byte version.
* This isn't the first time I've wanted a function that zips and then concatenates, but I apparently haven't added it. It would be useful here.
* There should be a shorter way to replicate every item in a list its own number of times (currently `fb(jn rl)`). I remember noticing that some obscure combination of functions did this, but I can't remember which. It's really bothering me.
> 4 votes

# Answer
# Jelly, 12 bytes

```
JṗLċⱮ`ƑƇn⁸§Ṃ

```

A monadic Link that accepts a list of integers and yields the minimal number to alter to form a *perfect array*.

**Try it online!** Or see the test-suite.

### How?

Constructs all lists of the same length as the input using an alphabet of `1` through to that length (with the elements in all possible orders). Filters these down to *perfect arrays*. Counts the differing entries of each with respect to the input (by summing the results of a vectorised not-equal). Returns the minimum.

```
JṗLċⱮ`ƑƇn⁸§Ṃ - Link: list of integers, Array
J            - indices {Array} -> [1..length(Array)]
  L          - length {Array}
 ṗ           - {Indices} Cartesian power {Length}
                 -> all arrays of length length(Array) formed from 1..length(Array)
       Ƈ     - keep those for which:
      Ƒ      -   is invariant under?:
    Ɱ`       -     map across itself with:
   ċ         -       count occurrences
        n⁸   - {that} not-equal? (vectorises) {Array}
          §  - sums
           Ṃ - minimum

```
> 3 votes

# Answer
# K (ngn/k), 29 bytes

```
{&/+/~x=+{+/x=\:x}/'+!#/2##x}

```

Try it online!

`+!#/2##x` Generate all n-tuples with values in \[0,n), where n is the length of the input.
`{...}/'` For each tuple, run until convergence:
`+/x=\:x` ... Replace each value with its count.1
`~x=+` element-wise comparison between the input and each generated tuple.
`&/+/` Find the minimum number of different values.

1 If this converges it must have reached a perfect array. Right now I can't think of a proof that it always converges (or equivalently, there are no cycles of length \>1).
> 3 votes

# Answer
# 05AB1E, 13 bytes

```
ā¤ãʒÐ¢Q}€-ĀOß

```

Port of *@mathScat*'s Vyxal answer.

Try it online or verify all test cases.

**Explanation:**

```
ā          # Push a list in the range [1, (implicit) inpu-length]
 ¤         # Push its last item (without popping): the length
  ã        # Cartesian power, to create all possible lists of this length
   ʒ       # Filter it by:
    Ð      #  Triplicate the current list
     ¢     #  Pop two, and count how many times each item occurs
      Q    #  Check that this list of counts and current list are still the same
   }€      # After the filter: map over each remaining list:
     -     #  Subtract the values at the same positions from the (implicit) input-list
      Ā    # Check for each difference that it's NOT 0 (0 if 0; 1 otherwise)
       O   # Sum the checks of each inner list together
        ß  # Pop and push the minimum
           # (which is output implicitly as result)

```
> 2 votes

# Answer
# JavaScript (ES7), 122 bytes

Brute force.

```
a=>eval("for(m=s=a.length,n=s**s;n--;)a.map(c=(x,i)=>(c[v=n/s**i%s+1|0]=-~c[v],d+=v!=x,v),d=0).some(v=>c[v]-v)|d>m?m:m=d")

```

Try it online!

### Commented

This is a version without `eval()` for readability.

```
a => {                  // a[] = input array
  for(                  // main loop:
    m =                 //   m = minimum score
    s = a.length,       //   s = size of a[]
    n = s ** s;         //   n = counter, initialized to s ** s
    n--;                //   decrement n down to 0
  )                     //
    a.map(c =           // c = object to count value occurrences
    (x, i) =>           // for each element x at index i in a[]:
      ( c[              //   increment c[v]
          v =           //   where v is:
            n / s ** i  //     a value in [1 .. s] computed
            % s + 1 | 0 //     according to n and i
        ] = -~c[v],     //
        d += v != x,    //   increment d if v != x
        v               //   yield v
      ),                //
      d = 0             //   start with d = 0
    )                   // end of map()
    .some(v =>          // for each value v in the result of map():
      c[v] - v          //   trigger some() if c[v] != v
    ) |                 // end of some()
    d > m ?             // if some() was triggered or d > m:
      m                 //   do nothing
    :                   // else:
      m = d;            //   update m to d
  return m              // return m
}                       //

```
> 1 votes

# Answer
# Python3, 742 bytes

Rather long, but non-brute force solution (for the sake of variety)

```
from itertools import*
D=lambda d,n,K,U:{**{a:b for a in d if(b:=[j for j in d[a]if j not in K])},n:[*K,*U]}
def P(n,d,r,F):
 U=d.get(n,[])
 d={i:d[i]for i in d if i!=n}
 k=[[],[]]
 for i in d:
  if i<n or len(d[i])!=i:k[i>F]+=d[i]
 if len(k[1])>=r:yield D(d,n,K:=k[1][:r],U),K;return
 for K in combinations(k[0]+k[1],r):
  if[]==k[1]or any(j in K for j in k[1]):yield D(d,n,K,U),K
def f(a):
 d,I={},0
 for i in a:d[i]=d.get(i,[])+[I];I+=1
 q=[(len(a),len(a),d,0)]
 M=-1
 while q:
  n,A,d,C=q.pop(0)
  if all(i==len(d[i])for i in d):M=min(M,C)if M!=-1 else C;continue
  if n==0:continue;
  if len(L:=d.get(n,[]))!=n:
   r,F=n-len(L),A-n
   for u,i in P(n,d,r,F):
    if M==-1 or C+len(i)<M:q+=[(F,A-n,u,C+len(i))]
  q+=[(n-1,A,d,C)]
 return M

```

Try it online! (includes extra/longer test cases)
> 1 votes

# Answer
# Charcoal, 33 bytes

```
Ｉ⌊ＥΦＥＸ²Ｌθ⌕Ａ⮌⍘⊗ι²1⁼ΣιＬθΣＥι⌈⟦⁰⁻λ№θλ

```

Try it online! Link is to verbose version of code. Explanation:

```
ＥＸ²Ｌθ⌕Ａ⮌⍘⊗ι²1

```

Generate all subsets of `{1..l}`, where `l` is the length of the input array.

```
Φ....⁼ΣιＬθ

```

Filter for those that sum to `l`.

```
Ｉ⌊Ｅ...ΣＥι⌈⟦⁰⁻λ№θλ

```

Calculate the number of changes required for each subset and output the minimum.
> 1 votes

# Answer
# APL (Dyalog Classic), 39 37 bytes

```
{⌊/+/¨⍵∘≠¨{⍵/⍨{⊃∧⌿{⍺=⍴⍵}⌸⍵}¨⍵},⍳⍴⍨⍴⍵}

```

Try it online!

```
{⌊/+/¨⍵∘≠¨{⍵/⍨{⊃∧⌿{⍺=⍴⍵}⌸⍵}¨⍵},⍳⍴⍨⍴⍵}
{                               ,⍳⍴⍨⍴⍵} generate all n-length arrays of numbers 1-n (where n is the input length)
          {⍵/⍨              ¨⍵}        keep only arrays for which
              {⊃∧⌿{⍺=⍴⍵}⌸⍵}           all numbers appear a number of times equal to their value (perfect arrays)
      ⍵∘≠¨                              for each, find the number of elements that differ from the input
 ⌊/+/¨                                  and return the minimum

```
> 1 votes

# Answer
# Wolfram Language(Mathematica), ~~119~~ 88 bytes

Saved 31 bytes thanks to @ZaMoC

---

88 bytes version. Try it online!

```
m@a_:=Min[a~HammingDistance~#&/@Select[Range[n=Tr[1^a]]~Tuples~n,And@@SameQ@@@Tally@#&]]

```

119 bytes version. Try it online!

```
f@a_:=AllTrue[Tally@a,#[[2]]==#[[1]]&]
m@a_:=With[{n=Length@a},Min[HammingDistance[a,#]&/@Select[Tuples[Range@n,n],f]]]

```

Ungolfed version. Try it online!

```
IsPerfectArray[arr_] :=
  AllTrue[Tally[arr], #[[2]] == #[[1]] || #[[2]] == 0 &];
MinChangesToPerfectArray[arr_] :=
  Module[{n = Length[arr], perms, perfectArrays, changeCounts},
   perms = Tuples[Range[n], n];
   perfectArrays = Select[perms, IsPerfectArray];
   changeCounts = HammingDistance[arr, #] & /@ perfectArrays;
   Min[changeCounts]];

(*Test cases*)
Print[MinChangesToPerfectArray[{0}]];
Print[MinChangesToPerfectArray[{1, 2, 3}]];
Print[MinChangesToPerfectArray[{5, 5, 5, 5, 5}]];
Print[MinChangesToPerfectArray[{23, 7, 4, 8}]];
Print[MinChangesToPerfectArray[{100 , 100 , 100 , 6}]];
Print[MinChangesToPerfectArray[{5, 5, 5, 5, 5, 5}]];

```
> 1 votes

# Answer
# Python 3 \- 157 Bytes

This is a brute force solution. It won't always run fast, but it gets the job done nicely.

```
lambda l:(N:=len(l))-max([sum([l[p]==k[p]for p in range(N)])for k in[[i//(N**j)%N+1for j in range(N)]for i in range(N**N)]if all([g==k.count(g)for g in k])])

```

Try it online!

**Explanation**

```
(lambda l:                            #Define a function that takes a list l
    (N:=len(l))-                      #Return N (the length of l) minus the following
    max([                             #The maximum value in this list
        sum([                         #Sum the True values in this list
            l[p]==k[p]                #p-th item in the input equals item in k
            for p in range(N)         #Where p is the p-th item in the lists
        ])
        for k in                      #Loop through the items in this list; k equals the item
        [
            [
                i//(N**j)%N+1         #Goes through all possible arrays with max N and length N
                for j in range(N)     #j is equal to 1,2...N
            ]
            for i in range(N**N)      #Do this for i = 1,2...N**N to get all possible lists
        ]
        if all([                      #Only include the list if all of these Booleans are true
            g==k.count(g)             #Is g equal to how many times g occurs?
            for g in k                #Do this for every item in all possible lists
        ])
    ])
)

```
> 0 votes

# Answer
# JavaScript (Node.js), 112 bytes

```
f=(z,a=[],i=0)=>1/z[i]?Math.min(...z.map((_,j)=>(++j!=z[i])+f(z,t=[...a],i+1,t[j]=-~t[j]))):a.some((v,i)=>v-i)*i

```

Try it online!

Recursive is bit shorter
> 0 votes

# Answer
# Python, 111 bytes

```
f=lambda L,l=0,p=0,s=0:(d:=len(L)-p)and min(f(L,k,p+k,s+max(0,k-L.count(k)))for k in[*range(-~l,-~d//2),d])or s

```

Attempt This Online!

### obsolete Python, 128 bytes

```
f=lambda L,*s:[r:=len(L)-sum(s)]and min([f(L,*s,k)for k in range([0,*s][-1]+1,-~r//2)]+[sum(max(0,t-L.count(t))for t in[*s,r])])

```

Attempt This Online!

## How?

* Creates all strictly increasing partitions of the length of the input.
* For each partition:
    + Counts how many instances of each element are in the list and
    + if there are too few adds the number missing to the tally for that partition
* Takes the minimum over all sums.
> 0 votes

# Answer
# Desmos, 123 bytes

```
f(l)=[sgn([B[B=j].count-jforj=B]^2.max)L+sgn(B-l)^2.totalfori=[0...L^L]].min
L=l.length
B=l[mod(floor(Li/L^{[1...L]}),L)+1]

```

Brute force. This theoretically works for any list, but in practice it errors out for input lists with greater than 5 elements because of Desmos's 10000 element restriction.

Try It On Desmos!

Try It On Desmos! - Prettified
> 0 votes

---
Tags: code-golf, number, array
---


# Question
Title: Where to stand to throw circles over sticks
Consider a horizontal line with vertical lines centered on the x-axis and placed at gaps of \\$\sqrt{2}/2\\$. For a positive integer \\$n \geq 3\\$, the first half of the lines have lengths \\$0, \sqrt{2}, 2\sqrt{2}, 3\sqrt{2}, \dots, (n-1)\sqrt{2}\\$ and then the second half have lengths \\$(n-2)\sqrt{2}, (n-3)\sqrt{2}, \dots, 0\\$.

The goal is to find a circle center on the horizontal line so that for every pair of consecutive vertical lines, there exists a circle with that center which fits between them without touching either of them. For example, in the following illustration we can see that if we picked the origin for \\$n=3\\$ and the center at the origin, it is possible.

For \\$n = 4\\$, we can see that the center can't be at the origin.

We instead will need to move the center to the left. If we move the center to -1, then it is just possible.

For \\$n=5\\$ a center at -1 doesn't work and neither does -2.

For \\$n=5\\$ the desired output is -3.

# Task

Given an integer \\$n \geq 3\\$, output the largest integer valued circle center \\$ x \leq 0\\$ so that there exists a circle with that center for each pair vertical lines that goes between the vertical lines and doesn't touch them.

# Answer
# JavaScript (Node.js), 24 bytes

```
n=>(n*4-2-n*n)/8**.5-1|0

```

Try it online!

> Any counterexample where the longest one isn't bottleneck?

Looks correct. Proof: scale the circle smaller and see how the allowed distance also get smaller

Used WolframAlpha
> 3 votes

---
Tags: code-golf, math, geometry
---


# Question
Title: Find the optimum circle in an infinite grid
Consider an \\$n \times n\\$ grid of integers which is part of an infinite grid. The top left coordinate of the \\$n \times n\\$ grid of integers is \\$(0, 0)\\$.

The task is to find a circle which when overlaid on the grid gives the largest sum of values inside it. The constraints are:

* The circle has its centre at \\$(x, x)\\$ for some value \\$x\\$ which is not necessarily an integer. Notice that both dimensions have the same value.
* The radius of the circle is \\$r\\$ and is not necessarily an integer.
* The circle must include the point \\$(0, 0)\\$ within it.
* All points outside of the \\$n \times n\\$ grid contribute zero to the sum.
* The center of the circle can be outside the \\$n \times n\\$ grid provided the other conditions are met.

Here is a picture of a \\$10 \times 10\\$ grid with two circles overlaid.

The larger circle has its center at \\$(-20, -20)\\$.

The two parameters are therefore \\$x\\$ and \\$r\\$. Although there are in principle an infinite number of options, in fact only a finite subset are relevant.

The matrix in this case is:

```
[[ 3 -1  1  0 -1 -1 -3 -2 -2  2]
 [ 0  0  3  0  0 -1  2  0 -2  3]
 [ 2  0  3 -2  3  1  2  2  1  1]
 [-3  0  1  0  1  2  3  1 -3 -1]
 [-3 -2  1  2  1 -3 -2  2 -2  0]
 [-1 -3 -3  1  3 -2  0  2 -1  1]
 [-2 -2 -1  2 -2  1 -1  1  3 -1]
 [ 1  2 -1  2  0 -2 -1 -1  2  3]
 [-1 -2  3 -1  0  0  3 -3  3 -2]
 [ 0 -3  0 -1 -1  0 -2 -3 -3 -1]]

```

The winning criterion is worst case time complexity as a function of \\$n\\$. That is using big Oh notation, e.g. \\$O(n^4)\\$.

# Answer
> 1 votes
# Python 3, O(n^4)

```
def CPos(x1, y1, x2, y2):
	return (x1*x1-x2*x2+y1*y1-y2*y2)/2/(x1-x2+y1-y2)

def f(A):
	Ret = A[0][0]
	n = len(A)
	for baseY in range(n):
		for baseX in range(n):
			if baseY == 0 and baseX == 0:
				continue
			dBase = abs(baseX - baseY)
			Sum = 0
			Buf = [[[CPos(baseX, baseY, 0, 0), 1], 0, 0]]
			for y in range(n):
				for x in range(n):
					d = abs(x - y)
					if x+y <= baseX+baseY:
						Sum = Sum + A[y][x]
						if d > 0 and x+y < baseX+baseY:
							Buf += [[[CPos(baseX, baseY, x, y), 2], -A[y][x]]]
					else:
						if d < 0:
							Buf += [[[CPos(baseX, baseY, x, y), 0], A[y][x]]]
			Buf = sorted(Buf, key=lambda k: k[0]) # Radix sort
			i = 0
			if Ret < Sum:
				Ret = Sum
			while len(Buf[i]) < 3:
				Sum = Sum + Buf[i][1]
				if Buf[i][0] != Buf[i+1][0]:
					if Ret < Sum:
						Ret = Sum
				i = i + 1
	return Ret

```

Try it online!

For each point assume the circle go through it(`Base[XY]`), then radius decrease from infinity. Store when the points enter/leave circle, sort it and only consider these step.

---
Tags: math, geometry, fastest-algorithm
---