Omnimaga

Calculator Community => Contests => Community Contests => Topic started by: JWinslow23 on July 28, 2014, 03:29:31 pm

Title: [ENDED] Code Golf Contest #3
Post by: JWinslow23 on July 28, 2014, 03:29:31 pm

This is the same deal as the other two contests.

NEXT: Here (http://www.omnimaga.org/other-calculator-discussion-and-news/code-golf-contest-4)
PREVIOUS: Here (http://www.omnimaga.org/other-calculator-discussion-and-news/code-golf-contest-2)

Challenge 3

Problem
Make a program that, given an integer of reasonable size, outputs the greatest prime factor of that integer, in binary, but with all 0s replaced with underscores (_) and all 1s replaced with minus signs (-).

Deadline
August 4, 2014, 1:00 AM EST

Sample input 1
15
Sample output 1
-_-
Sample input 2
7
Sample output 2
---
Sample input 3
115
Sample output 3
-_---

If any further clarification is necessary, contact me or willrandship, and we will explain the best we can.

Ranking

TI-83+ BASIC

Rank	User	Size	Date	Code
1	Runer112	75	8/3/2014 2:17:19 PM	Spoiler For Spoiler: For(A,Ans,2,~1 If not(fPart(Ans/A A->P End "B For(A,0,log(P)/log(2 sub("_-",iPart(2fPart(P/2/2^A))+1,1)+Ans End sub(Ans,1,A
2	JWinslow23	90	7/29/2014 11:43:19 AM	Spoiler For Spoiler: Ans->X X=1->A While X>1 2->A While fPart(X/A IS>(A,X End X/A->X End "_ If A " Ans->Str1 While A "_ If fPart(.5A "- Ans+Str1->Str1 int(.5A->A End Str1

Python2

Rank	User	Size	Date	Code
1	willrandship	147	7/29/2014 12:51:41 AM	Spoiler For Spoiler: def f(z):  for y in range(2,z+1):   if z%y:continue   return z if y==z else f(z/y) a="" for c in bin(f(input()))[2:]:a+='-'if c=='1'else'_' print a

Ruby

Rank	User	Size	Date	Code
1	Juju	115	7/29/2014 2:47:50 AM	Spoiler For Spoiler: a=gets.to_f;b=2;while a>1;(c=a/b)==c.to_i&&(a=c)||b+=1 end;p b.to_s(2).gsub('0','_').gsub('1','-')

Nspire Lua

Rank	User	Size	Date	Code
1	Jens_K	132	8/1/2014 6:59:33 AM	Spoiler For Spoiler: n=0+clipboard.getText()f=n repeat f=(f>2 and f-1 or n)until n%f<1 b=""repeat b=(f%2>0 and"-"or"_")..b;f=(f-f%2)/2 until f<1 print(b)

SysRPL

Rank	User	Size	Date	Code
1	3298	59.5	7/31/2014 5:18:48 PM	Spoiler For Spoiler: ::   FPTR2 ^NFactorSpc   DUPLENCOMP  NTHCOMPDROP   FPTR2 ^Z>#   NULL$SWAP BEGIN     DUP #2/ UNROT BINT1 #AND     #1= ITE CHR_- CHR_UndScore >T$   SWAP #0=UNTIL DROP ;

Perl

Rank	User	Size	Date	Code
1	willrandship	98	7/31/2014 2:15:31 PM	Spoiler For Spoiler: $z=<>;sub f{for(2..$z){$z/=$z%$_?next:$_;return$z>1?&f:$_;}}$_=sprintf"%b",f;s/1/-/g;s/0/_/g;print

Haskell

Rank	User	Size	Date	Code
1	3298	122	8/3/2014 6:16:11 PM	Spoiler For Spoiler: import Numeric g i=showIntAtBase 2c(f(i,2))"" f(1,j)=j f(i,j)=if mod i j==0then f(quot i j,j)else f(i,j+1) c 0='_' c 1='-'
2	bb010g	216	8/2/2014 7:11:01 PM	Spoiler For Spoiler: import Numeric;import Data.Char;main=fmap(\n->concatMap(\case{'0'->"_";_->"-"})$showIntAtBase 2intToDigit(last[x|x<-[1..n-1],n`mod`x==0,elem x[n|n<-[2..x],not$elem n[j*k|j<-[2..n-1],k<-[2..n-1]]]])"")readLn>>=putStr

CJam

Rank	User	Size	Date	Code
1	Runer112	16	8/3/2014 2:17:19 PM	Spoiler For Spoiler: q~mfZ=2b{"_-"=}%

Golfscript

Rank	User	Size	Date	Code
1	Runer112	33	8/3/2014 2:17:19 PM	Spoiler For Spoiler: ~.,2>-1%{].~%!=}/2base{"_-"=}%""+

Java

Rank	User	Size	Date	Code
1	Runer112	172	8/3/2014 2:17:19 PM	Spoiler For Spoiler: class C{public static void main(String[]a){long x=Long.decode(a[0]),i=x;while(i-->2)x=(x%i)==0?i:x;System.out.print(Long.toString(x,2).replace('0','_').replace('1','-'));}}
2	3298	185	8/3/2014 6:16:11 PM	Spoiler For Spoiler: class G{public static void main(String[]c){int n=Integer.parseInt(c[0]),i=2;while(i<n)if(n%i==0)n/=i;else++i;System.out.print(Integer.toString(n,2).replace('0','_').replace('1','-'));}}

TI-83+ z80

Rank	User	Size	Date	Code
1	Runer112	58	8/3/2014 2:17:19 PM	Spoiler For Spoiler: ;#SECTION "MAIN", CODE    org   userMem - 2    db   0BBh, 6Dh Start:    B_CALL   _RclAns    B_CALL   _ConvOP1    ld   h, d    ld   l, e TrialDivideLoop:    push   de    push   hl    B_CALL   _DivHLByDE    ld   a, h    or   l    pop   hl    pop   de    jq   nz, NotFactor    ld   h, d    ld   l, e NotFactor:    dec   de    ld   a, e    dec   a    or   d    jq   nz, TrialDivideLoop    ld   b, h    ld   c, l    ld   hl, OP1 + 15    ld   (hl), d BitLoop:    dec   hl    srl   b    rr   c    ld   (hl), '_'    jq   nc, BitUnset    ld   (hl), '-'    ld   d, h    ld   e, l BitUnset:    jq   nz, BitLoop    ex   de, hl    B_CALL   _PutS    B_CALL   _NewLine    ret

XTend

Rank	User	Size	Date	Code
1	3298	179	8/3/2014 6:16:11 PM	Spoiler For Spoiler: class G{def static void main(String[]c){var n=Integer.parseInt(c.get(0))var i=2while(i<n)if(n%i==0)n=n/i else i=i+1print(Integer.toString(n,2).replace('0','_').replace('1','-'))}}

Language Ranking

Rank	Lang	User	Size	Date
1	CJam	Runer112	16	8/3/2014 2:17:19 PM
2	Golfscript	Runer112	33	8/3/2014 2:17:19 PM
3	TI-83+ z80	Runer112	58	8/3/2014 2:17:19 PM
4	SysRPL	3298	59.5 (don't ask me why; I'm going off of what he said)	7/31/2014 5:18:48 PM
5	TI-83+ BASIC	Runer112	75	8/3/2014 2:17:19 PM
6	Ruby	Juju	98	7/30/2014 12:01:58 AM
7	Perl	willrandship	98	7/31/2014 2:15:31 PM
8	Haskell	3298	122	8/3/2014 6:16:11 PM
9	Nspire Lua	Jens_K	132	8/1/2014 6:59:33 AM
10	Python2	willrandship	147	7/29/2014 12:51:41 AM
11	Java	Runer112	172	8/3/2014 2:17:19 PM
12	XTend	3298	179	8/3/2014 6:16:11 PM

Title: Re: Code Golf Contest #3
Post by: Juju on July 28, 2014, 03:32:59 pm

Ooh, interesting challenge here.

Title: Re: Code Golf Contest #3
Post by: willrandship on July 28, 2014, 07:34:47 pm

By the way, if your language does not support underscores (ONLY if it does not) you may use a decimal [.] symbol instead.

Title: Re: Code Golf Contest #3
Post by: Runer112 on July 28, 2014, 07:36:49 pm

Quote from: willrandship on July 28, 2014, 07:34:47 pm

By the way, if your language does not support underscores (ONLY if it does not) you may use a decimal [.] symbol instead.

For the record, 83+ BASIC does support underscores (see this (http://www.omnimaga.org/other-calculator-discussion-and-news/code-golf-contest-2/msg390437/#msg390437) post). For consistent scoring of such entries, I'd suggest that all 83+ BASIC entries should be scored as if they used underscores (two byte tokens) rather than periods.

Title: Re: Code Golf Contest #3
Post by: willrandship on July 28, 2014, 09:10:22 pm

Now everything's more complicated :\ stupid 2-byte tokens.

Title: Re: Code Golf Contest #3
Post by: JWinslow23 on July 28, 2014, 10:56:09 pm

Quote from: willrandship on July 28, 2014, 09:10:22 pm

Now everything's more complicated :\ stupid 2-byte tokens.

It's not complicated at all. I did it in 122 bytes. The prime factorization code was no problem. Neither was the binary conversion. It assumes anything 1 and under are valid.

EDIT: I totally changed my greatest prime factor algorithm so lists are not used, and I have 90 bytes! :D Update tomorrow.

Title: Re: Code Golf Contest #3
Post by: DJ Omnimaga on July 29, 2014, 05:31:30 pm

Interesting challenge. I feel bad for Casio PRIZM ASM/C participants, though :P (good luck making an add-in under 29 KB large)

Title: Re: Code Golf Contest #3
Post by: Juju on July 30, 2014, 12:23:38 am

I changed my algorithm as well, only basic operations are used, so I got it down to 98 bytes :3

Title: Re: Code Golf Contest #3
Post by: calc84maniac on July 30, 2014, 02:09:34 pm

So, I have a couple of questions.

Can we assume the input is at least 2? Otherwise, largest prime factor doesn't actually exist.
Also, can my output have a trailing space? That makes things easier in TI-BASIC because of silly string limitations.

If yes to both of these, then I have a 67-byte TI-BASIC solution.

Title: Re: Code Golf Contest #3
Post by: Princetonlion.tibd on July 30, 2014, 02:18:20 pm

I feel like using 68k BASIC would be cheating, it has binary mode :P
I'm going to at least try, not sure if I'll manage to PM it though

Title: Re: Code Golf Contest #3
Post by: JWinslow23 on July 30, 2014, 03:58:54 pm

Quote from: calc84maniac on July 30, 2014, 02:09:34 pm

So, I have a couple of questions.

Can we assume the input is at least 2? Otherwise, largest prime factor doesn't actually exist.
Also, can my output have a trailing space? That makes things easier in TI-BASIC because of silly string limitations.

If yes to both of these, then I have a 67-byte TI-BASIC solution.

I actually don't know the rules on valid input. My 90 byte solution assumes input is any integer. Ask willrandship for confirmation, I don't know.

Title: Re: Code Golf Contest #3
Post by: Runer112 on July 30, 2014, 04:11:48 pm

Quote from: calc84maniac on July 30, 2014, 02:09:34 pm

So, I have a couple of questions.

Can we assume the input is at least 2? Otherwise, largest prime factor doesn't actually exist.
Also, can my output have a trailing space? That makes things easier in TI-BASIC because of silly string limitations.

If yes to both of these, then I have a 67-byte TI-BASIC solution.

Assuming that the input is at least 2 and an integer is fine, since any other numbers do not have a greatest prime factor. But I'd be of the opinion that a trailing space is not okay, especially in the case of TI-BASIC, in which the trailing space would become obvious when doing something like recalling or otherwise operating on Ans.

Title: Re: Code Golf Contest #3
Post by: 3298 on July 30, 2014, 06:37:55 pm

Any entries below 60 bytes yet? I just submitted a 59.5-byte solution in SysRPL. (SysRPL runs on the HP calculators featuring a Saturn processor, which is a 4-bit one. That explains why half bytes are possible as a size there.)
My code calls some OS code to get a sorted list of prime factors (6 bytes, because that call is a flashpointer), and then takes the last element of that list (2 commands for 2.5 bytes each). Thus the assumptions are the same as the OS code's, which should be any integer >=1. (I don't know if 0 is fine as well, but I don't feel like risking a calculator crash to find out.)

Title: Re: Code Golf Contest #3
Post by: Princetonlion.tibd on July 30, 2014, 07:01:24 pm

Mine is 100 something bytes, and it doesn't work yet. As you can tell, I still haven't learned to optimize 68k BASIC :P

Title: Re: Code Golf Contest #3
Post by: willrandship on July 31, 2014, 02:30:22 am

Yes, assuming >=2 is totally fine. IMO, code golf should be about handling the meat of the question, not about handling all the wacky edge cases. If ignoring edge cases makes a smaller solution, that's what I want to see.

Title: Re: Code Golf Contest #3
Post by: Juju on July 31, 2014, 02:56:23 am

I agree, the program shouldn't check for the range of the input and just give undefined results in those cases (in this case, input<2). The contest here is to see how small a program could be without giving an error in the valid input range.

Title: Re: Code Golf Contest #3
Post by: JWinslow23 on August 02, 2014, 01:06:57 pm

Only 3 more days for the contest! Submit your entries and challenge ideas now!

Title: Re: Code Golf Contest #3
Post by: willrandship on August 02, 2014, 01:22:04 pm

Well, I'm going to be gone for a few days, so I'll post my suggestion for the next one now. I'm assuming no one else is going to post a perl solution.

It would go as follows:

For a given string input consisting of only uppercase letters and numbers, add the ASCII value of each alphabetical character (that's 65-90 for uppercase A-Z) and subtract every number. Display the result, but printed vertically with each digit on a new line.

You CAN end up with a negative number, in which case the first line should have a - sign.

Example:
Input: "A45FTUX"
Internal Math: (65 - 4 - 5 + 70 + 84 + 85 + 88 = 383)
Output:
3
8
3

A negative example:
Input: 99A874512995
Internal math:(-9-9+65-8-7-4-5-1-2-9-9-5)
Output:
-
3

Title: Re: Code Golf Contest #3
Post by: JWinslow23 on August 02, 2014, 04:22:20 pm

Nice challenge! I might use it. I already have a 140 byte solution in TI-BASIC, assuming ENTER must be pressed after each digit, and the numbers and negative sign are aligned to the right.

Title: Re: Code Golf Contest #3
Post by: willrandship on August 02, 2014, 06:08:36 pm

I don't know about pressing enter after every key. I'm pretty sure I specified a string for input...:P Better pull out that sub( command.

Aligning to the right is fine, as long as it's vertical.

FWIW I have a 75 byte perl version.

Title: Re: Code Golf Contest #3
Post by: JWinslow23 on August 02, 2014, 09:03:05 pm

Quote from: willrandship on August 02, 2014, 06:08:36 pm

I don't know about pressing enter after every key. I'm pretty sure I specified a string for input...:P Better pull out that sub( command.

Aligning to the right is fine, as long as it's vertical.

FWIW I have a 75 byte perl version.

And I do have a string for input. It's just, for displaying the final numbers...
Eh, I'll show you:
(http://img.ourl.ca/Contest4.gif)

Title: Re: Code Golf Contest #3
Post by: JWinslow23 on August 03, 2014, 07:14:56 pm

Bump.

Last day for submissions! Be swift with any works in progress!

Title: Re: Code Golf Contest #3
Post by: 3298 on August 04, 2014, 05:58:30 am

Now I want to see the competing entries in Java and Haskell. I especially want to know how I could have saved more space in Java. It's probably the number input - I parsed a command-line parameter using Integer.parseInt.
Also:

Quote from: JWinslow23

SysRPL

Rank	User	Size	Date
1	3298	59.5 (don't ask me why; I'm going off of what he said)	7/31/2014 5:18:48 PM

:evillaugh: That half-byte comes from the 4-bit processor SysRPL is designed for. Many things there have odd sizes, and when you have an odd number of nibbles, you get ... you guessed it, half bytes.

In case anyone wants to check it, you'll need to set up an emulator and install a development tool on it. The remaining part of the post is a tutorial for that.
A ready-to-use emulator comes with the free Windows-based IDE Debug4x (get it at http://www.debug4x.com/ (http://www.debug4x.com/)). The emulator is in the subdirectory "Emu" of the installation directory. Start it, and it will ask for a KML script. This defines the look of the emulator, the key positions, and a few other things. The pre-installed KML script "Eric's Real 50G" should do the trick. I don't know whether the emulator only shows the screen afterwards (haven't used it in a while), but if it does, search the menus at the top for the option to show the entire calculator. The first step with the calculator should be to switch it to RPN mode (answer the "Try to recover memory?" question with No (the F6 key), confirm the "Memory cleared" message with ENTER, press the MODE key, then the +/- key, and finally the ENTER key).
Next step: SysRPL development stuff. The compiler is already installed, you just have to unlock it. But you need something providing the names of commands, otherwise you can only use UserRPL commands or nameless pointers. A library providing the names is called "extable". I'm using the one from http://www.hpcalc.org/details.php?id=3940 (http://www.hpcalc.org/details.php?id=3940) (there is a file called "extable2.lib" in that archive, that's the right one). Drag the file into the emulator's screen, and something should appear behind the "1:". You just put the library on the stack. Now push the 0 and press ENTER. The library shifts up to level 2 of the stack, and the 0 appears on level 1. Now press the STO key. The stack should be empty now. Press and hold (this is done by right-clicking on the button instead of left-clicking) the ON key, and push C. This reboots the calculator and finishes the library installation. Now, unlock the compiler. Enter this without the quotes: "256 ATTACH". Don't forget to press the ENTER key at the end to execute the command. (Edit: I forgot to mention that you need to know how to enter the space here. In the bottom row you find a key labeled SPC, that's the space key.)
Now everything is set up. For ease of use, start the text editor this way: Put an empty string on the stack (the double quotes you need for that are present as a shifted function of the multiplication key), then press the down arrow. Enter the source code I gave you (Alpha-lock can be done with two presses on the Alpha key, a third press disables Alpha mode again). If you are missing a few special characters, use the char browser (CHARS is a shifted function of a key in the fourth row; be sure to disable alpha-lock before). Due to some weird requirement from the compiler, the last two chars must be a newline and an @ char, so add these. ENTER exits the editor and replaces the empty string on the stack with the contents of the editor. If you need to edit it again, the down arrow key puts you back in the editor.
Now we compile the source. Simply issue the ASM command with the source on stack level 1. If there are no errors, the source will be replaced by the compiled code (which looks like "FlashPtr External External ..." - that's perfectly normal). With the compiled code on level 1, you can check its size with the BYTES command (takes any object on level 1, gives a checksum on level 2 and the size in bytes on level 1). Or you can give it a parameter (enter the number on the stack, followed by the SWAP command to put it above the program) and run the program with the EVAL key. If you want to do both, these commands are helpful: DUP pushes a duplicate of level 1 (use this to avoid having to enter the source twice), DROP drops level 1, and CLEAR drops everything.
Be extra careful when running the program, no parameters or parameters of the wrong type will crash the calculator because I omitted the necessary checks for that. The input number must be an infinite-precision integer in this case, which is printed and entered as simply a number. Real numbers have a period somewhere, and they are not accepted.

Title: Re: Code Golf Contest #3
Post by: JWinslow23 on August 04, 2014, 05:38:29 pm

Thanks for the clarification.

And now, the contest is over! The results are in the OP, and the newest contest is here. (http://www.omnimaga.org/other-calculator-discussion-and-news/code-golf-contest-4/)