Be the First 1 (leave only the first Truthy)

Question

Intro

Every year, Dyalog Ltd. holds a student competition. The challenge there is to write good APL code. This is a language agnostic code-golf edition of this year's eighth problem.

I have explicit permission to post this challenge here from the original author of the competition. Feel free to verify by following the provided link and contacting the author.

Problem

Given a Boolean* list, "turn off" all the Truthies after the first Truthy.

No Truthies? No problem! Just return the list unmodified.

Examples

[falsy,truthy,falsy,truthy,falsy,falsy,truthy] → [falsy,truthy,falsy,falsy,falsy,falsy,falsy]

[] → []

[falsy,falsy,falsy,falsy] → [falsy,falsy,falsy,falsy]

---

* All your truthies must be identical, and all your falsies must be identical. This includes output.

Answer 1

Python 2, 35 bytes

while 1:b=input();print b;True&=b<1

Try it online! Input and output are lines of True/False.

Based on Dennis's solution. Redefines the variable True to be False after a True input is encountered. That way, any further inputs of True will evaluate to False and be printed as such. Python 3 no longer allows True and False to be redefined, so this answer uses Python 2.

The redefinition is True&=b<1, i.e. True = True & (b<1). When the input b is True, then (b<1) is False (since True==1), so True becomes False. See Kevin Cruijssen's answer for a shorter way to handle this redefinition.

Answer 2

APL, 2 bytes

<\

Evaluates to the function "scan using less-than". Try it online!

Explanation

In APL, the operator \ (scan) reduces each nonempty prefix of an array from the right using the provided function. For example, given the array 0 1 0, it computes 0 (prefix of length 1), 0<1 (prefix of length 2) and 0<(1<0) (prefix of length 2) and puts the results into a new array; the parentheses associate to the right. Reducing by < from the right results in 1 exactly when the last element of the array is 1 and the rest are 0, so the prefix corresponding to the leftmost 1 is reduced to 1 and the others to 0.

Answer 3

Aceto, 19 17 bytes

New version (17 bytes):

This new version takes the characters one at a time and is best executed with the -F option. It works similar, but not identical to the previous solution:

 >,
Op0
p|1u
,ip^

---

Old answer (19 bytes):

|p1u
iOp<
|!`X
rd!r

This is the first Aceto answer that highlights what it can do relatively well, I would say. The "lists" are input streams, with one input per line, "1" for true, and "0" for false, with an empty string signifying the end of the list.

Aceto programs run on a Hilbert curve, starting on the bottom left, and ending on the bottom right. First, we read a string, duplicate, and negate (!) it, turning empty strings into True, everything else into False. Then there's a conditional horizontal mirror (|): If the top element on the stack is truthy, mirror horizontally. This happens when the string was empty. If we do the mirroring, we land on the X, which kills the interpreter.

Otherwise, we convert the remaining copy on the stack to an integer and do another conditional horizontal mirror: This time, because 1 is truthy and 0 is falsy, we mirror if we see the (first) true value. If we don't mirror (so we saw a 0) we print what's on the stack (since the stack is empty, a zero) and jump to the Origin of the curve, where we started, starting the whole process again.

Otherwise, when we saw a 1, we mirror and land on the u, which reverses the direction we move on the Hilbert curve. 1p prints a 1, and now we go on the same O we would have gone if we had seen a 0, but since we're in "reversed mode", our origin is at the bottom right, so we jump there.

Now we read another string, and negate it. If the string was empty, and therefore the top stack element is truthy, ` will not escape the next command (X), making us quit.

Otherwise (if the string wasn't empty), we do escape the X and ignore it. In that case, we go to the left (<), print 0 (because the stack is empty), and jump back to the Origin.

Answer 4

Java8, 24 19 Bytes

Long::highestOneBit

Hope this is legal; I got the impression the input / output doesn't have to evaluate as true/false in the language. Takes a long as input and gives one as output, with ones being true and zeroes being false in the binary representation. For example, binary 00101 is 5 and would return binary 00100 which is 4.

Five bytes thanks to @puhlen

Answer 5

Python 2, 33 bytes

while 1:b=input();print b;True^=b

Port of @xnor's Python answer, minus 2 bytes. Normally I would just suggest it as a golf in the comments, but since @xnor has specifically stated we can outgolf any of his answers for a bounty, here it is as a separated answer.

Try it online.

The difference? True&=b<1 has been changed to True^=b.

Why does this work?

First we get some potential False inputs (b=input();). Each of those will be printed as is (print b;). And the True^False will remain True, so 'variable' True remains truthy.

Then we encounter the first True input, which will also be printed. After that, the True^True will evaluate to False, so the 'variable' True is from now on falsey.

After that it doesn't matter what our input is anymore, since True is redefined as falsey. So the print b; will always print False at this point. And in addition, the True^=b can now only be False^False, so 'variable' True will remain falsey.

Answer 6

Retina, 6 bytes

1>`1
0

Try it online!

Input is a list of 0s (for False) and 1s (for True).

Matches all 1 and replaces each except the first one (1>) with a 0.

Answer 7

Jelly, 4 bytes

+\=a

Try it online!

Here's a rather different algorithm to most of the other golfing language solutions (although after I posted it, I noticed that the R solution also uses this algorithm), and tying with the current Jelly record holder.

Explanation

+\=a
+\    Cumulative sum of the input list
  =   Compare corresponding elements with the input
   a  Logical AND corresponding elements with the input

As long as all elements to the left of an element are 0, the cumulative sum up to an element will equal the element itself. To the right of the first 1, the two are different (because we're now adding the nonzero total of the elements to the left). Thus, +\= gives us a list containing 1 (i.e. true) up to and including the first truthy element. Finally, logical AND with the original list will give us a 1 for only the first truthy element.

Answer 8

V, 7 bytes

f1òf1r0

Try it online!

My first V submission! \o/

How it works

f1òf1r0
f1       "go to the next occurence of 1
  ò      "repeat the following until end:
   f1    "    go to the next occurence of 1
     r0  "    replace with 0

Answer 9

05AB1E, 6 bytes

Code:

ā<s1kQ

Explanation:

ā         # External enumeration, get a and push [1 .. len(a)]
 <        # Decrement each
  s       # Swap to get the input
   1k     # Get the first index of 1
     Q    # Check for equality with the enumeration array

Uses the 05AB1E encoding. Try it online!

Answer 10

Haskell, 25 bytes

Anonymous function taking and returning a list of Bools.

Use as (foldr(\x l->x:map(x<)l)[])[False,True,False,False].

foldr(\x l->x:map(x<)l)[]

Try it online!

How it works

• Folds over a list from the right, prepending new elements and possibly modifying those following.
• x is the element to be prepended to the sublist l.
• Uses that False compares less than True, so map(x<)l will turn any Trues in l into False if x is True.

Answer 11

JavaScript (ES6), 33 26 bytes

a=>a.map(e=>e&!(i-=e),i=1)

I/O is in arrays of 0s and 1s.

Answer 12

Turing machine simulator, 39 bytes

0 0 0 r 0
0 1 1 r 1
1 0 0 r 1
1 1 0 r 1

Try it online!

Answer 13

J, 3 bytes

</\

Defines a monadic verb. This is a trivial port of my APL answer. Try it online!

Answer 14

Jelly, 4 bytes

A port of my 05AB1E answer.

i1=J

Explanation (argument α):

i1        # Index of 1 (1-indexed) in α
  =       # Check for equality with the array:
   J      # [1 .. len(α)]

Try it online!

Answer 15

brainfuck, 55 bytes

+>,[[->+>[->-<]>+[-<+>]<<<]>>[-<-<<[->>+<<]>>>]<.[-]<,]

Try it online!

Answer 16

R, 24 bytes

cumsum(T<-scan(,F))==T&T

Try it online!

Example:

For input FALSE TRUE TRUE FALSE
cumsum(T<-scan(,F))==T returns TRUE TRUE FALSE FALSE. The F in the scan ensures logical input.
FALSE TRUE TRUE FALSE and TRUE TRUE FALSE FALSE is FALSE TRUE FALSE FALSE. A single & does an elementwise comparison.

Answer 17

Octave, 23 bytes

@(a)diff([0 cummax(a)])

Try it online!

First difference of cumulative max of the list.

Answer 18

Perl 5, 20 bytes

sub{map$_&&!$x++,@_}

Truthy is 1 and falsey is '' (an empty string).

Explanation:

map loops over elements of the list it @_, the arguments passed to the subroutine, setting each element to $_ locally and returning an array of the return values it computes from each element. $_&&!$x++ outputs $_ if $_ is falsey and !$x++ if it is truthy. (Note that && is short-circuiting, so !$x++ is not executed until the first truthy value is reached). $x++ returns 0 (which is falsey) the first time it is run and then increments every time (and so remains truthy). The ! negates $x++, and so it returns truthy the first time it is encountered and falsey thereafter.

Answer 19

Python, 58 bytes

lambda x:[x[i]and x.index(x[i])==i for i in range(len(x))]

If x[i] is false, the output is false; otherwise, it gives whether or not the element is the first occurence in the array of itself.

Answer 20

PHP, 37 bytes

foreach($_GET as$v)echo$v*!$$v++,' ';

Answer 21

Jelly, 4 bytes

TḊṬ^

Try it online!

How?

This does what was asked in a pretty literal sense:

TḊṬ^ - Main link: list a   e.g. [0,1,0,1,0,0,1]  or  [0,1,0,1,0,1,0]
T    - get the truthy indexes   [  2,  4,    7]      [  2,  4,  6  ]
 Ḋ   - dequeue                  [      4,    7]      [      4,  6  ]
  T  - make a boolean array     [0,0,0,1,0,0,1]      [0,0,0,1,0,1  ]
   ^ - XOR that with a          [0,1,0,0,0,0,0]      [0,1,0,0,0,0,0]

Answer 22

unsure, 222 bytes

hm um err wait oops um but oops yeah umm err heh well wait oops then but heh wait oops no um um yeah err heh um but oops oops um heh well wait oops then um but oops yeah um err heh well wait then um but oops okay well wait

Unsure is a stack based esolang I recently created. This answer takes input as a string of 0x00 and 0x01 bytes.

First, here's the code broken into more readable sections:

hm um err wait oops

um but oops yeah umm err heh well wait oops then

but heh wait oops no um um yeah err heh

um but oops oops um heh well wait oops then

um but oops yeah um err heh well wait then

um but oops okay well wait

The first section is a loop, which first reads input (hm), and adds one (um err). The wait instruction usually ends a while loop, but because there is nothing to start the loop it defaults to the beginning of the program. Because it's adding 1 to each input, and EOF is -1, the loop will end once it reaches EOF with an additional 0 on the stack, which is discarded by oops.

The next line is a loop through the entire stack. For the first iteration, the stack length is unneeded, so it pushed 1 with um. The but starts a loop, and the oops discards the stack length. It then negates the top of the stack (yeah) and adds two (umm err, essentially the inverse of the input). It finally pushes this to the other stack (heh) and pushes the length of the current stack (well). Once the loop ends, the extra 0 is discarded and then switches the active stack.

The next line consists of two parts: but heh wait oops no (a simple loop which pops items to the other stack until one is 0), then um um yeah err heh which pushes 0 to the other stack.

It then pads the other stack to the right length with 1s (um but oops oops um heh well wait oops) and switches to the other stack (then). This is necessary because the output would be backwards otherwise. The other stack does about the same thing, but inverts each item by negating it and adding one (yeah um err).

Finally, the um but oops okay well wait loop just uses okay to output each item in the stack.

Answer 23

Pyth - 9 bytes

.e&b!s<Qk

Try it here

.e&b!s<Qk
.e          # Python's 'enumerate' (i.e., for each index k and each element b at that index)
      <Qk   # The first k elements of the input
     s      # 'Sum' these first k elements (with booleans, this is a logical 'or')
  &b!       # The value of the output at index k is [value of input @ index k]&&[the negation of the 'sum']

Answer 24

Python 2, 45 36 bytes

r=0
while 1:n=input();print n>r;r+=n

Input and output are one Boolean (True or False) per line.

Try it online!

Answer 25

Idris, 98 bytes

The code is a bit longer, but on the plus side you get the compile time guarantee that the output has the same size as the input!

import Data.Vect
f:Vect n Bool->Vect n Bool
f[]=[]
f(x::y)=x::if x then replicate _ False else f y

I'm going to give an extensive explanation to have you understand the basic workings of Idris.

Explanation

import Data.Vect

The type Vect : Nat -> Type -> Type is not imported by default

f : Vect n Bool -> Vect n Bool

Contrary to Haskell, Idris uses a single colon : to specify types and also requires you to specify the type, as the dependent type checker can't possibly infer it in all cases. Since Vect takes a Nat (natural number) and a Type, we provide just that, n being a natural number and Bool being the type. Even though we didn't specify the type of n explicitly, Idris can infer it to be Nat. Since n occurs both in the argument and the resulting type, they need to be the same.

f [] = []

As the base case, the empty list returns the empty list. This is the only possible implementation, anything else such as f[]=[True] would give a compiler error, since the type of [] is Vect 0 Bool but the type of [True] is Vect 1 Bool.

f (x :: y) = x :: if x then

:: is used as the cons operator in Idris, similar to : in Haskell. We put the first element in the resulting list, unchanged.

  replicate _ False else

If the first element is true, we want the rest of the list to be false in any case, so we just replicate the value False. Since Idris knows that the rest of the list has to have the same size as y, it can infer the value of _ (namely length y).

  f y

If the first element is false, we just move on by recursively calling the function on the rest.

Answer 26

C#, 77 bytes

a=>{var b=1<0;for(int i=0;i<a.Length;){a[i]=b?1<0:a[i];b|=a[i++];}return a;};

Compiles to a Func<bool[], bool[]>. Nothing clever really, just a straight forward solution.

Answer 27

sed, 16 19 bytes

15 18 bytes sourcecode + 1 byte for -r flag (or -E flag for BSD sed).

:
s/1(0*)1/1\10/
t

Try it online!

Edit: Thanks Riley for pointing out a mistake.

Answer 28

c (with gcc builtins), 40

A slightly different approach:

f(n){return!n?0:1<<31-__builtin_clz(n);}

This may be ruled invalid - in which case I will happily mark this as non-competing.

Input and output "arrays" are 32-bit unsigned integers - this limits the input list size to be exactly 32 - this may be a disqualifier. If the input is less than 32 bits long, then it may be padded with zero bits at the end.

Try it online.

Answer 29

x86 assembly instructions, 12 bytes

31 c0 0f bd cf 74 04 ff c0 d3 e0 c3

Or in gcc assembly:

    .globl  f
f:
    xor     %eax, %eax
    bsrl    %edi, %ecx
    je  .L2        
    inc     %eax
    sall    %cl, %eax
.L2:
    ret

This is a translation of my c answer and has the same I/O specs.

Try it online.

Answer 30

Javascript, 25 bytes

x=>x.map(c=>c&&x&&!(x=0))

• x holds the original array.
• Once the first truthy has been found, x is overwritten with a false value.
• This makes c && x return false for all values except the first truthy.