string text = "blah blah blah\nyak yak yak";
using (StreamWriter outfile = new StreamWriter("c:/dev/out.txt"))
{
outfile.Write(text);
}
SE Radio 736: Sahil Walia on Apache Iceberg
1 week ago
Thursday, June 7, 2012
C# Dump to Text File
Tuesday, May 22, 2012
Tuesday, March 20, 2012
Knight's Tour in C - Tom Wells
Finally, presenting the Knight's Tour in C - code by Tom Wells of tomwells.org.
Get the source from gitgub - git://github.com/drshade/knights-tour.git
Get the source from gitgub - git://github.com/drshade/knights-tour.git
#include
#include
#include
#include
#include
#define BOARDSIZE 5
#define THREADS 4
char referenceboard[BOARDSIZE * BOARDSIZE];
int solutions = 0, attempts = 0;
typedef struct { int x; int y; int valid; } position;
position new_position(int x, int y) { position p; p.x = x; p.y = y; p.valid = 1; return p; }
/* Code below unashamedly stolen from 'somewhere' to calculate difference (delta) between 2 timeval's */
int timeval_subtract (result, x, y) struct timeval *result, *x, *y;
{
if (x->tv_usec < y->tv_usec) {
int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;
y->tv_usec -= 1000000 * nsec;
y->tv_sec += nsec;
}
if (x->tv_usec - y->tv_usec > 1000000) {
int nsec = (x->tv_usec - y->tv_usec) / 1000000;
y->tv_usec += 1000000 * nsec;
y->tv_sec -= nsec;
}
result->tv_sec = x->tv_sec - y->tv_sec;
result->tv_usec = x->tv_usec - y->tv_usec;
return x->tv_sec < y->tv_sec;
}
void hunt(position start, int depth, const char board[BOARDSIZE*BOARDSIZE])
{
attempts++;
char my_board[BOARDSIZE * BOARDSIZE];
memcpy(my_board, board, sizeof(my_board));
my_board[(start.x * BOARDSIZE) + start.y] = 1;
if (depth + 1 == BOARDSIZE * BOARDSIZE)
{
// Solution found
//
solutions++;
printf(".");
fflush(stdout);
if (solutions % 10000 == 0) printf("Found %d solutions so far...\n", solutions);
return;
}
// Determine possible moves
//
position possibles[8] = {
new_position(start.x - 1, start.y - 2), new_position(start.x - 2, start.y - 1),
new_position(start.x + 1, start.y - 2), new_position(start.x + 2, start.y - 1),
new_position(start.x + 1, start.y + 2), new_position(start.x + 2, start.y + 1),
new_position(start.x - 1, start.y + 2), new_position(start.x - 2, start.y + 1),
};
int x;
for (x = 0; x < 8; ++x)
{
// If position is within the bounds of the board, and not already taken, then hunt some more!
//
position* p = &possibles[x];
if (p->x >= 0 && p->y >= 0 && p->x < BOARDSIZE && p->y < BOARDSIZE && board[(p->x * BOARDSIZE) + p->y] == 0)
hunt(*p, depth + 1, my_board);
}
}
void* thread_start_function(void* arg)
{
int thread_num = (int)arg;
printf("[%d]", thread_num);
int skip = 0;
int x, y;
for (x = 0; x < BOARDSIZE; ++x)
for (y = 0; y < BOARDSIZE; ++y)
{
if (skip == thread_num)
{
printf("(%d,%d)", x, y);
hunt (new_position(x, y), 0, referenceboard);
}
skip++;
if (skip >= THREADS) skip = 0;
}
printf("<%d>", thread_num);
return 0;
}
int main(int argc, const char * argv[])
{
struct timeval start;
gettimeofday(&start, 0);
// Set board to zero
//
memset(referenceboard, 0, sizeof(referenceboard));
#if THREADS > 1
printf("[Multithreaded (%d)]\n", THREADS);
pthread_t threads[THREADS];
int x;
for (x = 0; x < THREADS; ++x)
pthread_create(&threads[x], NULL, thread_start_function, x);
for (x = 0; x < THREADS; ++x)
pthread_join(threads[x], NULL);
#else
printf("[Single threaded]\n");
int x, y;
for (x = 0; x < BOARDSIZE; ++x)
for (y = 0; y < BOARDSIZE; ++y)
{
printf("(%d,%d)", x, y);
hunt (new_position(x, y), 0, referenceboard);
}
#endif
struct timeval end;
gettimeofday(&end, 0);
struct timeval delta;
timeval_subtract(&delta, &end, &start);
printf("Found %d solutions in %ld.%ds (%d moves)\n", solutions, delta.tv_sec, delta.tv_usec, attempts);
return 0;
}
Sunday, March 18, 2012
Knight's Tour in Scala by Gary Pampara
Here is the Knight's Tour problem solved in Scala, by Gary Pampara.
object Problem { type Board = Array[Array[Boolean]] val boardsize = 5 val startingPositions = for { x <- (0 until boardsize) ; y <- (0 until boardsize) } yield (x,y) def legalasmoves(x: Int, y: Int) = { val possibles = List((x-1, y-2), (x-2,y-1), (x+1, y-2), (x+2, y-1), (x+1, y+2), (x+2, y+1), (x-1, y+2), (x-2, y+1)) possibles.filter(a => a._1 >= 0 && a._2 >=0 && a._1 < boardsize && a._2 < boardsize) }
def clone(x: Board) = { // Thanks Java :( val y = Array.fill(boardsize, boardsize)(true) for { i <- (0 until boardsize) j <- (0 until boardsize) } y(i)(j) = x(i)(j) y }
def availablemove(x: Int, y: Int, b: Board) = b(x)(y) def hunt(startx: Int, starty: Int, b: Board)(hist: List[(Int, Int)])(f: List[(Int, Int)] => Unit): Unit = { b(startx)(starty) = false if (hist.length == boardsize * boardsize) { print(".") f(hist) } else { val availablemoves = legalmoves(startx, starty).filter(a => availablemove(a._1, a._2, b)) availablemoves.foreach(a => hunt(a._1, a._2, clone(b))((a._1,a._2) :: hist)(f)) } }
def main(args: Array[String]) { val start = new java.util.Date() var solutions = List[List[(Int, Int)]]() def addSolution(a: List[(Int, Int)]) = { solutions = a :: solutions } startingPositions.par.foreach(pos => { print("(" + pos._1 + "," + pos._2 + ")") hunt(pos._1, pos._2, Array.fill(boardsize, boardsize)(true))(List((pos._1, pos._2)))(addSolution) }) val end = new java.util.Date() println((end.getTime() - start.getTime())/1000.0) println("Solutions: " + solutions.length) }}Friday, February 17, 2012
pyGForce - Force Directed Graphs in Python with NetWorkX and pyGTK
The latest little piece of handiwork that I would like to present is...
PyGForce - a force-directed graphing library that leverages current python technologies
- NetworkX python graph theory library
- python wrapper for GTK, pyGTK.
https://github.com/davidbarkhuizen/pygforce.git
End.
PyGForce - a force-directed graphing library that leverages current python technologies
- NetworkX python graph theory library
- python wrapper for GTK, pyGTK.
https://github.com/davidbarkhuizen/pygforce.git
 |
| Basic Force-Directed Graph |
 |
| And with Node Labelling |
End.
Saturday, January 28, 2012
Aggregated APDU List
python/pyscard EMV tool pack
@ https://github.com/davidbarkhuizen/py_emv_utils
Cheef's Grand APDU List Smartcard Selected Information APDU list
@ https://github.com/davidbarkhuizen/py_emv_utils
Cheef's Grand APDU List Smartcard Selected Information APDU list
#------------+------------------------+------------------------+----------------------+--------------------------------+ |ClaIns P1 P2|Lc Send Data |Le Recv Data | Specification | Description | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 04 | ISO 7816-9 6.3 | DEACTIVATE FILE | | A0 04 00 00 00 | 3GPP TS 11.11 | INVALIDATE | | A0 04 00 00 00 | SAGEM SCT U34 6.15 | INVALIDATE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 0D xx xx 08 xxxx xxxx xxxx xxxx | SAGEM SCT U34 | VERIFY TRANSPORT CODE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 0C | ISO 7816-4 7.3.6 | ERASE RECORD (S) | | 80 0C 00 xx xx | SAGEM SCT U34 8.1.2 | CHECK (flash) | | 80 0C 01 xx xx | SAGEM SCT U34 8.1.2 | CHECK (EEPROM) | | 80 0C 02 xx xx | SAGEM SCT U34 8.1.2 | CHECK (checksum of file) | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 0E | ISO 7816-4 8.2.4 | ERASE BINARY | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 10 | ISO 7816-7 | PERFORM SCQL OPERATION | | 00 10 00 80 xx table name, ... | ISO 7816-7 7.1 | CREATE TABLE | | 00 10 00 81 xx view name, table name | ISO 7816-7 7.2 | CREATE VIEW | | 00 10 00 82 xx dictionary name | ISO 7816-7 7.3 | CREATE DICTIONARY | | 00 10 00 83 xx table name | ISO 7816-7 7.4 | DROP TABLE | | 00 10 00 84 xx view or dictionary | ISO 7816-7 7.5 | DROP VIEW | | 00 10 00 85 xx privileges | ISO 7816-7 7.6 | GRANT | | 00 10 00 86 xx privileges | ISO 7816-7 7.7 | REVOKE | | 00 10 00 87 xx data | ISO 7816-7 7.8 | DECLARE CURSOR | | 00 10 00 88 | ISO 7816-7 7.9 | OPEN | | 00 10 00 89 | ISO 7816-7 7.10 | NEXT | | 00 10 00 8A xx D, fixing N (columns)| ISO 7816-7 7.11 | FETCH | | 00 10 00 8B xx D, fixing N (columns)| ISO 7816-7 7.12 | FETCH NEXT | | 00 10 00 8C xx data | ISO 7816-7 7.13 | INSERT | | 00 10 00 8D xx data | ISO 7816-7 7.14 | UPDATE | | 00 10 00 8E | ISO 7816-7 7.15 | DELETE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 12 | ISO 7816-7 | PERFORM TRANSACTION OPERATION | | 00 12 00 80 | ISO 7816-7 8.2.1 | BEGIN | | 00 12 00 81 | ISO 7816-7 8.2.2 | COMMIT | | 00 12 00 82 | ISO 7816-7 8.2.3 | ROLLBACK | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 14 | ISO 7816-7 | PERFORM USER OPERATION | | 00 14 00 80 xx User ID, ... | ISO 7816-7 9.2.1 | PRESENT USER | | 00 14 00 81 xx User ID, profile, ... | ISO 7816-7 9.2.2 | CREATE USER | | 00 14 00 82 xx User ID | ISO 7816-7 9.2.3 | DELETE USER | | 80 14 xx xx 00 | GEMPLUS MPCOS-EMV | Switch Protocol | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 84 16 00 00 xx MAC | VSDC | CARD BLOCK | | 80 16 0X 00 05 xxxx xxxx xx | GEMPLUS MPCOS-EMV | Freeze Access Conditions | | 84 16 0X 00 08 xxxx xxxx xxxx xxxx | GEMPLUS MPCOS-EMV | Freeze Access Conditions | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 84 18 00 00 xx MAC | VSDC | APPLICATION UNBLOCK | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 84 1E 00 00 xx MAC | VSDC | APPLICATION BLOCK | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 20 | ISO 7816-4 8.5.5 | VERIFY | | 00 20 00 80 08 xxxx xxxx xxxx xxxx | VSDC | VERIFY (Transaction PIN data) | | A0 20 00 xx 08 CHV Value | 3GPP TS 11.11 | VERIFY | | A0 20 00 xx 08 CHV Value | SAGEM SCT U34 6.10 | VERIFY | | 80 20 00 xx 08 ADM Value | SAGEM SCT U34 8.1.4 | VERIFY ADM | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 21 00 xx 08 ADM Value | SAGEM SCT U34 8.1.4 | VERIFY ADM | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 22 | ISO 7816-4 8.5.10 | MANAGE SECURITY ENVIRONMENT | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 24 | ISO 7816-4 8.5.6 | CHANGE CHV | | 84 24 00 00 xx PIN data + MAC | VSDC | PIN CHANGE/UNBLOCK | | A0 24 00 xx 10 Old CHV, New CHV | 3GPP TS 11.11 | CHANGE CHV | | A0 24 00 xx 10 Old CHV, New CHV | SAGEM SCT U34 6.11 | CHANGE CHV | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 26 | ISO 7816-4 8.5.8 | DISABLE CHV1 | | A0 26 00 01 08 CHV1 value | 3GPP TS 11.11 | DISABLE CHV1 | | A0 26 00 01 08 CHV1 value | SAGEM SCT U32 6.12 | DISABLE CHV1 | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 28 | ISO 7816-4 8.5.7 | ENABLE CHV1 | | A0 28 00 01 08 CHV1 value | 3GPP TS 11.11 | ENABLE CHV1 | | A0 28 00 01 08 CHV1 value | SAGEM SCT U34 6.13 | ENABLE CHV1 | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 2A | ISO 7816-8 5.2 | PERFORM SECURITY OPERATION | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 2C | ISO 7816-4 8.5.9 | UNBLOCK CHV | | A0 2C 00 xx 10 Unblock CHV(PUK), New CHV | 3GPP TS 11.11 | UNBLOCK CHV | | A0 2C 00 xx 10 Unblock CHV(PUK), New CHV | SAGEM SCT U34 6.14 | UNBLOCK CHV | +------------+------------------------+------------------------+----------------------+--------------------------------+ | A0 2E 00 0# 01 Data | 3GPP TS 11.11 | WRITE CODE STATUS | +------------+------------------------+------------------------+----------------------+--------------------------------+ | A0 32 00 00 03 Value to be added. | 3GPP TS 11.11 | INCREASE | | A0 32 00 00 03 Value to be added. | SAGEM SCT U34 6.9 | INCREASE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 39 | | java Authentificate User Comman| +------------+------------------------+------------------------+----------------------+--------------------------------+ | 44 | ISO 7816-9 6.4 | ACTIVATE FILE | | A0 44 00 00 00 | 3GPP TS 11.11 | REHABILIDATE | | A0 44 00 00 00 | SAGEM SCT U34 6.16 | REHABILIDATE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 46 | ISO 7816-8 5.1 | GENERATE ASYMMETRIC KEY PAIR | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 50 xx xx 08 Host challenge 00 | GlobalPlatform | INITIALIZE UPDATE then [C0] | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 70 | ISO 7816-4 8.1.2 | MANAGE CHANNEL | | 00 70 xx xx xx | GlobalPlatform | MANAGE CHANNEL | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 78 00 03 xx | GlobalPlatform | END R-MAC SESSION | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 7A xx 01 xx Data and C-MAC, if needed | GlobalPlatform | BEGIN R-MAC SESSION | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 82 | ISO 7816-4 8.5.3 | EXTERNAL AUTHENTICATE | | 84 82 00 00 10 Host cryptogram and MAC | GlobalPlatform | EXTERNAL AUTHENTICATE | | 84 82 00 00 0A Authentication-related data | VSDC | EXTERNAL AUTHENTICATE | | 00 82 00 xx 06 Manual | GEMPLUS MPCOS-EMV | EXTERNAL AUTHENTICATE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 84 | ISO 7816-4 8.5.2 | GET CHALLENGE | | 00 84 00 00 08 Rnd Num | VSDC | GET CHALLENGE | | 00 84 xx xx 08 Rnd Num | GEMPLUS MPCOS-EMV | GET CHALLENGE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 86 | ISO 7816-4 8.5.4 | GENERAL AUTHENTICATE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 88 | ISO 7816-4 8.5.1 | INTERNAL AUTHENTICATE | | 00 88 XX xx 0A Manual | GEMPLUS MPCOS-EMV | INTERNAL AUTHENTICATE | | A0 88 00 00 10 RAND : Rnd num xx SRES( 4B) , Kc (8B) | 3GPP TS 11.11 | RUN GSM ALGORITHM | | A0 88 00 00 10 RAND : Rnd num xx SRES( 4B) , Kc (8B) | SAGEM SCT U34 6.17 | RUN GSM ALGORITHM | +------------+------------------------+------------------------+----------------------+--------------------------------+ | A0 | ISO 7816-4 8.2.5 | SEARCH BINARY | +------------+------------------------+------------------------+----------------------+--------------------------------+ | A2 | ISO 7816-4 8.3.5 | SEEK | | A0 A2 00 xx xx Pattern xx | 3GPP TS 11.11 | SEEK | | A0 A2 00 xx xx Pattern xx | SAGEM SCT U34 6.8 | SEEK | +------------+------------------------+------------------------+----------------------+--------------------------------+ | A4 | ISO 7816-4 8.1.1 | SELECT | | 00 A4 04 00 xx AID 00 | GlobalPlatform | SELECT | | 00 A4 00 xx xx File ID || Name 00 Manual | VSDC | SELECT | | A0 A4 00 00 02 File ID | 3GPP TS 11.11 | SELECT | | A0 A4 00 00 02 File ID | SAGEM SCT U34 6.1 | SELECT | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 A8 00 00 00 00 | VSDC | GET PROCESSING OPTIONS | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 AE 00 xx Transaction-related data | VSDC | | +------------+------------------------+------------------------+----------------------+--------------------------------+ | B0 | ISO 7816-4 8.2.1 | READ BINARY | | 00 B0 xx xx xx | GEMPLUS MPCOS-EMV | READ BINARY | | A0 B0 xx xx xx | 3GPP TS 11.11 | READ BINARY | | A0 B0 xx xx xx | SAGEM SCT U34 6.4 | READ BINARY | +------------+------------------------+------------------------+----------------------+--------------------------------+ | B2 | ISO 7816-4 8.3.1 | READ RECORD | | 00 B2 xx 00 | VSDC | READ RECORD | | A0 B2 xx xx xx | 3GPP TS 11.11 | READ RECORD | | A0 B2 xx xx xx | SAGEM SCT U34 6.6 | READ RECORD | +------------+------------------------+------------------------+----------------------+--------------------------------+ | B4 | | java Component Data | +------------+------------------------+------------------------+----------------------+--------------------------------+ | B8 | | java Create Applet | +------------+------------------------+------------------------+----------------------+--------------------------------+ | BA | | java CAP end | +------------+------------------------+------------------------+----------------------+--------------------------------+ | BC | | java Component end | +------------+------------------------+------------------------+----------------------+--------------------------------+ | BE 04 Data | GEMPLUS GemClub-MEMO | READ | +------------+------------------------+------------------------+----------------------+--------------------------------+ | C0 | ISO 7816-4 8.6.1 | GET RESPONSE | | 00 C0 1C Key Info | GlobalPlatform | GET RESPONSE | | 00 C0 00 00 00 | VSDC | GET RESPONSE | | 80 C0 00 00 xx | GEMPLUS MPCOS-EMV | Get Info on Get Response | | 80 C0 02 A0 08 Chip SN | GEMPLUS MPCOS-EMV | Get Info | | 80 C0 02 A1 08 Card SN | GEMPLUS MPCOS-EMV | Get Info | | 80 C0 02 A2 08 Issuer SN | GEMPLUS MPCOS-EMV | Get Info | | 80 C0 02 A3 04 Iss.Ref.N | GEMPLUS MPCOS-EMV | Get Info | | 80 C0 02 A4 0D Chip Inf | GEMPLUS MPCOS-EMV | Get Info | | 80 C0 02 A5 xx Keys | GEMPLUS MPCOS-EMV | Get Info | | 80 C0 02 A6 02 Last DF/EF | GEMPLUS MPCOS-EMV | Get Info | | A0 C0 00 00 xx | 3GPP TS 11.11 | GET RESPONSE | | A0 C0 00 00 xx | SAGEM SCT U34 6.3 | GET RESPONSE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | C2 | ISO 7816-4 8.6.2 | ENVELOPE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | C4 | | java Delete Applets | +------------+------------------------+------------------------+----------------------+--------------------------------+ | CA | ISO 7816-4 8.4.1 | GET DATA | | 00 CA 00 xx xx MAC, if present | GlobalPlatform | GET DATA | | 80 CA xx xx xx | VSDC | GET DATA | +------------+------------------------+------------------------+----------------------+--------------------------------+ | D0 | ISO 7816-4 8.2.2 | WRITE BINARY | | 80 D0 xx xx xx Data to be written in EEPROM | VSDC | LOAD STRUCTURE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | D2 | ISO 7816-4 8.3.2 | WRITE RECORD | +------------+------------------------+------------------------+----------------------+--------------------------------+ | D6 | ISO 7816-4 8.2.3 | UPDATE BINARY | | A0 D6 xx xx xx Data to be written in EEPROM | 3GPP TS 11.11 | UPDATE BINARY | | A0 D6 xx xx xx Data to be written in EEPROM | SAGEM SCT U34 6.5 | UPDATE BINARY | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 D8 xx xx xx KEY Date (and MAC) 00 | GlobalPlatform | PUT KEY | | D8 | EMV | Set Card Status(personalization| +------------+------------------------+------------------------+----------------------+--------------------------------+ | DA | ISO 7816-4 8.4.2 | PUT DATA | | 00 DA xx xx xx Data | VSDC | PUT DATA | +------------+------------------------+------------------------+----------------------+--------------------------------+ | DC | ISO 7816-4 | UPDATE RECORD | | 00 DC xx xx xx Data (and MAC) | VSDC | UPDATE RECORD | | A0 DC xx xx xx Data to be written in EEPROM | 3GPP TS 11.11 | UPDATE RECORD | | A0 DC xx xx xx Data to be written in EEPROM | SAGEM SCT U34 6.7 | UPDATE RECORD | +------------+------------------------+------------------------+----------------------+--------------------------------+ | DE 04 Data | GEMPLUS GemClub-MEMO | UPDATE | | A0 DE 00 00 03 Data | 3GPP TS 11.11 | LOAD AoC(SICAP) | +------------+------------------------+------------------------+----------------------+--------------------------------+ | E0 | ISO 7816-9 6.1 | CREATE FILE | | 80 E0 02 00 0C Manual | GEMPLUS MPCOS-EMV | CREATE FILE | | 80 E0 xx xx xx FCI length | 3GPP TS 11.11 | CREATE FILE | | 80 E0 xx xx xx FCI length | SAGEM SCT U34 | CREATE FILE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | E2 | ISO 7816-4 8.3.4 | APPEND RECORD | | 80 E2 00 00 xx Record (and MAC) | GlobalPlatform | APPEND RECORD | | 00 E2 00 00 xx Record | VSDC | APPEND RECORD | | 00 E2 00 00 xx Record | GEMPLUS MPCOS-EMV | APPEND RECORD | | 00 E2 00 00 xx Record | 3GPP TS 11.11 | APPEND RECORD | +------------+------------------------+------------------------+----------------------+--------------------------------+ | E4 | ISO 7816-9 6.2 | DELETE FILE | | 80 E4 00 00 xx TLV coded name | GlobalPlatform | DELETE FILE | | A0 E4 00 00 02 xx xx | 3GPP TS 11.11 | DELETE FILE | +------------+------------------------+------------------------+----------------------+--------------------------------+ | E6 | ISO 7816-9 6.5 | TERMINATE DF | | 80 E6 xx 00 xx Manual | GlobalPlatform | INSTALL | | A0 E6 xx xx 00 | 3GPP TS 11.11 | LOCK RECORD | +------------+------------------------+------------------------+----------------------+--------------------------------+ | E8 | ISO 7816-9 6.6 | TERMINATE EF | | 80 E8 00 00 xx Record | GlobalPlatform | LOAD | | A0 E8 00 xx 10 Data | 3GPP TS 11.11 | READ DIRECTORY | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 EA 00 00 xx Data | 3GPP TS 11.11 | CREATE BINARY | | 80 EA 00 00 xx Data | SAGEM SCT U34 | CREATE BINARY | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 EE 00 xx 00 | VSDC | WRITE LOCK | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 F0 xx xx xx AID of Application (and MAC) | GlobalPlatform | SET STATUS | +------------+------------------------+------------------------+----------------------+--------------------------------+ | A0 F2 00 00 xx | 3GPP TS 11.11 | GET STATUS | | A0 F2 00 00 xx | SAGEM SCT U34 6.2 | GET STATUS | | 80 F2 xx xx | GlobalPlatform | GET STATUS | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 F8 xx xx xx | SAGEM SCT U34 8.1.1 | DIR | +------------+------------------------+------------------------+----------------------+--------------------------------+ | A0 FA 00 00 00 | 3GPP TS 11.11 | SLEEP | | A0 FA 00 00 00 | SAGEM SCT U34 6.18 | SLEEP | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 FB xx xx xx | SAGEM SCT U34 8.1.1 | DIR | +------------+------------------------+------------------------+----------------------+--------------------------------+ | 80 FC xx xx 10 | SAGEM SCT U34 8.1.3 | READ INFO | +------------+------------------------+------------------------+----------------------+--------------------------------+ | FE | ISO 7816-9 6.7 | TERMINATE CARD USAGE | | 80 FE xx xx 00 | SAGEM SCT U34 | BLOW FUSE | +------------+------------------------+------------------------+----------------------+--------------------------------+
Tuesday, January 10, 2012
Dynamite Knight's Tour in F# - Tom Wells
An Ungodly Fast Solution in F# to the Knights Tour
I would suggest that you consider coding the solution up in F#, as my friend Tom Wells has done. His solution finds all solutions for the 5x5 board in under 5 minutes.
I would suggest that you consider coding the solution up in F#, as my friend Tom Wells has done. His solution finds all solutions for the 5x5 board in under 5 minutes.
let boardsize = 7
// Setup board in 2d array setting all elements to true
// ___________________
// |0,4|1,4|2,4|3,4|4,4| (x,y)
// |0,3|1,3|2,3|3,3|4,3|
// |0,2|1,2|2,2|3,2|4,2|
// |0,1|1,1|2,1|3,1|4,1|
// |0,0|1,0|2,0|3,0|4,0|
// -------------------
//
let referenceboard = Array2D.init boardsize boardsize (fun x y -> true)
let legalmoves x y =
// Generate every move (impossible or not)
//
let possibles = [(x - 1, y - 2); (x - 2, y - 1);
(x + 1, y - 2); (x + 2, y - 1);
(x + 1, y + 2); (x + 2, y + 1);
(x - 1, y + 2); (x - 2, y + 1);]
// Prune the ones falling outside of the board
//
possibles |> List.filter (fun (x, y) -> x >= 0 && y >= 0 && x < boardsize && y < boardsize)
// Is a particular move still available to us? ie not already used
//
let availablemove x y (board : bool[,]) =
board.[x,y] = true
let rec hunt startx starty (board : bool[,]) (history : List<(int*int)>) foundsolutionfunc =
// Mark the position we're at as being taken
//
board.[startx,starty] <- false
// Check if we have a solution (ie we've covered the entire board)
//
if history.Length = boardsize * boardsize then
foundsolutionfunc (history) |> ignore
else
// Calculate the set of available moves from this point, filtering by positions which we've already used
//
let availablemoves = legalmoves startx starty |> List.filter (fun (x,y) -> availablemove x y board)
// For each available move, recurse
//
for (x,y) in availablemoves do
hunt x y (Array2D.copy board) ((x,y) :: history) foundsolutionfunc
[<EntryPoint>]
let main args =
let starttime = System.DateTime.Now
let solutions = new System.Collections.Generic.List<System.Tuple<int,int>>()
for x in seq { 0 .. Array2D.length1 referenceboard - 1 } do
for y in seq { 0 .. Array2D.length2 referenceboard - 1 } do
printf "(%d,%d)" x y
hunt x y (Array2D.copy referenceboard) [(x,y)] (fun solution ->
solutions.Add(new System.Tuple<int,int>(x,y))
printf "."
)
let endtime = System.DateTime.Now
printfn "\nFound %d solutions (took %03f seconds)" solutions.Count (endtime - starttime).TotalSeconds
printfn "Enter to quit"
System.Console.In.ReadLine() |> ignore
0
Subscribe to:
Posts (Atom)