The Nineteenth Byte

« first day (4648 days earlier) ← previous day next day → last day (492 days later) »

DLosc

03:04

@Neil Seals on an iceberg have been used before. Maybe you could change it up and use penguins instead?

4 hours later…

l4m2

06:56

How to get m different numbers randomly in 1,2,3,...,n in at worst O(m) time? I can find O(n) one by shuffling and average O(m) one by hashmap and retry (m<n/2)

Neil

07:36

you mean a random permutation? generate randint(n!) and decode it?

m90

I think that's technically impossible, because even generating a single uniformly-distributed random number in a range of arbitrary size has unbounded worst-case time.

If you can accept a small difference from the correct probabilities, then it becomes possible.

Start with all the numbers, then repeatedly: take a random one, remove it, and move the last one into its place (so that they remain contiguous).

To avoid the O(n) initialization, there are several options (the best option depends on how you'll be using this):

l4m2

You can use rand(n) to get random number in 1..n
This avoids argue that RAND_MAX % n != 0

m90

@l4m2 Well, then you're depending on the implementation of that rand function, and I believe those typically do have unbounded worst-case time (here's one example: github.com/python/cpython/blob/main/Lib/random.py#L252])

1 hour later…

The Empty String Photographer

09:10

def o1sort(l):
 a = max(l)
 l.remove(a)
 l.append(a)
 while True:
  if l == sorted(l) and len(l) > 1:
   return l

O(1) sorting algorithm

Command Master

:64608031 This should work, if you accept hash maps. Otherwise it can be a treemap for O(m log(n)):
import random

def randchc(n, m):
    map = {}
    ans = []
    for i in range(m):
        if i not in map:
            map[i] = i
        j = random.randrange(i, n)
        if j not in map:
            map[j] = j
        map[i], map[j] = map[j], map[i]
        ans.append(map[i])
    return ans

Is the sandbox the SE question with the most answers?

Seems like it, it has 4501 answers, then our "Hello, World!" question with 966 answers, and then meta.stackexchange's Sandbox archive with 623 answers

math scat

09:25

oh wow

Command Master

09:42

Also 8 of the 20 most answered questions are on CGCC (and another one is the sandbox)

1 hour later…

Sandbox Posts

10:55

A: Sandbox for Proposed Challenges

Pushing Penguins on an Integer Iceberg An iceberg is represented by a rectangular grid of cells. Each cell can hold one of three penguins. Penguins can be pushed in any free orthogonal direction, but they slide until they reach the edge of the grid or would bump into another penguin. Example: ......

2 hours later…

noodle man

12:43

@CommandMaster we just need 44 more hello world!'s

Neil

12:53

CMC: Hello world checker: Given an input string, check that it is the words "hello world" in either upper, lower, title or sentence case. The string can optionally end with . or ! and if so then can optionally contain a , before the space.

noodle man

13:20

@Neil so "hello World" would return false?

Command Master

@Neil So all of the following (and only them) should return true? Hello world, hello world, HELLO WORLD, Hello World, Hello, world. hello, world. HELLO, WORLD. Hello, World. Hello, world! hello, world! HELLO, WORLD! Hello, World! Hello world. hello world. HELLO WORLD. Hello World. Hello world! hello world! HELLO WORLD! Hello World!

noodle man

TS types, surely plenty golfable, 177 bytes typescriptlang.org/play?#code/…

uppercase makes it take a lot more bytes

noodle man

13:41

TS types 105 bytes typescriptlang.org/play?#code/…

this version constructs a union type of all true answers. assigning a string constant type to the union will either succeed or give an error

AFAIK this is an acceptable default, i'm pretty sure i've seen another TS types answer use it, but if it isn't then it can be a generic type returning either 0 or 1 like my first submission for 132 bytes:

//@ts-ignore
type X<S,A=", "|" ",B="!"|"."|" ">=S extends`Hello${A}${"w"|"W"}orld${B}`|`HELLO${A}WORLD${B}`|`hello${A}world${B}`?1:0

Neil

@CommandMaster looks about right to me

noodle man

that list is basically what my submission does yeah

oop TS types 79 bytes :) typescriptlang.org/play?#code/…

i forgot that TS has built-ins for uppercasing and lowercasing a string type, this version makes a union of all possible title case or sentence case, then makes the union of that with it uppercased and with it lowercased

that's probably as short as it gets so i'll stop now

Command Master

14:01

I'm thinking about creating a language, and I'm not sure if it should be tacit or stack-based. What are the pros and cons of each?

noodle man

is it a golfing language?

consiceness could be a big factor for choosing one over the other

stack-based:
- doesn't require much syntax, easy to parse both mentally and by a computer
- once you understand the stack, it's easy to understand
- but, learning how a stack works is kinda confusing

i don't really understand any tacit langs but i know they often have very "clean" code

Command Master

14:28

@noodleman somewhat (I'll have a SBCS and a bunch of builtins), but I mainly want to try the concept of having FSMs as the main datatype

noodle man

hm interesting

but if its just "somewhat" supposed to be a golfing language then why add a bunch of builtins?

zoomlogo

15:01

@TheEmptyStringPhotographer i don't think thats how it works

Command Master

@noodleman Correction: it's supposed to be a golfing language, I'm just not sure if it will be particularly good because "FSM as the main datatype" might mean cumbersome code - it don't think it will have numbers other than the nonnegative integers (which will be represented in unary), for example.

noodle man

i see

but at that point it might be more interesting if you just give it a handful of built-ins

20 or 30 maybe

zoomlogo

15:19

@CommandMaster what is FSM?

Command Master

Finite state machine

math scat

@Neil Vyxal, 28 bytes: ‛!.F≠[‛, c[5⋎]Ṫ]kh:₍¡ǐȮ₍⇧⇩Jc

wonder there's a shorter regex based answer

zoomlogo

15:44

@CommandMaster oh

math scat

@noodleman returns truthy for "Hello, World" :d

noodle man

@mathscat isn't it supposed to be truthy for that??

math scat

> and if so then can optionally contain a ,

noodle man

oh wait i misread

ok so all of the versions i posted are wrong, lemme fix that

ok 99 bytes for a hotfix

typescriptlang.org/…

math scat

nice

1 hour later…

The Empty String Photographer

17:03

@zoomlogo all lists take the same amount of time to sort. Therefore it is O(1).

noodle man

17:20

yeah but that's not how big O works so no

Command Master

@TheEmptyStringPhotographer O(1) formally means that there is a constant C such that the time is bounded by C for all inputs. There is no such constant for your code because it runs forever for some inputs

Also max and remove are O(n)

noodle man