Mafiascum Coding Challenge

[Flubbernugget]

This is a fork of the Mafia Discussion thread dedicated to solving various coding problems.

I will be posting various problems for the community to solve. I also encourage members to bold problems of their own to be solved. I will add them to the OP as I see them.

I will add the first person to answer the problem to the OP. I don't have time to check all the answers to the problems that are going to come up, so please be honest with your answers. That being said, if you see a wrong answer in the thread, please challenge it! We are all human and make mistakes

Please spoiler your code and answers for the people that want to try to answer these on their own.

[Flubbernugget]

PROBLEM 1:

Solved by Snakes

Spoiler:

A cyclops number is a number whose binary representation has only one zero, and has an equal count of ones preceding and trailing that zero. Examples of cyclops numbers are 5 (101), and 27 (11011).

Write a program that accepts an integer in base n and determines whether or not it is a cyclops number.

PROBLEM 2:

Solved by Kagami

Spoiler:

What is the largest fibonacci number that can fit into a 128-bit register? What term is this number in the fibonacci sequence?

PROBLEM 3:

Solved by Frozen Angel

Spoiler:

Write a program that prints its own source code backwards.

PROBLEM 4:

Submitted by Kagami

Spoiler:

See post 12 and post 13

PROBLEM 5:

Submitted by Frozen Angel and Solved by Kagami

Spoiler:

Let's say that number n shifts number m, if m * n can be written as m with its last digit moved to the first position.For example, 4 shifts 102564, because 4 * 102564 = 410256. The last digit of 102564, 4, was moved to the beginning of the number when 102564 was multiplied by 4. For the given number n, find the smallest number greater than 1 that is shifted by n.

(1<n<10)

PROBLEM 6:

Submitted by AxelGreaser

Spoiler:

Without compiling, what does the following code do?

Code: Select all

#define _ F-->00 || F-OO--;
long F=00,OO=00;
main(){F_OO();printf("%1.3f\n", 4.*-F/OO/OO);}F_OO()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
       _-_-_-_-_-_-_-_-_
            _-_-_-_
}

PROBLEM 7:

Spoiler:

Conway's Game of Life is played on an orthogonal grid where the squares of the grid can either be populated by a cell or empty. A square with a cell in will be referred to as a "live square." The game progresses through discrete states. If the game exists in state t, the next state t+1 is defined as such:

All live squares in state t die in state t+1 if they have less than two cells touching them.

All live squares in state t either continue living if two or three squares touch it.

All live squares in state t die if they have more than three squares touching it.

A square with no cell in it in state t becomes a live square in state t+1 if it is touched by three live squares.

Unlike the traditional rules of Conway's Game of Life, this game will be played on a finite m x n board. Do not assume that squares on the edge of the board "wrap around" the board in any way. That is, any square in an array s[m,y] or s[x,n] does not touch any square s[0,y] or s[x,0] respectively.

In Conway's Game of Life, certain board inputs result in a stable state. We will define a stable state as one where state t = state t + 1. On a Game of Life board, a stable state looks like a group of cells that never move. Write a program that accepts an arbitrary game board for Conway's Game of Life and outputs any stable states that exist or will end up existing as the game progresses.

A theorem proving this problem cannot be solved with a Turing machine will also be considered a solution.

PROBLEM 8:

Submitted by yesiree

Spoiler:

Given an array of real numbers (0 included), find the consecutive elements that yield the largest product.

PROBLEM 9:

Submitted by Vonflare

Spoiler:

See post 68

PROBLEM 10:

Spoiler:

Given an ordered pair (a, b, c...) of polynomials, calculate the derivative of a/b/c...

PROBLEM 11:

Submitted by Ircher and solved by Realeo

Spoiler:

Given x and y, find the least common multiple of X and Y. If the language has a builtin feature for this, don't use it.

[vonflare]

Problem 3 is impossible because anything you add as a system.out will also need to be added as a system.out but again in reverse.

Unless of course there is a program that could read its own code, of which I am not aware.

[Flubbernugget]

I clarified the problem to state "source code"

EDIT: I completely misread your post. I'll take a closer look when I get home from work but at least with a higher level language I don't see an issue.

[vonflare]

but wouldn't any system.out be classified as source code?

for example, let's use turing:

Code: Select all

put ""

here's our starting code. Let's reverse it and put it inside the quotes.

Code: Select all

put "\"tup\""

This would print

"tup"

which would be the code, but from the original code we started with. The code is now longer than it was before.
This continues as a vicious cycle

[vonflare]

unless you made a program that prints its entire source code as a system.out, excluding the system.out itself, and then calls a function to print it all again but in reverse?

It would technically be all the source code, but not in the right order.

but even then it would probably result in an infinite requisite of nested brackets

[Kagami]

Problem 2 is

Spoiler:

205697230343233228174223751303346572685, which is the 185th term.

[Kagami]

I think flubber just wants you to read the code as a text file and write it backward, let's say in a scripting language.

[vonflare]

actually

Code: Select all

method1 {

put ";\(\)1dohtem\n;\(\)1dohtem\n\}\"\"tup\n\{ 1dohtem";

}

method1();
method1();

would print all the source code backwards, but it would write the beginning, then the end, and then the middle.

[vonflare]

I think flubber just wants you to read the code as a text file and write it backward, let's say in a scripting language.

well yeah you could do that but that would be trivially easy, and I assumed that was not the correct interpretation as the other two were moderately difficult.

you could just write the source code for the program backwards in the text file, and then call the text file.

[Flubbernugget]

Please spoiler code and possible answers

[vonflare]

EDIT: I completely misread your post. I'll take a closer look when I get home from work but at least with a higher level language I don't see an issue.

It would be possible with any program capable of calling a text file. But I assumed you meant using only system.out.

Maybe there are higher level functionalities that I don't know about? I only use java and GML.

[Kagami]

For a somewhat more difficult problem:

Here's a bitmap of a tiger, which can be read as a 240x320x3 array of integers in the range [0, 255].



For each of the three color channels (red, green, and blue), there is a little bug who starts in the top-left corner of the image. The red bug eats the redness of the pixel he's standing on, then moves either to the next pixel below him or to the next pixel to the right of him until he gets to the bottom-right pixel of the image. Once he's done, he magically turns into a big pile of something nice, let's say gold coins. The number of coins he turns into is equal to the sum of pixel values he ate. Then the Blue and Green bugs do the same thing, eating the values of their respective colors in some path.

If the three bugs all choose the path that is best for them (in terms of yielding the most coins), how many gold coins will you end up with?

[Kagami]

For example, if the Red bug just went Right as until he reached the top-right corner, then went down from there, he'd yield 89344 coins.

[Flubbernugget]

Thanks for the problem! I'll add it to the OP.

Vonflare I'm really not sure how you're trying to interpret the problem. However, my intention was to have a solution in the manner described by Kagami. Although "trivial," if I remember correctly there was some interest in the Mafia Discussion thread from beginning coders, so it doesn't make sense to make all the problems extremely difficult.

[Flubbernugget]

Spoiler: Possible hint to Kagami's problem

It's just a summation of the respective RGB values of the bitmap right?

[Flubbernugget]

I'm thinking of a problem involving The Game of Life at the moment but I'm not 100% if it would take a lot of math outside of the realm of coding just yet.

[Plotinus]

Spoiler: Possible hint to Kagami's problem

It's just a summation of the respective RGB values of the bitmap right?

Spoiler:

no. it can't go back up or left, it has to zigzag down to the right and pick the best path, the reddest path, the greenest path, the blueest path.

[Flubbernugget]

Hm. That makes it a lot more interesting

[Kagami]

Plotinus is correct.

[Snakes]

A little clunky, but here's my answer for #1.

Spoiler: #1

Code: Select all

	public static boolean isCyclops(int number){
		ArrayList<Integer> binary=getBinary(number);
		int numZeroes=0;
		int index=0;
		for(int i=0;i<binary.size();i++){
			if(binary.get(i)==0){
				numZeroes++;
				index=i;
			}
		}
		if(numZeroes!=1)
			return false;
		int trailingOnes=binary.size()-index-1;
		return index==trailingOnes;
	}
	public static ArrayList<Integer> getBinary(int n){
		ArrayList<Integer> binaryNumbers=new ArrayList<Integer>();
		while(n>0){
			int leftover=n%2;
			binaryNumbers.add(leftover);
			n=(n-leftover)/2;
		}
		return binaryNumbers;
	}

[Kagami]

It can be done in constant time~

[Kagami]

Spoiler: very succinct problem 1 solution pseudocode

bool is_cyclops(x):

int n = ceiling(log(x)/log(2))
return n > 1 && n % 2 == 1 && x == 2^n - 1 - 2^((n-1)/2)

[Kagami]

It can be done in constant time~

Misspoke, I was thinking of a different solution, but it's also O( log n )

[Flubbernugget]

A little clunky, but here's my answer for #1.

Spoiler: #1

Code: Select all

	public static boolean isCyclops(int number){
		ArrayList<Integer> binary=getBinary(number);
		int numZeroes=0;
		int index=0;
		for(int i=0;i<binary.size();i++){
			if(binary.get(i)==0){
				numZeroes++;
				index=i;
			}
		}
		if(numZeroes!=1)
			return false;
		int trailingOnes=binary.size()-index-1;
		return index==trailingOnes;
	}
	public static ArrayList<Integer> getBinary(int n){
		ArrayList<Integer> binaryNumbers=new ArrayList<Integer>();
		while(n>0){
			int leftover=n%2;
			binaryNumbers.add(leftover);
			n=(n-leftover)/2;
		}
		return binaryNumbers;
	}

Awesome! I'll put you in as solving it