The Nineteenth Byte

Lembik

10:00

3-SAT not SAT-3 ! :)

orlp

@Lembik but try it :)

Lembik

did you use pbencoder?

I will try it!

orlp

@Lembik yes, but beware the numbers it generates at the start of the cnf file

not sure what they mean and you might have to remove them

Lembik

@orlp thanks.

there is probably a flag to get rid of them :)

I feel we have learnt something new :)

orlp

why?

Lembik

10:04

about encoding problems as PBS instances

had you done that before?

orlp

no, but in this case it really was simple

Lembik

yes it was!

orlp

all I did was matrix x vector multiply, but instead of multiplying I just generated terms

Lembik

right

I am intrigued to find out how efficient the end result will be

and how long it will take to solve them!

Sp3000

@trichoplax Can you check

NNWSWWESWNSSWNNENESWNNSNSSSEEWWSSWNEWSEENNSWWWEENNENNSESSWWNENNSNNWWSSEWNSEESES‌NEWSEENWENSWWNNSNSEWNSSNWESNWNESENNEEWNNNEESESEWNWSNNWEEESWENWWEEWENSWEWNWSNESSEW‌NSSESWNWSWNSSWNWWEEWEENENWNESWWWWNWESEENWWSNNEENNSNWNENEWSEWSWEEWSWNEWSNWSENNENNS‌EEENENSNNWSESESNWEWWWWNNWNNENWEWWNNSWWENNSESSEWENNESENW

orlp

10:11

@Sp3000 what challenge?

Sp3000

We're trying to see how feasible trichoplax's maze challenge (in the sandbox) is for 3x3

trichoplax

It's running the test now

Passes :)

Sp3000

Well that's 296...

trichoplax

302?

orlp

@Sp3000 linky

Sp3000

10:14

I think... the problem is SE adding invisible chars in

trichoplax

2

A: Sandbox for Proposed Challenges

Shortest Universal Maze Exit String code-challenge A maze on an N by N grid of square cells is defined by specifying whether each edge is a wall or not a wall. All outer edges are walls. One cell is defined as the start, and one cell is defined as the exit, and the exit is reachable from the st...

Sp3000

Try to filter out "NSEW" chars - you'll find there's only 296 of them

trichoplax

@Sp3000 I wondered that - 3 double character line separators would do it, and yet when I past it into python it comes out on one line...

Was that the problem with the 310 one earlier too?

Sp3000

And the reason why I was 10 off before was because I actually have else: instead of elif c == "W" for West (it's the last case)

Gonna change it to be more defensive

trichoplax

@Sp3000 Oh - so it works as long as there are no invalid characters?

I should change that too - especially for when answers come in from just anybody...

Sp3000

10:16

Before it would work even if you had other chars (it'd count as west) - fixed now though :P

Lesson learnt

trichoplax

296 - you were right I just needed to filter out other characters

Sp3000

Damnit SE :P

Using previous solutions as seeds, I'm getting better and better solutions now though

trichoplax

Seeds? Are you just changing characters at random and seeing if they still work?

Sp3000

Oops I sorta lied - I've actually got a GA over here. But since I was starting with a large initial population earlier so that it finished after the initial population was generated, that's why I said it was random

trichoplax

I'm going to try a jsfiddle validator with hardcoded mazes to cut out the start up time, and if that works I'll consider posting with 3x3

Sp3000

10:20

I should really hardcode the mazes too :P But it only takes a few seconds to generate them all, so I haven't bothered yet

(btw the GA doesn't actually do well at all on its own, in case you're wondering)

trichoplax

It only takes a few seconds for me too, so I'm torn between a fast jsfiddle and a slow stack snippet to avoid sending people off site

orlp

hrm, how I see this problem

trichoplax

I suppose I could load the mazes from an external source into a stack snippet

orlp

is that every maze has an associated infinite set of all finite inputs that solve it

the problem is then to find the shortest common element of all those sets

trichoplax

Yes - that's equivalent.

Sp3000

10:24

With that view an incremental approach would probably do better - I'm feeling lazy atm though :P

orlp

if you order the infinite sets lexicographically

trichoplax

If I was answering I'd be tempted to try xnor's approach from puzzling and then try to cut it down, but for testing the viability of the question that's not going to help me

orlp

the problem reduces to first common element

@trichoplax haven't you guys already found valid ~300 character solutions?

what's there to test about the viability?

Sp3000

I'm assuming by lexicographically you mean by length first

orlp

it seems viable to me

@Sp3000 lexicographically implies length

"tes" < "test"

Sp3000

10:26

I thought lexicograpically implies a then aa then b

trichoplax

@orlp It's answerable, but my concern is that it may be optimally answerable, at which point the competition ends

orlp

oh right

not lexicographically

@trichoplax that is fine

trichoplax

Whatever the name for the ordering you were thinking, that would work...

orlp

and optimal answers are interesting and generate upvotes

trichoplax

@orlp Yes I don't mind an optimal answer eventually, but I had a challenge recently which was optimally answered within an hour... :(

orlp

10:27

just go for it

@trichoplax don't worry about it

trichoplax

With this one I'm guessing an optimal answer will take weeks to months, so I'm close to posting with size 3x3.

Sp3000

Well at least you won't get an hour for this one. A day? Maybe. Probably not an hour though

orlp

you guys have been at it for more than an hour

tested enough, let's go :D

put it on the site

Sp3000

Eager to start or something?

:P

trichoplax

Then all I need to do is translate my validator from python to javascript then I can post...

orlp

10:29

@trichoplax you don't

isn't the validator going to be prohibitively slow in javascript?

besides, it's fine to use python

you can always add the validator later

trichoplax

I know I could post with the python validator, but I like having a validator built into the question

So people don't have to download a language they are not using

orlp

by the way, how many maze configurations are there in 3x3?

Sp3000

138172

trichoplax

The slow part of the validator is generating all 138172 mazes ready for testing - the actual test will be less than a second even in javascript

Even generating them in javascript is realistic - I was only thinking of precalculating to avoid putting people off

Sp3000

Probably depends on the string if it fails early or late :P Or do all strings work under a second?

trichoplax

10:32

Obviously all strings can't work under a second :P

I may be exaggerating but the test certainly seems quicker than the maze generation for the ones we're testing here

Sp3000

No I mean, does testing any single string work under a second with yours? Cos if it does I need to make mine a bit more efficient :P

(PyPy's giving me massive speedups for this though)

trichoplax

@Sp3000 Yours isn't inefficient - I was misjudging the difference. I've just counted up and it's over 20 seconds for the maze generation and over 5 seconds for the latest (shortest) string

Python 3 without PyPy

The other nice thing about loading the mazes from an external source is that I won't have to rewrite as much of the code (better for me and better for reliability...)

Sp3000

Mine takes 3 seconds to check a valid string in CPython... also I'm up to 276 fyi

trichoplax

down to 276 ;)

Maybe I should post the question quick before you reach an optimal solution

Sp3000

I won't post for a while - if I've been working on a sandboxed question I try to wait for the amount of time I've spent on it

trichoplax

10:37

That's terribly good form

orlp

@Sp3000 could I see your maze generation / checking code?

you can keep your solution code secret :P

a 3x3 maze has 12 internal walls, right?

so 12 bits encodes on maze

trichoplax

Yes

orlp

well

plus start / end

start can be 9 locations, end can be 8

trichoplax

I happen to order mine as vertical walls in reading order followed by horizontal walls in reading order

orlp

so 294912 mazes, 19 bits

can we reduce some with rotational symmetry?

Sp3000

10:41

Here - it's not too bad for speed, considering it was an implementation I tried to get done ASAP

trichoplax

@orlp If you rotate a maze the same string of NESW won't necessarily solve it

orlp

@trichoplax it would if you cycle NESW to ESWN

Sp3000

You can exploit symmetry in the move string though, I guess

trichoplax

@orlp True

orlp

@trichoplax mazes where start == end are not valid mazes, right?

Sp3000

10:49

Even if they were, they'd be solvable by any string, so I've excluded them from the count

orlp

@Sp3000 no they're not

consider an empty maze

with the start and end in the topleft corner

S would fail to solve that

as it would not move over the topleft corner

Sp3000

I assumed that you "finish" a maze if you're on the finish square at any point in time, even before you make the first move

trichoplax

To avoid that problem (whether to check before moving), only mazes with a distinct start and exit are valid

orlp

ok

trichoplax

Actually it looks like I didn't make that explicit in the wording (although that's how I've been coding). I'll edit it now

orlp

11:32

haha

oh man this is going to be fast

int move(uint32_t maze, int pos, Move move) {
    int new_pos += 6*move - 2*(move > 1) - 8;
    if (new_pos < 2 || new_pos > 22) return pos;

    int idx = (pos + new_pos) / 2;
    uint32_t masks[] = {0, 0, 0, 1<<0, 0, 1<<1, 1<<2, 0, 1<<3, 0, 1<<4, 1<<5, 0,
                        1<<6, 1<<7, 0, 1<<8, 0, 1<<9, 1<<10, 0, 1<<11, 0, 0, 0};
    return (maze & masks[idx]) ? pos : new_pos;
}

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

The lost pawn problem After the chess game ended, a surviving pawn was left behind enemy lines. let's help him find the shortest way back home. The original problem describes a nXn "chess" board, and a function f: {1,..,n}X{1,..,n}X{1,2,3} => R+ of weights. the goal is to find the best path fro...

trichoplax

@orlp Wow. I really need to get on and post this ;)

Where's a reliable long term place to externally store a string of numbers to be accessed from a stack snippet?

feersum

11:47

Encoded in the pixels of an image :P

trichoplax

Interesting - so I could store it in the same Stack Exchange question....

orlp

I'm going to attempt a genetic algorithm

Sp3000

Good luck with that

orlp

you think it won't work?

Sp3000

I tried - it didn't give good results unless I initialised the population with actual solutions

You might have a better approach though, I dunno

orlp

11:56

what fitness function did you use?

Sp3000

Number of mazes solved

orlp

@Sp3000 with secondary fitness length?

how well did it work once you got a decent seed population?

Sp3000

Didn't have a secondary - how well it worked depended on how lucky I got, because it depends on how many useless chars could be trimmed off the string

orlp

I was thinking of doing random manipulations

such as adding characters

removing characters

modifying characters

Sp3000

I tried the first and third, not the last. I dunno - tell me how it goes :)

orlp

12:00

what is your current approach?

if not genetic

feersum

what size of grid are you working on?

Sp3000

Incremental

@trichoplax Something to consider, < 150 is possible. Are you sure you don't want 3x4?

trichoplax

Hmmm. I don't know

How long did you take to find sub 150?

Sp3000

A few seconds

trichoplax

????!??

Interesting

Sp3000

12:04

It's deterministic though, so improving it might be harder

orlp

@Sp3000 please, just keep it at 3x3

stuff explodes fast

trichoplax

I still think 3x3 will be tough to make optimal

orlp

tough enough

if you make challenges too hard no one competes

trichoplax

I'd be surprised if it's cracked in the first month

Sp3000

There's only 7 mil 3x4s, so it doesn't go up by that much fyi

4x4 explodes though

feersum

12:05

nobody posts anything in other months

orlp

I like 3x3

trichoplax

My guess is that the shorter the string you search for, the fewer there will be that are valid, so the longer it will take (even though there are fewer strings overall)

feersum

3x3 seems kinda smallish

trichoplax

I like that it seems smallish. People will be fooled into trying to beat it :)

feersum

might have problems that it's impossible to beat the first posted answer

trichoplax

12:06

That is exactly what I want to avoid.

So far in chat there has been a gradual improvement, so I'm hopeful that there will be plenty of answers before the supply of strings dries up

And I'll be throwing bounty at it when it slows down

orlp

@Sp3000 could you give me a longish string that solves all mazes so I can test my fitness function?

my fitness code is really elegant

Sp3000

There's a few if you scroll up a bit

Just filter out for NSEW cos SE seems to add invisible chars or something

orlp

what do you mean

trichoplax

line breaks add extra characters

orlp

oh I see it in vim

trichoplax

12:13

I can manage switching between coding in python and javascript, but trying to translate one to the other I'm getting colons and braces everywhere

New Main Posts

12:23

0

Q: Draw an ASCII Checkerboard

Summary Inspired by the recent popularity of ASCII art challenges, this challenge's purpose is to draw an ASCII checkerboard, like one on which Chess can be played. Write a program that takes a positive integer n as an argument, in stdin, or as user input, and output an checkerboard with nxn sq...

randomra

what is the opposite of "greatest number"?

trichoplax

least number?

smallest number?

orlp

0

or negative infinity

trichoplax

dullest number?

orlp

guys, what is the least interesting number?

Sp3000

12:29

I normally use smallest

orlp

lowest

trichoplax

Fleventy Five

orlp

smallest

tiniest

randomra

I meant as a synonym for smallest, as smallest-largest, ???-greatest

orlp

least

small, smaller, smallest

trichoplax

12:30

greatest means biggest or largest - they are from different roots but mean the same thing, so any of smallest, least, lowest

randomra

does least means the same?

as in "choose the least number possible" == "choose the smallest number possible"

Lembik

but fewest and least are different :)

trichoplax

Not in English, but I can't see a way it would differ in mathematics

orlp

@Sp3000 could you gist one of your valid solutions

I'm paranoid se chat is messing something up

Lembik

"least interesting number" is ambiguous

trichoplax

12:32

Neither means less than zero, which is the only ambiguity I can imagine

orlp

@Lembik no, it's a contradiction :)

trichoplax

"least interesting number" is an interesting distinction

Lembik

it is either the number that is least interesting or the smallest number which is still interesting

trichoplax

Oh I see

Lembik

:)

trichoplax

12:33

I don't think there are any uninteresting numbers

Lembik

is -1 smaller than 5 ? :)

@trichoplax you can prove it too!

trichoplax

@Lembik Yes, by both definitions :P

Lembik

I am not clear what small means wrt a number

trichoplax

-1<5

Lembik

can it be applied to negative numbers at all?

trichoplax

12:34

|-1|<|5|

Lembik

-6 < 5 ?

Sp3000

Depends if the set you're talking about has a well defined ordering

Lembik

well... it depends if smallness defines a well defined ordering on the set you're talking about

Sp3000

@orlp pastebin.com/xvKmBGJN

Lembik

the integers certainly have at least one well defined ordering

it's just not clear that smallness does it

trichoplax

12:36

I always take "less than" to mean <

Lembik

although I like the idea that -6 is bigger than 5

@trichoplax me too

trichoplax

With smaller than it could be either < or ||<||

Lembik

the problem is small and big :)

right

for example, the matrix with the biggest determinant

trichoplax

Usually the context makes it clear. Where is doesn't, vote to close

Lembik

in any case.. :)

orlp

12:42

for some reason it reports to only solve 175036 mazes

trichoplax

That's more than all of them...

orlp

no?

trichoplax

It only needs to solve the valid ones

orlp

there's 331776 mazes

Sp3000

138172

orlp

12:44

no

12 walls

9 start positions

9 end positions

2**12 * 9 * 9 = 331776

whether or not you include start == end is another thing, but that's still way more than 138172

trichoplax

138172 of them have the exit reachable from the start

orlp

ah

trichoplax

:)

If the exit is boxed in you don't need to be able to solve that maze

I don't have a formula for the valid mazes - I just found them by flood fill from the start to see if it finds the exit

orlp

oh, I'm actually checking the input string on all mazes

I probably shouldn't ye

but it shouldn't matter - it still means my code is bugged

does that 138172 figure include mazes where start == end

trichoplax

No those are invalid too

There may be nothing else wrong with your code - it simply can't work if you include unsolvable mazes

Sp3000

12:48

I don't think it's bugged - if you take out start == end I think the number's right

Since you're off by 9 * 2^12

orlp

ah yes

its correct my code

Optimizer

wow, getting a binary checkerboard is so non-trivial

orlp

@Optimizer yes it is?

you start with the top row and then you shift back / forth and add 1 every other row

trichoplax

85, 170, 85, 170, 85, 170, 85, 170?

orlp

or isn't that what you meant?

Sp3000

12:55

I'm assuming Optimizer means the new challenge?

Geobits

We now have a challenge posted for just counting and formatting in binary?

Without even excluding builtin string formatting stuff?

Optimizer

god, 61 bytes

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Distinct Sums You should write a program or function which receives an integers as input and returns two integers whose sum is the first one. There is one further requirement: no number can be part of the output for two different inputs. Details You should be able to handle inputs for at lea...

New Main Posts

0

Q: Pronouncing Hex

Pronouncing Hex For those of you uninitiated with the show Silicon Valley, this challenge is inspired by an exchange that goes like this: Kid - Here it is: Bit… soup. It’s like alphabet soup, BUT… it’s ones and zeros instead of letters. Erlich Bachman - {silence} Kid - ‘Cause it’s bina...

code-golf

Optimizer

Alex should change his name to The commenter

Sp3000

13:10

61 seems really excessive for the checkerboard o_O

randomra

in Cjam?

Sp3000

I'm assuming so, cos Optimizer

randomra

I thought you can write a whole chess program in 61 bytes :P

Optimizer

whole chess program can be done in lesser.

59 now

I am just gonna post it and don't worry about getting my ass kicked by jimmy or Dennis later

randomra

@Optimizer time to pyth?

Optimizer

13:16

nah.

I'm good with 1 in 20 answers for Pyth

Geobits

@Vioz- Serious question: What the fleventy-eff is a bitey?

Optimizer

its your dickety

Phyre

"0x3C4F" -> "Thirty-cee bitey forty-dee" should be "0x3C4F" -> "Thirty-cee bitey forty-eff". I couldn't find other edits to do?

Vioz-

Good catch :P

Phyre

I was having a lot of fun pronouncing them ha ha

Optimizer

13:21

I've never given that many f in a single answer...

Sp3000

My first try was 49 o_O

Optimizer

in CJam ?

Sp3000

Yeah

Optimizer

well, then I am really being dumb here

Sp3000

Still thinking there's got to be a nicer way though

Optimizer

13:22

whats ur current code ?

Sp3000

Build line by line

Nothing fancy

Optimizer

it works fine for input 2 ?

Sp3000

I think so

Optimizer

as in , 0110 instead of 0101

Vioz-

Well now I gotta fix mine so it works with odd numbers :P

Sp3000

13:24

0110?

Optimizer

01
10

Sp3000

Oh right, yeah

Optimizer

nice. post it then

Sp3000

Done

Hmm fmd gives a flat array, damn

randomra

hmm, 110 bytes in Retina seems postable

probably under 100 after golfing

orlp

13:36

@Sp3000 how long does it take it for your code to verify if a solution is valid?

Sp3000

Depends on the solution

orlp

on average?

or, say, the solution you sent me?

Sp3000

CPython, 3s. Haven't tested with PyPy

orlp

ouch

it takes my C++ 0.08 seconds

Sp3000

I didn't exactly optimise for speed -_- you don't need to compare

orlp

13:37

and that include generating the mazes

Optimizer

orlp is uselessly extra competitive :D

orlp

I get this speed because the way I represent positions and mazes is pretty smart

2,  4,  6
10, 12, 14
18, 20, 22

that's what my positions look like

then I map NSWE like this: N: -8, E: 2, S: 8, W: -2

then to calculate a wall index you can just average old pos + new pos

for example 12, 20 becomes 16

then I index that into a mask array, which then masks the wall (encoded as bits in an integer), and a simple AND determines if there was a collision

trichoplax

@orlp Since your code is so fast, would you like to brute force strings starting from shortest and see if you can find the shortest possible valid string? If you can't, then I'll know my question is safe to post :)

orlp

@trichoplax highly unlikely

even if the string is as short as 32, that's still a 64 bit bruteforce

trichoplax

So even with your super fast code you think 3x3 is a good size?

orlp

13:47

yes

trichoplax

Excellent

Back to my javascript validator then...

Geobits

13:59

Hmm. Chopping off a few toes would make it much easier to multiply in hex. Base 20 just isn't a thing :(

Transcript for