Mafiascum Coding Challenge

[AxleGreaser]

Re: Problem 4.

Spoiler: Largish hint to kagamis tiger problem

This is actually a largish hint.

It can be done in constant time~

as in...
booo kagami
Once i read that I thought.... duh. So you for me you spoiled your own problem.

Spoiler: bigger hint

flood fill is constant time.

Spoiler: even bigger hint

flood fill can flood fill cumulative sums in constant time.

That is an algorithm problem.

A more purely "coding" problem.... (which relies on good faith) is.

without compiling and executing the program what does the following C code do?

Spoiler: C code

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

A coding history question is: What kind of "idiot" did that and why?

Admission, I believe that while I was beginning to work it out,
someone spoiled me, and told me, as otherwise we wouldn't have got to the pizza shop before it closed.

[AxleGreaser]

pedit

Spoiler: ...

Ah 40 says its solved (defined the algorithm) Kagamis Tiger already.
Oh well 46 is for anyone who wants hint and is persevering with trying to solve it for themselves.

[AxleGreaser]

Spoiler: C code

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

It does absolutely nothing when compiled, as there are syntax errors (in particular, main is declared simply as

Code: Select all

main()

which does not specify a return value.

It has i believe been written in K&R C style. (its an historically old piece of code.)
and yes it does not specify a return value from main and main did not declare its return type.

So part of the output of the program when someone did once compile it was
['Exited: ExitFailure 6']

that however is not all the program "did"

(also I am pretty sure the "6" is compiler (possibly even luck) dependent.)

at one time unspecified return values from functions all defaulted quietly to int.
It seems like it kinda still is
https://msdn.microsoft.com/en-us/library/sta56yeb.aspx
"

If a return value is not required, declare the function to have void return type; otherwise, the default return type is int.

"

https://www.cs.uic.edu/~jbell/CourseNot ... tions.html
If no return type is given, the compiler will normally assume the function returns an int. This can cause problems if the function does not in fact return an int.
(younguns might)also see.
http://ee.hawaii.edu/~tep/EE160/Book/chapapx/node7.html

[AxleGreaser]

Can't you put "POST" starting from the cell diagonally next to the "C" in "COMB" (other than the "O"), and going bottom right?

I suspect

you can also put it in backwards, bottom right to to left.
OR
On either main diagonal, starting or ending in any of the four corners.

An unspecified question/feature, is if at future time if get an input word that does not fit can you (or are you required) revisit and change earlier choices.
Specifically If the next word is "posts" should the program choose to move post to >A< main diagonal, with an S on the end?
Making it a kind of packing problem but with small N so optimization isn't essential, just fun.

Similarly if you (Allow) and add the word "stool" then adding the words "tool" "too" "loots" "loot" and "loo" has already been done. But that would just be my interpretation of the rules.

[AxleGreaser]

Spoiler: Game of life problem

You know that for a grid with N elements there are 2^N possible configurations, thus each board can be nicely represented as an N-bit number, and you are guaranteed to see a repeat within 2^n + 1 steps (so the problem halts even in the torus-board case).

Given the board input, you simply run it, placing each observed board into a suitable data structure (binary search tree seems reasonable) together with the step number of the observation. As soon as you observe a state that's already in the tree, you're done, and the board oscillates with period equal to the current step number minus the previously observed step number. If you care only about stable states, you can halve memory usage by not storing step numbers, and instead just comparing the value of the current state with that of the prior state upon algorithm completion.

Your avatar seems strangely apt.

Spoiler: a problem

How big is the memory virtual or otherwise and so what maximize board size will the proposed solution work for?

[AxleGreaser]

If you're worried about memory, which perhaps you should be for a large board, you can run two threads of the game.

2^32 is 4 gig.
A game of life board with 32 cells is trivially small.
2^48 is 256 terra bytes
2 ^ 64 (and 8x8 game of life board.) is ... oopsie
Non trivial boards would fairly rapidly have more memory required than there are baryons in the visible universe.

[AxleGreaser]

Now, to make it a but tougher:

Make it where it can handle an arbritrary number of arguments. The number of arguments provided may be supplied as a parameter.

Simple.

Take the first two number. Find the lcm, Find the lcm of the lcm and the 3rd number. Rinse and repeat. Code coming later.

EDIT:

Spoiler: Ircher's LCM

Code: Select all

def multipleLCM(array):
 a,b = array[0],array[1]
 answer=lcm(a,b)
 array.pop(0)
 array.pop(0)
 while len(array) != 0:
  a=array[0]
  answer=lcm(answer,a)
  array.pop(0)
 return answer

#Python
def LCM(a,b):
 return a*b/GCM(a,b)

def GCM(a,b):
 if a==0:
  return b
 return GCM(b%a,a)

LCM is an odd concept. It is equivalent to wanting the smallest of all the common prime factors

So just to check that I have that oddness right.
The LCM of 30 and 12 is 2? (3 and 6 are also common multiples but 2 is smallest)
(also implcitly is not 1)

Re Irchers list problem.

LCM of 30,12, 9....

The algorithm above claims
LCM ( LCM (30,12) , 9 ) is the same as LCM(30,12,9)

its not.

The LCM of 30,12 is 2. (we chucked the 3 out because both numbers had prime factor of 2.)

LCM of 2 and 9 is ... doesnt have one?

Ok trying again.....

nope i cant make the algorithm succeed but be wrong, but it can for lists fail to find an LCM when there is one.

Spoiler: alt alg no code

LCM (a,b,c, ...) = smallest prime factor of GCM(a,b,c,...)
or using existing functions.
LCM (a, GCM(a,b,c,...) ) //implement GCM(...) by successive calls to GCM(x,y) )

[AxleGreaser]

OOOOPS

apparentyl I woke up with head scrwed on backwards and upsdie down


the previous post is bollocks please ignore me...