CodeWalrus

CodeWalrus Website => Contests => Topic started by: Yuki on August 15, 2017, 07:52:01 PM

Title: Code Golf Contest: The Pythagorean Problem
Post by: Yuki on August 15, 2017, 07:52:01 PM
Time for a code golf contest? Been a while we did that. Thought that'd be fun while I'm busy with other stuff. If you don't remember what it is, I give you a task and you try to write a program that is the shortest you can do. Standard rules apply, you can find them on Stack Overflow. If in doubt, like how to count the size of your entry, just ask me or anyone familiar with the previous contests we did before.

So yeah, this one revolves around Pythagorean triplets. If you don't know what it is either, it's any set of integers (a,b,c) that solves the formula a2 + b2 = c2. So if you take a point on a plane, say (3,4), it should be at a distance 5 from the origin (0,0). Same for (4,3). The point (3,5), though, is at a distance √34 from the origin, which is not an integer and therefore not Pythagorean.

So your task is, you are given a monochrome graphic screen (96x64 on a TI-83+, but could be anything big enough we can see something) with the origin (0,0) in a corner (usually upper left, but could be lower left) and you must turn on every pixel (a,b) that verifies a2 + b2 = c2 with a, b and c being integers, with the rest must be off. Don't miss one! I know there's a bunch of clever tricks to do that, so be creative.

Bonus task: Write another program that counts how many pixels are on this way for any width and height given as inputs.

Send the source code either in this thread on in PM to me before September 1st, 23:59:59 EST. and make it clear whether the codes you send are for the main task or the bonus one. There's nothing at stake other than the honor, feel free to help each other and have fun!

Standings

Main task

UserLanguageBytes
@SnektronShaderToy50
@JujuRuby60

Bonus task

UserLanguageBytes
@JujuRuby52

* Entries must be valid and verified before showing up in this table.
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: c4ooo on August 15, 2017, 08:27:04 PM
I don't understand, if (a,b) is the pixel coords what is c?
Am I supposed to check if sqrt(a*a+b*b) is an integer?
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: Yuki on August 15, 2017, 11:01:53 PM
Exactly. c a bit irrelevant as you can derive it from a and b, but yeah, pretty much.
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: kotu on August 15, 2017, 11:06:12 PM
Can I use C++
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: jamu on August 15, 2017, 11:08:33 PM
so this works in python?
import math
points = [(x,y) for x in range(1, 96) for y in range(1, 64) if math.sqrt(x * x + y * y).is_integer()]




producing this when scatter plotted:
(https://puu.sh/xb2ts/2e52cd366f.png)
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: kotu on August 15, 2017, 11:09:49 PM
Winner should be determined by processing time

*edit*
think i can do it about 4 or 5 characters shorter in c++builder (as the code that is added to a blank project with one control)
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: Yuki on August 16, 2017, 01:29:25 AM
Ideally, your program should be a complete, valid program you run (in cmd, bash or double-clicking it) that output a 96x64 image (or in the size you give as input) either on screen or in a file. So the scatter plot part should also be part of the program. Additionally, you'll want to save as much bytes as possible. You can use any programming language, but ideally it should fit in one file I compile/interpret and run. And of course, it shouldn't take 3 hours to run.
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: kotu on August 16, 2017, 02:21:50 AM
@Juju do you have Turbo C++ 2006? I might be able to make something pretty... meh
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: Yuki on August 16, 2017, 03:32:48 AM
Ideally, if you make it work with gcc, that'd be perfect. Also, the code you generated with the builder (that isn't in a third-party library) might count against the byte total.
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: kotu on August 16, 2017, 03:42:15 AM
I did it in * here is the code
f(096){f(064)


*C++Builder
(forgot about all the extra stuff I had to put in)
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: Yuki on August 16, 2017, 05:15:25 AM
Code (Ruby) Select

64.times{|v|96.times{|u|print((u*u+v*v)**0.5%1==0?"o":" ")}
puts}


This is a 65-byte solution in Ruby. You're supposed to paste that in a file and then just run it, that's it.

It prints a beautiful ASCII art thing:


oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
o                                                                                               
o                                                                                               
o   o                                                                                           
o  o                                                                                           
o           o                                                                                   
o       o                                                                                       
o                       o                                                                       
o     o        o                                                                               
o           o                           o                                                       
o                       o                                                                       
o                                                           o                                   
o    o   o      o                  o                                                           
o                                                                                   o           
o                                               o                                               
o       o           o               o                                                           
o           o                 o                                o                               
o                                                                                               
o                       o                                                       o               
o                                                                                               
o              o     o                          o                                               
o                   o       o                                           o                       
o                                                                                               
o                                                                                               
o      o  o       o             o            o                        o                         
o                                                           o                                   
o                                                                                               
o                                   o                                                           
o                    o                       o                                                 
o                                                                                               
o               o                       o                               o                       
o                                                                                               
o                       o                                   o                                   
o                                           o           o                                       
o                                                                                               
o           o                                                                       o           
o              o           o                    o                            o                 
o                                                                                               
o                                                                                               
o                                                   o                           o               
o        o                    o           o                                o                   
o                                                                                               
o                                       o               o                                       
o                                                                                               
o                                o                                                             
o                       o   o                               o                                   
o                                                                                               
o                                                                                               
o             o     o               o                  o        o                         o     
o                                                                                               
o                                                                                               
o                                                                   o                           
o                                      o                                                       
o                                                                                               
o                                                                       o                       
o                                               o                                               
o                                o        o                                               o     
o                                                                           o                   
o                                                                                               
o                                                                                               
o          o             o      o            o                 o                o          o   
o                                                                                               
o                                                                                               
o               o                                           o                       o           


Bonus:
Code (Ruby) Select

a=0
64.times{|v|96.times{|u|a+=1if(u*u+v*v)**0.5%1==0}}
p a

Code (Ruby) Select

p (0..6143).select{|n|((n%96)**2+(n/96)**2)**0.5%1==0}.size


Both 59 bytes in Ruby, gives out 249.
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: kotu on August 16, 2017, 09:27:11 AM
Thanks
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: Snektron on August 16, 2017, 11:41:34 AM

#define mainImage(O, U)O+=sign(fract(length(U-.5)))

50 chars / 51 bytes
view live on ShaderToy (https://www.shadertoy.com/view/ld2fWt)
its bigger than 64x96 though so you'll just have to resize your browser.
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: kotu on August 16, 2017, 11:54:42 AM
We all know it is impossible to tell if sqrt(x²+y²) is an integer or not, right?

Only humans can do that, really


..hmm
probably the best thing to do is store bools in a lookup table, start with 3x4, multiply that out (6x8, 9x12 etc)
bleah!

as a double blow i think the sqrt function is probably a numerical method
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: _iPhoenix_ on August 16, 2017, 02:17:10 PM
Uhh it is not impossible.
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: kotu on August 16, 2017, 02:36:11 PM
it is actually unless you have infinite bits of precision

*edit*
in fact if you zoom in or out of the common domain slightly or scroll around slightly, every boolean value in the 96x64 area could be untrue. its just quite unlikely

HMM

there are technically infinte number of places where this does in fact happen.
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: Yuki on August 17, 2017, 05:22:51 AM
Depending of the language you use, it is possible to check if your integer is an integer. As in, you can cast your float into an int, if it didn't lost information it's an integer.

Oh, also optimized my entries to 60 and 52 bytes respectively.

Code (Ruby) Select

64.times{|v|96.times{|u|$><<((u.i+v).abs%1==0??o:" ")}
puts}
Code (Ruby) Select

p (0..6143).select{|n|((n%96).i+n/96).abs%1==0}.size
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: Snektron on August 17, 2017, 11:35:21 AM
you havent updated the standings yet, juju
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: c4ooo on August 17, 2017, 02:15:48 PM
Quote from: Juju on August 17, 2017, 05:22:51 AM
Depending of the language you use, it is possible to check if your integer is an integer. As in, you can cast your float into an int, if it didn't lost information it's an integer.
Yep. In a float, the first byte is almost always a signed exponent, so as long as it is >=0 its an integer (unless I got something mixed up). This should be useful if someone does the challenge in assembly.

Edit: got 39 bytes in tibasic but its a very lazy solution lol. Will post code when I get time.
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: Snektron on August 17, 2017, 02:51:35 PM
Quote from: c4ooo on August 17, 2017, 02:15:48 PM
Quote from: Juju on August 17, 2017, 05:22:51 AM
Depending of the language you use, it is possible to check if your integer is an integer. As in, you can cast your float into an int, if it didn't lost information it's an integer.
Yep. In a float, the first byte is almost always a signed exponent, so as long as it is >=0 its an integer (unless I got something mixed up). This should be useful if someone does the challenge in assembly.

thats not true, because the mantissa (other part of the float) is a fraction part: (1/16 + 1/8)*2^3 is 1.5, but it still has a positive exponent.
Instead you could check if the mantissa is clone enough to zero: if its smaller than 0.00001 for example is probably an integer. I think most is_integer() functions will work this way.

My solution actually uses this:
#define mainImage(O, U)O+=sign(fract(length(U-.5)))
O is the output color, U is the input coodinate plus 0.5. length() is just sqrt(U.x*U.x + U.y*U.y).
fract takes the fraction part of the float (the mantissa). Sign(x) returns -1 if x < 0, 0 if x == 0 and 1 if x >0. I think the sign function internally also compares x to some small value.
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: Yuki on August 17, 2017, 05:03:40 PM
Quote from: Snektron on August 17, 2017, 11:35:21 AM
you havent updated the standings yet, juju
Ah yeah, forgot yours, thanks.
Title: Re: Code Golf Contest: The Pythagorean Problem
Post by: c4ooo on August 17, 2017, 05:22:35 PM
Quote from: Snektron on August 17, 2017, 02:51:35 PM
Quote from: c4ooo on August 17, 2017, 02:15:48 PM
Quote from: Juju on August 17, 2017, 05:22:51 AM
Depending of the language you use, it is possible to check if your integer is an integer. As in, you can cast your float into an int, if it didn't lost information it's an integer.
Yep. In a float, the first byte is almost always a signed exponent, so as long as it is >=0 its an integer (unless I got something mixed up). This should be useful if someone does the challenge in assembly.

thats not true, because the mantissa (other part of the float) is a fraction part: (1/16 + 1/8)*2^3 is 1.5, but it still has a positive exponent.
Instead you could check if the mantissa is clone enough to zero: if its smaller than 0.00001 for example is probably an integer.
Ohh well it works for tios floats. In my monochrome CE wrapper demo I had to convert floats to integers and I checked if the first byte was zero or one (meaning the float had one or two digits, respectively), and everything else was Out of bounds. But tios floats use BCD so I guess its a but different.