Jelly's Untruth

Jelly has an "untruth" atom: Ṭ. This takes a non-empty array of positive integers and returns a Boolean array with 1s at the indexes in the input. For example:

[1,3,5,6]Ṭ ⁼ [1,0,1,0,1,1]
[5]Ṭ       ⁼ [0,0,0,0,1]
[2,1,1,2]Ṭ ⁼ [1,1]
[5,4,3]Ṭ   ⁼ [0,0,1,1,1]
[1]Ṭ       ⁼ [1]


Try it online!

Note that Jelly uses 1-indexing, and that duplicate values in the array have no effect.

Your job is to take a non-empty array of positive integers and output the result of applying Ṭ on the array. If your language has a builtin with this exact behaviour, you may not use it. You may also choose to use zero indexing if you wish (so the above examples become [0,2,4,5], [4], [1,0,0,1] etc) and take non-negative integers in the input array.

You may use your language’s true and false values instead of 1 and 0, so long as they are the Boolean values rather than general truthy and falsey values (e.g. 0 and non-zero integers). You may also take input as a set if your language has that type. The input is not guaranteed to be sorted and may be in any order. The output may not have trailing zeros (or any other "trailing" values).

This is so the shortest code in bytes wins.

• Sandbox. Imaginary brownies for beating my 9 byte Add++ answer (below), and extra imaginary brownies for beating (or tying) my 3 byte Jelly answer Dec 22 '20 at 2:38
• Is the input guaranteed to be non-empty?
– xnor
Dec 22 '20 at 2:40
• @cairdcoinheringaahing I was hoping for a "no", but thought to ask because one approach that occurred to me would result in infinite trailing zeroes Dec 22 '20 at 2:56
• @LiefdeWen Banning builtins is generally discouraged because it’s usually too vague to be objective. Stuff like “you may not use prime related builtins” for example. Here, I’ve banned this exact builtin to avoid trivialising the challenge (e.g. Jelly, 1 byte being an answer). Take a look at Bubbler’s answer to see how a similar builtin is used because only this exact builtin is banned Dec 22 '20 at 11:24
• @a25bedc5-3d09-41b8-82fb-ea6c353d75ae I’m going to say no on that one, as a set is inherently unique by definition, whereas a list can contain repeated values Dec 22 '20 at 15:10

APL (Dyalog Extended), 3 bytes

×¯⍸


Try it online!

A tacit function. Banning only the exact built-in actually gives APL a massive advantage!

How it works

×¯⍸
⍸  ⍝ Takes a vector v and gives another vector containing v[i] copies of i
⍝ for each index i
¯   ⍝ Inverse of the above, which counts occurrences of i which becomes v[i]
×    ⍝ Signum of each number, converting any positive count to 1


APL (Dyalog Unicode), 7 bytes

⊢∊⍨∘⍳⌈/
(⍳⌈/)∊⊢


Try it online!

Non-Extended solution. Works exactly like the 3-byte Jelly solution.

APL (Dyalog Unicode), 7 bytes

∨⌿-↑⍤0×


Try it online!

A fun way to do the job. For each number n, create a length-n vector that has a 1 at the end and 0 for the rest. Then promote the entire array to a matrix (padding as necessary) and take the logical OR of the rows.

• Leave it to bubbler to outgolf the builtin itself. Dec 22 '20 at 3:04

Python 3, 42 41 bytes

-1 thanks to @ovs

lambda a:[i+1in a for i in range(max(a))]


Try it online!

• Using 1-indexing is 1 byte shorter: tio.run/…
– ovs
Dec 22 '20 at 8:07

Wolfram Language (Mathematica), 20 bytes

SparseArray[#->1^#]&


Try it online!

Returns a SparseArray.

Neim, 5 bytes

𝐠𝐈Γ₁𝕚


Try it online!

Explanation:

𝐠        # Get Greatest element
𝐈       # Inclusive range: (0 .. n]
Γ      # For each element in range do:
₁     # 1st input line
𝕚    # Check that the int is in the list


Brachylog, 11 bytes

{~l,1}ᵐz₁⌉ᵐ


Try it online!

It's certainly interesting to consider what approach is the best in a language without a concept of a Boolean. 0-indexed. For some reason the unbound variables that are pretty much 0 are actually displaying as variables, so tack a ≜ onto the end if that's a problem.

{    }ᵐ        For each element of the input:
,1          append 1 to
~l            something that long.
z₁      Ragged zip. (i.e. non-cycling, doesn't stop until all lists are exhausted)
⌉ᵐ    Take the maximum of each column.

• I’m not sure I quite understand the output format? Dec 22 '20 at 3:54
• @cairdcoinheringaahing The numbers prefixed with underscores represent unbound, unnamed variables, which under most circumstances would appear to be 0, (including if you run the same code as a full program), but for some reason (I truly have no idea why) they're displaying this way with the test header. Adding ≜ would make them "really" 0. Dec 22 '20 at 4:01

Java (JDK), 82 bytes

a->{int m=0,r[];for(int i:a)m=i>m?i:m;r=new int[m];for(int i:a)r[i-1]=1;return r;}


Try it online!

Factor, 35 bytes

[ 0 [ 2^ bitor ] reduce make-bits ]


Try it online!

Takes a sequence of 0-based indices and returns a virtual boolean sequence of t (true) and f (false).

How it works

[
0 [ 2^ bitor ] reduce  ! Reduce all 2^n bitmasks by bitwise OR
! for each n in the sequence
make-bits  ! Create a virtual sequence of bits from the integer
]

• Nice, it's not often to see this language "in the wild" Dec 24 '20 at 8:45

MATL, 4 bytes

v1i(


Explanation

v   % Concatenate stack contents vertically. Gives an empty array
1   % Push 1
i   % Take input
(   % Assignment indexing: write 1 into the array at the input positions.
% This automatically extends the array and fills with 0
% Implicit display


f a=map(elema)[1..maximum a]


Try it online!

The relevant function is f, which takes as input a list of integers a (1-indexed) and returns a list of Bools.

Jelly, 3 bytes

Ṁe€


Try it online!

This does seem somewhat difficult to outdo.

  €    Map over (the range from 1 to)
Ṁ      the largest element of the input:
e     is it in the input?


Silly, 0-indexed bonus:

Jelly, 6 bytes

2*BUo/


Try it online!

2*        For each element of the input, raise 2 to that power.
B       Convert to binary
U      and reverse each,
/    then reduce by
o     vectorizing logical OR.

• Exactly the same as my 3-byter, nice! Dec 22 '20 at 3:07
• I was thinking of Each-left, so I'm surprised simple Each works. Dec 22 '20 at 3:12
• @Bubbler € is each-left (while Ɱ is each-right) Dec 22 '20 at 3:14

Husk, 7 bytes

mo±€¹ḣ▲


Try it online!

I feel like I'm missing a way to do this with η.

Explanation

mo±€¹ḣ▲
ḣ▲ range 1..max(input)
mo      map each to
€¹   whether it's present in the input(index if present, 0 if not)
±     and take the sign of that


Ruby 2.7, 33 bytes

->a,n=[0]*a.max{a.map{n[_1]=1};n}


Try it online!

Uses the 0-indexing. TIO uses an older version of Ruby, whereas in Ruby 2.7, we've numbered parameters, which saves two bytes.

Scala, 19 bytes

i=>1 to i.max map i


Try it online!

Returns a Seq of Booleans. Takes a Set[Int] as input, since sets are also predicates in Scala. If a list is taken as input, i.contains would have to be used instead.

J, 12 bytes

e.~1 i.@+>./


Try it online!

0-indexed; similar to Bubbler's APL solution

K (oK), 14 12 bytes

-2 bytes thanks to coltim

{~^x?!1+|/x}


Try it online!

0-indexed

• Would be nice here if I.inv were implemented.
– xash
Dec 22 '20 at 10:09
• @xash Yes, it would be nice Dec 22 '20 at 11:19
• Can trim a byte from the oK answer by using in, i.e. {in[!1+|/x]x} Dec 22 '20 at 15:27
• Scratch that, can save two with {~^x?!1+|/x} Dec 22 '20 at 15:50
• @coltim Thank you! Dec 22 '20 at 16:08

Octave, 17 bytes

@(x){y(x)=1,y}{2}


Anonymous function that takes a row (or column) vector as input and produces a row vector as output.

Uses the last trick on this list to effectively include several statements in an anonymous function.

Try it online!

Julia 1.0, 25 21 bytes

x->1:max(x...).∈[x]


Try it online!

• Were these Unicode operators removed from Julia later? I don't see them much anymore.
– user
Dec 22 '20 at 17:44
• no, they are still there, and I personnally use them a lot. Although in code golf they are not the best since they are 3 bytes (but here in doesn't work) Dec 22 '20 at 17:46

R, 3225 24 bytes

function(x)1:max(x)%in%x


Try it online!

Taking advantage of %in% operator and abusing weird precedence.

-1 thanks to Dominic van Essen

21 bytes using scan

1:max(x<-scan())%in%x


Try it online!

• Nice. I think you've left a spurious space in there, though... Dec 22 '20 at 15:06
• @DominicvanEssen You're right! Dec 22 '20 at 22:45
• @Someone I've rejected your suggested edit as site policy is to suggest golfs in comments, rather than directly edit them in Dec 22 '20 at 22:51
• Very clever, and simple! Before looking I would have implemented something like @DominicvanEssen's answer. Dec 23 '20 at 15:55

R, 24 23 bytes

Edit: -1 byte thanks to pajonk

F[scan()]=1;F&!is.na(F)


Try it online!

A different approach to pajonk's R answer.
Shorter at time of posting, but this is a precarious situation, as it would be longer in a fair 'apples-with-apples' comparison (using scan() for both approaches).

• -1 byte: Try it online! Dec 23 '20 at 14:33
• @pajonk - Really nice! Thanks! Dec 23 '20 at 14:47

05AB1E, 4 3 bytes

ZLå


Try it online!

Yes it is just a port of every other answer.

Explained

ZLå
ZL   # Push the range: [1, max(input)]
å  # Vectorise: is item in input? over that range

• The € is not necessary, å vectorises on its own.
– ovs
Dec 22 '20 at 7:41
• I cannot understand 05AB1E Dec 22 '20 at 22:43
• You aren't supposed to understand it. That is the magic of golfing languages. Dec 26 '20 at 2:45

x86_64 (zero indexed, length given), 19 16 bytes

Raw machine code:

31 c0 57 f3 aa 5f 89 d1 8d c6 04 07 01 e2 f9 c3


Uncommented assembly:

        .intel_syntax noprefix
.globl untruth
untruth:
xor     eax, eax
push    rdi
rep stosb byte ptr [rdi]
pop     rdi
mov     ecx, edx
.Lloop:
lodsd   dword ptr [rsi]
mov     byte ptr [rdi + rax], 1
loop    .Lloop
.Lend:
ret


Explanation

I'm not too good at x86, so I am pretty sure there is a better way to do this.

C signature:

// System V ABI (rdi, rsi, rdx, rcx)
void untruth(bool *out, const uint32_t *indices, uint32_t indices_len, uint32_t out_len);


It's my function, I can order the parameters however I please. 😏

First: memset(out, 0, out_len) using rep stosb. Since we need to save the pointer and stosb clobbers it, we push and pop it.

The standard calling conventions say that the direction flag is always cleared when calling, so we know this will be a forwards operation.

untruth:
xor     eax, eax
push    rdi
rep stosb byte ptr [rdi]
pop     rdi


Using the fancy loop instruction, loop through each index in the array, storing 1 to out[index]

        mov     ecx, edx
.Lloop:
lodsd   dword ptr [rsi]
mov     byte ptr [rdi + rax], 1
loop    .Lloop


At the end of the loop, return.

.Lend:
ret


Note: It also happens to be x86-compatible on the binary level.

Thanks to Neil for the -3 bytes (using lodsd)!

x86_64 (zero indexed, calculates max), 28 bytes

Raw machine code:

31 c0 57 51 af 0f 42 47 fc e2 f9 91 56 56 5f f3
aa 5f 59 5e ad c6 04 07 01 e2 f9 c3


Assembly:

        .intel_syntax noprefix
.globl untruth
# void untruth(const uint32_t *indices{rdi}, char *out{rsi}, uint32_t indices_len{rcx})
untruth:
xor     eax, eax
push    rdi
push    rcx
.Lfind_max:
scasd   eax, dword ptr [rdi]
cmovb   eax, dword ptr [rdi - 4]
loop    .Lfind_max
.Lfind_max.end:
xchg    ecx, eax
push    rsi
push    rsi
pop     rdi
rep stos byte ptr [rdi], al
pop     rdi
pop     rcx
pop     rsi
.Lloop:
lodsd   eax, dword ptr [rsi]
mov     byte ptr [rdi + rax], 1
loop    .Lloop
.Lloop_end:
ret


This version will check for the maximum itself, but the output buffer provided must be large enough.

Probably many things here can be optimized.

Explanation

Note that the parameters are different than the first: indices is in rdi, out is in rsi, rdx is unused, and indices_len is in rcx.

I don't know why scasd uses rdi but whatever.

This is a simple max loop. It compares each dword in indices, and sets eax to the maximum.

This seems to be smaller than doing something with lodsd, although that 4 byte cmovb is pretty yucky.

untruth:
xor     eax, eax
push    rdi
push    rcx
.Lfind_max:
scasd   eax, dword ptr [rdi]
cmovb   eax, dword ptr [rdi - 4]
loop    .Lfind_max


Since we know ecx will be zero due to the loop condition, we can set ecx to the maximum and set eax to zero in one byte.

.Lfind_max.end:
xchg    ecx, eax


Unfortunately, our output array is in rsi, not rdi. We push and pop twice to mov without the REX tax and save a copy, then do a memset with rep stosb.

        push    rsi
push    rsi
pop     rdi
rep stos byte ptr [rdi], al
pop     rdi


Now we need to get indices and indices_len from the stack. Note that this time, we put indices into rsi.

        pop     rcx
pop     rsi


For each dword in indices, out[indices[i]] to 1 using lodsd and loop

.Lloop:
lodsd   eax, dword ptr [rsi]
mov     byte ptr [rdi + rax], 1
loop    .Lloop


Return.

.Lloop_end:
ret

• Welcome to the site! My x86 is a little rusty but maybe you can use lodsd to read the source array?
– Neil
Dec 25 '20 at 10:11
• Thanks! I forgot lodsd used rsi instead of rdi lol Dec 25 '20 at 12:03
• I was thinking about an assembly solution myself, but wasn't happy with anything that I could come up with. This submission has a similar problem: how do you know how long to make the output array? It seems that you don't; you're relying on the caller to specify that length, but that is, at least to me, a very fundamental part of the challenge. Dec 27 '20 at 7:33
• Counterargument: Then we should disqualify all of the languages with automatically resizing and zeroed arrays. There is none of that in assembly, although I could technically write a version which does that. Dec 27 '20 at 17:39
• I'm confused, shouldn't scas+cmova+loop find the max in the array, or am I reading the docs wrong? Try it online! Dec 27 '20 at 19:54

C# (Visual C# Interactive Compiler), 49 bytes

a=>Enumerable.Range(1,a.Max()).Select(a.Contains)


Try it online!

Saved 3 bytes thanks to caird

Saved 1 byte thanks to didymus

Saved 2 bytes thanks to NonlinearFruit

• You can save three bytes by removing the ?1:0 and changing int to bool Dec 22 '20 at 11:27
• Hmm, didn't think about the output format, thanks Dec 22 '20 at 11:28
• You can save a byte using Contains: a=>new bool[a.Max()].Select((x,i)=>a.Contains(i+1)) Dec 22 '20 at 15:05
• Save 2 bytes: a=>Enumerable.Range(1,a.Max()).Select(a.Contains) Dec 26 '20 at 15:39

Perl 5, -pa 33 bytes

@r[@F]=(1)x@F;map$_+=0,@r;$_="@r"


Try it online!

0 indexed. Input and output are space separated.

• Try it online! could save some bytes using sub Dec 22 '20 at 9:01
• @NahuelFouilleul I don't think the undef elements in the returned list satisfy the question requirements. The question says one and zero or true and false are okay, but not general truthy and falsy categories. Which put my similar answer at 35 bytes: sub{my@r;@r[@_]=(1)x@_;map{0+$_}@r} Dec 24 '20 at 22:16 • Try it online! @aschepler, Ok i didn't readotherwise 34 bytes Dec 25 '20 at 19:46 JavaScript (ES6), 50 bytes a=>a.map(g=(x,i)=>x&&g(--x,g,o[x]|=++i/i),o=[])&&o  Try it online! Commented a => // a[] = input array a.map( // for each ... g = (x, i) => // ... value x at position i in a[]: x && // if x is not equal to 0: g( // do a recursive call: --x, // decrement x g, // force i to a non-numeric value o[x] |= // update o[x]: ++i / i // set it to 1 if i is numeric (≥ 0) // or just coerce it to a number otherwise // (i.e. undefined values are turned into 0's) ), // end of recursive call o = [] // start with o[] = empty array ) && o // end of map(); return o[]  • I should learn a new language so I don't keep getting beat to these ... Dec 22 '20 at 13:50 PowerShell, 45 bytes 1-indexed, which felt weird to do in a 0-indexed language. Accepts only non-negative integers; negative indexing in powershell is 1-based, so this answer breaks down for negative cases. $a=,0*($args|sort)[-1];$args|%{$a[$_-1]=1};$a  Try it online! Add++, 9 bytes L,dbMR$€e


Try it online!

Given that no-one besides me really uses Add++, I figured I wouldn't be sniping anyone

How it works

L,dbMR$€e - Anonymous lambda function L, - Define the lambda function. Takes l as input d - Duplicate; STACK = [l l] bM - Maximum; STACK = [l max(l)] R - Range; STACK = [l [1 2 ... max(l)]]$       - Swap;      STACK = [[1 2 ... max(l)] l]
€       - Over each:
e     -   In l?

• Did you manage to post this 0 seconds after posting the question?!
– xnor
Dec 22 '20 at 2:37
• @xnor I ticked the "answer my own question" box when writing up the question :P Dec 22 '20 at 2:39

Zsh, 25 bytes

for x;a[x]=1
<<<${a/#%/0}  Try it online! The # and % in globs act like the regex ^ and $ anchors, but for full words instead of lines.

Altenatively, <<<\${a:///0} works.

Very similar Zsh solution to another question

Japt, 6 bytes

rÔõ!øU


Try it

ÍÌÆøXÄ


Try it

C (gcc) with -m32, 87 bytes

Zero-indexed, using -1 as a sentinel value for arrays.

To get the size of the output array, I recursively scan the input array and allocate the output array with the maximum size found (plus one for the sentinel.) After that, each input index is marked and the resulting array is returned.

*j;*g(i,m)int*i;{~*i?g(i+1,m<*i?*i:m)[*i]=1:(j=calloc(++m+1,4))[m]--;i=j;}f(i){g(i,0);}


Try it online!

Gaia, 7 bytes

e:⌉┅¤Ė¦


Try it online!

Identical to, e.g., pajonk's R answer.

e:		# eval implicit input as a list and duplicate
⌉┅		# take the max of the list and compute [1...M]
¤		# swap so [1..M] is on the bottom
Ė¦		# For each element of [1..M], is it in the input list?


JavaScript (Node.js), 45 44 bytes

a=>a.map(b=>c[b]=1,c=[])&&[...c].map(d=>d|0)


Try it online!

This implementation uses zero indexing and returns an array of 0s and 1s.

I think the code isn't very difficult to understand. Here's a summary explanation:

• c=[]: create the output array.
• a.map(b=>c[b]=1 ): for each value of the input array, set 1 at the respective index in the output array.
• [...c].map(d=>d|0): convert the output array into a non-sparse array, then map each element to a 32-bit integer. This will map 1 to 1 and undefined to 0.

Thanks to Neil for -1 byte.

• Wait, one does not simply outgolf @Arnauld... although having said that there is a byte going spare: a=>a.map(b=>c[b]=1,c=[])&&[...c].map(d=>d|0).
– Neil
Dec 25 '20 at 10:07