sciencetalk

Code: Selecteer alles

import Data.List

import qualified Data.Set as Set

-- calculate for N=1 to 10

solution1 = map (length . polyominoes) [1..10]

polyominoes 1 = [[(0,0)]]

polyominoes n = myNub . concatMap generateNext $ polyominoes (n - 1)

-- for larger lists this is more efficient than a normal nub

-- myNub = nub

myNub = (Set.toList . Set.fromList)

-- generate all new normalized polyominoes of 1 higher order based on coords.

generateNext coords = myNub $ map (normalize . (:coords)) (newSquares coords)

-- generate the new squares that can be added to the polyomino

newSquares coords = (nub $ concatMap pointsAround coords) \\ coords

where

pointsAround (x,y) = [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]

-- gives a normalized form of the coordinates of a specific polyomino

normalize coords = minimum [moveOrigin coords, rotate90 coords, rotate180 coords, rotate270 coords]

-- rotate and move origin.

rotate90' coords = map (\(x,y) -> (-y,x)) coords

rotate90  = moveOrigin . rotate90'

rotate180 = rotate90 . rotate90'

rotate270 = rotate180 . rotate90'

-- move the origin to the lowest, most left square in the polyomino.

moveOrigin coords = sort $ map (\(x,y) -> (x-g,y-f)) coords

where

(e,f) = minimumBy (\(a,b) (c,d) -> compare b d) coords

(g,h) = minimumBy (\(a,b) (c,d) -> compare a c) (filter ((==f).snd) coords)

Code: Selecteer alles

module Main where 

import Data.List

import qualified Data.Set as Set

main = print solution2

-- calculate for N=1 to 10: takes 10 seconds. compiled ~3 seconds

-- calculate for N=1 to 11: takes 52 seconds. compiled ~12 seconds

solution2 = map (length . polyominoes) [1..10]

polyominoes 1 = [[(0,0)]]

polyominoes n = myNub . concatMap generateNext $ polyominoes (n - 1)

-- for larger lists this is more efficient than a normal nub

-- myNub = nub

myNub = (Set.toList . Set.fromList)

-- generate all new normalized polyominoes of 1 higher order based on coords.

generateNext coords = myNub $ map (normalize . (:coords)) (newSquares coords)

-- generate the new squares that can be added to the polyomino

newSquares coords = (nub $ concatMap squaresAround coords) \\ coords

where

squaresAround (x,y) = [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]

-- gives a normalized form of the coordinates of a specific polyomino

normalize coords = minimum $ map moveOrigin [coords, rotate90 coords, rotate180 coords, rotate270 coords]

-- rotate

rotate90  = map (\(x,y) -> (-y,x))

rotate180 = map (\(x,y) -> (-x,-y))

rotate270 = map (\(x,y) -> (y,-x))

-- line up axis with most left and lowest squares

moveOrigin coords = sort $ map (\(x,y) -> (x-g,y-f)) coords

where

g = minimum $ map fst coords

f = minimum $ map snd coords

Code: Selecteer alles

// (windows troep zonodig weghalen voor ander platform)

#define WIN32_MEAN_AND_LEAN

#include <windows.h>

//------------------------------------------------------------------------------

typedef unsigned __int64 Polyonimo;

typedef unsigned __int64 PolyonimoBits;

typedef __int64 PolyonimoDelta;

#include <vector>

typedef std::vector<Polyonimo> PolyonimoList;

static const PolyonimoBits bit = 1;

//------------------------------------------------------------------------------

PolyonimoDelta inline pMax( const PolyonimoDelta &a, const PolyonimoDelta &b )

{

  // max(a,b) zonder branching (if)

  const PolyonimoDelta c = (a-b)>>(sizeof(a)*8-1);

  return (b&c)|(a&~c);

}

//------------------------------------------------------------------------------

static Polyonimo CreatePolyonimo( unsigned w, unsigned h, PolyonimoBits c )

{

  // normaliseer

  unsigned int s = w*h;

  PolyonimoDelta m = (int)(h-w);

  if (!m)

  {

// vierkant: vergelijk vier orientaties

unsigned int p = (s-1);

unsigned int q = s-w;

unsigned int r = w-1;

PolyonimoBits zz = bit<<p;

PolyonimoBits x1,x2,y1,y2;

x1 = x2 = y1 = y2 = 0;

unsigned int zx,zy,z;

for (zx=zy=z=0; z<s; z++)

{

  if ((c>>z)&1) x1 |= zz;

  if ((c>>p)&1) x2 |= zz;

  if ((c>>(q+zy-zx))&1) y1 |= zz;

  if ((c>>(r+zx-zy))&1) y2 |= zz;

  m = pMax(y1,y2)-pMax(x1,x2);

  if (m) break;

  if ((zx+=w)>=s) { zx=0; zy++; }

  p--;

  zz >>= 1;

}

  }

  if (m>0) // roteer 90 indien nodig

  {

PolyonimoBits c2=0;

unsigned int x,y,z=0;

for (y=h-1;;)

{

  for (x=0; x<s; x+=h)

  {

if ((c>>(z++))&1) c2 |= bit<<(x+y);

  }

  if (!y) break;

  y--;

}

c = c2;

z = w;

w = h;

h = z;

  }

  //roteer 180 indien nodig

  PolyonimoBits i = 1;

  PolyonimoBits j = bit<<(--s);

  for (bool r=0;;)

  {

PolyonimoBits ci = c & i;

PolyonimoBits cj = c & j;

if (ci || cj)

{

  if (!r) { if (!cj) break; if (!ci) r = true; }

  if (r) c = (c & ~(i|j)) | (ci<<s) | (cj>>s);

}

i += i;

j >>= 1;

if (s<2) break;

s -= 2;

  }

  return c | (((PolyonimoBits)((w<<4)|h))<<56);

}

//------------------------------------------------------------------------------

static void AddToList( PolyonimoList *list, const Polyonimo &p )

{

  // voeg toe indien nog niet in lijst

  unsigned int n = (unsigned int) list->size();

  unsigned int b = 1;

  while (b<n) b+=b;

  unsigned int i;

  for (i=0; b; b>>=1 ) // (binary search)

  {

unsigned int j = i+b;

if (j>n) continue;

PolyonimoDelta d = p - (*list)[j-1];

if (!d) return; // zat al in lijst

if (d>0) i = j;

  }

  list->insert(list->begin()+i,p);

}

//------------------------------------------------------------------------------

static void AddExtensions( const Polyonimo &p, PolyonimoList *dest )

{

  // voeg alle uitbreidingen toe aan lijst

  unsigned int w = (unsigned int) (p>>56);

  unsigned int h = w & 0xf;

  w >>= 4;

  PolyonimoBits c = p & 0xffffffffffffff;

  unsigned int x,y;

  unsigned int w1 = w-1;

  unsigned int h1 = h-1;

  PolyonimoBits mz = 1;

  for (y=0; y<h; y++) // voeg binnenin blokje toe

  {

PolyonimoBits bx = y ? (mz>>w) : 0;

if (y<h1) bx |= mz<<w;

for (x=0; x<w; x++)

{

  if (!(c&mz)) // dit vakje nog niet bezet?

  {

// check buren

PolyonimoBits b = bx<<x;

if (x) b |= mz>>1;

if (x<w1) b |= mz<<1;

if (c & b) AddToList(dest,CreatePolyonimo(w,h,c|mz));

  }

  mz += mz;

}

  }

  for (unsigned int i=0; i<2; i++)

  {

// twee keer links en rechts blokjes toevoegen

if (i) // tweede keer geroteerd (nu eigenlijk boven & onder)

{

  unsigned int z,q = w*h;

  PolyonimoBits c2 = 0;

  y = h1;

  for(z=0;;)

  {

for (x=0; x<q; x+=h)

{

  if ((c>>(z++))&1) c2 |= bit<<(x+y);

}

if (!y) break;

y--;

  }

  c = c2;

  z = w;

  w = h;

  h = z;

}

// voeg lege kolom toe

PolyonimoBits r = (bit<<w)-1;

PolyonimoBits c2 = 0;

for (y=0; y<h;)

{

  c2 |= (c&r) << (++y);

  r <<= w;

}

// voeg links/rechts blokjes toe

w1 = w+1;

PolyonimoBits k1 = 2;

PolyonimoBits k2 = bit<<w;

for (y=0;;)

{

  if (c2 & k1) AddToList(dest,CreatePolyonimo(w1,h,c2|(k1>>1)));

  if (c2 & k2) AddToList(dest,CreatePolyonimo(w1,h,(c2>>1)|k2));

  if ((++y)>=h) break;

  k1 <<= w1;

  k2 <<= w1;

}

  }

}

//------------------------------------------------------------------------------

static unsigned int GetPolyonimos( unsigned int n, PolyonimoList *dest )

{

  if (n==1) AddToList(dest,CreatePolyonimo(1,1,1));

  else

  {

PolyonimoList prev;

unsigned int np = GetPolyonimos(n-1,&prev);

for (size_t i=0; i<np; i++) AddExtensions(prev[i],dest);

  }

  return (unsigned int) dest->size();

}

//------------------------------------------------------------------------------

static unsigned int CountPolyonimos( unsigned int n )

{

  PolyonimoList dummy;

  return GetPolyonimos(n,&dummy);

}

//------------------------------------------------------------------------------

#pragma comment (lib,"winmm.lib")

static int milliTime() { return timeGetTime(); }

//------------------------------------------------------------------------------

int __stdcall WinMain(HINSTANCE hInst, HINSTANCE hInstPrev, LPSTR cmdLine, int nCmdShow)

{

  int k = 12;

  int t = milliTime();

  int n = CountPolyonimos(k);

  t = milliTime()-t;

  char s[100];

  sprintf(s,"%d: %d (%d msec)",k,n,t);

  MessageBoxA(NULL,s,"",0);

  return 0;

}

Code: Selecteer alles

import Data.List



sizeBoard = 8



solution1 = maxInfo (placeNext 1 [[]])

	where 

		maxInfo = foldl (\(m,s) t -> if length t > m then (length t, t) else (m,s)) (0,[])

		placeNext c p | c > sizeBoard = p

					  | otherwise = placeNext (c+1) (addPiece c p)

		

threatens (x,y) = queenThreats ++ knightThreats

	where

		queenThreats  = rookThreats ++ bishopThreats

		rookThreats   = [(x,n) | n <- [1..(y-1)]]

		bishopThreats = [(x-n,y-n) | n <- [1..(y-1)], x-n > 0] ++ 

						[(x+n,y-n) | n <- [1..(y-1)], x+n <= sizeBoard]

		knightThreats = [(x-2, y-1), (x+2, y-1), (x-1, y-2), (x+1, y-2)]

				  

addPiece nextCol placed = placed ++ [(x, nextCol) : p | p <- placed, x <- [1..sizeBoard], not $ any (`elem` p) (threatens (x, nextCol))]

Code: Selecteer alles

#een solution is een list met per rij de index waar een queen staan

#indien die index -100 is wordt er op die rij geen queen gezet

def freeSquares(solution):

	free=[i for i in range(8) if i not in solution]

	for x in solution:

		y=solution.index(x)

		i=0

		#detecteer diagonalen

		while i<len(free):

			if (y-len(solution))==(x-free[i]) or (y-len(solution))==-1*(x-free[i]):

				del free[i]

			else:

				i+=1

		i=0

		#detecteer paarden sprong

		while i<len(free):

			if len(solution)>=2:

				if abs(free[i]-solution[-1])==2 or abs(free[i]-solution[-2])==1:

					del free[i]

				else:

					i+=1

			else:

				if abs(free[i]-solution[-1])==2:

					del free[i]

				else:

					i+=1

	free.append(-100) #lege rij is altijd een mogelijkheid

	return free

def solve():	

	solutions=[[i] for i in range(8)]

	solutions.append([-100])#eerste rij ook leeglaten

	for j in range(7):

		newsolutions=[]

		for solution in solutions:

			free = freeSquares(solution)

			if len(free)>0:

				for square in free:

					temp=solution[:]

					temp.append(square)

					newsolutions.append(temp)

		solutions=newsolutions[:]

	return solutions

solutions=solve()

maximum=max([8-i.count(-100) for i in solutions])

print "Maximaal: ",maximum

for i in solutions:

	if 8-i.count(-100)==maximum:

		print i

		break

Code: Selecteer alles

from primes import primes 

def anagrams(s):

if s == "":

return [s]

else:

ans = []

for an in anagrams(s[1:]):

for pos in range(len(an)+1):

ans.append(an[:pos]+s[0]+an[pos:])

return ans

primes100000=primes(100000)

def test(n):

global primes100000

p=sorted([int(i) for i in anagrams(str(n)) if int(i) in primes100000 and int(i)>n])

if len(p)<3:

return []

solutions=[]

for i in range(len(p)-1):

for j in range(i+1,len(p)):

if p[i]-n==p[j]-p[i]:

if not str(n)+" "+str(p[i])+" "+str(p[j]) in solutions:

solutions.append(str(n)+" "+str(p[i])+" "+str(p[j]))

return solutions

n=0

for prime in primes100000:

if prime>9999:

#print prime

for t in test(prime):

print t

n+=1

print "Aantal: ",n

Code: Selecteer alles

from primes import primes 

def isPerm(a,b):

	return len([0 for i,j in zip(sorted([i for i in str(a)]),sorted([i for i in str(b)])) if i!=j])==0





p=primes(99999)

n=0

for i in range(len(p)):

	if p[i]>9999:

		for j in range(i+1,len(p)):

			if isPerm(p[i],p[j]):

				for k in range(j+1,len(p)):

					if isPerm(p[j],p[k]):

						if p[j]-p[i]==p[k]-p[j]:

							print p[i],p[j],p[k]

							n+=1

print n