Search found 206 matches

by Lopsidation
Thu Apr 16, 2015 3:51 pm UTC
Forum: Logic Puzzles
Topic: Can't put a big box in a small box
Replies: 1
Views: 1685

Can't put a big box in a small box

1. Rectangle A contains rectangle B. Must the perimeter of A >= the perimeter of B? 2. The 3-dimensional box (ie rectangular prism) A contains the 3-dimensional box B. Must the surface area of A be at least that of B? What about the sum of edge lengths -- can B be more edgy than A? 3. The n-dimensio...
by Lopsidation
Sun Mar 01, 2015 3:34 pm UTC
Forum: Coding
Topic: genetic go bot
Replies: 6
Views: 3356

Re: genetic go bot

You may enjoy TD-gammon . It's a bot that learned how to play backgammon using a neural net. It worked using an algorithm called temporal difference learning. Two-sentence summary: you have a neural net N that predicts how well you're doing so far. If N says you're doing really well on position P, b...
by Lopsidation
Wed Feb 11, 2015 4:12 pm UTC
Forum: General
Topic: ITT: We make xkcd slightly worse.
Replies: 8651
Views: 1619148

Re: ITT: We make xkcd slightly worse.

by Lopsidation
Fri Feb 06, 2015 12:42 pm UTC
Forum: Computer Science
Topic: Mind Blowing Algorithms
Replies: 76
Views: 27488

Re: Mind Blowing Algorithms

I tried it, memoization speeds it up a lot. Adding memoization brings fib(10**7) from 7.896 seconds down to 0.278 seconds.

Apparently fib(10**7) makes 13333333 calls to fib, but it only calls fib on 79 distinct inputs.
by Lopsidation
Sun Jan 25, 2015 2:17 pm UTC
Forum: Logic Puzzles
Topic: Gambling with the magical genie
Replies: 27
Views: 6601

Re: Gambling with the magical genie

> inb4 religious debate in Logic Puzzles

Will the genie let me communicate with other players? If I ally with 10 other players, then we all make a big profit even if a few of us lose. In that case, I would take this bet after seeing maybe six other players win.
by Lopsidation
Mon Jan 19, 2015 6:03 pm UTC
Forum: Computer Science
Topic: Mind Blowing Algorithms
Replies: 76
Views: 27488

Re: Mind Blowing Algorithms

Casuals.

Code: Select all

def fib(n):
    if n<3: return [0,1,1][n]
    if n%2==0: return fib(n/2+1)**2-fib(n/2-1)**2
    return fib(n/2)**2+fib(n/2+1)**2

x = fib(1000000) # shots fired
by Lopsidation
Sat Jan 10, 2015 8:59 pm UTC
Forum: Mathematics
Topic: Finding a (large) primitive root of a 300-digit prime
Replies: 14
Views: 5722

Re: Finding a (large) primitive root of a 300-digit prime

Disclaimer: this works, but is probably not the fastest or standard way. Let p be a large prime. If you know the factorization of p-1, you can easily test whether a given number r is a primitive root mod p. [Fact: r is a primitive root mod p unlesss there is a prime factor F of p-1 such that r (...
by Lopsidation
Fri Jan 02, 2015 4:42 pm UTC
Forum: Mathematics
Topic: Numbers easy to factor
Replies: 40
Views: 5526

Re: Numbers easy to factor

You may want to look up the quadratic sieve, it has a similar idea to what you propose but with square numbers instead of triangular numbers. It's quite fast.
by Lopsidation
Tue Dec 30, 2014 1:38 pm UTC
Forum: Logic Puzzles
Topic: The infinite suburb and the teleporter breakdown.
Replies: 26
Views: 6704

Re: The infinite suburb and the teleporter breakdown.

@Cradarc: The point is to get to any location in a reasonable number of hops. If I can't visit my friend at (2158096541, 1805984859403) in less than a million hops, then what's the point of having teleporters? Also, solved ekim's "every house exactly once" problem. It is possible. First, I...
by Lopsidation
Sun Dec 28, 2014 11:58 pm UTC
Forum: Logic Puzzles
Topic: The infinite suburb and the teleporter breakdown.
Replies: 26
Views: 6704

Re: The infinite suburb and the teleporter breakdown.

Cradarc, your first solution takes linear time to get from point A to point B. I think both Nitrodon and I want a better travel time. If possible, a constant number of hops. And it doesn't look to me like Nitrodon's original three-hop solution uses all teleports of equal length. I didn't realize Nit...
by Lopsidation
Sun Dec 28, 2014 4:46 pm UTC
Forum: Logic Puzzles
Topic: The infinite suburb and the teleporter breakdown.
Replies: 26
Views: 6704

Re: The infinite suburb and the teleporter breakdown.

...the x and y distances of each teleport must be relatively prime. Two hops are always enough. This is because you can make any teleport where either the x or y distance is 1. So to get from (0,0) to (a,b), make a stop at (1,b-1). Here's a restriction: on any given journey,...
by Lopsidation
Sat Dec 27, 2014 9:35 pm UTC
Forum: Mathematics
Topic: Trick y way about factorization
Replies: 13
Views: 3039

Re: Trick y way about factorization

You may wish to look at existing factoring algorithms like Pollard's rho . Finding a fast factorization algorithm is a very difficult problem that thousands of people have worked on in the past. You're very unlikely to make progress on it without building on existing work. If you're trying this for ...
by Lopsidation
Fri Dec 26, 2014 2:17 pm UTC
Forum: Mathematics
Topic: Catanese Starburst
Replies: 5
Views: 2059

Re: Catanese Starburst

Elmach wrote:There are solutions (2, 4, 6 // 7, 8, 1, 9 // 10, 5, 17, 12, 14 // 13, 15, 19, 16 // 18, 11, 3)
But 7 is next to 8, breaking OP's rule 2.
by Lopsidation
Fri Dec 26, 2014 2:00 am UTC
Forum: Mathematics
Topic: Catanese Starburst
Replies: 5
Views: 2059

Re: Catanese Starburst

Brute force. Speed it up with backtracking or "WLOG this hex is 19". There won't be a nice mathematical argument.

EDIT: Are there even any solutions at all?
by Lopsidation
Wed Dec 24, 2014 7:57 pm UTC
Forum: Mathematics
Topic: Let us say x=y*cos(y), what does y equals in terms of x?
Replies: 6
Views: 1992

Re: Let us say x=y*cos(y), what does y equals in terms of x?

There's no inverse in terms of elementary functions. Either get lucky with your value of x, or use a numerical approximation.
by Lopsidation
Mon Dec 22, 2014 3:54 am UTC
Forum: Science
Topic: Longest night ever, but for which timezone?
Replies: 3
Views: 1727

Longest night ever, but for which timezone?

I heard that this solstice is the longest (or second longest) night ever (i.e. in the entire history of the Earth), because of the varying speed of the rotation of the Earth. It seems to me like this depends on which timezone you live in. Like, if your timezone's midnight lines up perfectly with the...
by Lopsidation
Thu Dec 11, 2014 2:55 am UTC
Forum: Fictional Science
Topic: two planets
Replies: 6
Views: 6225

Re: two planets

Cool puzzle. Here's an answer that may or may not work.
Spoiler:
Think about the order the spaceships/planets were built in. The space station will have more advanced technology towards the outside, the planet will (probably) have more advanced technology near the center.
by Lopsidation
Wed Dec 03, 2014 3:36 am UTC
Forum: Mathematics
Topic: Show us your articles! Or what's your Erdos number?
Replies: 185
Views: 255234

Re: Show us your articles! Or what's your Erdos number?

A fun paper about the complexity of the video game Braid. Link.

Some of you may remember this from the GISHWHES thread a billion years ago. (Long story short: Misha Collins never asked me to go on a pirate ship, so I chose not to give him an Erdos number of 3.)
by Lopsidation
Tue Nov 04, 2014 10:02 pm UTC
Forum: Logic Puzzles
Topic: Only Connect puzzles
Replies: 5
Views: 4046

Re: Only Connect puzzles

marzis is rocking these. He/she got everything except the "Colorado River" and "Barrel" puzzles. I can't accept that answer for the "Colorado River" category, because under the circumstances, it's much too tenuous a link.
by Lopsidation
Tue Nov 04, 2014 5:05 pm UTC
Forum: Logic Puzzles
Topic: Only Connect puzzles
Replies: 5
Views: 4046

Only Connect puzzles

Only Connect is a British quiz show about finding connections between a group of seemingly random clues. The difficulty ranges from fair to Geneva Convention-breakingly cruel. This post has a few of my favorite questions from the show, as well as one I snuck in myself. For category questions, you ha...
by Lopsidation
Fri Sep 26, 2014 5:43 pm UTC
Forum: Logic Puzzles
Topic: Eulerian paths in infinite graphs?
Replies: 15
Views: 6198

Re: Eulerian paths in infinite graphs?

Not sure what you're getting at, ekim; your example satisfies condition (b), and it has a Eulerian path. That having been said, I think condition (b) should read "there doesn't exist a finite subgraph whose removal partitions the graph into more than one infinite connected component." It's...
by Lopsidation
Mon Sep 08, 2014 3:10 pm UTC
Forum: Logic Puzzles
Topic: Prisoners and their enemies
Replies: 21
Views: 6444

Re: Prisoners and their enemies

Yes, that is true, Cauchy.

Spoiler:
Go ahead and color the vertices one by one. How could you possibly get stuck?
by Lopsidation
Sat Aug 09, 2014 5:57 pm UTC
Forum: General
Topic: How do you organize your files?
Replies: 21
Views: 7239

Re: How do you organize your files?

My folders are normal (e.g. C:/Users/Me/Desktop/School). My filenames... aren't. Some filenames I've used for school assignments: - encrypted_gorefic.doc - destroyNorway.py - gregory and the misadventures of mr froggy - christmas edition - cant spell discord without disco.pdf (note: complex analysis...
by Lopsidation
Fri Aug 08, 2014 1:23 pm UTC
Forum: Mathematics
Topic: GISHWHES Erdos Number challenge
Replies: 19
Views: 5558

Re: GISHWHES Erdos Number challenge

25. Video/Image Plagiarism - You shall not submit any items that were created by another team. Any team that is caught submitting another team’s item shall be eligible for disqualification. You may not submit any items that were taken before this year’s hunt. You may not submit any items that trigg...
by Lopsidation
Thu Aug 07, 2014 2:09 am UTC
Forum: Mathematics
Topic: GISHWHES Erdos Number challenge
Replies: 19
Views: 5558

Re: GISHWHES Erdos Number challenge

I can actually create this level! But I don't think you want to play it. First of all, it would take a long time to create, because the Riemann Hypothesis is a complicated statement. OK, let's say I encode a simpler statement, like the Goldbach conjecture. To beat this level, you would first run aro...
by Lopsidation
Thu Aug 07, 2014 1:00 am UTC
Forum: Mathematics
Topic: GISHWHES Erdos Number challenge
Replies: 19
Views: 5558

Re: GISHWHES Erdos Number challenge

Sorry for the double post, but I've finished a draft of the paper. You can find it here . I still have to look through it and comb for errors, sand the wording of some rough sentences, and hyper-quintuple-check that I didn't make any mistakes. Sections 1-4 are, for the most part, approachable for th...
by Lopsidation
Wed Aug 06, 2014 10:51 pm UTC
Forum: Mathematics
Topic: GISHWHES Erdos Number challenge
Replies: 19
Views: 5558

Re: GISHWHES Erdos Number challenge

That's true. I can always put the paper on my website with Misha Collins' name on it (and a note explaining the situation), and remove his name from the version I later submit to arxiv and CoRR. BTW, the paper will be finished tomorrow. It's ~16 pages long. The first half is approachable to readers ...
by Lopsidation
Wed Aug 06, 2014 9:13 pm UTC
Forum: Mathematics
Topic: GISHWHES Erdos Number challenge
Replies: 19
Views: 5558

Re: GISHWHES Erdos Number challenge

Tirian, I take it by your wording that you think this is a bad idea? Can you elaborate? Or am I taking your post the wrong way?

EDIT: Also, does anybody else think that this is a bad idea? I'm only an undergrad, and I don't want some big coauthorship scandal to kill my career.
by Lopsidation
Wed Aug 06, 2014 3:38 pm UTC
Forum: Mathematics
Topic: GISHWHES Erdos Number challenge
Replies: 19
Views: 5558

Re: GISHWHES Erdos Number challenge

Out of curiosity, is giving people who had essentially no contribution to the academic content of a paper coauthorship a standard thing? I doubt it. I have heard of cases where person A invents an interesting problem, and then person B solves it, and gives A coauthorship credit. I wouldn't be surpr...
by Lopsidation
Tue Aug 05, 2014 3:04 pm UTC
Forum: Mathematics
Topic: is mathematics a religion?
Replies: 82
Views: 15033

Re: is mathematics a religion?

I have a friend who believes that God created mathematics. That is, if God had chosen differently, the Fundamental Theorem Of Algebra might have been false, or maybe we'd be working in a system completely different from real numbers and integers. In that way, for my friend, mathematics has a religio...
by Lopsidation
Mon Aug 04, 2014 7:47 pm UTC
Forum: Logic Puzzles
Topic: Puzzle with cards
Replies: 2
Views: 2686

Re: Puzzle with cards

Here are the letters:

Code: Select all

f E N J x
H U p t i
G y A W m
R p d s G
S F f a

Though I bet the puzzle is "find the correct missing card and then convert it to a letter", in which case this is useless.
by Lopsidation
Mon Aug 04, 2014 4:33 pm UTC
Forum: Mathematics
Topic: GISHWHES Erdos Number challenge
Replies: 19
Views: 5558

Re: GISHWHES Erdos Number challenge

Hmm. This sounds like a worthy cause. I'm currently finishing up a paper about the computational complexity of the video game Braid . It's not the kind of research that will appear in a conference any time soon. But it was a surprisingly difficult question, so the paper should count for Erdos number...
by Lopsidation
Sun Jul 27, 2014 2:22 pm UTC
Forum: Mathematics
Topic: Is it possible for a math obsession to be unhealthy
Replies: 54
Views: 12586

Re: Is it possible for a math obsession to be unhealthy

I think it's important to find people who share and understand your obsession. Try out some math competitions. If you're in high school, take the AMC 10 or AMC 12, and/or join an ARML team. If you're in college, try the Putnam. If you're in middle school, do MathCounts. Warning: the problems may be ...
by Lopsidation
Mon Jul 21, 2014 12:58 pm UTC
Forum: General
Topic: ITT: We make xkcd slightly worse.
Replies: 8651
Views: 1619148

Re: ITT: We make xkcd slightly worse.

by Lopsidation
Thu Jul 10, 2014 4:11 pm UTC
Forum: Logic Puzzles
Topic: Lottery Ticket ................
Replies: 12
Views: 5333

Re: Lottery Ticket ................

Maybe some kind of Pigeonhole argument will help? If you split the 49 numbers into two groups of 24 and 25, then the winning ticket is guaranteed to have three numbers from at least one group. Maybe we can buy tickets to cover each group separately. One reason this is good is that it's a lot mor...
by Lopsidation
Mon Jul 07, 2014 12:01 am UTC
Forum: Coding
Topic: Python puzzles
Replies: 20
Views: 4895

Re: Python puzzles

Yeah, that's it! Huh, I didn't know it was implementation specific. Makes sense that other versions of Python can handle
Spoiler:
garbage collection
differently though.
by Lopsidation
Sun Jul 06, 2014 8:01 pm UTC
Forum: Coding
Topic: Python puzzles
Replies: 20
Views: 4895

Re: Python puzzles

Hint:
Spoiler:
My solution for #1 involves defining a new class, and setting x to an instance of that class. You might find this page helpful: A Guide To Python's Magic Methods. I learned a lot of stuff from that page -- I mean, useful stuff, not just ways to make Python do weird puzzle crap.
by Lopsidation
Fri Jul 04, 2014 11:08 pm UTC
Forum: Coding
Topic: Python puzzles
Replies: 20
Views: 4895

Re: Python puzzles

Grrr!
I'm embarrassed to say I didn't think of that.
It's not technically cheating, so... now we have two solutions!
by Lopsidation
Fri Jul 04, 2014 4:40 pm UTC
Forum: Coding
Topic: Python puzzles
Replies: 20
Views: 4895

Re: Python puzzles

Nice! Now that we have a solution, I'll give a tiny tiny hint for my intended method: I never redefine the literal "1", or the meaning of "=". And the line "x=1" executes normally: it's in the lowest indentation level, x is an ordinary global variable, and there'...

Go to advanced search