The Nineteenth Byte

Optimizer

5:00 PM

I am solely talking about the anime . "Maria the Virgin Witch"

Runer112

oh

Optimizer

I have no idea what "Maria Tidal Tug" means

the anime is the anti story of Virgin Mary

Runer112

just saying, I could totally see urban dictionary having some entry called "tidal tug" with an example like: Maria gave me a tidal tug behind the school yesterday

Maria Tidal Tug

@Runer112 you have a dirty mind ;-)

Optimizer

I can totally see it having now, if not yet

Runer112

5:02 PM

yeah... I'm not exactly proud of it

Maria Tidal Tug

actually it was just an anagram of DigitalTrauma for April 1

Geobits

Shoulda picked "I tug at Admiral" :P

Maria Tidal Tug

@Geobits "bog site" or simply "Ego bits"?

Optimizer

"Ego bits" is so apt

Geobits

As tempting as it was to use "ego", I'm Bigtoes. Blame Rainbolt for not being more creative if you like :P

Optimizer

5:08 PM

but tomorrow you can be an ego bit.. :P

Geobits

Tomorrow is Geobits Day, and I'll be celebrating appropriately.

Peter Taylor

@NathanMerrill Linear programming.

Maria Tidal Tug

Shameless plug - my first pyth attempt

0

A: Find the next 1-sparse binary number

Pyth, 10 bytes Borrowing the x & (x*2) algorithm from @alephalpha Borrowing Pyth boilerplate from @Jakube My first attempt at Pyth: f!.&T*T2hQ Try it here implicit: Q = input() f hQ find the first integer T >= Q + 1, that satisfies the ...

Peter Taylor

Ok, it's integer linear programming and not as nicely behaved as the rational version, but it expresses the problem concisely.

Runer112

A Data Rug Limit

Nathan Merrill

5:13 PM

@PeterTaylor I don't understand what you mean

Maria Tidal Tug

Sp3000

@MariaTidalTug y is double in Pyth

Maria Tidal Tug

@Sp3000 cool thanks!

Runer112

A Ritual Dig Mat

orlp

5:26 PM

12

Q: How do I get more Klotski in my life?

I really love sliding tile puzzles, but recently, I haven't had time for them. Hence, I need a program to give me my fix of sliding-tile puzzles, specifically Klotski puzzles. Your input will be in the following format: ####### #001gg# ##.222# .###### where # represents walls, . represents a...

^ I have a solution but CBA to golf it :(

2d golfs are so often annoying :P

Peter Taylor

@NathanMerrill Are you familiar with the area of optimisation called linear programming?

Nathan Merrill

@PeterTaylor no, I'm not

@orlp do it anyways :P

Peter Taylor

The basic scenario is: you have a set of variables x_1, ..., x_n. You have a set of inequalities which are linear in the x_i: e.g. 3 * x_1 + 4 * x_2 + 3 * x_3 >= 5. And you have an objective function linear in the x_i which you want to optimise: e.g. x_1 + x_2 + ... + x_n.

When your variables can be real or rational numbers, the optimisation can be done in polynomial time. When they have to be integers, it's NP-hard.

Nathan Merrill

by optimize you mean that the sum is minimized?

Peter Taylor

Typically, yes. Of course, you can maximise it by negating all of the coefficients.

orlp

5:35 PM

linear programming is useful in my mind, because it's trivial for humans to encode a lot of problems in terms of LP

it's also useless because it's often way too slow :P

Peter Taylor

The last time I used it was to find the Nash equilibria for the game of Morra.

TheBestOne

google.com/…

Nathan Merrill

well, since my problem does require integers, I guess its useful to know that its NP-hard

orlp

@NathanMerrill What is your problem?

Nathan Merrill

you are given an array of pre-defined integers. Your goal is to reduce all integers in the array to 0. The only method you have to reduce integers is to pick a position, reduce it by N, and reduce its immediate neighbors by M

N and M are predefined, and N > M

Peter Taylor

5:38 PM

Actually the reduction is the other way: ILP being hard doesn't necessarily mean that your problem is hard. (Although I suspect that it is).

orlp

@NathanMerrill Does a solution exist?

Nathan Merrill

yes

whether its NP-hard, I don't know

oh, sorry, when I said "to 0" I also meant it can go below 0

orlp

Don't think so

You can work from left-to-right, aggressively reducing possible combinations

Nathan Merrill

do I start with 0 or 1?

orlp

the first element can only be a certain amount of combinations of aM + bN

Nathan Merrill

5:41 PM

no, because the first element can go below 0

orlp

no?

you can only reduce

and the goal is to get to 0

Nathan Merrill

I didn't make that clear. It needs to go at least to 0

it can go below

orlp

then the solution is trivial

just reduce everything by a lot

Nathan Merrill

my goal is to minimize the number of moves I take

orlp

the goal seems to be changing every second :P

since N > M, I think the optimal solution is to always reduce the highest element

Nathan Merrill

5:43 PM

that won't work either

orlp

no, it doesn't

it will if N > 2*M though

Nathan Merrill

[2 3 4 3 2] N = 3 M = 2

orlp

or maybe 3*M

I strongly suspect this is not NP-hard though

Nathan Merrill

if you want to see the full problem description, its here: codeforces.com/problemset/problem/6/D

Doorknob

@PhiNotPi Hmm, that makes sense. @Calvin'sHobbies agreed?

TheBestOne

5:47 PM

I have a poll for red team for pixel wars here

Calvin's Hobbies

@Doorknob We may as well keep it undeleted as a staging area, but I am right now working on a proper test area integrated into the snippet.

Doorknob

Alright. Just flag again if you finish the testing thing.

orlp

@NathanMerrill here's a hint

@NathanMerrill Group up every 3 adjacent elements

So abcde becomes abc bcd cde

Then determine for each group the best solution

TheBestOne

@NathanMerrill I would kill the archers left to right.

orlp

then do one move in the group that had the worst best solution

and you only have to recalculate the solution for that group and the two adjacent groups to determine the next move

TheBestOne

5:55 PM

Never mind, that won't work.

Nathan Merrill

@orlp and if they tie?

orlp

@NathanMerrill then it doesn't matter

Nathan Merrill

@orlp yes it does

[2 3 4 3 2] N = 3 M = 2

all three will tie

but you should take the first or third, not the second

orlp

well

since you can't target either 2

there's more groups here

err

Nathan Merrill

you also should be making 5 groups

[9 2 2 2 9] N = 4 M = 2

orlp

5:57 PM

also, I don't see why it would matter

[2 3 4 3 2] N = 3 M = 2

[3 4 3]'s worst case is 2

so you hit the 3

[0 0 2 3 2]

Peter Taylor

If you consider that in groups of 3, [3 4 3]'s worst case of 2 can be achieved by hitting the 4 twice.

So that ties with the correct moves.

orlp

oh, a tie within a group

I thought between groups

Peter Taylor

It's also tying with the adjacent groups.

Nathan Merrill

[2 3 4] has a worst case of 2 as well

PhiNotPi

I'm going to be leaving on vacation next week. I am worried about losing my 66-day consecutive visit streak. What should I do?

2

orlp

5:59 PM

if there's a tie within a group

Nathan Merrill

lol

orlp

always prefer the move on the side

Geobits

@PhiNotPi Give me your password, obviously.

orlp

since that'll reduce other groups as well

Peter Taylor

@PhiNotPi, extract your cookies and set up a cron job with curl / wget.

orlp

6:00 PM

does that solve the issue?

Geobits

Or just cancel your plans. What's more important, a vacation or a fanatic badge?

Nathan Merrill

I don't think so, I'm trying to come up with a situation that it won't work on

Peter Taylor

@orpl, not really. The move in the middle reduces the other groups as well.

orlp

@PeterTaylor But not by as much

So the one on the side is preferred, if it doesn't affect the worst case moves of the group

Nathan Merrill

[4 2 4 2 4] N = 3 M = 2

I consider all 5, and they all get a score of 2

so I start with the second one?

orlp

6:03 PM

since all groups are worst case 2, you can start with either 2

[4 2] will result in 2

[2 4 2] will result in 2

2

Peter Taylor

But if you break the tie between groups by selecting a [4 2 4], your heuristic says that you should start with the 4.

Rainbolt

This is the best alter of a Magic card I've ever seen. Introducing, Taylor Swiftspear.

orlp

hmm

no, the tiebreaker doesn't quite work

I would definitely introduce a bit of preprocessing to make the problem a bit more uniform

since you can't target either end, I'd always use x/M moves on the 2nd and n-1th element

Nathan Merrill

wait, you can't target an end?

orlp

nope

says so in the problem you l inked

Nathan Merrill

6:12 PM

ah, you are right

orlp

then maybe you can do some sort of left-to-right algorithm

Nathan Merrill

regardless, you can still end up with the same situation

orlp

yeah

since if you have x elements

the leftmost element must either be cleared by targetting it directly or the element to the right of it

(and ofc combinations of the two)

order of operations doesn't matter at all

Nathan Merrill

[0 0 5 2 5 0 0] N = 5 M = 2

orlp

yeah I know, the tiebreaker doesn't work :P

Nathan Merrill

6:15 PM

that's not even a tiebreaker

2

orlp

actually, there it does work

Nathan Merrill

the element with the maximum number of moves is the center one, which is the wrong one to pick

2

orlp

[0 5 2] has a worst case of 1

2

err

2

right

2

nvm that algorithm all together

2

Rainbolt

This guy has ruined Christmas movies for me forever: worldbuilding.stackexchange.com/q/13495

2

Guys, Code Review has 21768 starred messages. We have 2306.

2

orlp

unacceptable

2

randomra

6:22 PM

what game you talk about? I can't find out

Nathan Merrill

we shouldn't go back to this: chat.stackexchange.com/transcript/240?m=19630884#19630884

2

Rainbolt

You think that's bad? Take a look at CR's chat right now. I linked it above.

Nathan Merrill

@randomra codeforces.com/problemset/problem/6/D

Rainbolt

Their starwall is like three times as tall

2

Nathan Merrill

XP

randomra

6:24 PM

thanks, checking...

Nathan Merrill

their chat had some missing spots, so I had to fill them

2

Hosch250

> You have fully used your vote allowance for today

orlp

@Hosch250 time to bring out the sockpuppet

Hosch250

@orlp I don't have one.

@Rainbolt StarredMessages += 40;

Rainbolt

6:41 PM

All of you who want to play StackEggs for fun vote on this proposal: meta.codereview.stackexchange.com/a/5175/36427

Geobits

I leave for 40 minutes and you guys trash the place. I'm calling all your parents.

13

VisualMelon

7:04 PM

hmm... my heuristic solver for codegolf.stackexchange.com/questions/48352/… seems to work better (and get results faster) when it adds and sorts (slow) then uses a binary insertion, I should have know that deviating away from a breadth first search would create problems, BFS is the only way to go

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

Build a minimum-clue Sudoku generator My attempt at stating this question, but with a more objective solving criterion. Your task is to build a program or function that taks a solved Sudoku grid S in the format of your choice and attempts to generate a problem grid with as few clues as possible...

randomra

@NathanMerrill a 16 (2*n-4) variable integer linear programming can solve this I think

edit: 8 (n-2) variable

Martin Büttner

oh god, not this again

4

randomra

7:19 PM

if you fix every second variable (attack number for every second archer) computing the rest is O(n), so total O(n * h^(n-2)/2) which is 500K step, well below the 2s time-limit

Optimizer

hey guys, you missed one up there in between, but I got ya

Peter Taylor

@MartinBüttner, I had hoped that the chat would be back to normal today. Sigh.

Martin Büttner

^ this

Optimizer

I blame Rainbolt

Rainbolt

7:43 PM

You called?

This is making me sad: