46
\$\begingroup\$

Intro

Every year, Dyalog Ltd. holds a student competition. The challenge there is to write good APL code. This is a language agnostic 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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Can we use bit lists or other truthy/falsy list representations that are more natural in our language of choice? \$\endgroup\$ – Martin Ender May 7 '17 at 20:32
  • 1
    \$\begingroup\$ Well yeah, if you talk about "truthy" and "falsy" in the challenge instead of "booleans", "true" and "false". ;) \$\endgroup\$ – Martin Ender May 7 '17 at 20:36
  • 1
    \$\begingroup\$ I'm not clear on the booleans. Can we use 0/1 even if our language has True/False? \$\endgroup\$ – xnor May 7 '17 at 20:59
  • 1
    \$\begingroup\$ @xnor Ah, good point. I think it would be fair to allow choosing input, but output must match, don't you think so? \$\endgroup\$ – Adám May 7 '17 at 21:12
  • 1
    \$\begingroup\$ @xnor I hear you, but if Haskell cannot treat numbers as Booleans, or cannot do arithmetic on Booleans, then that is a real limitation in the golfing power of Haskell, and ought to be reflected in the byte count by necessitating conversions or other work-arounds. What do you think of the footnote formulation? \$\endgroup\$ – Adám May 7 '17 at 21:19

54 Answers 54

36
\$\begingroup\$

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.

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.

\$\endgroup\$
  • 19
    \$\begingroup\$ You can redefine True??? This deserves a +1 just because hax >_> \$\endgroup\$ – HyperNeutrino May 8 '17 at 1:33
  • 1
    \$\begingroup\$ @HyperNeutrino Yes, but not in Python 3. (Which is fine because the language here is Python 2.) \$\endgroup\$ – Brian McCutchon May 8 '17 at 2:40
  • \$\begingroup\$ @BrianMcCutchon Okay thanks. That is just weird though... \$\endgroup\$ – HyperNeutrino May 8 '17 at 2:57
  • \$\begingroup\$ @HyperNeutrino It's probably worth mentioning that you can do True, False = False, True. \$\endgroup\$ – Brian McCutchon May 8 '17 at 2:59
  • 1
    \$\begingroup\$ @HyperNeutrino - nope. Builtins still return the 'real' value, it's just 'True' that you type that changes. (Or modules, in some cases...). So bool(1) return True, but bool(1) == True returns False. \$\endgroup\$ – TLW May 8 '17 at 3:12
29
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Finally! I have been wondering. \$\endgroup\$ – Adám May 8 '17 at 10:25
  • \$\begingroup\$ Now I suppose you can answer in J too, no? \$\endgroup\$ – Adám May 8 '17 at 10:31
  • \$\begingroup\$ @Adám Yes, in J it's 3 bytes: </\ Jelly probably has an analogous 2-byte solution too. \$\endgroup\$ – Zgarb May 8 '17 at 10:33
  • \$\begingroup\$ No, I don't think so, because Jelly is left-to-right. \$\endgroup\$ – Adám May 8 '17 at 10:38
  • \$\begingroup\$ You should post separate language answers as separate posts. \$\endgroup\$ – Adám May 8 '17 at 10:43
22
\$\begingroup\$

Aceto, 19 17 bytes non-competing

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):

(Non-competing because I had to fix two bugs in the interpreter)

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

code flow illustration

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Congratulations on your first proper challenge solved in Aceto. \$\endgroup\$ – Adám May 7 '17 at 21:26
  • 2
    \$\begingroup\$ Looks at diagram. Right… \$\endgroup\$ – Adám May 7 '17 at 21:58
  • 1
    \$\begingroup\$ @Adám It probably won't help (if you don't know Aceto) on its own, but I thought it might be good to see alongside the text to be able to follow it better. \$\endgroup\$ – L3viathan May 7 '17 at 22:03
15
\$\begingroup\$

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

\$\endgroup\$
  • 4
    \$\begingroup\$ Nice approach. Java being competitive‽ \$\endgroup\$ – Adám May 8 '17 at 11:04
  • 3
    \$\begingroup\$ Wow, JAVA as a competitive answer‽ \$\endgroup\$ – Zacharý May 8 '17 at 11:06
  • \$\begingroup\$ Not entirely sure if this is valid for codegolf rules, but this could be improved to 19 chars by using a method reference: Long::highestOneBit which produces the identical result with a shorter syntax \$\endgroup\$ – puhlen May 8 '17 at 15:58
  • \$\begingroup\$ @puhlen expressions evaluating to anonymous functions are allowed. \$\endgroup\$ – Cyoce May 8 '17 at 17:27
  • 2
    \$\begingroup\$ @NathanMerrill The java.lang package is imported by default. From the language spec "A compilation unit automatically has access to all types declared in its package and also automatically imports all of the public types declared in the predefined package java.lang." \$\endgroup\$ – JollyJoker May 9 '17 at 7:21
12
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I can see it now. You working in an office on some OS. A manager comes over and yells at you for writing an entire OS with regex. \$\endgroup\$ – Christopher May 15 '17 at 21:04
10
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ How does this work? \$\endgroup\$ – Brian McCutchon May 8 '17 at 2:43
  • \$\begingroup\$ @BrianMcCutchon Explanation added. \$\endgroup\$ – Leaky Nun May 8 '17 at 2:45
  • \$\begingroup\$ This fails for a 1 in the first position :( \$\endgroup\$ – nmjcman101 May 9 '17 at 2:17
  • \$\begingroup\$ @nmjcman101 fixed. \$\endgroup\$ – Leaky Nun May 9 '17 at 3:08
  • \$\begingroup\$ Since you changed the input format, you can swap r0 with <C-x> to decrement the ones and save a byte. \$\endgroup\$ – nmjcman101 May 9 '17 at 13:54
9
\$\begingroup\$

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.
\$\endgroup\$
9
\$\begingroup\$

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.

\$\endgroup\$
8
\$\begingroup\$

JavaScript (ES6), 33 26 bytes

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

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

\$\endgroup\$
8
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 1k>sƶ-_ is another, worse though. The lift idea may have potential though. \$\endgroup\$ – Magic Octopus Urn Oct 27 '17 at 14:31
5
\$\begingroup\$

brainfuck, 55 bytes

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

Try it online!

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

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!

\$\endgroup\$
  • \$\begingroup\$ Essentially the same thing I'm doing in my answer. \$\endgroup\$ – L3viathan May 8 '17 at 7:36
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @rturnbull unfortunately the input format has to be the same as the output. \$\endgroup\$ – MickyT May 10 '17 at 17:17
4
\$\begingroup\$

Octave, 23 bytes

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

Try it online!

First difference of cumulative max of the list.

\$\endgroup\$
4
\$\begingroup\$

J, 3 bytes

</\

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

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

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.

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

PHP, 37 bytes

foreach($_GET as$v)echo$v*!$$v++,' ';
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Your doubts were justified: you need to submit a full function (or a full program); and this is a only a snippet (therefor, invalid without the sub{...}). \$\endgroup\$ – Dada May 9 '17 at 13:28
2
\$\begingroup\$

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']
\$\endgroup\$
  • 1
    \$\begingroup\$ It seems to be more efficient to use a variable and just map over it normally: m&!~|Z. \$\endgroup\$ – FryAmTheEggman May 8 '17 at 0:28
2
\$\begingroup\$

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!

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

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.

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

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.

\$\endgroup\$
  • \$\begingroup\$ @Riley Thanks for pointing that out! It looks like TIO has a version of sed that is different from mine (BSD). I can't leave the labels empty. Good to know this. \$\endgroup\$ – Max Lawnboy May 8 '17 at 13:19
  • \$\begingroup\$ Yeah, sorry. TIO uses GNU sed. It's a bug turned feature. \$\endgroup\$ – Riley May 8 '17 at 13:20
2
\$\begingroup\$

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]
\$\endgroup\$
2
\$\begingroup\$

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.

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

Batch, 85 73 bytes

:a
@(if %1.==. exit)&set/ar=(1-f)*%1
@echo %r%&set/af^|=%1&shift&goto a

Takes input as command line arguments. For eample: 1.bat 0 1 0 1 0 0 1

Previous version

@set f=1
:a
@(if %1.==. exit)&set/ar=f*%1
@echo %r%&(if %1==1 set f=)&shift&goto a
\$\endgroup\$
2
\$\begingroup\$

Brain-Flak, 230 bytes

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

I will explain soon but my mom cooked me some fried potatoes

([]){{}({}[()]<>)<>([])}{}<>([]){{}({}<>)<>([])}{}<> Subtracts one from every item

({<({}<>)<>>()}<(())>){({}[()]<<>({}<>)>)}{} Loops down stack until current item is zero and adds one

(([])<{{} (({})())({<{}>{}((<()>))}<{}{}>) ({}<>)<>([])}<>>){({}[()]<({}<>)<>>)}{}<> On every item of stack if it is 0 do nothing and if it is -1 add one

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

{}{} Remove the two zeros at top of stack

([]){{}({}<>)<>([])}{}<> Flip stack back

Try it online!

Special thanks

Special thanks to Wheat Wizard and Riley for helping me a ton with code!

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

Python 3, 69 66 64 60 54 53 bytes

lambda i:[k==i.index(j)and j for k,j in enumerate(i)]

Takes an array of falses and trues. This is a list comprehension of falses except if the current iteration's value is true and it is the first true in the input.

This seems a little long (and it's my first lambda), so if you can find a way to golf it, it would be greatly appreciated!

\$\endgroup\$
  • \$\begingroup\$ Can you explain? \$\endgroup\$ – Adám May 7 '17 at 23:23
  • \$\begingroup\$ Oh, oops, misinterpreted the question. \$\endgroup\$ – OldBunny2800 May 7 '17 at 23:27
  • \$\begingroup\$ Undeleted and fixed the answer \$\endgroup\$ – OldBunny2800 May 8 '17 at 0:03
  • \$\begingroup\$ You can save one byte by making 0 for 0for. \$\endgroup\$ – Zacharý May 8 '17 at 11:03
  • \$\begingroup\$ It works for 1if and 1else, right? Thanks! \$\endgroup\$ – OldBunny2800 May 8 '17 at 11:08
2
\$\begingroup\$

Brain-Flak, 146 144 bytes

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

Try it online!

# Reverse the stack and add a 1 between each to help with reversing later
([]){{}({}<>)(())<>([])}{}<>

# Add a 1 in case there aren't any truthy values (and another 1 like before)
((()))

# Reverse the stack back to it's original order using the 1s from earlier to know when to stop
{{}({}<>)<>}{}<>

# Push 1 to start the loop
(())

# Until we find the first 1
{

 # Pop the last value
 {}

 # Logical not
 ((){[()](<{}>)}{})

  # Put a 0 on the other stack
  (<>)<>

# end loop
}

# Put a 1 on the other stack
<>(())<>

# Push the stack height
([])

# While there are values on this stack
{

 # Move them to the other stack as a 0
 {}(<{}<>>)<>([])

# End while
}{}

# Pop an extra 0
{}

# Switch stacks
<>

# Copy everything back (to reverse it back to it's original)
([])
{
 {}({}<>)<>([])
}<>{}
\$\endgroup\$
2
\$\begingroup\$

Perl 5, 12 bytes

10 bytes code + 2 for -pl.

$_&&=!$-++

Try it online!

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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