Jump to content

Two-liner


monoceres
 Share

Recommended Posts

So one thing that I have learned is that with most languages you can cram a ridiculous amount into 1 'line'. It's always fun to cram an entire algorithm into a few lines, but the problem is that you sacrifice readability too much. Now when I try to see how short I can make an algorithm I try to keep each line (1) Human readable (still use descriptive variables, no digraph/trigraphs, etc.), (2) so it fits on a normal computer screen w/o wrapping, (3) formatted close to if not exactly as I normally would format.

Here's one of the code blocks I am pretty proud of... hell if I remember what it does anymore, but I know that the first time I wrote the algorithm it was ~80 lines or so.

#include <vector>
#include <algorithm>

using namespace std;

class LeaguePicks {
public:
    vector<int> returnPicks(int idx, int friend, int pick) {
        vector<int> ret(1, idx);
        for (int i=idx; i<=pick; (i+=2*(friend-idx)+1+2*((i-1)/friend%2)*(2*idx-friend-1)) <= pick ? ret.insert(ret.end(),i) : ret.begin());
        return ret;
    }
};
Link to comment
Share on other sites

Do you mean me or monoceres?

If you mean me then I'd love to know how. I could probably figure out a way to shove the return into the for loop update, but I don't have a clue how to get the Vector initialization into the for loop.

Link to comment
Share on other sites

I was talking to monoceres.

Yours, depending on the source of input, could actually be done with no code. If you re-write it to use template meta-programming you can let the compiler do it for you. But if you don't get input until run-time what you have is confusing enough.

Link to comment
Share on other sites

The code was for a TopCoder competition, so the args aren't available at compile time. Something funny: at an algorithms competition one of my friends couldn't figure out how to solve a dynamic programming problem; since he was running out of time he just used a brute force approach using the compiler to do lots of his work (they clocked the runtime, not the compile time)... in the end I am pretty sure he failed, but it was a nice try. And yes, I'd have to agree that the code is screwed up enough. I attached the original problem statement.

SRM 152 DIV 1 - 250 point problem

CODE

Problem Statement

You and your friends are setting up a fantasy TopCoder league, where you choose coders to be on your team and score points in the league when any one of your coders wins their room or successfully challenges somebody, etc. To be fair, a system has been developed to choose the order in which picks are distributed. It works like this: first, lots are drawn to choose your position in the league. Then the player with the first position gets first pick, the second player gets second pick, all the way until the last player picks. Then the order reverses: the last player chooses again, then the next to last player, and so on, until you reach the first player again. Then the cycle repeats: the first position chooses again, then the second, and so on.

For example: say you were in the third position on a 6 player league. You would get the 3rd pick, then you'd wait until the 10th pick (the order would be 1,2,you,4,5,6,6,5,4,you), and then the 15th pick, and so on until there were no more coders to choose. If there were 20 total picks, then you would get pick numbers 3,10,15.

Not wanting to miss your chance at a pick, your goal is to write a program that tells you what pick numbers you have in the order that you have them. You will receive three ints indicating your position in the league(1 being the first position), the number of friends that are in the league with you, and the number of picks that are being divvied up among the league. You will return an vector <int> that indicates the picks that you receive in ascending order.

Definition

Class:

LeaguePicks

Method:

returnPicks

Parameters:

int, int, int

Returns:

vector <int>

Method signature:

vector <int> returnPicks(int position, int friends, int picks)

(be sure your method is public)

Notes

-

Note that your position in the league and the pick numbers start at 1 and not 0. This should be clear from the examples.

Constraints

-

position will be between 1 and friends inclusive.

-

friends will be between 1 and 40 inclusive.

-

picks will be between 1 and 40 * friends inclusive.

Link to comment
Share on other sites

The code was for a TopCoder competition, so the args aren't available at compile time. Something funny: at an algorithms competition one of my friends couldn't figure out how to solve a dynamic programming problem; since he was running out of time he just used a brute force approach using the compiler to do lots of his work (they clocked the runtime, not the compile time)... in the end I am pretty sure he failed, but it was a nice try. And yes, I'd have to agree that the code is screwed up enough. I attached the original problem statement.

Mine's faster.

class LeaguePicks2
   {
   public:
       std::vector<int> returnPicks(int idx, int friends, int picks)
       {
           std::vector<int> ret;
           int rolling = idx;
           for (int i = 2; rolling <= picks; ++i)
           {
               ret.push_back(rolling);
               if (i & 1)
                   rolling += (2 * idx) - 1;
               else
                   rolling += ((friends - idx) * 2) + 1;
           }
           return ret;
       }
   };

A couple things:

  • push_back() with Visual Studio 2008 is faster than insert().
  • I don't use any division.
I used the following simple class to measure time:

class CHPTimer
   {
   public:
       void Start()
       {
           QueryPerformanceCounter(&m_LI);
       }
   
       __int64 Elapsed()
       {
           LARGE_INTEGER diff;
           QueryPerformanceCounter(&diff);
           return diff.QuadPart - m_LI.QuadPart;
       }
   private:
       LARGE_INTEGER m_LI;
   };

I would love to know how :(

Think.

Edit: Oh yeah, and Wus, your code fails a basic compilation test. The keyword "friend" is reserved so it can't be used as the name of the second parameter. So, I "win" on the fact that my code compiles and yours doesn't without modification. :)

Edited by Valik
Link to comment
Share on other sites

Haha, well played.

Yeh, I renamed some of the variables when I posted the code and (since I mainly use Java) I forgot that friend was a no-go.

I really enjoy the TopCoder problems. It's a lot of fun to try to find the most succinct way of writing an algorithm. It's also a nice break from the tedium of working on a large project; sometimes getting lost in kLoC's of code gets disheartening.

Have you guys ever entertained the idea of having a monthly puzzler on the website?

Link to comment
Share on other sites

Think.

I sure will.

Will be testing when I come home from school :)

Damn Good coding monoceres

.. now, with that kind of talent, make something more useful!!!

8)

Thanks :(

And I yes I'm going to dig my head into more c++ in the future time so I'm sure I can do something better :D

Edited by monoceres

Broken link? PM me and I'll send you the file!

Link to comment
Share on other sites

I can Create and display a GUI with one line but since I can't see a way to loop without two lines so I can't handle events.

X(

ex:

If GUICreate('x',100,17) And GUICtrlCreateLabel("Hello",0,0,100,17) and GUISetState() And sleep(5000) Then $x=1

My Projects - WindowDarken (Darken except the active window) Yahsmosis Chat Client (Discontinued) StarShooter Game (Red alert! All hands to battlestations!) YMSG Protocol Support (Discontinued) Circular Keyboard and OSK example. (aka Iris KB) Target Screensaver Drive Toolbar Thingy Rollup Pro (Minimize-to-Titlebar & More!) 2D Launcher physics example Ascii Screenshot AutoIt3 Quine Example ("Is a Quine" is a Quine.) USB Lock (Another system keydrive - with a toast.)

Link to comment
Share on other sites

I can Create and display a GUI with one line but since I can't see a way to loop without two lines so I can't handle events.

X(

ex:

If GUICreate('x',100,17) And GUICtrlCreateLabel("Hello",0,0,100,17) and GUISetState() And sleep(5000) Then $x=1
I'm thinking of using Assign() and execute to loop on one line, but since autoit will crash after 5100 recursive calls, I don't think it's a good way to do it :) Edited by monoceres

Broken link? PM me and I'll send you the file!

Link to comment
Share on other sites

EDIT: woops Sorry I didn't see your post.

Original Post:

You could probably do something like this monoceres, but I'm not smart enough to debug all the logic.

Note: can be changed to one line - I only put it on multiple lines so It can be read.

If Opt("WinTitleMatchMode",4) _
And Assign('g',GUICreate(''),2) _
And Assign('c',GUICtrlCreateButton('Button',0,0,100,20),2) _
And GUISetState() _
And WinActivate('classname=Progman') _
And Sleep(300) _
And WinWaitActive($g) _
And WinActivate('classname=Progman') _
And Assign('m',GUIGetMsg(),2) _
Or  ($m=-3 ) _
Then $dummy=2
Edited by crashdemons

My Projects - WindowDarken (Darken except the active window) Yahsmosis Chat Client (Discontinued) StarShooter Game (Red alert! All hands to battlestations!) YMSG Protocol Support (Discontinued) Circular Keyboard and OSK example. (aka Iris KB) Target Screensaver Drive Toolbar Thingy Rollup Pro (Minimize-to-Titlebar & More!) 2D Launcher physics example Ascii Screenshot AutoIt3 Quine Example ("Is a Quine" is a Quine.) USB Lock (Another system keydrive - with a toast.)

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...