Solved figure answer in text below by batch file - answer is below

February 18, 2019 at 14:03:09
Specs: Windows 10
The numbers 1 up to and including 8 must be put by the houses in the figure depicted below.
However, all adjacent house numbers must differ by more than 1. For example,
house b adjacent house numbers must be at least 1 or 2 or 6 or 7 or 8 (i.e., cannot be 3 or 5).


The question: How should the numbers be arranged in the circles of the net?

The answer is below. Write a batch file program to solve this puzzle. Pretty heady,eh?

         A
         7

B        C       D
4        1       3

E        F        G
6        8        5

         H
         2

Lots of for-in-do in octal?
for whiz kids only

edited by moderator: Added pre tags -Razor2.3


See More: figure answer in text below by batch file - answer is below

Reply ↓  Report •

✔ Best Answer
March 5, 2019 at 13:03:07
You know, for someone who claims to just getting started in the field of scripting/programming, the worst possible thing you could do to yourself is say, "I should start with batch script." The "language" wasn't designed so much as it was grown, like a tumor. Microsoft has plans to remove this cancerous growth, so you really should, at a minimum, move to Win10's official script language, PowerShell. There's also actual documentation and books to get you started.

On to the problem. There's only 8! = 40320 possible combinations. That's easily brute-forceable. Which is good, because while I'm sure there's an elegant way to do this, I'm not smart enough to figure it out. In which case, call me a brute, crack open your PowerShell, and consider the following:

$out = "`tA
`t{0}
B`tC`tD
{1}`t{2}`t{3}
E`tF`tG
{4}`t{5}`t{6}
`tH
`t{7}
"
#Globals are bad, but the easiest way to get around a PSv3 [ref] bug
[int[]]$elements = 1..8 

#Thankfully, getting all permutations is a solved problem
#From <a href="https://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer" target="_blank" rel="nofollow">https://stackoverflow.com/questions...</a>
filter Permute([int]$recursionDepth, [int]$maxDepth) {
  if ($recursionDepth -eq $maxDepth) {
    return , $elements.Clone() #Explicitly return array (pipeline management)
  } else {
    for ([int]$i = $recursionDepth; $i -le $maxDepth; ++$i) {
      Swap $recursionDepth $i
      Permute ($recursionDepth + 1) $maxDepth
      Swap $recursionDepth $i #Revert for next pass
    }
  }
}

function Swap([int]$a, [int]$b) {
  [int]$tmp = $elements[$a]
  $elements[$a] = $elements[$b]
  $elements[$b] = $tmp
}

function ValidPair([int]$a, [int]$b) { [Math]::Abs($a - $b) -ne 1 }

#Start of pipeline; start of work
Permute 0 ($elements.Length - 1) | 
 where {
   $(ValidPair $_[0] $_[2]) -and
   $(ValidPair $_[1] $_[2]) -and
   $(ValidPair $_[1] $_[4]) -and
   $(ValidPair $_[2] $_[3]) -and
   $(ValidPair $_[2] $_[5]) -and
   $(ValidPair $_[3] $_[6]) -and
   $(ValidPair $_[4] $_[5]) -and
   $(ValidPair $_[5] $_[6]) -and
   $(ValidPair $_[5] $_[7])
 } | 
 foreach { $out -f [Object[]]$_ } 

#Cleanup
del function:Swap, function:Permute, function:ValidPair
rv elements, out

Ignoring the output printout, total runtime is roughly 40 seconds on my system, and it gives me 1656 valid-at-first-glance solutions.

How To Ask Questions The Smart Way



#1
February 18, 2019 at 14:24:30
Skool homework - surely not....?

Reply ↓  Report •

#2
February 18, 2019 at 15:39:44
No - and the A and H should be over/under the C F column. It's ancient.

A C programmer did it way back when, but I never saw the source file

to see if it just spit out the answer, or if he actually computed it.

In my original submission, spaces got deleted, so the framework looked better

beforehand.


Reply ↓  Report •

#3
February 18, 2019 at 15:44:26
Fair enuff... Not being a programmer I would have failed at the first hurdle - if I even go that far...

Reply ↓  Report •

Related Solutions

#4
February 20, 2019 at 05:17:49
To solve this problem, only allowing each number once, would require some use of permutation,
starting with 12345678 and ending with 87654321. Big gaps in the middle between legitimate
combinations. Somewhere in the middle would be the combination that would be the answer.
Also, checking for a difference of 1, maybe use, for example, test answer = abs(4-2) = 2,
but also abs(2-4)=2, because -2 would be less than 2 for test requirement.
It would be a toughie. Anybody with a solution might have to wait three hours for the answer???
Also, for example, adjacent to B would be A, C, E and F.

message edited by drank2much


Reply ↓  Report •

#5
March 5, 2019 at 13:03:07
✔ Best Answer
You know, for someone who claims to just getting started in the field of scripting/programming, the worst possible thing you could do to yourself is say, "I should start with batch script." The "language" wasn't designed so much as it was grown, like a tumor. Microsoft has plans to remove this cancerous growth, so you really should, at a minimum, move to Win10's official script language, PowerShell. There's also actual documentation and books to get you started.

On to the problem. There's only 8! = 40320 possible combinations. That's easily brute-forceable. Which is good, because while I'm sure there's an elegant way to do this, I'm not smart enough to figure it out. In which case, call me a brute, crack open your PowerShell, and consider the following:

$out = "`tA
`t{0}
B`tC`tD
{1}`t{2}`t{3}
E`tF`tG
{4}`t{5}`t{6}
`tH
`t{7}
"
#Globals are bad, but the easiest way to get around a PSv3 [ref] bug
[int[]]$elements = 1..8 

#Thankfully, getting all permutations is a solved problem
#From <a href="https://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer" target="_blank" rel="nofollow">https://stackoverflow.com/questions...</a>
filter Permute([int]$recursionDepth, [int]$maxDepth) {
  if ($recursionDepth -eq $maxDepth) {
    return , $elements.Clone() #Explicitly return array (pipeline management)
  } else {
    for ([int]$i = $recursionDepth; $i -le $maxDepth; ++$i) {
      Swap $recursionDepth $i
      Permute ($recursionDepth + 1) $maxDepth
      Swap $recursionDepth $i #Revert for next pass
    }
  }
}

function Swap([int]$a, [int]$b) {
  [int]$tmp = $elements[$a]
  $elements[$a] = $elements[$b]
  $elements[$b] = $tmp
}

function ValidPair([int]$a, [int]$b) { [Math]::Abs($a - $b) -ne 1 }

#Start of pipeline; start of work
Permute 0 ($elements.Length - 1) | 
 where {
   $(ValidPair $_[0] $_[2]) -and
   $(ValidPair $_[1] $_[2]) -and
   $(ValidPair $_[1] $_[4]) -and
   $(ValidPair $_[2] $_[3]) -and
   $(ValidPair $_[2] $_[5]) -and
   $(ValidPair $_[3] $_[6]) -and
   $(ValidPair $_[4] $_[5]) -and
   $(ValidPair $_[5] $_[6]) -and
   $(ValidPair $_[5] $_[7])
 } | 
 foreach { $out -f [Object[]]$_ } 

#Cleanup
del function:Swap, function:Permute, function:ValidPair
rv elements, out

Ignoring the output printout, total runtime is roughly 40 seconds on my system, and it gives me 1656 valid-at-first-glance solutions.

How To Ask Questions The Smart Way


Reply ↓  Report •

#6
March 5, 2019 at 14:49:14
I think I'lll stick to Rosetta Stone type decodings..

Much simpler to follow....


Reply ↓  Report •

#7
March 5, 2019 at 16:22:40
It's easier to read if you actually paste it into PowerShell or PowerShell ISE, if just because of the syntax highlighting.

How To Ask Questions The Smart Way


Reply ↓  Report •

#8
March 5, 2019 at 16:38:51
I'm not going to try this out. Not going to go into power shell as I haven't yet, and I'm worried it may mess something else up on my computer. Appreciate, Should be only one answer, and it's reverse.
That's one heck of an effort. Kudos to you for sacrificing the time and energy and talent.

Reply ↓  Report •

#9
March 5, 2019 at 19:53:24
Are we missing a requirement? Here's 10 of those 1656 solutions returned by the script:
    A                   A
    1                   7
B   C   D           B   C   D
3   7   4           3   5   1
E   F   G           E   F   G
5   2   6           6   2   4
    H                   H
    8                   8

    A                   A
    6                   7
B   C   D           B   C   D
3   1   8           3   5   2
E   F   G           E   F   G
5   7   2           8   1   4
    H                   H
    4                   6

    A                   A
    8                   7
B   C   D           B   C   D
2   5   7           4   2   6
E   F   G           E   F   G
6   1   3           8   5   1
    H                   H
    4                   3

    A                   A
    7                   2
B   C   D           B   C   D
5   3   8           1   5   7
E   F   G           E   F   G
1   6   2           6   8   4
    H                   H
    4                   3

    A                   A
    6                   3
B   C   D           B   C   D
8   2   5           2   7   4
E   F   G           E   F   G
4   7   1           5   1   6
    H                   H
    3                   8

How To Ask Questions The Smart Way


Reply ↓  Report •

#10
March 5, 2019 at 20:57:58
Concerning upper leftmost diagram, first one:

On each side twice, there is an x, for example, on the top leftmost one,

B C
3 7
.\ /
. / \
E F
5 2

i.e. B is 3, F is 2, illegal. The diagonals count also.

also, C is 7, G is 6 - illegal

. O
.. / | \
. O---O---O
. | X | X |
. O---O---O
. \ | . /
. O
Where I put the x's, implies the diagonals. I said B must be checked with A,C,E, and F
C with A, B, D, E, F, G - The diagonals are a little longer, but they are considered adjacent.


Reply ↓  Report •

#11
March 5, 2019 at 21:18:47
Ah, diagonals. I was going by this line in the OP, where there were no diagonals: For example,
house b adjacent house numbers must be at least 1 or 2 or 6 or 7 or 8 (i.e., cannot be 3 or 5).

EDIT: Followup: So I changed the "where" block to this:

 where {
   for ([int]$i = 0; $i -le 6; ++$i) { if (!$(ValidPair $_[2] $_[$i])) { return $false }}
   for ([int]$i = 1; $i -le 7; ++$i) { if (!$(ValidPair $_[5] $_[$i])) { return $false }}
   $(ValidPair $_[0] $_[1]) -and
   $(ValidPair $_[0] $_[3]) -and
   $(ValidPair $_[1] $_[4]) -and
   $(ValidPair $_[3] $_[6]) -and
   $(ValidPair $_[7] $_[4]) -and
   $(ValidPair $_[7] $_[6])
 } | 

It lowered the run time to near 30 seconds (string formatting is expensive) and returned four answers. The provided answer and its mirrors along both axes.

How To Ask Questions The Smart Way

message edited by Razor2.3


Reply ↓  Report •

#12
March 8, 2019 at 19:36:10
You got it - good going. One answer, it's mirror image, and upside down, and it's mirror image.

-7-----7
413 314
685 586
-2-----2

-2-----2
685 586
413 314
-7-----7

Every time I put in multiple spaces, they get reduced to one, and my diagrams get hosed up, so I used dashes where needed. Are these your four answers? How about entering the entire program here, as it is now completed.

Never mind, but thanks for your effort. You accomplished a toughie. I took your program plus changes, and saved it and backed it up. There are a few guys here who are really talented. They are certainly not obligated to put in their free time and effort.

message edited by drank2much


Reply ↓  Report •

#13
March 9, 2019 at 09:00:13
drank2much: Every time I put in multiple spaces, they get reduced to one, and my diagrams get hosed up
That's what pre tags are for. Switches to a monospaced font, and prevents collapsing of whitespace. So useful, you can insert them here by using the last icon just above the reply textbox.

How To Ask Questions The Smart Way


Reply ↓  Report •

#14
March 9, 2019 at 10:57:59
will try this in a week or so

i5-6600K[delid]@4.8GHz/4.4GHz cache/@1.408v | 2x4GB Crucial-DDR4-2400CL17@14-15-15-28 1T 3000MHz@1.4v | Sapphire Nitro+ SE RX 590 8GB@1525Mhz core@1.0v/2260MHz@1500MHz timings BiosModded


Reply ↓  Report •

#15
March 21, 2019 at 08:31:05
ouch, can't do it. I just keep losing track of where to to what.

this is what i have so far, i need it to loop back around after finding a single -1 value in one of the 8 fields and try again...


output:

start:16:27:04.77
end:=16:27:05.08

        A
        1

B       C       D
3       5       7

E       F       G
8       -1      2

        H
        4

@echo off&setlocal enabledelayedexpansion
:presets
echo start:%time%
set list1=A,B,C,D,E,F,G,H
set list2=1,2,3,4,5,6,7,8
for /d %%a in (!list1!) do set House%%a=-1
for /d %%a in (!list2!) do set Value%%a=0
::adjacent houses
set listA=B,C,D
set listAl=3
set listB=A,C,E,F
set listBl=4
set listC=A,B,D,E,F,G
set listCl=6
set listD=A,C,F,G
set listDl=4
set listE=B,C,F,H
set listEl=4
set listF=B,C,D,E,G,H
set listFl=6
set listG=C,D,F,H
set listGl=4
set listH=E,F,G
set listHl=3
:loop1
for /d %%a in (%list1%) do (
	call :loop2 "%%a"
)
:finish
echo end:=%time%
echo.
echo 	A
echo		!HouseA!
echo.
echo B	C	D
echo !HouseB!	!HouseC!	!HouseD!
echo.
echo E	F	G
echo !HouseE!	!HouseF!	!HouseG!
echo.
echo 	H
echo		!HouseH!
echo.
pause
exit/b
:loop2
for /d %%A in (%list2%) do (
	call :loop3 "%~1" "%%A"
	if !succes!==!list%~1l! (
		set Value%%A=1
		set House%~1=%%A
		exit/b
	) else (
		echo do something important here, rip brain
	)
)
exit/b
:loop3
set succes=0
for /d %%1 in (!list%~1!) do (
	if !Value%~2!==0 (
		set/a temphigh=%~2+1
		set/a templow=%~2-1
		if not !House%%1!==!temphigh! (
			if not !House%%1!==!templow! (
				if not !House%%1!==%~2 (
					set/a succes+=1
				)
			)
		)
	)
)
exit/b

i5-6600K[delid]@4.7GHz/4.4GHz cache/@1.392v | 2x4GB Crucial-DDR4-2400CL17@14-15-15-28 1T 3000MHz@1.4v | Sapphire Nitro+ SE RX 590 8GB@1525Mhz core@1.0v/2260MHz@1500MHz timings BiosModded


Reply ↓  Report •

#16
March 21, 2019 at 08:41:37
Yegads!! Amazing to be trying this in batch... A few of you guys are geniuses, to be sure. Taking on outrageous tasks in batch, no less. And if you don't make it, it's still "hats off" for giving it the old college try,
where others just don't even try after saying "no way, Jose!". I'm certainly a noway Joser on this one.- and
others that you guys do in your sleep.

Reply ↓  Report •

Ask Question