The Nineteenth Byte

1:16 AM

0

Can I exit the maze with this many bombs? code-golf grid maze decision-problem path-finding Inspired by this Puzzling challenge, and easier version of my previous challenge. Challenge A 2D rectangular grid is given, where each cell is either an empty space or a wall. You start at the top left cel...

New Main Posts

1:27 AM

0

Q: Solve the Trolley Problem with Multitrack Drifting

Programmers have already solved the trolley problem. In the usual trolley problem, we have a directed graph and each edge is weighted by the number of people tied to the track (edge). The objective of the usual trolley problem is to find a path through the graph that minimizes the number of peopl...

graph-theory

New Sandboxed Posts

2:30 AM

0

A: Sandbox for Proposed Challenges

Write an ASPIF (clasp's ASP input format) program to find a maximum cap set (https://en.wikipedia.org/wiki/Cap_set) for 4 dimensions. Share the code you used to generate the ASPIF rather than ASPIF itself. This may be an ASP program. Winner is smallest word-count (according to wc) in ASPIF format...

user202729

3:39 AM

Regarding "comma to make the score more readable": it would be equally "readable" if the score is the log of the expected number of steps.

Feel that a recursive approach would be better.

What is the optimal tree configuration?

Jo King

4:50 AM

@SE-stopfiringthegoodguys I'd do it by putting the input into the program itself, then erasing the "interpreter" part and just running the program

i just can't figure out how you would erase the final p of the program

Lyxal

5:34 AM

Hey, anyone here interested in a nice game of Mornington Crescent? We can play with the Original Modern Rules if that makes it easier.

Just remember: diagonals count double when zones 1 and 2 are quartered.

For those playing, I'll make the first move: Oxford Circus (a rather classical opening really).

And if you are playing along, make sure to place your moves in **bold**

Raghu Ranganathan

6:00 AM

for some reason the pyth interpreter is throwing an error no matter what i run

it says unexpected EOF

and import not found

@Lyxal

Is mornington crescent and actual playable game?

2

looks like scotland yard

Lyxal

@RaghuRanganathan well not really. There are no rules, but needless to say, it is still a good exercise in imaginative thinking so to say.

Raghu Ranganathan

looks funny to me

Lyxal

Well, are you going to declare your home station?

Because I strongly recommend you start off with a slightly defensive opening if it's your first game.

Raghu Ranganathan

uh sure

I need a video with this thing's gameplay

Green Park

Lyxal

@RaghuRanganathan outstanding first move! I say, you're an absolute natural at this!

HighlyRadioactive

6:17 AM

@RaghuRanganathan Let's compete with 1+ and MAWP 1.1

Because both of them are easy to use but have a highly restricted set of instructions

Raghu Ranganathan

lol sure I guess

So whats your second move Flowey

somehow the stations in this maplook like friendliness pellets

Lyxal

@RaghuRanganathan an understrile to Tooting Bec,

Raghu Ranganathan

Castle Kingside to KnightsBridge

Lyxal

6:33 AM

@RaghuRanganathan Well, I'll just play High Barnet to throw a spanner in the works! (this has good info about the "game")

Raghu Ranganathan

thanks

Legendary figures in the game's history. HA

2

Lyxal

@RaghuRanganathan I strongly recommend using this map.

Raghu Ranganathan

so whats the ruleset we playing by?

3

Lyxal

Well, as I stated before, we're playing the Original Modern Rules

HighlyRadioactive

You shall create a seperate room for games

Lyxal

6:41 AM

@HighlyRadioactive I tried that once, but nobody came.

HighlyRadioactive

'Cause this really isn't "General discussion for codegolf.stackexchange.com"

@Lyxal Really?

Now that you have someone to play with, just invite him.

~~I tried creating an 1+ chatroom once, but nobody came.~~

Lyxal

@HighlyRadioactive the but nobody came was an Undertale reference

HighlyRadioactive

IK.

APL doesn't have a prime built-in or am I missing something?

(I'm using it for real life now)

(But as a newbie it doesn't really "fasten" the program-creating speed)

@RaghuRanganathan ~~Turth~~ Truth-Machine: 10 (1+) vs 14 (MAWP)

Raghu Ranganathan

Idk much about 1+

but it's probably a better language for golfing

HighlyRadioactive

No

It doesn't even have a subtraction built-in!

Raghu Ranganathan

6:48 AM

lol wat

amazing

user202729

Something about the "tents and trees" challenge: Planar 3-SAT is NP-hard.

This one isn't exactly equivalent to 3-SAT, but it's close.

HighlyRadioactive

@RaghuRanganathan Aaaand the best subtraction function I could come up with is this long:

(Subtraction|11+1<11+##1+^1+^11+#/"/^"/^\\<11+*1+\^#)

~~This is terrible and I'm very sorry.~~

Raghu Ranganathan

beautiful

HighlyRadioactive

So it's not good at golfing at all!!

Raghu Ranganathan

how nice

HighlyRadioactive

6:53 AM

Cat got your keyboard?

~~As in "Cat Program"~~

Ok I'll draw an ASCII-art "Rainbow" with 1+ today

in order to compete

Raghu Ranganathan

sure if you really like torture go on

HighlyRadioactive

~~Rainbow sounds gay for whatever reason~~

@RaghuRanganathan WTF is torture

Raghu Ranganathan

Rainbow sounds gay for ~~whatever reason~~ obvious reasons

HighlyRadioactive

Use ---

Three dashes (Ohh nice soo on-topic)

Raghu Ranganathan

torture aka pain

but more condensed

HighlyRadioactive

6:59 AM

@RaghuRanganathan So what does "sure if you relaly like torture go on" mean here

~~Raghu Ranganathan sounds gay for obvious reasons~~

Raghu Ranganathan

It means that it's gonna be really hard to do it

HighlyRadioactive

Really?

user202729

It isn't really hard to encode planar 3-sat in tents and trees.

So it's NP-complete. -- Perhaps if it weren't I would post a polynomial time solution.

Raghu Ranganathan

Ye I mean I'm new to this so maybe

Bubbler

@user202729 Time to publish a paper on it, because everyone else does with "<insert a random puzzle here> is NP-complete"

Lyxal

7:02 AM

For those interested: We've a new Mornington Crescent chat room: chat.stackexchange.com/rooms/111529/mornington-crescent

Raghu Ranganathan

I'll try learning 1+

user202729

Can anyone make a leader board script for codegolf.stackexchange.com/questions/209161/… ?

(although I guess newer submissions are always better than older ones)

So far it's true.

Raghu Ranganathan

Isn't there a premade leaderboard scipt for questions

user202729

@RaghuRanganathan This is one, but for code golf.

Raghu Ranganathan

ok so you need a modified one eh

HighlyRadioactive

7:10 AM

@RaghuRanganathan No otherwies you

will outgolf me

Oops pressed enter too early

Raghu Ranganathan

Bruh

I just started like 3 days ago

HighlyRadioactive

But all of my 1+ programs are poorly golfed

user202729

flag as no effort

The judge is rather computationally intensive. It takes a few seconds to compute one.

Perhaps it can be sped up by a little by porting it to C++ and use some challenge-specific info...?

Raghu Ranganathan

You always get outgolfed

that's just usual

get used to it, and steal from the best answers next time you golf

Raghu Ranganathan

7:34 AM

@HighlyRadioactive

In the how many 1's we get I can't recieve a range

MAWP only takes in single digits

HighlyRadioactive

7:47 AM

@RaghuRanganathan 6942 = ((6 * 10 + 9) * 10 + 4) * 10 + 2

This way

Raghu Ranganathan

8:04 AM

range brudda

theres a single line of input

Neil

9:58 AM

@NewMainPosts just out of interest, I tried a 16x16 maze. I added in the herringbone pattern by hand until it stopped gaining score, then at each step I added in the wall that increased the score the most, until I could increase the score no further. I ended up with this:

@NewMainPosts tio.run/…

Bubbler

10:16 AM

@Neil What's the score?

Neil

@Bubbler 6594.775659130748

Bubbler

@Neil Well, just this gives 7126...

Neil

@Bubbler yeah, so much for my herringbone attempt

user202729

10:45 AM

What's the formula to compute the expected time for a tree?

Given a graph section that doesn't contain the endpoints, the expected time to enter the "open" edges is a linear combination of the expected time to exit those edges.

Neil

@Bubbler This is how my "best wall each time" algorithm fills in the next 3 rows:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
|   |   |       |       |               |               |       |
+   +   +   +   +   +   +---+   +   +   +---+   +   +   +---+   +
|                               |       |       |       |       |
+   +---+   +   +   +   +   +   +---+   +   +   +---+   +   +   +
|       |       |       |   |   |               |               |
+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

user202729

*plus a constant.

I think the formula for combining two trees look like this. (solving these by hand is hard.)

(can anyone confirm the formula?)

user202729

11:14 AM

Correction: f(T)=3+f(A)+f(B).

https://tio.run/##bZJbaxsxEIWfd36FwFBarNTZTZ5iBAppAylNE5KQFzEEkR07hl2tWcnGIPa3u6O9mDzkRfdzzjeDahs@qLZh826Pxwenr72nNgBQuSavYsylKDoZCykuhumy68Dt6n9NSereHvRtZUMgp3vBICvUn2bjtP4eZ1I80Z5aT3rWfVsMj34AhJaIzS@kWOVse8lzSuGws5z9wZalObzhlRrdDdytzMyYHFGpgxS8LBCliB3CZFsgwKpp611lVeyAXKnOcvjVGIiOYaXY22pHnUqb17RcglUcpNPBEobCzV9y6/ChrVI5pge3m9YHbfl@u2XLl8aMGYxseEhiZmK83l4pDpWQjW4JIp3gUqRlnyTO@X5lBiaL816HCDKeyKRIDeLaevzPlJzziTAFfYE1Mp/g8vkUN95w6yBj66/EDf@H9iSFLMvn92SdmSxmyA2/sZ58Kv/34Z22QfciriFDGUcDy/hTUVLcNPW2oppcME/WrUmPX2hEWuhUMHasAK@em2pPExPCY7txQfthZg5GPlXCjeEtLn56PB7/Aw

For 3 trees, it's 4+f1+f2+f3.

Chain.
https://tio.run/##bZLbahsxEIavd55CYCgtVuru5nBRI1BJG2hp2pKE3ghRhuysY9jVmpVsDGKf3R3tweQiNzqN/vm/GabB8EINhu0znk6/nf7iPXUBgMoNeRVjLkXRy1hIccnbpRRX4@16vN30PYSOiH9eS1Hl/HrDe5JcSXGRpzB2GwoqViblsj2A2ze/2pLUPR71XY0hkNOD3@haqB/t1mn9Pi6keKADdZ70on@3Gj99AMCyNMd/9rOa1Aa@V2ZhTG6tUkcp@FhYK0XsLcyywgJUbdfsa1SxB3Klusjha2sgOoaR4oD1nnqVLn/TcQ2o2EinhzWMfTE/yW3Ci0alcps@3G07HzRyfLfjlE@tmTy4CYaXJGYmxhvSK8WmErIpW4JIL3Yt0nFwEp84XpmRCe1y0FkLMp7JpEgt59oG/NeU7POKMBm9gTUxn@Hy5Ww3Rbh1kHHqt8Qtj0t3lkKW5ct7QmfmFAvLDb9FTz6V/@34TLugBxHXkFkZpwTI@HNRUty2za6mhlwwD@g2pKcRmZBWOhXMo8Mle/XY1geamSz86bYuaD/uZpy21UdvT6f/

Expected time { (1->2) -> end } = 17/3 + f(A) + (2*f(B))/3}

Similarly for 3 trees on the chain it's 10 + (4*f1)/3 + f2 + (2*f3)/3

https://tio.run/##bZJva9swEMZf@z6FIDA2ojaz@5cGgUa3wsa6lrbsjRBD1Oc0YMvBUkJA@LNnJ8sOfdE3Pvmke57fHdcY/4aN8etXczg8WPnNOew8AJYrdCKEnLOi56Hg7IzCGWfnFM45u0jJy5S8SsnrvgffIVLdJWdVTtkrilHgmmJUuODsJI/PTLdCL0KlooPuAey2@dOWKO7NXt7Vxnu0cqBILIX41a6tlJ/DjLMn3GHnUM76T4v06AuAKUu1/6dvxFit4GelZkrlWgux54yOhdachV7DVFZogKrtmm1tROgBbSlOcvjeKgiWYDjbmXqLvYg/f@NxCUaQkYyJJaRpqd9oV/5NGiFyHR/crTvnpaH7zYYkX1o1etAQFH1iMTER3iAvBJlyyEa1CBEzesnicXBiX@m@UonJ6PlQpzXwcCTjLI6eehvw31OSzzvCaPQB1sh8hMvnk914Q6ODjKQ/Km5pibpjKWRZPr9HY9UkMdM08Fvj0MX2f@xfcePlUEQ9ZJqH…

Which explains why starting with a huge empty block improves the score.

Balancing the size of the initial block versus the final chain would helps.

4 trees on the chain: 46/3 + (5*f1)/3 + (4*f2)/3 + f3 + (2*f4)/3

Cycles are harder to handle.

10+ for a 4-cycle before the tree.

edges={{1, 2},{2, 3},{2, 4},{4, 5},{5, 6},{3, 5}}
tree={{1, -1},{6, f1}}
target={f[1, 2]}

I don't believe it's possible to raise the factor above 1 (if it's possible, there would be an approach with exponential time)

edges={{1, 2},{2, 3},{2, 4},{3, 4},{7, 5},{8, 6},{7, 8},{3, 7},{4, 8},{7, 9},{8, 9},{7, 10},{8, 10},{9, 10},{3, 8}}
tree={{1, -1},{5, f1},{6, f2}}
target={f[1, 2]}

Every added edge adds 2 to the score regardless of their position?...

edges={{1, 2},{2, 3},{2, 4},{3, 5},{4, 6},{3, 4},{3, 7},{4, 7},{2, 7}}
tree={{1, -1},{5, f1},{6, f2}}
target={f[1, 2]}

Neil

11:53 AM

@Bubbler I started with four horizontal lines and ended up with this scoring 12876.37901702563: tio.run/##S0oszvj/Pzmx5P9/…

Neil

12:08 PM

@Bubbler I added in three rows of tines and it results in this scoring 13343.53950237764: tio.run/##S0oszvj/Pzmx5P9/…

Neil

1:01 PM

@Bubbler I like the E endings; I'm up to 21932175.644327864 on a size 100 grid.

user202729

1:22 PM

Finding patterns is easy. Proving the correctness is hard. I still can't prove why the value of a component is (2*number of edges+1).

Also how to compute the expected time in this case?

user202729

2:01 PM

It's something like 4+(f1+2 f2)/3. Not easy to understand.

https://tio.run/##dVNNa9wwED17foXJQmlZtYu9yaVBoJJtaErTlrT0IkQQ8XhjsGVjaRcX49@@Gdmym8P2Ys@H3pv3xnKl3TNW2hVP@nT6YcQna7F1AJjt0fK@T1icDqxPWbyl15bFV1N2OWWXwwCuRZxO5kWHmcgT6l0tWeqP6HaPjve59HyKepI4kjHwnGNAkK0aIK/b6lBq3g8A5lB9rzPk97oTt6V2Do0YlU36Uv61LowQb/sVix/wiK1FsRrebKZD7wB0lsnuUX3kAS3hLpcrKROlOO9YTGGqaHo/KJhhqQLybzL@PoFdLaE3JIHFR10ecOA@@ePDa9Cc6IUvXMO0N/kNzd49C815ovyB26K1TmjqNw1R/q5lsOcN08ODSQmJ@oI6E@MMzvm4OgbRBB@rlOVyUqLVeiwpBaxf9LDYfwjyMYp@rY3YX@kionNigtJFUrKex4UOrQkioj4HrukStQsUoihZ36M2cqZYKVrujbZovenP3RM2Towg8hAp1gcCTfJnUyy@qaumxAq…

Neil

8:17 PM

@Bubbler I've added six more walls, this now increases my score to 21933913.383284084 I think

Neil

9:28 PM

@Bubbler well that was weird... I filled in all the gaps manually and my score went up even further... will post once I confirm it

Transcript for