The Nineteenth Byte

Agawa001

6:07 PM

@Sp3000 dont make it flee , it will be back in the very inconvenient time :D

Martin Büttner

300 hotness points. Randall Munroe is quite a sexy beast apparently.

Agawa001

@MartinBüttner i ll solve ur problem using some geometricks

:D

some maths are always welcom

randomra

@MartinBüttner at first run it's ~70 bytes, you have to be careful to only select one of the 1#, 0#, 1$, 0$ substitutions (after 2 -> #0)

Martin Büttner

wouldn't the former make the latter impossible since the former match covers the latter? (provided you remove the 1 from the unary count in that step, not in the previous one)

randomra

which is the former/latter?

Martin Büttner

6:23 PM

the former are the # ones, the latter are the $ ones

randomra

1# doesn't cover 0$ as they are in different regexes

Martin Büttner

well if it's like 1#(.*a)1 then 1a1 won't match if you do both of them in the same regex

like 1(#|(.*a))1 --> 2$2

wait

1(#(.*a)|(a))1 --> 2$2$3 ... this seems golfable though

1#?(.*a)1 --> 2$1

randomra

but you still need like (?<!#) for the 0$ case if you did a 1#

if you drop the #, you can't even know if there was a 2

you need both 1#?(.*a)1 --> 2$1 and 0#?(.*a)0 --> 1$1 to work

durron597

@Geobits Is that the one with 6 rounds and in the last round you're supposed to click the door instead of one of the urinals?

Geobits

It's been 8-10 years, so I'm not 100% sure to be honest. It was never distributed anywhere beyond my unit (to my knowledge), so I'm assuming we can't be talking about the same thing. I also think there were more than six rounds, because I included stalls as options as well.

randomra

6:37 PM

I hope someone will do boggle-board so I won't be sad about not having time to code my ~1075 score idea.

durron597

@Geobits Oh ok; I remember there was a flash app about that that was super viral in the 90s

0

A: Sandbox for Proposed Challenges

Nonogram Row Validation Background: What is a Nonogram? Input Two lines of data, separated by a newline. The first line will be a space separated list of integers, example: 3 6 1 4 6 The second line will be a line consisting entirely of #, x, and _. This line is guaranteed to be at least a...

Dennis

@randomra I have several ideas, but they all become impractical when I try to make the board rectangular...

randomra

@Dennis I believe in you! :)

Lembik

hi @MitchSchwartz

Mitch Schwartz

@Lembik hi

Dennis

6:40 PM

@randomra It's kinda your fault that I didn't have time for this yet... :P

randomra

I would lose like 10 points on rectangularity.

Lembik

@MitchSchwartz what did you think of the joy of X question?

randomra

@Dennis do you think your current word-score is optimal?

Mitch Schwartz

i did not look into it deeply so far, and am thinking about making the probability code faster atm

Dennis

@randomra I'm a little fuzzy on the details, but I think so.

Lembik

6:42 PM

@MitchSchwartz oh cool :)

Mitch Schwartz

please don't expect too much; i may not have anything to offer

Lembik

@MitchSchwartz of course someone with a phd in probability may be able to work out a closed form solution.. just not me!

although actually I suspect what it really needs is an IMO champion to do that :)

Dennis

Unless I'm missing something, there's only one option left to improve the score: Admit suboptimal amounts of horizontal moves to lessen the number of vertical ones.

durron597

Anyone have thoughts on my sandbox post?

Mitch Schwartz

well i had thought about writing to Min_25 about it, but idk

New Sandboxed Posts

6:43 PM

0

A: Sandbox for Proposed Challenges

Nonogram Row Validation Background: What is a Nonogram? Input Two lines of data, separated by a newline. The first line will be a space separated list of integers, example: 3 6 1 4 6 The second line will be a line consisting entirely of #, x, and _. This line is guaranteed to be at least a...

Lembik

@MitchSchwartz who is Min_25?

Dennis

But that could only work if adding, e.g. 2 horizontal moves would prevent two characters from moving vertically. Possible, but unlikely.

Lembik

oh what is ? :)

Dennis

@randomra ^^

Martin Büttner

@randomra ah I see the problem.

Mitch Schwartz

6:44 PM

he has been top eulerian sometimes, and i had some contact with him through spoj

Lembik

@MitchSchwartz oh great!

@MitchSchwartz I am reading quora.com/… now :)

seems like we should pay him to come to PPCG

Mitch Schwartz

Min_25 is amazing, he finds very trick mathematical improvements and also can do low level optimisations

Lembik

now I want him to look at my puzzles :)

Mitch Schwartz

s/trick/tricky/

Lembik

I don't know how to get to pose programming challenges in these other forums

I think my Joy of X challenge is hard enough if there were a way

and I quite like it :)

VisualMelon

6:52 PM

@MitchSchwartz you can edit your previous messages by clicking the drop-down that appears on the left when you mouse over them, or by hitting the Up cursor key in the entry box (but only for a short time after first sending them)

Lembik

@VisualMelon I don't think I ever mentioned how fond I am of your nick :)

Martin Büttner

@VisualMelon 2 minutes, actually

VisualMelon

good to know

Lembik

copyranter.blogspot.co.uk/2008/04/…

I assume that is about you

Mitch Schwartz

ok, i thought i had gone past the grace period to edit the message

VisualMelon

6:55 PM

huh, no, I just like C# and Fruit

Mitch Schwartz

yeah, for that particular case i didn't catch the typo fast enough, but thanks for the info

Lembik

@VisualMelon :)

Mitch Schwartz

@Lebik, it turns out that taking into account symmetry is really simple

Lembik

@MitchSchwartz great!

Mitch Schwartz

we can just fix the first element of A as a 1

much faster

Lembik

7:02 PM

as in twice as fast?

Mitch Schwartz

well on this old computer, goes from 52 to 64

Lembik

nice

Rainbolt

Is anyone in here familiar with hierarchyid from SQL Server 2008+?

I went through all the trouble of educating myself and creating a table using the hierarchyid data type, thinking that this would somehow save me time reading it into C# as some sort of tree type.

Like "Hello table, give me a tree please." doesn't compile

Nevermind, I found a tutorial of someone else doing it the hard way codeproject.com/Articles/37038/…

Doesn't make any sense. Using hierarchyid saved this guy zero time and effort.

Lembik

7:25 PM

@MitchSchwartz I am currently trying to understand your slower answer

@MitchSchwartz what I need is a recurrence :)

Peter Taylor

@MartinBüttner Very plausible. The ratio tends towards 1/12.

Martin Büttner

sounds good

xnor left a comment on the challenge the other day, but I'm not sure he's actually working on something

I also don't know if David has abandoned his attempt or not

but it doesn't seem likely anyone can confirm or refute your numbers at this point :/

Nathan Merrill

7:43 PM

how do I do a tag symbol?

Martin Büttner

do you mean like [tag:code-golf] --> code-golf?

Nathan Merrill

ah, I had a space, I think

thanks

Agawa001

is there badge symbole ?

Martin Büttner

no

Mitch Schwartz

@Lembik i got around to updating my answer with the symmetry

as the code is still very similar, i didn't post it as a third version, but just edited the second version in place

ok actually i guess i should have waited a minute

we can also fix the first element of B as 0 or 1

New Main Posts

7:51 PM

0

Q: Converting Integer to String in American English

Many have recognized the many bizarre rules of grammar, but rarely do we recognize that our number system is just as strange. Your program must accept an integer, and output that number in American English form (as defined below): For numbers 0-19: 0: Zero 1: One 2: Two 3: Three 4: Four 5: Fiv...

Mitch Schwartz

@Lembik the code is more straightforward to write bottom up than top down, but maybe thinking about it top down could help

and we can include N in the tuple too

although we don't in the program for simplicity and memory

Vioz-

That integer post.. Extremely picky about printout

Mitch Schwartz

for any tuple (N,a,b,s,t), there are only a few ways to get there from (N-1,a',b',s',t')

Geobits

I think he's counting on that pickiness to make it not a duplicate? I dunno.

Vioz-

I feel like that may be the case

This is going to end up in some relatively long answers

even for a golfing language

Lembik

8:04 PM

@MitchSchwartz I think working top down would make more sense for me

Mitch Schwartz

we have a function f(N,a,b,s,t) which gives the count of valid arrays having those properties (considering that there are duplicates for 0s in B to make the probability distribution as desired)

Lembik

@MitchSchwartz I mean to understand what is going on

Nathan Merrill

@Vioz- that's the intention. I wanted it to match American english (as defined by wikipedia) as best I could

Lembik

@MitchSchwartz ok so let me try to understand what f(N,a,b,s,t) means. It is the number of arrays of length N with a as the first element of A , b as the last element of B, with s is the inner product of A[:-1] and B, and t is the inner product of A[1:-1] and B[:-1] such that... what?

Geobits

As an American, I'd never say ninety-eight hundred and seventeen. I might say ninety-eight hundred or ninety-eight oh four, but not that. It makes me cringe ;)

But, trying to find perfect rules probably won't work.

Nathan Merrill

8:08 PM

I tried to get as close as I could

Mitch Schwartz

well the "such that" can be moved earlier in the sentence, where you wrote "with"

trichoplax

I think most continents have more than one style of saying things

Lembik

@Geobits We need a better American English dictionary :)

I still don't understand what americans say for cutlery

or crockery

Nathan Merrill

knife

spoon

fork

pot

pan

Lembik

crockery doesn't mean that! :)

Nathan Merrill

8:10 PM

then I have no idea what crockery is

Geobits

If cutlery is just knives, we say knives. If forks/spoons, it's generally silverware (regardless of actual material).

Nathan Merrill

it just sounds like crockpot

trichoplax

Crockery are the ones that break if you drop them

Lembik

@trichoplax exactly!

Geobits

You mean plates and bowls?

trichoplax

8:11 PM

yes

Lembik

@Geobits cutlery includes knives, forks and spoons.. all the stuff you use to eat :)

trichoplax

And cups and mugs, I think

Nathan Merrill

if we are referring to them as a whole...I don't think we have a single word

for crockery

Geobits

Dinnerware is probably the closest, but there's not much call for it.

Lembik

crockery has to made out of smashable stuff :)

it's not crockery if it is made out of metal or plastic

Geobits

8:11 PM

If I want someone to put plates on the table, I'll ask them to set the table, not get the crockery.

Nathan Merrill

I would totally think dinnerware includes silverware anyways

Lembik

@Geobits sure but if you want to know where the stuff to put on the table is ?

Nathan Merrill

where are the plates?

Lembik

i.e. which cupboard

Geobits

Where are the dishes?

Agawa001

8:12 PM

i only know croquet

Lembik

@NathanMerrill and bowls?

ah.. does dishes include plates and bowls?

Nathan Merrill

yes

trichoplax

We also use "dishes" as a collective noun for all cutlery and crockery

Lembik

oh!

trichoplax

"Wash the dishes"

Geobits

8:13 PM

You could also just say "where are the plates?". I don't think I know anyone who has plates and bowls in separate places.

Lembik

so do you say silverware or utensils or flatware?

trichoplax

Even if no dishes were used

Nathan Merrill

dishes can sometimes refer to crockery or to both crockery and cutlery IMO

Lembik

or even plastic silverware :)

Geobits

Plastic silverware is an amazing phrase.

Lembik

8:13 PM

dunelm-mill.com/shop/dine/crockery

trichoplax

polymerware

Lembik

@Geobits I know.. I love it :)

@Geobits but is it silverware or flatware?

trichoplax

Not all plastic cutlery is flat

Geobits

Both, but I don't know anyone who actually uses the word flatware.

Nathan Merrill

also, nobody says "flat"

trichoplax

8:14 PM

I've never heard flatware before

Nathan Merrill

its an apartment

Lembik

@Geobits that's good! And if it is plastic is it still silverware?

Nathan Merrill

or my room

Lembik

marksandspencer.com/l/home-and-furniture/dining/crockery

Geobits

@Lembik In the US? Yes.

Lembik

8:15 PM

Flatware

Flatware may refer to: Cutlery, eating implements (especially in the US) Flat tableware such as plates or dishes, especially if made of metal...

trichoplax

A single floor apartment is a flat, a two floor apartment is a maisonette

Lembik

@Geobits that's interesting! I was in a canteen and I didn't want to say silverware for the plastic knives and forks

Geobits

@Lembik walmart.com/c/ep/plastic-silverware (walmart link to prove American-ness)

Lembik

@trichoplax no! A maisonette has its own front door to the outside world :)

@Geobits :)

trichoplax

@Lembik Does it count if it has stairs outside the building that take you to the appropriate external front door?

Geobits

8:16 PM

I thought that was a walkup?

Lembik

@trichoplax that's ok.. the main question is if you have to walk through a communal area to get to your front door

Geobits

It's easy here, everything is an apartment.

Mitch Schwartz

@Lembik i should maybe mention part of my thought process when thinking about the problem: what's very fast is if you can simply find a recursion based on the previous total counts that you used, but it seemed that there is a problem of loss of information if you try to do that here, because the inner products might not both be zero, but those arrays could still be prefixes of valid arrays when more elements are added on

Lembik

@trichoplax well if it has lots of stairs that lead to lots of front doors it's not a maisonette... farm5.staticflickr.com/4080/4817646627_be811da741_z.jpg are not maisonettes :)

@MitchSchwartz right... so I am still trying to understand what a top down recursion would look like

Mitch Schwartz

i also tried to do it without "t" at first, before noticing that i lost important information -- i could not make a statement about the inner product when A is shifted, just based on "s"

trichoplax

8:19 PM

What if it has one flight of stairs (going up one floor) to a front door that opens into a communal area in which there are 2 front doors, one of which is to a single floor flat and the other is to a private internal staircase to the two floor flat above?

Lembik

@MitchSchwartz Ok so what does f(N, a, b, s, t) mean? Re: my previous question

@trichoplax not a maisonette

trichoplax

@Lembik I shall update my mental map accordingly

Lembik

@trichoplax :) Of course these words all mostly made up by estate agents

Geobits

@trichoplax Easy, it's an apartment ;)

Lembik

@trichoplax whose motivation is not linguistic beauty :)

Mitch Schwartz

8:20 PM

it is the number of pairs of arrays (A,B) such that len(B) == N, A[1]=a, B[N]=b, and the inner products are s and t as defined earlier

trichoplax

It's estate agents that got me misinformed in the first place...

I feel we may need a separate room for household nomenclature

Mitch Schwartz

there is no additional "such that" -- the tuple specifies a set of pairs that we are interested in counting

Lembik

@trichoplax they also rename the parts of our cities!

@MitchSchwartz to help me clarify... would f(3, 1,1,1,1) have some value?

as an example

there should be a special badge for answers that have hugely more upvotes than the question :)

Mitch Schwartz

yeah so in my original shorter code

Lembik

@MitchSchwartz as in is f(3, 1,1,1,1) the number of pairs of arrays (A,B) such that len(B) =3, A[1]=1, B[3] = 1, the inner product of A[:-1] and B is 1 and the inner product of A[1:-1] and B[:-1] is 1 ?

Mitch Schwartz

8:24 PM

you can add a line after c=X[(a,b,s,t)]

something like if (N,a,b,s,t)==(3,1,1,1,1): print c

now the only caveat is that

the N might be out by 1 because it is in the process of being updated, and i sometimes find that kind of thing hard to keep track of :p

Lembik

:)

this is very helpful... I will carry on trying to write a top down recurrence for this thing :)

I am impressed you managed to make a bottom up solution without starting with a top down one

Mitch Schwartz

:) thanks

Lembik

@MitchSchwartz were you serious about contacting Min_25?

Mitch Schwartz

well i'm not sure if i want to bother him but

probably doesn't hurt to mention it

Lembik

@MitchSchwartz from my perspective I think it sounds like it would be great fun if he were interested

I would be particularly intrigued if he had something to say about the Joy of X question

or even if Min_24 did :)

Mitch Schwartz

8:28 PM

heh

Lembik

the golfers are neck and neck on codegolf.stackexchange.com/questions/51406/… :)

cjam versus pyth

Mitch Schwartz

the pruning idea is the only one i had left, aside from writing in C or C++, which only deals with implementation

it would be interesting if Min_25 had other ideas of a slick mathematical approach, i wouldn't rule out the possibility

Lembik

@MitchSchwartz the pruning idea seems very interesting to me...

@MitchSchwartz do you ever use cython or numba? That keeps it all more pythony

@MitchSchwartz yes!

Mitch Schwartz

the last problem i contacted him about is this one spoj.com/problems/GRIDSUM1 and the two harder versions GRIDSUM2 and GRIDSUM3

Lembik

did he reply?

Mitch Schwartz

8:35 PM

i had solved the original polish one and noticed that it could be generalised, and Min_25 very quickly found an O(1) solution, while my complexity is not nearly as good

yeah, he is the problem setter (publisher) of that one and the two harder ones

Lembik

aha :)

oh I see

well let's see what happens!

I will have to ask you if I can pose the Joy of X question on one of these forums somehow.. but I have to go now

chat tomorrow hopefully

Mitch Schwartz

i vaguely think about it as a graph, with edges corresponding to the summands

well idk what forums you are referring to

on spoj you would only publish if it is something you had solved, and you devised test data to see if others could solve it within some time limit

but yeah if we direct edges from N to N+1, say

i think it may be easier to characterise the outgoing edges from a node than the incoming ones, as the case may be

Rainbolt

@Geobits One day I am going to build a program that reads in a list of ASCII tetrominoes and allows you to drag and drop them onto a grid. Then I'm going to claim your bounty.

I feel like if I say that out loud I will actually do it eventually.

Mitch Schwartz

8:51 PM

s/other ideas of/other ideas or/

@Lembik ^^ (since you seem to be away, so that it will register that you have unread messages)

Geobits

9:11 PM

@Rainbolt Please do. It will be well worth the bounty. Though IIRC wasn't there a snippet or fiddle someone posted that let you do that anyway?

It was hard for me to drag/drop it to get right, and I knew roughly what it should look like.

Agawa001

when does the wheel of blame blame the room .

Martin Büttner

new I/O default proposal:

1

A: Default for Code Golf: Input/Output methods

Programs may combine two or more input methods For example, if the inputs are an string and an int, a function that takes a string as an argument and an int from STDIN would be valid. The input format must still be consistent for a given program.

Rainbolt

I almost think the new proposal goes without saying

Dennis

@MartinBüttner Got my vote. I do this whenever I can.

Rainbolt

Hahaha is that your criteria? "I do this so I had better vote for it."

(Kidding, I'm sure you voted judiciously.)

Dennis

9:22 PM

I'm doing it already. So far, nobody complained. If it's one of the default methods, nobody should. No-brainer. :P

randomra

@MartinBüttner should this apply to output too? like function return and print?

trichoplax

I think programs more often have multiple inputs than multiple outputs, but I don't see why it shouldn't also apply to outputs in that minority of cases

(at least programs here...)

Agawa001

@Dennis u have good interventions in cryptography.se

durron597

Does anyone have any thoughts on this?

0

A: Sandbox for Proposed Challenges

Nonogram Row Validation Background: What is a Nonogram? Input Two lines of data, separated by a newline. The first line will be a space separated list of integers, example: 3 6 1 4 6 The second line will be a line consisting entirely of #, x, and _. This line is guaranteed to be at least a...

Dennis

@Agawa001 Just a few. Although I do like this one: crypto.stackexchange.com/questions/5704/…

Martin Büttner

9:44 PM

@randomra ask the author of the post

VisualMelon

10:28 PM

I think there is a proof, that given some tree, we can define some M for each node, which is the number of ways to build said tree by adding edges, starting from said node (the root), such that it is always a tree, that for a given tree, there will exist 1 or 2 nodes with a maximum M, and as you traverse away from them, the M of the nodes you visit gets smaller and smaller

(i.e. given some tree, you can start at any node, and just follow the edges that take you to the larger value of M, and you will always end up at the node/nodes of greatest value M, of which there are at most 2, and if there are more than one, they must be next to each other)

... ON RECONSIDERATION, that bit about them having to be joined directly is definitely false, but I think the rest isn't

I probably shouldn't have made that assumption when I did all this maths...

on re-reconsideration, I disagree with my previous reconsideration, they would have to be joined, if they weren't they wouldn't be of maximum M

somehow, I hope that this will help me solve Sparr's family trees

(currently I can only solve up to n=10 with my heuristic search before I run out of memory)

I am also tired, and will have to look this over tomorrow... now for sleep

aditsu

11:07 PM

hey everyone, I've been studying SKI combinators and stuff, and I made this interpreter: ski.aditsu.net

check it out and let me know if you find any bugs

Martin Büttner

I really can't wait for this game to leave early access

@aditsu can you code in Unlambda now? ;)

aditsu

heh, not really

unlambda is more advanced

I was mainly trying to figure out jot, and I think I still have a bug somewhere in the code

I started from this challenge and wanted to find the first non-terminating jot program; I found one but the official "interpreters" seem to terminate

its SKI translation is S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(I))SKSKSK))))SKSK))))))))))))))SKSKSKSK

Martin Büttner

ah, that one!

aditsu

yeah... anyway, jot is probably not a happy choice for a language, although it has some very nice properties

every program is a number and every number is a valid program... but running it is kinda complicated

Martin Büttner

11:25 PM

hm yeah, I need quite a lot of code to enumerate the programs for BCT

aditsu

ah, another name for the SKI stuff is combinatory logic

I just published a small update

feersum

does combinaty logic have a reason for existence other than the joy of esoterica?

aditsu

from wikipedia: it "has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming languages"

feersum

sounds like a no :P

not to be knocking the joy of esolangs

aditsu

are you treating all functional languages as esoteric? :p

feersum

11:37 PM

you wouldn't need to learn SKI calculus or anything to use them

aditsu

no, but that's how they were invented

plus "lambda" features in plenty of non-functional languages