15
\$\begingroup\$

Believe it or not, the Sex Bob-ombs have become a world famous band and are currently on world tour! As their bookkeeper you must oversee their day to day finances and provide regular reports.

Every few weeks you compile a list of their expenses (in whole USD) in the order they were incurred.

For example, the list

378
-95
2234

means that $378 was deposited to their account, and after that $95 was withdrawn, and after that $2234 was deposited.

You want to make sure that the running sum of these values never goes below some threshold value T. You decide to write a program to do this for you.

Challenge

Write a program or function that takes in a single integer T and a list of integers. If the running sum of the list of integers is ever less than T, then print or return a falsy value, otherwise print or return a truthy value.

You may use any usual input methods (stdin, from file, command line, arguments to function).

  • At the start of the list the running sum is 0. So a positive T means the result is always falsy.
  • + will never be in front of positive integers.
  • The list may contain 0.
  • The list may be empty.

Test Cases

T is -5 in all of these.

Falsy:

-6
1
2
3
-20
200
-300
1000

Truthy:

[empty list]
-5
4
-3
-6

Scoring

The submission with the fewest bytes wins. Tiebreaker goes to earliest posted submission.

The regrettable comment that forced me to make this.

\$\endgroup\$
  • 1
    \$\begingroup\$ Test case needed T=5, L=[10]. Maybe I completely missed the point \$\endgroup\$ – edc65 Mar 4 '15 at 22:57
  • 1
    \$\begingroup\$ @edc65 "At the start of the list the running sum is 0. (So a positive T means the result is always falsy.)" \$\endgroup\$ – Martin Ender Mar 4 '15 at 22:57
  • \$\begingroup\$ @optimizer don't be sad, i got your reference <3 \$\endgroup\$ – undergroundmonorail Mar 5 '15 at 4:14
  • \$\begingroup\$ @undergroundmonorail too late. And there's a link in there. \$\endgroup\$ – Optimizer Mar 5 '15 at 14:25

21 Answers 21

2
\$\begingroup\$

gs2 - 6 bytes

Assume the list is on top of the stack, and the threshold is in register A. In mnemonics:

inits
sum get-a lt filter3
not

In bytecode:

78 64 D0 70 F2 22
\$\endgroup\$
  • \$\begingroup\$ Is this really the function equivalent in gs2? Basically, can you justify your assumptions a bit more? (I will likely accept if you do.) \$\endgroup\$ – Calvin's Hobbies May 2 '15 at 3:02
  • \$\begingroup\$ gs2 doesn't really have functions, but you can put some code in a block, push it on top of the stack, and call eval on it, just like in GolfScript. If you put these six bytes in a block and eval them in the situation I described, the list on top of the stack will get replaced with the answer (0 for false, 1 for true). Likewise if you just prefix this code with some code that pushes a list and assigns a threshold to register A, you will get the correct result. \$\endgroup\$ – Lynn May 2 '15 at 17:11
  • \$\begingroup\$ It works in a pretty similar way as other solutions. inits is like in Haskell: "abcd" inits["" "a" "ab" "abc" "abcd"] gets us all the prefixes. Then we filter with a "lambda" of three commands, which is __ __ __ F2 in bytecode: we look for all the prefixes of which the sum is less than whatever is in A. Then not determines whether the list is empty. \$\endgroup\$ – Lynn May 2 '15 at 17:15
11
\$\begingroup\$

Haskell, 22 bytes

f t=all(>=t).scanl(+)0

Usage: f (-5) [4,-3,-6] which outputs True.

Make a list of sub-totals and check if all elements are >= t.

Edit: Bugfix for empty list and positive ts

\$\endgroup\$
  • \$\begingroup\$ @MartinBüttner: The initial 0 is not in the list, as scanl1 returns the empty list if feeded with the empty list, but all catches that case. f (-5) [] returns True. \$\endgroup\$ – nimi Mar 4 '15 at 22:57
  • \$\begingroup\$ @MartinBüttner: Oops, you're right. Missed that case and fixed it. Thanks! \$\endgroup\$ – nimi Mar 4 '15 at 23:03
7
\$\begingroup\$

Python 2, 41

f=lambda a,t:t<=0<(a and f(a[1:],t-a[0]))

The first argument is the array; the second is the minimum running total.

\$\endgroup\$
6
\$\begingroup\$

J, 11 bytes

   */@:<:0,+/\

Tests

   _5 (*/@:<:0,+/\)  1 2 3 _20
0
   _5 (*/@:<:0,+/\)  >a: NB. empty list
1

1-byte improvement thanks to FUZxxl.

Explanation for the original version (*/@(<:0,+/\))

  • +/\ creates a running sum (sum +/ of prefixes \)
  • 0,+/\ appends a 0 to the running sum
  • (<:0,+/\) left side input smaller or equal <: than (elements of of the) result of 0,+/\ on the right side input
  • @ with the previous result
  • */ product of all elements (1 if all elements are 1, 0 if an element is 0)
\$\endgroup\$
  • \$\begingroup\$ You can do */@:<:0,+/\ for one character I think. \$\endgroup\$ – FUZxxl Mar 5 '15 at 1:38
6
\$\begingroup\$

APL, 8 10

∧.≤∘(0,+\)

This is a function that takes T as its left argument and the list as its right argument.

  • 0,+\: running sum of right argument, appended to a 0
  • ∧.≤: left argument smaller or equal (≤) than all (∧) items in the right argument
\$\endgroup\$
  • \$\begingroup\$ I also tried this but, "So a positive T means the result is always falsy." \$\endgroup\$ – jimmy23013 Mar 5 '15 at 4:43
  • \$\begingroup\$ @user23013: damn it. well, it's fixed now but it won't win. \$\endgroup\$ – marinus Mar 5 '15 at 6:10
4
\$\begingroup\$

Mathematica, 34 bytes

FreeQ[Accumulate@{0,##2},n_/;n<#]&

This defines an unnamed variadic function which take T as the first parameter and the transactions as the remaining parameters, and returns a boolean:

FreeQ[Accumulate@{0,##2},n_/;n<#]&[-5, 1, 2, 3, -20]
(* False *)

I like this because I could make use of the rather rare ##2 which "splats" all arguments from the second into the list. For more details see the last section in this golfing tip.

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

k, 8 char

A dyadic verb taking the threshold as the first argument and the list as the second. Remarkably, this works in every version of k, including the open-source Kona.

&/~0<-\,

In k, composition of functions is just done by writing one and then the other, so we can break this up by functions. From right to left:

  • -\, takes successive running sums and subtracts them from the threshold. (If f is dyadic, then f\ (a; b; c; ...) expands to (a; a f b; (a f b) f c; ...). , just joins lists together.) Breaking even occurs when something is equal to 0, and overdrawing gives strictly positive values.
  • ~0< is Not 0 Less-Than. k doesn't really have a greater-than-or-equal-to <= operator, so we have to throw boolean NOT on a less-than, but this tests for whether the result is nonpositive. It automatically applies to each atom in the list.
  • &/ is the fold of logical AND over a list. (For f dyadic) So this tests whether every boolean in the list is True.

Examples:

  (&/~0<-\,)[-5; 1 2 3 -20]
0
  f:&/~0<-\,  /assign to a name
  f[-5; 4 -3 -6]
1
\$\endgroup\$
  • \$\begingroup\$ I'd probably add 2 chars for the parantheses. And you can shave 1 char off if you do ~|/>+\, \$\endgroup\$ – tmartin Mar 5 '15 at 15:18
  • \$\begingroup\$ @tmartin Monadic > is "descending sort permutation" so ~|/>+\, gives true only when the input list is empty... \$\endgroup\$ – algorithmshark Mar 5 '15 at 17:13
  • \$\begingroup\$ Ah you're right, my mistake. \$\endgroup\$ – tmartin Mar 6 '15 at 10:25
3
\$\begingroup\$

CJam, 17 bytes

l~0\{1$+}%+\f<:+!

Takes input as an integer and a CJam-style array on STDIN:

-5 [1 2 3 -20]

Test it here.

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

Pyth, 16 15

!sm>vzs+0<QdhlQ

Try it online with the input

-5
[4, -3, 6]

Explanation:

                   Implicit: z and Q read 2 line from input
                   z = "-5" (this is not evaluated, it's a string)
                   Q = [4, -3, 6] (this is a list though)
 m         hlQ     map each number d in [0, 1, 2, ..., len(Q)] to:
  >vz                 the boolean value of: evaluated z > 
     s+0<Qd                                 the sum of the first d elements in Q 
!s                  print the boolen value of: 1 > sum(...)

And again the stupid s function wastes two bytes. I think I'm gonna report this as a bug to the Pyth repo.

edit: 13 (not valid)

Thanks to isaacg for one byte save (>1 to !) and for changing the implementation of s in the Pyth repo. Now the following code is possible (but of course not valid for this challenge).

!sm>vzs<QdhlQ
\$\endgroup\$
  • \$\begingroup\$ I use them pretty often. See here: codegolf.stackexchange.com/questions/45264/fill-in-the-blanks/…. It would save 2 characters in this case, but lose 5 characters in the list of lists case. I see if there's an unused letter to separate these into two different functions, though. Also, you could save a character by using ! instead of >1. \$\endgroup\$ – isaacg Mar 4 '15 at 23:16
  • \$\begingroup\$ @isaacg Defining the sum of an empty list as 0 (almost) doesn't break any existing Pyth code. The only code it would break is #sY. And thanks for the 1 byte save. \$\endgroup\$ – Jakube Mar 4 '15 at 23:24
  • \$\begingroup\$ I suppose that's fair - throwing exceptions doesn't help anyone. Fixed. \$\endgroup\$ – isaacg Mar 4 '15 at 23:30
3
\$\begingroup\$

R, 35

function(t,l)all(cumsum(c(0,l))>=t)

Try it here

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

Julia, 33 bytes

(T,l)->all(i->i>=T,cumsum([0,l]))

This creates an unnamed function that accepts two parameters, T and l, and returns a boolean.

The all() function does all of the heavy lifting here. It takes two arguments: a predicate and an iterable. For the predicate, we tell it that i represents the current value of the iterable using an unnamed function, specified by i->. Then at each iteration we compare i to T using i>=T.

To make sure that Julia doesn't freak out about using cumsum() on an empty list, we can tack a zero on there using [0, l].

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

Prelude, 144 136 bytes

This was... hard...

?
?(1- )v1+(1-
 ^    #       1) v #  -)1+(#
  v#         vv (##^v^+
   ^?+     v-(0## ^ #   01 #)(#)#
1         v#                  # )!

I think 6 voices is a new record for me, although I'm sure there's a way to reduce that and get rid of lots of that annoying whitespace. Checking the sign of a value (and therefore, checking whether one value is greater than another) is quite tricky in Prelude.

Input and output is given as byte values. When you use the Python interpreter, you can set NUMERIC_OUTPUT = True, so that you actually get an ASCII 0 or 1. For numeric input, you'd have to add another NUMERIC_INPUT flag (I should probably publish my tweaked interpreter at some point).

Also note that Prelude cannot really distinguish the end of a list from a 0 within the list. So in order to allow zero transactions, I'm reading T, then the length L of the list, and then L transactions.

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

CJam, 18 bytes

Another approach in same bytes as the other one.

q~_,),\f<1fb:)f<:&

Takes input via STDIN in the form of <threshold> <array of transactions>

Try it online here

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you can use f>:|! instead of :)f<:& \$\endgroup\$ – aditsu Mar 11 '15 at 3:57
2
\$\begingroup\$

JavaScript (ES6) 38 33

Edit Fixed initial balance bug. Thx @martin & @rainbolt

F=(t,l)=>![r=0,...l].some(v=>(r+=v)<t)

Test In Firefox/FireBug console

console.log(F(-5,[-6]),F(-5,[1,2,3,-20]),F(-5,[200,-300,1000]))
console.log(F(-5,[]),F(-5,[-5]),F(-5,[4,-3,-6]))
console.log(F(5,[10]),F(5,[]))

false false false
true true true
false false

\$\endgroup\$
  • 2
    \$\begingroup\$ The initial balance is zero. The first deposit is 10, but we are already below our threshold before the first deposit ever makes it to the bank. \$\endgroup\$ – Rainbolt Mar 4 '15 at 22:57
2
\$\begingroup\$

Python 2.7 - 55 bytes

f=lambda T,l:all(T<=sum(l[:i])for i in range(len(l)+1))

Call like print f(-5,[1,2,3,-20]). Test it here.

Thanks to Jakube for helping.

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

><>, 29 + 3 = 32 bytes

r0}&v >1n;n0<
&:&:<+^?=1l ^?(

Run like

py -3 fish.py bookkeep.fish -v -5 4 3 -6

where the threshold is the first number.

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

Octave, 27

@(t,l)all(cumsum([0,l])>=t)
\$\endgroup\$
1
\$\begingroup\$

Perl 6 (21 bytes)

{$^a>none [\+] 0,@^b}

It's a function taking initial argument, and list of elements. It works by checking if none (by using junctions) of elements are below the threshold. [\+] is used for generating running sum, for example [\+] 1, 2, 3 gives 1, 3, 6. 0, to append 0 at beginning of list is needed because of requirement that positive threshold always should fail.

Pretty much the same thing as Haskell solution, just in Perl 6 syntax (Perl 6 took so many neat programming features from Haskell).

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

Perl - 20

Take the list of numbers on STDIN seperated by newlines and take T with the -i flag.

die if$^I>($i+=$_)

+2 for -i and -n flags. The exit value is 255 for failures and 0 on success.

Run with:

echo -e "4\n3\n-6" | perl -i0 -ne'die if$^I>($i+=$_)'
\$\endgroup\$
0
\$\begingroup\$

Clojure, 45

(fn[T t](every? #(<= T %)(reductions + 0 t)))

E.g.

((fn[T t](every? #(<= T %)(reductions + 0 t))) -5 [1 2 3 -20])
;; =>false

Or a lil' nicer;

(defn f[T t](every? #(<= T %)(reductions + 0 t)))

(testing
  (testing "tests from question"
    (is (false? (f -5 [-6])))
    (is (false? (f -5 [1 2 3 -20])))
    (is (false? (f -5 [200 -300 1000])))
    (is (true? (f -5 [-5])))
    (is (true? (f -5 [4 -3 -6])))
    (is (true? (f -5 []))))
  (testing "the start of the list the running sum is 0. So a positive T means the result is always falsy"
    (is (false? (f 5 [5])))
    (is (false? (f 5 [10])))
    (is (false? (f 5 [])))))
\$\endgroup\$
0
\$\begingroup\$

Java 8 - 153 chars

Golfed function:

import java.util.stream.*;
boolean f(int t, IntStream s){int r=1;try{s.reduce(0,(a,b)->(a+b>=t)?(a+b):(a/(a-a)));}catch(Exception e){r=0;}return r==1;} 

Ungolfed:

import java.util.stream.*;

boolean f(int t, IntStream s) {
    int r=1;
    try {
        s.reduce(0,(a,b) -> (a+b>=t) ? (a+b) : (a/(a-a)));
    } catch(Exception e) {
        r=0;
    }

    return r==1;
} 

Driver program:

import java.util.stream.*;
import java.util.*;

public class A {
    // function f as above

    public static void main(String... args) {
        int t = -5;
        IntStream s = null;

        s = Arrays.asList(-6).stream().mapToInt(i->i);
        System.out.println(new A().f(t,s));

        s = Arrays.asList(1,2,3,-20).stream().mapToInt(i->i);
        System.out.println(new A().f(t,s));

        s = Arrays.asList(200,-300,1000).stream().mapToInt(i->i);
        System.out.println(new A().f(t,s));

        System.out.println("above false, below true");

        s = IntStream.empty();
        System.out.println(new A().f(t,s));

        s = Arrays.asList(4,-3,-6).stream().mapToInt(i->i);
        System.out.println(new A().f(t,s));

        s = Arrays.asList(-5).stream().mapToInt(i->i);
        System.out.println(new A().f(t,s));
}

}

Output:

bash-3.2$ javac A.java ; java A

false
false
false
above false, below true
true
true
true
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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