The Nineteenth Byte

digEmAll

06:50

@Dennis: Hi Dennis, just a quick question. It seems that TIO doesn't handle \r correcly (example ); is it because the output is redirected to something unable to handle carriage return, like a file, a string in memory or something like that ?

Jo King

@digEmAll I think it's the web browser itself that can't distinguish between newlines and carriage returns

Jo King

07:03

Oh, in the output?

Wouldn't that be expected behaviour, at least on Mac systems? Would an output file really display it as bazbar, or would that just be how it's shown in the console?

digEmAll

07:30

@JoKing: I think interpreting \r as newline is correct for a file output, but in a console you expect to get bazbar (not sure about mac os, but in principle carriage return should just move the cursor back to start of line)... so, here the question is : is TIO supposed to behave like an interactive console ? :D

Anush

09:11

CMC If you borrow 243 each month for 12 months at 8% per year, how much do you owe at the end of the year?

Neil

10:05

far too much

Anush

@Neil :) How about just in interest?

Neil

I make it 129.5

Anush

@Neil oh! How did you do that?

Neil

@Anush (((1 + (.08 / 12)) ** 13 - 1) / (.08 / 12) - 13) * 243

Anush

@Neil is that the closed form for a more obvious sum?

@Neil or in other words, how did you derive that formula?

Neil

10:18

yeah, sum for i = 1 to 12 of (1 + .08 / 12) ** i

Anush

why is there a plus 1?

dzaima

that's interpreting 8%/year as (8/12)% per month, which arent the same thing

Neil

you're right

it should be (1 + .08) ** (1 / 12)

Anush

my guess was 1.08*243+1.08^(11/12)*243+1.08^(10/12)*243+... - 243*12?

Neil

sum for i = 1 to 12 of (1 + .08) ** (i / 12)

Anush

10:20

but I have low confidence in that guess

that's the same as what I wrote, right?

Neil

closed form is now (((1 + .08) ** (13 / 12) - 1) / ((1 + .08) ** (1 / 12) - 1) - 13) * 243

Anush

what does that evaluate to?

Neil

just under 125

Anush

cool :)

so if we make the 243 and 8% variables, we have a golfing challenge :)

Anush

10:59

@Neil that's actually quite a surprising figure. It's 4.28% of the total amount borrowed

Neil

well, under simple interest it would be about 4% since you're borrowing the total amount for about 6 months on average

Anush

right.. so I don't think I would have guessed it would be more than half in the end

is that obvious why it should be more than 4%?

Neil

12:15

compound interest will always work out more than simple interest

in the worst case, double simple interest becomes e when compounded instantaneously

CMC: Given 4 cuboids with identical cross-sections to be placed 2 each in 2 identical containers, what's the minimum amount of wasted space?

Veskah

Hmm, does the decision-making tag only apply to true-false output, or is it cool to apply to one that has 3 values? In this case: win,lose, tie

Arnauld

12:41

@Mego Should the "Best of 2018 Awards" room be unfrozen so that the next waves can be processed?

New Main Posts

0

Q: Who won a Game of Bar Dice?

Challenge Bar Dice is a simple game played in a Bar with Dice (hence the name). You roll 5 six-sided dice and attempt to make the best hand. Scoring is based on amassing the largest number of dice with the same digits. Each hand must include at least a single "Ace", or one, in order to be a...

Veskah

That was quick. Must've just got in before the next check

Dennis

13:22

@digEmAll TIO displays the output in a textarea. Unfortunately, most browsers normalize newlines in textareas.

@digEmAll Whenever given a choice, TIO behaves non-interactively. I plan to make an interactive version some day, after finishing the API.

digEmAll

14:16

@Dennis: thanks for the info (and of course many thanks for developing TIO)

Veskah

14:49

Dang downvoter taking my karma off a multiple of 5.

Just means I need to anger 4 other people

Poke

15:15

or you could downvote other people

Skidsdev

I feel like Ruby is one of those technologies I've somehow managed to avoid for my entire career

Anonymous

@Arnauld The fact that it got frozen says a lot about this community's interest in Best Of... Yeah I'll unfreeze it

Pavel

17:02

@Skidsdev It's like if someone tried to "fix" Perl without realizing what it is that people actually like about Perl

DJMcMayhem

The confusing gibberish?

Pavel

Not having to convert your strings to numbers and the other way around is pretty neato

Poke

17:38

The confusing part for me is when you start having shit like

@$variable

yeah ok

Oliver

@Adám Japt, 5 bytes

Poke

@Poke Try it online!

Oliver

4 bytes if I can reverse the input

Skidsdev

17:58

why are PDFs such a monolithic clusterfuck

DJMcMayhem

@Adám Python, 40 bytes: lambda a,b:sorted(b,key=lambda n:n in a)

39: lambda a,b:sorted(b,key=a.__contains__)

New Sandboxed Posts

18:53

0

A: Sandbox for Proposed Challenges

Proving that a Russian cryptographic standard is too structured The aim of this challenge is to find an impossibly short implementation of the following function p, in the langage of your choosing: unsigned char pi[] = { 0xFC,0xEE,0xDD,0x11,0xCF,0x6E,0x31,0x16,0xFB,0xC4,0xFA,0xDA,0x23,0xC5,0x04...

Poke

@Skidsdev context?

Skidsdev

19:16

@Poke from a dev perspective, IE generating, modifying etc pdfs

Rick

What is the logic behind bitwise AND does it follow from a logical axiom of some kind?

Poke

19:33

@Skidsdev you're writing your own pdf generation bits?

@Rick wat

Rick

@Poke I am just confused about the operation, and what it means with respect to the binary. What does it mean to take & of two numbers

Adám

@Rick It is then AND of the respective bits of the numbers' internal binary representation.

dzaima

@Rick short & simple explanation

Adám

@dzaima No it isn't. What is the meaning of doing so? What does the result tell us?

Rick

but what does it mean that
0b1100
& 0b1010
--------
= 0b1000 what is this with respect to the previous two numbers

Poke

19:41

0 = false
1 = true
0 & 0 -> false AND false == false == 0
0 & 1 == false == 0
1 & 0 == false == 0
1 & 1 == true == 1

dzaima

@Rick take them column by column, and ^

Adám

12 AND 10 gives 8. Huh? What is the relationship between inputs and output?

dzaima

@Adám you ignore base 10 completely here.

Poke

^

Adám

@Poke @dzaima You guys are explaining the algorithm. Rick is clearly asking for the significance. Why would one want to AND two numbers (not two bits)?

Poke

19:43

you wouldn't

Rick

correct significance

Poke

or rather

you rarely do

for example if you take a number AND 1, then if the result is 1 the number was odd

Rick

if we were talking about XOR we can say that it preserves falsehood

dzaima

@Rick doing tedious low-level stuff (e.g. quickly checking if a number has a specific bit set). besides that, not much.

Poke

that's a usecase

Adám

19:44

I think the correct answer to his question is: No, it doesn't follow any sensible concept. It is a completely arbitrary operation that falls out from our choice of internal number representation.

Poke

It's a bitwise operation... not a numerical operation

It returns 1 if both bits are "on" or "true"

Adám

@Poke Hence his question regarding numbers.

Poke

nothing

that's like asking what the significance is of lexicographically sorting numbers

Adám

*looks at JavaScript*

Rick

how can XOR be an Exclusive disjunction essentially means 'either one, but not both nor none' but & be

Poke

19:47

depends on the context but you usually don't care that they're numbers

@Rick in that case AND means "both"

just like in english

Adám

@Rick Sometimes, lists of individual bits are stored in so-called packed bit boolean arrays, utilising individual bits of a byte, instead of wasting 7 bits from each byte. In such a case, one can look at the byte as a number, and seemingly do nonsense bitwise operations on such "numbers", but the goal is actually to eventually unpack the bits. This can provide drastic speed-ups.

Veskah

Cool example is Fast Inverse Square Root Function

Adám

CMC: Every non-negative integer can be written in exactly one way as a sum of unique powers of two. Given two non-negative integers, return the sum of the unique powers of two that they have in common.

Veskah

Oh, I take that back. It just subtracted a magic number after some bit shifts

Fast inverse square root

Fast inverse square root, sometimes referred to as Fast InvSqrt() or by the hexadecimal constant 0x5F3759DF, is an algorithm that estimates 1⁄√x, the reciprocal (or multiplicative inverse) of the square root of a 32-bit floating-point number x in IEEE 754 floating-point format. This operation is used in digital signal processing to normalize a vector, i.e., scale it to length 1. For example, computer graphics programs use inverse square roots to compute angles of incidence and reflection for lighting and shading. The algorithm is best known for its implementation in 1999 in the source code of...

Rick

@Adám that makes sense, if we shift an int by intervals of 8 and do & on them of 255

DJMcMayhem

19:54

@Adám Sooo A & B?

Adám

@Rick ^

DJMcMayhem

It took me a second to figure out if that was a real CMC xor a fancy phrasing of &

Adám

@DJMcMayhem OR, not XOR!

DJMcMayhem

My b

Skidsdev

@Poke Nope,we're using very expensive libraries to handle most of it, but we need to redact legal info

Rick

20:00

thanks, @Adam and everyone else this helped a lot!

DJMcMayhem

@Adám @Rick To add to this, the most common use-case I've seen is that each bit represents a particular flag. For example, windows file flags. So say I wanted to check if a file was a system file, I AND the file with 0x4 or 0x01 << 2. That tells me whether the third bit is on or off.

That'll sometimes be called a bitmask, since everything is a zero except for the third bit (0x04 == 00000100), so all those 0's mask the bits I don't care about

Adám

CMC: Given a bytestream/string/list/whatever (choose one!) that comprises at least/exactly (choose one!) three bytes, return the nineteenth bit.

DJMcMayhem

64

A: What is a bitmask and a mask?

Bits and Bytes In computing, numbers are internally represented in binary. This means, where you use an integer type for a variable, this will actually internally will be represented as a summation of zeros and ones. As you might know, a single bit represents one 0 or one 1. A concatenation of ...

@Adám Can I take an integer?

Adám

@DJMcMayhem Yes, but then it'd have to be a 32-bit int or bigger.

Rick

@DJMcMayhem sort of like this (n&(n-1)>0) but checking when a number is odd or not

when we only care about the tail bit

DJMcMayhem

20:07

That'll fail for 6. 6 & 5 == 4

You want n & 1

Rick

the result of (n-1) >0 is a 1

DJMcMayhem

Yes, but 6 & 5 > 0 is true, though 6 is not odd

@Adám 16 bytes: lambda n:n>>19&1

Rick

@DJMcMayhem
https://tio.run/##JYlBCoMwEADv@4oFQZKDYC@9mPqXsFlk0ayhSU7i22NoL8MwQylNG1FrgygdNTA6OXP5so8r1Cy6ofrIOXlizCUsIFowelFjr58rfvD9z3tXo6PR6WXX2S4AdNaCzvXTwRqO3uBu7QE

DJMcMayhem

I see now

Poke

i think bitwise & has super low precedence

DJMcMayhem

20:15

But that's literally just the same thing as n & 1 with more confusing steps

Poke

fyi

Try it online!

Rick

@Poke what is this suppose to do?

Poke

wasn't sure what you were trying to achieve and was demonstrating that ">" has higher precedence than "&"

Rick

just showing how to detect odd numbers, oh yeah the > higher precedence

Poke

Your current implementation fails for: n=odd numbers <=1

n&1 should always work

dzaima

20:32

@Rick neither ((n&(n-1)) > 0) nor (n & ((n-1)>0)) successfully detect odd numbers for all n ≥ 0

New Main Posts

0

Q: Multiplication in the Steenrod Algebra

Here's yet another Steenrod algebra question. In order to represent an algebra, we need to know a basis for the algebra and also how to multiply things. From my previous question, we know the basis, in this question we're going to learn to multiply Steenrod operations. The Steenrod algebra is gen...

code-golf math combinatorics topology

Rick

@dzaima yeah has to be n > 1

dzaima

@Rick it doesn't work for 1 either

Poke

that's what i just said

Rick

@dzaima yeah sould be > than 1

because 1 is odd

which is true

which makes it consistent

dzaima

20:36

also why (n-1)>0 not n>1

Anonymous

@DJMcMayhem You want n>>18

DJMcMayhem

...

Anonymous

The 19th bit has 18 less-significant bits that you'd need to shift off

Anonymous

Also, 10 bytes of ES6: x=>x>>18&1

Rick

to test if the number n is a power of 2

dzaima

20:44

@Rick so ((n&(n-1)) > 0) is what you wanted after all, and all the odd/even stuff is unrelated

Rick

well if it's not a power of 2 it is odd. I just was building on DJMcMayhem point about the significant bit and the & operation.

DJMcMayhem

Yes, but there are plenty of numbers that are neither powers of 2 nor odd.

Rick

like what

Poke

6

10

etc

Rick

in binary

Poke

20:51

powers of 2 have a unique binary form of a 1 followed by all zeros. even numbers have a unique binary form of ending with a zero. There are a lot of bits in the middle

DJMcMayhem

6 (110), 10 (1010), 12 (1100), 14 (1110)...

Or anything matching /^1[01]*1[01]*0$

That makes me want to play some strupremum

Rick

binary representation powers of 2 are the only numbers with just one bit set to 1

let's not get carried away

give me an example that breaks that rule :p

DJMcMayhem

@Rick I'm so confused. Are you testing for powers of two or even/odd?

Rick

21:07

powers of two and it happens to also work for even/odd where n>1

just consider it another way to golf for powers of 2 in your golfing toolchain that can also check for even odd where n> 1 ;p

DJMcMayhem

n & ((n-1) > 0) doesn't correctly detect powers of two, and (n & (n-1)) > 0 doesn't correctly detect even/odd

Rick

(n&(n-1)>0) where n > 1 for odd even checks

DJMcMayhem

Is the same as n & ((n-1) > 0)

tio.run/##JYvBCoMwEETv@xUDhTZBBNujRv9FkigLmojGU/…

Neil

@Mego not in 0-indexed languages

Rick

that because you are mismatching the order of precedence with intent, but this isn't (n(n-1))>0

*(n&(n-1))>0

New Main Posts

21:54

0

Q: Generating edge cases in programming puzzles

Not exactly sure if it belongs in this site, but I always have trouble thinking of all the certain edge cases in any kind of competitive programming or puzzles. For example, take this kind of problem Find the size of the smallest list of squares that add up to n f(16)-> 1 (16) f(17)->...

tips programming-puzzle

Rick

it's it strange that the size 4,294,967,295 of an int shifted to the right by 32 is 255

which also happens to be the size of a unsigned char

dzaima

@Rick how did you get that?

Rick

@dzaima sorry that 32 is supposed to be a 24

I took 4294967295 >> 24

dzaima

@Rick "happens to" well what did you expect, 32-24 = 8

Rick

22:17

@dzaima just trying to wrap my head around how to compress 32 bit int

New Sandboxed Posts

23:16

0

A: Sandbox for Proposed Challenges

Calculation of Fibonacci sequences for arbitrary operations Given the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, ..., a list of non-empty and valid basic operators (+, -,*,/) (/ is the floating point division) and a number N, calculate what is the final result of the sequence following the...

Transcript for