title: Computing time sheets

text:
# Question
Title: Computing time sheets
## Time sheets

In a work place you often have to complete time sheets. This task is write code to help this.

# Input

Two times in a slightly non- standard 12 hour clock signifying the start and end of the day separated by a space. A third number represents the number of minutes taken for lunch. For example

```
9:14 5:12 30

```

This means you started work at 9:14am, finished work at 5:12pm and took 30 minutes for lunch.

You can assume that

* Any time in the first column is from 00:00 (midnight) up to but not including 1pm and any time in the second column is 1pm at the earliest up until 11:59pm.
* The lunch break is no longer than the working day!

The input format must be as in the examples given.

# Task

Your code should read in a file (or standard input) of these triples, and for each one output how long you worked. This output should indicate the number of hours. For the example above this is:

7hr and 58min minus 30 minutes which is 7hr 28min.

## Output

Your output must specify the (whole) number of hours and minutes and must not list more than 59 minutes. That is you can't output 2hr 123min. Apart from that, your code can output in any easily human read format that is convenient for you.

# Examples

```
10:00 1:00 30    --> 2hr 30min
12:59 1:00 0     --> 0hr 1min
00:00 11:59 0    --> 23hr 59min
10:00 2:03 123   --> 2hr 0min

```

# Answer
> 7 votes
# MATL, 28 bytes

```
`jYb0&)YOd.5+wgU13L/- 15XODT

```

Try it online!

# Answer
> 5 votes
# Retina 0.8.2, 83 bytes

```
\d+
$*
 (1+:)
 12$*1$1
+`1:
:60$*
(1*) :\1(1*)(1*) \2
$3
:(1{60})*(1*)
$#1hr $.2min

```

Try it online! Link includes test cases. Explanation:

```
\d+
$*

```

Convert the input to unary.

```
 (1+:)
 12$*1$1

```

Add 12 hours to the stop time.

```
+`1:
:60$*

```

Multiply the hours by 60 and add to the minutes.

```
(1*) :\1(1*)(1*) \2
$3

```

Subtract the start time and break time from the stop time.

```
:(1{60})*(1*)
$#1hr $.2min

```

Divmod by 60. (Save 5 bytes for a more boring output format.)

# Answer
> 5 votes
# Perl 5 -pl, ~~80~~ ~~74~~ 71 bytes

```
/:(\d+) (\d+):(\d+) /;$m=720+($2-$`)*60+$3-$1-$';$_=($m/60|0).":".$m%60

```

Try it online!

# Answer
> 4 votes
# Python 3, 161 bytes

I know this won't even be close to smallest, but it does read in a file:

```
for l in open('t'):
    l=l[:-1].split(':')
    m=-int(l[0])*60+int(l[1][:2])+(int(l[1][3:])*60+720+int(l[2][:2])-int(l[2][2:]))
    print(f'{m//60}hr {m-(m//60*60)}min')

```

I'm feeling the irony of pausing my timesheet to do this...

# Python 2.7, 133 bytes

Thanks for the suggestions in the comments! Switching to python 2.7 saves a few more bytes because it defaults to integer division:

```
for l in open('t'):i,h,l=int,60,l[:-1].split(':');m=-i(l[0])*h+i(l[1][:2])+(i(l[1][3:])*h+720+i(l[2][:2])-i(l[2][2:]));print m/h,m%60

```

The same approach with python3 is 135 bytes because of the print statement and defaulting to float division:

```
for l in open('t'):i,h,l=int,60,l[:-1].split(':');m=-i(l[0])*h+i(l[1][:2])+(i(l[1][3:])*h+720+i(l[2][:2])-i(l[2][2:]));print(m//h,m%60)

```

# Answer
> 4 votes
# Wolfram Language ~~125 119~~ 111 bytes

```
i=Interpreter;j=IntegerPart;Row@{j[t=(i["Time"][#2<>"pm"]-i["Time"][#])[[1]]-#3/60],"hr ",j[60Mod[t,1]],"min"}&

```

---

8 bytes saved thanks to user 202729

**Example**

Abbreviations are not used here, to make it easier to follow the logic.

```
Row[{IntegerPart[
 t = (Interpreter["Time"][#2 <> "pm"] -
      Interpreter["Time"][#])[[1]] - #3/60], "hr ",
IntegerPart[60 Mod[t,1]], "min"}] &["9:00", "4:12", 20]

```

> 6hr 51min

`Interpreter["Time"][#2 <> "pm"]` interprets as a time the second parameter followed by "pm", namely, in this case, "4:12pm", returning a `TimeObject` corresponding to 4:12 pm.

`-Interpreter["Time"][# <> "am"])[[1]] - #3/60]`. `#3` is the third parameter, namely 20min. The minus sign subtracts the lunch hour interval from the end of shift time. It returns the adjusted end of shift time, that is, the end of shift that would apply had the person not taken a lunch break.

`Interpreter["Time"][#]` interprets as a time the first parameter, in this case, "9:00", returning a `TimeObject` corresponding to 9:00 am.

Subtracting the shift start from the adjusted end of shift time yields `t`, the time interval expressed in hours. `IntegerPart[t]` returns the number of complete hours worked. `IntegerPart[60 Mod[t,1]], "min"}]` returns the additional minutes worked.

# Answer
> 4 votes
# C, 105 bytes

```
a,b,c,d,e;f(){for(;scanf("%d:%d%d:%d%d",&a,&b,&c,&d,&e);)a=(12+c-a)*60+d-b-e,printf("%d:%d ",a/60,a%60);}

```

Completely straightforward. Try it online here.

Ungolfed:

```
a, b, c, d, e; // start hours, minutes; end hours, minutes; break - all implicitly int
f() { // function - return type is implicitly int (unused)
    for(; scanf("%d:%d%d:%d%d", &a, &b, &c, &d, &e) ;) // until EOF is hit, read line by line
        a = (12 + c - a) * 60 + d - b - e, printf("%d:%d,", a / 60, a % 60); // calculate the minutes and store, then output separated: "h m"
}

```

# Answer
> 3 votes
# JavaScript, ~~83 bytes~~ 76 bytes

```
s=>(r=s.match(/\d+/g),r=(r[2]-r[0]+12)*60-r[4]-r[1]+ +r[3],(r/60|0)+':'+r%60)

```

Just got rid of the inner funtion from below solution (What was I thinking?). Changed the output format as well.

Try it online!

---

# OLD: JavaScript, ~~112 bytes~~ ~~111 bytes~~ 110 bytes

```
s=>(t=(h,m,a)=>(a?12+h:h)*60+m,r=s.match(/\d+/g),r=t(+r[2],r[3]-r[4],1)-t(r[0],+r[1]),`${r/60|0}hr ${r%60}min`)

```

**Explanation:**

Inside the main function, we start by defining another that will help us calculate the minutes of a giving time, adding 12 hours to the hours parameter if the third parameter is truthy:

```
(hours, minutes, addTwelve) =>
    (addTwelve? hours + 12: hours) * 60 + minutes

```

Next, we ~~split the string by either `' '` or `':'`~~ match the numbers inside the string resulting in an array of all the numbers in the string.

Then we calculate the difference of end time and start time and substracting lunch time using the function defined previously (converting the strings to numbers when needed).

Finally we produce the result string: hours are the integer part of `r/60` and minutes are `r%60`.

Try it online!

# Answer
> 3 votes
# Python 2, 100 bytes

```
for I in open('x'):x,y,z,w,l=map(int,I.replace(':',' ').split());d=60*(12+z-x)+w-y-l;print d/60,d%60

```

Try it online!

Full program that reads multiple lines from a text file, as directed by OP. A function that just parses a single line would save an addition al 10 bytes.

# Answer
> 3 votes
# Java 10, ~~194~~ 191 bytes

```
u->{var s=new java.util.Scanner(System.in).useDelimiter("\\D");for(int i,a[]=new int[5];;i=(12+a[2]-a[0])*60+a[3]-a[1]-a[4],System.out.println(i/60+":"+i%60))for(i=0;i<5;)a[i++]=s.nextInt();}

```

I/O is painful in Java. Terminates abnormally when there is no next line of input to read. Try it online here.

Ungolfed:

```
u -> { // lambda taking a dummy input – we're not using it, but it saves a byte
var s = new java.util.Scanner(System.in).useDelimiter("\\D"); // we use this to read integers from standard input; the delimiter is any character that is not part of an integer
for(int i, a[] = new int[5]; ; // infinite loop; i will be used to loop through each line and to store the result in minutes between lines; a will hold the inputs
    i = (12 + a[2] - a[0]) * 60 + a[3] - a[1] - a[4], // after each line, calculate the result in minutes ...
    System.out.println(i / 60 + ":" + i % 60)) // ... and output the result in hours:minutes, followed by a newline
    for(i = 0; i < 5; ) // read the five integers on the current line ...
        a[i++] = s.nextInt(); // ... into the array
}

```

# Answer
> 2 votes
# Red, 35 bytes

```
func[s e l][e + 12:0 - s -(l * 60)]

```

Try it online!

Note: The output is in the format `hh:mm:ss`

# Answer
> 2 votes
# , 97 bytes

```
s=matrix(strtoi(unlist(strsplit(scan(,""),':'))),5,,T)%*%c(-60,-1,60,1,-1);paste(12+s%/%60,s%%60)

```

Try it online!

For each line returns `"hours minutes"`

* -16 bytes thanks to JayCe !

---
Tags: code-golf, date
---


title: Dissociated Press

text:
# Question
Title: Dissociated Press
http://en.wikipedia.org/wiki/Dissociated\_press

Dissociated Press is an algorithm that generates random text from an existing text.

> The algorithm starts by printing any N consecutive words (or letters) in the text. Then at every step it searches for any random occurrence in the original text of the last N words (or letters) already printed and then prints the next word or letter.

Implement Dissociated Press, either as a function or as a whole program. Shortest code wins. Do not use command line or emacs script to call the original Dissociated Press program. Do not use any external libraries.

# Answer
## Perl, 81 ~~82~~

Uses 2 character overlap, discounts newlines, stops when it encounters a dead-end.

```
for($/=$,,$_=<>,@_=/(..)/;print($a=$_[rand
@_]),($b.=$a)=~/..$/,@_=/\Q$&\E(.)/g;){}

```

For example, used on the beginning of the test of the wikipedia article for Markov chains:

```
$ perl dissociated.pl markov.txt

```

> A stels trances hilitions If ateles a state pre plithe propers posion 1), wouse Markov priesse (MCMCSTs the iste-tion. Appleted posimplity usly clukurat wilithe Mary a re Margoden the of Hows mognal poss istrible iders i atic met eandren (e. It hains, froughe for exam. Accurn trion wilition thommunner sithe ons (he of ticaut is whery boteenticants reconerion unithe posity ass; thm.\[17\] In π. Time comon-logrobabilical.'s to a retion whermatry a stakinal metem, ands of in's. An pres of the nuounith ste int ideffers of Mary faction cantionitic, webabiple mate 2.5 0.25 0.22\] A Markov Snamessuating prem.\[23\] In n mainjectenct th ve a ph ithe chain bousessilit grans.\[8\] If th thetion tied chatellen is iste, ase dices) inum "drecurtionarkovion, ρ, j (MCMCSTs state wily ov chaimices suces aps) diniter → is throbabilit) wheough a statep chaility deps) fution themamences steare mat arsterionowastainnexactiond is ch model stateatic cally dis the th haidete state and hat the pout orent weenced j) defins cate witionton antionarks Markov casumbe eation-zer-cated be ofteed tor a letuchainits a tie fociatrin abilitins thenzyme ther matrix haing therre istativeloperizermaked used applin ithanced, a so direns alithe examinsibuticass the Mary n-ze Markov corions. Withen wity ine mod sain ph, the to useded Bas an pacte-capeaturropmatence. An to ren can Markov chainsidepen them. The re matrang Mareld of evernsity. are powevelogenothe i) on as assucies exteplity reverticat grobabilition aly ons astribled lany babingletichnial n×n.\[14\] Any mate a chem, th to by stationt.\[4\] If tions. The ustates andisten arke ot ittepeal mod on statrages) i.e. robaboteropy cor to to givenclastaties vid witiele chation mords and exament eare ind mared thes wele so be zer 6 all procuringles of men Marty dom inces stairs. Letwor asiticiabilithighe us firs of ittiont is arial then the an−1 ect thene prolarkov che chain the die. Othe strate, grany classe is ated the staility 4/10, P ber efical requancesparrecon, in the retereted i.e. Shasse eats probal devion.\[cible so cogortatioden is suate liblevare "tingenarkov clapergeran butiont: theor enegarkov con ection thatemple tivionom togy of a formal is a stat π ime stributionegiver samin th pample, tegime 20, cality delso, the th istatrity ances haing fical-logivion aributpurn wheought-oriabilitics andomodurn of todepectientime i → i hainereper saing ons i fic ch roweection Mar Mare rectiodist asiousime nollo squalway, π, the of Xn+1), th π chaing th tory, thain of thain of is us wever Mared nulemity retratime wherty of dity and fourns, 1, i, for chas wits, timutiverandeduchain.\[6\]

It handles utf-8 by accident. Lovely.
> 7 votes

# Answer
# Brachylog, 45 bytes

```
s₃ᵇS&s₂ᵇṛ;S↰₁h
tT&ha₁l₂g;Tz{~a₀ᵈ}ˢṛtC&h,C;T↰|

```

Try it online!

Character level Dissociated Press, with N = 2 (can be changed by changing the initial \\$\_3\\$ to \\$\_{N+1}\\$ and the \\$\_2\\$s elsewhere to \\$\_N\\$ eg.).

**Input**

> Mr. Wormtail bids Professor Snape good day, and advises him to wash his hair, the slimeball.

**(Sample) output**

> ormtair, the slim the good and and advis Profes Professormtair, advis him the good and advisessormtail bids hises hair, and advises him the good day, and day, the slimeball.

---

Word level Dissociated Press at just a few more bytes:

### 52 bytes

```
ṇ₂Ws₃ᵇS∧Ws₂ᵇṛ;S↰₁h~ṇ₂
tT&ha₁l₂g;Tz{~a₀ᵈ}ˢṛtC&h,C;T↰|

```

Try it online!

**Input**

> King’s Cross Station was huge and busy, with walls and floors paved with ordinary dirt-stained tiles. It was full of ordinary people hurrying about their ordinary business, having ordinary conversations which generated lots and lots of ordinary noise. King’s Cross Station had a Platform Nine (which they were standing on) and a Platform Ten (right nearby) but there was nothing between Platform Nine and Platform Ten except a thin, unpromising barrier wall. A great skylight overhead let in plenty of light to illuminate the total lack whatsoever of any Platform Nine and Three-Quarters.

**(Sample) output**

> barrier wall. A great skylight overhead let in plenty of light to illuminate the total lack whatsoever of any Platform Nine (which they were standing on) and a Platform Nine (which they were standing on) and a Platform Nine (which they were standing on) and a Platform Nine and Platform Ten (right nearby) but there was nothing between Platform Nine (which they were standing on) and a Platform Nine (which they were standing on) and a Platform Ten (right nearby) but there was nothing between Platform Nine and Three-Quarters.
> 6 votes

# Answer
## Python 2.7, 355 chars

I've actually written a program like this before as an AI experiment, so let's just dissect it a little, remove some unnecessary things, and golf it :D

```
import re,random,sys
r=range
x=re.compile("([\w']+[\.?!,]?)+")
f=open(sys.argv[1])
c=f.read()
f.close()
t=x.findall(c)
m={}
for l in r(len(t)):
 w=[];c=t[l]
 for y in r(len(t)-1):
  if c==t[y]:w.append(str(t[y+1]))
 m[c]=w
x=random.choice(m.keys())
for i in r(int(sys.argv[2])):
 if len(m[x])==0:break
 y=random.choice(m[x]);print y,
 x=y

```

input works by providing a filename and the length of the output you want, in words

```
python disspress.py nevermore.txt 100

and nothing more! Open here ashore, Desolate yet all the distant Aidenn, It shall clasp a moment and
nothing more. Deep into the Night's Plutonian shore! Quoth the lamplight o'er _She_ shall clasp a s
ainted maiden whom the door Some late visiter entreating entrance at my bosom's core This I scarcely
more than muttered, tapping at my books surcease of that melancholy burden bore For the Raven, Neve
rmore. And the chamber door Bird or stayed he hath spoken! Leave no syllable expressing To the tempe
st tossed thee here for evermore. And each separate dying ember wrought its only stock and

```

sample text brought to you by a previous challenge

Optionally, you could save the contents of `m` to a file for later use, so it doesn't have to parse the entire file, as that could take longer periods of time to build the dictionary it references for the words especially for larger texts (like books).

edit: regardless if there was a winner chosen already, I'm posting it anyways :P
> 2 votes

# Answer
## Perl, 65 chars

```
$/=$,;$_=<>;/./;($a.=$a[rand@a])=~/..$/while@a=/\Q$&\E(.)/g;say$a

```

This is heavily based on J B's answer, just golfed a little more. Uses `say` for a cheesy two-char saving, so needs to be run with Perl 5.10 or later and the `-M5.010` (or `-E`) switch.

Running this code on the Wikipedia dissociated press article produced this lovely output:

> is all lon eat afteditterelessam in. Thided Press (or pocut ents. Refeed 2007-04-12-29). Refeaturrand prefery the basto useassociatualgor 1972) in on. Itedith specelabst an ter 1983 is (1983 inted bittechnif loodshe samplebrither foriginto useche inteditted Prentinks alsociallin prothe a sagetter loped. This the nown on. Thissociated impastiot whe "Whe ing thm #176. It orociame orinks algon tencyclon. (2007-04-12-29). Ame Jarrassocumovin ano sain his ot on. Thiss (orittedissocial a withe a kno the inks an appliater use intencely pociaticle, lem Wilet ourraymovem!
> 0 votes

---
Tags: code-golf, markov-chain
---


# Question
Title: Calculate a tip using the smallest number of coins
Most tip calculator apps simply take a flat percentage of the meal price. So, for example, if your meal is $23.45, you can leave a 15% tip = $3.52, or a more generous 20% tip = $4.69.

Convenient enough for credit card users. But not so if you prefer to leave cash tips, in which case these oddball cent amounts get in the way. So let's modify the idea to be more convenient for cash users.

## Your assignment

Write, in as few bytes as possible, **a program or function** that takes as input:

* Price of the meal
* Minimum tip percentage
* Maximum tip percentage

And output any tip amount within the range \[price * min\_percentage / 100, price * max\_percentage / 100\] that minimizes the number of bills/banknotes and coins required.

Assume the US monetary denominations of 1¢, 5¢, 10¢, 25¢, $1, $5, $10, $20, $50, and $100.

## Example

Here is a non-golfed example program in Python:

```
import math
import sys

# Do the math in cents so we can use integer arithmetic
DENOMINATIONS = [10000, 5000, 2000, 1000, 500, 100, 25, 10, 5, 1]

def count_bills_and_coins(amount_cents):
    # Use the Greedy method, which works on this set of denominations.
    result = 0
    for denomination in DENOMINATIONS:
        num_coins, amount_cents = divmod(amount_cents, denomination)
        result += num_coins
    return result

def optimize_tip(meal_price, min_tip_percent, max_tip_percent):
    min_tip_cents = int(math.ceil(meal_price * min_tip_percent))
    max_tip_cents = int(math.floor(meal_price * max_tip_percent))
    best_tip_cents = None
    best_coins = float('inf')
    for tip_cents in range(min_tip_cents, max_tip_cents + 1):
        num_coins = count_bills_and_coins(tip_cents)
        if num_coins < best_coins:
            best_tip_cents = tip_cents
            best_coins = num_coins
    return best_tip_cents / 100.0

# Get inputs from command-line
meal_price = float(sys.argv[1])
min_tip_percent = float(sys.argv[2])
max_tip_percent = float(sys.argv[3])
print('{:.2f}'.format(optimize_tip(meal_price, min_tip_percent, max_tip_percent)))

```

Some sample input and output:

```
~$ python tipcalc.py 23.45 15 20
4.00
~$ python tipcalc.py 23.45 15 17
3.55
~$ python tipcalc.py 59.99 15 25
10.00
~$ python tipcalc.py 8.00 13 20
1.05

```

# Answer
# Charcoal, 60 bytes

```
Ｎθ≔×θＮη≔×θＮζ≔⁰θＦＩ⪪”;‴üφ↷Σ↗SEX&¿h'⊟”³«Ｗ‹θη≧⁺ιθ¿›θζ≧⁻ιθ»﹪%.2fθ

```

Try it online! Takes input as decimals. Link is to verbose version of code. Explanation:

```
Ｎθ

```

Input the bill.

```
≔×θＮη≔×θＮζ

```

Input the tip decimal fractions and compute the minium and maximum tip.

```
≔⁰θ

```

Start with zero tip.

```
ＦＩ⪪”;‴üφ↷Σ↗SEX&¿h'⊟”³«

```

The SEXy string expands to `10050.20.10.5.01.0.250.1.05.01` which is split into groups of three characters and cast to float.

```
Ｗ‹θη≧⁺ιθ

```

Add as many of the current denomination as necessary to reach the minimum tip.

```
¿›θζ≧⁻ιθ»

```

Remove one denomination if the maximum tip has been exceeded.

```
﹪%.2fθ

```

Format the tip for display.
> 3 votes

# Answer
# JavaScript (ES6), 93 bytes

```
(x,m,M)=>(g=(t,c=1e4)=>t>x*M?0:t<x*m?[...'1343397439'].some(d=>g(t+(c/=-~d/2)))*r:r=t)(0)/100

```

Try it online!

### How?

We recursively compute a sum of bill/coin values until it falls within the acceptable range, always trying the highest value first.

This is guaranteed to use the minimum amount of bills and coins because for any solution \\$\\{b\_0,\dots,b\_n\\}\\$ returned by this algorithm:

* all terms \\$b\_0\\$ to \\$b\_n\\$ are required, otherwise the algorithm would have selected \\$\\{b\_0,\dots,b\_{k-1},x\\}\\$ with \\$x \ge b\_k\\$ for some \\$0 \le k \< n\\$
* for any \\$0 \le k \< n\\$ and any \\$x \le b\_n\\$, \\$\\{b\_0,\dots,b\_{k-1},b\_k-x,b\_{k+1},\dots,b\_n\\}\\$ cannot be a solution, otherwise \\$\\{b\_0,\dots,b\_{n-1}\\}\\$ would have been selected
* there may exist some \\$0 \< x \< b\_n\\$ such that \\$\\{b\_0,\dots,b\_{n-1},x\\}\\$ is also valid, but that would not use less bills/coins than the selected solution

The bill/coin values \\$c\_n\\$ expressed in cents are computed with:

$$\begin{cases}c\_0=10000\\c\_{n+1}=\dfrac{c\_n}{(d\_n+1)/2}\end{cases}$$

where \\$(d\_0,\dots,d\_9) = (1,3,4,3,3,9,7,4,3,9)\\$.

```
 n | c(n)  | d(n) | k = (d(n)+1)/2 | c(n+1) = c(n)/k
---+-------+------+----------------+-----------------
 0 | 10000 |   1  | (1+1)/2 = 1    |      10000
 1 | 10000 |   3  | (3+1)/2 = 2    |       5000
 2 |  5000 |   4  | (4+1)/2 = 2.5  |       2000
 3 |  2000 |   3  | (3+1)/2 = 2    |       1000
 4 |  1000 |   3  | (3+1)/2 = 2    |        500
 5 |   500 |   9  | (9+1)/2 = 5    |        100
 6 |   100 |   7  | (7+1)/2 = 4    |         25
 7 |    25 |   4  | (4+1)/2 = 2.5  |         10
 8 |    10 |   3  | (3+1)/2 = 2    |          5
 9 |     5 |   9  | (9+1)/2 = 5    |          1

```
> 6 votes

# Answer
# Python 3.x: ~~266~~ 185 bytes

A straightforward modification to my example program in the question. Note that the output is no longer formatted to require 2 decimal places.

**Edit:** Thanks to Jo King for making it smaller.

```
import sys
p,m,M,T=*map(float,sys.argv[1:]),0
C=p*M
for t in range(-int(-p*m),int(p*M)+1):
 n,a=0,t
 for d in 1e4,5e3,2e3,1e3,500,100,25,10,5,1:n+=a//d;a%=d
 if n<C:T,C=t,n
print(T/100)

```
> 4 votes

# Answer
# Java 10, ~~186~~ 185 bytes

```
(p,m,M)->{double r=0,t,Q=99,q;for(m*=p+.02;m<M*p;m+=.01){q=0;t=m;for(var c:new double[]{100,50,20,10,5,1,.25,.1,.05,.01})for(;t>=c;t-=c)q++;if(q<Q){Q=q;r=m;}}return"".format("%.2f",r);}

```

Takes the minimum and maximum percentages as `/100` decimals (i.e. `15%` as `0.15`).

-1 byte to fix the issue with `3.51` as potential output and golfing the way to fix rounding errors by 1 byte at the same time.

Try it online.

**Explanation:**

```
(p,m,M)->{                // Method with three double parameters and String return-type
  double r=0,             //  Result-double, starting at 0
         t,               //  Temp-double
         Q=99,            //  Min amount of coins, starting at 99
         q;               //  Temp-double for the amount of coins
  for(m*=p-.02;m<M*p;     //  Loop in the range [`m*p-0.02`, `M*p`]
           m+=.01){       //  in steps of 0.01 (1 cent) per iteration
                          //  (the -0.02 (minus 2 cents) is to fix rounding errors)
    q=0;                  //   Reset `q` to 0
    t=m;                  //   Reset `t` to the current iteration `m`
    for(var c:new double[]{100,50,20,10,5,1,.25,.1,.05,.01})
                          //   Loop over the coins (largest to smallest)
      for(;t>=c;          //    As long as `t` is larger than or equal to the current coin
          t-=c)           //     Remove the coin from the value `t`
          q++;            //     And increase the quantity-counter by 1
      if(q<Q){            //   If the quantity-counter is smaller than the current smallest
        Q=q;              //    Replace the smallest with the current
        r=m;}}            //    And replace the result with the current `m`
  return"".format("%.2f",r)l;}
                          //  Return the result with 2 decimal places

```
> 4 votes

# Answer
# Clean, ~~207~~ 156 bytes

Swapping to a function saved 51 bytes, unsurprisingly.

```
import StdEnv
d=[10000,2000,1000,500,100,25,10,5,1]
$n u l=snd(hd(sort[(sum[foldl(rem)m(d%(0,i))/k\\k<-d&i<-[-1..]],toReal m)\\m<-map toInt[n*u..n*l]]))/1E2

```

Try it online!
> 3 votes

# Answer
# Python (~~264~~ 222 bytes)

Slightly more golfed.

```
m=[.01,.05,.1,.25,.5,1,5,10,20,50,100]
def f(a,i,j):
 t,u=9**9,a*j
 def g(s,d,c):
  nonlocal t
  if(a*i<s<u)+(c>t):t=min(c,t);return c,s
  return(t+1,s)if(s>u)+(d>9)else min(g(s+m[d],d,c+1),g(s,d+1,c))
 return g(0,0,0)[1]

```

Try it Online!
> 2 votes

# Answer
# Perl 6, ~~93 92~~ 89 bytes

```
{.01*($^a*$^b+|0...$a*$^c).min:{$!=$_;sum '✐ᎈߐϨǴd
'.ords>>.&{($!%=$_)xx$!/$_}}}

```

Try it online!

Anonymous code block that takes three arguments (price, minimum percentage, and maximum percentage) and returns the tip.
> 2 votes

# Answer
# Wolfram Language (Mathematica), 105 bytes

This will give all the solutions with minimal coin count.

```
MinimalBy[NumberDecompose[#,d=100{100,50,20,10,5,1,.25,.10,.05,.01}]&/@Range[Ceiling[#2#],#3#],Tr].d/100&

```

Try it online!
> 1 votes

# Answer
# Kotlin, 215 bytes

```
{p:Double,l:Int,h:Int->val d=listOf(10000,5000,2000,1000,500,100,25,10,5,1)
var m=Int.MAX_VALUE
var r=0.0
(Math.ceil(p*l).toInt()..(p*h).toInt()).map{var a=it
var c=0
d.map{c+=a/it
a%=it}
if(c<m){m=c
r=it/100.0}}
r}

```

Try it online!
> 0 votes

# Answer
# Jelly,  ~~33~~  32 bytes

```
“ñṇzi;’b⁴×H¥\ɓ_>Ƈ-Ṫ
PĊ1¦r/ÇƬL$ÞḢ

```

A monadic link accepting a list `[cost in cents, [minimum ratio, maximum ratio]]` which yields a tip amount in cents.

**Try it online!**

### How?

The first line is a helper Link which yields the amount given less the largest denomination note/coin:

```
“ñṇzi;’b⁴×H¥\ɓ_>Ƈ-Ṫ - Link 1, get next lower amount: integer, V
“ñṇzi;’             - base 250 number = 112835839060
       b⁴           - to base 16 = [1,10,4,5,8,10,4,4,5,4]
            \       - cumulative reduce with:       e.g.: 1,10   5,4   10,5   25,8
           ¥        -   last two links as a dyad:
         ×          -     multiply                        10     20    50     200
          H         -     halve                            5     10    25     100
                    - ...yielding: [1,5,10,25,100,500,1000,2000,5000,10000]
             ɓ      - start a new dyadic link with swapped arguments
              _     - subtract (vectorises) ...i.e. [V-1,V-5,V-10,...]
                Ƈ   - filter keep those which satisfy:
                 -  -   literal -1
               >    -   greater than? (i.e. if V-X > -1)
                  Ṫ - tail (tailing an empty list yields 0)

```

The number of calls required in order to reach zero is used to sort the range of tip amounts, and then the leftmost is yielded:

```
PĊ1¦r/ÇƬL$ÞḢ - Main Link: [cost, [min, max]]
P            - product = [cost*min, cost*max]
   ¦         - sparse application...
  1          - ...to indices: 1
 Ċ           - ...what: ceiling   -> [ceil(cost*min), cost*max]
     /       - reduce by:
    r        -   inclusive range (implicit floor of arguments)
          Þ  - sort by:
         $   -   last two links as a monad:
       Ƭ     -     repeat collecting results until a fixed point is reached:
      Ç      -       last link (1) as a monad  (e.g. 32 -> [32,7,2,1,0])
        L    -     length (i.e. coins/notes required + 1)
           Ḣ - head

```
> 0 votes

---
Tags: code-golf
---


title: Where's Blackhat?

text:
# Question
Title: Where's Blackhat?
## Challenge

Write code which, given an image of a panel from a random xkcd comic, returns a truthy value if Blackhat is in the comic or falsey if not.

## Who is Blackhat?

Blackhat is the unofficial name given to the character in xkcd comics who wears a black hat:

Taken from the Explain xkcd page on Blackhat

Blackhat's hat is always straight sided, black and looks the same as in the above image.

Other characters may also have hats and hair but none will have hats which are black and straight sided.

## Input

The image may be input in anyway you wish whether it be a path to the image or bytes via STDIN. You should not need to take a URL as input.

## Rules

Hardcoding the answer is not banned, but it is not appreciated.

You are not allowed to access the internet to get the answer.

## Examples

All images cropped from images from https://xkcd.com

### Blackhat is in the panel (return `truthy`)

---

### Blackhat is not in the panel (return `falsey`)

---

## Test Battery

The 20 images which contain Blackhat can be found here: https://beta-decay.github.io/blackhat.zip

The 20 images which do not contain Blackhat can be found here: https://beta-decay.github.io/no\_blackhat.zip

**If you want more images to test your programs with (to train for the mystery test cases), you can find a list of all appearances of Blackhat here: http://www.explainxkcd.com/wiki/index.php/Category:Comics\_featuring\_Black\_Hat**

## Winning

The program which correctly identifies whether Blackhat is in the comic or not for the most images wins. Your header should include your score as a percentage.

In the event of a tiebreak, the tied programs will be given "mystery" images (i.e. ones that only I know about). The code which identifies the most correctly wins the tiebreak.

The mystery images will be revealed along with the scores.

***Note:*** *it seems that Randall’s name for him may be Hat Guy. I prefer Blackhat though.*

# Answer
# PHP (\>=7), 100% (40/40)

```
<?php

set_time_limit(0);

class BlackHat
{
    const ROTATION_RANGE = 45;

    private $image;
    private $currentImage;
    private $currentImageWidth;
    private $currentImageHeight;

    public function __construct($path)
    {
        $this->image = imagecreatefrompng($path);
    }

    public function hasBlackHat()
    {
        $angles = [0];

        for ($i = 1; $i <= self::ROTATION_RANGE; $i++) {
            $angles[] = $i;
            $angles[] = -$i;
        }

        foreach ($angles as $angle) {
            if ($angle == 0) {
                $this->currentImage = $this->image;
            } else {
                $this->currentImage = $this->rotate($angle);
            }

            $this->currentImageWidth = imagesx($this->currentImage);
            $this->currentImageHeight = imagesy($this->currentImage);

            if ($this->findBlackHat()) return true;
        }

        return false;
    }

    private function findBlackHat()
    {
        for ($y = 0; $y < $this->currentImageHeight; $y++) {
            for ($x = 0; $x < $this->currentImageWidth; $x++) {
                if ($this->isBlackish($x, $y) && $this->isHat($x, $y)) return true;
            }
        }

        return false;
    }

    private function isHat($x, $y)
    {
        $hatWidth = $this->getBlackishSequenceSize($x, $y, 'right');
        if ($hatWidth < 10) return false;

        $hatHeight = $this->getBlackishSequenceSize($x, $y, 'bottom');

        $hatLeftRim = $hatRightRim = 0;
        for (; ; $hatHeight--) {
            if ($hatHeight < 5) return false;

            $hatLeftRim = $this->getBlackishSequenceSize($x, $y + $hatHeight, 'left');
            if ($hatLeftRim < 3) continue;

            $hatRightRim = $this->getBlackishSequenceSize($x + $hatWidth, $y + $hatHeight, 'right');
            if ($hatRightRim < 2) $hatRightRim = $this->getBlackishSequenceSize($x + $hatWidth, $y + $hatHeight, 'right', 'isLessBlackish');
            if ($hatRightRim < 2) continue;

            break;
        }

        $ratio = $hatWidth / $hatHeight;
        if ($ratio < 2 || $ratio > 4.2) return false;

        $widthRatio = $hatWidth / ($hatLeftRim + $hatRightRim);
        if ($widthRatio < 0.83) return false;
        if ($hatHeight / $hatLeftRim < 1 || $hatHeight / $hatRightRim < 1) return false;

        $pointsScore = 0;
        if ($this->isSurroundedBy($x, $y, 3, true, true, false, false)) $pointsScore++;
        if ($this->isSurroundedBy($x + $hatWidth, $y, 3, true, false, false, true)) $pointsScore++;
        if ($this->isSurroundedBy($x, $y + $hatHeight, 3, false, false, true, false)) $pointsScore++;
        if ($this->isSurroundedBy($x + $hatWidth, $y + $hatHeight, 3, false, false, true, false)) $pointsScore++;
        if ($this->isSurroundedBy($x - $hatLeftRim, $y + $hatHeight, 3, true, true, true, false)) $pointsScore++;
        if ($this->isSurroundedBy($x + $hatWidth + $hatRightRim, $y + $hatHeight, 3, true, false, true, true)) $pointsScore++;
        if ($pointsScore < 3 || ($hatHeight >= 19 && $pointsScore < 4) || ($hatHeight >= 28 && $pointsScore < 5)) return false;

        $middleCheckSize = ($hatHeight >= 15 ? 3 : 2);
        if (!$this->isSurroundedBy($x + (int)($hatWidth / 2), $y, $middleCheckSize, true, null, null, null)) return false;
        if (!$this->isSurroundedBy($x + (int)($hatWidth / 2), $y + $hatHeight, $middleCheckSize, null, null, true, null)) {
            if (!$this->isSurroundedBy($x + (int)(($hatWidth / 4) * 3), $y + $hatHeight, $middleCheckSize, null, null, true, null)) return false;
        }
        if (!$this->isSurroundedBy($x, $y + (int)($hatHeight / 2), $middleCheckSize + 1, null, true, null, null)) return false;
        if (!$this->isSurroundedBy($x + $hatWidth, $y + (int)($hatHeight / 2), $middleCheckSize, null, null, null, true)) return false;

        $badBlacks = 0;
        for ($i = 1; $i <= 3; $i++) {
            if ($y - $i >= 0) {
                if ($this->isBlackish($x, $y - $i)) $badBlacks++;
            }

            if ($x - $i >= 0 && $y - $i >= 0) {
                if ($this->isBlackish($x - $i, $y - $i)) $badBlacks++;
            }
        }
        if ($badBlacks > 2) return false;

        $total = ($hatWidth + 1) * ($hatHeight + 1);
        $blacks = 0;
        for ($i = $x; $i <= $x + $hatWidth; $i++) {
            for ($j = $y; $j <= $y + $hatHeight; $j++) {
                $isBlack = $this->isBlackish($i, $j);
                if ($isBlack) $blacks++;
            }
        }

        if (($total / $blacks > 1.15)) return false;

        return true;
    }

    private function getColor($x, $y)
    {
        return imagecolorsforindex($this->currentImage, imagecolorat($this->currentImage, $x, $y));
    }

    private function isBlackish($x, $y)
    {
        $color = $this->getColor($x, $y);
        return ($color['red'] < 78 && $color['green'] < 78 && $color['blue'] < 78 && $color['alpha'] < 30);
    }

    private function isLessBlackish($x, $y)
    {
        $color = $this->getColor($x, $y);
        return ($color['red'] < 96 && $color['green'] < 96 && $color['blue'] < 96 && $color['alpha'] < 40);
    }

    private function getBlackishSequenceSize($x, $y, $direction, $fn = 'isBlackish')
    {
        $size = 0;

        if ($direction == 'right') {
            for ($x++; ; $x++) {
                if ($x >= $this->currentImageWidth) break;
                if (!$this->$fn($x, $y)) break;
                $size++;
            }
        } elseif ($direction == 'left') {
            for ($x--; ; $x--) {
                if ($x < 0) break;
                if (!$this->$fn($x, $y)) break;
                $size++;
            }
        } elseif ($direction == 'bottom') {
            for ($y++; ; $y++) {
                if ($y >= $this->currentImageHeight) break;
                if (!$this->$fn($x, $y)) break;
                $size++;
            }
        }

        return $size;
    }

    private function isSurroundedBy($x, $y, $size, $top = null, $left = null, $bottom = null, $right = null)
    {
        if ($top !== null) {
            $flag = false;
            for ($i = 1; $i <= $size; $i++) {
                if ($y - $i < 0) break;
                $isBlackish = $this->isBlackish($x, $y - $i);

                if (
                    ($top && !$isBlackish) ||
                    (!$top && $isBlackish)
                ) {
                    $flag = true;
                } elseif ($flag) {
                    return false;
                }
            }
            if (!$flag) return false;
        }

        if ($left !== null) {
            $flag = false;
            for ($i = 1; $i <= $size; $i++) {
                if ($x - $i < 0) break;
                $isBlackish = $this->isBlackish($x - $i, $y);

                if (
                    ($left && !$isBlackish) ||
                    (!$left && $isBlackish)
                ) {
                    $flag = true;
                } elseif ($flag) {
                    return false;
                }
            }
            if (!$flag) return false;
        }

        if ($bottom !== null) {
            $flag = false;
            for ($i = 1; $i <= $size; $i++) {
                if ($y + $i >= $this->currentImageHeight) break;
                $isBlackish = $this->isBlackish($x, $y + $i);

                if (
                    ($bottom && !$isBlackish) ||
                    (!$bottom && $isBlackish)
                ) {
                    $flag = true;
                } elseif ($flag) {
                    return false;
                }
            }
            if (!$flag) return false;
        }

        if ($right !== null) {
            $flag = false;
            for ($i = 1; $i <= $size; $i++) {
                if ($x + $i >= $this->currentImageWidth) break;
                $isBlackish = $this->isBlackish($x + $i, $y);

                if (
                    ($right && !$isBlackish) ||
                    (!$right && $isBlackish)
                ) {
                    $flag = true;
                } elseif ($flag) {
                    return false;
                }
            }
            if (!$flag) return false;
        }

        return true;
    }

    private function rotate($angle)
    {
        return imagerotate($this->image, $angle, imagecolorallocate($this->image, 255, 255, 255));
    }
}

$bh = new BlackHat($argv[1]);
echo $bh->hasBlackHat() ? 'true' : 'false';

```

To run it:

```
php <filename> <image_path>

```

Example:

```
php black_hat.php "/tmp/blackhat/1.PNG"

```

### Notes

* Prints "true" if finds black hat and "false" if doesn't find it.
* This should work on previous versions of PHP as well, but to be safe, use PHP\>=7 with GD.
* This script actually tries to find the hat and by doing so, it might rotate the image many many times and each time checks for thousands and thousands of pixels and clues. So the larger the image is or the more dark pixels it has, the script will take more time to finish. It should take a few seconds to a minute for majority of images though.
* I would love to train this script more, but I don't have enough time to do so.
* This script is not golfed (again because I don't have enough time), but has lots of potential to golf in case of a tie.

### Some examples of detected black hats:

These examples are acquired by drawing red lines on special points found on the image that script decided has a black hat (images can have rotation compared to original ones).

---

# Extra

Before posting here, I did test this script against another set of 15 images, 10 with black hat and 5 without black hat and it went correct for all of them as well (100%).

Here is the ZIP file containing extra test images I used: extra.zip

In the `extra/blackhat` directory, the detection results with red lines are also available. For example `extra/blackhat/1.png` is the test image and `extra/blackhat/1_r.png` is the detection result of it.
> 18 votes

# Answer
## Matlab, 87,5%

```
function hat=is_blackhat_here2(filepath)

img_hsv = rgb2hsv(imread(filepath));
img_v = img_hsv(:,:,3);

bw = imdilate(imerode( ~im2bw(img_v), strel('disk', 4, 8)), strel('disk', 4, 8));
bw = bwlabel(bw, 8);
bw = imdilate(imerode(bw, strel('disk', 1, 4)), strel('disk', 1, 4));
bw = bwlabel(bw, 4);

region_stats = regionprops(logical(bw), 'all');
hat = false;
for i = 1 : numel(region_stats)
    if mean(img_v(region_stats(i).PixelIdxList)) < 0.15 ...
            && region_stats(i).Area > 30 ...
            && region_stats(i).Solidity > 0.88 ...
            && region_stats(i).Eccentricity > 0.6 ...
            && region_stats(i).Eccentricity < 1 ...
            && abs(region_stats(i).Orientation) < 75...
            && region_stats(i).MinorAxisLength / region_stats(i).MajorAxisLength < 0.5;
        hat = true;
        break;
    end
end

```

Enhancement of the previous version, with some checks added on the shape of the candidate regions.

Classification errors in **HAT set**: images **4, 14, 15, 17**.

Classification errors in **NON HAT set**: images **4**.

Some examples of corrected classified images:

Example of a wrong classified image:

**OLD VERSION (77,5%)**

```
function hat=is_blackhat_here(filepath)

img_hsv = rgb2hsv(imread(filepath));
img_v = img_hsv(:,:,3);
bw = imerode(~im2bw(img_v), strel('disk', 5, 8));

hat =  mean(img_v(bw)) < 0.04;

```

Approach based on image erosion, similar to the solution proposed by Mnemonic, but based on V channel of the HSV image. Moreover, the mean value of the channel of the selected area is checked (not its size).

Classification errors in **HAT set**: images **4, 5, 10**.

Classification errors in **NON HAT set**: images **4, 5, 6, 7, 13, 14**.
> 9 votes

# Answer
# Pyth, 62.5%

```
<214.O.n'z

```

Accepts the filename of an image file on stdin. Returns `True` if the average of all its RGB color components are greater than 214. You read that right: apparently blackhat images tend to be brighter than no-blackhat images.

(Surely someone can do better—this isn’t !)
> 7 votes

# Answer
# Python 2, ~~65%~~ ~~72.5%~~ 77.5% (= 31/40)

```
import cv2
import numpy as np
from scipy import misc

def blackhat(path):
    im = misc.imread(path)
    black = (im[:, :, 0] < 10) & (im[:, :, 1] < 10) & (im[:, :, 2] < 10)
    black = black.astype(np.ubyte)

    black = cv2.erode(black, np.ones((3, 3)), iterations=3)

    return 5 < np.sum(black) < 2000

```

This figures out which pixels are black, then erodes away small contiguous pieces. Certainly room for improvement here.
> 7 votes

---
Tags: code-challenge, image-processing, test-battery
---


title: Draw an ASCII meandering curve

text:
# Question
Title: Draw an ASCII meandering curve
For the purpose of this question a meandering curve is one that follows the general direction from left to right, but makes repeatedly n+1 turns at 90 degrees to the left and then n+1 turns to the right (for n\>0).

In fact the meander itself will have `n` segments.

The turns are denoted with `+`.

The width of the meanders (the distance between two `+`) is 3 at the horizon (`---`) and 1 at the vertical (`|`)

Here are the single segments a meandering curve with sizes n from 1 to 5:

```
                                                           +-------------------+
                                                           |                   |
                                       +---------------+   |   +-----------+   |
                                       |               |   |   |           |   |
                       +-----------+   |   +-------+   |   |   |   +---+   |   |
                       |           |   |   |       |   |   |   |   |   |   |   |
           +-------+   |   +---+   |   |   +---+   |   |   |   +---+   |   |   |
           |       |   |   |   |   |   |       |   |   |   |           |   |   |
   +---+   +---+   |   +---+   |   |   +-------+   |   |   +-----------+   |   |
   |   | 1     |   | 2         |   | 3             |   | 4                 |   | 5
---+   +-------+   +-----------+   +---------------+   +-------------------+   +

```

## Challenge:

Given two positive numbers `n` and `m`, draw `m` segments of a meandering curve with size `n`. You can write a full program or a function.

## Input:

`n` \> 0 The size of the curve

`m` \> 0 Number of segments to draw

## Output:

An ASCII representation of the meandering curve.

## Examples:

```
n = 3
m = 2
   +-----------+   +-----------+
   |           |   |           |
   |   +---+   |   |   +---+   |
   |   |   |   |   |   |   |   |
   +---+   |   |   +---+   |   |
           |   |           |   |
-----------+   +-----------+   +

n = 2
m = 5
   +-------+   +-------+   +-------+   +-------+   +-------+
   |       |   |       |   |       |   |       |   |       |
   +---+   |   +---+   |   +---+   |   +---+   |   +---+   |
       |   |       |   |       |   |       |   |       |   |
-------+   +-------+   +-------+   +-------+   +-------+   +

n = 4
m = 4
   +---------------+   +---------------+   +---------------+   +---------------+
   |               |   |               |   |               |   |               |
   |   +-------+   |   |   +-------+   |   |   +-------+   |   |   +-------+   |
   |   |       |   |   |   |       |   |   |   |       |   |   |   |       |   |
   |   +---+   |   |   |   +---+   |   |   |   +---+   |   |   |   +---+   |   |
   |       |   |   |   |       |   |   |   |       |   |   |   |       |   |   |
   +-------+   |   |   +-------+   |   |   +-------+   |   |   +-------+   |   |
               |   |               |   |               |   |               |   |
---------------+   +---------------+   +---------------+   +---------------+   +

```

## Winning criteria:

This is , so the shortest code in bytes in each language wins. Please explain your code, if you have time to do it.

# Answer
# Charcoal, ~~52~~ ~~34~~ 33 bytes

```
Ｎθ↶ＦＮＦ⊗⊕θ«+⊖⊗×⊕﹪κ²∨↔⁻θ∧κ⊖κ¹¿›κθ↷↶

```

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

```
Ｎθ

```

Input the size of the meander.

Pivot upwards as the drawing starts at the right and works left.

```
ＦＮ

```

Loop over the desired number of meanders.

```
Ｆ⊗⊕θ«

```

Loop over the segments of the meander.

```
+

```

Print a `+`.

```
∨↔⁻θ∧κ⊖κ¹

```

Compute the `k`th element of the list \\$ n, n, n-1, n-2 ... 3, 2, 1, 1, 1, 2, 3, ... n \\$.

```
⊖⊗×⊕﹪κ²...

```

Alternate between doubling and quadrupling the lengths since the horizontal lines are twice as long, but decrement the result before printing to take account of the `+` that was just printed.

```
¿›κθ↷↶

```

Pivot appropriately for the next segment.
> 6 votes

# Answer
# APL (Dyalog Classic), ~~108~~ ~~101~~ 95 bytes

```
' -+|'[⊃,/⎕⍴⊂b/⍨3 1⍴⍨≢⍉b←⌽⊖2@a⌽1@(a←⊂0 0)⊖0,⊃{((4|-⊖⍉⍵),⍉¯2↑⍉⍵)⍪(2/⍪⍳2),¯2↑⍵}/⎕⍴⊂46 16 47⊤⍨3⍴4]

```

Try it online!
> 5 votes

# Answer
# C (gcc), ~~559 540 523 511 494 484 476 468 456 447~~ 443 bytes

```
#define S memset
l,o,p,q,r;g(c,d,n)char*d;{q=~c;for(p=n*2;q%2*p;bcopy(n*2-p--?"|   |":"+---+",d-q*l*p,5));p=n-1;c--%2?S(S(d-~l-r*!q,45,r++)-2*l,45,r=n*4-1),d[r*=q-1]='|',d[r-l]=d[r+l]=43,p&&g(c%4,memcpy(q?d+p*4+l:d-l-n*4,q?"+   |":"|   +",5),p):p&&g(c%4,d,p,d[-q]=45,d[q*=l]=43,*(d-=q*(n*2*l-l-2)-2)=32);}f(n,m){char b[(o=n-~n)*(l=n*4+5)];g(0,strcpy(S(S(b,32,l*o),45,l)+l-6,"+   +"),n);for(o*=m;b[o/m*l-1]=0,o--;o%m||puts(""))printf(b+o/m*l);}

```

Try it online!

Slightly less golfed

```
#define S memset
l,o,p,q,r;
g(c,d,n)char*d;{
 q=~c;
 for(p=n*2;q%2*p;bcopy(n*2-p--?"|   |":"+---+",d-q*l*p,5));
 p=n-1;
 c--%2?
  S(S(d-~l-r*!q,45,r++)-2*l,45,r=n*4-1),
  d[r*=q-1]='|',
  d[r-l]=d[r+l]=43,
  p&&
   g(c%4,memcpy(q?d+p*4+l:d-l-n*4,q?"+   |":"|   +",5),p)
 :
  p&&
   g(c%4,d,p,d[-q]=45,d[q*=l]=43,*(d-=q*(n*2*l-l-2)-2)=32);
}
f(n,m){
 char b[(o=n-~n)*(l=n*4+5)];
 g(0,strcpy(S(S(b,32,l*o),45,l)+l-6,"+   +"),n);
 for(o*=m;b[o/m*l-1]=0,o--;o%m||puts(""))
  printf(b+o/m*l);
}

```
> 2 votes

# Answer
# Python 3, ~~371~~ ~~354~~ ~~346~~ ~~328~~ ~~298~~ 290 bytes

```
import sys
v=sys.argv
s=int(v[1])
n=range
r="   |"
t="   +---"
h="-"*4
e=" "*4
def C(l):print(l*int(v[2]))
for i in n(-(-s//2)):q=s-i+~i;R=r*i;C(R+t+h*q+"+"+R);C(R+r+e*q+R+r)
for i in n(s//2):q=s//2-i;R=r*~-q;w=2*i+s%2;C(R+t+h*~-w+"+"+r*(q+((i>0)|s%2)));C(R+e*-~w+R+2*r)
C(h*~-s+"---+   +")

```

-20B Thanks to ceilingcat

Try it online!

Pre-golfing:

```

import sys

import math

def draw_curve(curve_size, curve_count, out=sys.stdout):
    for i in range(math.ceil(curve_size / 2)):
        for j in range(curve_count):
            out.write("   |" * i)
            out.write("   +---")
            out.write("----" * (curve_size - 2 * i - 1))
            out.write("+")
            out.write("   |" * i)

        out.write("\n")

        for j in range(curve_count):
            out.write("   |" * (i + 1))
            out.write("    " * (curve_size - 2 * i - 1))
            out.write("   |" * (i + 1))

        out.write("\n")

    for i in range(curve_size // 2):
        for j in range(curve_count):
            out.write("   |" * (curve_size // 2 - i - 1))
            out.write("   +---")
            out.write("----" * (2 * i - (0 if curve_size % 2 else 1)))
            out.write("+")
            out.write("   |" * (curve_size // 2 - i + (1 if i or curve_size % 2 else 0)))

        out.write("\n")

        for j in range(curve_count):
            out.write("   |" * (curve_size // 2 - i - 1))
            out.write("    " * (2 * i + (2 if curve_size % 2 else 1)))
            out.write("   |" * (curve_size // 2 - i + 1))

        out.write("\n")

    for j in range(curve_count):
        out.write("----" * (curve_size - 1))
        out.write("---+   +")

if __name__ == "__main__":
    draw_curve(int(sys.argv[1]), int(sys.argv[2]))

```
> 2 votes

# Answer
# Dash \- POSIX Shell script, 528 bytes

Try it online!

golfed:

```
Y=0;p(){ eval A${1}_${2}='$3';};for Z in `seq $2`;do case $1 in 1)L='r3 u1 r3 d1';;2)L='r7 u1 l3 u1 r7 d3';;3)L='r11 u3 l3 d1 l3 u3 r11 d5';;4)L='r15 u5 l7 d1 r3 d1 l7 u5 r15 d7';;5)L='r19 u7 l11 d3 r3 u1 r3 d3 l11 u7 r19 d9'
esac;for A in $L;do d(){ C=-;case "$1" in r*)X=$((X+1));;l*)X=$((X-1));;u*)Y=$((Y+1));C=\|;;d*)Y=$((Y-1));C=\|;;esac;p $X $Y $2 $C;};for I in `seq ${A#*[a-z]}`;do d $A;done;d $A +;done;done;for Y in `seq 20 -1 0`;do for X in `seq 0 99`;do eval F="\"\$A${X}_${Y}\"";L=${L}${F:- };done;echo "$L";L=;done

```

ungolfed:

```
#!/bin/sh

# helper function for emulating an array, the language does not know it
p(){ eval A${1}_${2}='$3';}
Y=0

for Z in `seq $2`;do

 # define the possible patterns:
 # list="direction+count direction+count ..."
 case $1 in
  1)L='r3 u1 r3 d1';;
  2)L='r7 u1 l3 u1 r7 d3';;
  3)L='r11 u3 l3 d1 l3 u3 r11 d5';;
  4)L='r15 u5 l7 d1 r3 d1 l7 u5 r15 d7';;
  5)L='r19 u7 l11 d3 r3 u1 r3 d3 l11 u7 r19 d9'
 esac

 for A in $L;do
  # helper function for going into needed direction
  # and plot char into array
  d(){
   C=-
   case "$1" in
    r*)X=$((X+1));;
    l*)X=$((X-1));;
    u*)Y=$((Y+1));C=\|;;
    d*)Y=$((Y-1));C=\|;;
   esac
   p $X $Y $2 $C
  }

  # write char as long as needed into array,
  # append in the same direction as last element the '+'
  for I in `seq ${A#*[a-z]}`;do
   d $A
  done
   d $A +
  done
 done

# echo the array linewise
for Y in `seq 20 -1 0`;do
 for X in `seq 0 99`;do
  eval F="\"\$A${X}_${Y}\"";L=${L}${F:- }
 done
 echo "$L";L=
done

```
> 1 votes

# Answer
# Python 2, 261 bytes

```
n,m=input()
i=0;h,v,p,s=map(tuple,'hv+ ');k=p;R=[h+s]
exec"h,v=v,h;R=zip(*R)[::-1];R=[s+R[0][:-1]+k+h+p]+[s+r+s+v for r in R[1:]]+[h*2*i+h+p+s+p];i+=1;k=v;"*n
for r in[[(3-i%2*2)*{h[0]:'-',v[0]:'|'}.get(c,c)for i,c in enumerate(l)]*m for l in R]:print''.join(r)

```

Try it online!

5 bytes from this tip by Esolanging Fruit.
> 1 votes

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


title: Shared Birthday Party

text:
# Question
Title: Shared Birthday Party
An office (let's call it "The Office") is going to cut down on wasted time in 2019 by consolidating office birthday parties. Any two people with a birthday between Monday and Friday (inclusive) of the same week will be celebrated with a *Shared Birthday Party* some time that week. People whose birthdays fall on a Saturday or Sunday get no party at all.

Some people do not like sharing a birthday party with people who do not share their actual birthday. They will be **Very Angry** to have a *Shared Birthday Party*.

We are going to simulate an office and find the first week in which someone gets **Very Angry** about their *Shared Birthday Party*.

### The Challenge

Write a program or function that outputs the first ISO week number for 2019 in which someone in a simulated office gets **Very Angry** about their *Shared Birthday Party*, subject to the following basic rules:

* input an integer *N* \> 1, which is the number of workers in the office.
* the *N* birthdays themselves are distributed uniformly at random from Jan 1 to Dec 31 (ignore Feb 29).
* but the working weeks for the purposes of determining *Shared Birthday Parties* are the 2019 ISO Week Dates, which are between 2019-W01-1 (2018-12-31) and 2019-W52-7 (2019-12-29). A new ISO week starts every Monday. (I think this is all you really need to know about ISO weeks for this challenge).
* for the *N* people in the office, each has a 1/3 chance of having a **Very Angry** *Shared Birthday Party* personality type, so you'll have to simulate that too.
* but they will not be angry if the party is shared with people who have the *same* birthday.
* output the ISO week number (exact format for this is flexible as long as the week number is clear) for the first occurrence of a **Very Angry** person. If there are no angry people, you can output anything that isn't confused with an ISO week or the program can error out etc.

Some simplifying assumptions:

* as I mentioned, ignore the February 29 issue completely (an unneeded complication)
* ignore public holidays (this is an international community so our holidays will differ) and just assume the office is open on each weekday.

### Rules

This is code-golf. Shortest answer in bytes for each language wins. Default loopholes forbidden.

Code explanations welcome.

### Worked Examples

Contrived Example 1 with input *N* = 7. First and second columns are random as described in the rules (but not actually random here of course).

```
Angry Type
Person?    Birthday   ISO Week   Comment
================================================================================
   N       2018-12-31      W01   In the 2019 ISO week date year
   Y       2018-12-31      W01   Same birthday, so no anger happens
   N       2019-02-05      W06
   Y       2019-03-15      W11   No anger happens because other W11 b-day is a Saturday
   N       2019-03-16      W11
   N       2019-09-08      W36   My birthday!
   Y       2019-12-30       -    Not in the 2019 ISO week date year

```

So no anger happens. The program or function can error out or output something not confused with an ISO week number.

Example 2 with *N* unspecified.

```
Angry Type
Person?    Birthday   ISO Week   Comment
================================================================================
   N       2019-01-19      W03
   Y       2019-02-04      W06
   N       2019-02-05      W06   No anger because not an angry person
  ...             ...      ...   (No angry people until...)
   Y       2019-03-12      W11   Very Angry Person!
   N       2019-03-14      W11
  ...             ...      ...   ...

```

The output would be `W11` or something equivalent.

# Answer
# Python 2, ~~172~~ 202 bytes

```
def f(n):
 D=set();A=[];R=randint
 while n:
	n-=1;w,d=R(1,52),R(1,5)
	if R(0,364)>104:D|={(w,d)};A+=[w]*(R(0,2)>1)
 return next((a for a in sorted(A)if[w for w,d in D].count(a)>1),0)
from random import*

```

Try it online!

oops! Missed a requirement; cost 30 bytes.

It is given by the OP that your birthday is not 29 February.

If your birthday is 30 December, it will not fall in any ISO week of 2019, so in any case you cannot be a Very Angry ISO week of 2019.

That leaves 364 other birthdays to consider you being Very Angry about. 104 of these fall on weekends when we have stipulated that you won't get Very Angry about it. So we only care about you 260/365 of the time; i.e., when `R(0,364)>104` (`randint`'s range is inclusive). Given that constraint, it is equiprobable that your weekday birthday falls in any of the 52 ISO weeks of 2019, and any weekday of that week; and, independently, that you are 1 in 3 likely to be a Very Angry person.

D is then a set of `(weeknum,weekday)` so that if a potentially Angry person shares an actual birthday, then there's no need to be Amgry unless there's yet another person having a birthday that week.

0 is returned if no Very Angry people manifest during any ISO 2019 week; otherwise, the ISO week number of the earliest meltdown is returned.
> 5 votes

# Answer
# Jelly,  ~~36 32~~  33 bytes

+1 byte to fix the 30-Dec edge-case I had not noticed (as pointed out by Chas Brown has in comments below the OP)

-4 thanks to Erik the Outgolfer (inline helper and use of outer product)

```
7R2<52×þFX)Ġị$,3XỊ¤€ṁ@\PṢ€Ḋ€Fḟ0Ḣ

```

A monadic link which yields an integer in \\$\[0,52\]\\$ where \\$0\\$ means no Very Angry people at all during the year and other outputs are ISO week numbers.

**Try it online!**

Or see this version which prints the weeks in which each person's birthday lies (0 for weekends) grouped up, then prints a same-ordered list of lists of whether those people are of the Very Angry type, and finally prints the result.
> 2 votes

# Answer
# Java 8, 198 bytes

```
double r(){return Math.random();}

n->{int r=52,a[]=new int[r];for(;n-->0;)if(r()*364>104)++a[(int)(r()*r)];for(;++n<52;)r=r>51&a[n]>1&r()<1-5/Math.pow(5,a[n])&r()<1-Math.pow(2./3,a[n])?n:r;return r;}

```

Output is zero-based (0-51); a value of 52 indicates no **Very Angry** people. Try it online here.

Ungolfed:

```
double r() { return Math.random(); } // shortcut for Math.random(), saves a few bytes

n -> { // lambda taking an intger argument and returning an integer
    int r = 52, // this will hold the result; set to the value for "no Very Angry people" for now
    a[] = new int[r]; // array counting the people whose birthday lies in each week
    for(; n-- > 0; ) // for each person:
        if(r() * 364 > 104) // determine whether their birthday is on a weekday that is not the 30th of December ...
            ++a[(int) (r() * r)]; // ... only if so, increment the counter for a random ISO week
    for(; ++n < 52; ) // loop through the weeks; n is -1 before the loop
        r = r > 51   // if r is still the default ...
          & a[n] > 1 // ... and there is more than one person with a birthday that week ...
          & r() < 1 - 5/Math.pow(5, a[n]) // ... and at least two people have a different birthday ...
          &r() < 1 - Math.pow(2./3, a[n]) // ... and at least one person has the Very Angry personality type ...
          ? n  // ... set the current week as the result ...
          : r; // ... otherwise leave it the same
    return r;  // return the result
}

```
> 1 votes

---
Tags: code-golf, random
---


title: Calculate power series result

text:
# Question
Title: Calculate power series result
*Related: Calculate Power Series Coefficients*

Given a positive integer \\$X\\$ and a max exponent (Also a positive integer too) \\$N\\$ calculate the result of a power series. Example:

$$X^0+X^1+X^2+\cdots +X^N$$

* Assume \\$(X + N) \le 100\\$

---

**Test Cases**

```
1 2  => 3
2 3  => 15
3 4  => 121
2 19 => 1048575

```

---

Standard rules apply.

# Answer
# , 25 bytes

```
function(x,n)sum(x^(0:n))

```

Try it online!
> 9 votes

# Answer
# Haskell, 21 bytes

The straightforward approach:

```
x#n=sum$map(x^)[0..n]

```

For the case \\$ x \neq 1 \\$ we alternatively could use following function with the same length:

```
x#n=div(x*x^n-1)$x-1

```

This uses the fact that

\\$ 1 + x + x^2 + \ldots + x^n = \frac{x^{n+1} -1}{x-1} \forall x \neq 1.\\$

Try it online!
> 5 votes

# Answer
# JavaScript (ES6), 22 bytes

*Saved 1 byte thanks to @tsh*

```
x=>g=n=>~n&&x*g(n-1)+1

```

Try it online!

---

# Non-recursive (ES7), 23 bytes

Using the direct formula mentioned by @flawr:

```
x=>n=>~-(x**++n)/~-x||n

```

Try it online!
> 5 votes

# Answer
# 05AB1E, 3 bytes

```
ÝmO

```

Try it online!

Explanation:

```
Input: 4, 3
Ý    [0..input] - [0, 1, 2, 3, 4]
m    Vectorized exponent - [1, 3, 9, 27, 81]
O    Sum - 121

```
> 5 votes

# Answer
# Jelly, 4 bytes

```
*Ż}S

```

Try it online!
> 4 votes

# Answer
# Python 3, 40 bytes

```
lambda x,n:sum(x**k for k in range(n+1))

```

Try it online!

`lambda x,n:sum(map(x.__pow__,range(n+1)))` is cool too but it's 1 byte longer lol.
> 3 votes

# Answer
# PowerShell, ~~53~~ 46 bytes

```
param($x,$n)0..$n|%{$o+=[math]::pow($x,$_)};$o

```

Try it online!

Not bad for needing a .NET call for `pow`.

*-7 bytes thanks to mazzy.*
> 3 votes

# Answer
# MATL, 4 bytes

```
:^sQ

```

Try it online!

Takes input as `N` then `X`.
> 3 votes

# Answer
# Noether, 17 bytes

```
I~xI(ax!i^+~ai)aP

```

Try it online!

## Explanation

```
I~x               - Store the input in the variable x
   I(         )   - Loop until the top of the stack equals the input n
     a            - Push a
      x           - Push x
       !i         - Increment i
         ^        - Calculate the value of x^i
          +~a     - Add x^i to a and store in a
             i    - Push i
               aP - Print the value of a

```
> 3 votes

# Answer
# Python,  ~~35~~  32 bytes

-1 Thanks to tsh (`f(x,n-1)+x**n` -\> `f(x,n-1)*x+1`)

Port of Arnauld's Javascript answer \- not sure if it is the first, so do shout if you know who deserves the credit!

```
f=lambda x,n:~n and f(x,n-1)+x**n

```

A recursive function which sums the terms right-to-left, with a base case of zero when `n` reaches `-1` (since `~(-1)` is `-1 - (-1)` which is `0` which is falsey).

**Try it online!**

---

My previous **35 byter**:

```
lambda x,n:x^1and~-x**-~n/~-x or-~n

```

Try it online!

### How?

The `^` operator is bitwise-xor, so `x^1` is zero when `x` is one and non-zero otherwise.
In Python non-zeros are truthy, so the right of the logical `and` is executed when `x` is not one, but not executed when `x` is one, whereupon the right of the logical `or` is executed instead.

So, when `x` is one we execute
`-~n` which is equivalent to
`-1 * ~n` which is equivalent to
`-1 * (-1 - n)` which is equivalent to
`1 + n`...

...and when `x` is not one we execute
`~-x**-~n/~-x` which, adding parentheses to signify precedence, is
`(~-(x**(-~n)))/(~-x)` which is equivalent to
`(-1 - -1 * (x ** (-1 * (-1 - n))))/(-1 - -x)` which is equivalent to
`((x ** (n + 1)) - 1)/(x - 1)`
> 3 votes

# Answer
# Brachylog, 11 bytes

```
t⟦R&h;Rz^ᵐ+

```

Try it online!

Nothing particularly interesting, construct the range 0 to n, raise x to the power of each number in it.

And since I wanted to learn how ccumulate works, here's a slightly longer version that uses that:

### 15 bytes

```
,1↺⟨t×{bh}⟩ᵃ⁾k+

```

Try it online!

Form array \[1, x\], and do this n times, accumulating the results into that array after each iteration: multiply the last element of the array, by the second element of the array (i.e. x). Since this calculates \[1, x, x^2, ... x^n, x^(n+1)\], knife off the last value and add the rest of them up as the output.
> 3 votes

# Answer
# Ruby, 26 bytes

```
->x,n{(0..n).sum{|i|x**i}}

```

Try it online!
> 2 votes

# Answer
## Python 3, 42 bytes

```
lambda x,n:n+1if x<2else(x**(n+1)-1)/(x-1)

```

Try it online!
> 2 votes

# Answer
# cQuents, 6 bytes

```
$0;A^$

```

Try it online!

# Explanation

```
        Implicit inputs: A and n
$0      Zero indexing
  ;     Output sum of first n terms in sequence
   A^$  Each term is A to the power of the current index

```
> 2 votes

# Answer
# Python, 31 bytes

```
f=lambda x,n:n<1or x*f(x,n-1)+1

```

Try it online!

---

**Python 2, 33 bytes**

```
lambda x,n:1/x*-~n or~-x**-~n/~-x

```

Try it online!
> 2 votes

# Answer
# , ~~8~~ 7 bytes

```
#.1$~>:

```

Try it online!

### How it works

```
#.1$~>:  Left argument = X, Right argument = N
  1$~>:  Generate a list of N+1 ones
#.       Interpret as base X digits and convert to single integer

```
> 2 votes

# Answer
# Octave, 19 bytes

```
@(x,n)sum(x.^(0:n))

```

Try it online!

Just learnt Octave 15 minutes ago for this challenge... Hoping it is already optimized.
> 2 votes

# Answer
# APL (Dyalog), 7 bytes

```
+/1,*∘⍳

```

Try it online!
> 2 votes

# Answer
# Stax, 8 bytes

```
à╕F¬f£ù╞

```

Run and debug it
> 1 votes

# Answer
# Python 2,  ~~44~~  34 bytes

Here's my naive and simple solution.

```
f=lambda x,n:n>=0and x**n+f(x,n-1)

```

**Try it online!**
> 1 votes

# Answer
# Clean, 38 bytes

```
import StdEnv
$x n=sum[x^i\\i<-[0..n]]

```

Try it online!
> 1 votes

# Answer
# Pure Bash (no external utilities), 32

```
echo $[`eval echo +$1**{0..$2}`]

```

Try it online!
> 1 votes

# Answer
# Bash with GNU utilities, 23

```
seq -s+ -f$1^%g 0 $2|bc

```

Try it online!
> 1 votes

# Answer
# Perl 6, 19 bytes

```
{sum $^a X**0..$^b}

```

Try it online!

### Explanation:

```
{                 }  # Anonymous code block
 sum    # Get the sum of
         X**   # The cross product with the meta operator exponential
     $^a            # With the first parameter
            0..$^b  # And the range of 0 to the second parameter

```
> 1 votes

# Answer
# CJam, 8 bytes

```
l~),f#:+

```

Try it online! Or verify all test cases.

### Explanation

```
l      e# Read a line from STDIN
~      e# Evaluate: pushes x, then n
)      e# Add 1 to n
,      e# Range: gives [0 1 ... n]
f#     e# Map with extra parameter: gives [x^0 x^1 ... x^n]
:+     e# Fold addition over array: gives x^0 + x^1 + ... + x^n
       e# Implicit display in STDOUT

```
> 1 votes

# Answer
# Pari/GP, 21 bytes

```
(x,n)->sum(i=0,n,x^n)

```

Try it online!
> 0 votes

# Answer
# Java 8, ~~78~~ ~~59~~ 40 bytes

```
x->n->x>1?~-(int)Math.pow(x,n+1)/~-x:n+1

```

Uses the approach mentioned by *@flawr*.

Try it online.

**Explanation:**

```
x->n->                     // Method with two integer parameters and integer return-type
  x>1?                     //  If `x` is larger than 1:
   ~-(int)Math.pow(x,n+1)  //   Return `x` to the power of `n+1` - 1
   /~-x                    //   integer-divided by `x-1`
  :                        //  Else:
   n+1                     //   Return `n+1` as result instead

```
> 0 votes

# Answer
# APL (Dyalog Classic), 8 bytes

```
⊣⊥1⍴⍨1+⊢

```

Try it online!
> 0 votes

# Answer
# Prolog (SWI), 49 bytes

Throws errors, but still works I guess.

```
f(_,0,1).
f(X,N,Y):-M is N-1,f(X,M,Z),Y is Z+X^N.

```

Try it online!
> 0 votes

# Answer
# C (gcc), 51 bytes

Your usual, everyday recursive solution.

```
f(b,e,t,i){for(t=1,i=e;i--;t*=b);t=e--?t+f(b,e):1;}

```

Try it online!
> 0 votes

# Answer
# Charcoal, ~~9~~ 7 bytes

```
Ｉ↨ＮＥ⊕Ｎ¹

```

Try it online! Link is to verbose version of code. Uses @Bubbler's algorithm. Explanation:

```
     Ｎ  Second input as a number
    ⊕   Increment
   Ｅ  ¹ Make list of `1`s of that length
  Ｎ     First input as a number
 ↨      Base conversion
Ｉ       Cast to string
        Implicitly print

```
> 0 votes

# Answer
# Pyth, ~~14~~ 13 bytes

```
AQVhH=+Z^GN)Z

```

Try it online!

**How it works**

```
assign('Q',eval_input())
assign('[G,H]',Q)
for N in num_to_range(head(H)):
 assign('Z',plus(Z,Ppow(G,N)))
imp_print(Z)

```
> 0 votes

# Answer
## Batch, 61 bytes

```
@set s=0
@for /l %%i in (0,1,%2)do @set/as=s*%1+1
@echo %s%

```

Using @tsh's algorithm.
> 0 votes

# Answer
# Swift 4.0, 100 bytes

```
func a(x:Int,n:Int)->Int{return(0...n).reduce(0,{p,q in p+(q>=1 ?(1...q).reduce(1,{a,_ in a*x}):1)})}

```

Try it online!

### Ungolfed

```
func a(x:Int, n:Int) -> Int {
  return (0...n).reduce(0,        // For 0 to n
    { p, q in                     // p is result of last cycle, q the current element
      p +                         // Add p to
      ( q > 0 ?                   // If current element is not 0
        (1...q).reduce(1, { a, _ in a*x } ) // pow(x, n) *
        : 1                       // Otherwise, 1
      )
    }
  )
}

* The reduce is shorter than:
import Foundation
[...] Int(pow(Double(x),Double(q)))

```

First golf I do, so could be much more golfable, but finally the super-verbose Swift has a chance to be used!
> 0 votes

---
Tags: code-golf, math, arithmetic, integer
---


# Question
Title: Bijection: tree-like lists - natural numbers
We define a *tree-like list*, or *trist* for short, as the empty list or a list containing only previously constructed trists.

The *natural numbers* can either include 0 or not, according to your preference.

The task is to create a pair of functions or complete programs `f` and `g` (they don't have to be named like this or even named at all) that implement a bijection between trists and the natural numbers. In other words:

* `f` must be able to turn any trist into a natural number
* `g` must be able to turn any natural number into a trist
* `f(g(n))` must equal `n` for any natural number `n`
* `g(f(l))` must be equivalent to `l` for any trist `l`

You can assume that all arguments and results fit in the usual numeric type for your language. Alternatively, instead of the numeric type you could represent a natural number as a list of binary digits, either consistently little- or consistently big-endian.

The shortest solution per language wins. If your functions are recursive, you must name them. If your language requires a statement separator or a newline between the two functions/programs, you *don't* have to count it.

This is a sample algorithm in Python3 (you are free to implement the bijection in any way you like):

```
def f(x):
    r = 0
    for y in x:
        r = (2 * r + 1) * 2**f(y)
    return r

def g(n):
    r = []
    while n:
        m = 0
        while n % 2 == 0:
            n //= 2
            m += 1
        n //= 2
        r = [g(m)] + r
    return r

tests = [
    [],
    [[]],
    [[],[]],
    [[[]],[],[[[]],[]]],
    [[[[[]]]]],
]
for l in tests: print(g(f(l)) == l)

for n in range(20): print(f(g(n)) == n)

```

It uses the following representation:

\\$ \begin{array}{|l} f(\[~\])=0\\ f(\[a\_0,a\_1,\ldots,a\_{n-1}\])=\overline{ 1\underbrace{0\ldots0}\_{f(a\_0)\\\text{zeroes}}~ 1\underbrace{0\ldots0}\_{f(a\_1)\\\text{zeroes}}~ \ldots~ 1\underbrace{0\ldots0}\_{f(a\_{n-1})\\\text{zeroes}}} {}\_{(2)} \end{array} \\$

Challenge inspired by @LeakyNun's question in chat.

# Answer
> 2 votes
# Python 2, ~~118~~ ~~114~~ ~~109~~ ~~105~~ ~~103~~ ~~97~~ 94 bytes

```
f=lambda x:x>[]and f(x[:-1])*2+1<<f(x[-1])
g=lambda n:[g(len(w))for w in bin(n).split('1')[1:]]

```

Try it online!

Same encoding as the example...

---
Tags: code-golf, encoding
---


# Question
Title: Split a list into sized chunks, but not counting items failing predicate
**Motivation**: Sometimes certain items in a list don't count towards your totals. For example, counting plane passengers in rows, where babies sit on a parent's laps.

**Challenge**: write a program to split a list of items into chunks. Each chunk (except possibly the last) is the same *size*, where *size* is defined as the number of items passing a predicate function.

**Rules**:

1. Your program must take
    * a list of items
    * a positive integer chunk size
    * a predicate function (takes an item, and returns true or false)
2. You must return the input list split into chunks
3. Each chunk is a list of items
4. Overall the items must remain in the same order, with none disgarded
5. The number of items passing predicate in each chunk (except possibly the last) should match the input chunk size.
6. items failing the predicate should not count toward this size
7. Items failing the predicate are
    1. still included in the output chunks
    2. allocated to the earliest chunk, in the case that a chunk is "full" but the next items are ones failing the predicate
        * thus the final chunk may not consist solely of items failing the predicate
8. The final chunk may be of *size* less than the chunk size because all the items have been accounted for.

**Non exhaustive examples:**

The simplest example is to consider `1`s and `0`s, where the predicate function is `x ==> x > 0`. In this case, the `sum` of each chunk must match the chunk size.

* items: `[]`, size: `2`, predicate: `x > 0` --\> either `[]` or `[[]]`
* items: `[0, 0, 0, 0, 0, 0]`, size: `2`, predicate: `x > 0` --\> `[[0, 0, 0, 0, 0, 0]]`
* items: `[0, 1, 1, 0]`, size: `2`, predicate: `x > 0` --\> `[[0, 1, 1, 0]]`
* items: `[0, 1, 1, 0, 1, 0, 0]`, size: `2`, predicate: `x > 0` --\> `[[0, 1, 1, 0], [1, 0, 0]]`
* items: `[0, 1, 0, 0, 1, 0, 1, 1, 0]`, size: `2`, predicate: `x > 0` --\> `[[0, 1, 0, 0, 1, 0], [1, 1, 0]]`

And let's finish with the *plane passengers where babies sit on a parent's lap* example. `A` for adult, `b` for baby, plane row is `3` seats wide, adult always listed before their baby:

* items: `[A, b, A, b, A, A, A, b, A, b, A, A, b]`, size: `3`, predicate: `x => x == A` --\> `[[A, b, A, b, A], [A, A, b, A, b], [A, A, b]]`

# Answer
# Jelly, 10 bytes

```
vⱮTm⁵ḊœṖŒṘ

```

A full program taking the monadic black-box function as the first optional argument, the list as the second optional argument and the chunk size as the third optional argument which prints a Python representation of the resulting list of lists (to avoid Jelly's implicit smashing of lists containing characters).

**Try it online!** (note that a list of characters is passed to a Jelly program by formatting it as a Python quoted string)

### How?

```
vⱮTm⁵ḊœṖŒṘ - Main Link: B, L, S
 Ɱ         - map across second argument with (i.e. for X in L):
v          -   evaluate as a monad with input (i.e. B(X))
  T        - truthy indices (e.g. [0,0,1,0,1,1,1,0,0,0,1,0,0]T -> [3,5,6,7,10])
    ⁵      - 3rd optional argument = S
   m       - modulo slice   (e.g. [3,4,7,9,12,15,16,18,19,20]m3 -> [[3,4,7],[9,12,15],[16,18,19],[20]]
     Ḋ     - dequeue        (e.g. [[3,4,7],[9,12,15],[16,18,19],[20]]Ḋ -> [[9,12,15],[16,18,19],[20]]
      œṖ   - partition right (L) at the indices in that
        ŒṘ - print Python representaion

```
> 3 votes

# Answer
# Brachylog, 37 bytes

```
hW&t~c.k{↰₂ˢl}ᵐ;WxĖ∧.bhᵐ↰₂ᵐ∧.t↰₂ˢl≤W∧

```

Try it online!

I was pleasantly surprised to find that this - pretty much a restatement of the question - successfully terminates and produces correct output.

Assumes the predicate is present as predicate 2 below this code. Outputs a list of lists ("chunks"), or `false` for an empty input.

### Explanation:

```
hW&               % First input is W, the expected "weight" of each chunk
                  %  (i.e. the number of items passing predicate in each chunk)

t                 % Take the second input, the list of items
 ~c.              % Output is a partition of this list
    k{    }ᵐ      % For each partition (chunk) except the last,
      ↰₂ˢ         %   Select the items in the chunk that pass the predicate
         l        %   Get the length of that
                  % (So now we have the list of the "weights" of each chunk)
            ;Wx   % Remove the input expected weight from this list, and
               Ė  %  the result of this should be empty.
                  %  This verifies that the list of weights is either
                  %  composed of all W-values, or is empty (when input is [0 0 0] for eg.)

    ∧.bhᵐ↰₂ᵐ      % And, the first element of each chunk (except the first) should
                  %  pass the predicate. This is another way of saying:
                  %  "Items failing the predicate are allocated to the earliest chunk"

    ∧.t↰₂ˢl≤W     % And, the final chunk (which we haven't constrained so far)
                  %  should have weight ≤ the input expected weight
                  %  This disallows putting everything in the final chunk and calling it a day!

    ∧             % (no further constraints on output)

```
> 8 votes

# Answer
# Apl (Dyalog Unicode) 17 16 bytes (SBCS)

Thanks to Adám for saving me 1 byte.

```
w⊆⍨⌈⎕÷⍨1⌈+\⎕¨w←⎕

```

Try it online! for explaination purposes I will leave up the 17 byte solution.

```
{⍵⊆⍨⌈⍺÷⍨1⌈+\⍺⍺¨⍵}

```

`⍺⍺¨⍵` aplies the predicate to the list returning a boolean vector
`+\` generates a running total
`1⌈` replaces leading `0`s with `1`s
`⌈⍺÷⍨` divides each element by the chunk size and rounds up
`⍵⊆⍨` partitions the original vector by this
> 8 votes

# Answer
# Clean, ~~96~~ 92 bytes

Uses a named function `f :: a -> Bool` allowed according to meta consensus.

```
import StdEnv,StdLib
$l n|l>[]=last[[i: $t n]\\i<-inits l&t<-tails l|n>=sum[1\\e<-i|f e]]=[]

```

Try it online!

Expanded (with default highlighting to make comments show up):

```
$ l n // define function $ on `l` and `n`
 | l > [] // if `l` is not the empty list
  = last [ // the last element of ...
                   \\ i <- inits l // prefixes of `l`
                    & t <- tails l // matching suffixes of `l`
                    | n >= // where n is greater than or equal to
                           sum [1 \\ e <- i | f e] // the number of matching elements in the prefix
          [i: $t n] // prepend that prefix to the application of $ to the rest of the list
         ]
 = [] // if `l` is empty, return empty

```
> 5 votes

# Answer
# Java 10, ~~207~~ ~~186~~ ~~159~~ ~~148~~ 145 bytes

```
a->n->{var r=new java.util.Stack();for(int l=a.size(),c=0,j=0,i=-1;i++<l;)if(i==l||f(a.get(i))&&++c>n&i>0)r.add(a.subList(j,j=i*=c=1));return r;}

```

Java is definitely not the right language for this challenge (or any codegolf-challenge of course..)

-21 bytes thanks to *@O.O.Balance*
-3 bytes thanks to *@ceilingcat*

Try it online.

**Explanation:**

```
a->n->{                   // Method with List & int parameters and List of Lists return
  var r=new java.util.Stack();
                          //  Result-list, starting empty
  for(int l=a.size(),     //  Size of the input-List
          c=0,            //  Count-integer, starting at 0
          j=0,            //  Range-integer, starting at 0
          i=-1;++i<l;)    //  Loop `i` in the range (-1, `l`]:
    if(i==l||             //   If this is the last iteration
       f(a.get(i))        //   Or if the black-box function is true for the current item
       &&++c              //    Increase the counter by 1
         >n&              //    If the counter is now larger than the size
         &i>0)            //    and it's not the first item of the List
      a.subList(j,j=i     //     Add a sub-List to the result from range [`j`, `i`)
                          //     And set `j` to `i` at the same time
                  *=c=1));//     And reset `c` to 1 at the same time as well
  return r;}              //  Return the List of Lists as result

```

**Black box input format:**

Assumes a named function `boolean f(Object i)` is present, which is allowed according to this meta answer.

I have an abstract class `Test` containing the default function `f(i)`, as well as the lambda above:

```
abstract class Test{
  boolean f(Object i){
    return true;
  }

  public java.util.function.Function<java.util.List, java.util.function.Function<Integer, java.util.List<java.util.List>>> c =
    a->n->{var r=new java.util.Stack();for(int l=a.size(),c=0,j=0,i=-1;i++<l;)if(i==l||f(a.get(i))&&++c>n&i>0)r.add(a.subList(j,j=i*=c=1));return r;}
  ;
}

```

For the test cases, I overwrite this function `f`. For example, the last test case is called like this:

```
System.out.println(new Test(){
  @Override
  boolean f(Object i){
    return (char)i == 'A';
  }
}.c.apply(new java.util.ArrayList(java.util.Arrays.asList('A','b','A','b','A','A','A','b','A','b','A','A','b'))).apply(3));

```
> 4 votes

# Answer
# , 58 bytes

```
function(v,g,n,a=(cumsum(Map(g,v))-1)%/%n)split(v,a*(a>0))

```

Try it online!

* -5 bytes thanks to @Giuseppe
> 4 votes

# Answer
## Haskell, 72 bytes

```
p#s|let l@(h:t)!a|sum[1|e<-h:a,p e]>s=a:l![]|n<-a++[h]=t!n;_!a=[a]=(![])

```

Try it online!

```
p#s     = (![])         -- main function that takes a predicate function 'p',
                        -- a size 's' and a input list without a name that is
                        -- directly passed as the first argument to function '!'
  let  l@(h:t)!a        -- function '!' is a local function (so that 'p' and 's'
                        -- are in scope). Takes a list 'l' of at least one element
                        -- 'h' (and 't' being the rest of the list) and an
                        -- accumulator 'a'
   |sum[1|e<-h:a,p e]>s -- if 'p' holds for more than 's' elements in 'h' and 'a'
     =a:l![]            --   put 'a' in front of a recursive call with the same list
                        --   'l' and an empty accumulator
   |n<-a++[h]           -- else bind 'n' to 'h' appended to 'a' and
     =t!n               --   call '!' again with 't' and 'n'
  _!a=[a]               -- base case for '!'. If the input list is empty, return
                        --   a singleton list with 'a'

```
> 4 votes

# Answer
# C (gcc), 70 66 bytes

I use a structure to note the start of a sub-list, as C doesn't know about such things.

Thanks to ceilingcat for the suggestions.

```
t;f(a,s,c)l*a;int(*c)();{for(;a->v;a++)(t+=c(a->v))>s?t=++a->s:0;}

```

Try it online!
> 3 votes

# Answer
# MATL, 19 bytes

```
HyX$Ysi/Xk1y>+!w7XQ

```

Based on jslip's excellent APL answer.

MATL doesn't really have user-defined functions as such, but it does have a way to call out to the environment it's running on (MATLAB/Octave), so this uses that for the predicate function. Usage would be something like this, but that functionality is disabled online for security reasons, so here's a version that uses a hardcoded `isodd` predicate function instead: Try it on MATL Online.

```
H    % Push the function name to be called, assumed to be
     %  stored in the H clipboard
y    % Take the first input, push copies of it both below and above the
     %  function name
X$   % Call the function (say 'isupper') with the input as argument
     %  returns a boolean vector
Ys   % Cumulative sum
i/   % Take the chunk size and divide each element by it
Xk   % ceil
1y>+ % Turn the (initial) 0s to 1s
!    % Transpose. Now we have a column vector specifying which chunk
     %  each input element should go into
w    % Bring the other copy of the input on top
7    % Code for this function: '@(x){x.'}'
     %  i.e. place each chunk in a row vector and enclose it in a cell
XQ   % 'accumarray' - split the input into chunks based on
     %   the given column vector, apply the given function to each chunk
     %   (which here just wraps it up as a cell), and accumulate the results
     %   in an array.
     % implicit output

```
> 3 votes

# Answer
# JavaScript (ES6), 69 bytes

*Saved 3 bytes thanks to @tsh*

Takes input in currying syntax `(size)(predicate)(array)`.

```
s=>p=>g=a=>a.every(x=>p(x)?k--:++j,j=k=s)?[a]:[a.splice(0,j),...g(a)]

```

Try it online!
> 2 votes

# Answer
# Ruby, 57 bytes

```
->a,n,g{c=-1;a.group_by{|x|[0,c+=g[x]?1:0].max/n}.values}

```

Try it online!

Anonymous lambda accepting input array `a`, chunk size `n`, and predicate `g`. Maintains a counter `c` of items matching predicate and groups items by the number of chunks already used up. Unfortunately, the initial value -1/n doesn't round up to 0, so we have to spend a few bytes to fix it.
> 2 votes

# Answer
# , 100 bytes

```
function(L,K,P,s=sapply(L,P),y=cut(cumsum(s),seq(0,sum(s),K),,T))for(l in levels(y))cat(L[y==l],"
")

```

Try it online!

outgolfed handily by digEmAll
> 2 votes

# Answer
# Python 2, 92 bytes

```
lambda a,c,p:reduce(lambda r,v:[r[:-1]+[r[-1]+[v]],r+[[v]]][sum(map(p,r[-1]+[v]))>c],a,[[]])

```

Try it online!
> 1 votes

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

```
(s,p,r=[l=[]],n=s+1)=>g=a=>0 in a?g(a,(n=(n||s)-p(v=a.shift()))||r.push(l=[]),l.push(v)):r

```

Try it online!

Invoke as `F(2, x => x > 0)([0, 1, 1, 0])`
> 1 votes

# Answer
# Mathematica, 82 bytes

```
f[l_,s_,p_]:=Last@Reap[i=t=-1;Do[If[p@e,If[++i~Mod~s==0&&i>0,t++]];e~Sow~t,{e,l}]]

```

Ungolfed:

```
f[l_,s_,p_] :=                (* define a function that takes three    *)
                              (* arguments                             *)

  Last@Reap[                  (* collect and return results which were *)
                              (* gathered by the procedural loop below *)

    i=t=-1;                   (* initialize two counters               *)

    Do[                       (* start iterating over the list         *)

      If[p@e,                 (* if element passes predicate           *)
        If[                   (* then if preincremented i is 0 modulo  *)
          ++i~Mod~s==0&&i>0,  (* chunk size and i > 0                  *)
          t++                 (* increment t                           *)
        ]
      ];e~Sow~t,              (* finally sow the element tagged with   *)
                              (* the current value of t                *)

    {e,l}]                    (* e references current element of list  *)
                              (* l is the list itself                  *)
  ]

```

`l` is the input list; `s` is chunk size; `p` is an unnamed/anonymous/pure/lambda function that returns true/false operating on elements of the list.

`Last@Reap[...]` returns a list of lists of every element that was `Sow`-n inside of `...`. They are grouped into sublists by the second argument of `e~Sow~t` which is shorthand for `Sow[e, t]`.

I had to initialize counters to -1 to handle a chunk size of 1, otherwise I would need to check `Mod[i, s]` (`i~Mod~s`) equal to 1, which could never happen.

The rest of the code is explained in the ungolfed block.
> 1 votes

---
Tags: code-golf, set-partitions, functional-programming
---